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

Authors: justin  singh kang
u c berkeley
landon  butler
ramtin  pedarsani
santa  barbara
kannan  ramchandran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:39:19

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\"{o}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.

Main paper: 
 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 we learn? The Shapley value [1] , a 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 or tokens. This value represents the weighted average marginal contribution of an input, quantifying the change in the function'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] , a mathematical transformation that projects functions onto a fundamental interpretable basis known in game theory as the unanimity function basis.The Möbius transform has a 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 Figure 1 : The movie review "Her acting never fails to impress" is passed into a BERT language model fine-tuned to do sentiment analysis [8] . Presented are 1 st , 2 nd and 3 rd order Möbius coefficients, with positive interactions in green and negative in red computed via (1) . The coefficients explain how groups of words influence BERT's perception of sentiment. For instance, while never and fails have strong negative sentiments individually, when combined, they impose a profound positive sentiment.f            Her acting never fails to impress            = F            Her acting never fails to impress            + F            Her acting never fails to impress            + F            Her acting never fails to impress            + F            Her acting never fails to impress            + • • • + F            Her acting never fails to impress            + F            Her acting never fails to impress            + F            Her acting never fails to impress            + • • • + F                      = F            Her acting never fails to impress            + F            Her acting never fails to impress            + F           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. 1 . The model's objective is to classify the sentiment of the review as positive or negative. The Möbius transform assigns a score to all word subsets within a sentence. For instance, in the sentence "Her acting never fails to impress" each subset of words is evaluated-positive 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 to 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 2 n inferences (masking over all 2 n subsets of features), as well as n2 n time using a divide-and-conquer approach similar to that of the Fast Fourier Transform (FFT) algorithm. GPT-4 currently supports in the range of 8000 words-per-prompt, and context length will continue to grow with new architectures [9] . Running inference 2 8000 times is not even close to possible, and even if you could, 2 8000 coefficients are hardly interpretable! In Fig. 1 we see that many coefficients are insignificant. This is typical. The solution to 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-assuming that only K Möbius coefficients (which K values are significant 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 O(Kn) with O(Kn 2 ) time. We also explore the regime where the non-zero interactions occur between at most t inputs, with t ≪ n, showing that only O(Kt log(n)) samples are required in 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 a value function for a model with n inputs across subsets S ⊆ [n] denoted as f (S). The construction of this function varies based on the model: in Fig. 1 , 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 : Z n 2 → R, where f (S) = f (m) with S = {i : m i = 1}. The relationship between f : Z n 2 → R and its Möbius transform F : Z n 2 → R is characterized by the forward and inverse transforms:EQUATIONwhere k ≤ m means that k i ≤ m i ∀i. This transform acts as a bridge, connecting various importance metrics, which can be expressed as projections onto a subset of the Möbius basis. The Shapley value SV(i) and Banzhaf value BZ(i) for feature i is elegantly represented within this framework:EQUATIONThese relationships are foundational to the definition of the Shapley and Bhanzaf values themselves.The left equality appears as Eq. 10 in Lloyd Shapley's original report from 1952 [1] where the concept of Shapley value was first introduced and is central to his derivation of a closed-form expression.This work is inspired by the literature on sparse Fourier transforms, which began with [10, 11, 12] . The sparse Boolean Fourier (Hadamard) transform [13, 14] is most relevant.Group Testing This manuscript establishes a strong connection between the interaction identification problem and group testing [15] . Group testing was first described by Dorfman [16] , 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 a feature selection/importance problem, using a group testing matrix in their algorithm. [18] also mentions group testing in relation to Shapley values.Möbius Transform Möbius transforms [5] have been studied in the pseudo-Boolean (set) function literature, and dates back to at least [19] . [20] develops a framework for computing sparse transforms of pseudo-Boolean functions. They do not directly consider the Möbius transform as we define it, but one can apply their algorithm to compute a K sparse transform in O(nK) adaptive samples and O(K 2 n) time. In the sparse and noiseless setting, our algorithm improves on this by being fully nonadaptive 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 [21] , the authors show that a classifier satisfying certain properties can be well represented by a sparse and low degree Möbius transform.Explainability [2] proposes model explanation via pseudo-Boolean functions approximated by Shapley values, effectively utilizing only first-order Möbius coefficients. Constructing these functions, [22, 23, 24, 25] especially for generative models with complex outputs [26, 27, 28] , is an ongoing research area. [3] presents the Taylor-Shapley interaction index (STII), scoring interactions up to size t. For sets smaller than t, STII are exactly Möbius coefficients. [4] introduces the Faithful Shapley Interaction index (FSI), which computes scores via projection onto up to t 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.In data valuation [18] the goal is to assign an importance score to data, either to determine a fair price [30] or to curate a 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, 33] try to approximate this by looking at the accuracy of partially trained models, though this introduces sampling noise.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 O(Kn 2 ) time in the limit as n → ∞ with K growing at most as 2 nδ with δ ≤ 1 3 . 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 wordlevel sentiment analysis task using a BERT model [8] like in Fig. 1 . 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 are in Appendix B. In all cases, the number of features n ≈ 20, for which it is possible to perform the full Möbius transform. On the top row, we plot achievable faithfulness R 2 as a function of sparsity. We observe that in all cases, faithfulness approaching 1 requires only a few thousand Möbius coefficients, motivating our sparsity assumption. The bottom row of plots considers achievable faithfulness vs. degree, i.e., what R 2 can be achieved using only Möbius coefficients F up to a given degree. Here we observe that in nearly all cases, low degree coefficients suffice to get quite small R 2 , motivating our low degree assumption.• We develop a formal connection with group testing and present a variant of SMT that works when all non-zero interactions are low order. If the maximum order of interaction is t = Θ(n α ) where α < 0.409 then we can compute the Möbius transform in O(Kt log(n)) samples in O(K poly(n)) time with error going to zero as n → ∞ with growing K. • Using robust group testing, we develop an algorithm that, under certain assumptions, computes the Möbius transform in O(Kt log(n)) samples, with vanishing error as n → ∞ 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-adaptive meaning that all samples can be computed in parallel. Code has been made publicly available 1 .Notation Lowercase boldface x and uppercase boldface X denote vectors and matrices respectively.x ≥ y means that x i ≥ y i ∀i. Multiplication is always standard real field multiplication, but addition between two elements in Z 2 should be interpreted as a logical OR ∨. We define subtraction, of xy for x ≥ y by standard real field subtraction. x corresponds to bit-wise negation for Boolean x, and x ⊙ y represents an element-wise multiplication. 
