Learning to Understand: Identifying Interactions via the Möbius Transform

Thank you for your review. We believe that some aspects of this review may be based on misunderstandings, which may have resulted in some false or misleading statements in your review. In this rebuttal we will provide additional information and clarification that will hopefully resolve your concerns, and help underscore the significance of this work.

Point 1 and 3: In your first point you said: "it is not clear how the significant interactions could be recovered at the end after obtaining the required samples". You also asked in your third point "That being said, it is not clear how exactly the interactions are obtained; as the authors stated in the paper, the naive computation of all Mobius coefficients includes exponentially many parameters; given the samples, what interactions should be included as significant?"

A: The purpose of this manuscript is precisely to show how a small number of the interactions (which correspond to Mobius coefficients) can be recovered. A Mobius coefficient corresponds to an interaction, because it represents the joint effect of a given set of inputs that only occurs when all those given inputs are active.

Theorem 1 shows that our algorithm recover the $K$ non-zero Mobius coefficients using the SMT algorithm. In this noise-free context "significant" means non-zero. Theorem $2$ considers the setting where we have $K$ large non-zero Mobius coefficients, but there is also noise, which corresponds to many relatively small interactions between inputs. In this context the SMT algorithm recovers the $K$ large interactions, which are the ones we call "significant".

Point 2: You have also made the following claim. "Aside from the clarification, though having an innovative approach and some interesting results, the method seems to have little applicability in real-world applications; one reason for doing so is one of the main assumptions of the method of having only K nonzero interactions (= K nonzero Mobius coefficient). For explainability, as defined, for instance, in SHAP, it is typically the case that we have many nonzero interactions since it is rare that the interactions among a feature subset will go to zero (given the way we compute the interactions). This implies that in most cases, we have a very large K of nonzero interactions, and this would make the sparse Mobius transformation impractical."

A: This is an important distinction. You are correct in your statement that in nearly all practical settings, there will be a large number of nonzero interactions (or Mobius coefficients). However, what has been discovered by ourselves and many others is that a relatively small number of Mobius coefficients are needed to faithfully represent the functions learned by well-trained machine learning algorithms. For reference on a diverse set of machine learning algorithms and applications, we refer the review to Figures 2 and 6 in our paper, Figure 3 in [1], and Figure 3 in [2]. Furthermore, as shown Figure 2 in our paper and Figures 4, 7-9 in [1], these significant interactions (high magnitude Mobius coefficients) tend to be low-order. Under the interpretation that insignificant interactions are treated as noise (an interpretation also made by [1] and [2]), we provided in this work a noise-robust algorithm for extracting the K significant interactions up to order t, with the precise statement of this result in Theorem 5.2.

[1] Ren et al. Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs. ICLR, 2024.

[2] Li et al. Does a Neural Network Really Encode Symbolic Concepts? ICML, 2023.

Point 4: "Last but not least, in explainability, we usually seek the most influential features and the most important interactions (rather than all feature importance or significant interactions); the paper seems to merely focus on computing all the significant interactions rather than the most important ones, and in explainability, this is not essentially sought and seems impractical due to many nonzero interactions."

A: We could not make sense of this comment. To be clear, this paper aims to accomplish exactly what you state is the essential goal of explainability. Please feel free to clarify.

Note on Clarity and Narrative: You have mentioned that you felt that this work was "difficult to follow and does not have a clear storyline". This comment was rather surprising to us, as we have received contradictory feedback from others (including both of the other reviews). We believe the paper is organized in such a way as to naturally explain the different parts of the algorithm, and we have included many figures to aid in explanation. If you have any concrete suggestions on how to improve clarity and the narrative, we welcome it.

Extending beyond binary functions: The Mobius transform can certainly be extended beyond the binary inputs, but there remains significant work to extend this algorithm to the $q$-ary case. Critically, we have used group testing designs and results from group testing. Results in non-binary group testing are very limited. In addition, it is unclear how one would extend other core parts of the algorithm, such as the sampling, to the $q$-ary case for $q> 2$.

