SHAP values via sparse Fourier representation
Authors: Ali Gorji
Andisheh Amrollahi
Andreas Krause
Venue: NeurIPS 2025 spotlight ()
Keywords: SHAP
Interpretability
XAI
Fourier
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Computing SHAP values for black-boxes and trees using sparse Fourier representation of models, orders of magnitudes faster than other methods

Abstract: SHAP (SHapley Additive exPlanations) values are a widely used method for local feature attribution in interpretable and explainable AI. We propose an efficient two-stage algorithm for computing SHAP values in both black-box setting and tree-based models. Motivated by spectral bias in real-world predictors, we first approximate models using compact Fourier representations, exactly for trees and approximately for black-box models. In the second stage, we introduce a closed-form formula for {\em exactly} computing SHAP values using the Fourier representation, that ``linearizes'' the computation into a simple summation and is amenable to parallelization. As the Fourier approximation is computed only once, our method enables amortized SHAP value computation, achieving significant speedups over existing methods and a tunable trade-off between efficiency and precision.

SHAP values via sparse Fourier representation
Ali Gorji
Andisheh Amrollahi ETH Zürich, Switzerland amr amrollaa@alumn: ethz. ch
Andreas Krause ETH Zürich, Switzerland krauseaßethz.co .ch
ETH Zürich, Switzerland ali gorj @@llumni. ethz.ck
Abstract
SHAP (SHapley Additive exPlanations) values widely used method for local feature attribution in interpretable and explainable AL. We propose an efficient two-stage algorithm for computing SHAP values in both black-box setting and tree-based models. We assume the black-box predictor or tree model accepts binary (zero-one) features. Motivated by spectral bias in real-world predictors, we first approximate the predictor using compact Fourier representations, exactly for trees and approximately for black-box models. In the second stage, we introduce a closed-form formula for exactly computing SHAP values using the Fourier representation, that "linearizes" the computation into simple summation and is amenable to parallelization. As the Fourier approximation is computed only once, our method enables amortized SHAP value computation, achieving significant speedups over existing methods and tunable trade-off between efficiency and precision.
Introduction
Interpretability of machine learning models paramount, especially in high-stakes applications in areas such as medicine, fraud detection, credit scoring. This is crucial to the extent that in Europe, the General Data Protection Regulation (GDPR) mandates the legal right an explanation of algorithmic decisions [Voigt and Von dem Bussche 2017]. Say we are given a predictor/model h: X + which maps an input (data) instance E X to prediction h(2*). Instance-wise a.k.a. local feature attribution methods assign "importances" to each of the features x; E X of the instance x² which quantify how influential that feature was the model predicting the value h(x=)).
A widely used method for deriving attributions (importances) is the notion of SHapley Additive exPlanations, commonly referred to simply as SHAP values. Originally, the notion Shapley values was introduced in the seminal work of Shapley [1952] in the context of cooperative game theory. The Shapley value mathematically well- and "fair" way distributing a reward among all the members of group playing a cooperative game and it is computed based on the rewards that would be received for all possible coalitions. The Shapley value is the unique way of distributing the reward that satisfies several reasonable mathematical properties that capture notion of fairness [Shapley [952]. . In context of machine learning and statistics, the players become features, the reward is the prediction of the predictor / and the SHAP value is the "contribution" or "influence" of that feature on the prediction. Shapley values are widely used due to their mathematical soundness and desirable properties (Gromping [007 Strumbelj et al. 2009)] Owen 20144) Datta al. 2016).
Owen and Prieur 2017), Lundberg and Lee 2017]. Lundberg et al. [2020] Aas et al. [2021]
Despite their prevalence, computing SHAP values is challenging, as involves exponential summation, i.c., a summation over exponentially many terms see Equation []] This is because the formula accounts for feature's 's importance in the context of all possible "coalitions" of other features, and therefore the formula covers all possible subsets of other features. Therefore, approximating them and speeding up the computation has received attention in variety of settings.
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

SHAP value computation can easily dominate the computation time of industry-level machine learning solutions on datasets with millions or more entries Yang 202T Yang [002]] point out that industrial applications sometimes require hundreds of millions of samples to be explained. Examples include feed ranking, ads targeting. and subscription propensity models. In these modeling pipelines, spending tens of hours in model interpretation becomes a significant bottleneck (Yang) 202 and one usually needs to resort to multiple cores and parallel computing.
Significant work has gone into speeding up the computation of SHAP values for a variety of settings. In the (ensemble of) trees setting, full access to the tree structure is assumed. Yang 2021]. Bifet et al.
2022 provide theoretical and practical computational speedups to the classic TREESHAP [Lundberg
ct al. 2020). Similar to these results, in this work, we provide significant speedups for the tree setting over previous methods.
As opposed the tree setring, which is "white box" setting, in the model-agnostic a.k.a black-box setting, we only have query access to the model. Here, our only means of access to the predictor is that we can pick an arbitrary x E x and query the predictor for its value (zx).. The usual approach here is to approximate the exponential sum of the SHAP value computations using stochastic sampling [Covert and Lee, 2020, Mitchell et al. 2022a Lundberg and Lee 2017]. In this setting, Covert and Lee 2020]. Mitchell et al. [022a]] provide sampling methods that require fewer queries to the black- compared to vanilla KERNELSHAP Lundberg and Lee 2017] for equal approximation accuracy. FASTSHAP Jethami et al. [2021], which introduces a method for estimating Shapley values in single forward pass using an end-to-end learned explainer neural network model. Our algorithm FOURIERSHAP falls into the query-access black-box setting as well. However, we take a different approach. We are guided by the key insight that many models used in practice have a "spectral bias". Yang and Salman (2019) Valle- et al. (2018) provably and experimentally show that fully connected neural networks with binary (zero-one) inputs learn low-degree - and therefore - - functions in a basis called the Walsh-Hladamate a.k.a Fourier basis. It is well known that the Halsh-Had transform (WHT) of an ensemble of T trees of depth d is also of degree at most d and moreover, A: = )(pars- (Kushilevitz and Mansour 1993
Mansour 1994).
Guided by the aforementioned insights, we provide an algorithm to compute SHAP values using the Fourier representation of the tree or black-box model. We first approximate the black-box function by taking its sparse Fourier transform. We theoretically justify, and show through extensive experiments, that for many real-world models such as fully connected neural networks and (ensembles of) trees this representation accurate. Subsequently, we prove that SHAP values for single Fourier basis function admit closed-form expression not involving an exponential summation. Therefore, using the Fourier representation we overcome the exponential sum and can utilize compute power effectively to compute SHAP values. Furthermore, the closed- form expression we derive effectively "linearizes" the computation into a simple summation and is amenable to parallelization only done once, therefore FOURIER amortizes the cost of computing explanations for many inputs. Subsequently, SHAP computations using the Fourier approximation are orders of magnitude faster compared to other black-box SHAP approximation methods such as KERNEL.SAA and other variations of it which all involve computationally expensive optimization. We show speedups over other methods such as DEEPLIFT (Shrikumar et al., 2017) and FASTSHAP (Jethani et al. [021] as well. In addition to the speedup, our algorithm enables a reliable continuous trade-off between computation and accuracy, controlled in fine manner by the sparsity of the Fourier approximation.
Our contributions:
multiple cores or GPU. The Fourier approximation step is
2 Background
This section reviews the notion of SHAP values, and sparse and low-degree Fourier transforms.
2.1 Shapley values
In game theory, a cooperative game is a function ; 21n) + R that maps a subset (coalition) S S [n]] of group of players [m]= = (I....,,) _n} to their total reward (when they cooperate). all the players cooperate they win a total reward of value v((z)). The main question is how they would distribute this reward among themselves. [Shapley| [1952] resolved this problem by a deriving a unique value based on "fairness axioms" proposed in his seminal work (Shapley 1952.. The Shapley value of

---

player i E [n] is:
vSSU (3) v(S) [S]
(c(1)
(I)
T2
Intuitively, can view the term v(S U {i}) v(S) the marginal contribution of player i when they are added to the coalition S. This marginal value is weighted according to the number of permutations the leading |S| players and trailing |S| players can form.
In the machine learning context, we have a predictor x - R mapping an n--imensional feature vector to value. In this context, the players become features 2; E X' and the reward is the prediction of the predictor and the Shapley value is the "contribution" or "influence" the prediction. We define (S) accordingly to capture this notion [Lundberg and Lee 2017]:
the i'th feature on
(S) = ( [1 [mm])s));
where x= E 2 is the instance we are explaining. This definition implicitly captures the way we handle the missing features (feature not present in the coalition): with respect to the marginal distribution (()(m) In practice, the marginalization is performed with an empirical distribution by taking a subset of the training data as background dataset.
integrate the missing features
The choice which distribution to average the missing features from has been discussed thoroughly in the relevant literature. As mentioned before, in this work, we focus on the SHAP values as defined
in KERNELSHAP introduced by Lundberg and Lee [2017), Lundberg et al. [0200] also known as "Interventional" (Jazzing al.) [020 Van den Broeck et al. [021] or "Baseline" [Sundararajan and Najmi 2020] SHAP, where the missing features are integrated out from the marginal distribution
p( [z]) s), as opposed the conditional distribution p( We refer the reader Ap- pendix A.3 for comprehensive overview of the literature discussing these two notions and their
conceptual differences.
Since we will be using the well-known KERNELSHAAP (Lundberg and Lee 2017 and its variant LINREGSHAP [Covert and Lee| 2020) as baseline, we briefly review their method here. Lundberg and Lee 2017) propose "least squares characterization" of SHAP values. They prove that SHAP values the solution to the following minimization problem:
" 8 A arg min
n
80 + Σ
Bi v(S)
u(S)
So..... Sn
(s
(S])
DE Sl
SES
> B. v(n)) s.h.: Bo =
Then (1))) = 3;
Unfortunately, the above optimization still involves an exponential sum. Therefore, Lundberg and Lee [017] propose to sample subsets S uniformly at random. Covert and Lee [2020]. Mitchell al. 2022a] provide better ways of sampling and solving the optimization to get approximations with lower variances and biases. Nevertheless, all these methods require solving least squares minimization subject to constraints for each explained instance x and, therefore, are computationally expensive.
Later, we also compare our method FASTSHAP (Jethani et al.) 2021], a model-agnostic algorithm for computing SHAP values. In FASTSHAP, a parametric explainer o (e.g.. MLP) is trained to directly generate SHAP values given data samples. Since training is only done once, this, similar to us, it amortizes the cost of generating SHAP values across multiple instances. Computing SHAP values only requires a forward pass on the trained model and therefore can be done very quickly.
2.2 Fourier representations
Here we review the notions of the Fourier basis and what we mean by sparsity. We will later use sparse Fourier representation
functions to compute SHAP values. In this work, we focus on the setting where the inputs to the black-box function (predictor) are binary, i.e., X = {0. 1)nh. This means, we assume we have binary features and/or categorical features, through standard one-hot representations Continuous features can be discretized into quantiles, enabling their transformation

---