understanding assumptions: sparsity and low degree: 
 Computing the forward transform (1) typically requires sampling all 2 n 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 f :EQUATION)Note that this corresponds to the standard definition of R 2 in statistics when f is zero-mean, and we generally define f such that this is the case. A good explanation model should have a high R 2 , a succinct representation, and most importantly, be easily computed. For the Möbius transform, we aim to learn coefficients F (k) efficiently and construct f using the inverse transform (1) . With no restrictions on F (k) we can achieve R 2 = 1, but this fails to meet our simplicity criterion. Fortunately, many real-world functions are sparse-only a few F (k) coefficients need to be nonzero to yield R 2 ≈ 1. Fig. 2 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 a small number of Möbius coefficients to achieve R 2 ≈ 1. Furthermore, real-world functions are low degree, such that those small number of non-zero coefficients satisfy |k| ≤ t for some small t. This results in a 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 in 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) f : Z n 2 → R has a Möbius transform of the following form: k 1 , . . . , k K are sampled uniformly at random from Z n 2 , and haveF (k i ) ̸ = 0, ∀i ∈ [K], but F (k) = 0 for all other k ∈ Z n 2 . Assumption 2.2. (K t-Degree Interactions) f : Z n 2 → R has a Möbius transform of the following form: k 1 , . . . , k K are sampled uniformly from {k : |k| ≤ t, k ∈ Z n 2 }, and have F (k i ) ̸ = 0, ∀i ∈ [K], but F (k) = 0 other k ∈ Z n 2 .Assumption Limitations By assuming that the non-zero coefficients are uncorrelated and uniformly distributed, we aim to understand the fundamental difficulty in learning a 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 for p = 1 to P do 6:u c,p (ℓ) ← f H T c ℓ + d c,p , ∀ℓ ∈ Z b 2 7: U c,p ← FastMobius (u c,p ) 8:end for 9: end for 10: S = {(c, j, k, v) : Detect (U c (j)) = H S (k, v)} 11: while |S| > 0 do 12: for (c, j, k, v) ∈ S with k ∈ K do 13: F (k) ← v; K ← K ∪ {k} 14: for c ′ = 1 to C do 15: res ← U c ′ (H c ′ k) -F (k)(1 -D c ′ k) 16: U c ′ (H c ′ k) ←EQUATION) where we have the freedom to choose m ℓ . Critically, the Möbius transform of u, denoted U , is related to F via the well-known signal processing phenomenon of aliasing:EQUATIONwhere A(j) corresponds to an aliasing set determined by m ℓ . Fig. 3 shows this subsampling procedure on a "sparsified" version of our sentiment analysis example using different m ℓ . Our goal is to choose m ℓ such that the non-zero values of F (k) are uniformly spread across the aliasing sets, since that makes them easier to recover. If only a single k with non-zero F (k) ends up in 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. In this work, we have determined two different subsampling procedures that perform well under our two assumptions: 2. Under Assumption 2.2 with t = Θ(n α ) for some α ≤ 0.409, there exists a matrix H chosen from b rows of a near constant column weight group testing matrix.u 1 (00) = f (110011) u 1 (01) = f (110111) u 1 (10) = f (111011) u 1 (11) = f (111111) u 2 (00) = f (111100) u 2 (01) = f (111101) u 2 (10) = f (111110) u 2 (11) = f (111111) U 1 (00) = 0 U 1 (01) = F (k 3 ) U 1 (10) = F (k 1 ) U 1 (11) = F (k 2 ) + F (k 4 ) U 2 (00) = F (k 1 ) + F (k 2 ) + F (k 3 ) U 2 (01) = F (k 4 ) U 2 (10) = 0 U 2 (11) = 0           Her acting never fails to impress           =           0 0 1 0 0 0           = k1           Her acting never fails to impress           =           0 0 0 1 0 0           = k3           Her acting never fails to impress           =           0 0 1 1 0 0           = k2           Her acting never fails to impress           =           0 0 1 1 0 1           = k4With the given H, non-zero indices are mapped to the 2 b sampling sets A(j) independently and uniformly at random asymptotically, thus maximizing the number of singletons when b = Θ(log(K)).In both cases the matrix H can be viewed as a part of a group testing matrix. This is explicit under Assumption 2.2, but under Assumption 2.1, H can be viewed as part of an individual testing matrix, where elements are tested one-by-one. These matrices are optimal in an information-theoretic sense because they achieve an optimal rate asymptotically in their respective setting. We can think of rate as the amount of information about k what we get from the matrix product Hk (see [15] for a 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 a 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.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. 
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 U (j) is a singleton. Secondly, we need to identify the value of k that singleton corresponds to. Section 4 discusses both tasks. For now, we discuss the rest of the algorithm assuming that we can accomplish both tasks.Recovered SingletonSampling Group c = 1 Sampling Group c = 2Figure 4 : Depiction of our peeling message passing algorithm for the samples in Fig. 3 . The singleton in U 2 (01) is subtracted (peeled) so we can resolve F (k 2 ) from U 1 (11) .Since we don't know the non-zero indices beforehand, collisions between multiple non-zero indices in the same aliasing set are inevitable. These are called multitons. One approach to deal with these multitons is to repeat the procedure over again: Peeling algorithms were popularized in information and coding theory for decoding fountain codes [38] and have since been applied to 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.u c (ℓ) = f (m c,ℓ ) ⇐⇒ U c (j) = k∈Ac(j) F (k), c = 1, . . . , CQuestion: 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 are complete and correct. Section 3 and 4 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 crossreferenced. • 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 to provide a 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. 
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 ∈ Z b×n 2, and f : Z n 2 → R, and some d ∈ Z n 2 . If U is the Möbius transform of u, and F is the Möbius transform of f we have:EQUATIONThe proof can be found in Appendix C.4. The form of ( 6) allows us to shrink the aliasing set in a controlled way. Define d c,0 := 0 n , and D c ∈ Z P ×n 2 for some P > 0. The i th row of D c is denoted d c,p , p = 1 . . . , P . Using these vectors, we construct C(P + 1) different subsampled functions u c,p :EQUATIONWe compute the Möbius transform of each u c,p denoted by U c,p and construct a vector-valued function U c (j) := [U c,0 (j), . . . , U c,P (j)] T . The goal of singleton detection is to identify when U c (j) reduces to a single term, and for what value k that term corresponds to. To do so, we define the Type (•):1. Type (U c (j)) = H Z denotes a zeroton, for which there does not existF (k) ̸ = 0 s.t. Hk = j. 2. Type (U c (j)) = H S (k, F (k)) denotes a singleton with only one k with F (k) ̸ = 0 s.t. Hk = j. 3. Type (U c (j)) = H M denotes a multiton with more than one k with F (k) ̸ = 0 s.t. Hk = j.To describe our type estimation rule, we define the following ratios between elements of U c (j):EQUATIONand construct the vector y c := [y c,1 , . . . , y c,P ] T . Then, our estimate for the type is given byDetect (U c (j)) :=    H Z , U c (j) = 0 H M , y c / ∈ {0, 1} P H S (k, F (k)), y c ∈ {0, 1} P . (9) By considering the definition of U c it is possible to show that if Type (U c (j)) = H S (k * , F (k * )), then y c = D c k * .When we have a singleton taking D c = I, and thus P = n suffices to recover k * . So long as the non-zero coefficients, F (k) are not chosen in an adversarial way, this choice of D c also ensures that Detect (U c (j)) = Type (U c (j)). 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 do better if we don't have any extra information about k * , but we can if we know |k * | ≤ t as we show below. Going back to our example in Fig. 3 , with D c = I we use a total of 8 × 7 = 56 samples as opposed to 2 6 = 64. While this improvement is modest at this scale, for larger problems the improvement is dramatic.Singleton Identification in the Low Degree Setting Let's say we want to determine the singleton from U 1 (10) in Fig. 3 , and we know |k * | ≤ 1. By exploiting group testing, it is possible to design D c with fewer rows, and thus fewer overall measurements:Decode y k 1 k 1 = D c = y Her acting never fails to impress 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 Figure 5:We use group testing [16] to identify the singleton k 1 , which corresponds to the first-order term "never". By designing the masking patterns with the help of group testing, we can efficiently recover interactions with O(t log(n)) extra measurements.The matrix product D c k * has a different output for each |k| ≤ 1. 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 c = I. If all non-zero F (k) had satisfied |k| ≤ 1, we could use this matrix for our example in Fig. 3 . However, we only have |k| ≤ 3 for non-zero F (k) in this example, so D c as in ( 5) does not suffice. In the case of general |k| ≤ t, [42] says that for any scaling of t with n, there exists a group testing design D c with P = O(t log(n)) that can recover k * in the limit as n → ∞ with vanishing error in poly(n) time. If we also assume that F (k) are Detect (U c (j)) has vanishing error (see Appendix C.7.2).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:EQUATIONwhereEQUATION∼ N (0, σ 2 ). 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 (k i )|, such that the signal-to-noise ratio (SNR) remains fixed. Secondly, the matrix D c must be modified. It now consists of two parts:D c = [D 1 c ; D 2 c ]. We design D 2 c ∈ Z P2×n 2as a standard noise robust Bernoulli group testing matrix with P 2 = O(t log(n)) tests, which suffices for singleton identification under any fixed SNR [43] . However, unlike the noiseless case, the samples from the rows of D 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 conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: The algorithm is exactly stated in the paper, and implementation details (specifically related to group testing) are included in the appendix. A reader would be able to exactly reproduce our code with the given information. We plan to release the code with the camera ready version. 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 a 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 it 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or 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.In the case of closed-source models, it 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 to have some path to reproducing or verifying the results. • 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. 
results: 
 Now that we have discussed all components of the algorithm, we present our theoretical guarantees: For various values of t, we set n = 500 and K = 500, using a group testing matrix with P = 1000. We plot the performance of our algorithm against SNR, measured in terms of the R 2 . Error bands represent the standard deviation over 10 runs. (c) Runtime comparison of SMT, SHAP-IQ [29] , and t = 5 order FSI via LASSO [4] . All are computing the Möbius transform in the setting where all non-zero interactions are order t, K = 10. SMT easily outperforms both, while the other methods quickly become intractable. Error bands represent standard deviation over 10 runs. Figure 7 : Since our ultimate goal is compact, meaningful and computable representations, we compare representations generated from SMT (Algorithm 1) with other popular explanation models. We plot R 2 (faithfulness) vs. the number of terms used in the representation (sparsity). For Shapley and Banzhaf values, to generate an r-sparse representation, we use the top r magnitude values. For SMT and Faith-Banzhaf, we do a slightly more sophisticated refinement procedure. Faith-Banzhaf is included because it is the first-order metric that maximizes R 2 . As observed in the breast cancer and sentiment analysis tasks, SMT can achieve better R 2 than other approaches by utilizing higher-order interactions. In the sentence-level multiple choice dataset, we observe less of a difference, since in those cases the entire answer to a 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 (k)| = ρ is only due to limitations of group testing theory. In practice, we observe that a lower bound on the magnitude suffices. In addition to our theoretical results, we also conduct numerical experiments on synthetic and real word models, which are discussed below.We tested SMT's efficacy on functions satisfying Assumption 2.1 and 2.2, setting non-zeroF (k) uniformly in [-1, 1]. SMT is implemented as in Algorithm 1, with group testing decoding via linear programming (see Appendix F.2). Fig. 6a is a phase transition plot that shows the percent of cases where SMT achieves R 2 = 1 with fixed K = 100 at different sample complexities and values of n.We vastly outperform the naive approach: when n = 1000, we get perfect reconstruction with only 10 -294 percent of total samples! Furthermore, the number of samples necessary to achieve perfect reconstruction scales linearly in n as predicted. Fig. 6b assesses SMT under noise for various values of t, plotting R 2 against SNR with K = 500, n = 500, and P = 1000. Fig. 6c plots the runtime for SMT and competing methods. Test functions f have K = 10 non-zero Möbius coefficients at locations that satisfy |k| = 5 (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 5 th order FSI, as well as the method of [4] which computes 5 th order FSI via LASSO. As shown in Appendix A, the t th order FSI are exactly the t th 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 n ≥ 100. Additional simulations and discussion can be found in Appendix E.Our objective is a computable, faithful, and compact representation of real-world machine-learned functions. Fig. 7 addresses this goal head-on, by plotting R 2 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-based 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, we use the top r magnitude values. For SMT and Faith-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 2 . 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. 
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 a 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. 
 
 Appendix: Our assumption of independently sampled interactions was made for informationtheoretic hardness and may not hold in some settings where correlated interactions exist. For instance, in the sentiment problem in Fig. 1 , words with strong 2 nd order interactions are likely to appear together in important 3 rd order interactions. In such settings, correlation is exploitable, so a more specific algorithm can likely exploit this correlation and eliminate this assumption. Another limitation is that we have focused on taking a 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 can be achieved by truncation, however, with non-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 a sparse low degree Möbius projection, but do not have a sparse transform.Future Work Applying SMT to real-world tasks like understanding protein language models [45] , LLM chatbots [46] or diffusion models [47] would be insightful. Working with large and complicated models will likely require further improvements to robustness-both 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 in [29] 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) .We begin with some notation. We define the Möbius basis function (which are all possible products of inputs) as:EQUATIONNow we define the following sub-spaces of pseudo-Boolean function in terms of the linear span of Möbius basis functions: EQUATIONThe Shapley values SV(i) [1] of the inputs m i , i = 1, . . . , n with respect to the function f are [48] :EQUATION)where σ is the Shapley kernel. SV(i) = F (e i ) when f is a linear function.Banzhaf Index The Banzhaf index BZ(i) of the inputs m i , i = 1, . . . , n with respect to the function f are [48] :EQUATIONwhere µ is the uniform measure. BZ(i) = F (e i ) when f is a linear function.Faith Shapley Interaction Index The t th order Faith Shapley interaction index SV t (k) for |k| ≤ t [4] isEQUATION)where σ is the Shapley kernel. SV t (k) = F (k) when f is a t th order function, i.e., F (k) = 0 when |k| > t.Faith Banzhaf Interaction Index The t th order Faith Shapley interaction index BZ t (k) for |k| ≤ t [4] isEQUATION)where µ is the uniform measure. BZ t (i) = F (k) when f is a t th order function, i.e., F (k) = 0 when |k| > t.Shapley-Taylor Interaction Index The t th order Shapley-Taylor Interaction Index [3] STII t (k) is:EQUATION)where σ is the Shapley kernel. Explicitly, it can be shown that:EQUATION)As a consequence of the above, we have STII t (k) = SV t (k) = F (k) when f is a t th order function, i.e., F (k) = 0 for |k| > t.Let f be the real-world function we wish to explain. In subsections B.1, B.2, and 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 2 (faithfulness) for a variety of explanation models f , measured through:R 2 = 1 - f -f 2 2 f -f 2 2.where we use the notation ∥f ∥2 2 = m∈Z n 2 f (m) 2 .In Figure 2 , we consider settings where n ≈ 20, such that we can run optimization procedures to 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:EQUATIONEQUATIONAchievable Sparsity: On the other hand, we cannot efficiently find the optimal faithful K-sparse approximation due to the problem's combinatorial nature. Instead, informed by the strong faithfulness of low degree approximations, we employ the following heuristic to obtain some sparse approximation.Let S K ⊆ Z n 2 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:EQUATIONIn Figure 7 , we consider the four explanation models described below.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 r, we consider approximations that only include the top-r Banzhaf values by magnitude.Faith-Banzhaf Indices: We calculate Faith-Banzhaf indices using the regression formulation described in [4] . To measure the faithfulness captured by sparse approximations of Faith-Banzhaf indices, we modify the regression problem by adding an ℓ 1 penalty on the values of the Faith-Banzhaf indices. We vary the penalty coefficient to obtain different levels of sparsity.SMT: We run SMT (Algorithm 1) to obtain a sparse Möbius representation F with support supp( F ).Then, we fine-tune the values of the coefficients by solving the following regression problem over a uniformly sampled set of points D ⊆ Z n 2 :min f ,α m∈D ( f (m) -f (m)) 2 s.t. f (m) = k≤m,k∈supp( F ) α k , ∀m.To measure the faithfulness captured by sparse approximations, we modify the regression problem by adding an ℓ 1 penalty on the values of the Möbius coefficients. Then, we vary the penalty coefficient λ to obtain different levels of sparsity:min f ,α m∈D ( f (m) -f (m)) 2 + λ k∈supp( F ) |α k | s.t. f (m) = k≤m,k∈supp( F )α k , ∀m.We train an XGBoost model for classification using the Wisconsin Breast Cancer dataset [49] . This dataset contains the mean, standard deviation, and largest value of ten measurements, resulting in thirty features. For Figure 2 , we use 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 7 , we present the aggregated results over the first twenty.To explain the XGBoost model h (the probability associated with a positive classification) on each data point x ∈ 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 [h(X)|do(X m = x m )]where we use the notation x m = {x i : m i = 1}.We employ the sentiment analysis model from [8] , which is built upon BERTweet [50] , a RoBERTa model trained on English tweets. We take movie reviews from the IMDb Movie Reviews dataset [51] . For a particular review, we define its function as a mapping from maskings of words (using the [UNK] token) to the model's logit value associated to the correct sentiment classification.For Figure 2 , 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 22 respectively. In Figure 7 , we take a random sampling of reviews, with number of words spanning from 17 to 38. The reviews we used, alongside their word counts and sentiment, are included below:For multiple choice answering, we use a RoBERTa model [35] fine-tuned on RACE [52] : a largescale reading comprehension dataset. This dataset contains over 28,000 passages, each containing corresponding multiple-choice questions. For our experiments, we 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. We pass the masked passage, alongside the multiple choice question into the RoBERTa model, and measure the logit value of the question's correct answer. The characters are unlikeable and the script is awful. It's a waste of the talents of Deneuve and Auteuil. NegativeTable 1 the addition and multiplication table for arithmetic between x, y ∈ Z 2 . We also note that Z 2 is typically used to refer to the integer ring modulo 2. The arithmetic we are describing here is actually that of a monoid. Since the audience for this paper is people interested in machine learning, we continue to use Z 2 since it is commonly used to simply refer to the set {0, 1}. + x = 1 x = 0 y = 1 1 1 y = 0 1 0 Multiplication Table × x = 1 x = 0 y = 1 1 0 y = 0 0 0 Subtraction Table - x = 1 x = 0 y = 1 0 1 y = 0 N/AWhen a 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.1 is a key tool that we will use in this work to design subsampling patterns that result in good aliasing patterns.EQUATION)If U is the Mobius transform of u, and F is the Mobius transform of f we have:EQUATION)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 f . Understanding why we choose this relationship, however, is more complicated. Underlying this choice is 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 a simple and useful construction for H. . Let h i correspond to the i th row of H, given by h i = e ij , the length n unit vector in coordinate i j . Then if we subsample according to (23) we have:EQUATION)which happens to result in aliasing sets A(j) = {k : k i = j i ∀i ∈ I} all of equal size 2 b . The above choice H actually induces a rather simple sampling procedure when we follow (23) . For instance if I = [b], we have:EQUATIONIn other words, in this case, we construct samples by freezing nb of the inputs to 1 and then varying the remaining b inputs across all the 2 b 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 k 1 , . . . , k K be sampled uniformly at random from Z n 2 , where F (k i ) ̸ = 0, ∀i ∈ [K], but F (k) = 0 for all other k ∈ Z n 2 . Construct disjoint sets I c ⊂ [n] for c = 1, . . . , C, and the corresponding matrix H c according to Definition C.2. Let A c (j) correspond to the aliasing sets after sampling with respect to matrix H c . Now define:EQUATIONThen if b = O(log(K)), K = O(2 n/C ), in the limit as n → ∞ with C = O(1), j c i are mutually independent and uniformly distributed over Z b 2 .The proof is given in Appendix C.6.1, and follows directly from the form of the aliasing sets A c (j).Corollary C.3 means that using H as constructed in Definition C.2 ensures that we all 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 a uniform distribution in this case, we need to exploit a group testing matrix.Lemma C.4. (low degree interactions) Let k 1 , . . . , k K be sampled uniformly at random from {k :|k| ≤ t, k ∈ Z n 2 }, where F (k i ) ̸ = 0, ∀i ∈ [K], but F (k) = 0 for all other k ∈ Z n 2 .By constructing C matrices H c , c = 1, . . . , C from rows of a near constant column weight group testing matrix, and sampling as in (23) , if t = Θ(n α ) for α < 0.409, and b = O(log(K)), K = O(n t ), in the limit as n → ∞, j c i as defined in (27) are mutually independent and uniformly distributed over Z b 2 .The proof is given in Appendix C.6.2. It relies on an information theoretic argument, exploiting a result from optimal group testing [53] .Proof. Taking the Mobius transform of u gives us:U (k) = ℓ≤k (-1) 1 T (k-ℓ) u(ℓ) = ℓ≤k (-1) 1 T (k-ℓ) f i:ℓi=0 h i = ℓ≤k (-1) 1 T (k-ℓ) r≤ i:ℓ i =0 hi F (r) = ℓ∈Z b 2 (-1) 1 T (k-ℓ) 1{ℓ ≤ k} r∈Z n 2 F (r)1 r ≤ i:ℓi=0 h i = r∈Z n 2 F (r)   ℓ∈Z b 2 (-1) 1 T (k-ℓ) 1{ℓ ≤ k}1 r ≤ i:ℓi=0 h i   = r∈Z n 2 F (r)I(r)Now let's just focus on the term in the parenthesis for now, which we have called I(r).Case 1: Hr = kEQUATIONFirst note that under this condition, ℓ = k =⇒ r ≤ i:ℓi=0 h i . To see this, note that k j = 0 =⇒ r ≤ h j . Since this holds for all j such that k j = 0, we have the previously mentioned implication.Conversely, if ℓ j < k j (this means ℓ j = 0 AND k j = 1) for some j, then r and h j must overlap. Thus,1 r ≤ h j = 0 =⇒ 1 r ≤ i:ℓi=0 h i = 0We can split I(r) into two parts, the part where ℓ = k and the part where ℓ < k:EQUATIONCase 2: Hr ̸ = k Let Hr = k ′ ̸ = k. This case itself will be broken into two parts. First let's say there is some j such that k j = 0 and k ′ j = 1. Since k ′ j = 1 we know that 1 r ≤ h j = 0. Furthermore, since ∀ℓ ∈ {ℓ : ℓ ≤ k} we have ℓ j = 0. Then by a similar argument to our previous one, we have 1 r ≤ i:ℓi=0 h i = 0 ∀ℓ ≤ k. It follows immediately that I(r) = 0 in this case.Finally, we have the case where k ′ < k. First, if there is a coordinate j such that 0 = ℓ j < k ′ j = 1, we know that 1 r ≤ h j = 0 so we have 1 r ≤ i:ℓi=0 h i = 0 ∀ℓ s.t. ∃j, ℓ j < k ′ j . The only ℓ that remain are those such that k ′ ≤ ℓ ≤ k. It is easy to see that this is a sufficient condition for 1 r ≤ i:ℓi=0 h i = 1.EQUATION)Where the final sum is zero because exactly half of the ℓ have even and odd parity respectively.Thus, the subsampling pattern becomes:U (k) = Hr=k F (r).C.4 Proof of Section 4 Proof. The first step for proving both Theorem 5.1 and Theorem 5.2 is to show that Algorithm 1 can successfully recover all Mobius coefficients with probability 1 -O(1/K) under the assumption that we have access to a Detect (U c (j)) function that can output the type Type (U c (j)) for any aliasing set U c (j). Under this assumption, we use density evolution proof techniques to obtain Theorem C.5 and conclude both theorems.U (k) = ℓ≤k (-1) 1 T (k-ℓ) u(ℓ) = ℓ≤k (-1) 1 T (k-ℓ) f i:ℓi=0 h i ⊙ d = ℓ≤k (-1) 1 T (k-ℓ) r≤ i:ℓ i =0 hi F (r)1 r ≤ d = ℓ∈Z b 2 (-1) 1 T (k-ℓ) 1{ℓ ≤ k} r∈Z n 2 F (r)1 r ≤ i:ℓi=0 h i 1 r ≤ d = r∈Z n 2 F (r)1 r ≤ d   ℓ∈Z b 2 (-1) 1 T (k-ℓ) 1{ℓ ≤ k}1 r ≤ i:ℓi=0 h i   = r∈Z n 2 F (r)1 r ≤ d I(r)Then, to remove this assumption, we need to show that we can process each aliasing set U c (j)correctly, meaning that each bin is correctly identified as a zeroton, singleton, or multiton. Define E as the error event where the detector makes a mistake in O(K) peeling iterations. If the error probability satisfies Pr(E) ≤ O(1/K), the probability of failure of the algorithm satisfiesP F = Pr F ̸ = F |E c Pr(E c ) + Pr F ̸ = F |E Pr(E) ≤ Pr F ̸ = F |E c + Pr(E) = O(1/K).In the following, we describe how we achieve Pr(E) ≤ O(1/K) under different scenarios.In the case of uniformly distributed interactions without noise, singleton identification and detection can be performed without error as described in Section C.7.1. In the case of interactions with low degree and without noise, singleton identification and detection can be performed with vanishing error as 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.The density evolution proof is generally separated into two parts.• We show that with high probability, nearly all of the variable nodes will be 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 be 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 asG D, {M c } c∈[C] .D is the support distribution. The set of non-zero Mobius coefficients {r : M[f ](r) ̸ = 0} ∼ D is drawn from this distribution. In [13] , using the arguments above it is shown that if the following conditions hold, the peeling message passing successfully resolves all variable nodes:1. In the limit as n → ∞ asymptotic check-node degree distribution from an edge perspective converges to that of independent an identically distributed Poisson distribution (shifted by 1).2. The variable nodes have a constant degree C ≥ 3 (This is needed for the expander property).3. The number of check nodes b in each of the C sampling group is such that 2 b = O(K).Theorem C.5 ([13] ). If the above three conditions hold, the peeling decoder recovers all Mobius coefficients with probability 1 -O(1/K).In the following section, we show that for suitable choice of sampling matrix, these conditions are satisfied, both in the case of uniformly distributed and low degree Mobius coefficients.In order to satisfy the conditions for the case of a uniform distribution of we use the matrix in Corollary C.3. We select C = 3 different I 1 , I 2 , I 3 such that I i ∩ I j = ∅ ∀i ̸ = j ∈ {1, 2, 3}. Note that this satisfies condition (2) above. Furthermore, we let k scale as O(2 nδ ). In order to satisfy condition (3), we must have δ < 1 3 , since each I i can consist of at most 1 3 of all the coordinates. We now introduce some notation. Let g j (•) represent the hash function, that maps a frequency r to a check node index k in each subsampling group j = 1, . . . , C, i.e., g j (r) = H j r. Per our assumption, we have K non-zero variable notes r (1) , . . . , r (K) chosen uniformly at random. Technically, we are sampling without replacement, however, since K 2 n → 0, the probability of selecting a previously selected r (i) vanishes. Going forward in this subsection, we will assume that each r i 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.First, let's consider the marginal distribution of g j (r (i) ) for some arbitrary j ∈ [C] and i ∈ [K]. Assuming sampling with replacement, we have:EQUATIONThus, we have established that the our approach induces a uniform marginal distribution over the 2 b check nodes. Next, we consider the independence of our bins. By assuming sampling with replacement, we can immediately factor our probability mass function.EQUATIONFurthermore, since we carefully chose the I i such that they are pairwise disjoint, we haveEQUATION)establishing independence. Let's define an inverse load factor η = 2 b K . From a edge perspective, sampling with replacement with independent uniformly distributed gives us:EQUATIONFor fixed η, asymptotically as K → ∞ this converges to:EQUATIONFor this proof, we take an entirely different approach to the uniform case. We instead exploit the results of Theorem F.1, which is about asymptotically exactly optimal group testing, and then make an information-theoretic argument. Let X n be a 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 n on t, since by invoking Theorem F.1, we assume some implicit relationship where t = Θ(n θ ) for θ satisfying the theorem conditions. Now consider some r n chosen uniformly at random from the n t weight t binary vectors. Note that in this work we actually use what is known as the "i.i.d prior" as 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:EQUATIONFurthermore, we define the decoding function Dec n (•), which represents the deterministic procedure that successfully recovers r with vanishing error probability. We have the following bounds on the entropy of Y n :EQUATIONwhere we have used the fact that binary random variables have a maximum entropy of 1. Furthermore, by the properties of entropy we also haveH(Y n ) ≥ H(Dec(Y n , X n ) | X n ).Dividing through by T , we have:EQUATION) Let Dec n (Y n , X n )) = r n + err n (Y n , X n ).It is known (see [15] ) that Pr(err n (Y n , X n ) ̸ = 0) = O(poly(T )e -T ). Thus, we can bound the left-hand side as:EQUATIONEQUATIONWhere in (45) we have used the bound H(A + B) ≥ H(A) -H(B) and the fact that X n and r n are independent, and in (46) we have used the fact that conditioning only decreases entropy. By the continuity of entropy and Theorem F.1, we have that:EQUATIONThis establishes that:EQUATIONUnfortunately, 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 o(T (n))). Let G ⊂ N correspond to the set containing all the indicies i of the summands that are equal to 1. By using the fact that conditioning only reduces entropy, we haveEQUATIONNow we define the countable sequence of random variables:EQUATIONBy continuity of entropy, and the above limit and definition, we have:EQUATIONNoting that conditioning only decreases entropy, we immediately have that Ȳi ∼ Bern( 12 ). Now consider some arbitrary finite set S * ⊂ G. We will now prove that { Ȳi , i ∈ S * } is mutually independent.Proof. Let i 1 < i 2 < . . . < i |S * | be an ordered indexing of the elements of S * . Furthermore, let Q j = {i q | 1 ≤ q ≤ j}. Assume the set { Ȳi , i ∈ Q j } is mutually independent, and use the notation Y Qj to represent a vector containing all of these entries. We have:EQUATION) However, by using the fact that conditioning only decreases entropy we have:EQUATIONEQUATIONThis leads to the following chain of implications:H(Y ij+1 , Y Qj ) = H(Y Qj ) + H(Y ij+1 ) ⇐⇒ Y ij+1 ⊥ ⊥ Y Qj .(55) From this, and the initial inductive assumption, we can conclude that { Ȳi , i ∈ Q j+1 } is mutually independent. The base case of j = 1 follows from the fact that a set containing just one single random variable is mutually independent. SinceQ |S * | = S * the proof is complete. Now let L(n) = |G ∩ [n]| we know L = Θ(T (n)), which follows from the stronger result that lim n→∞ L(n) T (n) = 1. Take b ≤ L(n)C By leveraging the above results, we can select our subsampling matricesEQUATIONEQUATIONEQUATION) Due to the independence result proved above, the asymptotic degree distribution is:EQUATION)∃p * > 1 s.t. only *one* of k 1 or k 2 ≤ dp * . Without loss of generality we will assume k 2 ≤ dp * and k 1 ≰ dp * . Now, define the following sets:J 0 = N ∩ {k : H c k = j} (64) J p * = N ∩ {k : H c k = j k ≤ dp * } (65) We know k 2 ∈ J p * and k 1 ∈ J 0 \ J p * , thus |J p * | ≥ 1 and |J 0 \ J p * | ≥ 1.With this, we can show that the implication above cannot be satisfied.EQUATIONSince J * p is not empty, from our distributional assumption, the above sum cannot be 0.EQUATIONSince J 0 \ J * p is not empty, from our distributional assumption, the above sum cannot be 0. This implies that Type(U c (j)) = H M must be false, thus proving (2).Proof of (3): Since we have a converse for (1), a converse for (2) suffices to prove (3). The converse follows below:EQUATIONSince F (k * ) ̸ = 0, we have U c,0 (j) ̸ = 0 and all entries of U c (j) are either F (k * ) or 0. Thus, Detect(U c (j)) = H S .Here we include a sketch of the argument for the noiseless part of Theorem 2, which focuses on the case |k| ≤ t (the rest of Theorem 2 is unchanged).(1) Prove Detect(U c (j)) = H Z =⇒ Type(U c (j)) = H Z . (2+3) Prove Pr (Detect(U c (j)) = Type(U c (j))) → 1.Proof of (1) The proof is identical to above.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 * ) ≤ n -β , we correctly recover each k * in the limit, meaning we must have Pr(D c k 1 ̸ = D c k 2 ) → 1 (this is equivalent to the existence of p * ). Thus, by the same argument this implies that Detect (U c (j)) has vanishing error in the limit. The complete argument requires us to union bound over all of the singleton identifications success, but since T is linear in β, so long as K = poly(n), constant β suffices for vanishing error.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 ∈ Z P1×n. 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 a Bern ν t for some ν = Θ(1). We denote the i th row of D as d i . Each group test is derived from one of the delayed samples. Under the i.i.d. spectral noise model, this means each sample has the form:EQUATIONwhere Z i (k) ∼ N 0, σ 2 . Essentially, we can view this as a hypothesis testing problem, where we have one sample X, and hypothesis and the alternative are:H 0 : X = Z H 1 : X = F (r * ) + Z, Z ∼ N (0, σ 2 )Furthermore, lets say the magnitude of |F [k]| = ρ is known. We construct a threshold test:EQUATIONWith such a test, we can compute the cross-over probabilities:EQUATIONEQUATIONFor the sake of simplicity, we will make the choice to choose γ such that p 10 = p 01 . In that case, we can numerically solve for the cross-over probability which is fixed for a given signal-to-noise ratio. [54] , to prove our desired result. let q be the resulting cross-over probability for a given ρ/σ. The probability that all of our Singleton identifications succeed can computed by a union bound on P e = Pr k ̸ = k ≤ n -β . If K = poly(n), a constant β suffices us to drive the union bound to zero. Lemma C.8. For any fixed SNR, taking D c such that each element is Bern ν t , and t = Θ(n α ) for α ∈ (0, 1), taking P 1 = O(t log(n)) suffices to ensure that we can achieve error of bin identification failure with probability of error O(1/K 3 ).We note that the general flow of this proof follows [40] , but there are several fundamental differences that make this proof overall quite different. We define E b as the error event where a bin k is decoded wrongly, and then using a union bound over different bins and different iterations, the probability of the algorithm making a mistake in bin identification satisfiesPr(E) ≤ (# of iterations) × (# of bins) × Pr(E b )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 at each iteration in the worst case). Hence, Pr(E) ≤ ηCK 2 Pr(E b ). In order to satisfy Pr(E) ≤ O(1/K), we need to show that Pr(E b ) ≤ O(1/K 3 ).We already showed in Lemma C.8 that we can achieve singleton identification under noise with vanishing error O(1/K 3 ) with a delay matrix D ∈ Z P1×n 2 .To achieve type detection, we construct another pair of delay matrices D 1 ∈ Z P2×n We will choose D 1 and D 2 such that each element is drawn i.i.d. as a Bern (1/2) 1/t . We denote the i th row of D 1 as d 1 i and denote the i th row of D 2 as d 2 i . Then, with these delay matrices, we can obtain observations of the formU 1 i (k) = Hr=k r≤d 1 i F (r) + Z i (k) U 2 i (k) = Hr=k r≤d 2 i F (r) + Z i (k).Note that we can represent these observations asU 1 = S 1 α + W 1 U 2 = S 2 α + W 2with W 1 , W 2 ∼ N (0, σ 2 I), a α vector with entries F (r) for coefficients in the set and binary signature matrices S 1 , S 2 with entries indicating the subsets of coefficients included in each sum.Then, we subtract these observations to obtain a single observation U = U 1 -U 2 which can be written asU = Sα + Wwith W ∼ N (0, 2σ 2 I) and S = S 1 -S 2 . This construction allows us to show that the columns of S are sufficiently incoherent and hence we can correctly perform identification.Lemma C.9. For any fixed SNR, taking D 1 c and D 2 c such that each element is Bern (1/2) 1/t , and t = Θ(n α ) for α ∈ (0, 1/2) and taking P 2 = O(t log(n)) suffices to ensure that the probability Pr(E b ) for an arbitrary bin can be upper bounded as Pr(E b ) ≤ O(1/K 3 ).Proof. In the following, we prove that Pr(E b ) ≤ O(1/K 3 ) holds using the observation model. We consider separate cases where the bin in consideration is fixed as a zeroton, singleton, or multiton.The error probability Pr(E b ) for an arbitrary bin can be upper bounded asPr(E b ) ≤ F ∈{H Z ,H M } Pr(F ← H S (r, F (r))) + F ∈{H Z ,H M } Pr(H S ( r, F (r)) ← F) +Pr(H S ( r, F (r)) ← H S (r, F (r)))above, each of these events should be read as:1. {F ← H S (r, F (r))}: missed verification in which the singleton verification fails when the ground truth is in fact a singleton.2. {H S ( r, F (r)) ← F}: false verification in which the singleton verification is passed when the ground truth is not a singleton.3. {H S ( r, F (r)) ← H S (r, F (r))}: crossed verification in which a singleton with a wrong index-value pair passes the singleton verification when the ground truth is another singleton pair.We can upper-bound each of these error terms using Propositions C.10, C.11, and C.12. Note that all upper-bound terms decay exponentially with P 2 except for the term Pr( r ̸ = r) ≤ O(1/K 3 ).We use Theorem F.3 to show that we can achieve Pr( r ̸ = r) ≤ O(1/K 3 ) if we choose P 1 = O(t log n). Since all other error probabilities decay exponentially with P 2 , it is clear that if P 2 is chosen as P 2 = O(t log n), the error probability can be bounded as Pr(E b ) ≤ O(1/K 3 ).Proposition C.10 (False Verification Rate). For 0 < γ < η 4 SNR, the false verification rate for each bin hypothesis satisfies:Pr(H S ( r, F ( r)) ← H Z ) ≤ e -P 2 2 ( √ 1+2γ-1) 2 , Pr(H S ( r, F ( r)) ← H M ) ≤ e -P 2 γ 2 4(1+4γ) + K 2 e -ϵ 1-4γν 2 ρ 2 2 P2, where P 2 is the number of the random offsets.Proof. The probability of detecting a zeroton as a singleton can be upper-bounded by the probability of a zeroton failing the zeroton verification. This meansPr(H S ( r, F ( r)) ← H Z ) ≤ Pr 1 P 2 ∥W∥ 2 ≥ (1 + γ)ν 2 ≤ e -P 2 4 ( √ 1+2γ-1) 2 ,by noting that W ∼ N (0, ν 2 I) and applying Lemma C.13.On the other hand, given some multiton observation U = Sα + W, the probability of detecting it as a singleton with index-value pair ( r, F ( r)) can be written asPr(H S ( r, F ( r)) ← H M ) = Pr 1 P 2 U -F ( r)s r 2 ≤ (1 + γ)ν 2 = Pr 1 P 2 ∥g + v∥ 2 ≤ (1 + γ)ν 2 ,where g := S(α -F ( r)e r ) and v := W. Then, we can upper bound this probability asPr 1 P 2 ∥g + v∥ 2 ≤ (1 + γ)ν 2 ∥g∥ 2 P 2 ≥ 2γν 2 + Pr ∥g∥ 2 P 2 ≤ 2γν 2 .To upper bound the first term, we use Lemma C.13. Note that the first term is conditioned on the event ∥g∥ 2 /P 2 ≥ 2γν 2 , thus the normalized non-centrality parameter satisfies θ 0 ≥ 2γ. As a result, we can use Lemma C.13 by letting τ 2 = (1 + γ)ν 2 . Then, the first term is upper bounded by exp{-(P 2 γ 2 )/(4(1 + 4γ))}. To analyze the second term, we let β = α -F ( r)e r and write g = Sβ. Denoting its support as L := supp(β), we can further write Sβ = S L β L where S L is the sub-matrix of S consisting of the columns in L and β L is the sub-vector consisting of the elements in L. Then, we consider two scenarios:• The multiton size is a constant, i.e., |L| = L = O(1). In this case, we haveλ min (S ⊤ L S L )∥β L ∥ 2 ≤ ∥S L β L ∥ 2 Using ∥β L ∥ 2 ≥ Lρ 2 ,the probability can be bounded asPr ∥g∥ 2 P 2 ≤ 2γν 2 ≤ Pr λ min 1 P 2 S ⊤ L S L ≤ 2γν 2 Lρ 2On the other hand, using Lemma C.14 with the selection β = 1/2 and η = . which holds as long as γ < Lρ 2 /(4ν 2 ) = Lη 4 SNR. • The multiton size grows asymptotically with respect to K, i.e., |L| = L = ω(1). As a result, the vector of random variables g = S L β L becomes asymptotically Gaussian due to the central limit theorem with zero mean and a covarianceE[gg H ] = 1 2 Lρ 2 IProof. For any r sampled uniformly from vectors up to degree t, the probability that it will have degree 0 ≤ k ≤ t can be written asPr (|r| = k) = n k t k=1 n kWe know that the entries of s r are given as (s 1 r ) i = 1 r ≤ d1 i and (s 2r ) i = 1 r ≤ d2 i . Therefore, Pr (s 1 r ) i = 1 = Pr d 1 ij = 0, ∀j ∈ supp(r) = t k=1 Pr d 1 ij = 0, ∀j ∈ supp(r)||r| = k Pr (|r| = k) = t k=1 n k β k/t t k=1 n k . =: g(t, n)With β = Θ(1) and t = Θ(n α ) for α ∈ (0, 1/2), we can show that lim n→∞ g(t, n) = β. Therefore, there exists some n 0 such that | Pr (s 1 r ) i = 1 -β| ≤ η for all n ≥ n 0 . For the rest of the proof, let g = Pr (s 1 r ) i = 1 and assume |g -β| ≤ η. Then, recalling (s r ) i = (s 1 r ) i -(s 2 r ) i , the distribution for each entry of s r can be written as Pr ((s r ) i = 1) = Pr ((s r ) i = -1) = g(1g).Hence, using Hoeffding's inequality, we obtainPr 1 P 2 s ⊤ r s r ≤ 2β(1 -β) -η ≤ Pr 1 P 2 s ⊤ r s r ≤ 2g(1 -g) -η ≤ exp - η 2 2 P 2 .Furthermore, the conditional probability of another vector m ̸ = r being included in test i is given byPr (s 1 m ) i = 1|(s 1 r ) i = 1, |r| = k = Pr (d ij = 0, ∀j ∈ supp(m) \ supp(r)||r| = k) = t ℓ=0 β 1/t ℓ 1 - k n ℓ k n t-ℓ = k n + 1 - k n β 1/t t =: f (t, n, k).With β = Θ(1) and t = Θ(n α ) for α ∈ (0, 1), for any k ≤ t, we can show that lim n→∞ f (t, n, k) = β. Therefore, there exists some n 0 such that | Pr (s 1 m ) i = 1|(s 1 r ) i = 1 -β| ≤ η for all n ≥ n 0 . For the rest of the proof, let f = Pr (s 1 m ) i = 1|(s 1 r ) i = 1 and assume |f -β| ≤ η. On the other hand,Pr ((s m ) i (s r ) i = 1) = 2f g [1 -g -(1 -f )g] Pr ((s m ) i (s r ) i = -1) = 2 [(1 -f )g] 2As a result, we haveE[(s m ) i (s r ) i ] = 2g(f -g).Since lim n→∞ E[(s m ) i (s r ) i ] = 0, there exists some n 0 such that -η ≤ E[(s m ) i (s r ) i ] ≤ η for all n ≥ n 0 . For the rest of the proof assume -η ≤ E[(s m ) i (s r ) i ] ≤ η. As a result, we can writePr 1 P 2 |s ⊤ r s m | ≥ 2η ≤ Pr |s ⊤ r s m -P 2 E[(s m ) i (s r ) i ]| ≥ P 2 η ≤ exp - η 2 2 P 2 .By Gershgorin Circle Theorem, the minimum eigenvalue of 1 P2 S ⊤ L S L is lower bounded asλ min 1 P 2 S ⊤ L S L ≥ 1 P 2 min r∈L   |s ⊤ r s r | - m∈L m̸ =r |s ⊤ r s m |    .Lastly, we apply a union bound over all (r, m) pairs to obtainPr λ min 1 P 2 S ⊤ L S L ≤ 2β(1 -β) -(2L + 1)η ≤ 2L 2 exp - η 2 2 P 2 .In this section, we discuss the computational complexity of Algorithm 1, which is broken down into the following parts:Computing Samples Computing samples for one sapling matrix requires computing the row-span of H c , which can be computed in n2 b operations. Then for each sample, we must take the bit-wise and with each row of the delay matrix, so the total complexity is: Cn2 b P .Taking Small Mobius Transform Computing the Mobius transform for each of the CP subsampled functions is CP b2 b .Singleton Detection To detect each singleton requires computing y. This requires P divisions for each of the C2 b bins, for a total of CP 2 b operations.Singleton Identification To identify each singleton requires different complexity for our 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 y is poly(n), so for each singleton the complexity is CK poly(n)Message Passing In the worst case, we peel exactly one singleton per iteration, resulting in CK subtractions (the above singleton identification bounds already take into account the need to 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(CP n2 b + CP b2 b + CK) = O(CP nK) = O(n 2 K). Low degree (noisy) time complexity = O(CP n2 b + CP b2 b + CK poly(n)) = O(CP poly(n)K) = O(poly(n)K).In this section, we present some additional simulations that did not fit in the body of the manuscript. Fig 15 and 16 . Plot the runtime of SMT vs. n under both of our assumptions. In both cases we observe excellent scaling with n. We note that our low degree setting has a higher fixed cost since we 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 a phase transition, however, the phase threshold appears very insensitive to n, as expected, since our sample complexity requirement is growing like log(n), and we are already plotting on a log scale. We observe that the number of samples required to achieve perfect reconstruction is scaling linearly is very insensitive to n as predicted. We also include N = 2 n on the bottom axis, which is the total number of interactions. In this regime we do not appear to consistently maintain zero 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 ≤ 1000.F.1 Group Testing Achievability Results From Literature Theorem F.1 (Part of Theorem 4.1 and 4.2 in [15] ). Asymptotic Rate 1 Noiseless Group Testing: Consider a noiseless group testing problem with t = Θ(n θ ) defects out of n elements. We define the rate of a group testing procedure as:EQUATION)where T is the number of tests performed by the group testing procedure. For an i.i.d. Bernoulli design matrix, for θ ∈ [0, 1/3], in the limit as n → ∞, a rate R * BERN = 1 is achievable with vanishing error. Furthermore, for the constant column-weight design matrix, for θ ∈ [0, 0.409] a rate R * CCW = 1 is achievable with vanishing error. Theorem F.2 ( [42, 54] ). Noiseless Group Testing: Consider the noiseless non-adaptive group testing setup with t = |k| defects out of n items, with t scaling arbitrarily in n. Let k be the output of a group testing decoder and let T * = Θ (min {t log(n), n}). Then there exists a strategy using T ≤ (1 + ϵ)T * such that in the limit as n → ∞ we have:EQUATIONFurthermore, there is a poly(n) algorithm for computing k. From [54] , for t = o(n) we can achieve:EQUATION)with number of tests T = O((1 + δ)t log(n)).Note that the above error rate is not a state-of-art result, but suffices in this case for our proof, and is very convenient in its form.Theorem F. 3 ([43] ). Noisy Group Testing Under General Binary Noise: Consider the general binary noisy group testing setup with crossover probabilities p 10 and p 01 . We use i.i.d Bernoulli testing with parameter ν > 0. There are a total of |k| = t = Θ(n θ ) defects, where θ ∈ (0, 1). LetEQUATION, where we haveEQUATIONEQUATIONEQUATIONEQUATIONwhere D(x) = x log(x)x + 1, and w = (1p 01 )e -ν + p 10 (1e -ν ). For any α ∈ (p 10 , 1p 01 ), β ∈ (p 01 , 1p 10 ), there exist some number of tests T < (1 + ϵ)T * where the Noisy DD algorithm produces k such that in the limit as n → ∞ we have:EQUATIONThe above result is 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 a similar more compact result that suffices for our proofs in this paper.). Let |k| = t = o(n), and consider an i.i.d. 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:EQUATIONwith number of testsEQUATION)where γ is a constant that depends on β.We implement group testing via linear programming. As noted in [15] , linear programming generally outperforms most other group testing algorithms in both the noisy and noiseless case. We use the following linear program, to implement group testing.EQUATIONRigorous tools for understanding models can potentially profoundly increase trust in deep learning systems. If we can understand and reason for ourselves why a model is making a decision, we can put greater trust into those decisions. Furthermore, if we understand why a model is doing something that we believe is incorrect, we can better steer it towards doing what we believe is correct. This "steering" of model behavior is sometimes described as alignment, and is a critical task for addressing things like incorrect or misleading information generated by a model, or for address any undesirable biases. In terms of concerns, it is important to not misinterpret or over-interpret the interaction indices that come out of SMT. It could be the case that looking over some selection of interactions doesn't reveal the full picture, and leads one down an incorrect line of reasoning.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: There is a limitations section, and limitations are mentioned periodically when relevant.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 a separate "Limitations" section in their paper.• The paper should point out 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 a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text 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, a 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.https://github.com/basics-lab/sparseMobiusTransform 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

However, 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.**

1. 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.

 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*.

**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)$. 
The 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:

