Learning to Understand: Identifying Interactions via the Möbius Transform
Authors: Justin Singh Kang
Yigit Efe Erginbas
Landon Butler
Ramtin Pedarsani
Kannan Ramchandran
Venue: NeurIPS 2024 poster (2024)
Keywords: Shapley Value
Importance Scores
Transforms
Signal Processing
Interactions
Group Testing
Primary area: interpretability_and_explainability
TL;DR: Learning explainable representations of functions efficiently using ideas from signal processing and group testing

Abstract: One of the key challenges in machine learning is to find interpretable representations of learned functions. The Möbius transform is essential for this purpose, as its coefficients correspond to unique *importance scores* for *sets of input variables*. This transform is closely related to widely used game-theoretic notions of importance like the *Shapley* and *Bhanzaf value*, but it also captures crucial higher-order interactions. Although computing the Möbius Transform of a function with $n$ inputs involves $2^n$ coefficients, it becomes tractable when the function is *sparse* and of *low-degree* as we show is the case for many real-world functions. Under these conditions, the complexity of the transform computation is significantly reduced. When there are $K$ non-zero coefficients, our algorithm recovers the Möbius transform in $O(Kn)$ samples and $O(Kn^2)$ time asymptotically under certain assumptions, the first non-adaptive algorithm to do so. We also uncover a surprising connection between group testing and the Möbius transform. For functions where all interactions involve at most $t$ inputs, we use group testing results to compute the Möbius transform with $O(Kt\log n)$ sample complexity and $O(K\mathrm{poly}(n))$ time.  A robust version of this algorithm withstands noise and maintains this complexity. This marks the first $n$ sub-linear query complexity, noise-tolerant algorithm for the Möbius transform. While our algorithms are conceptualized in an idealized setting, they indicate that the Möbius transform is a potent tool for interpreting deep learning models.