into categorical features. The Fourier representation of the aseudo-boolent function h {0, + - is the unique expansion of h as follows: h(x))
Σ -
/2"
50(0.1)
The inner product of two vectors f,x E {0, 1 is defined as: (f,z) = Σi Jan Vf, 10,
The unique function h {0, R is called the Fourier transform of h. For any f E {0, 1)". h(ff) is called the Fourier coefficient corresponding to the frequency f. The family of functions ((+)
V2t w (-1)(f=), f E {0. 1)"h are the 2n -many Fourier basis functions. These basis functions
- { ( f+ f- f. E [0, Therefore, they form a basis for the vector space of all pseudo-boolcan functions / 10" + R.
are orthonormal:
Σ ()())
Z (0.1)"
We define the support of h to be supp(h) = (0, [f() 0}. We say that a function h is k-sparse if at most & of the 2n Fourier coefficients h(f) are non-zero, i.e., (supp(h)] S k. The degree of vector f E {0. 1)th is denoted by dJg(S) (f) and is defined as the number of ones in the vector. For example, n
then / = (1, 0, 0, 1, 0) is a vector of degree deg(/) = 2. We say a function is degree d when the frequencies f E {0, 1 corresponding to non-zero Fourier coefficients are of degree less or equal to d i.. Vf E supp(h) it holds that deg(f) < d.
By definition of the Fourier basis, a k-sparse degree d function can be written as a summation of l (Fourier basis) functions, each one depending on most d input variables. The converse is also true:
Proposition 1. Assume h {0, 13ah R. can be decomposed as follows: h(z) Σ h,(as,, ), S
[n]. That is, each function h4 {0, 1315: + TR depends on at most [S variables. Then, h is
k 0 2 2-sulrss and of degree d = max((Si)...... (Proof in Appendix B.1
The sparsity k and degree d capture a notion of complexity for the underlying function. Intuitively speaking. the sparsity factor ls puts limit the number of functions in the decomposition, and the degree d puts a limit on the order of interactions among the input variables.
One can see from Proposition | that modular functions, i.c., functions that can be written of functions each depending on exactly one variable, are h = slightly more "complex" function capturing second-order interactions among the input variables, i... a function that can be written as a sum where each term depends on at most two variables is going to be As O(n²) ((n2)-sparss -sparse and of degree d = 2. The following proposition generalizes this result.
and of degree = 1. A
Proposition 2. Let, h (w.r.. n). If h is of degree d, then, it is k = =(n"))-parse. (Proof in Appendlx B.
{0, 1) - R be assuudobboless function and let d E N be some constant
This proposition formally shows that limiting the order of interactions among the input variables implies an upper bound on the sparsity.
3 Many real-world black-box predictors have sparse Fourier transforms
In this section, we discuss the sparsity of the Fourier transforms of ensembles of trees and why neural networks can be approximated by a sparse Fourier representation because of their spectral bias. This shows both these classes of functions can be compactly represented in the Fourier basis. The results here will become useful in the next section, where we present our main contribution on how we can leverage this compact representation, to precisely compute SHAP values cheaply.
3.1 Spectral bias of fully connected neural networks
The function a fully connected neural network represents at initialization is sample from Gaussian Process (GP) [Rasmussen] 2004] in the infinite-width limit. Here, the randomness is over the initial weights and biases. The kernel K of this GP is called the Conjugate Kernel (CK) (Daniely et al. 2016 Lee et al.) 2017). As mentioned before, here we investigate the case where the inputs to the neural network binary, i.e., x {0. 1) similar to (angg and Salman
2019 Valle-Perez et al.
2018).
The CK kernel Gram matrix formed on the whole input space X {0. 1..1" has a simple

---

eigenvalue decomposition: KC E 2222"22 x2 K== Σ Xpufuf, where u E R²" is the eigenvector
SE(0.13"
formed by evaluating the Fourier basis function y for different values of x E {0.1)". Moreover, Yang and Salman [2019] show weak spectral bias result in terms of the degree of f. Namely, the eigenvalues corresponding to higher degree frequencies have smaller values Given the kernel, K, and viewing a randomly initialized neural network function evaluated
the boolean {0, 1)"h
sample from a GP one can see the following: This sample, roughly speaking, looks like a linear combination of the eigenvectors with the largest eigenvalues. This is due to the fact that sample of
the GP can be obtained Σ Xoungui ui (O, 1). Combining this with the spectral bias results
implies that neural networks are low-degree functions when randomly initialized.
Going beyond neural networks initialization, numerous studies have investigated the behavior of fully connected neural networks trained through (stochastic) gradient descent. Chizat et al. (2019), Jacot et al. (0188), Du et al. (2018), Allen-Zhu al. [2019a b) found that the weights of infinite- width neural networks after training do not deviate significantly from their initialization, which has been dubbed "lazy training" by Chizat et al. [2019). Lee al. 2018 2019] showed that training the last layer of an infinite-width randomly initialized neural network for an infinite amount of time corresponds to Gaussian process (GP) posterior inference with a certain kernel. [Jacot et al. [018b) extended the aforementioned results to training all the layers of neural network (not just the final layer). They showed the evolution of an infinite- anftt neural network function can be described by the "Neural Tangent Kernel" [NTK, Jacot INTK, et al.) [0188] with the trained network yielding, on
average, the posterior mean prediction of the corresponding GP after an infinite amount of training time. Lee et al. [2019] empirically showed the results carry over to the finite-width setting through
extensive experiments. Yang and Salman (019 again showed that the uy R² defined above are eigenvectors of the NTK Gram matrix and spectral bias holds. [ooji et al. [2023] validated
these theoretical findings through extensive experiments in finite-width neural networks by showing
that neural networks have "less tendency" to learn high-degree frequencies. We refer the reader to Appendix A. for more comprehensive review.
The aforementioned literature shows that neural networks can be approximated by low-degree functions. By Proposition 2 they can be approximated by sparse functions for large enough sparsity factor k. Our experiments in Section 5 provide further evidence that neural networks trained on real-world datasets approximated well with sparse (and therefore compact) Fourier representations.
3.2 Sparsity of ensembles of decision trees
In our context, a decision tree is rooted binary tree, where each non-leaf node corresponds to one of n binary (zero-one) features, and each Icaf node has a real number assigned to it. We denote the function a decision tree represents by t: {0, 13" + IR. Let E [n] denote the feature corresponding to the root, and let fiett {0, 1 -> I and fight {0. 1 R be the left and right sub-trees, respectively. Then the tree can be represented as:
1 (-1)(emm))
1 - (-1)(e.2)
t(x)
(x)
tright
2
2
where, e, E {0, 13"h is i'th indicator vector.
Thus, the Fourier transform of a decision tree can be computed recursively (Kushilevitz and Mansour 1993 Mansour ].94]. The degree of decision tree function of depth is d, and if (supp((eet = kien and |supp fright) | = kriihtt, then |supp(t)] < 2(kue + kright). ). As a result, decision tree function is k-sparse, where k = O(4)). although in some cases, when the decision tree is not balanced or cancellations occur, the Fourier transform can be sparser, i.e., admit a lower k. than the above upper bound on the sparsity suggests.
Due to the linearity of the Fourier transform, the Fourier transform of ensemble of trees, such as those produced by the random forest, cot-b [Dorogush et al. 2018). and XGBoost [Chen and Guestrin 2016) algorithms/ibraries, can be computed by taking the average of the Fourier transform
"To be more precise, they show that the eigenvalues corresponding to even and odd degree frequencies form decreasing sequences. That is, even and odd degrees considered separately.
5

---

of each tree. If the random forest model has T' trees, then its Fourier transform is l - O(T4") and of degree d equal to its maximum depth of the constituent trees.
4 Computing SHAP values with Fourier representation of functions
In the previous section, we saw that many real-world models trained on tabular/discrete data can be exactly represented (in the case of ensembles of decision trees), or efficiently approximated (in the case of neural networks) using a compact (sparse) Fourier representation. We saw neural networks have a tendency to learn approximately low-degree, and hence by Proposition 2 sparse functions. This has been attributed in numerous works to the reason why they generalize well and do not overfit despite their aver-parameterized nature [Valle-Perez et al. 2018) Yang and Salman 2019] Huh et al. 2022 Durvasula and Liter 2020. Kalimeris et al. 2019 Neyshabur et al. [2017 Arpit et al. 2017]. We also saw that (ensembles) of decision trees, by nature, have sparse Fourier representations [Kushilevitz and Mansour 1993 Mansour 1994]. More generally,
made formal in Proposition []
and the remarks after, any "simple" function that can be written as a summation of a "few" functions each depending on "few" of the input variables is sparse and low-degree in the Fourier domain.
We propose the following method to approximate SHAP values for black-bor functions. In the first step, given query access to black-box function, we utilize sparse Fourier approximation algorithm such as [Li and Ramchandran 2015 Amrollahi et al. 2019 Li et al. 2015] to efficiently extract its sparse and hence compactly represented Fourier approximation. See Appendix A.2 for a more detailed explanation. Next, in our second step presented here, we use the Fourier representation to exactly compute SHAP values.
Let h: {0, 11 + R be some predictor that we assume to be k-sparse. Assume [m] 2 {I, n2 as be the instance we are explaining. Aligned with (Lundberg
the set of features and let x² {0, 13"h
and Lee 2017), we use 2/2 (S) - pDd Σ ((i)ys) as the value function, which is the average
(a.v)E
prediction when fixing z'g in the (background) dataset D. We compute the Shapley values for single Fourier basis function V (z) = (-1)(fz2) f {0, according to Equation [S|!(n [S| -3-11 1)!
Σ ((-I)Me (e (- (-1) (o(ms)))
D
n!
SC
(D.N)D
The E operator concatenates two vectors along the same axis.
This expression still has an exponential sum (in n), since we are summing over all subsets S. As main contribution, combinatorial argument. This results in the following key Lemma:
find closed-form analytic expression for the inner summation using
Lemma 1.
Let 1 (z) = (-1)(fa) be the Fourier basis function for some f E (0.1)". 1)". Then the SHAP value of the Fourier basis function f with respect to the background dataset D is given
2f [D]
(LAI +1)
mod?
Σ
(-
[A| +1
(2.0)ED
where A é {j [n][e, # 23.j # i. 13. (Proof in Appendix B.2
Intuitively, feature é contributes to the prediction only if the Fourier basis function thy is sensitive to the value of feature i.e. fi and otherwise its contribution is zero. The SHAP values is also dependent on the parity of the number of differences between the query and background samples within support of f:: many positive and negative terms cancel during the exponential summation. The key combinatorial insight is that we can count the number of cancellations in the exponential sum without computing it and therefore this collapses into closed-form factor depending on the parity of the "overlap set" A.
Finally, by the linearity of SHAP values w.r.t. the explained function h, and by utilizing Lemma | we arrive at the final expression for SHAP values of h. We present this closed-fomm expression alongside its computational complexity in our main Theorem:
Theorem 2. Let h (0, 13" + R be a k-sparse pseudo-boolean function with Fourier frequencies fl fl...., fk E shpp(h) and amplitudes h(f), vf E supp(f). Let D be background dataset of size

---

(D). Then, Equation 5 provides precise expression for the SHAP value vector 6² =
One can compute this vector with ( (D) k) flops (floating point operations).
tf
2
Mn- Se
Σ (a.N))
1s:te; (-1)(ha)) (141 +1) mod 2
(5)
|A +1
(Esupp(h)
where A is the same as in Lemma
(Proof in Appendix B.3
Theorem provides computationally efficient method for deriving SHAP values from a Fourier representation of function h. The resulting SHAP values exact, that is. if the Fourier represen- tation is precise, then the SHAP values are also exact. This contrasts with KERNELSHAP, which approximates SHAP values via stochastic sampling, requiring convergence checks to ensure accuracy. In our method, any approximation arises solcly from estimating a sparse Fourier representation, and only in the black-box setting.
More importantly, the sum in Equation iss tractable. This is because we overcome the exponential sum involved in Equation analytically computing the sum, with a combinatorial argument, for single Fourier basis function. We show that the number of flops that are required to compute SHAP values in Theorem 2 is asymptotically equal to ( [D] k). We note that the [D] and k factors in the asymptotic computational complexity arise from the two summations present in Equation
Through this expression, are able to "linearize" the computation of SHAP values to summation over the Fourier coefficients and the background data set. This allows us to maximize parallclization on multiple cores and/or GPUs to speed up the computation significantly. Therefore, in the presence of multiple cores or a GPU, we can get speedup equal to the level of parallelization, as each core or worker can compute one part of this summation.
We implement our algorithm called FOURIERSHIAP using JAX [Bradbury et al. 2018 which allows fast vectorized operations GPUs. Each term within the summations of Equation 5 can be implemented with simple vector operations. Furthermore, summations over the & different frequencies in the support of h and also background data points can both be efficiently implemented and parallelized using this library using its VMAP operator. We perform all upcoming experiments on believe faster computation can also be achieved by crafting dedicated
single GPU. Nevertheless, code designed to efficiently compute Equation on GPU.
Finally, we note that the function approximation (first step) is only done once, i.e., we compute the sparse Fourier approximation of the black-box only once. This is typically the most expensive part of the computation. For any new query to be explained, we resort to an efficient implementation of Equation 5 As our experiments will show, this yields orders of magnitudes faster computation than previous methods such as KERNEL where, as mentioned before in Section [ each explained instance requires solving an expensive optimization problem.
Experiments
We assess the performance of our algorithm, FOURIERSHAP, on four different real-world datasets of varying nature and dimensionality. Three of our datasets are related to protein fitness landscapes
[Poelwijk et al.) 2019 Wu et al. 2016 Sarkisyan et al. 2016) and are referred to as "Entacmaea" (dimension n 13), "GBI" (n 80), and "avGHP" (n 236) respectively. The fourth dataset is a GPU-tuning [Nugteren and Codreanu] 2015) dataset referred to as "SGEMM" (n = 40). The features of these datasets are binary (zero-one) and/or categorical with standard one-hot encodings. See Appendix C for dataset details.
For the Entacmaea and SGEMM datasets, we train fully connected neural networks with 3 hidden layers containing 300 neurons each. For GB1 1 we train ensembles of trees models of varying depths using the random forest algorithm and for GvGFP train again, ensembles of trees models of varying depths using the cat-boost algorithm/libray Dorogush et al. 2018).
Black-box setting. The first step of the FOURIERSHAP algorithm is to compute sparse Fourier approximation of the black-box model. We use a GPU implementation of a sparse Vadama- Transform (sparse WHT) a.k.a Fourier transform algorithm [Amrollahi et al.) 2019] for each of the four trained models. The algorithm accepts a sparsity parameter k which is the sparsity of the computed Fourier representation. Higher sparsity parameter h results in better function approximation but the sparse-WHT WHT runtime increase linearly as well. In Figure [ we plot the accuracy of the Fourier function approximation measured by the Rs-or for different values of
7

---

Neural Network on Entacmasa
Neural Network on SGEMM
Random forest GB1
Catboost on avGFP
Nou 1o w00-0/pp00 www.rrorrrroooooo LOMFS
0ppeh-3
0.6
0cp0h=5
ospeh
doothe3
0-1
aspkh-7
dopth=3
aspeh
septh
02pch~
dcptt=
0tpeh-13 18
dtpth-a
20.0 12.5
2.30
150
30
1.00
200
2:00
320
420
500
Figure I: Step of FOURIERSHAP: Accuracy of the Fourier transform (in approximating the black- box function) vs. runtime of the sparse Fourier algorithm. The accuracy is evaluated by R score and comparing the outputs of the black-box -bx and the Fourier representation on a uniformly generated random dataset on the Boolean cube {0, 1)". For fixed level of accuracy, higher depth trees require a higher number of Fourier coefficients ls therefore a higher runtime. For the case of trees, we eventually able to reach perfect approximation since the underlying function is truly sparse.
Neural Network on Entacrnace
Neural Network on SGEMM
Spoedup over Kerneistpp
102
2-ayer
Spredup over KarnelSHAP
15a
byyor
2layor
30*
30t
Kome Bassincc
127
KomotsHAP loase inc)
PowrtershAP (oursl Deeal (whitebox) LiRuySHHp RastSMAP
100
Pouriestkk (ours)
DeepLitt (whneebo LinRogSHAP FAstSHAP
F
02
0.4
0.6
0.8
10
0.2
0.4
0.6
0.8
1.0
SHAP values acturacy
SHAP values accuracy
Random forest on GB1
Catboost an avGFP
10a
Specdup over KemelsHap
Speeduup KernelSHA
4-layer
Glayer
2dkyyr
10.
10.
Elayer
4-lyye
10"
KemndSHarP (baseine)
30?
FoutierSHtPP depth-3
SHAP dopot=3
162
FourientiWW depthis
101
Fourie SHAAP
depat-5
FourierSHAP depthau
Solt deptha7
107
LinRogEHAP dooth-s
10.
UnRegSHAPI depeh-S
FautsAAP| depabes
FantSM0PP1 cepphiss
10-1
0.94
0.66
0.88
0.30
0.92
0.94
0.96
0.98
1.00
0.60
0.65
0.70
0.75
0.50
0.85
0,00
0.95
1.00
SHAP values accuracy
R²
SHAP values accurasy A
Figure 2: Speedup vs. Accuracy. Speedup of different algorithms is reported as a multiple compared to the runtime of KERNELSHAAP. Accuracy is quantified by the Re-score against ground truth SHAP values. DEEPLIFT is a white-box algorithm for neural networks. LINREGSHAP is black-box algorithm and a variance-reduced version of KERNELSHAP FASTSHAP, a black-box algorithm, is a trained MLP to output SHAP values given inputs in one forward pass. We test MLPs of three different sizes for FASTSHAP. FOURIERSHAP is ours. We are 10-10000x faster than LIN REAPHAP on all dataset/model variations. More notably, outperform DeepLift in the neural network model setting even though we assume only query access (black-box setting). We achieve higher accuracy than FASTSHAP in 3/4 settings, while enabling fine- fine-grained control over the speed-accuracy trade-off.
l (which result in different runtimes). The R² score is computed over dataset formed by randomly sampling the Boolean cube (0, 1)".
The second step of SOUR utilizes the Fourier approximation to compute SHAP values using Equation 5 We implement this step using JAX library (Bradbury et al. 2018), and run it on a GPU, For each model to be explained, samples and four different values for the number of query points to be explained, resulting in a total of 16 runs of FOURIERSHAP for each model. Error bars capture these variations. We take the runtime of KERNELSHAP, with Github repo default settings, to be the base runtime all other methods are compared to, i.e., assume its runtime is 1 unit.
choose four different values for the number of background
In order to measure the accuracy of the SHAP values produced by our and other algorithms we need ground truth SHAP values. We use KERNEL SHAP to this extent. Note that KERNEL.SHAP inherently an approximation method for computing interventional SHAP values. However, this approximation becomes more precise by sampling more coalition subsets. Therefore, to generate
8

---

ground truth values, for each dataset, we sample more and more coalition subsets and check for convergence in these values. A more detailed explanation can be found in Appendix
We compute the R² values of Shapley values computed by FOURIERSHAP (ours) vs. ground truth values evaluate accuracy. For our method, higher sparsity k for the Fourier representation results in more accurate function approximation therefore higher Rt² values for the SHAP value quality, On the other hand, a higher results slower runtime as Equation is a sum over the k different frequencies. In Figure 2 we plot this trade-off.
We compare against the following baselines in Figure 2 The first is LHNR variance- reduced version of KERNELSHAN [Covert and Lee 2020]. We found that although this algorithm requires fewer queries from the black-box, it takes orders of magnitudes longer to compared to ours. Secondly, for the neural network models, we also compare against a state-of-the-art white-box method DEFPLIFT [Shrikumar et al. 2017]. This algorithm, requires access to the neural network's activations in all layers. In comparison, we achieve a 10-100x speedup while being both more accurate and only assuming query access the neural net (true black-box setting).
Finally, we compare against FAST [Jethani et al. 2021]. which is the most comparable to our setting, i.e., model-agnostic with amortized cost. We provide higher accuracy for similar speedup values compared to FASTSHA: HAP in 3/4 settings. More importantly, we can see that by controlling the sparsity parameter is of the Fourier function upproximation, can control the tradeoff between accuracy and speed in a reliable and fine- seeeegrrind manner. Whereas for FASTSHAP the accuracy of the SHAP values relies the functional approximation properties of the MLP which directly produce SHAP values. As seen in Figure 2 the MI.P can behave in unpredictable ways. In this figure, we can see that increasing the depth of the model (and hence the approximation capability of the MLP) does not have a reliable effect on SHAP accuracy. Finally, in FASTSHAP, for a different choice of background dataset, a new MLP model has to be trained from scratch since the MLP approximates the process of directly computing SHAP values. In contrast, we can support different sets of background datasets since our Fourier functional approximation is performed the black-bor predictor, and not on the whole process of producing SHAP values end-to-end (FASTSHAP).
Tree setting, SHAP can also be utilized for the computation of SHAP values for (ensembles of) trees in the white-box setting, i.e., where full access to the tree's structure is available. In this setting, the exact sparse Fourier representation of an ensemble of trees can be efficiently computed (the first step of FOURIER using Equation [ With the exact Fourier representation at hand, SHAP values be efficiently and exactly computed using Equation [ the second step of SHAP This makes our method a highly parallelizable alternative for TREESHIAP [Lundberg et al. 2020 with the potential for order of magnitude speedups.
To demonstrate our method's ' ability in fast computation of SHAP values in this setting, we compute SHAP values for random forests fitted on all aforemennioned real-world datasets. We compare FOURIERSHAP'S speedup over TREESHAP (Lundberg et al. 2020), to FASTTREESHAP (Yng
2021 fast implementation of TREESHAP, the GPU implementation of TREESHAP [Mitchell
et al. 2022b) and PLTREESHAP [Zern et al. 2023]. To the best of our knowledge, these are the fastest available frameworks for computation of the "interventional" SHAP values. Figure 3 shows the superior speed of our method over all state-of-the-ard algorithms in most settings, which weakens with increased depth and number of features, resulting in higher count of frequencies and greater computational overhead. Note that the SHAP values computed by all methods are precise and identical the values produced by TREESHAP, which is to be expected for FOURIERSHAP, given access to exact Fourier representation of random forests.
Conclusions
We illustrated in theory and practice how many black-box functions can be represented or efficiently approximated by compact Fourier representation. We proved that SHAP values of Fourier basis functions admit closed form expression, and therefore, we can compute SHAP values efficiently using the compact Fourier representation. Moreover, this closed form expression is amenable to parallelization. These two factors helped us gaining speedups of 10- 10-1000xx over baseline methods for the computation of SHAP values. We discuss the limitations & future works in Appendix FF]

---

Entacmasa (n=13)
SGEMM (1=40)
GB1 Inm 80]
SVGFP (n=236)
Spoedhp TroSS-a
Foureers loun))
TresSHAP (CPU)
301
Dapth
Dupth
Figure 3: Speedup vs. depth of tree, for different algorithms, reported as a multiple compared to the runtime of TREESHAP. FOURIERSHAP ours. As other basclines have a GPU implementation of TREESHAP, FASTTREESHAP and PLTREESHAP. We achieve order of magnitude speedups over all depths the Entacmaea and SGEMM datasets. We also achieve significant speedups in the other two datasets; however, the edge diminishes as the maximum depth increases.
Acknowledgments
This work was supported by the Swiss National Science Foundation (SNSF) through National Centre of Competence in Research (NCCR) Catalysis (Grant No. 180544). We thank Bhavya Sukhija for valuable feedback and help during the review and rebuttal process.
10

---

References
Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features dependent: More accurate approximations to shapley values. Artificial Intelligence, 298: 10300, 2021.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019a.
Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. Advances in neural information processing systems, 32, 2019b.
Andisheh Amrollahi, Amir Zandieh, Michael Kapralov, and Andreas Krause. Efficiently learning fourier sparse set functions. In Advances in Neural Information Processing Systems, pages 15120-15129, 2019.
Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better understanding of gradient-based attribution methods for deep neural networks. In International Conference Learning Representations, 2018.
Marcelo Arenas, Pablo Barceló, Leopoldo Bertossi, and Mikaël Monet. The tractability of shap- score-based explanations for classification over deterministic and decomposable boolean circuits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6670-6678, 2021.
Devansh Arpit, Stanistaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A Closer Look at Memorization in Deep Networks. In Proceedings of the 34th International Conference Machine Learning, pages 233-242. PMLR, July 2017. ISSN: 2640-3498.
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. In International Conference on Machine Learning, pages 685-694, PMLR, 2020.
Albert Bifet, Jesse Read, Chao Xu, et al. Linear tree shap. Advances Neural Information Processing Systems, 35:25816 18 188228888 2022.
James Bradbury, Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http://// github. com/ wow/google/aa.
Yuan Cao. Zhiying Fang. Yue Wu, Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv:19122. 0188, 2019.
Hugh Chen, Joseph D Janizek, Scott Lundberg, and Su-In Lee. True to the model or true to the data? arXiv preprint arXiv:2006.162: 16234, 2020.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
Mahdi Cheraghchi and Piotr Indyk. Nearly optimal deterministic algorithm for sparse walsh-haid hadamadd transform. ACM Transactions Algorithms (TALG), 13(3):1-36, 2017.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning, Advances in neural information processing systems, 22, 2009.
Ian Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation via linear regression, arXiv preprint
2020.

---

Amit Daniely. Sgd learns the conjugate kernel class of the network. Advances in Neural Information Processing Systems, 30, 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. Advances in neural information processing systems, 29, 2016.
Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems. In 2016 IEEE symposium on security and privacy (SP), pages 598-617, IEEE, 2016.
Anna Veronika Dorogush, Vasily Ershov, and Andrey Gulin. Catboost: gradient boosting with categorical features support. arXiv preprint arXiv: 18/0: /163,, 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wver-parameterize neural networks. arXiv preprint 11X.0::810002054, 2018.
Karthik Durvasula and Adam Liter. There is simplicity bias when generalising from ambiguous data. Phonology, 37(2):1772113, May 2020. ISSN 0952-6757, 1469-8188. doi: 10.1017/
50952675720000099, Publisher: Cambridge University Press.
Zhou Fan and Zhichao Wang. Spectra the conjugate kernel and neural tangent kernel for linear- width neural networks. Advances in neural information processing systems,
2020.
Ali Gorji, Andisheh Amrollahi, and Andreas Krause. A scalable aalsh-hadamard regularizer to overcome the low-degree spectral bias of neural networks. In Uncertainty in Artificial Intelligence, pages 723-733. PMLR, 2023.
Ulrike Gromping. Estimators of relative importance in linear regression based on variance decompo- sition. The American Statistician, 61(2):139-14) 2007.
Tamir Hazan and Tommi Jaakkola. Steps toward deep kernel methods from infinite neural networks. arXiv e-prints, pages arXiv-1508, 2015.
Y. Huang, Y. Chen, and J. Lee. Updates on the complexity of shap scores. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024.
Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung. Pulkit Agrawal, and Phillip Isola. The Low-Rank Simplicity Bias in Deep Networks, April 2022. arXiv:2103, 10427 [cs].
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018a.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 20.
Dominik Janzing, Lenon Minorics, and Patrick Bloebaum. Feature relevance quantification in explainable ai: A causal problem. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 2907-2916. PMLR, 26-28 Aug 2020. URL https://proceeddings mlr. latp://vvvv1oo//zinniee html
Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. Fastshap: Real-time shapley value estimation. In International Conference on Learning Representations. 2021.
Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. SGD on Neural Networks Learns Functions of Increasing Complexity. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 22:1331-1348, 1993.
12

---

Yongchan Kwon, Manuel A Rivas, and James Zou. Efficient computation and analysis of distributional shapley values. In International Conference on Artificial Intelligence and Statistics, pages 793-801. PMLR, 2021.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint vrXiv:/71..0010 2017.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohk-Dickstein. Deep neural networks as gaussian processes. International Conference on Learning Representations, 2018.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Xiao Li and Kannan Ramchandran. An active learning framework using sparse-graph codes for sparse polynomials and graph sketching. Advances in Neural Information Processing Systems, 28, 2015.
Xiao Li, Joseph K Bradley, Sameer Pawar, and Kannan Ramchandran. Spright: A fast and robust framework for sparse walsh- halls-h transform. arXiv preprint arXiv: 1508 06336, 2015.
Scott M Lundberg and Su-In Lee. unified approach interpreting model predictions. In Advances in Neural Information Processing Systems. volume 30, 2017. URL https: https://proceeddin pdf
neurips. http://ppw........///////////660
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):56-67, 2020.
Yishay Mansour. Learning boolean functions via the fourier transform. In Theoretical advances in neural computation and learning, pages 391-424, Springer, 1994.
A. Marzouk, V. Belle, and G. Van den Broeck. On the tractability of shap explanations under markovian distributions. Proceedings of the 41 International Conference on Machine Learning (ICML), 2024.
A. Marzouk, V. Belle, and G. Van den Broeck. On the computational tractability of the (many) shapley values. Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS), 2025.
Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for shapley value estimation. Journal of Machine Learning Research, 23(43):1-46 2022a.
Rory Mitchell, Eibe Frank, and Geoffrey Holmes. Gputreeshap: Massively parallel exact calculation of shap scores for tree ensembles, 2022b.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pages 29-53. Springer, 1996.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring Gener- alization in Deep Learning, July 2017. arXiv: 1.Xiv:1706... 776.009477 [cs].
Cedric Nugteren and Valeriu Codreanu. CL.Tune: A Generic Auto-Tuner for OpenCL. Kernels. In 2015 IEEE 9th International Symposium on Embedded Multicore/Many-cor Systems-on-Ciin -hhip. pages 195-202. September 2015. doi: 10.1109/MCSoC.20155.
Art B Owen. Sobol indices and shapley value. SIAM/ASA Journal on Uncertainty Quantificatio,, 2 (1):245-251, 2014.
Art Owen and Clémentine Prieur. On shapley value for measuring importance of dependent inputs. SIAM/ASA Journal Uncertainty Quantification, 5(1):966-102, 2017.
Judea Pearl. Causality. Cambridge university press, 2009.
13

---

F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel. M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Frank Poelwijk, Michael Socolich, and Rama Ranganathan. Learning the pattern of epistasis linking genotype and phenotype in protein. Nature Communications, 10(1):4213, September 2019. ISSN 2041-1723. doi: 10.1038/s41467-010 119--000--
Number: Publisher: Nature Publishing Group.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5310. PMLR, 2019.
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pages 63-71. Springer, 2004.
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. Advances in Neural Information Processing Systems, 32, 2019.
Karen S. Sarkisyan, Dmitry A. Bolotin, Margarita V. Meer, Dinara R. Usmanova, Alexander
Mishin, George V. Sharonov, Dmitry N. Ivankov, Nina G. Bozhanova, Mikhail S. Baranov, Onuralp Soylemez, Natalya S. Bogatyreva, Peter K. Vlasov, Evgeny Egorov, Maria D. Logacheva, Alexey S. Kondrashov, Dmitry M. Chudakov, Ekaterina V. Putintseva, Ilgar Z. Mamedov, Dan S. Tawfik, Konstantin A. Lukyanov, and Fyodor A. Kondrashov. Local fitness landscape of the green fluorescent protein. Nature, 533(7603):397-401 May 2016. ISSN 1476-4687. doi: 10. 10.10038/atuur:19955 Number: 7603 Publisher: Nature Publishing Group.
Robin Scheibler, Saeid Haghighatshoar, and Martin Vetterli. A fast hadamard transform for signals with sublinear sparsity in the transform domain. IEEE Transactions on Information Theory, 61)) 2115-2132, 2015.
Lloyd S. Shapley. A Value for N-Person Games. RAND Corporation, Santa Monica, CA, 1952. doi: 10.7249/P0295.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference on machine learming, pages 3145- 3153. PMLR, 2017.
Erik Strumbelj, Igor Kononenko, and M Robnik Šikonja. Explaining instance classifications with interactions of subsets of feature values. Data & Knowledge Engineering, 68(10):886 2009.
Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International conference on machine learning, pages 9269-9278. PMLR, 2020.
Guillermo Valle-Perez, Chico Q Camargo, and Ard A Louis. Deep learning generalizes because the parameter-fuucttin map is biased towards simple functions. arXiv preprint a8Xiv:1805.08522, 2018.
Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the tractability of shap explanations. In Proceedings the 35th Conference on Artificial Intelligence (AAAI), 2021.
Paul Voigt and Axel Von dem Bussche. The general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, (033152676:10-55555 2017.
Christopher Williams. Computing with infinite networks. Advances in neural information processing systems, 9, 1996.
Nicholas Wu, Lei Dai, Anders Olson, James O Lloyd-Smith, and Ren Sun. Adaptation in protein fitness landscapes is facilitated by indirect paths. eLife, 5:e16965, July 2016. ISSN 2050-084X. doi: 10.7554/eLife. 16965. Publisher: eLife Sciences Publications, Ltd.
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks. arXiv preprint 1907,09900,,099 2019.
14

---

Jilei Yang. Fast treeshap: Accelerating shap value computation for trees. arXiv preprint arXiv:2109.0980 09847, 2021.
Artjom Zern, Klaus Broelemann, and Gjergji Kasneii. Interventional shap values and interaction values for piecewise linear regression trees. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 11164-1117, 2023.
15

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.ccppullc//uuuii wwwiicccguie//eeeeeeeeeii CoodeSubeiiie ssi wsionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer:[Yes
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: While our method may enable beneficial applications in model interpretability. it does not introduce foreseeable risks or harms.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No models or datasets with misuse risk are released.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects is performed in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects is performed in this work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLM is used core component in this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: http:p/p......o..eeeeee////////. for what should or should not be described.
22

---

A Relevant work
A.1 Neural network theory and simplicity biases
With regards to simplicity biases in fully connected neural networks, substantial amount of research has been dedicated analyzing neural networks in function space. This line of research is dedicated to firstly showing that "eifintteewidth"" randomly initialized (with Gaussian distribution) neural networks are distributed as Gaussian Processes (GPs) and secondly computing the kernel associated
to the GP Neal 1996, Williams] 1996, Cho and Saul 2009 Hazan and Jaakkola 2015 Lee et al. 2017 Ancona et al., 2018 Daniely 2017]. . The kernel associated with the GP is commonly known as the "conjugate kernel" [Danclyy 2017 or the "NN-GP kernel" [Lee et al. [017]. Other works
show that in infinite-width neural networks weights after training via SGD do not end up too far
from the original [Chizat al., 2019 Jacot et al. 20 Du et al. 2018 Allen-Zhu et al. 2019a b), referred to as "lazy training" by Chizat et al. [019]. This allowed Jacot et al. [201 Sa to prove that the evolution of an infinitewwitth neural network during training can be described by kernel called the "Neural Tangent Kernel". Lee et al. 2019) showed, through extensive experiments that the same behavior holds even for the more realistic case of neural nets of finite width. Empirically speaking, it was shown by |Rahaman et al. [2019] that a neural net with one input tends to learn sinusoids of lower frequencies in earlier epochs than those with higher frequencies. By analyzing the spectrum of the NTK's Gram matrix, Ronen et al. [2019], Basri et al. [2020] were able to formally prove this empirical finding. Yang and Salman [2019), Fan and Wang (2020) analyze the spectra of the NTK gram matrix for higher dimensional inputs. Specifically, Yang and Salman [2019), Valle-Perez ct al.
2018) provide simplicity bias results for the case where the inputs to neural net are Boolean (zero-one) vectors.
A.2 Sparse and low-degree Fourier transform algorithms
We now discuss algorithms that efficiently approximate general black-box predictors by a Fourier sparse representation. Let h : (0,1)" + TR be a any function. We assume we have query access to h. That is, we can arbitrarily pick x E {0,1)" and query for its value h(z).. Without any further assumptions, computing the Fourier transform requires to query exponentially, to be precise 2", many queries: one for every x E {0, 1)" Furthermore, classical Fast Fourier Transform (FTT) algorithms are known take at least 92(2" log(2")) time.
Under the additional assumption that is k-sparse, works such as Cheraghehi and Indyk (2017).
Amrollahi et al. [2019) Scheibler et al. (2015), Kushilevitz and Mansour [1993], Li and Ramchandran
2015 Li et al. 2015 provide algorithms that obtain the Fourier transform more efficiently. In particular, Amrollahi et al. [2019] provide algorithms with query complexity O(nk) and time complexity Oink log k) time Assuming further that the function of degree
o(n). the query complexity reduces to O log n). with run time still polynomial in nt, k, d. Crucially, even if the function is not k-sparse, Algorithm ROBUSTSW WHT of Amrollahi et al. 2019 yields the best k-sparse approximation in the le- le sense. More precisely, let us denote by hy {0, 1)" + the function that is formed by only keeping the top i non-zero Fourier coefficients of h and setting the rest to zero. Then the algorithm returns O(k)) -sparse function g such that:
GV) - -(())² S C(1 +c) [
Σ
Σ
GV) - (T))
min k-sparse
9
where C' is a universal constant. By Parseval's identity, the same holds if the summations were over the time (input) domain instead of the frequency domain.
A.3 Shapley values in the context of Machine learning
In the context of ML. many works have derived a different notion of Shapley value depending on what they mean by data distribution, deleted features, etc. We refer the reader the survey by /Sundararajan and Najmi 2020), Janzing et al. (2020) for a comprehensive overview. In this work we focus on the notion SHAP introduced by Lundberg and Lee 2017 Lundberg et al. (2000) also known as "Interventional" (Janzing et al., 2020 Van den Broeck et al. 2021 or "Baseline" SHAP (Sundararajan and Najmil 2020) where the missing features are integrated out from the marginal distribution as
opposed to the conditional distribution (see Section 2). As pointed out by Janzing et al. (2200] there
23

---

are two main ways to define the SHAP value "interventional" and "observational" SHAP. These are referred by Sundararajan and Najmi
2020
"baseline" and "conditional" SHAP respectively.
the difference between these definitions can be better viewed Roughly speaking "observational" SHAP tells us about how influential a feature is to the prediction of the predictor if it goes from the state of being unobserved to observed. "Interventional" SHAP causal and tells us how influential feature in (through a process called an intervention) and change that feature in order to change the prediction. Put into the context of credit scores and loan approvals, "observational" SHAP will provide us with important features which are "observed" by the predictor and hence are influential in predicting if a particular loan request will be rejected or approved. Interventional SHAP would tell us which feature we could change or "intervene" in order to change the outcome of the loan request.
As pointed out by Janzing et al.
2020
with the lens of causality [Pearl 2009
we were reach
The original (ML) SHAP paper [Lundberg and Lee| 2017] proposes "observational" (conditional) SHAP as the correct notion of SHAP. Van den Broeck et al. (202T) Arenas et al. (2021) provide intractability results for observational SHAP in a variety of simple distributional assumptions on the data and simple predictors f. This line of research on observational SHAP has been extended in subsequent work, which provides computational theoretical results on the hardness of computing observational SHAP values for various classes of predictors and data distribution assumptions. [Huang The definition of SHAP the original work of [Lundberg and Lee| [017] has also lead to many attempts to approximate observational SHAP values [Lundberg
al. 2024 Marzouk et al. 2024 2025).
al. 2020,, Covert and Lee 2020 Aas et al., 2021 Kwon al. 2021, Sundararajan and Najmi
2020]. It is interesting to note that the version of "Kernel"-SHann
in Lundberg and Lee [2017] also
an approximation for observational SHAP values that ends up coinciding precisely with interventional SHAP values, which explains lot of the confusion in the community, Janzing et al. (2000) boldly claims that researchers should stop the pursuit of approximations to "observation" SHAP values as lacks certain properties, for example, sensitivity i.e. the SHAP value of a feature can be non-zero while the predictor f has no dependence on that feature. This phenomenon happens because when features are correlated, the presence of feature can provide information about other features that the predictor does depend on. This does not happen in interventional SHAP. Finally, [Cenn et al. [2020) argues that both SHAP definitions framework provides explanations that are more "true to the model", and the observational approach's 's explanations more "true to the data".
Finally/CChen
worthy of pursuit. They emphasize that the interventional
B
Proofs
Before we start with the proofs we review the Fourier analysis and synthesis equations. As we mentioned in the Background Section 2 the Fourier representation of the pseudo-boolean function h: 10. + R is the unique expansion of l as follows:
Mxx)
Σ (())(1))(51))
2
fE(0.1)"
This is the so called Fourier "synthesis" equation.
The Fourier coefficients Ti(f) are computed by the Fourier "analysis" equation:
To(f)
Σ
(x))(-1)(fa)
(6)
v 2
=E(0,11
B.1 Proof of propositions
We can now prove Proposition
Proposition Assume h : (0, 13" - TR can be decomposed as follows: h((x)) = Σ (1ss)),, S
==1
[n]. That is, each function hy {0, 13.1515: + R depends on at most [S,] variables. Then, h is
=00 0 E --s.are and of degree max([Si).....) 1Sp1). (Proof in Appendix B.1
24

---

Proof. Let {0, 1 + R be function dependent on exactly d variables ......., Fig. where "1...., La E [n] are distinct indices. We show that for any frequency f {0. 1)" if f, for some
j _ fi1,.... id). then, g(f) = 0. From the Fourier analysis Equation we have:
((f) 1
Σ
g(z) (-
E
E
g(z)(-1) (-I)Vnn===nna)
TCiES 23 JJENNN
Σ
g(x)(-1)(ssm))
Σ
(-1)
Σ
g-z)
(s .0=
PREES
ZyUE(N)NS
Where Equation Woolds because g is only dependent on the variables in S and Equation holds by checking the inner sum has equal number of 1 and - added together.
The proof of the proposition follows by the linearity of the Fourier transform.
Moving on to Proposition 2
Proposition 2. Let, h : 10, R be pseudo-boolean function and let E N be constant (W.r.. n). If h is of degree d, then, it is k O(nd) (Proof in Appendix B.
Proof. We simply note that the number of frequencies f {0, 13" of degree at most is equal to Σ ( This sum is (nd) for d constant w.r.t Tt.
B.2 Proof of Lemma 1
Proof.
We start from Equation
3
[S] |8| 1)!
Σ
(-I))
(1 ((-)))
n!
D
SC(MNN
(M.N)ED
1
Σ
Σ
IS|I(n - |S| 1)!
(o ( (-1)5ims)
D
(Z.))ED SC
By checking all 8 possible combinations of x4 2; E {0, (-1) 2f( 2²). This is simply because the two exponents only differ when f. 1 and x4 * 2
that (-1)fiR?
To determine (-1) (f St (eger we partition [m] \ {i} into two subsets A (j E [m]]ar + J * i, }} and A [n] \ (i)) Doing this, we can factor out (-1)1f-.2-d) and determine the of the sign based the number of indices in S where and x: disagree and fa 1. This is equal to s|:
2 D
S - |S| 1)! (-1)lans)
Σ (x, 1-))))
(x.W)ED
A and B partition
[n]
{i), therefore split the inner sum as follows:
2f
(L Mn ((A) [B) 1)! (-1)
8 v
Σ ((-x))(--)) -11= (1-
ΣΣ
[D]
n!!
(D.
BCB AÇA
Since the inner expression only depends on the cardinalities of Á and B we can recast the inner sum to be over numbers instead of subsets by counting the number times each cardinality appears in the summation:
2
22
|A|-1
IA
A - 1 1)
[A
(a + b)((n - a b 1)! (-1)a
Σ
(x. x (1)
n
D
b
n!
(a.))ED
6=0
0=0
2 [D]
||| -1
(lAl)
n
n 1A1-1
(xi x -1
Σ
(-1)a
Σ
b
(7)
(x.y)ED
a=0
1=0
n
b+b
25

---

Now we find closed-form expression for the innermost summation in the above Equation, which is a summation over b where a fixed:
|A|-1
(1A))
8
[A|
-1
(121) (n- ("-1Al-11
1) (12))
b
6=0 n
(iAI)
("-12)11)
6=0
T
|Ai-s
|4|
a + b)
nn b - 1 |A| a
n2 (==1)
[Al
b=0
(
n
1
|AA + 1
1
(8)
| +1
In Equation i we use the following identity: (w+1) (atth) ("TAp--)) = ( This can be checked algebraically by simply writing down each binomial term as factorials and doing the cancellations:
n
+ b) a
n a
|A|-6 -a) -b-1)
a + b)
(n 1)!
(a + 6)!
(n a 1)!
(a + b)((n
a - 1)!
a!b!
([ - a) a)
(|A] - a))!
(n 1)!
albi(IA] a)l(n - |A| - 1)!
(n 1)!
AA
(n |A| - 1)!
[All(n
|A| 1}1 a!([A] -a)!
bl(n A 1 b)
n |
[|A]
IA| -
In Equation ii use Σb=0 - (atbl) ( [a]-a = (1^4+a) which holds because of the following double-counting argument. The term (14(+1) counts the number of ways to choose subset of size |A| + +1 from set of elements. Imagine elements are numbered from
n, and T1 < T2 <
< A|+++ E [n] represent |A| + 1 chosen elements. Let's condition on Ma+1 = (a + b + 1) where
possible values for b can only be 0 < b < |A| 1. This is due to the fact that Ta-1 < + 1 implies Ti...., Ta are chosen from less than elements, and similarly 7a+1 > n - |A| + a implies Ta. T||++1 ([A) chosen elements) are chosen from less than |A| - elements, which are both impossible. Given the condition, a elements numbered lower than (a + 6 1) and |A| - elements numbered larger than (a (a+bb+t 1) are also chosen. This is possible in (0=+)) (" ("TA-b-) ways. b-
Therefore, keeping in mind that is fixed, Σx (o+h) (" ("TA---)) should give the number of ways to choose subset of size |A| + 1 from set of n elements, through the new perspective.
Based on Equation g we see that the innermost summation in Equation is only dependent on |A]. Thus, we rewrite Equation as follows:
2
Σ
(a.
-===))(- (I4) + 1)
mod?
D
A +1
(o.))D
By absorbing the sign of (r: - x;) into the (-1)(f- term we arrive at Equation
2
12 (-1)(1a)) (IA) + 1)
mod? 2
[D]
A +1
(z.0)ED
26

---

B.3 Proof of Theorem 2
Proof. Proof of Equation 5 simply follows from the fact that SHAP values are linear w.r.. the explained function. Regarding the computational complexity we restate Equation
of
2
Σ
MV) fi Σ
12 (-1)(fa) (1A + 1)
mod 2
D
A +
fESupp(h)
(2,9)E
where A - {j [n][æ, + 23.3 i, = 1}.
We first do a pre-processing step for amortizing the cost of computing |A]: we compute À {j [n|] A zj, Jj- 1} which takes ( n) flops.
We assume values for all E [n] at the same time. Going back to the inner summation above, computing A (and AA) for different values of E [n] is (()) if we utilize the pre-computed Å. The inner product (fxx) not dependent Therefore, the inner expression of the summand takes (n) flops for fixed data-point 'D and f E supp(h).
computing the whole vector & ( ( 4h)), that is
compute SHAP
and is ((n) flops. Computing 1 1x; for different values of [n] is (n).
Computing the inner sum for any fixed frequency f E supp(h) is (n)[D), because are summing over (D) vectors each of size n (the vector which holds SHAP value for each i [ni).. Moving on to the outer each evaluation of the inner sum is (n)[D) and it results in vector of size (one element for each SHAP value). The multiplication of h(f) fi is (n)). Therefore the cost of the inner sum dominates i.e. (n([D). Since we are summing over the whole support the total number of flops (n][D[k) where |supp(h)]
C Datasets
We list all the datasets used in the Experiments Section 5
Entacmaea quadricolor fluorescent protein. (Entacmaea) Poelwijk et al. (2019) study the fluorescence brightness of all 2 distinct variants of the Entacmaca quadricolor fluorescent protein, mutated at 13 different sites.
GPU kernel performance (SGEMM). Nugteren and Codreanu 2015 measures the running time matrix product using a parameterizable SGEMM GPU kemne,, configured with different parameter combinations. The input has 14 categorical features. After one-hot encoding the dataset is 40-dimensional.
Immunoglobulin-binddee domain of protein G (GB1). Wu al. [0066] study the "fitness" of variants of protein GB1, that are mutated at four different sites. Fitness, in this work, a quantitative measure of the stability and functionality of protein variant. Given the 20 possible amino acids at each site, they report the fitness for 20 = 160, 000 possible variants, which we represent with one-hot encoded 80-dimensional binary vectors.
Green fluorescent protein from Aequorea victoria (avGFP), Sarkisyan et al. 2016 estimate the fluorescence brightness of random mutations the green fluorescent protein sequence of Aequorea victoria (avGFP) at 236 amino acid sites. We transform the amino acid features into binary features indicating the absence presence of mutation at each amino acid site. This converts the original 54, 024 distinct amino acid sequences of length 236 into 49, 089 236-dimensional binary data points.
D FourierShap Implementation
implemented four versions of our algorithm, i.e., Equation 5 using Google JAX library (Bradbury et al. 2018 JAX provides flexible framework for developing high-performace functions for vectorized computations. JAX enables automatic performance optimisation of algebraic computation well as just-in-time (JIT) compilation of the vectorized functions for faster iterations runtime.
27

---

The full code base is provided as supplementary material to the paper. We refer the reader there for more details. Here we give a high level overview of the four versions we implemented and experimented with:
Base: In this version, frequencies are represented as n-dimensonal binary vectors. A simple implenctation provided for computing the SHAP values given a single frequency, single background instance, and a single query instance. This is next extended to multiple frequencies, multiple background instances, and multiple query instances using multiple JAX vmaps.
This version is modified version of the Base version. We take closer look at Equation S and pre-compute terms dependent only on frequencies f and background dataset points x (not including terms dependent on the query point z*). These are then loaded from memory at oun-time. This version was faster than Base in all of our experiments, but inherently requires more memory; in our case, more GPU memory.
Precompute:
Here we utilize the sparsity of frequencies f E (0, 1)" R i.e. the fact that frequencies have mostly zero entries in practice. In this version, for each frequency f. we focus on positions i where fi = 1. Inspecting Equation these are the only positions where f can affect the final SHAP value vector.
Sparse:
Positional: This version brings again builds on the previous and computes SHAP values separately for each coordinate [n]. This adds extra precomputation step map frequencies to coordinates they affect, but enables mathematical simplifications as well as potential for extra vectorization. We observed that although this extra precomputation step could become time-consuming for large set of frequencies, it can result in a significantly faster SHAP value computation at run-time in the case of low-degree Fourier spectrums, compared to the Sparse version.
E
Experiment Details
The code for running the experiments and the implementations all modules are open-sourced and We run all experiments
publicly available at https: // gi thub. com/ on machine with one NVIDIA GeForce RTX 4090 GPU, on servers with Intel(R) Xeon(R) CPU E3-12841 v4 @ 2.90GHz, restricting the memory/RAM to 20 GB, which was managed with Slurm.
E.1 Black-box
For the Entacmaea and SGEMM datasets, train fully connected neural networks with 3 hidden layers containing 300 neurons each. The network is trained using the means-squared loss and ADAM optimizer with learning rate of 0.01. For GBI train ensembles of trees models of varying depths using the random forest algorithm using the sklearn library [Pedregosa et al.) 201 For GvGFP we train again, ensembles of trees models with 10 trees of varying depths using the cat-boost algorithm/librrry (Dorogush et al. 2018 All other setting are set to the default in both cases. Model accuracy for different depths are plotted in Figure
Accuracy Random forest model on GB1 va depth
Accuraty Catboust model on avGFP vs depth
0.45
0.45
depth
0.30
0.30
0.25
0.25
4
5
12
Figure 4: Model accuracy of tree models evaluated on the test set for different depths
28

---

For each dataset, we use all possible combination of number of background samples and query instances (instances be explained) from {10, 20, 30, 40), resulting in total of 16 runs per dataset. Error bars in Figure 2 capture the variation in speedups.
E.1.1 FourierSHAP
For the first step of the FOURTERSHAP, i.e., computing sparse Fourier approximation of the black-box model, a.k.a Fourier transform algorithm [Amrollahi et al., 2019] for each of the four trained models. The implementation is done using Google JAX [Bradbury al. 2018 library as part of this work, and available in the project repository.
implementation of sparse Walsh-Hadamart Transform (sparse WHT)
For the second step of FOURIERSHAP, i.e., utilizing the approximated Fourier spectrum to compute SHAP values as per Equation 5 we use our "Precompute" implementation. We discussed the details in the previous Section, Section D
To showcase the flexibility of our method controlling the trade-off between speed and accuracy in Figure we prune the computed sparse Fourier spectrum in the first step, and remove frequencies with amplitudes smaller than a specific threshold from the spectrum. For the threshold, we use 10 values between 0.0001 and 0.05 and specified minimal descriptive subset of them points in Figure
E.1.2 KernelShap
use the standard library provided by the writers the paper (Lundberg and Lee 2017 with its default settings. As part of the default setting, the paired sampling trick is also enabled, which shown be beneficial for faster convergence of KERNELSHAP. KERNELSHIAP is written in C and is to our knowledge the fastest implementation of this algorithm.
For KERNELSHAA
To ensure fair comparison, Entacmaea and SGEMM datasets.
models GPU wherever possible, i.e., for Neural Networks
To emphasize the practical significance of speedups of FOURIERSHAP over SHAP we report the absolute runtimes of KERNELSHAP (in seconds) in our experiment on the SGEMM dataset in Table The runtimes correspond to the setting used in the main text, where background sizes were kept relatively small. This decision was made intentionally; during experimentation, we observed that larger background sizes caused LINREGSHAP and KERNELSI SHAP to become prohibitively slow, making it impractical to include full-scale results across datasets and seeds. Despite this limitation, method already achieved orders-or offers-o-nmme ofgmatit speedups.
Query Size
Background Size
10
20
30
40
10
2.0 s
3.9
5.6
7.8
20
2.9 s
5,8
8.7
11.7 s
30
3.9
7.5
11.0s
14.4
40
4.9
9.6
14.0
17.9
Table 1: KERNELSHAP runtimes seconds in our experiment on the SGEMM dataset across varying sizes of the query and background sets.
To further emphasize the practical gains of FOURIERSHAP, conducted additional experiments with significantly larger query and background sets, closer to what might be used in real-world deployments. Table reports the runtimes in this setting. Despite the background dataset still being modest in size (100-400), KERNELSHAP runtimes quickly increase to minutes, while FOURIER- SHAP continues run in milliseconds. These results reinforce that reported relative speedups (often 100x-10,000x)) translate into meaningful real-world runtime improvements.
httpss//ggthabb.co///uubbbbrrrr
29

---

Query Size // Background Size
100
200
300
400
100
35 5
71 5
104
133 $
200
43
84
129
169 5
300
52 $
107
161 S
212 $
400
69
132
197
265
(a) KERNEL runtimes (in seconds)
Query Size ! Background Size
100
200
300
400
100
14 ms
28 ms
43 ms
57 ms
200
29 ms
58
86 ms
110 ms
300
40 ms
79 ms
119 ms
159 ms
400
53 ms
106
160
213 ms
(b) FOURIERSHAP runtimes (in milliscconds)
Table 2: KERNELSHAP runtimes vs. FOURIERSHA runtimes across significantly larger sizes of the query and background sets than the setting used in the experiment on the SGEMM dataset.
E.1.3 Fast-SHAP
We tried best capture the full potential of FASTSHAP in predicting SHAP values in terms of speed and accuracy, to ensure a practical and grounded comparison to our method. Here are the details training Fast-SHAP baseline for computing interventional SHAP values:
Imputer: "Imputer" is FastSHAP module used in the computation of neural networks' loss, acting as the value function in SHAP formula, that generates model's prediction using strategy for treating features excluded in the subset, given the predictor and subset features. To compute interventional SHAP values, we use Marginal Imputer. implemented in the original FastSHAP repo, which computes mean predictions when using the backgorund dataset's values for excluded features. Therefore, each trained FAstSHAP fixed background dataset, as the Imputer used in its loss is. In
model is specific experiments, we use four different background datasets with multiple sizes per (real-world) dataset, which lead to training four FastSHAP models per setting.
Feature Subset Sampling: We train FastSHAP models with 1, 4, and 16 feature subset samples per input. Although did not observe monotonie improvements by increasing the number of feature subset samples, we decided to use the models trained with 16 samples per input compare method with, it was mostly performing the best in terms of accuracy.
We enable paired sampling in FastSHAP, which is a trick to pair each feature subset sample E (0. 1) with its complement
Paired Sampling:
that is shown to be beneficial in reducing the variance and improving the accuracy, in both KernelSHAP and FastSHAP.
Neural Network Architectures: We use MLPs with three different sizes to train FastSHAP, and reported the results for each separately:
Small (2-layer): in x 128 out.
Medium (4-layer): in X 128 x 128 X 128 X out.
Large (6-layer): in x 128 128 128 x 128 x 128 x oul.
We use ReLU as the activation function in all models.
Hyperparameters: We the training batch size of 64 and FastSHAP's defaults for all other components and hyper--aramen parameters. We train each model with early stopping and up to 200 epochs.
Table shows the time required to train the FASTSHAP models used in our black-box experi- ments. Both SOUR (ours) and FASTSHAP are amortized methods that have a heavier "pre-computation" step. For FASTSHAP this pre-computation appears as training an MLP that directly
30

---

predicts SHAP values and for us this appears as computing Fourier transform. When compar-
ing FASTSHAP's initial training time ours (reported in Figure DT. we can see our method has considerably lower pre-computation time.
Training time (m)
Black-box model
FastSHAP size
Total training time (m)
Dataset
for background dataset size
10
20
30
40
Small Medium
5
18
46
Entacmaea
MLP
2
4
10
22
Large
3
11
31
Small
47
130
249
173
599
SGEMM
MLP
Medium
55
52
162
128
397
Large
72
73
152
91
388
Small Medium
114
148
42
173
477
Random Forest (depth=5)
GBI
83
207
130
475
Large
54
102
155
184
495
Small
24
28
36
39
127
Catboost
avGFP
Medium
35
58
41
62
196
(depth=5)
Large
11
20
25
78
Table 3:
Training times of FASTSHAP models used in our black-box experiments (in minutes).
Unlike FOURIERSHAP (ours), FASTSHAP needs to be separately trained for each background dataset. Part of the difference in the training times are due to the variance in the number of training
epochs before the early stopping occurs. Original datasets are also of varying sizes that lead to different number of training samples per epoch.
E.1.4 LinRegShap
LINREGSHAP, is variance-reduced version of KERNELSHAP Covert and Lee use the implementation of the original writers"] Their implementation includes automatic detection of the convergence of stochastic sampling which is meant to speed up the algorithm by taking less samples from the black box. Furthermore, as per the default setting, we also allowed paired sampling.
2020
We again
To ensure fair comparison,
models GPU wherever possible, i.e., for Neural Networks Entacmaea and SGEMM datasets.
E.1.5 DiepLift
For DeepLift we as well use the library of Lundberg and Lee 2017 with default settings. In this setting the neural network passed to the algorithm on a GPU to make sure this algorithm as fast possible.
E.2
Trees
We fit random forests of maximum depths ranging from 3 8 with 20 estimators 90% of all four datasets used in the black-box setting. We compare performance of four algorithms in computing SHAP values for these random forest models; the classic TREESHAP as well as its GPU implementation 5 FASTTREESHAP and our FOURIERSHAP. We always use 100 datapoints as the background data samples, and 100 datapoints to explain and compute the SHAP values for. We report the speedup of each algorithm over classic TREESHAP in Figure 3 with error bars showing the standard deviation in speedup over five independent runs.
httpe///gthhbb.co///uuudeeg/////
31

---

Comparison of SHAP Values Neural Network on Entacmea
SHAP
Four (ours)
Ground Truth foriginal SHAP fomulas]
1.00
075
2.50
-025
-:00
with Aet
0.00
23
-1.00
Figure 5: From left to right, 1- SHAP values generated by KERNELSHAP, 2- SHAP values generated by FourierSHAP (ours), 3- and the ground truth SHAP values computed by the original exponential SHAP formula Equatior[] on the Entacmaea dataset. In 3, Computation of ground truth SHAP values using the exponential formula is possible due to the dataset containing all 2 possible boolean feature vectors. 10 query points and background dataset points are chosen at random and of size 10. This figure shows that both KernelSHAP and our method compute exact ground truth SHAP values.
For the first step of the FOURIERSHAP, we derive the exact sparse Fourier representation from the ensemble of trees, accessing the tree structures and using Equation 2 We also perform a pruning on the exact sparse Fourier representation derived from the ensemble of trees, and keep the frequencies with largest amplitudes that cover at least 99.95% of the original Fourier spectrum's 's energy. We also make sure to only remove frequencies with apmlitudes smaller than 0.005.
To run FOURIERSHAP,
use our "Precompute" implementation for Entacmaea, and "Positional" version for other datasets, given larger feature spaces and the low-degreeness of the spectrum as result of bounded maximum depth. See Section D for implementation details. We compare the resulted SHAP values with TREESHAP results and achieve R. of at least 0.99, ensuring precise values computed by FOURIERSHAP.
E.3 Using KernelShap to produce ground truth SHAP values
As mentioned before, in order to measure the accuracy of the SHAP values produced by our and other algorithms we need ground truth SHAP values. We use KERNELSHAP to this extent. KERNELSHAP an approximation method for computing interventional SHAP values. This approximation becomes more precise by sampling more coalition subsets. Therefore, to generate ground truth values, for each dataset, we sample more and more and check for convergence in these values.
In order to check KERNELSHAAP values have converged to ground truth interventional SHAP values, we update the number of subset samples KERNELSHAP uses to generate SHAP values for each instance. Looking into KERNEL repo this is the default number of samples in the code:
self. nsamples = 2 * self.N + 2++11
Here, self M is the number of indices where the instance is different from the background dataset.
To understand the convergence dynamics of FERNELSHAP. we multiply this number by multiple "sample factor"s and run the algorithm. This allows us to experiment with the number of subsets sam- pled, and find a sample factor that ensures convergence while avoiding unnecessary extra computation. We test sample factors in the set {0.02, 0.03, 0.04, 0.1, 1.0, 2.0, 10.0).
For instance, for GB1 dataset, we compute the R²2 score of the KERNEL SHAP values with different sample factors to sample factor 10 (as the ground truth). For this dataset, the default setting, i.e., sample factor 1, seems good enough to make sure we are producing ground truth values and that the algorithm has converged. This is the general procedure we use for all datasets.
32

---

Sample Factor
Runtime
Rd w.r.t Ground Truth
0.02
4.031
0.902
0.03
4.274
0,934
0.04
4.530
0.967
0.1
5.399
0,991
1.0
19.452
0.999
2.0
34.451
1.0
10.0
160.251
1.0 (R² w.r. itself trivially=1)
Table 4: Table of sample factor, runtime, and R with respect to sample factor 10, GB1 dataset.
F Limitations & Future Work
F11 Extending to continuous features
A limitation of FOURIERSHAP is that it currently does not natively support continuous features and they have to be handled by quantization into categorical features. However, there is value in computing efficient SHAP values for models with continuous features and this is an important potential future work. In the following, we discuss how we think such an extension would work for the two classes of models we extensively covered in this work, namely trees and MLPs.
Trees in the white-box setting. Trees can be seen as inherently discrete structures even though they perfectly work for continuous features. By setting threshold, i.e., a continuous number to define split of the node, all trees are inherently in fact binary. This way of thinking gives one very simple but crude extension of the current framework: To assign to each node of the tree binary feature specifying whether a certain continuous feature is bigger or smaller than its threshold. This would increase the feature dimension of the problem to the number of nodes in the tree in the worst case scenario. With the careful design the transformation of continuous features into node-based binary features, this could be potential extension for which the current work can lay a foundation.
second and more principled and less crude way to think about the case of trees is to not use Fourier transform that we are using now which is over Zg x Ze X ...Zg (n times where n is the number of features). But rather use a transform over ZK. x, Zk, where K; is the number of distinct thresholds feature i has in the tree. Coming up with a closed form solution for the SHAP values in this Fourier basis is an interesting question that we also plan to look at. It is not too far far-fetched to think that we can also find closed form solution to this discrete Fourier basis. This would perfectly handle the case of any tree, Note that by a recursive formula one can readily compute the Fourier transform of trees well.
MLPs. Regarding the case of MLPs with continuous input features, one can not simply resort to the discrete Fourier transform of type Zy x Za to perfectly capture this structure as it is no longer inherently discrete (like trees). This is a slightly tricky scenario because it requires us to characterize the relationship of continuous and discrete Fourier transforms of neural networks functions. In classical signal processing there are results which characterize what level of granularity in discretization is required to reconstruct continuous transform with the discrete one for a given level of error. These results depend on the Spectrum of the continuous transform. For example the case of super imposition of sinusoids, where the spectrum has bounded domain give rise to the Nyquist rate etc.
For Neural network functions, if one had clear theoretical results on the spectral behavior of con- tinuous transforms of neural networks it is not too hard come up with conditions on the level of quantization required for the discrete transform to approximate them. One result that computes the spectrum appears over multi dimensional inputs is (Theorem oa'ama et al. (2019] but we are not aware of any spectral bias bounds on the continuous spectrum derived from this equation. However, for Neural networks with single input dimension, bounds have been derived on the spec- trum Cao et al. (2019) (in addition to the empirical results of Rahaman et al. (2019). This intuitively means that single input Neural networks provably have tendency to approximate functions with lower frequency sinusoids in the continuous domain. This implies that a discrete Fourier transform over Zx can approximate these function correctly for sufficiently large discretization parameter K. This gives hope that empirically discrete Fourier transform of type ZK x Zk for sufficiently
33

---

large K would also approximate neural network function with higher dimensional inputs for large enough discretization parameter Therefore, an extension of our flosed-form solution for SHAP to Z x 7 transform could be potential direction for the future work.
F.2 Conditional SHAP values
Another direction for future work extending this work compute conditional SHAP values. In this work, we only cover interventional SHAP values (the difference of interventional and conditional SHAP versions is discussed in detail Appendix A..3).
In model-based methods like TREESHAP Lundberg et al. 2020). one can use the tree itself to approximate conditional distributions of the data in tractable way. One idea for extending this
work is to attempt to tractably find a representation the conditional distribution of the data using a sparse Fourier approximation of the predictor. Next, computing conditional SHAP Values using this conditional approximation.
34


Reviews:
[{"review_id": "dDyWfPZStM", "reviewer": "Reviewer_4ytr", "summary": "The paper \"SHAP Values via Sparse Fourier Representation\" introduces FOURIERSHAP, a two-stage algorithm for efficiently computing SHAP values by leveraging the observation that many real-world models—especially neural networks and tree ensembles—exhibit spectral sparsity and can be approximated by sparse low-degree Fourier representations. In the first stage, the method approximates the black-box model using a sparse Fourier transform. In the second stage, it derives a closed-form, exact expression for the SHAP values of each Fourier basis function, avoiding the exponential summation over coalitions and enabling highly parallelizable, amortized computations. This approach results in orders-of-magnitude speedups over existing SHAP methods (including KERNELSHAP and FASTSHAP).", "questions": "Why did you refer to the method as FourierSHAP and not FourierShapley?", "limitations": "See above.", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 1, "significance": 1, "originality": 1, "strengths_and_weaknesses": "The paper touches upon a computationally challenging problem of computing exact Shapley values, whose complexity grows exponentially with the number of features. The fact that the method can compute the exact Shapley value is the main strength of the paper. \n\nAlthough the paper seems a bit difficult to follow, FOURIERSHAP seems to approximate the trained model under explanation with a global, structured surrogate in the Fourier domain, enabling exact SHAP value computation without exponential cost. So, in principle, the authors put forward a global surrogate model that can approximate the trained model and able to compute Shapley values in closed form. Thus, the paper, IMHO, should be shared about providing a global surrogate model with Shapley value computation capability, not an approximation of the Shapley value itself for different models. As a result, the method is not comparable with amortizedSHAP (like FastSHAP which is studied in length in the paper). \n\nBased on this inception, the paper should discuss and study how this global surrogate model can approximate the functions, e.g., is it a universal approximation?  This approximation power would provide some perspective on how well the approximated Shapley values are, when the original model is replaced by the proposed surrogate model.\n\nIn the same line, the authors should discuss why this global surrogate model is preferred over TreeSHAP for instance, where we can compute the exact Shapley value. The current version of FourierSHAP seems to be focused on tabular data, and ensemble trees are the SOTA on tabular data, and we are able to compute exact Shapley values as well very efficiently. TreeSHAP is just an example, and there are a few other models that are capable of computing exact Shapley values.  \n\nThat being said, the authors ironically approximate the decision trees to apply FourierSHAP; why not using TreeSHAP?\n\nLast but not least, I did not why the authors use the term SHAP and FourierSHAP, while they try to approximate the Shapley value itself. So, I think the right terminology here is to use Shapley value and term the method as FourierShapley.", "was_revised": true, "final_justification": "positioning of the paper as a method and wrt to the literature", "rebuttal": "We thank the reviewer for their time and for thoughtful participation in our work. We appreciate the recognition of our method’s ability to compute exact SHAP values with orders-of-magnitude speedup through a sparse Fourier representation. Below are our responses to the concerns raised by the reviewer.\n\n**Positioning of FourierSHAP vs. FastSHAP:** We thank the reviewer for pointing out this distinction. While FastSHAP amortizes the computation of SHAP values by learning a model that maps input features directly to SHAP values, it does so by implicitly learning both the surrogate and the SHAP estimator end-to-end. Therefore, errors in the final SHAP values can arise jointly from the model approximation and also SHAP estimation.\n\nIn contrast, FourierSHAP decouples these steps: we first approximate the original predictive model using a global sparse Fourier surrogate, and then compute the exact SHAP values of this surrogate. This separation allows us to provide theoretical guarantees and also fine-grained control of the surrogate approximation quality through the sparsity parameter.\n\nAlthough different in structure, both methods aim to accelerate SHAP computation by orders of magnitude. Hence, we considered FastSHAP a relevant baseline for the empirical comparison. Moreover, we consider our method *amortized*, because the expensive training of the surrogate is done once and future evaluation of the SHAP value is, similar to FastSHAP, very fast. To re-iterate, we say the method is amortized because the upfront cost of training an expensive surrogate is done once and this cost is amortized over the large number of subsequent shap value predictions that are computationally extremely cheap. \n\n**Expressiveness of Surrogate Model:** This is indeed an important point. We discuss this in Section 3.2 for the case of ensemble of tress and in Proposition 1 for the more general case of functions that can be decomposed as a sum of low order functions. For these classes of functions, the Fourier representation is exact, therefore we incur no approximation error in the SHAP values.\n\nIn addition to the points above, we also have a discussion in Section 3.1 on why our method can approximate MLP functions as well, and furthermore provided empirical experiments ourselves in Section 5, validating the approximation capabilities. Finally, in Appendix A.2 we have discussed the type of guarantees available for the surrogate function when approximating a generic black box. These are uniform bounds that bound the L2 norm of the error based on the spectrum of the function.\n\n**Positioning of FourierSHAP vs. TreeSHAP:** We appreciate the reviewer raising this important point. Indeed, TreeSHAP allows exact SHAP computation for decision trees and is highly efficient. However, its applicability is limited to tree-based models.\n\nFourierSHAP, in contrast, is model-agnostic and furthermore captures a broader class of functions. As mentioned above as well as in Section 3.2 and Proposition 1, trees and, more generally, low-order functions admit exact sparse Fourier representations. Therefore, FourierSHAP provides exact SHAP computation capability for the case of these models. Indeed, as shown in Figure 3, for decision trees, our method reproduces TreeSHAP outputs exactly but with order-of-magnitude speedups. Therefore, not only is our method exact for trees, it is also applicable to a broader class of models, and it is more computationally efficient. We believe this makes our method a better alternative for computing SHAP values.\n\n**Unnecessary Approximation of Trees:** We would like to clarify that we did not approximate decision trees. We computed its Fourier transform exactly. The theory is detailed in Section 3.2. Thus, the surrogate is an exact representation, and the SHAP values derived from it are identical to those produced by TreeSHAP (see our response above to previous two concerns). \n\n**Naming of the Method:** We appreciate the reviewer’s point and agree that terminology should be used carefully to avoid confusion. While Shapley values are rooted in cooperative game theory, the term SHAP values has become the standard when referring to their adaptation for feature attribution in machine learning models, as popularized by Lundberg and Lee [1]. We believe FourierSHAP is consistent with names in existing literature (e.g., KernelSHAP, TreeSHAP). We have addressed how feature attribution is related to cooperative games in Section 2.1.\n\nIn summary, our method enables efficient SHAP value computation by approximating the original model with a global Fourier surrogate. This approximation is exact for common classes such as ensembles of trees and other black-blox low-degree functions.\nThe novelty lies in the closed-form SHAP computation in the Fourier basis, which, under sparsity assumptions, provides exact values and substantial computational gains. While the method can involve approximation of the underlying predictor, our focus is squarely on the accuracy and efficiency in the computation of the SHAP values themselves.\n\nWe hope that our detailed responses have addressed your concerns and clarified the contributions and scope of our work. If there are any remaining questions or further points to discuss, we would appreciate additional feedback otherwise we kindly ask you to please consider increasing your score.\n\n[1] Lundberg, Scott M., and Su-In Lee. \"A unified approach to interpreting model predictions.\" Advances in neural information processing systems 30 (2017)."}, {"review_id": "hCzprxbVXU", "reviewer": "Reviewer_pDrB", "summary": "This paper introduces FOURIERSHAP, a novel two-stage algorithm for efficiently computing SHAP values for models with discrete or binary inputs. The core contribution is to first approximate a model using a sparse Fourier representation and then apply a newly derived closed-form formula that approximates SHAP values via a simple, parallelizable summation, bypassing the traditional method's exponential complexity. The authors demonstrate that this approach provides significant speedups over existing baselines while maintaining strong accuracy.", "questions": "N/A", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths\n* S1. The approach using Boolean Fourier analysis is theoretically novel and exciting.\n\n* S2. The experimental validation is strong, with impressive and practical speedups.\n\n## Weaknesses\n* W1. The method is fundamentally designed for discrete inputs. However, the authors do suggest quantization as a workaround.\n\n* W2. The method's effectiveness relies on the assumption of spectral sparsity. While the authors justify this for some models, it may not hold universally.\n\n* W3. The justification for spectral bias in Section 3.1, which relies on the NTK, is not fully convincing. The author's arguments implicitly invoke the lazy regime, whereas there is now considerable work on more realistic \"rich regimes\". The motivation would be stronger with either more robust theoretical citations or direct empirical evidence of the claimed spectral sparsity.", "was_revised": true, "final_justification": "In light of the new concerns raised, I have slightly decreased my score and confidence", "rebuttal": "We are grateful for the positive and thoughtful assessment and happy to see that the reviewer finds our work both theoretically exciting and also having a strong experimental validation with significant speedups. We also acknowledge the weaknesses mentioned by the reviewer and discuss them below.\n\n**W1 - Discrete Input Assumption:** We appreciate the reviewer drawing attention to the limitation of our method to discrete inputs, which is a key point we discuss in Appendix F.1 of the paper. There, we discuss possible extensions for this purpose such as quantization. The challenge lies in the trade-off between discretization granularity and computational cost. Since the dimensionality increases with finer quantization, this has non-trivial impact on runtime and approximation error. A true and general extension to continuous features (potentially involving new surrogate representations), remains an open and important direction for future work. We believe this requires a careful theoretical and empirical treatment.\n\nWe focus the scope of our work to discrete features, for which we have provided theoretical guarantees and empirical validation. We think even for the discrete setting, our work proposes a SOTA method for computing accurate SHAP values efficiently and therefore makes for a strong algorithmic contribution.\n\n**W2 - Spectral Sparsity Assumption:** As the reviewer has thoughtfully pointed out the assumption of spectral sparsity is central to our method, and while it is theoretically and empirically supported for many real-world models (such as those presented in the paper), it is not always guaranteed. We have tried to be clear about this limitation and explained the scope of applicability in Section 3. Namely, we provided guarantees for the case of trees (Section 3.1), low-order functions (Proposition 1), MLPs (Section 3.2), and generic functions (Appendix A.2). \n\nWe also attempt to offer a broader intuitive argument in this rebuttal. Functions that only contain low-order interactions have a sparse Fourier spectrum by Proposition 2. We think low-order interactions is a useful inductive bias for models that can generalize well, especially when trained on limited data.\n\n**W3 - Limitations of NTK-based Justification for Spectral Bias:** We thank the reviewer for raising this point. NTK theory was used primarily as a theoretical motivation in the specific context of MLPs. In Sections 3.1 and 4, we also cited empirical works that highlight spectral bias in fully connected neural networks. Additionally, the results shown in Figure 1 reflect this phenomenon in our own empirical studies. \n\nAlthough NTK theory provides useful intuition in the lazy regime, we acknowledge its limitations and welcome deeper integration with insights from richer training regimes. We would be happy to consider incorporating additional references if there are particular works that the reviewer believes would help strengthen the motivation.\n\nWe appreciate the encouraging feedback from the reviewer and are excited to build on this work in future directions."}, {"review_id": "jGy9LRPGBg", "reviewer": "Reviewer_UB9P", "summary": "This paper introduces a novel approach to tackling the computational challenges associated with calculating Shapley Values (SV) for binary input vectors. The authors begin by reviewing the fundamentals of the Discrete Fourier Transform (DFT) applied to binary inputs, and they introduce key concepts such as k-sparsity and degree.\n\nThe authors provide a thoughtful discussion on the likelihood that many real-world prediction functions satisfy the sparsity requirement. They support this claim with educational examples, including modular functions and functions with only pairwise interactions, which effectively illustrate the practical relevance of their assumptions.\n\nBuilding on this foundation, the authors present their main result: surprisingly, the notoriously exponential summation inherent in SV computation can be expressed in a closed form when the input vector is represented in the binary Fourier space. This finding is a significant theoretical advancement.\n\nEmpirically, the authors demonstrate that their proposed method outperforms alternative approaches (FastSHAP, Kernel SHAP, DeepLIFT, and LigRegSHAP) in terms of SHAP value accuracy, further validating the practical utility of their contribution.", "questions": "I may add some later.", "limitations": "The authors need to explain the main limitation upfront: The theory is only for binary vectors.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\nThe authors make a substantial contribution to the field of Explainable AI (XAI) and potentially to game theory as well. To the best of my knowledge, a closed-form solution for SV computation has not been previously established in the game theory literature, which underscores the high originality and novelty of this work.\n\nThe authors also provide a meticulous analysis of sparsity in the Fourier space, grounded in a deep understanding of spectral biases in neural networks. As a machine learning researcher in industry, I concur with their assertion that, in most real-world applications beyond benchmark problems in flagship domains (text, speech, vision, and molecular data), lower-order interactions often dominate the meaningful patterns worth extracting from data.\n\nThe manuscript is generally well-written and accessible. Additionally, the authors demonstrate a strong focus on the computational aspects of their method, leveraging JAX for efficient vectorization and parallelization, which enhances the practical applicability of their approach.\n\n**Weaknesses:**\nWhile the authors excel in explaining the implications of Propositions 1 and 2 with intuitive and straightforward examples, the main results in Section 4 are presented without sufficiently accessible explanations, which detracts from the paper’s readability. As a reviewer, I am providing a positive assessment under the assumption that the proofs are correct. However, if the authors have intentionally omitted detailed explanations to avoid scrutiny, I find this approach concerning and not conducive to transparent scientific discourse.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their assessment. We are pleased that the key strengths of the paper, namely, the theoretical novelty of the closed-form SHAP expression, the principled use of Fourier sparsity, and the empirical demonstration of substantial computational gains, were clearly recognized. We also appreciate the reviewer’s perspective on our contribution to Explainable AI and its potential impact on game theory, as well as the validation of our assumptions on spectral sparsity in real-world models.\n\nRegarding the clarity of Section 4: we fully agree that the presentation is dense. This section introduces the main result, i.e., the closed-form SHAP expression in the Fourier basis, which is mechanically derived and is notationally heavy. The derivation relies on a sequence of algebraic manipulations and combinatorial identities that are correct but offer little in terms of intuition. For this reason, we chose to move the full derivation to Appendix B and keep the main text concise.\n\nHowever, we understand that this may have made the exposition harder to follow, and we will revise this section in the final version to improve accessibility. Specifically, we will include a high-level walkthrough of the key steps of the proof and better guide the reader to the relevant appendix material.\n\nWe also want to reassure the reviewer that we have validated the correctness of the formula both theoretically and empirically. In Figure 5 located in the Appendix, we include experiments comparing our computed SHAP values against ground-truth values (computed via enumeration), which serve as an internal consistency check on the correctness of the formula.\n\nFinally, we agree with the reviewer that the restriction to discrete inputs should be stated more clearly and prominently. Although we already mention this in Section 2.2 and dedicate Appendix F.1 to this topic, we will revise the introduction and abstract to explicitly highlight that the current theory is scoped to discrete features.\n\nWe are grateful for the reviewer’s valuable feedback, which we believe helps us improve the main text even further."}, {"review_id": "V99p8mUnAd", "reviewer": "Reviewer_ihkk", "summary": "The paper introduces FourierSHAP, a novel method to approximate SHAP values for black-box models. First, a sparse Fourier approximation of the black-box is estimated. Then, thanks to a novel fast closed-form expression of SHAP values for Fourier representations of functions, the exact SHAP values (of the Fourier approximation) can be efficiently computed. The proposed method is specific to pseudoboolean functions.\n\nTo validate the FourierSHAP empirically, the authors consider four test cases with only binary or categorical features (transformed through one-hot encoding). For each test case, they first train a preliminary black-box model (MLP or tree ensemble) and compute a baseline with KernelSHAP. They show that FourierSHAP achieves good accuracy while offering several orders of magnitude improvement with respect to KernelSHAP.", "questions": "* As mentioned above, my main issue lies with the generalization to continuous features. Could the authors comment on the expected additional computational burden in such scenario?\n* Instead of reporting only relative improvement with respect to KernelSHAP, would it be possible to report also the running time of KernelSHAP in e.g., the Appendix? From a practical perspective a $10^3$ improvement is only interesting as long as KernelSHAP runs for more than seconds\n* Other sparse representations, given as low-order additive decompositions of multivariate functions, are also popular, and they would also be computationally efficient since they break (to some extent) the exponential complexity. How would the authors position their work with respect to such competitors?", "limitations": "The authors discuss in Appendix F.1 the limitations related to continuous features, and in Appendix F.2 the extension of conditional SHAP values.\n\nI think Appendix F.1 should be expanded to give more practical details on how continuous features can be handled, and also contain at least one such illustration.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "I really enjoy the novelty of the paper, which shows that as long as a sparse Fourier representation is possible for a black-box model, it is possible to heavily reduce the computational burden of SHAP values. \nAs clearly motivated in the introduction, estimation of SHAP values is of great particular interest but usual running times prevent its broad application when the number of features is large. The new approach presented here is a new and promising point of view.\n\nThe paper is well-written and easy to follow, with novel (to the best of my knowledge) theoretical results fo Fourier representation. Sparse Fourier approximations of typical black-model models are validated in Figure 1, which is a very reassuring experiment. The running time improvements illustrated in all test cases are also impressive.\n\nHowever, I have a major concern about the limitation of the method on pseudoboolean functions. Of course categorical features can be transformed through one-hot encoding, and in Appendix F.1 the authors discuss quantization strategies to handle continuous features. To me, it is unfortunately still unclear:\n\n- how the SHAP value of the initial feature is recovered from the SHAP values of the new features after one-hot encoding (this may be trivial, but in this case this should be explicitly mentioned)\n- how running time improvement would change with respect to KernelSHAP used directly on the initial features (e.g., on SGEMM)\n- how continuous feature quantization would be handled in practice, and the impact of the increase in dimension\n\nI really think that the paper would benefit from at least one experiment with continuous feature to be more convincing.", "was_revised": true, "final_justification": "The new sparse Fourier representation introduced in this paper is an interesting new proposal for Shaply value estimation, and the computational speed-up it leads to is in practice impressive. The authors answered my concerns in the rebuttal, and I am convinced by their comments.", "rebuttal": "We sincerely thank the reviewer for the positive and encouraging feedback. We are especially grateful for the recognition of the novelty in using sparse Fourier representations to compute SHAP values efficiently, as well as for the kind words on the clarity of the paper, theoretical contributions, and experimental validation. We also discuss points mentioned by the reviewer below.\n\n**SHAP Values of One-hot Encoded Features:** We used the SHAP values of the individual one-hot components separately for each category and compared them across methods. We will clarify this in the paper to avoid confusion and make our evaluation choices more transparent.\n\n**Generalization to Continuous Features:** As for continuous features, we agree this is an interesting direction for future work. In Appendix F.1, we discuss possible extensions for this purpose such as quantization. The challenge lies in the trade-off between discretization granularity and computational cost. Since the dimensionality increases with finer quantization, this has non-trivial impact on runtime and approximation error. \n\nHowever, while interesting, we focus the scope of our work to discrete features, for which we can also provide theoretical guarantees and empirical validation. We think even for the discrete setting, our work proposes a SOTA method for computing accurate SHAP values efficiently and therefore makes for a strong algorithmic contribution.\n\n**Practical Significance of Speedups over KernelSHAP:** Below we report the absolute runtimes of KernelSHAP (in seconds) on the SGEMM dataset across varying sizes of the query and background sets.\n\nThe first table corresponds to the same settings used in the main paper, where background sizes were kept relatively small. This decision was made intentionally: during experimentation, we observed that larger background sizes caused LinregSHAP and KernelSHAP to become prohibitively slow, making it impractical to include full-scale results across datasets and seeds. Despite this limitation, our method already achieved orders-of-magnitude speedups.\n\n### KernelSHAP Runtime (Main Paper Setup) ###\n| **Query Size ↓ / Background Size →** | **10** | **20** | **30** | **40** |\n|--------------------------------------|--------|--------|--------|--------|\n| **10**                               | 2.0 s | 3.9 s | 5.6 s | 7.8 s |\n| **20**                               | 2.9 s | 5.8 s | 8.7 s | 11.7 s |\n| **30**                               | 3.9 s | 7.5 s | 11 s | 14.4 s |\n| **40**                               | 4.9 s | 9.6 s | 14 s | 17.9 s |\n\nTo further emphasize the practical gains of FourierSHAP, we conducted additional experiments for this rebuttal with significantly larger query and background sets, closer to what might be used in real-world deployments. Despite the background dataset still being modest in size (100–400), KernelSHAP runtimes quickly increase to minutes, while FourierSHAP continues to run in milliseconds.\n\n### KernelSHAP Runtime (Larger Setup) ###\n| **Query Size ↓ / Background Size →** | **100** | **200** | **300** | **400** |\n|------------------------------------------------------|---------|---------|---------|---------|\n| **100**                                              | 35 s    | 71 s    | 104 s   | 133 s   |\n| **200**                                              | 43 s    | 84 s    | 129 s   | 169 s   |\n| **300**                                              | 52 s    | 107 s   | 161 s   | 212 s   |\n| **400**                                              | 69 s    | 132 s   | 197 s   | 265 s   |\n\n### FourierSHAP Runtime (Same Setup, in milliseconds) ###\n| **Query Size ↓ / Background Size →** | **100** | **200** | **300** | **400** |\n|------------------------------------------------------|---------|---------|---------|---------|\n| **100**                                              | 14 ms   | 28 ms   | 43 ms   | 57 ms   |\n| **200**                                              | 29 ms   | 58 ms   | 86 ms   | 110 ms  |\n| **300**                                              | 40 ms   | 79 ms   | 119 ms  | 159 ms  |\n| **400**                                              | 53 ms   | 106 ms  | 160 ms  | 213 ms  |\n\nThese results reinforce that our reported relative speedups (often 100×–10,000×) translate into meaningful real-world runtime improvements. We will include both tables in the final version for completeness.\n\n**Positioning of FourierSHAP vs. Multivariate Function Decomposition:** Although we agree that low-order additive decompositions can yield computational benefits, it is unclear which specific work is being referred to. If the reviewer could point us to a particular method in mind, we could clarify how our approach compares.\n\nWe hope our response addresses the concerns raised by the reviewer, and we are happy to engage in further discussions."}]

Author rebuttal:

Meta-review: This paper presents a computational efficient, exact calculation of Shapley values for models with categorical features via a sparse Fourier representation.

It has split the reviewers:
- **4ytr** argues for rejection on the grounds that the paper adds little to e.g. Van den Broeck et al. (2022) and Arenas et al. (2023)), in addition to not sufficiently recognising those papers' contributions.
- **pDrB** favours acceptance, finding FourierSHAP novel, efficient and fast, while expressing some concerns about exposition.
- **UB9P** strongly favours acceptance - but does note that the Section 4 exposition is dense, and - thus - the reviewer cannot vouch for the results. No reviewer has found an error in the paper.
- **ihkk** favours acceptance as well, also citing the paper's novelty, efficiency and speed. This reviewer's impression has improved with the author engagement - hoping that some of the points arising in correspondence will be incorporated into the paper.

The authors, replying to 4ytr, emphasise:
1. their analysis applies to interventional/baseline Shapley values, in contrast to the cited papers.
1. none of the cited papers work through the Fourier representation, which allows a closed form representation.
1. their approach is explicitly constructive, presenting a closed form solution, while the cited work tends to present existence results.

My review of van den Broeck et al. and Arenas et al. largely favours the authors' claims:
1. vdB explicitly works with the 'original' Lundberg & Lee (observational) Shapley value.  Arenas et al. are not explicit about their choice, but do not seem to adopt any sort of $do()$ formalism. 
1. neither vdB et al. nor Arenas et al. mention Fourier representations.  I do not know the literature well enough to know whether there is an isomorphism between the formalisms considered.  I did not notice closed form solutions in vdB or Arenas.
1. vdB and Arenas do both consider algorithms.

Thus, while I - with 4ytr - would like to see a more careful comparison to the existing literature, I also share the view of the positive reviewers, that the paper does seem to make a contribution to the literature.

**12/09/25**: updated Meta-Review to 'accept' from 'accept (oral)', following query from PCs: I had understood 'oral' to be a step up from 'poster', rather than a step up from 'highlight'.  Above all, I would follow the judgement of the SAC, who has written one of the main papers that this paper builds upon.
Decision: Accept (spotlight)