|              | p=0    | p=1    | p=2    | p=3    | p=4    | p=5    | p=6    |
| ------------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
| $d_{c,p}$            | 000000 | 100000 | 010000 | 001000 | 000100 | 000010 | 000001 |
| $U_{c,p}(11)$ | 1/3    | 0      | 0      | 1/3    | 1/3    | 1/3    | 1/3    |

**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.

I 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.

---

2. 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.

---

3. 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.


[cite1] John C. Harsanyi. A simplified bargaining model for the n-person cooperative game. International Economic Review, 4(2):194–220, 1963.

[cite2] Ren et al. Defining and Quantifying the Emergence of Sparse Concepts in DNNs. CVPR, 2023.

[cite3] Li and Zhang. Does a Neural Network Really Encode Symbolic Concepts? ICML, 2023.

[cite4] Ren et al. Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs. ICLR, 2024.
questions: questions: See weaknesses above

---

After 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: **Major comments**
- 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. 
- 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? 

**Minor comments**
- It'd be better to clarify several notations, such as $|\mathbf{k}|$ and $[K]$.
- 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). 
- In the main text, $C$, the number of samplings (?), appears a bit out of sudden at line 193.
questions: questions: I'd like the Authors to answer the weaknesses raised above. Plus, 
- 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: Limitations are adequately presented. For the potential improvements, see Weakness and Questions.
paper_summary: paper_summary: The paper present a way to compute high-order interactions using Mobius transformation.
strength_weakness: strength_weakness: 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