Learning to Understand:
Identifying Interactions via the Möbius Transform
Justin Singh Kang UC Berkeley justin mrrreiiknnn@bbeeeeey.cco edu
Yigit Efe Erginbas
Landon Butler UC Berkeley landonb@berkeley. edu
UC Berkeley erginbas@berkeley.ro edu
Ramtin Pedarsani
Kannan Ramchandran
UC Santa Barbara ramtin@ece. ucsb. edu
UC Berkeley
kannanr@berkeley.co edu
Abstract
One of the key challenges in machine learning is find interpretable representa- tions of learned functions. The Möbius transform is essential for this purpose. as coefficients correspond to unique importance scores for sets of input variables. This transform is closcly related to widely used game-theorett, notions of impor- tance like the Shapley and Bhanzaf value, but it also captures erucial higher-order interactions. Although computing the Möbius Transform of function with n in- puts involves 2 coefficients, it becomes tractable when the function is sparse and of low degree as we show is the case for many real-world functions. Under these conditions, the complexity of the transform computation significantly reduced. When there are K non-zero coefficients, our algorithm recovers the Möbius trans- form O(Kn) samples and O(K)²² time asymptotically under certain assump- tions, the first non-adaptive algorithm to do We also uncover surprising nection between group testing and the Möbius transform. For functions where all interactions involve most inputs, Möbius transform with OKKt log n) sample complexity and O K poly(n)) time. A robust version of this algorithm withstands noise and maintains this complexity. This marks the first n sub-linear query complexity, noise-tolerant algorithm for the Möbius transform. In several examples, observe that representations generated via sparse Möbius transform are up to twice as faithful to the original function, as compared Shapley and Banzhaf values, while using the same number of terms.
group testing results to compute the
Introduction
As machine learning models become increasingly complex, our ability to interpret them has not kept pace. A natural question to ask is: What is the most fundamental interpretable representation of the functions
learn? The Shapley value [1] concept from cooperative game theory, has become a popular way to interpret model predictions (2) by assigning importance scores to individual inputs such as features, data samples tokens. This value represents the weighted average marginal contribution of an input, quantifying the change in the function's 's output when that input is included.
Recent research has expanded the scope of interpretability to encompass sets of inputs [3] 4. capturing the collective influence of input combinations and their synergies on model predictions. Central to this advancement is the Möbius Transform [5), mathematical transformation that projects functions onto fundamental interpretable basis known in game theory as the unanimity function basis.
The Möbius transform has more powerful and nuanced explanation capability than the Shapley value. Consider a sentiment analysis model (BERT [6] fine-tuned on the IMDB dataset (7) explained
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Her
Her acting
Her acting Fails to impress
Her acting
Her actiing
Her acting Ineerr Fails to Imppess
Her acting
Her acting
acting
acting fails to impress
Ineeer Fails to impress
falls
fails to impress
+
fails to Impress
fails to impress
Falls
to impress
to Immpress
+0.98
0.00
0.80
0.96
-0.59
U.87
0.75
0.58
+2.59
Ordee
Lst Order
2nd Order
ard Order and Highor
Her
Her acting
Her
Her acting
Her acting fails impress
acting
acting
Fails
fails
fails
fails
to
to Impress
to
impress
impress
impress
0.96
0.00
0.96
+0.599
0.58
sv
Her
sv
acting
sv(
never
sv]
fails
SV
to
SV impress
+0.05
+0.01
+0.32
+0.19
+0.10
+0.31
Figure 1: The movie review "Her acting never fails to impress" is passed into BERT language model fine-tuned to do sentiment analysis [8] Presented are 1st, 2nd and 3rd order Möbius coefficients, with positive interactions in green and negative in red computed via (I). The coefficients explain how groups words influence BERT's perception of sentiment. For instance, while never and fails have strong negative sentiments individually, when combined, they impose profound positive sentiment. In the second row, the word never is deleted, resulting in a large change in sentiment. In contrast, the Shapley values of each word SV(-), presented at the bottom of the figure, are less informative.
using both Shapley values and the Möbius transform as depicted in Fig. The model's s objective is to classify the sentiment of the review as positive or negative. The Mōbius transform assigns score all word subsets within a sentence. For instance, the sentence "Her acting never fails to impress" each subset of words is evaluated-posittee interactions receive positive scores, and negative interactions, negative scores. Summing these scores yields the overall sentiment +0.98. This granular analysis reveals the model's understanding of linguistic constructs like double negatives, as seen in the interaction between never and fails, and the inherent positivity of words like impress. When the word never is masked, interactions involving never are excluded, shifting the sentiment negatively to -0.96.
This level of detail is not readily available with the Shapley value, which assigns scores individual words without considering their interplay. The value of the Möbius transform is apparent, but given its complex structure, is it possible to compute efficiently?
In general, to compute a Möbius transform over n features requires 2n inferences (masking over all 2 approach similar to that of the Fast subsets of features), as well n22 time using a supports in the range of 8000 words-per-prome Fourier Transform (FFT) algorithm. GPT-4 currently and context length will continue to grow with new architectures (9. Running inference 28000 times is not even close to possible, and even if you could, 28000 coefficients are hardly interpretable! In Fig, see that many coefficients are insignificant. This is typical. The solution the computational problem is to just focus on computing the largest Möbius interactions and ignore the small ones. Is this possible in a systematic way? Yes assumingg that only K Möbius coefficients (which K values are sigmificant is unknown) are non-zero, our algorithm enables us to intelligently query the model to significantly reduce the number of samples of that are required to OKK) with O(Kn²) time. We also explore the regime where the non-zero interactions occur between at most inputs, with & showing that only O(K' log(n)) samples are required O(K poly(n)) time. We also have a robust algorithm that allows for some noise in the sampling process, effectively relaxing the constraint that the insignificant coefficients are exactly zero while maintaining the same complexities.
Defining the Möbius Transform We define value function for model with n inputs across subsets S C [ni] denoted as S(S). The construction of this function varies based on the model: in Fig. D words not in S might be masked or omitted. In other cases, we might take a conditional expectation over words not in S. To facilitate later discussion on group testing, we express the function as f 2 + R. where f(S) fmm with S
{i: m, = 1}. The relationship between f 2g R

---

and its Möbius transform F :22 + IR is characterized by the forward and inverse transforms:
Inverse: f(m)=
Σ F(k),
Forward:
F(k)
(-11)t(k-m f(m),
(I)
kmm
msk
where k S m means that A; S 1/4 Vi. This transform acts as bridge, connecting various importance metrics, which can be expressed as projections onto a subset the Möbius basis. The Shapley value (i) and Banzhaf value (Z( for feature is elegantly represented within this framework:
(V
Σ k=
F(k),
BZ(1) Σ
2 F(k).
k.
These relationships are foundational to the definition of the Shapley and Bhanzaf values themselves. The left equality appears as Eq. 10 in Lloyd Shapley's 's original report from 1952 [ where the concept of Shapley value was first introduced and is central to his derivation of closed-form expression.
1.1 Related Works and Applications
This work is inspired by the literature on sparse Fourier transforms, which began with 10 The sparse Boolean Fourier (Hadamard) transform 13 [4] is most relevant.
11 12
Group Testing This manuscript establishes a strong connection between the interaction identification problem and group testing (15). Group testing was first described by Dorfman [T6), who noted that when testing soldiers for syphilis,, pooling blood samples from many soldiers, and testing the pooled blood samples reduced the total number of tests needed. [17] is the first work to exploit group testing in feature selection/impootancee problem, using group testing matrix in their algorithm. [88 also mentions group testing in relation to Shapley values.
Möbius Transform Möbius transforms S have been studied in the pseudo- pseudo-Boolean (set) function literature, and dates back to at least [9]. 20 develops framework for computing sparse transforms of pseudo-Boolean functions. They do not directly consider the Möbius transform we define it, but one can apply their algorithm to compute a sparse transform in O(nK) adaptive samples and O(K²n) time. In the sparse and noiseless setting, our algorithm improves on this by being fully non- adaptive and having lower time complexity in most non-trivial settings. (20) does not consider the important low degree setting and does not consider robustness to noise (approximate sparsity), which are critical aspects of this work. In (2I), the authors show that a classifier satisfying certain properties can be well represented by sparse and low degree Möbius transform.
Explainability proposes model explanation via pseudo pseudo-Boolean functions approximated by Shapley values, effectively utilizing only first-order Möbius coefficients. Constructing these functions,
25 especially for generative models with complex outputs 126 27 28). is an ongoing research area. [3] presents the Shapley interaction index (STII), scoring interactions up size introduces the Faithful Shapley Interaction index (FSI), which computes scores via projection onto up to th order Möbius coefficients. 29] develops methods for computing FSI, STII, and other interaction indices. The relationship between the Möbius transform, FSI, STII, Shapley value, and Banzhaf value is detailed in Appendix[A]
122 23
24
For sets smaller than I, STII are exactly Möbius coefficients.
Data Valuation In data valuation determine a fair price [30 or to curate more efficient dataset [31. A feature of this problem is the high cost of getting a sample since we need to determine the accuracy of our model when trained on different subsets of data, making sample complexity of critical importance. [32 [3 try to approximate
18 the goal to assign an importance score to data, either to
this by looking at the accuracy of partially trained models, though this introduces sampling noise.
1.2 Main Contributions
Our algorithm and proofs are deeply interdisciplinary, and the contributions of this paper are theoretical. We use modern ideas spanning across signal processing, algebra, coding and information theory, and group testing to address the important problem of interpretability at the forefront of machine learning. The main contributions of this manuscript are:
For a function with K non-zero Möbius coefficients chosen uniformly at random, the Sparse Möbius Transform (SMT) algorithm exactly recovers the transform F in O(Kn) samples and OKK²) time in the limit + oo with K growing at most as 2nd with ò < $
3

---

XGBoost Breast Cancer Diagnoels
BERT Sentiment Analysis
BERT Multiple Choice
1,00
1.00
1.00
0.75
0.75
0.75
0:25
0.00
0.00
0.00
Sparity
Sparityy
Syumstt
1.00
0:72
8:50
0.50
0.25
0:25
0.25
0.00
0.00
0.00
Degree
Degire
Degice
Figure 2: These plots are strong indicators that sparsity and low degree assumptions are worthy of consideration. We consider three different learning tasks. The left-most plot shows results from an XGBoost 34] model used for breast cancer diagnosis. The middle plot shows results from word- level sentiment analysis task using BERT model [8] like in Fig. T The right- most plot shows results from a multiple choice question and answer task also using a BERT model [35] Error bars represent standard deviation over 10 different instances. Details for each setting the number of features n R/ 20, for which it is possible to perform the full Möbius transform. On the top row, we plot achievable faithfulness R² function of sparsity. We observe that in all cases, faithfulness approaching requires only a few thousand Möbius coefficients, motivating our sparsity assumption. The bottom row of plots considers achievable faithfulness vs. degree, i.c., what R²² can be achieved using only Möbius coefficients F up to given degree. Here we observe that nearly all cases, low degree coefficients suffice to get quite small R², motivating our low degree assumption.
in Appendix In all cases,
We develop formal connection with group testing and present a variant of SMT that works when all non-zero interactions are low order. the maximum order of interaction / = O(n where 0.409 then time with error going to zero as n - oo with growing K.
compute the Möbius transform in ((Ktlog(m) samples in O(K poly(n))
Using robust group testing. we develop an algorithm that, under certain assumptions, computes the Möbius transform in O(Ktlog(n) samples, with vanishing error - do with growing K.
In addition to our asymptotic analysis, we provide synthetic and real-world experiments that verify that our algorithm performs well even in the finite n regime. Furthermore, our results are non non-adaptive meaning that all samples can be computed in parallel. Code has been made publicly available !
Notation Lowercase boldface x and uppercase boldface X denote vectors and matrices respectively. x 2 y means that 2; Z ys Vi. Multiplication is always standard real field multiplication, but addition between two elements in Z, should be interpreted as logical OR V. We define subtraction, of x y for 2 y by standard real field subtraction. corresponds bit-wise negation for Boolean x. and x @ y represents an element-wise multiplication.
2 Understanding Assumptions: Sparsity and Low Degree
Computing the forward transform typically requires sampling all 2n input combinations, an infeasible task, even for modest n. For an arbitrary f. one cannot do any better. In fact, the same is true of the Shapley value, yet, computational tools like SHAP [2] exist because practical functions of interest are not arbitrary. To help understand this, we define faithfulness for an explanation model
Ra
Ilf / where Ilf]]
Σ mEZa
f(m)²
Note that this corresponds to the standard definition of R² in statistics when f is zero-mean, and generally define f such that this is the case. A good explanation model should have high R?.

---

a succinct representation, and most importantly. be easily computed. For the Möbius transform, we aim to learn coefficients Fkk) efficiently and construct f using the inverse transform ① With no restrictions on F(k) we achieve R 1, but this fails to meet simplicity criterion. Fortunately, many real-world functions are sparse-only a few F(k) coefficients need to be non- zero to yield R² ~ 1. Fig. considers three machine learning models for breast cancer diagnosis, sentiment analysis, and question answering respectively. In all three cases, we find that we only need small number of Möbius coefficients to achieve R ~ 1. Furthermore, real-world functions are low degree, such that those small number of non-zero coefficients satisfy [k| S for some small This results in much more compact representation and as we shall see, also enables efficient computation.
Fig. 2 validates our assumption for the deep-learning models mentioned above. Prior research [36] 21), have presented empirical and theoretical evidence that sparsity and low degree properties are common well-trained models. Further investigation of the spectral properties of explanation functions could be a promising avenue for future research. Our formal statements of assumptions are given below:
Assumption 2.1. (K Uniform Interactions) / 2 + has Möbius transform of the following form: k1..... kx are sampled uniformly at random from Z. and have F(k;) # O, Vi E [K], but F(k) = for all other k E zz.
Assumption 2.2. (K t-Degree Interactions) f 26 + R has Möbius transform of the following
form: kg..... kg are sampled uniformly from {k: k| S f, k E 22}, ). and have F(k,) + 0, Vi e
[K]. but F F(k) = 0 other k E ZЛ.
Assumption Limitations By assuming that the non-zero coefficients are uncorrelated and uniformly distributed, we aim to understand the fundamental difficulty in learning sparse Möbius transform. Correlation between non-zero coefficients means identifying one coefficient would tell us information about the locations of the others, which can be further exploited. The existence of a scheme that works well under the uniform setting suggests that it is possible to solve the problem where correlations between interactions exist. We also consider exact sparsity in our assumptions. In practice, these "zero" coefficients may instead have some small magnitude. We investigate this in Section 4
3 Algorithm Overview
Algorithm Sparse Möbius Transform (SMT)
Input: H. E zbxa for c 1, ,....., C
3.1 Subsampling and Aliasing
D₂ E Z for c I....,C C
First we perform functional subsampling: For some b < n we construct u according to
3: f(k) + 0 0k; K+ 0:
4: for to C' do
5: for p = 1 to P do
u(e) fmme, e z/e me Σ2 (4)
6: Ve. f Hie + dep
ve 31
where have the freedom to choose my- Critically, the Möbius transform of u, de- noted U. is related to F' via the well-known signal processing phenomenon of aliasing:
7: Ue.p FastMobius (ue.p)
8: end for
9: end for
10: S = f(c.j,, Detect (U.(i) = Hs(k, e)}
U(i)
Σ F(k),
(5)
11: while [S] > do
12: for k,.j,,v) E S with k E K. do
kEA()
13:
F(k) <- v; IC +- KU (k)
where A(j) corresponds to aliasing set de- termined by my. Fig. 3 shows this subsam- pling procedure
14:
for é' to C do
15:
res + U. (H ((k - Dyrk)
"sparsified" version of our sentiment analysis example using differ-
16:
U. -- res
17:
end for end for
ent me. Our goal is to choose me such that the non-zero values of F(k) are uniformly
18:
19: Update S: Re-rum Detect (-)
spread across the aliasing sets, since that
20:
end while
makes them easier to recover. If only single k with non-zero F(k) ends up an aliasing set A(j), we call it a singleton. In Fig. 3 our first subsampling generated two singletons, while our second one generated only one. Maximizing the number of singletons is one of our goals since we can ultimately use those singletons to construct the Möbius transform. this work, we have determined two different subsampling procedures that perform well under our two assumptions:
21: Output: F
5

---

Non-zero Interactions
Transform
Aliasing
Harr
Her
actinng
acting
DI
(00) S(110011)
(000
Zeroonn
Insver
[Hover
(01)
I(LIOLI))
U1(11]
F(ks)
Singleton
Gails
Eails
(I
I(LLIO1I)
(1(10)
F(ku)
Multiton
(11)
S(1II1I1)
(111]
F(kg) + Fiki)
impress
impress
Her
Her
Aliasing
acting
acting
M2(00) ((111100)
U2(00)
F(k, F(k.) F(ks)
Inever
vg(01) S(111101)
Ug(01)
F(k1)
Fails
foils
to
vg(10) = S(L111I0)
Us(10)
=
0
Impress
Imppress
(1(11) S(111111)
(2(11)
Figure 3: This figure considers "sparsified" version of the Möbius coefficients depicted in Fig keeping only the largest 4 depicted. Two different sampling choices are shown, well the resulting aliasing sets. In the first aliasing set, there is one zeroton, two singletons, and one multiton. In the second aliasing set, there
zerotons, singleton, and one multiton.
Lemma 3.1. Choose m H'E, which results in A(j) [k Hk j]. H is chosen as follows:
1. Under Assumption
2.1 we choose H = [Ixxc0pnnb]] or any column permutation of this matrix.
2. Under Assumption 2.2 with t (nn)) for some S 0.409, there exists matrix H chosen from b rows of a near constant column weight group testing matrix.
With the given H, non-zero indices are mapped to the 2 sampling sets A(j) independently and uniformly at random asymptotically, thus maximizing the number of singletons when + (log(())
In both cases the matrix H can be viewed part of group testing matrix. This is explicit under Assumption 2.2 but under Assumption 2.1 can be viewed as part of an individual testing matrix, where elements because they achieve an optimal rate asymptotically in their respective setting, We can think of rate the amount of information about k what get from the matrix product Hk (see [15] for formal definition). For example, if the matrix Hk was always the same for all k, then we would get little information about k from Hk, and we would say H has low rate. Conversely, if Hk is different for different k then the product Hk provides more information about k. Information theoretically, maximizing the rate of H can be thought of as maximizing the entropy [37] of Hk. It is this connection between rate and the randomness of the product Hk that enables us to prove Lemma 3.1
tested one-by-one. These matrices optimal in information thhooretcc sense
A detailed discussion of Lemma 3.1 is in Appendix C.2 with an enhanced version for independence across multiple H. as is required for our overall result. The proof of this lemma touches many areas of mathematics, including the theory of monoids, information theory, and optimal group testing.
3.2 Singleton Detection and Identification
Singletons are useful, but we cannot immediately use them to recover F(k). We first need to know that a given (j) a singleton. Secondly, we need identify the value of that singleton corresponds to. Section discusses both tasks. For now, we discuss the rest of the algorithm assuming that we can accomplish both tasks.
Sampling Group
Sampling Group
3.3 Message Passing to Resolve Collisions
00000 (01) (1
U (1L)
(2(00 U2(01)
(1010)
(1L
Since we don't know the non-zero indices be- forehand, collisions between multiple non-zero indices in the same aliasing are inevitable. These are called multitons. One approach to deal with these multitons is to repeat the procedure over again:
Shapkson
F(le
Fika
F(ki
F(ka)
Figure 4: Depiction of our peeling message passing algorithm for the samples in Fig. [ The singleton in (01) is subtracted (peeled) so we can resolve F(k2) from U, (11).
(e) = f(m = U.Ú) = Σ F(k), KEA.())

---

c=1...,,.. Each time, we get different aliasing sets (i) resulting in different singletons, and thus find different k with non-zero F(k). While this approach works, better approach combine this idea with message passing to use known non-zero indices and values (k, F(k)) to resolve these multitons and turn them into singletons. The type of message passing algorithm we use called graph peeling. The aliasing structure can be represented as bipartite graph. Each (i) is check node, and each non-zero coefficient F(k is a variable node. The variable node F (k) is connected to the check node (j) if H,k = j. Fig. 4 constructs this bipartite graph for the aliasing in Fig. Note that U1(11)= = F(2)) + F(k)) is a multiton; however, in the other sub-samping group U2(01) = F(k,) is singleton. Once resolve U2
simply subtract F (k,) from U1 (11), allowing us to create a new singleton, and extract F F(kg). The remaining values of F both appear as singletons resolve all 4 non-zero interactions F with only (7 unique)
in the first sampling group,
samples. Peeling algorithms were popularized in information and coding theory for decoding fountain
codes (38 and have since been applied variety of applications in communications (39] and signal
processing 13 40). They can be analyzed using density evolution theory [41), which we also use as part of our proof.
4 Singleton Detection and Identification
We have discussed how to subsample efficiently to maximize singletons and how to use message passing to recover as many coefficients as possible. Now we discuss (1) how to identify singletons and (2) how to determine the k' corresponding to the singleton. The following result is key:
Lemma 4.1. Consider H E E and f Z3 + R. and some d E 22. Uf the Möbius transform of u, and F is the Möbius transform of f we have:
u(() = 1 (H(2H)) > U(i)
Σ F(k).
kcd Hk-j
The proof can be found in Appendix C.4 The form of (6) allows us to shrink the aliasing set in a controlled way. Define de := On, and D. _=""" for some P P>l O. The 7th row of D is denoted de.p. p = 1...,.. P. Using these vectors, we construct C(P + 1) different subsampled functions de.pi
(e) f (H. + ve E Z/.
We compute the Möbius transform of each Wr.p denoted by Ue.p and construct a vector-valued function Ui( := [U,,0()..... (i)) The goal of singleton detection is to identify when Uz()) reduces to single term, and for what value k that term corresponds to. To do so, we define the Type (+):
Type (U)) Hz denotes a zeroton, for which there does not exist [kk o 0 s.t. HK = j. Type (U.(j) = Hs,(k, F()) denotes a singleton with only one k with F(k) o s.t. HK = j. 3. Type (i) = Hy denotes a multiton with more than one k with F() * S.t. Hk = j.
To describe our type estimation rule, we define the following ratios between elements of U.()):
De.p = 1 - Ui.((i)
(), p= I,.,,.
(8)
and construct the vector ye := [Ve,1, Ml. Then, our estimate for the type is given by
Hzz,
Ue(j) = Ye & {0, 13P
Detect (U.(i)) =
Hm.
(9)
(skk, F(k)),
Ye E 10.
By considering the definition of U. it is possible to show that if Type (U)(i) = Hs(k", F(k)) )). then y. D.k*. When we have singleton taking D. = I, and thus P = suffices to recover k". So long as the non-zero coefficients, F (k) are not chosen in an adversarial way, this choice of D. also ensures that Detect (U)(i) Type (U)()). For the purposes of our formal proof, we will assume that non-zero F(k) are drawn from an absolutely continuous joint distribution. We can't 't
do better if we don't t have any extra information about k* but we can we know k" < l as we show below. Going back to our example in Fig. 3 with D = I we use total of 8 x 7 = 56 samples as opposed to 26 64. While this improvement modest at this scale, for larger problems the improvement is dramatic.
7

---

Singleton Identification in the Low Degree Setting
Let's say we want to determine the singleton from Uj (10) in Fig. [] and we know |k* I By exploiting group testing, it is possible design
De with fewer rows, and thus fewer overall measurements:
kj
Her
acting
never
fails
to
impress
y
Decode
0
0
0
1
1
0
y
> ki
D. = 0
1
1
0
0
1
1 0
0
1
1
Figure 5: We use group testing [16] to identify the singleton k,, which corresponds to the first-order term "never". By designing the masking patterns with the help of group testing, efficiently recover interactions with Ott (og())) extra measurements.
The matrix product D.k" has a different output for each | S In this case, the result y corresponds to the binary index of the location of the 1. It requires P = 3, rather than the P 6 for D I. If all non-zero F(k) had satisfied [k| I 1, we could use this matrix for our example Fig. However, we only have k < 3 for non-zero F (k) in this example, so D in (5) does not suffice. In the case
of general | S l. 42 says that for any scaling of with n, there exists group testing design D with P = O log (n)) that can recover k* in the limit + with vanishing error in poly (n) time. If we also assume that (l) are Detect (U.)j) has vanishing error (see Appendix C.7.2
Extension to Noisy Setting We now relax the assumption that most of the coefficients are exactly zero. To do this, we assume each subsampled Möbius coefficient is corrupted by noise:
Uep(i)=
Σ
F(k) + Zep(i),
(10)
kSdp SL H.K=j
where (i) ~ ((0, There are two main changes that must be made compared to the noiseless case. First, we must place an assumption on the magnitude of non-zero coefficients [F())
such that the signal-to-noise ratio (SNR) remains fixed. Secondly, the matrix D must be modified.
It now consists of two parts: D D D.J. We design D _ standard noise robust
Bernoulli group lesting matrix with P2 = O log(n)) lests, which suffices for singleton identification under any fixed SNR [43]. However, unlike the noiseless case, the samples from the rows of D are not enough to ensure a vanishing error for singleton detection in the Detect (-) procedure. To solve this, we design D E zz7 xm as a Bernuuli group testing matrix with a different parameter. In Appendix C.7.4. show this modified version of Detect (.) has vanishing error if P Ot log(n)).
5 Results
Now that we have discussed all components of the algorithm, we present our theoretical guarantees:
Theorem 5.1. (Recovery with K Uniform Interactions) Let f satisfy Assumption for some O(2r)) with 8 < and let the non-zero coefficients of F be drawn from an absolutely continuous distribution, For {H.)am chosen in Lemma C.3 with Ollog K) K)), == and D. I, Algorithm I exactly computes the transform F in (Kn) samples and O (Kn2)) n²) time complexity with probability at least (()
Theorem 5.2. (Noise-Robust Recovery with K t-Degree Interactions) Let f satisfy Assumption 2.2 for K O(poly(n) and t O(na) with S 0.409. Assume either:
1. The non-zero coefficients of are drawn from an arbitrary continuous distribution, or
2. Ue. is corrupted by noise as in (10 and let non-zero coefficients satisfy [F(k)) =
Then, for (He)C- chosen as in Lemma C.4 with b (log(()) C C= 33,, and D. chosen as suitable group lesting matrix, Algorithm exacttly computes the transform F in O(Ki O(KHlg(n) samples and O poly(n)) time complexity with probubility least 1 - O(1 K) in both the noiseless case (1) and noisy case (2).
8

---

STLMP
301
2/0
3 30h
2000
90R (10)
(a)
(h)
(c)
Figure 6: (a) Perfect reconstruction against n and sample complexity under Assumption 2.1 Holding
C== 3, scale b to increase the sample complexity. We observe that the number of samples required to achieve perfect reconstruction is scaling linearly in as predicted. Results are plotted across for each choice of b and n.. (b) Plot of the noise-robust version of our algorithm. For various values of I, we set n = 500 and K = 500, using group testing matrix with P = 1000. We plot the performance of our algorithm against SNR, measured terms of the R Error bands represent the standard deviation over 10 runs. (c) Runtime comparison of SMT. SHAP-IQ [29]. and 5 order FSI via LASSO [4. All are computing the Möbius transform in the setting where all non-zero interactions are order f, K = 10. SMT easily outperforms both, while the other methods quickly become intractable. Error bands represent standard deviation over runs.
Bresed
Diaguosis
Sensineent Analysis s2
Multiple Choice [n = 15)
30)
1.0
0.8
(nithotzoe))
0.8
[Polhfohoe))
0.5
0.6
0.6
0.5
0.4
0.4
0.4
0
30
18
91
12
18
Spresity
Shopley Vilues
Bonshal Valios
Fulth Bonzheef Tndices
SMT (Algyriihm
Figure 7: Since our ultimate goal is compact, meaningful and computable representations, we compare representations generated from SMT (Algorithm[] [T) with other popular explanation models. We plot R (faithfulness) vs. the number of terms used in the representation (sparsity). For Shapley and Banzhaf values, to generate an r-sparse representation, we use top r magnitude values. For SMT and Faith-Banzhaf, we do slightly more sophisticated refinement procedure. First order Faith-Banzhaf is included because it is the first-order metrie that maximizes R²² As observed in the breast cancer and sentiment analysis tasks, SMT achieve better R than other approaches by utilizing higher-order interactions. In the sentence-level multiple choice dataset, we observe less of difference, since in those cases the entire answer to question is usually contained in a single sentence, thus higher-order interactions provide little advantage. Error bands represent the standard deviation over 10 instances.
The proof of Theorem 5.1 and 5.2 is provided in Appendix C.5 It combines results from all of the parts of the algorithm we have discussed: aliasing, singleton detection and graph peeling. The requirement [F) = p is only due to limitations of group testing theory. In practice, that a lower bound on the magnitude suffices. In addition to our theoretical results, we also conduct numerical experiments synthetic and real word models, which are discussed below.
observe
5.1 Synthetic Simulations
We tested SMT's efficacy on functions satisfying Assumption 2.1 and 2.2 setting non-zero F(k) uniformly in [-1, 1]. SMT implemented as in Algorithm|| [ with group testing decoding via linear programming (see Appendix F.2). Fig. ia phase transition plot that shows the percent of cases where SMT achieves R²2 with fixed K = 100 at different sample complexities and values of n. We vastly outperform the naive approach: when
1000, get perfect reconstruction with only 10-291 291 percent of total samples! Furthermore, number samples necessary to achieve perfect reconstruction scales linearly in predicted. Fig. 6b assesses SMT under noise for various values

---

of t. plotting R2 against SNR with K = 500, = 500, and P = 1000. Fig. 6c plots the runtime for SMT and competing methods. Test functions have K 10 non-zero Möbius coefficients at locations that satisfy k
(restricted to equality due to limitations in the SHAP-IQ code at the time of running). We compare against SHAP-IQ [29) configured to compute 5th order FSI, as well as the method of [4] which computes 5th order FSI via LASSO. As shown in Appendix AA] the hth
order FSI are exactly the 7dh order Möbius coefficients for our chosen f. This figure exemplifies that
SMT is the sole feasible method for identifying interactions on the scale of 2 100. Additional simulations and discussion can be found Appendix D
5.2 Real- World Models
Our objective is computable, faithful, and compact representation of real-world machine-learned functions. Fig. addresses this goal head-on, by plotting R² against the number of terms used in the representation (sparsity) for SMT and other popular model explanation approaches. We consider three different tasks: The first is an XGboost model for breast cancer diagnosis, and the other two are transformer-basee BERT models for the tasks of sentiment analysis and multiple choice question answering respectively. Appendix B discusses the setup in great detail. For Shapley and Banzhaf values, to generate an r-sparse representation, Banzhaf, we do a slightly more sophisticated refinement procedure using LASSO [44], described in the Appendix. We observe that for the breast cancer and sentiment analysis tasks, SMT can generate representations that, with the same number of terms, achieve a much higher R². This is done by identifying interactions between inputs that are important to the model output. Interestingly, in the case of the multiple choice model, there is less of a difference between the Faith-Banzhaf Indices and the SMT representations. This is likely because in the corresponding dataset, answers to the questions are usually contained in single sentences, making interactions less important.
the top magnitude values. For SMT and Faith-
6 Conclusion
Identifying interactions between inputs is an important open research question in machine learning, with applications to explainability. data valuation, and many other problems. We approached this problem by studying the Möbius transform, which is representation over the fundamental interaction basis. We introduced several new tools to the problem of identifying interactions. The use of ideas from sparse signal processing and group testing has allowed SMT to operate in regimes where all other methods fail due to computational burden. Our theoretical results guarantee asymptotic exact reconstruction and are complemented by numerical simulations that show SMT performs well with finite parameters and also under a noisy model.
Limitations Our assumption of independently sampled interactions was made for information- theoretic hardness and may not hold in some settings where correlated interactions exist. For instance, in the sentiment problem in Fig. words with strong 2nd order interactions are likely to appear together in important 3rd order interactions. In such settings, correlation is exploitable, so more specific algorithm can likely exploit this correlation and climinate this assumption. Another limitation is that we have focused taking sparse Möbius transform in this work. In practice, we may be more interested in taking a sparse projection onto a subset of low-order terms. For unitary transforms, projection be achieved by truncation, however, with not-orthogonal transforms like the Möbius Transform, projection is not straightforward. This is an important distinction, because there can be functions which are well-approximated by sparse low degree Möbius projection, but do not have sparse transform.
Future Work Applying SMT to real-world tasks like understanding protein language models 45 LLM chatbots [46] or difffusion models [47] would be insightful. Working with large and complicated models will likely require further improvements robustness- in terms of dealing with noise from small but non-zero interactions and dealing with potential correlations between interactions. Some interesting ideas in this direction could be using more standard statistical ideas like (9 or considering concepts from adaptive group testing. Finally, due to the connection with the Shapley or Banzhaf values (2). methods for computing the Möbius transform can also be used for computing these values by first computing the Möbius transform and then using (2).
10

---

References
[T] S. Shapley, A Value for N-Person Games. Santa Monica, CA: RAND Corporation, 1952.
[2] S. M. Lundberg and S.-I. Lee, "A unified approach interpreting model predictions." in Proceedings of the st International Conference on Neural Information Processing Systems, ser. NIPS' 17. Red Hook, NY, USA: Curran Associates Inc., 2017, p- 4768-4777.
[3] M. Sundararajan, K. Dhamdhere, and A. Agarwal, "The Shapley Taylor interaction index," in International Conference on Machine Learning, Jul 2020, pp. 9259-9268. [Online]. Available:
htps://proceedingge. www.:diiiiiinimmm.......eeee wtt..t/presssv11//snnaarrrgnggg 19/sundararajan200aa.
[4] C.-P. Tsai, C.-K. Ych, and P. Ravikumar, "Faith -sap:: The faithful Shapley interaction index," Journal of Machine Learning Research, vol. 24, no. 94, pp. 1-42, 2023.
[5] M. Grabisch, J.-L. Marichal, and M. Roubens, "Equivalent Representations of Set Functions," Mathematics of Operations Research, vol. 25, no. 2. pp. 157-178. May 2000. [Online].
Available: https:/ppubsonlime. httpiconniie.iffomm...oom wttp:///ii/...123/mr...2222.2.
[6] Devlin, M.-W. Chang, K. Lee, and K. Toutanova, "BERT: Pre-training of deep bidirectional transformers for language understanding," in North American Chapter of the Association for Computational Linguistics, 2019. [Online]. Available: httpss/app.scmmatticcccoooooorrp
52967399
[7] J. Lee, "IMDB Finetumed
2023, accessed Jan 2024. [Online]. Available:
htm.gig---eemmmmmeemmeeeeeeeeeee finetuned peretundd-bert---ee berttbase-uuee uncased
[8] J. M. Pérez, C. Giudici, and F. Luque, "pysentimiento: A python toolkit for sentiment analysis and SociaINLP tasks," 2021.
[9] T. Dao, D. Fu, S. Ermon, A. Rudra, and C. Ré, "Flashattention: Fast and memory-efficient exact attention with iO-awareness," Advances in Neural Information Processing Systems, vol. 35, pp. 16 36344163355 359, 2022.
[10] H. Hassanieh, P. Indyk, D. Katabi, and E. Price. "Simple and practical algorithm for sparse Fourier transform," " in SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 1183-1194. 1973099.93
[Online]. Available: https://epubs... siaepuuubsssamm.... www.o/oor///////a/ooe 0. 1t..1137/119999
[11] Stobbe and A. Krause, "Learning Fourier sparse set functions," in International Conference on Artificial Intelligence and Statistics (AISTATS), ser. Proceedings of Machine Learning Research, La Palma, Canary Islands, Apr 2012, pp. 1125-1133. [Online]. Available:
[12) S. Pawar and K. Ramchandran, "Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and Okklogk) complexity," in IEEE International Symposium on Information Theory (ISIT), 2013, pp. 468-668.
[13] X. Li, J. K. Bradley, S. Pawar, and K. Ramchandran, "The SPRIGHT algorithm for robust sparse Hadamard Transforms," in IEEE International Symposium Information Theory (ISIT), 2014, pp. 1857-1861.
[14] A. Amrollahi, Zandich, M. Kapralov, and A. Krause, "Efficiently learning fourier sparse set functions," Advances in Neural Information Processing Systems, vol. 32, 2019.
[15] M. Aldridge, O. Johnson, and J. Scarlett, "Group testing: An information theory perspective," " Foundations and Trends@ in Communications and Information Theory, vol. 15, no. 3-4, p. 2019. [Online]. Available: http::/dx..doi.or///// wt...oooo/.....//0.1.1 15111100000000
[16] R. Dorfman, "The detection of defective members of large populations." The Annals of mathe- matical statistics, vol. 14, no. 4, pp. 436-440, 1943.
[17] Y. Zhou, U. Porwal, C. Zhang, H. Q. Ngo, X. Nguyen, C. Ré, and V. Govindaraju, "Parallel feature selection inspired by group testing." in Advances in Neural Information Processing Systems, vol. 27, 2014.
[18] R. Jia, D. Dao, B. Wang, F. A. Hubis, N. Hynes, N. M. Gürel, B. Li, C. Zhang, D. Song, and C. J. Spanos, "Towards efficient data valuation based on the shapley value," " in International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 89, 16-18 Apr 2019, pp. 1167-1176. [Online]. Available: httpss//prooceeding.. prtpsssss////////aaaaaaa (atess/////jaa9ahhttm)
[19] C. Harsanyi, "A bargaining model for the cooperative n-person game," Ph.D. dissertation, Department of Economics, Stanford University, Stanford, CA, USA, 1958.

---

[20] C. Wendler, A. Amrollahi, B. Seifert, A. Krause, and M. Püschel, "Learning set functions that are sparse in non- non-orthogonal Fourier bases," in AAAI Conference on Artificial Intelligence. vol. 35, 2021, pp. 10 292-10292.
[21] Q Ren, J. Gao, W. Shen, and Q. Zhang, "Where we have arrived in proving the emergence of sparse interaction primitives DNNs," in International Conference on Learning Representations, 2024. [Online]. Available:
[22] K. Aas, M. Jullum, and A. Løland, "Explaining individual predictions when features are dependent: More accurate approximations to Shapley values," Artificial Intelligence, vol. 298, p. 103502, 2021.
[23] H. Chen, J. D. Janizek, S. Lundberg, and S.-L. Lee. "True to the model or true to the data?" 2020. [Online]. Available: https://arxiv.or//////0666
[24] D. Janzing, L. Minorics, and P. Blöbaum, "Feature relevance quantification in explainable AI:
A causal problem," in International Conference Artificial Intelligence and Statistics, 2020,
pp. 2907-2916.
[25] Ren, Z. Zhou, Q. Chen, and Q Zhang. "Can we faithfully represent absence states to compute shapley values on DNN?" in International Conference Learning Representattins, 2023.
[Online]. Available: https:/oppeneviee.eefffomm hidd YdVYVV
[26] J. Enouen, H. Nakhost, S. Ebrahimi, S. O. Arik, Y. Liu, and T. Pfister, "TextGenSHAP: Scalable
post-hoc explanations in text generation with long documents," " 2023. [Online]. Available: https:/aarii..ogg//d/22222220000
[27] V. Miglani, A. Yang. A. Markosyan, D. Carcia-Olano, and N. Kokhlikyan, "Using Captum to explain generative language models," in Workshop for Natural Language Processing Open Source Sofnware (NLP-OSS 2023), Singapore, Dec. 2023, pp. 165-173. [Online]. Available: http://iccaattloooy..////22/////
(28) L. M. Paes, D. Wei, H. J. Do, H. Strobelt, R. Luss, A. Dhurandhar, M. Nagireddy, K. N. Ramamurthy, P. Sattigeri, W. Geyer et al., "Multi-level explanations for generative language models," " 2024. [Online]. Available:
http://axxii.ooo//pp///////.3.1 14459
[29] Fumagalli, M. Muschalik, P. Kolpaezki, E. Hüllermeier, and B. E. Hammer, "SHAP-IQ: Unified approximation of any-order shapley interactions." in Conference on Neural Information Processing Systems, 2023. [Online]. Available:
[30] J. S. Kang, R. Pedarsani, and K. Ramchandran, "'hh fair value of data under heterogeneous privacy constraints in federated learning." Transactions on Machine Learning Research, 2024. [Online]. Available: http:://wwaaaavvvveveettoooooldg
[31] Wang and R. Jia. "Data Banzhaf: A robust data valuation framework for machine learning." " in International Conference on Artificial Intelligence and Statistics, vol. 206, 25-27 Apr 2023, pp. 6388-6421. [Online]. Available: https://rooceedinggs.. mlr prw.
[32] A. Ghorbani and J. Zou, "Data Shapley: Equitable valuation of data for machine learning," in International Conference on Machine Learning, vol. 97, 09-15 Jun 2019, pp. 2242 2251.. [Online]. Available:
htm
[33] A. Ghorbani, M. Kim, and J. Zou, "A distributional framework for data valuation," in International Conference on Machine Learning, vol. 119, 13-18 Jul 2020, pp. 3535-3544, [Online]. Available: https:/pproceedings..iii mlr press// 19/ghorban
[34] T. Chen and Guestrin, "XGBoost: A scalable tree boosting system," in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, 2016, pp.
785-794. [Online]. Available: htttp://doi http:///io..ccooo/o....o.. 0ttp./....11//999722995533
[35] A. Barbosa, "Roberta large fine tuned on race." " 2021. [Online]. Available: https//hugginggace co/l
finetuned-race/treee/ie
[36] Q Ren, Y. Xu, J. Zhang, Y. Xin, D. Liu, and Q Zhang, "Towards the dynamics of DNN learning symbolic interactions," 2024. [Online]. Available: https:/aaxi.oog/p/////1.11999
[37] T. M. Cover, Elements of Information Theory. John Wiley Sons, 1999.
[38] M. Luby, "LT codes," in IEEE Symposium on Foundations of Computer Science, 2002, pp. 271- 280.
12

---

[39] K. R. Narayanan and H. D. Pfister, "Iterative collision resolution for slotted aloha: An optimal uncoordinated transmission policy," in International Symposium on Turbo Codes and Iterative Information Processing (ISTC), 2012, pp. 136-139.
[40] Y. E. Erginbas, J. Kang, A. Aghazadeh, and K. Ramchandran, "Efficiently computing sparse fourier transforms of q-ary functions," in IEEE International Symposium on Information Theory (ISIT), 2023, pp. 513-518.
[41] S.-Y. Chung, Richardson, and R. Urbanke, "Analysis of sum com-product decoding of low-density parity-check codes using gaussian approximation," IEEE Transactions Information Theory, vol. 47, no. 2, pp. 657-670, 2001.
[42] W. H. Bay, Scarlett, and Price, "Optimal non-adaptive probabilistic group testing in general sparsity regimes." Information and Inference: A Journal of the IMA, vol. 11, no. 3, pp.
1037-1053, 02 2022. [Online]. Available: https://doi.or orgg 1093//maaaa//aaabb200
[43] Scarlett and O. Johnson, "Noisy non-adaptive group testing: A (near- )definite defectives approach," IEEE Transactions on Information Theory, vol. 66, no. 6, pp. 3775-3797, 2020.
[44] R. Tibshirani, "Regression shrinkage and selection via the lasso," " Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 58, no. 1, pp. 267-288, 1996.
[45] 7. Lin, H. Akin, R. Rao, B. Hie, Z. Zhu, W. Lu, N. Smetanin, R. Verkuil, O. Kabeli, Y. Shmueli, A. dos Santos Costa, M. Fazel-Zarania T. Sercu, S. Candido, and A. Rives, "Evolutionary-scat prediction of atomic-level protein structure with language model," Science, vol. 379, no. 6637. pp. 1123-1130, 3100, 2023. [Online]. Available: http:///ww..sserr..ooooo///////t ade2574
[46] OpenAI, "GPT-4 technical report," 2023.
[47] D. Kingma, T. Salimans, B. Poole, and J. Ho, "Variational diffusion models," in Advances in Neural Information Processing Systems, vol. 34, 2021, pp. 21 696-21 707.
[48] P. L. Hammer and R. Holzman, "Approximations of pseudo-boolean functions; applications to game theory," " Zeitschrift für Operations Research, vol. 36, no. 1, pp. 3-21, 1992. [Online]. Available: https://doi.coo wttp://///////////////1111 10000000/////0000000000
[49] W. Wolberg, O. Mangasarian, N. Street, and W. Street, "Breast Cancer Wisconsin (Diagnostic))"
UCI Machine Learning Repository, 1995, DOI: https//ddbborrr//1044443////
[50] D. Q. Nguyen, T. Vu, and A. T. Nguyen, "BERTweet: A pre-trained language model for English Tweets," in Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2020, pp. 9-14.
[51] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts, "Learning word vectors for sentiment analysis," in Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. Portland, Oregon, USA: Association for Computational Linguisties, June 2011, pp. 142-150. [Online]. Available: http://www..cclwc.boo//atttttt P11-1015
[52] G. Lai, Q. Xie, H. Liu, Y. Yang. and E. Hovy, "RACE: Large-scale ReAding comprehension dataset from examinations," in Conference on Empirical Methods in Natural Language Processing, Copenhagen, Denmark, Sep. 2017, pp. 785-794. [Online]. Available: https: /aclanthlloy.orgDD177--0
[53] A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and Loick, -Information--hherrtiic and algorithmic thresholds for group testing," IEEE Transactions on Information Theory, vol. 66, no. 12, pp. 7911 2020.
[54] C. L. Chan, S. Jaggi, V. Saligrama, and Agnihotri, "Non-adaptive group testing: Explicit bounds and novel algorithms," IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 3019-3035, 2014.
13

---

A Relationship between Möbius Transform and Other Importance Metrics
We begin with some notation. We define the Möbius basis function (which are all possible products of inputs) as:
bk (m)
II m4.
(11)
dxb;=1
Now we define the following sub-spaces of pseudo-Boolean function in terms of the linear span of Möbius basis functions:
M₁ (b kk S t).
(12)
Now we define the projection operator Proj,. (f. D), as the projection of the function f onto the function space D with respect the measure μ. If g(m) Proj (f. D), we write its decomposition as g(m) Ekezy cff. D, k)))(m). Note that linear independence implies the uniqueness of this representation.
Shapley Value The Shapley values SV(1) [ of the inputs m,, i = 1,... n with respect to the function f are 48
sV(I) = c(f. Mf.) = E F()).
(13)
k:k==1
where a is the Shapley kernel. SV(() = F(ee) when f is a linear function.
Banzhaf Index are 48)
The Banzhaf index BZ(i) of the inputs mi, i = l,..., with respect the function
(i = MI,M,), = Σ 21kIT F(k),
(14)
k:k,=1
where y is the uniform measure. BZ(() = F(e;) when ff is linear function.
Faith Shapley Interaction Index The 1th order Faith Shapley interaction index SV,(k) for [k| S
is
SV.(k) clf, M,, = F(k) (-1)t-Ik)
[
1.
Σ F(P),
(15)
++ k
[k]
p>k
|p|>at
where is the Shapley kernel. SV.(k) F(k) when f is 1th order function, i.e., F(k) 0 when
k > t.
Faith Banzhaf Interaction Index The tt order Faith Shapley interaction index BZ, (k) for [k] < t
is
1 |Pl
(Z,(k)
F(k) + 1-1) Σ
F(p),
(16)
2k
kk
k
p>k pp
where μ the uniform measure. (1) F()) when f is th order function, i.c., F(k) 0 when k > t.
Shapley- Shapley-Taylor Interaction Index The 9hh order Shapley-Taylue Interaction Index 3 STIL (k)
is:
(F(k)
[(k) g- MI-1,o,k)
k L k t,
ST],,(k)
f²-
F(k).
(17)
where a is the Shapley kernel. Explicitly, can be shown that:
cf -f- p-- Mr Mr.1,o,k) Σ (IK1) F(k') for [k] -t.
(18)
As consequence of the above, we have SKII, = SV,(k) F(k) when f a 1th order function, ic.. F(k) = 0 for kk| > t.
14

---

B Experiment Details
Let be the real-world function we wish explain. In subsections B.1 B.2
B.3 we describe
how we formed these functions for the tasks of breast cancer diagnosis, sentiment analysis, and multiple choice answering respectively. For our experiments, we plot the R² (faithfulness) for variety explanation models f, measured through:
R²
|| f
2'
where we use the notation |l 1iil=Emea Emery f(m)².
In Figure 2 we consider settings where n R 20, such that we can run optimization procedures find faithful approximations that are sparse and low degree.
Achievable Low Degree: To find the best approximation f of up to degree t, we solve the following quadratic programming problem:
min || - / 11 f.a
(19)
s.t. f(m)
Σ ksm./klst
ak. Vm.
(20)
Achievable Sparsity: On the other hand, cannot efficiently find the optimal faithful K-sparse ap- proximation due to the problem's 's combinatorial nature. Instead, informed by the strong faithfulness of low degree approximations, we employ the following heuristic obtain some sparse approximation.
Let SK S. ž be a set containing the first K coordinates with the lowest degree, where ties are randomly broken. With this set, we solve the following quadratic programming problem:
min || -
(21)
f.a
s.t. f(m)
=
Σ kSm,
Ok Vm.
(22)
In Figure 7 we consider the four explanation models described below.
Shapley Values: We approximate Shapley values by iterating through permutations of the inputs 2
For an efficient implementation of the algorithm, we use the SHAP Python package (2]. To measure the faithfulness captured by Shapley values at some sparsity level r, we consider approximations that only include the top-r Shapley values by magnitude.
We approximate Banzhaf values using the Maximum Sample Reuse Monte Carlo procedure described in [31. To measure the faithfulness captured by Banzhaf values at some sparsity level consider approximations that only include the top-r Banzhaf values by magnitude.
Banzhaf Values:
We calculate Faith-Banzhaf indices using the regression formulation de- scribed in 4 To measure the faithfulness captured by sparse approximations of SatthBBanzhaf in- dices, we modify the regression problem by adding an & penalty on the values of the Faith- Banzhaf indices. We vary the penalty coefficient to obtain different levels of sparsity.
Faith-Banzhal Indices:
SMT: We run SMT (Algorithm I) to obtain sparse Möbius representation F with support supp (F). Then, we fine-tune the values the coefficients by solving the following regression problem over uniformly sampled set of points D S Zz:
min (f(m)) - f(m))²
f.a MED
s.t. i(m) =
Σ
Ok Vm.
kgm.kesupp(P))
15

---

To measure the faithfulness captured by sparse approximations, we modify the regression problem by adding I penalty on the values of the Möbius coefficients. Then, we vary the penalty coefficient À to obtain different levels of sparsity:
min Σ (f(m)-((m)) +
Σ
|ak|
faa MED
kEsupp(P)
s.t. f(m)
=
Σ ksm,kEsupp(F)
0ki Vm.
B.1 XGBoost for Breast Cancer Diagnosis
We train XGBoost model for classification using the Wisconsin Breast Cancer dataset [4]. This dataset contains the mean, standard deviation, and largest value of ten measurements, resulting in thirty features. For Figure 2
only the mean and standard deviation, resulting in twenty features. For Figure 2 we use the first ten data points in the training set and for Figure we present the aggregated results over the first twenty.
To explain the XGBoost model (the probability associated with a positive classification) on each data point E X' we use an interventional expected value formulation: we freeze some of the features and take an expectation over all data points by infilling the remaining features. Formally,
f(m) E. [N(X)]do(X, =mm)
where we use the notation I' {xx
1).
B.2 BERT for Sentiment Analysis
We employ the sentiment analysis model from [8] which is built upon BERTweet [50], RoBERTa model trained on English tweets. We take movie reviews from the IMDb Movie Reviews dataset mapping from maskings of words (using the [UNK] token) to the model's logit value associated to the correct sentiment classification.
[5]] For partieular review, define its function
we use the first ten sentences in the dataset with 17, 18, or 19 words, where words separated through spaces in the review. Below, we include the reviews and their low degree and sparse approximations calculated with equations 20 and respectively.
For Figure 2.
(worls)
REVIEW
SENTIMENT
(a)
18
A rating of "I" does not begin express how dull, depressing and relentessly bad this movie is. Menially- scarred. Help me. It that TRd.T ME!!!
Negative
18
Hated with being. Worst
Negative
film The characters are unlikeable and the script awful. a waste
no good takents Demeave and Auteuil, don't know why like this movic so well, hat never get tired of watching it.
good film.
very fonny. Yet
films!
Posélive
19
Negative
(6)
18
Positive
(8)
19
you like Pauly Shore, you'll love Son in Low, If you hate Panly Shoce, then, well. liked it! This the definiivee
Positive
17
version of Hamlet. Branagh cuts nothing, but there The Spacegirl (vamp me baby!). Add little pem to your of holiday regulars. It is sweet, funny. and endearing no comment- stupid movie, acting average or worse... screenplay no serse at all... SKIP IT!
wasted
Postive
one Tobe Hoppor's
Epic staryteling, great special
Positive
61
17
Postivve
17
Negative
(a)
(b)
(c)
(d)
In Figure 7 we take a random sampling of reviews, with number of words spanning from 17 to 38. The reviews used, alongside their word counts and sentiment, are included below:
B.3 BERT for Multiple Choice
For multiple choice answering, we use a RoBERTa model 35 fine-tuned on RACE [2 large- scale reading comprehension dataset. This dataset contains over 28,000 passages, each containing
16

---

(e)
ii)
(a)
(d)
(c)
(h)
(i)
corresponding multiple-choice questions. For experiments, found the first ten passages with 15 sentences, and took their first multiple-choice question.
To construct the function, we consider sentence-level maskings of the passages using the [PAD] token. pass the masked passage, alongside the multiple choice question into the RoBERTa model, and measure the logit value of the question's correct answer.
17

---

x (words)
REVIEW
SONTIMENT
17
This the definitive movie version Homlet. Branagh nothing. but there wasted moments.
Positive Positive
18
I don't know why I like this movic so well. but I never get tired of watching it. Brilliant movie. The drawings were just amazing.
ended before it begun. I ve waited years for a sequel, but nopcoe!!!
23
Positive
Malcolm McDowell has had too many good movies lately
no different. Especially
26
Negative
designed for people who like Yellow filters on their movies.
Excellent episode movic alm Pulp Fiction. days suicides, doeent get more depressing than this, Movie rating: 8/10 Music rating: 10/10
24
Positive
You' 've got to be kidding. This movie sucked for the sci-fi fans. would only recommend watching
26
Negative
this only if you think Armageddon
good.
Despite its interesting premise, Sniper quite tedious. With a tighter script and sharper directing it could have been electrifying: instead plods along with little tension.
27
Negative
29
You may like Tim Burton's is fantasies, but not in commercial-likk, show off lasting 8 minutes, It demonstrates good technical points without real creativity Brilliant exccution in displaying once and for all. this time in the venue of politics, of how "good intentions du actually pave the ruad hell". Excellent!
Negative
established narrative pace.
27
Positive
I can't 't helieve they got the actors and actresses of that caliher to do this movie. That's all I've got to say - movie speaks for itself!!
28
Positive
Something does not work this movic. There are absolutely their very acting seems frozen, sometines amaleut. Also, the script is not convincing and not reliable. Great story, great music. A heartwarning love story that's beautiful watch and delightful listen to. Tou bad there is no soundtrack CD.
energies between the actors. In fact.
33
Negative
24
Positive
very carelessly written film. Pour character and idea development. The silly plot and weak acting by just about the ensemble cast didn't 't help. Seriously, watching this movic will NOT make you smile, may make you retch.
38
Negative
19
This is a good film. This is very funny. Yet after this film there were no good Ernest films! The characters unlikeable and script awful. It's waste talents of Deneuve Auteuil.
Positive
Negative
Missing Proofs
C.1 Boolean Arithmetic
Table [ the addition and multiplication table for arithmetic between x. y E Zz We also note that Ze is typically used to refer to the integer ring modulo 2. The arithmetic we are describing here is actually that of monoid. Since the audience for this paper is people interested in machine learning, we continue to use Z₂ since it is commonly used to simply refer to the set {0, 1}.
Addition Table
Multiplication Table
Subtraction Table
+
=
1 I =
O
X
2 = 1 0
r
1
x
0
1/
1
1
1
0
y 1
0
1
y
0
0
0
y/
=
0
N/A
0
Table 1: Addition, Multiplication and Subtraction table for Boolean arithmetic in this paper. Subtrac- tion is for x.
C.2 Discussion of Aliasing of the Möbius Transform
When function has many small or zero Mobius coefficients (interactions), our goal is to subsample (4) in such a way that the aliasing causes the non-zero coefficients to end up in different aliasing sets (5) (as opposed to all of them being aliased together, making them more difficult to reconstruct). Lemma C. is a key tool that we will use in this work to design subsampling patterns that result in good altasing patterns.
Lemma C.1. Consider H Zhx", b <<N and f
23 + R. Let
u(l) f H' Ve Z²)
(23)
If U the Mobius transform of u, and F is the Mobius transform of f we have:
U(i) Σ F(k).
F(K)
(24)
Hk=j
This lemma is a powerful tool, allowing us to control the aliasing sets through the matrix H. The proof can be found in Appendix C.3 and is straightforward, given the relationship between u and
18

---

f. Understanding why we choose this relationship, however, is more complicated. Underlying this choice the algebraic theory of monoids and abstract algebra.
As we have mentioned, our ultimate goal is to design H to sufficiently "spread out" the non-zero indices among the aliasing sets. Below, we define simple and useful construction for H.
Definition C.2. Consider {61, f ib} I C [n]] with I| b, and H Z2X" Let h, correspond to the 8th row of H. given by h; = B;g, the length n unit vector in coordinate iz. Then if we subsample according to 23 we have:
U(i) = Σ
F(k).
(25)
k: ki Viez
which happens to result in aliasing sets A(j) = -k: Vi E 7 all of equal size 2h. The above
choice H actually induces rather simple sampling procedure when follow 23 For instance if
[b.. we have:
u(() f ([e: bn)
(26)
In other words, in this case, we construct samples by freezing n - b of the inputs to 1 and then varying the remaining inputs across all the 2 possible options. In the case where the non-zero Mobius interactions are chosen uniformly at random, this construction does a good job at spacing them out across the various aliasing sets. The following result formalizes this.
Lemma C.3. (Uniform interactions) Let $1,...,k, be sampled uniformly at random from Zž. where F(k,) & O, Vi E [K], but F(k) = 0 for all other k Zž. Construct disjoint sets Ig C [n]] for C = 1,.... C, and the corresponding matrix H. according to Definition C.2 Let Ac(j) correspond the aliasing sets after sampling with respect malrix H Now define:
j such that KG E Acli)== =
(27)
Then b O(log(()) K = O(2n/C), in the limit n - oo with C 0(1), j are mutually independent and uniformly distributed over 2h.
The proof is given in Appendix C.6.1 and follows directly from the form of the aliasing sets Ae Corollary C.3 means that using H as constructed in Definition C.2 ensures that we k with F(k) * 0 are uniformly distributed over the aliasing sets, which maximizes the number of singletons. This result, however, hinges on the fact that the non-zero coefficients are uniformly distributed. We are also interested in the case where the non-zero coefficients are all low degree. In order to induce uniform distribution in this case, we need to exploit a group lesting matrix.
Lemma C.4. (low degree interactions) Let ki.... kg be sampled uniformly at random from {k k < 1, E Zi }. where F(k;) + 0, Vi E [K]. but F(k) = 0 for all other k E Zy. By constructing 1, 1,... ... C from rows of near constani column weight group lesting matrix, and sampling as in 23 ift (n) for a < 0.409, and b = O(lgg(K) K K=0t0 Onn',, ) in the limit as n + 00, J as defined in (27) are mutually independent and uniformly distributed over Zb..
C matrices H
The proof is given in Appendix C.6.2
It relies on an information theoretic argument, exploiting
result from optimal group testing [53
C.3 Proof of Lemma C
Proof. Taking the Mobius transform of u gives us:
19

---

U(k)
()(()
tsk
(kk
h
ESk
=::=0
E(-1) (((()
Σ F(r)
Ikk
rs 0 me, bi
(k 1les (1)
Σ F(r)
r h
rE2g
=d,=0
))
Σ F(r)
Σ(-1)
r
O h:)
rE2g
BE
==4==0
((r)
rEZS
Now let's just focus on the term the parenthesis for now, which we have called ((r).
Case 1: Hr= k
T(r) I h
(28)
85k
First note that under this condition, e = k = I i0 h4 To this, note that kj = r & hy. Since this holds for all j such that k; = O. we have the previously mentioned implication.
Conversely, é, < kj (this means l = 0 AND k5 = 1) for some j, then r and hy must overlap. Thus,
1 [r br
0 -
h
x=
We can split ((r into two parts, the part where l = k and the part where & < k:
((r) 1
h
Σ (-1)1"(k-e))
h:
(Hr (Hr= k)
(29)
=k
t<k
==f==0
(30)
tck
(31)
Case Hr # Let Hr k' + k. This case itself will be broken into two parts. First let's
say there is some j such that kj 0 and Kj Since Kj = we know that I {r S h 0. Furthermore, since Vl (e: L < k) have l 0. Then by a similar argument to our previous one, we have 1 (r 0 h.}
Vl k. follows immediately that ((r) 0 in this case.
Finally, we have the case where k' < k. First, if there is coordinate j such that 0 = < we know that {r < h = 0 so we have {r < O h.) = 0 VL s.t. Fj. lj < Wy. The only that remain are those such that k' < l < k. It is easy to see that this is a sufficient condition for {r & O+e,zo h.) 1.
I(x) = (1)
r Oh h
(32)
1Sk
i:f
Σ
(-1)
(33)
kStck
(34)
20

---

Where the final sum is zero because exactly half of the e have even and odd parity respectively.
Thus, the subsampling pattern becomes:
U(k)= E F(r).
Hr=k
C.4
Proof of Section 4
U(k)
(-1)
tSk
((0 h od
E(-1)(((-0)) (k-t)
tsk
i::=0
Σ
(-11)2 (k-()
Σ
F(r) (rsa)
Kk
r50 b.
Σ
Σ
F(r)
rs
h 1 d}
rE2g
=1,=0
Σ
F(r)1 {rs
(k
(-1) 11
r : h
6E22
==
Σ F(r)1 (rs adddd ((r)
re2g
Σ F(r)
Hr=k rSd
C.5 Proof of Main Theorems
Theorem 5.1. (Recovery with K Uniform Interactions) Let f satisfy Assumption 2.7 for some K = O(2nd) with 8 S and let the non-zero coefficients of be drawn from an absolutely continuous distribution. For {He)e= chosen as in Lemma C.3 with = Olog K)), C' = and D = Algorithu Seeriithheexxaelyyyy exactly computes the transform F in (KKn) samples and O(Kn)) time complexity with probability at least (()
Theorem 5.2. (Noise-Robust Recovery with K (-Degree Interactions) Let f satisfy Assumption 2.2 for K = (n)) and t = O(n²) with S 0.409. Assume either:
1. The non-zero coefficients of F drawn from an arbitrary continuous distribution, or
2. Uep is corrupted by noise in (10 and let non-zero coefficients satisfy [F(k)] = p.
Then, for [He]e chosen as in Lemma C.4
with b O(log( ()), C 3, and D. chosen suitable group lesting matrix, Algorithm exactly computes the trunsform O(Kt ((K(log(n) samples and O(K poly(n)) time complexity with probability least 1 - O(1/K) in both the noiseless case (1) and noisy case (2).
Proof. The first step for proving both Theorem 5.1 and Theorem 5.2 is show that Algorithm I can successfully recover all Mobius coefficients with probability O(1K)) under the assumption that have access to Detect (U)( function that output the type Type (U)( for any aliasing set (j). Under this assumption, we use density evolution proof techniques to obtain Theorem C.5 and conclude both theorems.
Then, remove this assumption, we need show that we can process each aliasing set cjorreecty meaning that each bin is correctly identified as zeroton, singleton, multiton. Define E as the error
21

---

event where the detector makes mistake in O(K) peeling iterations. If the error probability satisfies Pr(E) & O)) the probability of failure of the algorithm satisfies
PF Pr F F
Pr(E)) Pr F1E) Pi(E) Pr(E)
Pr
T + F E + Pr(E)
=0(1K)-
In the following, we describe how we achieve Pr(E) S O(L/K) under different scenarios.
In the case of uniformly distributed interactions without noise, singleton identification and detection can be performed without error described in Section C.7.1] In the of interactions with low degree and without noise, singleton identification and detection can be performed with vanishing error described in Section C.7.2 Lastly, we can perform noisy singleton identification and detection with vanishing error for low degree interactions as described in Section C.7.2
C.6 Density Evolution Proofs
The density evolution proof is generally separated into two parts.
We show that with high probability, nearly all of the variable nodes will resolved.
We show that with high probability, the graph is a good expander, which ensures that if only a small number are unresolved, the remaining variable nodes will resolved.
Whether the decoding succeeds or fails depends entirely on the graph (or rather distribution over graphs) that is induced by the algorithm. The graph ensemble is parameterized as G (D (D, (M))a
D is the support distribution. The set of non-zero Mobius coefficients {r (M 0 D is drawn from this distribution. In [13, using the arguments above shown that if the following conditions hold, the peeling message passing successfully resolves all variable nodes:
1. In the limit as - oo asymptotic check-node degree distribution from an edge perspective converges that of independent an identically distributed Poisson distribution (shifted by 1).
2. The variable nodes have a constant degree C 2 3 (This is needed for the expander property).
3. The number of check nodes in each of the C sampling group is such that 2 O(K).
Theorem C.5 ((3)). If the above three conditions hold, the peeling decoder recovers all Mobius coefficients with probability 1 (()
In the following section, we show that for suitable choice of sampling matrix, these conditions satisfied, both in the case of uniformly distributed and low degree Mobius coefficients.
C.6.1 Uniform Distribution
the matrix in Corollary C.3 We select C' = 3 different J, 72, Ia such that J, n = 0 Vi + E (1,2,3) Note that this satisfies condition (2) above. Furthermore, we let l scale as ( In order to satisfy condition (3), we must have 8 < J. since each 4; can consist of at most 1 of all the coordinates.
In order satisfy the conditions for the of a uniform distribution of
We now introduce some notation. Let g-(-) represent the hash function, that maps a frequency r to check node index k in each subsampling group j = l,..., C, i.e., (r) H2r. Per our assumption, have K non-zero variable notes r(1), ......,,(ff (K) chosen uniformly at random. Technically, we sampling without replacement, however, since 2- - 0, the probability of selecting a previously selected (()) vanishes. Going forward in this subsection, we will assume that each r; is sampled with replacement for a more brief solution. A more careful analysis that deals with sampling with replacement before taking limits yields an identical result.
22

---

First, let's consider the marginal distribution of g, ()(( for some arbitrary j E [C] and E [K]. Assuming sampling with replacement, we have:
Pr (r(0)) =k) Pr
1 F1 -k
-k)=
II mET
Pr
(t)
kim
1 2
(35)
Thus, we have established that the our approach induces uniform marginal distribution over the 2 check nodes. Next, we consider the independence of our bins. By assuming sampling with replacement, we can immediately factor our probability mass function.
Pr (T) = =k((.))
= I[ Pr (N5) -((ws)
(36)
Furthermore, since carefully chose the such that they are pairwise disjoint, we have
Pr ( ( (1()) =k(wo)
Pr (1:
(0) k(,))
II (rl) k(bJ))=
Il Pr ()(((())= =k(t)), (37)
establishing independence. Let's define an inverse load factor K. From a edge perspective, sampling with replacement with independent uniformly distributed gives us:
k-j
Pj = jm
(38)
26
For fixed 1), asymptotically as K - oo this converges to:
p5 (1/1)--1e-1)
(39)
1j
C.6.2 Low Degree Distribution
For this proof, we take an entirely different approach to the uniform case. We instead exploit the results of Theorem F.I which is about asymptotically exactly optimal group testing, and then make an information-theoree
argument. Let X be group testing matrix (constructed either by an i.i.d. Bernoulli design or a constant column weight design using the parameters required for the given n). We don't ' explicitly write the dependence of X" on since by invoking Theorem F.T we assume some implicit relationship where = O(n²) for 0 satisfying the theorem conditions. Now consider some r, chosen uniformly at random from the (?) weight binary vectors. Note that in this work we actually use what is known the "i.i.d prior" opposed to the "combinatorial prior" that we have just defined. As noted in [15), these are actually equivalent, so we can arbitrarily choose to work with one, and the result holds for the other as well. We define:
Y x"=""
(40)
Furthermore, define the decoding function Dec,, (-), which represents the deterministic procedure that successfully recovers r with vanishing error probability, We have the following bounds on the entropy of Y,;
HYY") H(Y") H(Y + < T,
H(YP Y YF_1
(41)
(42)
where we have used the fact that binary random variables have a maximum entropy of 1. Furthermore, by the properties of entropy also have H (Y 2 (Decc Y X") X*). Dividing through by
T. we have:
H (Dec Y X X
H Y
1.
(43)
23

---

Let Dec,, (Y", x))) r" + eIT Y", ).). It is known (see
[5]
that Pr(ert, (Y",
* 0)
O(poly(T)e 7). Thus, we can bound the left-hand side as: (DDco(Y" x") X")
H(r" + eIT, X") X*)
(44)
T
T
H(r") H H(rrr, ( (Y,, X") X")
(45)
T
H(r") -H ( (Y", X"))
(46)
T
Where in (45) we have used the bound (A + B) 2 H(A) (B) and the fact that X and r" independent, and in (46) have used the fact that conditioning only decreases entropy. By the continuity of entropy and Theorem F.I we have that:
H H(r") H(err (Y", )"))
log (?)
H(err, (Y", (",x")) =1-0= ==0=1 (47)
lim n1000
lim n-00
lim 700000
T
This establishes that:
T(n)
lim +00 T(n) Σ (Y,"
YY," I (I =1.
(48)
Unfortunately, this does not immediately imply that all of the summands have a limit of 1, however, it does mean that the fraction of total summands that are less than one goes to zero (it grows as (T))) Let G N correspond to the set containing all the indicies of the summands that are equal to 1. By using the fact that conditioning only reduces entropy, have
lim H (Y?" Y 1, S. ti < i,j E G}, 2=000
(49)
Now we define the countable sequence of random variables:
Y lim Y,", i N.
(50)
n
By continuity of entropy, and the above limit and definition, we have:
H (Y, Ys,)= =1
(51)
Noting that conditioning only decreases entropy, we immediately have that Y, Bern()). Now consider some arbitrary finite set S C G. We will now prove that (V,, i E S*3 mutually independent.
Let 12 <.. < iss-| be an ordered indexing of the elements of St. Furthermore, let Q (6g 1 S j). Assume the set (V,, i Q2} is mutually independent, and use the notation Y q; represent a vector containing all of these entries. We have:
Proof.
H(Y,, Yo,) H(Yo,) + H(Y,, \Q,)-
(52)
However, by using the fact that conditioning only decreases entropy we have:
= (Y
s - H( \Y,))= s H (Y,,,, 4 $
(53)
thus,
= H(Y 4+1 = ( 1.
(54)
This leads the following chain of implications:
(Y Y₂,) = (YQ,)))))))))))))))))))))))))( + (( + Yisu IL Yo.
(55)
From this, and the initial inductive assumption, we can conclude that {Y,, i E Q)+1} } is mutually independent. The base case of j = follows from the fact that a set containing just one single random variable mutually independent. Since Q15-1 = S" the proof is complete.
Now let L(n) |G n [n]] know L ((T())). which follows from the stronger result that L(n)
limp- T(x)
L(n) 1. Take b < Lid
By leveraging the above results, we can select our subsampling
HH, C 1=1 from suitable rows of X,. Let s(()) ,...,,S S...,( CGN (s!") and 5(())
(())
matrices
((x)) 0. Then take
(n) X.... Due to the independence result proved above, the asymptotic degree distribution is:
(56)
-
Pj + (j ( 1)!
(57)
24

---

C.7 Singleton Detection and Identification
In this section, we prove the main results about singleton detection and identification. For the noiseless case, we introduce another assumption:
Assumption C.6. (No Cancellation) Suppose the non-zen zero values F(k1), ... F(kk) are sampled
from joint distribution IP that satisfies the following condition:
E SS C 55
(58)
This assumption is quite mild, and there are many classes of IP that satisfy this assumption.
Lemma C.7. Any absolutely continuous satisfies Assumption C.6
a.s. C.o.ss.
Proof. For simplicity let F represent K dimensional random vector containing F(k;) at index i. Let the set a) = (F: Eies F(k;) = a). Since absolutely continuous, a density exists such that:
PPF E R(S,a))= -
dp.
(59)
(R(S,a)
However, dim (R(,, K -S). Thus for S * R(S, a) has Lebesgue measure zero, thus
Σ F(k:) -0 PPFF R(S,0) -RS dp 0. VES
Pr
(60)
JR(,0))
C.7.1 Uniform Interactions Singleton Identification and Detection without Noise
For singleton identification, we observe that in the case a singleton, Ye = k", thus, in the case of a singleton k* can be recovered. We still need to show that the Detect function correctly identifies the type. We separate the proof into three parts:
(1) Prove Detect (U.()) Hz
Type( (U)() Hzz.
(2) Prove Detect (U+(i)) = Hss
= Type(U.()) = H.s.
(3) Prove Detect Coetect(U,ae (i) = -ass = Type(U (i) = -HMM-
Consider the subsampling group Uj( for some fixed e. We first consider the case where |k| is not restricted, and denote the set non-zero indices kj...., kk as N.
Proof of (1) Let Detect Detect(U..() (U.(j) Hzz, and for contradiction's sake assume Type(U.(i) # Hz.
Detect(U,.)) Hz
Σ
F(k) = 0 Vp,
(61)
ksd, H.k=j
Since ('ype(U.()) * Hz. we have that / n (k: H,k j} + 0. Thus, we consider the above
implication for the case of p 0 and noting that do O, we have:
Detect Detect(U..)) Hz
Σ
F(k) =
(62)
But considering the no cancellation condition, this is impossible, thus proving (1).
Proof of Note that the converse of (1) true (the proof is immediate). Thus, proving Detect(U, (j))) Hs = -(Type(U, U.) = Har) is the same as proving (2). We will again use the method of contradiction, and assume Detect U (j)) = Hs and Typo(U..i)) = HM-
Detect(U,.)) = Hs = U (i) U..) Vp > 1.
(63)
Note that by our assumption, Uj)(j) * 0. By our assumption that Type( (U(j)) = HM, we must have W n (k: H.k * 0 > 2. Choose k,, kg e N (k: H.k j}. Given choice of d,
25

---

Ep" > 1 s.t. only *one* of 1 or k2 - dp.. Without loss of generality we will assume kg S d
and 1 E dp. Now, define the following sets:
To Nn (k: H.k =
(64)
Tp- = Nn (k H = jk v d
(65)
We know k2 Tp. and K1 To Tpr thus 1Jp and IJo Jp-1 2 1. With this, we can show that the implication above cannot be satisfied.
Case 1: Un. (i) 0.
Ucpp- (i)= = Σ
F(k)= =0
(66)
KEJ;
Since Jp is not empty, from our distributional assumption, the above sum cannot be O.
Case 2: Uep = U,)(().
Ue,(ii - Uc.p' -0)
Σ F(k) = 0.
(67)
KEJo WT,
Since To \ Jp not empty, from our distributional assumption, the above sum cannot be 0. This implies that Type(U.(i)) = HM must be false, thus proving (2).
Proof of (3): Since we have converse for (I), converse for (2) suffices to prove (3). The converse follows below:
Type(U.(i) Hs = 3k' s.t. U2p {0, F(k"), Vp. Since F(k*) * O, have (i) + and all entries of Ue()) either F(k*) 0. Thus, Detect U.(i)) Hs.
(68)
C.7.2 Low Degree Singleton Identification and Detection without Noise
Here we include sketch of the argument for the noiseless part of Theorem 2, which focuses on the case k| < (the rest Theorem unchanged).
(1) Prove Detect (i)( = Hz = Type(U.(i) = Hz.
(2+3) Prove Pr (Detect (U)( (Tpee(U.(i)) +
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. In this case, we can simply rely on the result of [54]. Since Pr(k + k*) I n 0 correctly recover each k" in the limit, meaning we must have Pr(D.ki + D.kg) + (this is equivalent to the existence of p²). Thus, by the same argument this implies that Detect (U.( has vanishing error the limit. The complete argument requires singleton identifications success, but since T is linear in B, so long as K poly(n), constant B suffices for vanishing error.
union bound over all of the
C.7.3 Singleton Identification in i..dd. Spectral Noise
In this section, we discuss how to ensure that we can detect the true non-zero index r" from the delayed samples, under the i.i.d. noise assumption. We first discuss the delay matrix itself. D 2 xn. As in the noiseless case, we want to choose this matrix to be a group testing matrix. For the purposes of theory, we will choose D such that each element is drawn i.i.d. as Bern (z) for some
@(1). We denote the tt row of D d, Each group test is derived from of the delayed samples. Under the i.i.d. spectral noise model, this means each sample has the form:
U,(k)
Σ F(r) + Z,(k)
(69)
Hr=k
rsd:
F(r')1 < d.) Zik),
(70)
26

---

where Zik ~ N (0, (N, o²) Essentially, we can view this as a hypothesis testing problem, where we have one sample X, and hypothesis and the alternative are:
Ho : X 7 H1 = F(r") + 2, Z ~ N((,0²²)
Furthermore, lets say the magnitude of |F]] is known. We construct threshold test:
(xx) = 1 {|x] > 7}
(71)
With such a test, we can compute the cross-over probabilities:
Po1
Pr (Ix] 7) 2Q(1/o), Hn
(72)
P1o Pr (|x) < H1
- (((-))(0((--)/))))
(73)
For the sake of simplicity, we will make the choice to choose 7 such that pio = po1- In that case, we numerically solve for the cross-over probability which is fixed for given signal-to-noise ratio.
Crounea Probati
0.3
36
w/r
Figure 14: Symmetric cross-over probability induced by hypothesis testing problem for noisy singleton identificatinndettettinn.
Now can use [4), to prove our desired result. let q be the resulting cross-over probability for given p/o. The probability that all of our Singleton identifications succeed can computed by union
bound on P = Pr + k) S n If = poly(n), a constant suffices us to drive the union bound zero.
Lemma C.8. For any fixed SNR, taking De such that each element is Bern (1) and t = (nn)) for E (0, 1), taking Pi (t lo)(n)) suffices to ensure that we can achieve error of bin identification failure with probability of error O(1/K" ()/
C.7.4 Singleton Detection i.idd. Spectral Noise
We note that the general flow this proof follows [40], but there are several fundamental differences that make this proof overall quite different. We define & as the error event where bin k is decoded wrongly, and then using a union bound over different bins and different iterations, the probability of the algorithm making mistake in bin identification satisfies
Pr(E)= < (# of iterations) X (# of bins) x Pr(E,)
The number of bins is at most K for some constant and the number of iterations is at most CK (at least one edge is peeled off each iteration in the worst case). Hence, Pr(E) S nCCKP)((E). In order to satisfy Pr(E)= < O(1/K) K), we need to show that Pr(&,) < O(1/K*).
We already showed in Lemma C.8 that vanishing error (11/33) with delay matrix D " 2 xn.
achieve singleton identification under noise with
To achieve type detection, construct another pair of delay matrices D E 2. and D E Zfax' We will choose D and 2 such that each element is drawn i..d. as a Bern (/1) We denote
27

---

the :dh row of D' as d and denote the ith row of D as df. Then, with these delay matrices, we can
obtain observations of the form
U1(K) Σ
F(r) + 2,(k
Hr=k
rsd;
U2(k) Σ
F(r) Z.(k).
Hr=k
rsd.
Note that we can represent these observations as
U = S W
U a W
with W W ~ o²..0²)), vector with entries F(r) for coefficients in the and binary signature matrices S' S with entries indicating the subsets of coefficients included each sum.
Then, we subtract these observations to obtain single observation U = U - U which can be written
U Sa + W
with W ~ (O, 2 and S St S This construction allows us to show that the columns of S sufficiently incoherent and hence can correctly perform identification.
Lemma C.9. For any fixed SNR, taking D and D such that each element is Bern ((1/2)2/1), and t (nn)) for a (0, 1/2) and taking P2 O(t log(n)) suffices to ensure that the probability Pr(E,) for an arbitrary bin can be upper bounded as Pr(E,) S O(1/K²).
Proof. In the following, we prove that Pr(E,) S O(1/K*) holds using the observation model. We consider separate cases where the bin in consideration is fixed zeroton, singleton, or multiton.
The error probability Pr(E,) for an arbitrary bin can be upper bounded as
Pr(Et) v
Σ
Pr(F + Hs(r, F(r)))
FE(H2, Har
Σ
Pr(Hs((, F(r)) F)
FE(
(P, ((r)) Hs(r, F(r)))
above, each of these events should be read
1. (F + Hs(r, F(r))}: missed verification in which the singleton verification fails when the ground truth is in fact singleton.
2. (fs(T, F(r)) < F}: false verification in which the singleton verification is passed when the ground truth is not a singleton.
3. (fs(F, Hs(r, F(r)): crossed verification in which singleton with wrong index-value pair passes the singleton verification when the ground truth another singleton pair.
We can upper- bound each of these error terms using Propositions C.10 upper- bound terms decay exponentially with P: except for the term Pr(r 7
C.I1 and C.12
Note that all K3).
O(I
We use Theorem F.3 to show that we can achieve Pr(f + r) < O(1/K3) we choose P1 = Ollog n). Since all other error probabilities decay exponentially with Ps, it is clear that if Pa is chosen as Pg = ( n),, the error probability can be bounded as Pr(&,) & O(1K33).
28

---

Proposition C.10 (False Verification Rate). For 0 0< PSNR, the false verification rate for each bin hypothesis satisfies:
Pr(Hs(E,F(T) - H2) se" (/1422-11)
Pgn?
+ K2E - -
(T, P(F)) HM) S a(t+)))
where P2 is the number of the random offisets.
Proof. The probability of detecting zeroton singleton can be upper-hounded by the probability of zeroton failing the zeroton verification. This means
Pr(Hs(FF ((F) + Hz) S Pr
|WI 2 (1 t)²?
P2
Se (v1+27-11)
by noting that W (N(0 and applying Lemma C.13
On the other hand, given some multiton observation U = Sa + W, the probability of detecting it as singleton with index-value pair (T, [(F) can be written
P2 - F())sp 1| s (1 ((+)))²)=
Pr(Hs(P, F(F) < HM) = Pr
Pr
where g S(a - ((F)ee))) and v W. Then, we can upper bound this probability
Pr (/10 11 vIl s (1 ?
11+
|
2702)
Pr
gg P2
2yp²
P2
To upper bound the first term, we use Lemma C.13 Note that the first term is conditioned on the event |l /P2 2 2yv², thus the normalized con-cantrality parameter satisfies 0, 2 2y. As result, we can use Lemma C. 13 by letting 72 = (1 + 7)v2. Then, the first term is upper bounded 4-))). To analyze the second term, we let B a (fF) and write g = S3. Denoting its support as L = s3))(3), we can further write SB = S. where S the sub-matrix of S consisting of the columns in L and Be is the sub-vector consisting of the elements in C. Then, we consider two scenarios:
by (P2)
The multiton size is a constant, i.e., = L- In this case, we have
Amiu (S]S2)11@2112 < ||S2Bcl1
Using |Bc|| 2 Lp², the probability can be bounded
[g 1
(15775) S
271²
Pr
S 2yn²
Pr
Ammin
P2
P/
Lp²
On the other hand, using Lemma C.14witt the selection we have
1/2 and 1) 142r. (1
2yy² T.p=
|g
Pg
(1-2x²²)
2 Znd
Pr
< 2712
S 212e 201220
P2
which holds as long as < Lp² (4 L
The multiton size grows asymptotically with respect to K, i.e. = w(1). As result, the vector of random variables g ScBe becomes asymptotically Gaussian due to the central limit theorem with zero mean and covariance
1 Lp²1
E Eight
2
29

---

Therefore, by Lemma C.13 we have
|gl|
2 11- g0? 2n² Se
Pr
S 2712
P2
which holds as long as < /p²/1²= LMSNR.
By combining the results from both cases, there exists some absolute constant > 0 such that
Pr
|g
S 2712)
S -K---t(1--2""
P2
as long as 7 < /2/(402)= SNR.
Proposition C.11 (Missed Verification Rate). For 0 < < 2 SNR, the missed verification rate for each bin hypothesis satisfies
Pa (0'162-0)
Pr(Hz c Hs(r, F(r))) se" 14204/02
Pr(HM < Hr,rr F(r))) se (VL+251111 + 2e 202 Pa + +Pr(f + r)
where P2 is the number of the random offsets.
Proof. The probability of detecting a singleton as zeroton can be upper bounded by the probability of singleton passing the zeroton verification. Hence, by noting that W ~ NN(0, I² and applying
Lemma C.13
Pr(Hz + Hs(r, Firl))
1
$ Pr
F(r)s w (1+
P2
(0-) 1420"10"
which holds as long as 7 p²/p²² u
On the other hand, the probability of detecting a singleton as a multiton can be written as the probability of failing the singleton verification step for some index-value pair (f, F(F). Hence, we can write
1
Pr(Has Hs(r, F(rl)) Pr
U
P|ris
(1 7)²²
< Pr
1
U
(1 ?)?²
P = F(r) [[]]= AF-)A-1)
P2
Pr (F * F(r) #1
Then, using Lemma C.13,
the first term is upper-bounded
F(1s | 2 F
Pr
U
S Pr
2 2 2 (1 (1+7)e2
P2
P2
Se (V142--11)
On the other hand, the second term can be bounded as
Pr( * F(r) VF < Pr (r(FFF) FT) + (r(
= +
+ Fbb
PP Fr)
< Pr((FF] #
30

---

The first term is the error probability of BPSK signal with amplitude p. and it can be bounded as
Pr(FFT Fi S 2e ne P2
Proposition C.12 (Crossed Verification Rate). For 0 < < SSNR, the crossed verification rate for each bin hypothesis satisfies
Pay
Ke -c(1 (1--taz2) Ps + KK2 (x1--=(11_20) P28/0
Pr(H.s(T, Hs(r, S 4(14
where P2 is the number of the random offsets.
Proof. This error event can only occur if singleton with index-value pair (r, F(r)) passes the singleton verification step for some index-value pair (F, F(F) such that + Hence,
Pr(Hs (F, F(F) ((r(r,(()))
Pr
1
F[r]s
F[r|s= + w (1 77)²))
P2
1
Pr
|SB w s (1+
P2
1
Pr
|S W 2 < (1 + 7)r²
|| > 2y22
P2
Pr
(|SB) < 2yy²)
where ,3 is 2-sparse vector with non-zero entries from fpr -p) Using Lemma C.13 is upper-bounded as
the first term
1 P2
Pr
183+
wIl < (1+7)v² ||8112 > 2712) S .गन
By Lemma C.14 the second term is upper bounded as
30 (1- 222
Pr (1|S3||| & 22x²) I 8e
k,p
which holds as long as y < (2/((2²)= 3SNR.
Lemma C.13 (Non-central Tail Bounds (Lemma 11 in 13 13)). Given any E R.P.P and Gaussian
vector NO0,, I),, the following tail bounds hold:
Pr
g
vIp2 2n m) Se (Vv -
v11
(1+00-72/02))
Pr
v11 $ T2 Ig p
Se - 172%
for any and T2 that satisfy 2211 2 + 00) 2 where
0. = |g[|
Pv2
is the normalized non-centrality parameter.
Lemma C.14. Suppose 3 = O(1,, 2(1), and /. = (n) for some a E (0,1/2). Then, there exists no such that for all n. 2 nip we have
Pr Amii
[ P2.
< 23(1 B) B)- (2L 022 1)1) < 212 exp (-7
(-
n2
31

---

Proof. For any sampled uniformly from vectors up to degree t, the probability that it will have degree can be written as
Pr = k)) Σk=1 (2)
We know that the entries of s, are given as (s,); fr S d!} and (s²); = 1 (r S de). Therefore,
Pr ((s+): = 1) = Pr (d. = 0, Vj E supp(r))
Σ Pr (d) = V, supp(r))|z) k) Pr (rrl = k)
Ei= gt/+
Ek=z
=: gl, m)
With / = (1) and t = O(n)) for a E e0,,1/2), we can show that lim, g(t, n) B. Therefore, there exists some such that Pr ((s)); = 1) - 31 - 1 for all n 2 no. For the rest of the proof, let g Pr ((+)); 1) and assume [g - 31 S 17.
Then, recalling (s,); = (s)): - (s.); the distribution for each entry of s. can be written as
Pr ((s,); = 1) = Pr ((s+); = 1) = g(1 - g).
Hence, using Hoeffding's 's inequality, we obtain
1 22(1 P2
1 1
T PR 2
Pr
s Pr
[ S, S 2g(1 g) -1) S <exp
Furthermore, the conditional probability of another vector m + r being included in test is given by Pr ((sm); 1|(s)); 1, |rl
k) Pr (dij 0, vj E supp(m) \ supp(r)][r( k))
Σ (B)+)
(1-7)
1
k: h
x-e
7i
k
k
@l/t
1
n n
ft, n, k).
With 3 ((1) and f = Onn") for (0, 1), for any k S t, we can show that lim ft,, 8. Therefore, there exists some no such that Pr ((s 1|(s)); 1) - $ for all n ng- For the rest of the proof, let f Pr ((sm)) 1[(s)) 1) and assume if -31 S 17. On the other hand,
Pr ((sm))(s+)) 1) =2fg [1 - 9- (1 ffgl Pr (((())((S5)) = -1) = 22 [ - -/
As result, we have
(((m)))(s))) = 2g(f - -g).
Since lim (s.)) O, there exists some no such that -77 S B[(sm))(s)))) S n for all 2 nn. For the rest of the proof assume 17 < (((m) < As a result, we can write
1 T Pr
(- 112 Pg
s sml 2 2n) < Pr (Is, sm - P. 2 Pan) S exp
P2
2
32

---

By Gershgorin Circle Theorem, the minimum eigenvalue of 1 Pg
S is lower bounded as
1 STSC
1
Amin
2
min rec
|
srl
Σ mEL myfr
ssp
8ml
P2
P3
Lastly, we apply union bound over all (r, m) pairs to obtain
(1SSSE)) s 23(1 B) (2L 1)1) $ 21 2222expp exp
12 (-
Pr (Amin
$21
(-2 P2
P2-
D Worst-Case Time Complexity
this section, we discuss the computational complexity of Algorithm I which is broken down into the following parts:
Computing Samples Computing samples for one sapling matrix requires computing the row-span of He, which can be computed in n2 operations. Then for each sample, we must take the bit-wise and with each row of the delay matrix, so the total complexity is: Cn2MP.
Taking Small Mobius Transform Computing the Mobius transform for each of the CP subsam- pled functions CP22
Singleton Detection To detect each singleton requires computing y. This requires P divisions for each the C2 bins, for a total of C22 operations.
Singleton Identification To identify each singleton requires different complexity for different assumptions.
1. In the case of uniformly distributed interactions, singleton detection is O(1), since y k* immediately, so doing this for each singleton makes the total complexity CK.
2. In the noiseless low degree case decoding k* from poly(n), so for each singleton the complexity is CK (nly(n)
Message Passing In the worst case, we peel exactly one singleton per iteration, resulting in CKK subtractions (the above singleton identification bounds already take into account the need re-do singleton identification).
Thus in the case of uniformly distributed and low degree interactions respectively, the complexity is:
Uniform distributed noiseless time complexity
O(CPn2' + +PP2 + CK)
O(CPnK)
O(n²K).
Low degree (noisy) time complexity
O(CP22' +CP + CK poly(n))
OCCPPolyy())
(p)olynn)K).
E
Additional Simulations
In this section, we present some additional simulations that did not fit in the body of the manuscript.
Fig 15 and [6] Plot the runtime of SMT vs. under both of our assumptions. both cases we observe excellent scaling with We note that our low degree setting has higher fixed cost since
33

---

are using linear programming to solve our group testing problem and the solver appears to have some non-trivial fixed time cost.
Fig. 17 plots the perfect reconstruction percentage against n. and sample complexity. We also observe phase transition, however, the phase threshold appears very insensitive n, expected, since sample complexity requirement is growing like log(n), and we are already plotting on log scale.
10
SALT
Rowstne Complesity (eec)
10/
107
Complesit
10-2
10m2
10'19
21
2200
100
200
3000
2400
400
2000
500
2000
600
2.00
700
800
900
20000
1000
2.00
2000
2300
2000
2000
2000
2700
2003
2000
2000
Figure 15: Time complexity of SMT under As-
Figure 16: Time complexity of SMT under as- sumption [.2 The parameters and are fixed and plot the runtime v.s. n. Our theory says we have poly (n) complexity. In practice, for reasonable n our algorithm is running quickly.
sumption 2.1 The parameter K fixed and we plot the runtime v.s. n. our algorithm remains possible to run for n = 1000 where other com- petitors fail.
100%
Perfect
Somple Compleciy
10*
60%
40%
10'
X
0%
100
200
300
400
500
800
700
800
800
1000
N
2300
2000
2300
2000
2000
2000
2200
2000
2000
g2000
Figure 17: Perfect reconstruction percentage plotted against sample complexity and under Assump- tion 2.2 Holding = 3, we seale 6 increase the sample complexity. We observe that the number of samples required achieve perfect reconstruction is scaling linearly is very insensitive to as predicted. We also include N 2n on the bottom axis, which is the total number of interactions. In this regime we do not appear to consistently maintain error. This could be due to the fact that the asymptotic behaviour of group testing might not yet be fuly realized in the regime with n S 1000.
F
Group Testing
F.1
Group Testing Achievability Results From Literature
Theorem F.1 (Part of Theorem 4.1 and 4.2 in 15 Asymptotic Rate Noiseless Group Testing: Consider noiseless group testing problem with (nn)) defects of elements. We define the rate of group testing procedure as:
R == log (?)
(74)
T
where T is the number of tests performed by the group testing procedure. For an i.i.d. Bernoulli design matrix, for E [0, 1/3), in the limit as n + oc, a rate REERN = is achievable with vanishing error. Furthermore, for the constant column-wett weight design matrix, for 0 [0, 0.499 rate Ricww = is achievable with vanishing error.
Theorem F.2 [42 [4]). Noiseless Group Testing: Consider the noiseless non-adaptive group
testing setup with
k| defects out of n items, with scaling arbitrarily in Let k be the output
34

---

of a group testing decoder and let T = ④ (min { (tlog(n),n)) Then there exists strategy using
T & (1 + +)T* such that in the limit as n we have:
Pr x O.
(75)
Furthermore, there is a poly(n) algorithm for computing k. From 54 for L = o(n) we can achieve:
Pr
k x k
S En
(76)
with number of tests T O(1 3)g(o))
Note that the above error rate is not state-of-art result, but suffices in this case for our proof, and is very convenient in its form.
Theorem F.3
Noisy Group Testing Under General Binary Noise: Consider the general binary noisy group testing setup with crossover probabilities p1o and pmi We use i.idd Bernoulli
testing with parameter v > O. There a total of [k] = t O(n") defects, where @ E (0, 1). Let
T max (D)
1 T2
T I D) D) TIND)>. }. where we have
T(D) = (P (()oo))
t log(t),
(77)
P10)
T(ND)
vwD(a/w) tlog(n),
(78)
T(D)
+ :log(t),
(79)
ve- P10) D(3/11))
1 log(n)) T2 (NDD) VPo1 D(3/Po1)
(80)
where D(x) = x log(z) - 1, and w = (1- P + P10 B (po1, Piu), there exist number of tests T (1 c)T where the Noisy DD algorithm
-e For any a E 1-
produces k such that in the limit as > Dc we have:
Pr k + k)
- 0.
(81)
The above result state-of-art for noisy group testing and could be of interest generally for proving the type of results we have here, however, but for simplicity, we state similar more compact result that suffices for our proofs this paper.
Theorem F.4 (544). Lei |k| = I o(n), and consider an i..dd Bernoulli design group testing matrix. Further consider the binary symmetric noise model with crossover probability q. If we construct k via the noisy column matching algorithm, we achieve:
Pr 1 + k
S 5n.8.
(82)
with number of tests
T 16(1 [ + (7)(++7)(11+3) ())(2) log(n).
(83)
1-c-2(1 2 22
where y is constant that depends on B.
F.2 Group Testing Implementation
We implement group testing via linear programming. As noted in (5), linear programming generally outperforms most other group testing algorithms in both the noisy and noiscless case. We use the
35

---

following linear program, to implement group testing.
P
min k
Σ ==1
A
f
s.t.
0
2₂2
(84)
5 p S.t. 1// =1
d = 4n s.t. 4/ =0 0
d + Ep 21 1 pss.t V/ =1
G
Impact Statement
Rigorous tools for understanding models potentially profoundly increase trust in deep learning systems. If we can understand and reason for ourselves why model making a decision, we can put greater trust into those decisions. Furthermore, if understand why model is doing something that we believe incorrect, we can better steer it towards doing what we believe correct. This "steering" " of model behavior is sometimes described alignment, and is critical task for addressing things like incorrect or misleading information generated by a model, or for address any undesirable biases. In terms of concerns, is important not misinterpret over-interpret the interaction indices that come out of SMT. It could be the case that looking over some selection of interactions doesn't 't reveal the full picture, and leads one down an incorrect line of reasoning.
36

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable answer "[No] provided a proper justification given (e.g.. "error bars are not reported because it would be too computationally expensive" "we were unable find the license for the dataset general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer is often more nuanced, so please just your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] question, in the justification please point to the section(s) where related material for the question can be found.
used"). In
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction explicitly state the main theoretical contributions of this work. The main contributions section highlight this, and specifically call out the theoretical nature of this work. The introduction contains information about the practical applications and motivations. A detailed descriptions of assumptions is left to Section 2, to avoid an overly technical introduction, but is made clear that there limiting assumptions
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
37

---

Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
There is a limitations section, and limitations are mentioned periodically when relevant.
Justification;
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The proofs are included in the Appendix, and complete and correct. Section 3 and are effectively a proof sketch explaining how and why the algorithm works.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
38

---

The algorithm is exactly stated in the paper, and inplementation details (specifically related to group testing) are included in the appendix. reader would be able to exactly reproduce our code with the given information. We plan to release the code with the camera ready version.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is included.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//iips.cc/pult httpssscccppplccccceeeeeeee http:/gdddscccceee https//cccpiicccgiieeeeeeeeeeee http:/uddddeeeeeeeuuussssttteooo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
39

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The algorithms are relatively simple and complicated implementation details are in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bars are included in the main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric eтror bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments are not run at very large scale and runtime numbers are included only for relative comparison.
40

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compule required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Ethical concerns satisfied.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Though this work is primarily theoretical, there is clear application in mind, and thus is discussed in appendix section G.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
41

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The details of the code included in the main body of the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
42

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "PbLAj9PCyR", "reviewer": "Reviewer_jcxh", "summary": "This paper proposes an algorithm to efficiently compute Mobius transform under the assumption that the function to be transformed is composed of sparse and low-degree interaction terms. The paper also provides an asymptotic analysis of the sample complexity, time complexity, and accuracy of the algorithm.", "questions": "See weaknesses above\n\n---\n\nAfter rebuttal: The authors' response mostly addresses my concern about the singleton detection algorithm. The authors also commit to incorporating the relevant literature into their paper. Therefore, I have raised my score to acceptance.", "limitations": "NA", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper focuses on an important problem in Explainable AI, i.e., how to efficiently compute the Mobius transform (or equivalently, the Harsanyi dividend [cite1]) of a function to obtain the interaction between different input variables. The computation requires inferences on $2^n$ different subsets of input variables, which is intractable in general. The paper proposes an algorithm that leverages the sparse and low-degree structure of the interactions observed in experiments, thus reducing the computational cost.\n\n2.\tThe algorithm is presented in full detail, with straightforward examples to illustrate each step.", "weaknesses": "I have been studying explainable AI (XAI) for years, with a special interest in the Shapley value, the Shapley interaction index, and the Mobius transform. I am impressed by this work and greatly appreciate the progress in the efficient computation of Mobius transform. The sparsity and low-degree structure of interactions and the proposed algorithm can be of great interest to the XAI community, because they help explain a neural network’s decision-making logic into sparse symbolic interactions.\n\nHowever, I find that the claim and corresponding proof on the singleton detection algorithm are incorrect, and the literature review is insufficient. Nevertheless, **I would like to significantly raise my score to acceptance if these concerns are appropriately addressed.**\n\n1. The most important part of the proposed method is the singleton detection algorithm (in Section 4 and Appendix C.7). However, I find that the claim “singleton identification and detection can be performed without error in the noiseless setting” and the corresponding proof (in Appendix C.7.1) are incorrect. To be specific, the proposed method uses $U(j)$ to efficiently compute of the Mobius transform if $U(j)$ passes the singleton detection, but I find that the singleton detection algorithm in the paper cannot guarantee that $U(j)$ *is indeed a singleton*, although the paper claims that it can.\n\n To this end, we can easily find counterexamples on which the singleton detection algorithm fails. In summary, we can prove that the algorithm will fail under the following conditions. Given the number of input variables $n$ and the subsampling parameter $b<n$, the interactions satisfy (1) $\\forall k\\in \\\\{0,1\\\\}^n$ s.t. the first $b$ elements of $k$ are all 1’s, $F(k)=-\\delta$ if $|k|=n$, $F(k)=\\frac{\\delta}{n-1-b}$ if $|k|=n-1$, and $F(k)=0$ if $|k|<n-1$, where $\\delta \\in \\mathbb{R}$ is an *arbitrary* scalar (2) $\\forall k\\in \\\\{0,1\\\\}^n$ s.t.  at least one of the first $b$ elements of $k$ is 0, the value of $F(k)$ can be *arbitrary*.\n\n**Counterexample:** Let us consider $n=6$ input variables and set $b=2$ for subsampling, which follows the setting in Figure 3. Suppose there are five non-zero interactions in total: $k_1=110111, k_2=111011, k_3=111101, k_4=111110, k_5=111111$. And $ F(k_1)= F(k_2)= F(k_3)= F(k_4)=1/3$, $F(k_5)=-1$. In the $c$-th subsampling run, let the subsampling matrix $H_c=[[1,0,0,0,0,0],[0,1,0,0,0,0]]$. Then, we will obtain $u_c(00)=f(001111)$, $u_c(01)=f(011111)$, $u_c(10)=f(101111)$, $u_c(11)=f(111111)$, and also $U_c(00)=0$, $U_c(01)=0$, $U_c(10)=0$, $U_c(11)=F(k_1)+ F(k_2) + F(k_3) + F(k_4) + F(k_5)$. \nThe next step in the proposed method is to detect if each $U_c(j)$ is a zeroton, a singleton, or a multiton. This is done by adding different unit vectors $d_{c,p}=e_p, p=1,…,n$, and obtain $u_{c,p}(l)=f\\left(\\overline{H_c^\\top \\bar{l} + d_{c,p}}\\right) \\rightarrow U_{c,p}(j)=\\sum_{k\\le \\bar{d} \\ s.t. Hk=j} F(k)$. We list the results of $U_{c,p}(j)$ for $j=11$, in the following table:\n\n|              | p=0    | p=1    | p=2    | p=3    | p=4    | p=5    | p=6    |\n| ------------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |\n| $d_{c,p}$            | 000000 | 100000 | 010000 | 001000 | 000100 | 000010 | 000001 |\n| $U_{c,p}(11)$ | 1/3    | 0      | 0      | 1/3    | 1/3    | 1/3    | 1/3    |\n\n**The above counterexample passes the singleton detection algorithm, but $U_c(11)= F(k_1)+ F(k_2) + F(k_3) + F(k_4) + F(k_5)$ contains five terms and is apparently not a singleton.** To be more specific, we can see that the metric $y_{c,p}=1-\\frac{U_{c,p}(11)}{U_{c,0}(11)}$ is either 0 or 1, for $p=1,…,n$. Therefore, according to the criteria in Equation (9), the multiton $U_c(11)= F(k_1)+ F(k_2) + F(k_3) + F(k_4) + F(k_5)$ will be mistakenly judged as a singleton by the algorithm. As a result, the algorithm will yield an incorrect output that contains only one interaction term, while the ground truth contains five interaction terms.\n\nI suggest the authors either revise the claim and the proof in Appendix C.7.1 to be in an asymptotic or probabilistic manner, or provide detailed discussion to the failure cases of the singleton detection algorithm. Even though the algorithm cannot handle all scenarios, I’m still willing to raise my score if proper discussion on the failure cases is added.\n\n---\n\n2. The literature review is insufficient. The core background behind the proposed method is the sparsity of Mobius transform. In fact, the sparsity of Mobius transform (or equivalently, the Harsanyi dividend) has been well studied by many previous works, but these works are not properly discussed in the paper. For example, [cite2, cite3] observed the sparsity of Mobius transform on a wide range of network architectures (e.g., MLPs, CNNs, transformers, PointNet) trained on various tasks (e.g., tabular data classification, image recognition, sentiment analysis, pointcloud classification). [cite4] explored the source of the sparsity and even proved the sparsity of Mobius transform under three sufficient conditions. The authors are expected to include these previous works in the Related Work section or in the discussion of the sparsity assumption in Section 2.\n\n---\n\n3. The paper reports the relationship between Mobius transform and the Shapley value in Equation (2) and Appendix A. However, this relationship has already been discussed in the original paper of Harsanyi dividend [cite1]. Therefore, I encourage the authors to cite paper [cite1] as a proper reference.\n\n\n[cite1] John C. Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194–220, 1963.\n\n[cite2] Ren et al. Defining and Quantifying the Emergence of Sparse Concepts in DNNs. CVPR, 2023.\n\n[cite3] Li and Zhang. Does a Neural Network Really Encode Symbolic Concepts? ICML, 2023.\n\n[cite4] Ren et al. Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs. ICLR, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n**Proof Correction** \n\nWe have corrected the technical issue you highlighted, and will include that information in a separate comment.\n\n**Literature Review**\n\n 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.\n\n**Final note**\n\n 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qvyrQqYsii", "reviewer": "Reviewer_kQft", "summary": "This study proposes a new efficient method to compute the Möbius Transform. To understand the behavior of large complex machine learning models, various studies have used game theory concepts such as the Shapley value to measure the impact of input variables on the model's outputs. While Shapley values only focus on individual impacts of input variables, Möbius Transform can score any subset of input variables, which can take into account higher-order interactions between input variables. One of the fundamental challenges of computing Möbius Transform is its exponential computational cost (i.e., requiring $2^n$ inferences with $n$ input variables). This study reduces its cost; with a sparsity assumption, the computation runs with $O(n)$ number of samples, and with a low-degree assumption, it further reduces to $O(\\log(n))$. The proposed method (Sparse Möbius Transformer; SMT) exploits a connection between the Möbius Transform in the original $n$-dimensional space (say, F-space) and that in a lower $b$-dimentional space (say, U-space). If the *aliasing set* is a singleton, then the Möbius Transform in F-space can be recovered from that in U-space. The authors proposed methods to detect singletons and turn mulitons into singletons using graph peeling. The experimental results justify the efficiency and the high faithfulness recovered by SMT.", "questions": "I'd like the Authors to answer the weaknesses raised above. Plus, \n- At Limitations, the Authors mentioned that \"we may be more interested in taking a sparse projection onto a subset of low-order terms\", but I'm not fully following this. Can't we resolve it simply by zeroing out the coefficients of high-order terms (just as \"a low-pass filter\")?", "limitations": "Limitations are adequately presented. For the potential improvements, see Weakness and Questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This study offers an efficient computational method of Möbius Transform, which encompasses widely used game-theoretic metrics such as Shapley values and Benzhaf values, and the accelaration from baselines is significant.\n- The proposed method is theoretically supported.\n- While the paper is densely theoretical, the paper writing is generally easy to follow. \n- While not strongly practical and large scale, the assumptions and claims are justified by numerical experiments at key points.", "weaknesses": "**Major comments**\n- The proposed algorithm works on a $b$-dimensional space, but I was not able to find out how $b$ is set in the experiments and ablation experiments on this hyper-parameter. While the theory suggests $b = O(\\log(K))$, this is not very suggestful due to the lack of the constant factor. \n- The baselines in Fig. 6 are all first-order metrics. In machine learning and computer vision, second-order metrics (e.g., Interactions) are also popular. Why were those methods not included in the experiments? \n\n**Minor comments**\n- It'd be better to clarify several notations, such as $|\\mathbf{k}|$ and $[K]$.\n- To better convince readers of the connection between Shapley value and Möbius basis, it'd be better to provide a deriviation of the left equality of Eq. (2). \n- In the main text, $C$, the number of samplings (?), appears a bit out of sudden at line 193.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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)\n\n[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).\n\n2. Fig. 5 focuses on comparisons with second order methods, and reveals the massive computational advantage of our method as compared to those baselines. \nIn 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.\n\nQuestion 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.\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QQcsC9uzqu", "reviewer": "Reviewer_vNmZ", "summary": "The paper present a way to compute high-order interactions using Mobius transformation.", "questions": "how can the results of the paper be generalized to non-boolean functions? this would generalize the results from detecting interactions for explainability to a general case of interaction detection for any arbitrary dataset.", "limitations": "The assumption of having only K non-zero interactions, while in practice K is typically large for explainability.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The paper shows some interesting results on the sampling requirement for recovering the interactions among features, specially tailored for explainability with boolean functions (i.e., explanation game)", "weaknesses": "1. The paper is difficult to follow and does not have a clear storyline; most importantly, it is not clear how the significant interactions could be recovered at the end after obtaining the required samples\n\n2. 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.\n\n3. 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?\n\n4. 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.\n\nMinor: \nSome nations need more explanation as they are borrowed from other disciplines (as the authors also stated in the Introduction, the paper is multidisciplinary); For instance, the functional subsampling and aliasing that are the backbone of the sampling strategies, required more explanation to average reader of the paper, IMHO.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\n**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?\"\n\nA: 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. \n\nTheorem 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.\nTheorem $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\".\n\n**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.\"\n\nA: 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.\n\n[1] Ren et al. Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs. ICLR, 2024.\n\n[2] Li et al. Does a Neural Network Really Encode Symbolic Concepts? ICML, 2023.\n\n**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.\"\n\nA: 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. \n\n\n**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. \n\n**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$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers, ACs and Senior ACs. 

We have posted individual rebuttals to all three reviewers. We believe we have addressed the concerns of all reviewers. We would particularly like to thank jcxh as an outstanding reviewer. 

Taking into account the issues, which are now resolved, we are still confident in the candidacy of this manuscript, and look forward to the discussion period.

Meta-review: As the reviews and the follow-up discussion illustrate, this is an interesting contribution towards the theory and efficient algorithms for computing the Mobius transform that can be used to interpret which tokens in the input were the ones most responsible for the final output. The paper provides interesting connections with group testing and is technically solid (modulo a correction in one of the proofs pointed out in the review process). I recommend acceptance as a poster.
Decision: Accept (poster)