1. $b = O(\log(K))$. In the appendix, we consider the constant $\eta = \frac{2^b}{K}$, which we refer to as the inverse load factor. Theoretically, if we carry through the density evolution analysis, it is possible to find the minimal $\eta$ to ensure convergence of the message passing asymptotically. This is a relatively small number. for instance, $\eta = 0.4073$ suffices for $C=3$ (see [1], Table 1 for a full analysis). In practice, for the real, finite-regime experiments we find $b = \mathrm{ceil}(\log(K))$ typically works well, though it is possible to tune the parameter and adjust $b$, which can be helpful, especially in noisy settings, and if we don't know $K$ a priori, we can increase $b$ until the the algorithm works. (In fact, it is possible to re-use data from smaller values of $b$ to re-run with larger $b$ to expedite this process)

[1] Li, Xiao, Joseph K. Bradley, Sameer Pawar, and Kannan Ramchandran. "SPRIGHT: A fast and robust framework for sparse Walsh-Hadamard transform." arXiv preprint arXiv:1508.06336 (2015).

2. Fig. 5 focuses on comparisons with second order methods, and reveals the massive computational advantage of our method as compared to those baselines. In Fig. 6, we have chosen to focus on first order comparisons because these experiments are run at a reasonably large scale where running higher order methods begins to get computationally difficult. It is likely that higher order methods would perform closely to our methods, just with an increased computational burden.

Question about projection: In this case truncation is not the same thing as a sparse projection onto low order terms, though it is not obvious. The reason this is not the case is because the Mobius transform is a representation in terms of an AND function basis. In fact, the Shapley value, and other interaction indices are usually different projections into the Mobius AND basis. This is different from a Fourier transform, which uses an XOR basis. In the case of the Fourier transform, due to orthonormality, your assertion is correct, and simply "zeroing-out" higher order terms is a projection.

Thank you for the clarification. The authors addressed my concerns properly. About 2), while Figure 5 compares second-order methods, it does not show how faithfulness increases with the increase of computational budgets. Practically, we may be interested in the cost of reasonable reconstruction (e.g., 90%). I believe this kind of analysis and second-order version of Fig.6 (with a small dataset) will improve the completeness of this work (just a comment, not asking for an immediate response).

Overall, I'll maintain my score for now. There seems to be a correction/improvement in the proofs pointed out by Reviewer jcxh, so my final score can be affected by the consequences of the discussion between the Authors and Reviewer jcxh.

Dear reviewer jcxh. Thank you for your through and helpful review. We are delighted that you are impressed with our contributions towards efficient Mobius Transform computation, and agree with our assumptions of low-degree interactions and sparsity. We believe that our work will in time be appreciated as a significant step forward for Mobius transform computation.

Proof Correction

We have corrected the technical issue you highlighted, and will include that information in a separate comment.

Literature Review

Regarding the literature review, we are very happy to see these other references, particularly the modern ones. It is exciting to see a community of people working on these types of problems, and these are excellent examples that highlight the practical points of our assumptions. These papers will bolster our current Section 2, and add credibility to our work. We will also certainly include the Harsanyi reference.

Final note

Reviewer vNmZ has raised concerns about the validity of our assumptions for practical settings. We have made the case that these are in fact interesting and important assumptions to consider. Given your expertise in this area, we would welcome your contribution to the discussion.

Here we include a sketch of the argument for the noiseless part of Theorem 2, which focuses on the case $\left\lvert \mathbf{k}\right\rvert \leq t$ (the rest of Theorem 2 is unchanged).

(1) Prove $\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_Z \implies \mathrm{Type}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_Z$.

(2+3) Prove $\mathrm{Pr}\left(\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j})) = \mathrm{Type}(\mathbf{U}\_c(\mathbf{j})) \right) \rightarrow 1$.

Proof of (1)

The proof is identical to above.

Proof of (2+3)

The proof is the same, with one notable exception. In the low-degree case, $p^*$ may not always exist. Using the results in citation [47] from the paper, and the union bound that already exists in the proof in Appendix C.7.2, we show that $p^*$ exists with probability approaching $1$.

We separate the proof into three parts:

(1) Prove $\mathrm{Detect}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_Z \implies \mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_Z$.

(2) Prove $\mathrm{Detect}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_S \implies \mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_S$.

(3) Prove $\mathrm{Detect}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_M \implies \mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_M$.