2. 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.

3. 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?

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.

Minor: 
Some 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.
questions: 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: limitations: The assumption of having only K non-zero interactions, while in practice K is typically large for explainability.

Comments: title: raise score
Response to rebuttal
Proof Revision (Proof, Theorem 2)
Proof Revision (Proof, Theorem 1)
Proof Revision (Assumption)
comment: Dear Reviewer, 

Thank you for your reply. We wanted to ask: 
*What are the issues that still keep this paper from being a clear accept*?

It would be great if we could resolve these issues and have a unanimous opinion on this paper. 

**Regarding Point 4**:

Thank you for your clarification. As we now understand it , we believe we have a solution to this. In fact, this solution is *already present* in the paper from line 516-521. The core idea is that we include a post-processing step that takes the $K$ coefficients, and further sparsifies them to our desired level. This is what we have done in Fig. 6 to produce the results for SMT. Thus you can extract a much smaller number $k << K$ coefficients using the following idea in practice:

1. Choose $b$ (which serves as a proxy for $K$) and run the full SMT algorithm to get $\hat{F}$. $b$ should be set such as the computational budget allows.

2. Apply regression and LASSO steps to further process the transform $\hat{F}$ to reduce the number of coefficients.

Empirically, we observe that as we increase the amount of regularization in the LASSO, some of the coefficients get set to zero, and their mass is moved to other coefficients. *If this is the main issue you still have, we could include this idea and discussion more prominently in the manuscript*. For your convenience, we have included the relevant appendix excerpt below

---
We run SMT to obtain a sparse Möbius representation $\hat{F}$ with support $\mathrm{supp}(\hat{F})$. Then, we fine-tune the values of the coefficients by solving the following regression problem over a uniformly sampled set of points $\mathcal{D} \subseteq \mathbb{Z}\_2^n$:

\begin{align*}
    & \min\_{\hat{f}, \boldsymbol{\alpha}} \;  \sum\_{\mathbf{m} \in \mathcal{D}} (\hat{f}(\mathbf{m}) - f(\mathbf{m}))^2 \\\\
& \\;\\; \text{s.t.} \quad \hat{f}(\mathbf{m}) = \sum\_{\mathbf{k} \leq \mathbf{m}, \mathbf{k} \in \mathrm{supp}(\hat{F})} \alpha_{\mathbf{k}}, \forall \mathbf{m}.
\end{align*}

To measure the faithfulness captured by sparse approximations, we modify the regression problem by adding an $\ell_1$ penalty on the values of the Möbius coefficients. Then, we vary the penalty coefficient $\lambda$ to obtain different levels of sparsity:
\begin{align*}
    & \min\_{\hat{f}, \boldsymbol{\alpha}} \;  \sum\_{\mathbf{m} \in \mathcal{D}} (\hat{f}(\mathbf{m}) - f(\mathbf{m}))^2 + \lambda \sum\_{\mathbf{k} \in \mathrm{supp}(\hat{F})} |\alpha_{\mathbf{k}}|\\\\