Consider the subsampling group $\mathbf{U}_{c}(\mathbf{j})$ for some fixed $c, \mathbf{j}$. We first consider the case where $\left\lvert \mathbf{k}\right\rvert$ is not restricted, and denote the set of non-zero indices $\mathbf{k}_1, \dotsc, \mathbf{k}_K$ as $\mathcal{N}$.

Proof of (1)

Let $\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_Z$, and for contradiction's sake assume $\mathrm{Type}(\mathbf{U}\_c(\mathbf{j})) \neq \mathcal{H}\_Z$.

$

    \mathrm{Detect}(\mathbf{U}\_c(\mathbf{j}))  = \mathcal{H}\_Z \implies \sum_{\mathbf{k} \leq \bar{\mathbf{d}}\_p\; \text{ s.t. } \mathbf{H}\_c \mathbf{k} = \mathbf{j}} F(\mathbf{k}) = 0 \;\forall p,

$

Since $\mathrm{Type}(\mathbf{U}_c(\mathbf{j})) \neq \mathcal{H}_Z$, we have that $\mathcal{N} \cap \\{ \mathbf{k} : \mathbf{H}_c \mathbf{k} = \mathbf{j}\\} \neq \emptyset$. Thus, if we consider the above implication for the case of $p=0$ and noting that $\mathbf{d}_0 = \boldsymbol{0}$, we have:

$

\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j}))  = \mathcal{H}\_Z \implies \sum\_{\mathcal{N} \cap \\{ \mathbf{k} : \mathbf{H}\_c \mathbf{k} = \mathbf{j}\\}} F(\mathbf{k}) = 0

$

But considering the no cancellation condition, this is impossible, thus proving (1).

Proof of (2)

Note that the converse of (1) is true (the proof is immediate). Thus, proving $\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_S \implies \neg(\mathrm{Type}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_M$) is the same as proving (2). We will again use the method of contradiction, and assume $\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_S$ and $\mathrm{Type}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_M$.

$

    \mathrm{Detect}(\mathbf{U}\_c(\mathbf{j}))  = \mathcal{H}\_S \implies U_{c,p}(\mathbf{j}) \in \\{0, U\_{c,0}(\mathbf{j})\\}  \; \forall p > 1.

$

Note that by our assumption, $U_{c,0}(\mathbf{j}) \neq 0$. By our assumption that $\mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_M$, we must have $\left\lvert \mathcal{N} \cap \{ \mathbf{k} : \mathbf{H}_c \mathbf{k} = \mathbf{j}\} \neq \emptyset \right\rvert \geq 2$. Choose $\mathbf{k}\_1, \mathbf{k}\_2 \in \mathcal{N} \cap \\{ \mathbf{k} : \mathbf{H}\_c \mathbf{k} = \mathbf{j}\\}$. Given our choice of $\mathbf{d}\_p$ $\exists p^* > 1$ s.t. only one of $\mathbf{k}\_1$ or $\mathbf{k}\_2 \leq \bar{\mathbf{d}}\_{p^*}$. Without loss of generality we will assume $\mathbf{k}\_2 \leq \bar{\mathbf{d}}\_{p^*}$ and $\mathbf{k}\_1 \nleq \bar{\mathbf{d}}\_{p^*}$. Now, define the following sets: \begin{eqnarray} \mathcal{J}_0 &=& \mathcal{N} \cap \{ \mathbf{k} : \mathbf{H}_c \mathbf{k} = \mathbf{j}\} \\ \mathcal{J}_{p^} &=& \mathcal{N} \cap \{ \mathbf{k} : \mathbf{H}_c \mathbf{k} = \mathbf{j} ; \mathbf{k} \leq \bar{\mathbf{d}}_{p^} \} \end{eqnarray} We know $\mathbf{k}\_2 \in \mathcal{J}\_{p^*}$ and $\mathbf{k\_1} \in \mathcal{J}\_0\setminus \mathcal{J}\_{p^*}$, thus $\left\lvert \mathcal{J}\_{p^*}\right\rvert \geq 1$ and $\left\lvert \mathcal{J}\_0\setminus \mathcal{J}\_{p^*}\right\rvert \geq 1$. With this, we can show that the implication above cannot be satisfied.