& \\;\\; \text{s.t.} \quad \hat{f}(\mathbf{m}) = \sum_{\mathbf{k} \leq \mathbf{m}, \mathbf{k} \in \mathrm{supp}(\hat{F})} \alpha_{\mathbf{k}}, \forall \mathbf{m}.
\end{align*}
Thank you for your prompt response. Our discussions with reviewer jcxh are now concluded. If you have any further comments please let us know. 

Regarding your comments about comparison, we will keep this in mind as we prepare the final manuscript if this paper is accepted.
Thank you for your diligence as a reviewer, we will be certain to correctly state the theorems with this additional assumption, and include this revised proof in the appendix.
I appreciate the responses of the authors to all reviewers and adjust my score accordingly.

Just to elaborate more on point 4; the proposed method finds all K significant interactions, which is very interesting since the search space for finding such interactions is exponential. However, the limitation of the method is when K is large (which is typical of the way we define explanation games in explainability), and many of them are not probably of use since we mainly seek the most significant interactions for explanations (e.g., k most significant interactions where k <<<< K).
Thank you for your response. The added assumption and proof address my concern for the singleton detection algorithm. I hope this assumption and proof, as well as the mentioned literature review for the sparsity of Mobius transform, will be properly stated in the final version of the paper if the paper is accepted. Furthermore, I have raised my score accordingly.
Thank you for the clarification. The authors addressed my concerns properly. About 2), while Figure 5 compares second-order methods, it does not show how faithfulness increases with the increase of computational budgets. Practically, we may be interested in the cost of reasonable reconstruction (e.g., 90%). I believe this kind of analysis and second-order version of Fig.6 (with a small dataset) will improve the completeness of this work (just a comment, not asking for an immediate response). 

Overall, I'll maintain my score for now. There seems to be a correction/improvement in the proofs pointed out by Reviewer jcxh, so my final score can be affected by the consequences of the discussion between the Authors and Reviewer jcxh.
Here we include a sketch of the argument for the noiseless part of Theorem 2, which focuses on the case $\left\lvert \mathbf{k}\right\rvert \leq t$ (the rest of Theorem 2 is unchanged).

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

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

**Proof of (1)**

The proof is identical to above.

**Proof of (2+3)** 

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

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

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

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

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

**Proof of (1)**

Let $\mathrm{Detect}(\mathbf{U}\_c(\mathbf{j})) = \mathcal{H}\_Z$, and for contradiction's sake assume $\mathrm{Type}(\mathbf{U}\_c(\mathbf{j})) \neq \mathcal{H}\_Z$.
\begin{equation}
        \mathrm{Detect}(\mathbf{U}\_c(\mathbf{j}))  = \mathcal{H}\_Z \implies \sum_{\mathbf{k} \leq \bar{\mathbf{d}}\_p\; \text{ s.t. } \mathbf{H}\_c \mathbf{k} = \mathbf{j}} F(\mathbf{k}) = 0 \;\forall p,
\end{equation}
Since $\mathrm{Type}(\mathbf{U}_c(\mathbf{j})) \neq \mathcal{H}_Z$, we have that $\mathcal{N} \cap \\{ \mathbf{k} : \mathbf{H}_c \mathbf{k} = \mathbf{j}\\} \neq \emptyset$.
Thus, if we consider  the above implication for the case of $p=0$ and noting that $\mathbf{d}_0 = \boldsymbol{0}$, we have:
\begin{equation}
    \mathrm{Detect}(\mathbf{U}\_c(\mathbf{j}))  = \mathcal{H}\_Z \implies \sum\_{\mathcal{N} \cap \\{ \mathbf{k} : \mathbf{H}\_c \mathbf{k} = \mathbf{j}\\}} F(\mathbf{k}) = 0
\end{equation}
But considering the no cancellation condition, this is impossible, thus proving (1).

**Proof of (2)**

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

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

\begin{equation}
    U_{c,p^*}(\mathbf{j}) = 0 \implies \sum_{\mathbf{k} \in \mathcal{J}_p^*} F(\mathbf{k}) = 0.
\end{equation}
Since $\mathcal{J}_p^*$ is not empty, from our distributional assumption, the above sum cannot be $0$.

*Case 2:* $U_{c,p^*} = U_{c,0}(\mathbf{j})$.
\begin{equation}
        U_{c,0}(\mathbf{j}) - U_{c,p^*}(\mathbf{j}) = 0 \implies \sum_{\mathbf{k} \in \mathcal{J}_0 \setminus \mathcal{J}_p^*} F(\mathbf{k}) = 0.
\end{equation}
Since $\mathcal{J}_0 \setminus \mathcal{J}_p^*$ is not empty, from our distributional assumption, the above sum cannot be $0$. This implies that $\mathrm{Type}(\mathbf{U}_c(\mathbf{j})) = \mathcal{H}_M$ must be false, thus proving (2).

**Proof of (3):**

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

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


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

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

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


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

**Proof.**

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

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

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

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