Case 1: $U_{c,p^*}(\mathbf{j}) = 0$.

$

U_{c,p^*}(\mathbf{j}) = 0 \implies \sum_{\mathbf{k} \in \mathcal{J}_p^*} F(\mathbf{k}) = 0.

$

Since $\mathcal{J}_p^*$ is not empty, from our distributional assumption, the above sum cannot be $0$.

Case 2: $U_{c,p^*} = U_{c,0}(\mathbf{j})$.

$

    U_{c,0}(\mathbf{j}) - U_{c,p^*}(\mathbf{j}) = 0 \implies \sum_{\mathbf{k} \in \mathcal{J}_0 \setminus \mathcal{J}_p^*} F(\mathbf{k}) = 0.

$

Since $\mathcal{J}_0 \setminus \mathcal{J}_p^*$ is not empty, from our distributional assumption, the above sum cannot be $0$. This implies that $\mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_M$ must be false, thus proving (2).

Proof of (3):

Since we have a converse for (1), a converse for (2) suffices to prove (3). The converse follows below: \begin{eqnarray} \mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_S \implies \exists \mathbf{k}^* \text{ s.t. } U_{c,p} \in \{0, F(\mathbf{k^*})\},;\forall p. \end{eqnarray} Since $F(\mathbf{k^*}) \neq 0$, we have $U_{c,0}(\mathbf{j}) \neq 0$ and all entries of $\mathbf{U}_{c}(\mathbf{j})$ are either $F(\mathbf{k^*})$ or $0$. Thus, $\mathrm{Detect}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_S$.

Updated Proof

We would like to thank the reviewer for identifying this issue. After a thorough analysis, we see that the previous proof in Appendix C.7.1 (which applies to the noiseless case only) was only for multitons of order $2$, and pathological examples as you described can be constructed for higher order multitons. We have resolved this issue with the full proof included below. As the reviewer has suggested, we have introduced a very mild probabilistic assumption on the values of the non-zero coefficients, so that they may not be completely arbitrary.

The proof for our noisy result, which uses a more complicated approach and requires additional samples (along with already restricting $F(\mathbf{k})$) is not impacted by this issue.

Assumption 2.3 (No Cancellation) Suppose the non-zero values $F(\mathbf{k}_1)$, ... , $F$\mathbf{k}_K$$ are sampled from a joint distribution $\mathbb{P}$ that satisfies the following condition:

$

\sum_{i \in S}F(\mathbf{k}_i) \neq 0, \;\forall S \subseteq [K], \; S \neq \emptyset.

$

Assumption 2.3 is quite mild, and there are many classes of $\mathbb{P}$ that satisfy this assumption. For example, any absolutely continuous $\mathbb{P}$ satisfies Assumption 2.3 a. s.

Proof.

For simplicity let $\mathbf{F}$ represent a $K$ dimensional random vector containing $F$ \mathbf{k}_i $$ at index $i$. Let the set $\mathcal{R}(S, \alpha) = \\{\mathbf{F} : \sum_{i \in S}F(\mathbf{k}\_i) = \alpha\\}$. Since $\mathbb{P}$ is absolutely continuous, a density $p$ exists such that:

$

\mathbb{P}(\mathbf{F} \in \mathcal{R}(S,\alpha))  = \int_{\mathcal{R(S,\alpha)}}dp.

$

However, $\mathrm{dim}(\mathcal{R}(S,\alpha)) = K - \left\lvert S \right\rvert$. Thus for $S \neq \emptyset$, $\mathcal{R}(S,\alpha)$ has Lebesgue measure zero, thus

$

\mathrm{Pr}\left(\sum_{i \in S} F(\mathbf{k}_i) = 0\right) = \mathbb{P}(\mathbf{F} \in \mathcal{R}(S,0)) = \int_{\mathcal{R}(S,0)} dp = 0.

$

Thank you for your response. The added assumption and proof address my concern for the singleton detection algorithm. I hope this assumption and proof, as well as the mentioned literature review for the sparsity of Mobius transform, will be properly stated in the final version of the paper if the paper is accepted. Furthermore, I have raised my score accordingly.