Efficient and Accurate Explanation Estimation with Distribution Compression
Authors: Hubert Baniecki
Giuseppe Casalicchio
Bernd Bischl
Przemyslaw Biecek
Venue: ICLR 2025 Spotlight (2025)
Keywords: explainable ai
feature attributions
feature importance
sampling
kernel thinning
Primary area: interpretability and explainable AI

Abstract: We discover a theoretical connection between explanation estimation and distribution compression that significantly improves the approximation of feature attributions, importance, and effects. While the exact computation of various machine learning explanations requires numerous model inferences and becomes impractical, the computational cost of approximation increases with an ever-increasing size of data and model parameters. We show that the standard i.i.d. sampling used in a broad spectrum of algorithms for post-hoc explanation leads to an approximation error worthy of improvement. To this end, we introduce Compress Then Explain (CTE), a new paradigm of sample-efficient explainability. It relies on distribution compression through kernel thinning to obtain a data sample that best approximates its marginal distribution. CTE significantly improves the accuracy and stability of explanation estimation with negligible computational overhead. It often achieves an on-par explanation approximation error 2-3x faster by using fewer samples, i.e. requiring 2-3x fewer model evaluations. CTE is a simple, yet powerful, plug-in for any explanation method that now relies on i.i.d. sampling.

Published as a conference paper at ICLR 2025
EFFICIENT AND ACCURATE EXPLANATION ESTIMATION WITH DISTRIBUTION COMPRESSION
Hubert Baniecki
Giuseppe Casalicehio
University of Warsaw h. b.bbnncck @uw.
LMU Munich
Munich Center for Machine Learning
Bernd Bischl
Przemyslaw Biecek
LMU Munich
University of Warsaw
Munich Center for Machine Learning
Warsaw University of Technology
ABSTRACT
We discover a theoretical connection between explanation estimation and distribu- tion compression that significantly improves the approximation of feature attribu- tions, importance, and effects. While the exact computation of various machine learning explanations requires numerous model inferences and becomes imprac- tical, the computational cost of approximation increases with an ever-increasing size of data and model parameters. We show that the standard i.i.d. sampling used in a broad spectrum of algorithms for post-hoc explanation leads to an ap- proximation error worthy of improvement. To this end, we introduce compress then explain (CTE), new paradigm of sample-efficient explainability. It relies on distribution compression through kernel thinning to obtain data sample that best approximates its marginal distribution. CTE significantly improves the accuracy and stability of explanation estimation with negligible computational overhead. It often achieves on-par explanation approximation error 2-3x faster by using fewer samples, i.e. requiring 2-3x fewer model evaluations. CTE a simple, yet powerful, plug-in for any explanation method that now relies on i.idd. sampling.
INTRODUCTION
Computationally efficient estimation of post-hoc explanations is at the forefront of current research on explainable machine learning (Strumbelj & Kononenko, 2010; Slack et al., 2021; Jethani et al., 2022; Chen et al., 2023; Donnelly et al., 2023; Muschalik et al., 2024). The majority of the work focuses on improving efficiency with respect to the dimension of features (Covert et al., 2020; Jethani et al., 2022; Chen et al., 2023; Fumagalli et al., 2023), specific model classes like neural networks (Erion et al., 2021; Chen al., 2024) and decision trees (Muschalik et al., 2024), or approximating the conditional feature distribution (Chen et al., 2018; Aas et al., 2021; Olsen et al., 2022; 2024).
However, in many practical settings, marginal feature distribution is used instead estimate expla- nations, and i..d. samples from the data typically form the so-called background data samples, also known as reference points or baselines, which plays a crucial role in the estimation process (Lundberg & Lee, 2017; Scholbeck et al., 2020: Erion et al., 2021; Ghalebikesabi et al., 2021; Lundstrom et al., 2022). For example, Covert al. (2020) mention "[Ojur sampling approximation for SAGE was run using draws from the marginal distribution. We used fixed set of 512 background samples [..]]' and we provide more such references in Appendix improve on standard i.i.d. sampling in explanation estimation?
motivate our research question: Can we reliably
We make a connection to research on statistical theory, where kernel thinning (KT, Dwivedi & Mackey, 2021; 2022) was introduced to compress distribution more effectively than with i.i.d. sampling. KT has an efficient implementation the COMPRESS++ algorithm (Shetty et al., 2022) and was applied to improve statistical kernel testing (Domingo-Enric) et al., 2023). Building on this line of work, this paper aims to thoroughly quantify the error introduced by the current sample then explain paradigm in feature marginalization, which is involved in the estimation of both local and global removal-basel explanations (Covert et al., 2021). We propose an efficient way to reduce this approximation error based distribution compression (Figure 1).

---

Published as a conference paper at ICLR 2025
Compress Then Explain (CTE)
L..dd sample
compressed distribution
negligthle overhend
estimated explanation
sample then explain
compress then explain
is recidivist
10'
10
10'
10
priors count
time
MAR
race
underestimate
sex
1.0
age
overestimare
0.5
charge degree
4x more efficient 4x fustr
approximation error
stay length
2%
496
6%
8%
sample size
Figure 1: Garbage sample in, garbage explanation out. Sample then explain is a conventional approach to decrease the computational cost of explanation estimation. Although fast, sampling is inefficient and prone to error, which may even lead to changes in feature importance rankings. We propose compress then explain (CTE), a new paradigm for accurate, yet efficient, estimation of explanations based on marginal distribution that is compressed, e.g. with kernel thinning.
Contribution. In summary, our work advances literature in multiple ways: (1) Quantifying the error of standard i.i.d. sampling: We bring to attention and measure the approximation error introduced by using i.i.d. sampling of background and foreground data in various explanation methods. It may even lead to changes in feature importance rankings. (2) Compress then explain (CTE): We introduce feature attributions and effects, are estimated based on a marginal distribution compressed more efficiently than with i.idd sampling. CTE is theoretically justified explanation estimation and distribution compression. (3) Kernel thinning for (explainable) machine learning: We show empirically that KT outperforms i.i.d. sampling in compressing the distribution of popular datasets used in research on explainable machine learning. In fact, this is the first work to evaluate distribution compression via on datasets for supervised learning, which itself valuable. (4) Decreasing the computational cost of explanation estimation: We benchmark compress then explain (CTE) with popular explanation methods and show results in more accurate explanations of smaller variance. CTR often achieves on-par error using 2-3x fewer samples, i.e. requiring x-3x fewer model inferences. CTE is a simple, yet powerful, plug-in for broad class of methods that sample from a dataset, e.g. removal-based and global explanations.
paradigm of sample-efficient explainability where post-hoc explanations, like
discover a connection between
Related work. Our work is the first to empirically evaluate KT on datasets for supervised learning, and one of the first to reliably improve on i.i.d. sampling for multiple post-hoc explanation methods at once. Laberge al. (2023) propose a biased sampling algorithm to attack the estimation feature attributions, which further motivates finding robust improvements for i.i.d. sampling. Our research question is orthogonal to that of how to sample perturbations around an input (Petsiuk et al., 2018; Slack et al., 2021; Li et al., 2021; Ghalebikesahi et al., 2021; Li et al., 2023), how efficiently sample feature coalitions (Chen et al., 2018; Covert Lee, 2021; Fumagalli et al., 2023). Instead of generating samples from the conditional distribution itself, which is challenging (Olsen et al., 2022), we explore how to efficiently select an appropriate subset of background data for explanations (Hase al., 2021; Lundstrom et al., 2022). Specifically for Shapley-based explanations, Jethani al. (2022) propose to predict them with a learned surrogate model, while Kolpaczki et al. (2024) propose their representation detached from the notion of marginal contribution. We aim to propose general paradigm shift that benefits broader class of explanation methods including feature effects (Apley & Zhu, 2020; Moosbauer et al., 2021) and expected gradients (Erion et al., 2021; Zhang et al., 2024).
Concerning distribution compression, the method most related to KT (Dwivedi & Mackey, 2021) is the inferior standard thinning approach (Owen, 2017). Cooper et al. (2023) use insights from KT to accelerate distributed training, while Zimmerman et al. (2024) apply KT in robotics. In the context of data-centric machine learning, we broadly relate to finding coresets to improve the efficiency of clustering (Agarwal al., 2004; Har-Peled & Mazumdar, 2004) and active learning (Sener & Savarese, 2018), as well as dataset distillation (Wang et al., 2018) and dataset condensation (Zhao al., 2021; Kim al., 2022) that create synthetic samples to improve the efficiency of model training.
2

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
We aim to explain a prediction model trained on labeled data and denoted by f: X' + R where X' is the feature space; it predicts output using an input feature vector x. Usually, we assume X' S R². Without loss of generality, in the case of classification, we explain the output of a single class as a posterior probability from [0. 1]. We can assume a given dataset {(x(1, ( (x("), )) where every element comes from X' X V. the underlying feature and label space, which the explanations are computed. Depending on the explanation method and scenario, the dataset could be provided without labels. We denote such n x d dimensional dataset by X where x(0) appears in the i-th row of X. which is assumed to be sampled in an i.i.d fashion from an underlying distribution p(x, y) defined on X' x V. We denote a random vector as X E X. Further, let C (I,..., d} be feature index set of interest with its complement
{1...... ......... d} \ We index feature vectors x and random variables X by index set s to restrict them to these index sets. We write px(x) and px, (Xe) for marginal distributions on X and X., respectively, and /x. Xx (x,|xx) for conditional distribution on X, X We use q% to denote empirical distribution approximating Px based on dataset X.
2.1 SAMPLING FROM THE DATASET IS PREVALENT IN EXPLANATION ESTIMATION
Various estimators of post-hoc explanations sample from the dataset to efficiently approximate the ex- planation estimate (Appendix A). For example, many removal-based explanations (Covert et al., 2021) like SHAP (Lundberg & Lee, 2017) and SAGE (Covert et al., 2020) rely on marginalizing features out of the model function f using their joint conditional distribution ExxxxxxxXxxx>. [x X,)] =
I [(xx; Xx) Xx))xxxXX==x> (xx|x.,)rr (r][xxxxxx Jdlx. Note that the practical approximation of the conditional distribu- tion Ix,IX,=x, (Xg)X,) itself is challenging (Chen al., 2018: Aas et al., 2021: Olsen et al., 2022) and there is no ideal solution to this problem (see recent benchmark by Olsen et al., 2024). For example, the default for SAGE to assume feature independence and use the marginal distribution Px, (x))x.) == Px, (x,) (Covert et al., 2020, Appendix D); so does the KERNEL-SHAP esti- mator, i.e. a practical implementation of SHAP (Lundberg & Lee, 2017). This trend continues in more recent work sampling from marginal distribution (Fumagalli et al., 2023; Krzyziński et al., 2023).
Definition (Feature marginalization). Given a set of observed values xs, we define a model function with marginalized features from the set 3 as (xxiPx) == Ex,rxx (x..X.))
In practice, the expectation Ex,~px; [f X.)] is estimated by i.i.d. sampling from the dataset X that approximates the distribution Px, (Xx). This sampled set of points forms the so-called background data, aka reference points, or baselines as specifically in case of the expected gradi- ents (Erion et al., 2021) explanation method, which can be defined as EXPECTED-GRADIENTES
=
Ex<px.a~U(0. (x X). af(x+a -X)] Klein et al. (2024) benchmark feature attribution 8x
methods showing that SXPEECEDD-GRADIENT is among the most faithful and robust ones.
Furthermore, i.i.d. sampling is used in global explanation methods, many of which are an aggregation of local explanations. To improve the computational efficiency of these approximations, often only a subset of X is considered, called foreground data. Examples include: FEATURE- explanations (Apley & Zhu, 2020), an aggregation of LIME (Ribeiro et al., 2016) into G-LIME (Li et al., 2023), and again SAGE, for which points from X require to have their corresponding labels y.
2.2 BACKGROUND ON DISTRIBUTION COMPRESSION
Standard sampling strategies can be inefficient (Dwivedi & Mackey, 2021). For example, the Monte Carlo estimate n En= h(x(9) of an unknown expectation Ex~px h(X) based on n i.i.d. points has 011/V/) integration error h(x) - E h(((()) requiring 102 points for 10% relative error and 10s points for 1 1% error (Shetty et al., 2022). To improve on i.i.d. sampling, given a sequence X of n input points summarizing target distribution px. the goal of distribution compression to identify a high quality coreset X of size ñ < n. This quality is measured with the coreset's integration error ""_,hh h)x()) - 1 E h(xe(()) for functions h in the reproducing kernel Hilbert space induced by a given kernel function k (Muandet et al., 2017). The recently introduced KT algorithm (Dwivedi & Mackey, 2021; 2022) returns such a coreset that minimizes the kernel maximum mean discrepancy (MMD), Gretton al., 2012).
3

---

Published as a conference paper at ICLR 2025
Definition 2 (Kernel maximum mean discrepancy (Gretton et al., 2012; Dwivedi & Mackey, 2021)))
Let k : R2 x IRd + R be a bounded kernel function with k(x,) .) measurable for all x E R e.g. Gaussian kernel. Kernel maximumn mean discrepancy between probability distributions p. Ia is defined as MMDx(p: q) = su ( [xx h(X) - -x h(X)), where Hy is a reproducing kernel Hilbert induced by k.
To formulate Propositions & 2 in the next Section, we recall biased estimate of maximum mean discrepancy, which discussed in (Chérief-Abdellane & Alquier, 2022, remark 3.2) and (Sriperumbudur et al., 2010, corollary 4).
Definition 3 (Biased estimator of MMDx). From (Muandet el al., 2017, section 5.1), as shown in (Gretton et al., 2012), the L2 distance between kernel density estimates px, is special case of the 2 biased MMDx estimator, i.e. we have MMD, (px, 9x) = |lpx 9x 112 = f (px(x) - -x((x) 2 dx.
An unbiased empirical estimate of MMDR can be relatively easily computed given kernel func- tion k (Gretton et al., 2012). COMPRESS++ (Shetty et al.. 2022) is an efficient algorithm for KT that returns coreset of size /n in (n log n) time and (Vvn log" n) space, making KT viable for large datasets. It was adapted to improve the kernel two-sample test (Domingo-Enrich et al., 2023).
3 COMPRESS THEN EXPLAIN (CTE)
We propose distribution compression as a substitute to i.i.d. sampling for feature marginalization in removal-based explanations and for aggregating global explanations. We now formalize the problem and provide theoretical intuition as to why methods for distribution compression can lead to more accurate explanation estimates. We defer the proofs to Appendix B.
Definition 4 (Local explanation based on feature marginalization). A local explanation is func- tion g(x: P.Px): X' + IR of input x given model f that relies on a distribution px for feature marginalization. For estimation, it uses an empirical distribution yz in place of px-
Examples of such local explanations include SHAP (Lundberg & Lee, 2017) and EXPECTED- GRADIENTS (Erion et al., 2021). We aim to provide high-quality explanations stemming from compressed samples as measured with given approximation error, e.g. mean absolute error.
Problem formulation. To optimize the approximation error, we propose novel formulation of the sample selection problem:
min X
||](x; f.9x) - s(
s.t. for a given n, where i...d. sampling, distribution compression, or for example clustering, are the potential methods to find X in unsupervised manner. We discover connection between distribution compression and explanation estimation in Propositions 1 & 2.
- F
Proposition 1 (Feature marginalization is bounded by the maximum mean discrepancy between data samples). For two empirical distributions qx, 0% approximated with kernel density estimator k, we have [xxs: qx) [(xs: qg) S Cy MMDx (gx, qz), where Cj denotes constant that bounds the model function f, i.e. YXERo f(x) S CC..
Proposition provides a worst-case bound for feature marginalization, the backbone of local explana- tions, in terms of the MMDx distance between the (often compressed) empirical data distributions. complements the results for input and model perturbations obtained in (Lin et al., 2023, Lem- mas & 4), which also shows how such bound propagates the local explanation function g. Effectively, Proposition states that an algorithm minimizing MMD e.g. KT, restricts the approx- imation error of explanation estimation. This makes CTE a natural contender to improve on i.i.d. sampling, given it was efficient and stable, which we evaluate empirically in extensive experiments.
Compress then explain globally. Local explanations are often aggregated into global explanations based on a representative sample from data, resulting in estimates of feature importance and effects. Definition 5 (Global explanation). A global explanation is function that aggregates local explana- tions of model f over input samples from distribution px. i.e. G(px: f. g) = Ex-px [g(X; f. -)) For estimation, uses an empirical distribution qx in place of px.
4

---

Published as a conference paper at ICLR 2025
Examples of such global explanations include FEATURE-EFFECT like partial dependence plots and accumulated local effects (Apley & Zhu, 2020), and SAGE (Covert et al., 2020), which additionally re- quires input labels y of the samples drawn from px- Notably, the local explanation function g in SAGE itself relies on feature marginalization leading to using px twice, i.e. Ex-px [g(X; (xx)) (see Listing for a practical implementation).
Problem formulation revisited. For global explanations, following Equation 1, we have:
min
|[( f.9) G((g::.9))
s.t. X - Knn.
In Proposition 2, we conduct a worst-case analysis for global aggregated explanations. Proposition (Global explanation bounded by the maximum mean discrepancy between data samples). For empirical distributions 9x, og approximated with kernel density estimator k, have [[G[xx; J. G(yg: J.9))l2 | I Cg 1MD (1x, gg), where Cg denotes constant that bounds the local explanation function g. i.e. YXEBr (|g]= 1l12 C...
Analogously to Proposition 1, Proposition states that an algorithm minimizing MMDk, e.g. KT. restricts the approximation error of explanation estimation, which makes CTE natural contender to improve on i.i.d. sampling. It extends the bounds for total variation distance obtained (Baniecki al., 2024). Moreover, in Section 4.5, explore empirically the impact that minimizing MMDx has on decreasing alternative distribution discrepancies in practical (explainable) machine learning settings. It gives further intuition estimation. Our insights may guide future work on tighter theoretical guarantees for improving explanation estimation with distribution compression.
why clustering often leads higher errors in explanation
Implementation. The pivotal strength of CTE is that it is simple to plug into the current workflows for explanation estimation as shown in Listing for SAGE. We provide analogous code listings for SHAP, GRADIETTTSS and FEATURE- EFFETTS in Appendix C.
x, model
from goodpoints import compress
ids compress compresspp_keee (X, kernel_type-b "gausssiaaaasssaaa............. g=4)
X x_compressed X[ids]
import sage
imputer sage Margina Imputer (model predict, X_compressed)
estimator sage KernelEst imator (imputer)
explanation estimator (X, y)
# or even
y_compressed yiida]
explanation est i mator (X_compressed, y_compressed)
Listing 1: Code snippet showing the 3-line plug-in of distribution compression for SAGE estimation.
EXPERIMENTS
In experiments, we empirically validate that the CTE paradigm improves explanation estimation across 4 methods, 2 model classes, and over 50 datasets. We compare CTE to the widely adopted practice of i..dd sampling (see Appendix for further motivation). We also report sanity check results for more deterministic baseline sampling with k-medoids where centroids from the clustering define a coreset from the dataset. use the default hyperparameters explanation algorithms (details are provided in Appendix D) For distribution compression, we use COMPRESS++ implemented in the goodpoints Python package (Dwivedi & Mackey, 2021), where we follow (Shetty et al., 2022) to use a Gaussian kernel k with o = 2d.. For all the compared methods, the subsampled set of points is of size /n as we leave oversampling distribution compression for future work. We repeat all experiments where we apply some form downsampling before explanation estimation 33 times and report the mean and standard error (se.) deviation (sd.) of metric values.
Ground truth. The goal of CTE to improve explanation estimation over the standard i.i.d. sampling. We measure the accuracy and effectiveness of explanation estimation with respect to "ground truth"
5

---

Published as a conference paper at ICLR 2025
A)
B)
KernelSHAP
KHAP
ArrmutationSHAP
PermurationSHA
compreis sampll
Karne SAGE
KemaISAGE
SaG
NermttationAGE
comprexx
0,002
0,004
0,006
0.008
0.5
0.6
Top-k
KernelSHAP
KerneSHAPP
PermutationSHuAP
PermuratioSHAP
eapla Ionund sunt explo tompresset
Karne SAGE
KemalSAGE
PerutationSAGE
PermutationSAGG
10
100
107 302 10a
10
10
10a
10
10*
10
10
Figure 2: Comparison between CTE and i.i.d. sampling for the two estimators of SHAP and SAGE explanations on the adult t dataset. A) We measure mean absolute error (MAF 1) between feature attribution and importance values, and B) the precision in correctly identifying the 5 most important features (Top-k 1). C) Comparison between the computational time of distribution compression and explanation estimation on the compressed sample, assuming the time of i.i.d. sampling is 0. D) Comparison between the computational time explanation estimation on the compressed sample and on full data (in green). Analogous results for the other 4 datasets in Appendix E. (mean + se.)
explanation (cf. Appendix 1) that is estimated using full validation dataset X. i.c. without sampling or compression. We consider settings where this is very inefficient to compute in practice (n == Revalid is between 1000 and 25000 samples). For large datasets, truncate the validation dataset 20 the size of the compressed dataset. Since some explanation methods include a random component in the algorithm, we repeat their ground truth estimation 3 times and average the resulting explanations.
Accuracy. We are mainly interested in the accuracy of estimating a single explanation, measured by the explanation approximation error. Namely, mean absolute error (MAE), where mea- and de G( f.g) Gigg; 9) with dG = d for SAGE. We have dç = 100 (d - d') for FEATURE- EFFECTS, since we use 100 uniformly distributed grid points for I-dimensional effects and 10x 10 uniformly distributed grid points for 2-dimensional effects (see Appendix D). For broader context, in Section 4.1, we also measure the precision of correctly indicating the top & features.
sure Ru Enmi (x; fxgx) (x) fl))),, for SHAP and EXXPECED-GRADDENTT
Efficiency. We measure the efficiency of compression and explanation estimation with CPU wall- clock time (in seconds), assuming the time of i.i.d. sampling is O. We rely on popular open-source implementations of the algorithms (see Appendix C) and perform efficiency experiments computer with an M3 chip. This is to imitate the most standard workflow of explanation estimation, while we acknowledge that specific time estimates will vary in more sophisticated settings.
personal
4.1 CTE IMPROVES THE ACCURACY OF ESTIMATING FEATURE ATTRIBUTIONS & IMPORTANCE
We use the preprocessed datasets and pretrained neural network models from the well-established
OpenXAI benchmark (Agarwal et al., 2022). We filter out three datasets with less than 1000 observations in the validation set, where sampling is not crucial, which results in five tasks: adult (Nvalid = 9045, d = 13), compas (Nvali 1235, d = 7), gaussian (a synthetic dataset, Mvalid 1250, d = 20), gmsc e (Give Me Some Credit, nlaaid 20442, d 10), and heloc (aka FICO, Tivalid 1975, d = 23). Further details on datasets and models are provided in Appendix D.2.
We aim to show that CTR improves the estimation of feature attribution and importance explanations, estimators: kernel- and
namely for SHAP and SAGE. We experiment with two permutation- based. For example, Figure 2 shows the differences in MAE and Top-k between CTE and standard i.i.d. sampling on the adult t dataset. Analogous results for the other 4 datasets from OpenXAl are shown in Appendix E. On all the considered tasks, CTE results a notable decrease in approximation error when compared to i.i.d. sampling and increase in precision (for top-k feature identification) with negligible computational overhead. Moreover, CTE results explanation estimates of significantly smaller variance on average shown in Table 1.

---

Published as a conference paper at ICLR 2025
We report the improvement in the mean absolute error of estimating four popular explana- tions on five datasets from the OpenXAI benchmark. CTE not only improves the accuracy over i.i.d. by 20-45%, but also leads to more stable estimates by about 50%. MAE (4, + sd.) values are scaled and rounded to improve readability while detailed and extended results are reported in Appendix E.
Table 1:
Task
Explanation estimator
KERNEL-SHAF
PERMUTATION-SHAAL
KERNEL-SAGE
PERMUTATION
adult
( Li.d.
ditr.
CTE
13
21%
58
65
37%
41
63440
40%
38
compas
10
40%
64
11+4
46%
6+
19
38%
18
28
39%
17+8
aaussian
13:2
811
1542
27%
11
121
42%
30
52
44%
29
gmsc
23
39%
14
2545
32%
17:3
30413
40%
18
28
43%
16
heloc
67:15
39%
4117
72:13
33%
48
34
21%
27:16
29:11
26%
2116
4.2
CTE AS AN EFFICIENT ALTERNATIVE TO LLI.D SAMPLING EXPLANATION ESTIMATION
We find CTE be very efficient alternative to standard i..d. sampling in explanation estimation. For example, com- pressing distribution from Ik to 32 samples takes less than 0.1 seconds, and from 20k to 128 samples takes less than I second. The exact runtime will, of course, differ based on the number of features. Figure reports the wall-clock time for datasets of different sizes. Note that the potential runtimes for distribution compression are of magnitudes smaller than the typical runtime of explanation estimation. For example, estimating KERNEL-SIIAP for 9k samples us- ing 128 background samples takes 30 minutes, which about 60x less than estimating the ground truth explana- tion (Figure 2). Moreover, estimating KERNEL-SHAU or PERMUTATION-SAGG for Ik samples using 32 background samples takes about 10 seconds, which about 30x less than estimating the ground truth explanation (Appendix E).
gaussian
comprees cluster
compas
heloc
adult
gmsc
10 2
Time[s]
Figure 3: Compressing a distribution
from 20k to 128 samples takes less than 1 second compute a CPU. (mean + se.)
4.3 CTE IMPROVES GRADIENT-BASES EXPLANATIONS SPECIFIC TO NEURAL NETWORKS
Next, we aim to show the broader applicability of CTE by evaluating it gradient-based explanations specific to neu- ral networks, often fitted to larger unstructured datasets.
A)
Imdb
Sanity check. We first compress the validation sets of IMDB and ImageNet- Ik on a single CPU as a samity check for the viability of CTF in settings considering larger datasets. For the IMDB dataset (Nvalid = 25000, d = 768), CTE takes as an input text embeddings from the pretrained DistilBERT model's last layer (preceding a classifier) that has a dimen- sion of size 768. Similarly, for ImageNet-Ik (Ai 50000, d = 512), CTE operates on the hidden representation ex- tracted from ResNet-18. Figure shows the optimized MMD₂ metric between the distributions and computation time in seconds. We can see that proper compression results in huge benefits w.r.t. MMDx (compared to i.i.d. sampling and clustering) and only negligible computational overhead.
imagenet1k
10-5
10-4
MMD
B)
Imdb
imagenet1k
Time (s)
Figure 4: A) COMPRESS++ effec- tively optimizes MMDj unstruc- tured IMDB and Imagenet- datasets. B) Compressing distribution from 25k-50k to 128 samples in 512-768 dimensions takes about 5-10 sec. to compute on CPU, (mean + se.)
Accuracy and efficiency. We now study CTE together with EXPECTED-GRADIENT of neural network models trained to 18 datasets (Nvali 1000, d > 32) from the OpenML-
CC18 (Bischl et al., 2021) and OpenML-CTR23 (Fischer et al., 2023) benchmark suites. Details datasets and models provided in Appendix D.2.
7

---

Published as a conference paper at ICLR 2025
Explanation: Expected Gradients
sample
compress
cluster
1e-4
mnist_ 784
1e-3
satimage
le-4
Fashion-MNIST
1e
CIFAR_10 10
2.4
1.8
1.8
1.6
1.2
1.2
0.8
0.6
3x more efficient
0.0
0.0
0.0
512
128
256
256
N samples
samples
N samples
N samples
Figure 5: Comparison between CTE, i.i.d. sampling and clustering for SRRDINTSSS explanations on the 4 image classification datasets. We measure mean absolute error (MAE 4) between feature attribution values. CTE not only more accurate but also more stable as measured with deviation. Analogous results for the remaining 14 datasets are in Appendix F, (mean + sd.)
In Figure 5, we show the explanation approximation enror for 4 image classification tasks, while analogous results for the remaining 14 datasets are provided in Appendix F. Additionally here, we vary the number of data points sampled from i.i.d. inspect the increase in efficiency of CTE. In all cases, CTE achieves on-par approximation error using fewer samples than i.i.d. sampling, i.e. requiring fewer model inferences, resulting faster computation and saved resources. The accuracy improvements are significant, i.c. CTE decreases the estimation eπгоr for EXPECTED-GRADIENT by 35% on mnist s78 (Welch's t-test: p < le- 10-10), by 40% on Fashion-MNIST (p < 1e le-10), and by 21% % on CIFAR_10 (p < 1e-10). Moreover, CTE provides 2-3x efficiency improvements as measured by the number of samples required for i.i.d. to reach the error of CTE.
Model-agnostic explanation of a language model. In Appendix F, we further experiment with applying CTE to improve the estimation of G-LIME (Li al., 2023) explaining the predictions of a DistiBERT language model trained on the IMDB dataset for sentiment analysis.
4.4 ABLATIONS WITH ANOTHER 30 DATASETS, AN XGBOOST MODEL FEATURE EFFECTS
For a convincing case to use CTE instead of i.i.d. in practice, we perform additional empirical analysis on various datasets, with a different model class, and include another global explanation method. More specifically, we use CTE to improve FEATURE-EIFECTS of XGBoost models trained on further 30 datasets (Neald > 1000, and models are provided in Appendix D.2. Moreover, we include SHAP and SAGE in the benchmark similarly to Section 1. As another ablation, SAGE evaluated in two variants that consider either compressing only the background data (a rather typical scenario), or using the compressed samples as both background and foreground data (as indicated with "fg.": refer to Listing for this distinction).
32) from OpenML-CC18 and OpenML-CTR23. Details on datasets
Figure shows the explanation approximation error for 3 predictive tasks, while analogous results for the remaining explanation estimators and 27 datasets are provided Appendix G. We observe that CTE significantly improves the estimation of PEATURE-EFFECTS in all cases. We further confirm the conclusions from Sections 4.1 & 4.2 that CTE improves SHAP and SAGE. Another insight is that, on average, CTE provides smaller improvement over i.i.d. sampling when considering compressing foreground data in SAGE.
Conclusion from the experiments. In Figure 7, aggregated the results from Sections 4.3 & 4.4 to conclude the main claim that CTE offers 2-3x improvements in efficiency over i.i.d. sampling.
4.5 KERNEL THINNING ON DATASETS FOR (EXPLAINABLE) MACHINE LEARNING
We have already established that distribution compression a viable approach to data sampling, which regularly entails better approximation of explanations. Moreover, its computational overhead is negligible when applied before explanation estimation. To provide more context on discovering the theoretical justification for CTE from Section 3, we aim to show that COMPRESS++ entails better approximation of feature distribution on popular datasets for (explainable) machine learning. This is out-of-the-hox, without tuning its hyperparameters, which is natural direction for future work.
8

---

Published as a conference paper at ICLR 2025
Dataset: california housing
sample
compress
1e- 2
KernelSHAP
1e-2 2
PermutationSAGE
1e- PermutationSAGE (fg.)
1e-
Feature
7.5
7.5
1.2
IAAE
5.0
5.0
0.8
2.5
2.5
0.4
3x more efficient
0.0
0.0
0.0
64
128
192
256
64
128
192
256
64
128
192
256
128
192
256
N samples
N samp es
N samp
samples
Dataset: diamonds
sample
compress
cluster
1e-2
KernelSHAP
1e-2
PermutationSAGE
1e-2
PermutationSAGE (fg.) le-
Feature Effects
6
1.2
1.5
MAE
0.8
4
1.0
0.4
4x more efficient
2
4
0.5
0.0
0.0
64
128
192
256
64
128
192
256
64
128
192
256
64
128
192
256
N samples
N samp es
N samp es
samples
Dataset: grid stability
sample
compress
cluster
1e
KemeISHAP
PermutatioNAGE
PermutationSAGE (fg.) le
Feature Effects
3.0
7.5
3.0
5.0
4x efficient
2.5
1.5
0.6
0.0
0.0
0.0
64 samples
128
samples
N samples
samples
Figure 6: CTE improves the approximation error of local and global removal-based explanations. SAGE is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples both background and foreground data (as indicated with "fg."). Analogous results for the remaining estimators and 27 datasets are in Appendix G. (mean sd.)
A)
3
5
B)
3
4
5
sample
compress (2.4
5.4)
cluster
(4x) sample (2-1
0:5)
cluster
(3x) sample (2.5)
(3.9) sample (2x)
sample (2.8)
(4.1) sample (2x)
Figure 7: Critical difference diagrams of average ranks (lower is better) aggregated over explanation estimators and 48 dataset-mode pairs: A) for MAE averaged over repeats, and B) for the sd. of MAE over repeats that corresponds to the stability of explanation estimation. CTE often achieves on-par explanation approximation error using 2-3x fewer samples, i.c. requiring 2-3x fewer model inferences, which is efficient. Moreover, CTE guarantees more stable estimates than i.i.d. sampling.
Measuring distribution change. In general, measuring the similarity of distributions or datasets is challenging, and many metries with various properties have been proposed for this task (Gibbs Su, 2002). Here, we report the following distance metric values between the original and compressed distribution: the optimized MMDk, total variation distance (TV, Gibbs & Su. 2002). Kullback-Leiblee divergence (KI., Gibbs & Su, 2002), and d-dimensional Wasserstein distance (WD, Feydy et al., 2019; Laberge et al., 2023). Since approximating d-dimensional TV and KI. infeasible in practice (see e.g. Sriperumbudur et al., 2012, section 5), we report an average of the top-3 largest discrepancies between the I-dimensional distributions of features as proxy.
Result. In Figure 8, we observe that COMPRESS++ works much better in terms of MMDx all five datasets from OpenXAI, compared to standard i...d. sampling or the clustering baseline, which no surprise as this metric is internally optimized by the former. Note that it also leads to notable improvements in all other metrics. Overall, there no consistent improvement in approximating the distribution using clustering, which explains why it leads to higher emor in explanation estimation.

---

Published as a conference paper at ICLR 2025
geussien
gaussian
compas
compas
compress samp e
heloc
heloc
cluster
adult
adult
gmsc
gmsc
A)
0.000
0.002
0.004
0.006
B
0,0
0.1
0.2
0.3
gaussian
gaussian
compress smmp chocsr
compas
compas
helac
heloc
adult
adut
gmsc
gmsc
0.0
0.1 0.2
0.3
D)
0.00
0.05
0.20
0.15
0.20
0.25
WD
KL
Figure 8: COMPRESS++ with Gaussian kernel on five datasets (rows) for the four considered distribution change metrics (panels): A) MMDx, B) total variation distance, C) d-dimensional Wasserstein distance, and D) Kullback-Leibe divergence. The length of the bar is the mean value = standard error across statistical repetitions, where color indicates the applied downsampling method.
DISCUSSION
We propose compress then explain as a powerful alternative to the conventional sample then explain paradigm in explanation estimation. CTE has the potential to improve approximation error across a wide range of explanation methods for various predictive tasks. Specifically, we show accuracy and stability improvements in popular removal-based explanations that marginalize feature influence, and in general, global explanations that aggregate local explanations over a subset of data. Moreover, CTE leads to more efficient explanation estimation by decreasing the computational resources (time, model inferences) required to achieve error on par with a larger i.idd sample size.
Future work on methods for marginal distribution compression other than kernel thinning and clustering will bring further improvements in the performance of explanation estimation. Distribution compression methods, by design, have hyperparameters that may impact the empirical results. Although we have shown that the default COMPRESS++ algorithm is robust baseline, exploring the tunability of its hyperparameters of conditional sampling methods, Olsen et al., 2024). We used the Gaussian kernel because it is the standard in the field of distribution compression (Dwivedi & Mackey, 2022: Shetty et al., 2022; Domingo-Enriin Enrich et al., 2023), especially in experimental analysis, and is generally adopted within machine learning applications. Although our empirical validation shows that the Gaussian kernel works well for over 50 datasets, exploring other kernels for which theoretical thinning error bounds exist, like Matérn or B-spline (Dwivedi & Mackey, 2021), is viable future work direction. Furthermore, especially for tabular datasets, dealing with categorical features can be issue, which we elaborate on in Appendix D.2. Specifically for supervised learning, stratified variant of kernel thinning taking into account distribution of the target feature could further improve loss-based explanations like SAGE, or even the estimation of group fairness metrics. In concurrent work, Gong al. (2024) generalize
natural future work direction (similarly as in the case
speed up supervised learning problems involving kernel methods. One could also investigate how influence functions (Koh & Liang, 2017), which aim to attribute the importance of data to the model's prediction, can guide sampling for efficient explanation estimation.
Broader impact. In general, improving explanation methods has positive implications for humans interacting with Al systems (Rong et al., 2024). But, specifically in the context this work, biased sampling can be exploited to manipulate the explanation results (Slack al., 2020; Baniecki & Biecek, 2022; Laberge et al., 2023). CTE could minimize the risk such adversaries and prevent "random seed/state hacking" based on the rather unstable i.i.d. sampling from data in empirical research (Hermann et al., 2024).
Code. We provide additional details reproducibility in the Appendix, well as the code to reproduce all experiments in this paper is available at https: gightb..ubb...gggg com/ hbwniecki////////////i. compress- then- exmnaexxlll. ain.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was financially supported by the Polish National Science Centre grant number 2021/43/0/ST6/003447, and carried out with the support of the Laboratory of Bioinformatics and Com- putational Genomics and the High Performance Computing Center of the Faculty of Mathematics and Information Science, Warsaw University Technology. Hubert Baniecki gratefully acknowledges scholarship funding from the Polish National Agency for Academic Exchange under the Preludium Bis NAWA program. We want to thank Maximilian Muschalik, Mateusz Biesiadowski, Paulina Kaczynska, Anna Semik, and anonymous reviewers for their valuable feedback regarding this work.
REFERENCES
Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features are dependent: More accurate approximations to Shapley values. Artificial Intelligence, 298: 103502, 2021. 1, 2.1
Chirag Agarwal, Satyapriya Krishna, Eshika Saxena, Martin Pawelczyk, Nari Johnson, Isha Puri, Marinka Zitnik, and Himabindu Lakkaraju. OpenXAI: Towards a transparent evaluation of model explanations. In NeurlPS, 2022. 4.1, D.2
Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. Journal of the ACM, 51(4):606 635, 2004.
Daniel W. Apley and Jingyu Zhu. Visualizing the effects of predictor variables in black box supervised learning models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82 (4):1059-1086, 2020. 1, 2.1, 3, D.I
Hubert Baniecki and Przemyslaw Biecek. Manipulating SHAP via Adversarial Data Perturbations (Student Abstract). In AAAI, 2022.
Hubert Baniecki, Giuseppe Casalicchio, Bernd Bischl, and Przemyslaw Biecek. On the Robustness of Global Feature Effect Explanations. In ECML PKDD, 2024. 3
Bernd Bischl, Giuseppe Casalicchio, Matthias Feurer, Pieter Gijsbers, Frank Hutter, Michel Lang, Rafael Gomes Mantovani, Jan N. van Rijn, and Joaquin Vanschoren. OpenML benchmarking suites. In NeurlPS, 2021. 4.3, D.2
Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. Algorithms to estimate Shapley value feature attributions. Nature Machine Intelligence, 5(6):590-601, 2023.
Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. Learning to explain: An information-theoreti perspective on model interpretation. In ICML, 2018. 1, 1.1 2.1
Ruoyu Chen, Hua Zhang, Siyuan Liang, Jingzhi Li, and Xiaochun Cao. Less is more: Fewer interpretable region via submodular subset selection. In ICLR, 2024.
Zhaozheng Chen and Qianru Sun. Extracting class activation maps from non-discriminative features as well. In CVPR, 2023.
Badr-Eddine Chérief-Abdellatte and Pierre Alquier. Finite sample properties of parametric mmd cstimation: Robustness to misspecification and dependence. Bernoulli, 28(1), 2022. 2.2
A. Feder Cooper, Wentao Guo, Khiem Pham, Tiancheng Yuan, Charlie F. Ruan, Yucheng Lu, and Christopher De Sa. Coordinating distributed example orders for provably accelerated training. In NeurlPS, 2023.
Ian Covert and Su-In Lee. Improving KemnelHHA. Practical Shapley value estimation via linear regression. In AISTATS, 2021.
Ian Covert, Scott M Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. In NewrlPS, 2020. 1, 2,1, A, D.1

---

Published as a conference paper at ICLR 2025
Ian Covert, Scott Lundberg, and Su-In Lee. Explaining by removing: A unified framework for model explanation. Journal of Machine Learning Research, 22((09):1-90, 2021. 1, 2.1
Carles Domingo-Enrich Raaz Dwivedi, and Lester Mackey. Compress then test: Powerful kernel testing in near-linear time. In AISTATS, 2023. 1, 2.2,
Jon Donnelly, Srikar Katta, Cynthia Rudin, and Edward Browne. The Rashomon importance distribution: Getting RID of unstable, single model-based variable importance. In NeurIPS, 2023.
Raaz Dwivedi and Lester Mackey. Kernel thinning. In COLT, 2021. 1, 2,2, 2,
Raaz Dwivedi and Lester Mackey. Generalized kernel thinning. In ICIR, 2022.
2022. 1, 2.2,
Gabriel Erion, Joseph D Janizek, Pascal Sturmfels, Scott M Lundberg, and Su-In Lee. Improving performance of deep learning models with axiomatic attribution priors and expected gradients. Nature Machine Intelligence, 3(7):620-631, 2021. 1, 2,1,,
Jean Feydy, Thibault Séjourné, François- Xavier Vialard, Shun-ichi Amari, Alain Trouve, and Gabriel Peyré. Interpolating between optimal transport and MMD using sinkhorn divergences. In AISTATS, 2019. 4.5
Sebastian Felix Fischer, Matthias Feurer, and Bernd Bischl. OpenML-CTR23- - a curated tabular regression benchmarking suite. In AutoML, 2023. 4.3, D.2
Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. SHAP-IQ: Unified approximation of any-order Shapley interactions. In NeurlPS, 2023. 1, 1, 2.1
Sahra Ghalebikesabi, Lucile Ter-Minassian, Karla DiazOrdaz, and Chris C Holmes. On locality of local explanation models. In NewrIPS, 2021. 1, A
Alison Gibbs and Francis Edward Su, On choosing and bounding probability metrics. International Statistical Review, 70(3):419-435 2002, 4.5
Albert Gong, Kyuseong Choi, and Raaz Dwivedi. Supervised kereel thinning. NeurlPS, 2024.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(1):723 773, 2012. 2.2, 2, 2.2
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC, 2004.
Peter Hase, Harry Xie, and Mohit Bansal. The out-of-distribution problem in explainability and search methods for feature importance explanations. NeurlPS, 2021.
Moritz Herrmann, F. Julian D. Lange, Katharina Eggensperger, Giuseppe Casalicchio, Marcel Wever, Matthias Feurer, David Rügamer, Eyke Hüllermeier, Anne-Laure Boulesteix, and Bernd Bischl. Position paper: Rethinking empirical research in machine learning: Addressing epistemic and methodological challenges of experimentation. In ICML, 2024. 5
Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. FastSHAP: Real-time Shapley value estimation. In ICLR, 2022. 1,
Bang-Hyun Kim, Jinuk Kim, Scong Joon Oh, Sangdoo Yun, Hwanjun Song, Joonhyun Jeong, Jung- Woo Ha, and Hyun Oh Song. Dataset condensation via efficient synthetic-data parameterization. In ICML, 2022.1
Lukas Klein, Carsten Lüth, Udo Schlegel, Till J. Bungert, Mennatallah El-Assady, and Paul F. Jäger. Navigating the maze of explainable AI: A systematic approach to evaluating methods and metrics. NeurlPS, 2024. 2.1
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In ICMI., 2017. 5
12

---

Published as a conference paper at ICLR 2025
Narine Kokhlikyan, Vivek Miglani, Miguel Martin, Edward Wang. Bilal Alsallakh, Jonathan Reynolds, Alexander Melnikov, Natalia Kliushkina, Carlos Araya, Siqi Yan, and Orion Reblitz- Richardson. Captum: A unified and generic model interpretability library for PyTorch. arXiv preprint arXiv:2009.07800 2020. D.1
Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Byke Hüllermeier. Approximating the Shapley value without marginal contributions. AAAI, 2024.
Mateusz Krzyziñski, Mikolaj Spytek, Hubert Baniecki, and Przemystaw Biecek. SurvSHAP(I): Time-dependent explanations of machine learning survival models. Knowledge- BaseededeeBedddd Systems, 262: 1 10234,, 2023. 2.1
Gabriel Laberge, Ulrich Aivodji, Satoshi Hara, and Foutse Khomh Mario Marchand. Fooling SHAP with Stealthily Biased Sampling. In ICLR, 2023. 1,5,, A
Jeffrey Li, Vaishnavh Nagarajan, Gregory Plumb, and Ameet Talwalkar. A learning theoretic perspective on local explainability. In ICLR, 2021.
Xuhong Li, Haoyi Xiong, Xingjian Li, Xiao Zhang, Ji Liu, Haiyan Jiang, Zeyu Chen, and Dejing Dou. G-LIME: Statistical learning for local interpretations of deep neural networks using global priors. Artificial Intelligence, 31 1::411 10382,, 2023. 1, 2.1, 4.3, F
Chris Lin, Ian Covert, and Su-In Lee. On the robustness of removal-based feature attributions. In NeurIPS, 2023.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In NeurIPS, 2017. 1, 2.1, A, D.1
Daniel D Lundstrom, Tianjian Huang, and Meisam Razaviyayn. A rigorous study of integrated gradients method and extensions to internal neuron attributions. In ICML, 2022. 1,
Julia Moosbauer, Julia Herbinger, Giuseppe Casalicchio, Marius Lindauer, and Bernd Bischl. Ex- plaining hyperparameter optimization via partial dependence plots. In NeurlPS, 2021. D.1
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in Machine Learning, 10(1-2):1-14,, 2017. 3.2,
Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, and Eyke Hüllermeier. Beyond Tree- SHAP: Efficient computation of any-order Shapley interactions for tree ensembles. In AAAI, 2024.
Lars H. B. Olsen, Ingrid K. Glad, Martin Jullum, and Kjersti Aas. Using Shapley values and variational autoencoders to explain predictive models with dependent mixed features. Journal of Machine Learning Research, 23(213):1-51, 2022. 2.1
I Lars Henry Berge Olsen, Ingrid Kristine Glad, Martin Jullum, and Kjersti Aas. A comparative study of methods for estimating model-agnostic Shapley value explanations. Data Mining and Knowledge Discovery, pp. 1-48, 2024. 1, 5.1,
Art B Owen. Statistically efficient thimning of markov chain sampler. Journal of Computational and Graphical Statistics, 26(3):738-744 2017.
Vitali Petsiuk, Abir Das, and Kate Saenko. RISE: Randomized input sampling for explanation of black-box models. In BMVC, 2018.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?" Explaining the predictions of any classifier. In KDD, 2016. 2.1.
Yao Rong, Tobias Leemann, Thai- Thai-Trang Nguyen, Lisa Fiedler, Peizhu Qian, Vaibhav Unhelkar, Tina Seidel, Gjergji Kasneci, and Enkelejda Kasneci. Towards suman-centered explainable AL: A survey of user studies for model explanations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(4):2104-213 2024.
13

---

Published as a conference paper at ICLR 2025
Christian A Scholbeck, Christoph Molnar, Christian Heumann, Bernd Bischl, and Giuseppe Casalic- chio. Sampling, intervention, prediction, aggregation: a generalized framework for model-agnostic interpretations. In ECML PKDD, 2020.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In ICLR, 2018.
Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Distribution compression in near-linear time. In ICLR, 2022. 1, 2.2, 2.2, 4,5
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling LIME and SHAP: Adversarial attacks on post hoc explanation methods. In AIES, 2020. 5
Dylan Slack, Anna Hilgard, Sameer Singh, and Himabindu Lakkaraju. Reliable post hoc explanations: Modeling uncertainty in explainability. In NeurIPS, 2021. 1,
Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert R.G. Lanekriet. Hilbert space embeddings and metrics on probability measures. Journal of Machine Learning Research, (1(50) 2010. 2.2
Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6:1550- 111590-199,,,, 2012. 4.5
Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. Journal of Machine Learning Research, 11:1-18, 2010.
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by proto- types. In ECML PKDD, 2021. A
Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A. Efros. Dataset distillation. arXiv preprint /8/ 10959, 2018.
Borui Zhang, Wenzhao Zheng, Jie Zhou, and Jiwen Lu. Path choice matters for clear attributions in path methods. In ICLR, 2024.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In ICLR, 2021.
Nicky Zimmerman, Alessandro Giusti, and Jérôme Guzzi. Resource-aware collaborative monte carlo localization with distribution compression. arXiv preprint arXiv:2404.020100 2024.
14

---

Published as a conference paper at ICLR 2025
APPENDIX FOR "EFFICIENT AND ACCURATE EXPLANATION ESTIMATION WITH DISTRIBUTION COMPRESSION"
In Appendix B, derive proof's for Propositions & 2. Appendix C. provides code listings for SHAP,
and FEATURE-FFFECTT, analogous to Listing for SAGE. Addi- tional details on the experimental setup are provided in Appendix D. Appendices E, F & report experimental results for the remaining datasets. Appendix H comments on compute resources used for experiments. Appendix provides exemplary visual comparisons of explanations. The code to reproduce all experiments in this paper is available at https: /ggtttb....///ggg/gg com/ waan/hbaaieckka compress- setessss-eeenetee lahen-explain
A Motivation: standard ii.d. sampling in explanation estimation
16
Proof'
17
Implementing CTE practice
18
Experimental setup
19
D.I Explanation hyperparameters
19
D.2 Details datasets and models
19
E CTE significantly improves the estimation of feature attributions & importance
21
CTE improves gradient-basee explanations
23
G Ablations
25
H Compute resources
35
Visual comparison of explanations
36
15

---

Published as a conference paper at ICLR 2025
A MOTIVATION: STANDARD LLI.D SAMPLING IN EXPLANATION ESTIMATION
We find that i.i.d. sampling from datasets is a heuristic often used (and overlooked) various estima- tors of post-hoc explanations. Our work aims first quantify the approximation error introduced by sample then explain, and then propose a method to efficiently reduce it. Below are a few examples from the literature on explainability that motivate the shift our introduced compress then explain paradigm.
In (Laberge al., 2023), we read "For instance. when dataset used represent a background distribution, explainers in the SHAP library such as the ExactExplainer and TreeFxplaine will subsample this dataset by selecting 100 instances uniformly at random when the size of the dataset exceeds 100."
In (Chen & Sun, 2023), we read "[Footnote 1.] We use a random subset of samples for each class in the real implementation, to reduce the computation costs of clustering."
In (Ghalebikesabi et al., 2021), we read "After training a convolutional neural network on the MNIST dataset, we explain digits with the predicted label 8 given a background dataset of 100 images with labels and 8.", as well as "Feature attributions are sorted by similarity according to a preliminary PCA analysis across subset of 2000 samples from the Adult Income dataset, using 2000 reference points."
In (Erion et al., 2021), read "During training. we let k be the number of samples draw to compute expected gradients for each bati-b and "This expectation- basddd formulation lends itself natural, sampling based approximation method: (I) draw samples of x! from the training dataset [...). (2) compute the value inside the expectation for each sample and (3) average over samples." "
In (Van Looveren & Klaise, 2021), read "We also need representative, unlabeled sample of the training dataset.", and in Algorithms and 2: "A sample X = =xI,,..,, Fn from training set."
In (Covert al., 2020), we read "When calculating feature importance, our sampling approximation for SAGE (Algorithm 1) was run using draws from the marginal distribution. We used a fixed set of 512 background samples for the bank, bike and credit datasets, 128 for MNIST, and all 334 training examples for BRCA."
In the shap Python package (Lundberg & Lee, 2017), there is a warning saying "Using 110 background data samples could cause slower run times. Consider using hhap.sample(data,, K) or shap.kmu seeapkmmensteee data, to summarize the background as K samples.", and the documentation mentions "For small problems, this background dataset can be the whole training set, but for larger problems consider using a single reference value or using the kmeans function to summarize the dataset."
16

---

Published as a conference paper at ICLR 2025
B PROOFS
Below, we derive proofs for Propositions & 2.
Proposition (Feature marginalization is bounded by the maximum mean discrepancy between data samples). For two empirical distributions qx, 9% approximated with kernel density estimator k. we have (x,xi - fxx;; 9x) S C. MMDx((g, (z). where O3 denotes constant that bounds the model function f. i.e. VXERP [f(x) C.
Proof. We derive the following inequality:
(f(x):px,) ((xs:xx.)) (Exx~xx) [f(xs Xz)] Exsmex [f(x,; Xz)l)²
(3)
-
-( [xx: Xx)xx (xx)dxxs - / (xx, x3) xx) (xx)dxx)
2
(4)
(px, (xs) - 9x, (xx)) cxxs)) ) Souuch-SShwwrz) $ (f(xe, "
(linearity) = (/ f(xx: xz) x(xx
(5)
dxx / (px, (x5s) qx, (xs)) dx:
(6)
(boundedness)) - C9. / (xx, ax, (xs)) 2 dxs
(7)
2 (Definition 3) == C3. HIMDx(PX..
(8)
Substituting with empirical distributions, we have
[x(xixx)) f(x:i S -MMD HODDx(Ox.. 1g)
(9)
Proposition 2 (Global explanation is bounded by the maximum mean discrepancy between data samples). For two empirical distributions qx. 9% approximated with kernel density estimator k, we have [|G(qx: f.g) G(az: f. f-g)ll2 I Cg MMD (9x, dg). where Cg denotes constant that bounds the local explanation function g. i.e. VxER=]19(<> )l1e S Cg.
Proof. We derive the following inequality:
[|G(px: f.9) G(gx: f.9)112 ||Exxxx lo(X: - Ex lo(X: f. 11
(10)
/ ((xx)xxxxxxxx / ((xx)x((x)xxx
(11)
(linearity) = / (xx 2x (x((x))
(12)
(Cauchy-Schwarz) < / [1ox))1[ / (px(xx) ax (x)xx))²dl dxx
(13)
(boundedness)) - C/. : / (xx(x)) - (x)) dxx dx
(14)
(Definition 3) C 2 (x).
(15)
Substituting with empirical distributions, we have
|[[[xx; f.g) - G(gg; S SC, MMX
(16)
17

---

Published as a conference paper at ICLR 2025
C IMPLEMENTING CTE IN PRACTICE
CTE is simple to plug-into the current workflows for explanation estimation as shown Listing for SAGE, Listing for SHAP, Listing for EXPECTED-GRADIENTS, and Listing for FEATURE- EFFECTS. We use the goodpoints Python package (Dwivedi & Mackey, 2021, MIT license).
model
from goodpoints import compress
ids = compress... compress.compresape compresspp kt (X, kernel taannel_ttyeeb"aussssiie g=4)
x_compressed x[ids]
import shap
masker shap. maskers Independent (X_ (X_compressed)
explainer shap. www.peettttttoexpppppppppppp explanation explainer (X)
(model predict, masker)
Listing 2: Code snippet showing the 3-line plug-in of distribution compression for SHAP estimation.
x, model
from goodpoints import compress
ids compress compresspp_kt (x, kernel_typar "gaussian", g-4)
x "_compressedd X X[ids]
import captum
explainer = cattum.attr.. Iwt...nnnnrrtteraaleenee (model)
import torch
inputs torch.as_tensor (X)
baselines torch.as_tensor (X_compressed)
explanation morch.mean (torch.. stack [I
explainer. (inputs, baselines [[]]], [i]], target=1)
for in range (baselines shape [0])
1), dim=0)
Listing 3: Code snippet showing the plug-in of distribution compression for EXPECTED-GRADDEENS.
x, model
from goodpoints import compress
ids compress compresspp_kt (X, kermel_.ype-=@guusiirr g=4)
x s_compressed X[ids]
import alibi
explainer = alibi explainers PartialDependence (predictor- predict)
explanation explainer explain (X compressed)
Listing 4: Code snippet showing the plug-in of distribution compression for FEATURE- EFFECTSS.
18

---

Published as a conference paper at ICLR 2025
D EXPERIMENTAL SETUP
D.1 EXPLANATION HYPERPARAMETERS
In Section 4, we experiment with explanation methods (6 estimators). Without the loss of generality, in case of classification models, we always explain a prediction for the 2nd class. For SHAP, we use the KERNEL-SHIE
implementations from the shap Python package (Lund- berg & Lee, 2017, MIT license) with default hyperparameters (notably, appemutationss 10 in the latter). For SAGE, we use the KERNEL- SAGE and PERMUTATION implementations from the sage Python package (Covert et al., 2020, MIT license). We use default hyperparameters: notably, a cross-entropy loss for classification and mean squared error for regression. For EXPECTED- GRADIENTS, we aggregate with mean the integrated gradients explanations from the captum Python package (Kokhlikyan et al., 2020. BSD-3 license), for which we use default byperparameters: notably, implement the
and PERMUTATION-
n.steps=50 and wwwchhhddggussseeeeeeeee partial dependence algorithm (Apley & Zhu, 2020; Moosbauer et al., 2021) ourselves for maximum computational speed in of 2-dimensional plots, mimicking the popular open-source implementa- tions. ! We use 100 uniformly distributed grid points for I-dimensional plots and 10x 10 uniformly distributed grid points for 2-dimensional plots.
For TEATURE-EFFECTS,
D.2 DETAILS ON DATASETS AND MODELS
Table 2 shows details of datasets from the OpenXAI (Agarwal et al., 2022, MIT license) benchmark used in Sections 4.1, 4.2 & 4.5. each dataset, there is pretrained neural network with an accuracy of 92% (gaussian), 85% (compas), 74% (heloc), 85% (adult) and 93% (gmsc). We do not further preprocess data; notably, feature values are already scaled to [0, 1].
Table 2: Datasets from OpenXAI with Avalid > 1000 used in experiments.
Dataset
Thtrin
Thyalid
No. classes
gaussian
3750
1250
20
2
compas
4937
1235
7
2
heloc oc
7896
1975
2
adult 36177
9045
13
2
gmsc 81767
20442
10
2
Table 3 shows details of datasets from the OpenML-CC18 (Bischl et al., 2021, BSD-3 license) and BpenML-CTR2. (Fischer et al., 2023, BSD-3 license) benchmarks used in Sections 4.3 & 4.4. We first split all datasets in 75:25 validttit) ratio and left 48 datasets with Ryalid 1000 for experiments. For the 30 smaller (d 32) datasets, we train XGBoost model with default hyperparameters (200 estimators) and explain it with SHAP, SAGE, FEATURE-EFFEE bigger (d 2 32) datasets, we train 3-layer neural network model with (128, 64) neurons hidden ReLU layers and explain it with EXPECTED-GRADIENT
For the 18
We perform basic preprocessing of data: (1) remove features with single or unique values, (2) target encode categorical features, (3) impute missing values with mean, and (4) standardize features.
In general, categorical features can be an issue for clustering and distribution compression algorithms; so are for many explanation algorithms and conditional distribution samplers. Although target encoding worked well in our setup, we envision two additional heuristics to deal with categorical features: (1) perform distribution compression using dataset restricted to non-categorical features, (2) target encode categorical features only for distribution compression.
'ttpp::// /ttc////ocsssoooo seldon, wtt.://www.gggeeee/////////////a hwtp:aaaii.bb..eellanee..... html falibi www.ibiieppppp.. eeppllllinne explainers.. Pa warrtaalppeeddeee
19

---

Published as a conference paper at ICLR 2025
Table 3: Datasets from OpenML-CCI8 and OpenML-CTR23 with Avalid 1000 used in experiments.
Dataset
Task ID
Pitrin
Thyalid
d
No. classes
phoneme
9952
4053
1351
5
wilt
146820
3629
1210
5
cps88wages
361261
21116
7039
6
jungle_chess
167119
33614
11205
6
abalone
361234
3132
1045
8
electricity
219
33984
11328
8
kin8nm
361258
6144
2048
8
california housing
361255
15480
5160
8
brazilian houses
361267
8019
2673
9
diamonds
361257
40455
13485
physiochemical_protte
361241
34297
11433
white_wine
361249
3673
1225
health insurance
361269
16704
5568
11
grid stability
361251
7500
2500
12
adult
7592
36631
12211
14
naval propulsion plant
361247
8950
2984
miami_housing
361260
10449
3483
15
letter
15000
5000
16
26
bank-marketing
14965
33908
11303
16
pendigits
32
8244
2748
16
10
video_tres sileo_transcodin
361252
51588
17196
18
churn
167141
3750
1250
20
kings_county
361266
16209
5404
21
numerai28.6
167120
72240
24080
21
sarcos
361254
36699
12234
21
cpu activity
361256
6144
2048
21
jml
3904
8163
2722
21
wall-robot-navigation
9960
4092
1364
24
361272
14383
4795
28
PhishingWebsiter
14952
8291
2764
30
pumadyn32nh
361259
6144
2048
32
GestureSegmentation
14969
7404
2469
32
satimage
2074
4822
1608
36
texture
125922
4125
1375
40
11
connect-4
146195
50667
16890
42
fps benchmark
361268
18468
6156
43
wave rave_energy
361253
54000
18000
48
theorem-proving
9985
4588
1530
51
6
spambase
43
3450
1151
57
optdigits
28
4215
1405
64
10
superconductivvtt
361242
15947
5316
81
nomao
9977
25848
8617
118
har
14970
7724
2575
561
isolet
3481
5847
1950
617
26
mnist_784
3573
52500
17500
784
10
Fashion-MNIST
146825
52500
17500
784
10
Devnagari-Soon
167121
69000
23000
1024
46
CIFAR_10
167124
45000
15000
3072
10
20

---

Published as a conference paper at ICLR 2025
E CTE SIGNIFICANTLY IMPROVES THE ESTIMATION OF FEATURE ATTRIBUTIONS & IMPORTANCE
We report the differences in MAE and Top-k between CTR and i...d. sampling in Figure 9 (compa s), Figure 10 (he), Figure 11 (gmsc) and Figure 12 (gaussi an). On all the considered tasks, CTF offers notable decrease in approximation error of SHAP and SAGE with negligible computational overhead (as measured by time in seconds).
Kamel5HAP
Consrres
Kam
PermutationSiAp
Permutation nSHAP
aemraa
KorneiSAGE
PermutationSAGE
PermutationAAG
Top-c
KernetSHAP
KernetSHAP
PormutationSNAP
Permutation NSHAP
KameiSAGE
expin
Kerne ISAGE
expain lgrourd truini
SemutatisssAce
10-2
10-1
10
10a
10a
10c
10A 10
10
Figure 9: Extended Figure 2 (1/4). CTE improves SHAP and SAGE estimation by using the compressed samples as background data for the compas dataset. We measure mean absolute error (MAE () between feature attribution and importance values, well the precision in correctly indicating the 3 most important features (Top-k f). Computational resources required to compress a distribution are negligible in the context of explanation estimation. (mean + se.)
KemAWtSAAP
KernetSHAP
PermutationSNWP
Permutatio ISHAP
camoncs
KerneiSAGE
KernetSAGE
AumutatisnSagE
PermtationnAGE
0.000
0.002
0.004 MAE
0.006
0,008
0.5
0.6
0.8
0.9
1.0
Top
PimutatiinnSAAP
NomutatioonSAP
(gr
KernelSAGe
Rere
CONSING saglan
SermutationSAGE
PeruuattionA@E
Time Es]
Time [s]
Figure 10: Extended Figure (2/4). improves SHAP and SAGE estimation the heloc dataset.
21

---

Published as a conference paper at ICLR 2025
KamalSHAP
KameBHAA
PermutationSHAP
Permutal ISSS rSHoPP
campriss
KemelSAGE
Karnel5AGE
simdle
PermutationSAE
PermutationAAE
0.000
KameetSHA
KareelHAPP
ParmutationSHAP
PermutationSHAP
Hep ain (rsunetnu uo (umprosedd
KerneSAAE
KerneSSAGE
PermutationSAGE
PermutationSALL
10
10a
10a
10'
10a
10
10'
107
10'
10
10"
Time
Figure 11: Extended Figure (3/4). CTE improves SHAP and SAGE estimation by using the compressed samples as background data for the gmsc dataset. We measure mean absolute error (MAE !) between feature attribution and importance values, as well as the precision in correctly indicating the most important features (Top-k t). Computational resources required to compress distribution are negligible in the context of explanation estimation. (mean +: se.)
KamelSHAP
KamelSHAP
PermutationSHAp
KernelSAGE
KerneltAGG
SemutationSAcE
samile
PermuatiioSAGe
0.000
0.005
0.010
0.015
0.6
0.7
0.8
1,0
MAE
Top-k
KemalSHAP
KameelHAP
PerMutationSNAP
KorneiSAS
comrnnos expish
SumutationSAGE
ParmuaatioSAGE
10-2
10-1
102
10
10a
107
Time
Figure 12: Extended Figure 2 (4/4). CTE improves SIAAP and SAGE estimation the gaus dataset.
22

---

Published as a conference paper at ICLR 2025
F CTE IMPROVES GRADIENT-BASED EXPLANATIONS
Figure 13 shows the EXPECTED-GRADIENT approximation error for 18 datasets. all cases, CTE achieves on-par approximation error using fewer samples than i.id. sampling, i.e. requiring fewer model inferences, resulting in faster computation and saved resources.
Explanation: Expected Gradients
isolet
1e-3
theorem-proving
mnist_ 784
1e-3
satimage
3
2.4
MAE
1.6
0.8
2
0
0.0
0
32
64
96
128
32
64
96
128
128
256
384
512
32
64
96
128
fos benchmark
Devnagari-Srript
nomao
texture
1.2
1.5
9
MAE
0.8
1.0
2
0.4
0.5
3
0.0
0.0
0
64
128
192
256
128
256
384
512
64
128
192
256
32
64
96
128
wave energy
1e
har
1e
Fashion-MNIST
optdigits
2.4
7.5
1.8
MAE
5.0
1.6
2.5
0.6
0.8
0.0
0.0
0.0
128
256
384
512
32
64
96
128
128
256
384
512
32
96
128
1e-3
connect-4
1e-4
CIFAR 10
1e-3
pumadyn32nh
1e-2
supercanductivity
2.4
MAE
1.2
6
3
0.8
0
0.0
0.0
128
256
384
512
128
192
256
32
64
128
64
128
192
256
samples
N samples
1e-3
spambase
le GestureSegmentation
4.5
Method
MAE
3,0
sample
compress
cluster
0
0.0
32
128
32
64 samples
96
128
N samples
Figure 13: Extended Figure 5. Comparison between CTE, i.i.d. sampling and clustering for EXPECTED-GRADIEST explanations on 18 datasets. We measure mean absolute error (MAE L) between feature attribution values. CTE is not only more efficient and accurate, but also more stable measured with deviation. (mean + sd.)
23

---

Published as a conference paper at ICLR 2025
Model-agnostic explanation of language model. We further experimented with applying CTE to improve the estimation of global aggregated LIME (Ribeiro et al., 2016), aka G-LIME (Li et al., 2023), which is more complex setup that we leave for future work. We aim explain the predictions of DistiBBERT language model? trained on the IMDB dataset' for sentiment analysis. We calculate LIME with & = 10 for all samples from the validation set using A100 GPU and aggregate these local explanations into global token importance with a mean of absolute normalized values (Li et al., 2023), which is the "ground truth" explanation. We then compress the with i.i.d. sampling, CTE, and clustering based on the inputs' text embeddings from the model's last layer (preceding classifier) that has a dimension of size 768. Figure shows results for explanation approximation error and an exemplary comparison between the explanations relating to Figure 1. To obtain these results, we used 8x more samples than the typical compression scenario (still 25x fewer than the full sample) so as to overcome the issue of rare tokens skewing the results. It becomes challenging to compute the distance between the ground truth and approximated explanations as the latter contains significantly fewer tokens (features), opposed to previous experiments where these two explanations always had equal dimensions. Thus, MAE becomes biased towards sparse explanations and popular tokens, Le. an explanation with single token of rell-approximated importance could have error close to O. For context, we measure TV between the discrete distributions of tokens in local explanations before the global aggregation (lower is better). We report results for different token cutoffs, where we remove the tokens from the ground truth explanation by their rarity, which saturates at 5% tokens left.
A)
D)
superbly
wonderfully
06
delightral
superb
excel ent
0.2
wonderful
funniest
terrific
0.95
finest
Taken cutoff
ous
B)
and
.025
never
.020
what
comp ete
.015
.010
say
those
0.85
0.90
Taken cutoff
tedious
dull
0:25
homrib
bering
disappointing
awful
fargettab e
15
campress
disgrace disappointment
0 10
0.90
0.95
0.0 Importance
Token cutoff
Figure 14: CTE for G-LIME of DistiIBERT model classifying IMDB reviews. A) It is not obvi- ous how to measure the distance between global explanations containing different sets of tokens (Token coverage in % w.r.t. ground truth, 1). Therefore, we gradually remove rare tokens from the measurement based on their occurrence in the ground truth explanation (Token cutoff in quan- tiles). B) Measurement of mean absolute error (MAE, L) between aggregated global explanations. C) Measurement of total variation distance (TV, between token occurrences in local explanations before global aggregation. D) We show an exemplary "worst-case" explanation, i.e. with the lowest MAE for cutoff 0.95 where token coverage is over 99%, for both CTE and i.i.d. sampling. For this visualization, we only show the importance of the 5 most positive/negative tokens, and 5 tokens with the importance closest to zero. Explanation approximation error is indicated with transparent bars. Notably, i..dd sampling misses containing any input with an important token "superbly", while CTE misses "disgrace". Sampling overestimates the global importance of tokens "disappointing" "into" and "get", while CTE, for example, overestimates "than" and underestimates "tedious" or "delightful".
mdb
24

---

Published as a conference paper at ICLR 2025
G ABLATIONS
Figures 15-23 report the explanation approximation emoor for 30 predictive tasks. We observe that CTE significantly improves the estimation of FEATURE-DFFECTS in all cases. Another insight is that, on average, CTE provides a smaller improvement over i.i.d. sampling when considering compressing foreground data in SAGE.
Dataset: california _ooriing
1e-2
KeMelSHAP
1e-2
1e-2
KemelSAGE (fg.)
1e-1
Feature
7.5
1.2
MAE
5.0
5.0
0.8
2.5
0.4
0.0
0.0
0.0
64
128
192
256
1e-2
PemutationSHAP
1e-2
Permutation
1e-2
PermutationSAGE (fg.)
samples
7.5
MAE
5.0
5.0
Method
sample
2-
2.5
compress
0
0.0
0.0
cluster
64
128
192
256
64
128
192
256
64
128
192
256
N samples
samples
N samples
Dataset: diamonds
1e-2
KemelSHAP
1e-2
KemelSAGE
1e-2
KemelSAGE (fg.)
le-1
Feature
1.8
1.5
MAE
1.2
4
1.0
0.6
2
0.5
0.0
0.0
64
128
192
256
1e-2
PermutationSHApP
1o-2
PermutationSAGE
1e-2 PermutationSAGE (fg.)
samples
1.2
MAE
0.8
Method
sample
0.4
compress
0.0
cluster
128
192
256
64
128
192
256
64
128
192
256
N samples
samples
N samples
Dataset: grid_ sttbddsttllltyyyy
KernelSHAP
1e-3
KemeeSAGE
KemelSAGE (fg.)
l8
Feature Effects
3.0
1.8
MAE
3.0
1.2
1.5
0.0
32
64
96
128
1e-2
PermutationSHAP
1e-3
PermutationSAGE
1e-2 Pee-PPerutatioonaee (fg.)
samples
4.5
MAE
3.0
Method
1.5
sample
2.5
compress
0.0
0.0
0.0
cluster
32
61
96 samples
128
32
64
96
128
32
64
128
samples
samples
Figure 15: Extended Figure (1/10). CTE improves the explanation approximation error of various local and global removal-bar based explanations. SAGE is evaluated in two variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
25

---

Published as a conference paper at ICLR 2025
Dataset: abalone
1e-2
KerneISHAP
1e-1
KerneISAGE
1e-1
KerneISAGE (fg.)
1e-1
Feature Effects
1.2
7.5
1.2
1.5
MAE
5.0
0.8
0.8
1.0
2.5
0.4
0.4
0.5
0.0
0.0
0.0
96
1e
PermutationSHAp
1e 1
PermutationSAGE
1e
PeermutationAAEE (fg.)
samples
1.2
1.2
7.5
MAE
5.0
0.8
0.8
Method
sample
2.5
0.4
compress
0.0
0.0
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Dataset: adult
1e-3
KemelSHAP
1e-3
KemelSAGE
1e-2
KernelSAGE (fg.)
1e-2
Feature Effects
4.5
1.2
MAE
1.6
0.8
I
3.0
0.8
0.4
1.5
0
0.0
0.0
0.0
64
128 N samples
192
256
1e-3
PermutationSHAP
1e-3
PermutationSAGE
1e-2
PermulationSAGE (fg.)
1.8
1.2
MAE
4-
1.2
0.8
Method
sample
2-
0.4
compress
0.0
0.0
cluster
samples
samples
samples
Dataset: bank-marketing
le
3
KemeeISHA
1e
KemelSAGE
le
2
KernelSAGE (fg.)
le
Feature Effects
6
4.5
2.4
1.2
MAE
0.8
3.0
0.8
0.4
64
128
192
256
1e-3 3
PermutationSHAP
1e-3
PermutationSAGE
1e-2 PermutationSAGE (fg.)
N samples
1.2
1.2
MAE
0.8
Method
sample
2
0.4
0.4
compress
0.0
0.0
cluster
64
128
192
256
64
128
192
256
64
128
192
256
N samples
N samples
samples
Figure 16: Extended Figure (2/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
26

---

Published as a conference paper at ICLR 2025
Dataset: brazilian_ houses
1e-1
KerneiSHAP
1e-1
KerneISAGE
1e1
KerneISAGE (fg.)
1e-1
Feature Effects
1.2
1.8
3.0
9
MAE
0.8
1.2
6
1.5
0.4
0.6
3
0.0
0.0
96
1e 1
PermutationSHAp
1e
PermutationSAGE
1e1
PermutationSAGE (fg.)
samples
1.2
3
MAE
0.8
1.0
2
Method
sample
0.4
0.5
1
compress
0.0
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Dataset: churn
1e-3
KernelSHAP
1e-2 1.2
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-2
Feature Effects
1.8
7.5
5.0
1.2
I
5.0
0.4
0.6
2.5
0.0
0.0
0.0
0.0
32
64
96
128
1e-3
PermutationSHAp
1e-3
PermutationSAGE
1e
2e-2PerrmuattonnAGG (fg.)
N samples
7.5
1.8
MAE
5.0
1.2
Method
sample
2.5
3
compress
0.0
0.0
cluster
samples
N samples
N samples
Dataset:
cps88wages
1e
2
KernelSHAP
le
3
KemelSAGE
le 2
KemelSAGE (fg.)
le
Feature Effects
4.5
7.5
1.2
MAE
3.0
6
5.0
0.8
1.5
3
2.5
0.4
64
128 N samples
192
256
1e-2
PermutationSHAp
1e-3
PermutationSAGE
le 1e-2 Pe-2rtttttaio (fg.)
9
7.5
MAE
3.0
5.0
Method
sample
1.5
3
2.5
compress
0.0
0
0.0
cluster
64
192 N samples
128
256
64
128
192
256
64
128
192
256
N samples
N samples
Figure 17: Extended Figure (3/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
27

---

Published as a conference paper at ICLR 2025
Dataset: cpu_ activity
1e-2
KerneiSHAP
1e-2
KerneISAGE
le-1
KerneISAGE (fg.)
1e-1
Feature Effects
4.5
6
1.5
7.5
3.0
1.0
5.0
1.5
2
0.5
2.5
0.0
0.0
96
1e 2
PermutationSHAp
1e 2
PermutationSAGE
1e
PermutationSAGE (fg.)
samples
1.2
4.5
4.5
MAE
3.0
0.8
Method
sample
1.5 -..
1.5
compress
0.0
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Dataset: jungle chess
1e-2
KernelSHAP
1e-3
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-2
Feature Effects
6
3.0
1.6
1.0
4
0.5
2
0.8
1.5
0.0
0
0.0
0.0
64
128
192
256
1e-2
PermutationSHAP
1e-3
PermulationSAGE
1e- PermulationSAGE (fg.)
N samples
1.8
2.4
6
MAE
1.6
Method
4
sample
0.6
2
0.8
compress
0.0
0.0
cluster
N samples
N samples
N samples
Dataset: electricity
1e
2
KernelSHAP
1e
3
KernelSAGE
le
2
KernelSAGE (fg.)
le
2
Feature Effects
1.5
4.5
2.4
MAE
1.0
6
1.6
3.0
3
0.8
1.5
0.0
64
128
192
256
1e-2
PermutationSHAp
1e-3
PermutationSAGE
1e 1e-2 PemmutttotiiE (fg.)
N samples
4.5
MAE
1.0
3.0
1.6
Method
sample
0.5
1.5
0.8
compress
0.0
0.0
0.0
cluster
64
128
192
256
64
128
192
256
64
128
192
256
N samples
N samples
N samples
Figure 18: Extended Figure (4/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
28

---

Published as a conference paper at ICLR 2025
Dataset: fifa
1e-3
KemmelSHAP
1.2
KereelSAGE
1e-2
KemneSSAEE (fg.)
1e-1
Feature Effects
1.2
7.5
0.8
MAE
5.0
0.8
2.5
0.4
2
0.4
0.0
0.0
192
256
le
PermutationSHAp
le 3
PermutationSAGE
1e
PemutatiioSAGE (fg.)
samples
2.4
4.5
MAE
6
1.6
3.0
Method
sample
0.8
1.5
compress
0.0
cluster
64
128
192
256
64
128
192
256
64
128
192
256
N samples
N samples
N samples
Dataset: health Insurance
1e-2
KernelSHAP
1e-3
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-2
Feature Effects
7.5
3
1
7.5
MAP
1.2
5.0
2
5.0
2.5
1
2.5
0.0
0.0
0
0.0
64
128
192
256
1e-2
PermutationSHAp
1e-3
PermulationSAGE
le- 22-22errutaatinnAAG (fg.)
N samples
1.8
4.5
2.4
MAE
1.2
3.0
1.6
Method
sample
0.6
1.5
0.8
compress
0.0
0.0
0.0
cluster
N samples
N samples
N samples
Dataset: jm1
1e 2
KemeelSHAP
le
2
KernelSAGE
le
2
KernelSAGE (fg.)
le
Feature Effects
1.5
2.4
3
MAE
1.6
1.0
1.6
2
0.8
0.5
0.8
32
64
96
128
1e-2
PermutationSHAP
1e-2
PermutationSAGE
1e PermutationSAGE (fg.)
N samples
1.5
2.4
2.4
MAE
1.0
1.6
Method
sample
0.5
0.8
compress
0.0
0.0
0.0
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Figure 19: Extended Figure (5/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
29

---

Published as a conference paper at ICLR 2025
Dataset: kin8nm
1e-2
KerneISHAP
1e-2
KernelSAGE
1e-2
KemneSAAE (fg.)
1e-1
Feature Effects
1.2
4.5
1.2
MAE
3.0
0.8
4
0.8
1.5
0.4
0.4
0.0
32
96
128
1e-2
PermutationSHAP
1e
PermutationSAGE
1e
PermutationSAGE (fg.)
N samples
4.5 -
MAE
3.0
6
I
Method
sample
1.5
3
2
compress
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Dataset: kings_county
1e-2
KernelSHAP
1e-2
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-1
Feature Effects
2.4
6
3
MAF
0.8
4
2
0.8
0.4
2
0.0
0.0
0
0
64
128
192
256
PermutationSHAP
1e-3
PermulationSAGE
1e-
PermutationSAGE (fg.)
N samples
2.4
9
6
MAE
1.6
6
Method
sample
0.8
3
2
compress
0.0
0
cluster
N samples
N samples
N samples
Dataset: miami housing
1e
2
KernelSHAP
le 3
KernelSAGE
le
2
KernelSAGE (fg.)
le
Feature Effects
1.8
7.5
6
1.8
MAE
1.2
5.0
1.2
0.6
2.5
0.6
32
64
96
128
1e-2
PermutationSHAP
1e-3
PermutationSAGE
1e-2 PermutationSAGE (fg.)
N samples
1.8
MAE
Method
sample
0.6
2
2
compress
0.0
cluster
32
96 N samples
64
128
32
64
96
128
32
64
96
128
N samples
N samples
Figure 20: Extended Figure (6/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
30

---

Published as a conference paper at ICLR 2025
Dataset: naval_propulsion _pantt
1e-1
KerneiSHAP
1e-2
KernelSAGE
1e-2
KerneISAGE (fg.)
2.4
Feature Effects
2.4
1.6
MAE
0.8
1.6
6
0.4
0.8
3
0.8
0.0
0.0
96
1e 1
PermutationSHAp
1e 2
PermutationSAGE
1e
PermutationSAGE (fg.)
samples
1.2
2.4
9
MAE
0.8
1.6
6
Method
sample
0.4
0.8
3
compress
0.0
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Dataset: pendigits
1e-3
KernelSHAP
1e-2
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-2
Feature Effects
7.5
1.2
1.5
6
MF
5.0
0.8
1.0
0.4
0.5
2
0.0
0.0
0.0
0
32
64
96
128
1e-3
PermutationSHAP
1e-2
PermutationSAGE
1e-2 PermutationSAGE (fg.)
N samples
7.5
1.2
1.5
MAE
5.0
T
0.8
1.0
1
Method
sample
2.5
0.4
0.5
compress
0.0
0.0
0.0
cluster
N samples
N samples
N samples
Dataset: numerai28.6
le
3
KernelSHAP
1e
4
KernelSAGE
1e
3
KerneSAGE (fg.)
le
2
Feature Effects
1.2
4.5
1.5
MAE
2
0.8
3.0
1.0
0.4
1.5
PermutationSAGE (fg.)
128
256 N samples
384
512
1e-3
PermutationSHAP
1e-4 1.2
PermutationSAGE
1e-3
4.5
4.5
MAE
3.0
0.8
3.0
Method
sample
1.5
1.5
compress
0.0
0.0
0.0
cluster
128
256
384
512
128
256
384
512
128
256
384
512
N samples
N samples
N samples
Figure 21: Extended Figure (7/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
31

---

Published as a conference paper at ICLR 2025
Dataset: phoneme
1e-2
KerneiSHAP
1e-3
KerneISAGE
1e-2
KerneISAGE (fg.)
1e-2
Feature Effects
7.5
MAE
1.6
5.0
3.0
4
0.8
2.5
1.5
2
0.0
0.0
96
1e-2
PermutationSHAp
1e
PermutationSAGE
1e
PermutationSAGE (fg.)
samples
7.5
4.5
2.4
MAE
1.6
5.0
3.0
Method
sample
0.8
2.5
1.5
compress
0.0
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
N samples
Dataset: physiochemical_pee protein
1e-2
KernelSHAP
1e-1
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-1
Feature Effects
7.5
1.5
3
MF
5.0
1.0
4
2
0.0
0.0
0
0
64
128
192
256
1e-2
PermutationSHAp
1e-1
PermulationSAGE
1e-2 Permutattiaa (fg.)
N samples
9
MAG
1.0
Method
sample
0.5
2
compress
0.0
0
cluster
N samples
N samples
N samples
Dataset: sarcos
1e
2
KernelSHAP
le 2
KernelSAGE
le 2
KernelSAGE (fg.)
le
Feature Effects
1.5
1.8
1.8
MAE
1.0
1.2
1.2
0.5
0.6
0.6
64
128
192
256
1e-2
PermutationSHAP
1e-3
PermutationSAGE
PermutationSAGE (fg.)
N samples
1.8
4.5
MAE
1.2
3.0
Method
sample
0.6
1.5
compress
0.0
0.0
0
cluster
64
192 N samples
128
256
64
192 N samples
128
256
64
128
192
256
N samples
Figure 22: Extended Figure (8/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
32

---

Published as a conference paper at ICLR 2025
Dataset: wall-robottnaviigaton
1e-3
KerneISHAP
1e-3
KerneISAGE
1e-2
KerneISAGE (fg.)
1e-1
Feature Effects
1.2
1.5
MAE
1.0
0.8
2
0.5
0.4
0.0
32
96
1e-3
PermutationSHAP
1e 3
PermutationSAGE
1e
PermutationAGE (fg..)
samples
9
MAE
Method
6
sample
compress
cluster
32
64
96
128
32
64
96
128
32
64
96
128
N samples
N samples
samples
Dataset: white wine
1e-2
KernelSHAP
1e-2
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-1
Feature Effects
4.5
1.2
6
2.4
I
1.6
MAP
0.8
4
1.5
0.4
2
0.8
0.0
0.0
0
0.0
32
64
96
128
1e-2
PermutationSHAp
1e-2
PermulationSAGE
Me-2PerrmtaatinnAAG (fg.)
N samples
4.5
1.2
MAE
3.0
0.8
4
Method
sample
2
compress cluster
0.0
0.0
0
N samples
N samples
N samples
Dataset: wilt
1e
2
KemelSHAP
1e
KemelSAGE
le 2
KerneSSAGE (fg.)
le 2
Feature Effects
3.0
MAE
1.5
2
32
64
96
128
1e-2
PermutationSHAP
1e-
PermutationSAGE
1e-2 PermutationSAGE (fg.)
samples
3.0
MAE
Method
1.5
sample
compress
0.0
cluster
32
64
96
128
32
96 N samples
64
128
32
96 N samples
64
128
samples
Figure 23: Extended Figure (9/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
33

---

Published as a conference paper at ICLR 2025
Dataset: video_tree tettttttttoooingggo
1e-2
KerneISHAP
1e-2
KerneISAGE
1e-2
KerneISAGE (fg.)
1e-1
Feature Effects
1.8
4.5
1.5
MAE
1.2
0.8
3.0
1.0
0.6
0.4
1.5
0.5
0.0
0.0
0.0
384
1e
PermutationSHAp
1
PermutationSAGE
1e-
PermutationSAGE (fg.)
samples
4.5
4.5
1.8
MAE
1.2
3.0
3.0
Method
sample
0.6
1.5
compress
cluster
128
256
384
512
128
256
384
512
128
256
384
512
N samples
N samples
N samples
Dataset: letter
1e-3
KernelSHAP
1e-3
KernelSAGE
1e-2
KernelSAGE (fg.)
1e-2
Feature Effects
1.2
2.4
3.0
3
MAE
2
0.8
1.6
1.5
1
0.4
0.8
0.0
0
0.0
0.0
64
128
192
256
1e-3
PermutationSHAP
1e-3
PermulationSAGE
1e
2ee-2PermtaationAAG (fg.)
N samples
4.5
3
1.2
MAE
3.0
2
0.8
Method
sample
1.5
1
0.4
compress
0.0
0.0
cluster
N samples
N samples
N samples
Dataset: PhishingWebsites
1e 3
KernelSHAP
le
3
KernelSAGE
le 2
KernelSAGE (fg.)
1e
Feature Effects
6
1.2
1.2
MAE
4
0.8
0.8
0.4
0.4
32
64
96
128
1e-3
PermutationSHAp
1e-3
PermutationSAGE
1e-3 PermutationnAGE (fg.)
N samples
7.5
9
2.4
MAE
5.0
Method
sample
2.5
0.8
3
compress
0.0
0.0
cluster
32
96 N samples
64
128
32
64
96
128
32
64
96
128
N samples
N samples
Figure 24: Extended Figure 6 (10/10). CTE improves the explanation approximation error of various local and global removal-based explanations. SAGE is evaluated in variants that consider either compressing only the background data (default), or using the compressed samples as both background and foreground data (as indicated with "fg."). (mean + sd.)
34

---

Published as a conference paper at ICLR 2025
H COMPUTE RESOURCES
Experiments described in Sections 4.1, 4.2 & 4.5, and Figure 4, were computed on a personal computer with an M3 chip as justified in the beginning of Section Experiments described in Sections 4.3 & 4,4 were computed on a cluster with 4x AMD Rome 7742 CPUs (256 cores) and 4TB of RAM for about 14 days combined.
35

---

Published as a conference paper at ICLR 2025
1 VISUAL COMPARISON OF EXPLANATIONS
We provide exemplary visual comparisons between ground truth explanations and those estimated on an i.i.d. and compressed sample in experimental settings.
Figure 25 shows a comparison for KERNEL-SAGE explaining an XGBoost model trained on the compas dataset. Figure 26 shows comparison for PERMUTATION-SIE network trained on the compas dataset, and Figure 27 shows the same on the heloc dataset. Note that we show all local explanations at once (not to hand-pick single one). which might falsely look like a good approximation "on average" when in fact the attribution values in specific cases differ significantly. Figure 28 shows a comparison for FEATURE-FFFECT explaining an XGBoost model trained on the gr d_stddbsblee ity dataset, and Figure 29 shows the same on the mi ami, hoou ing dataset. Figures 30 31 show exemplary visual comparisons for EXPECTED-GRADIENT explaining convolutional neural network trained the CIFAR_10 0 dataset.
explaining neural
Ground truth explanation estimated an Mil sample
Explanation estimated on an i... sample
twa,year rocid-
two_ycar rOCid
Charge dogrec
age-
ag
charge degree
sex Female-
sex Female-
length_ot, stay
bnngh_ot_stay
0.00
0.04
0,50
SAGE
SAGE
Ground truth explnatiion estimated on a full sample
Explanation estimated on comprested sample
priers count
priors court
race
race
yea_ recid
yon_year_ae rerid
c cang dogres. F
cacharge dogres,
ago
age-
sex, Female
sex Female
longthoot_stay
length_ot_co stay
-0.04
0.02
0.06
Figure 25: Comparison between KERNEL--SAGE estimated the full (left), sampled (right top), and compressed (right bottom) subsets of the compas dataset. MAE introduced by i.i.d. sampling equals 0.0050 for the importance values and 0. 0.00033 for their standard deviations (error bars), by CTE is 0.0011 1 and 0.00007 respectively, and so the relative improvement of CTE is 78% in both cases.
Ground truit acolatation retimatedd on ful ramble
Hig
Eaple on entimatted on an U.d. sample
In2_yer-ee0 2000
Ierght
coppps
3167 riu
5867 (rroac model suppptt
Ground wuth exclanation estimated on sarrep
Explarat on estimated on comp sample
CoMpe fo
CoN secFemee
secfumee
Figure 26: Comparison between all local PERMUTATION-SHET explanations estimated on full (left), sampled (right top), and compressed (right bottom) subsets of the compas s dataset. MAE introduced by i...d. sampling equals 0.0227, by CTE is 0.0032, and so the relative improvement of CTE is 86%.
36

---

Published as a conference paper at ICLR 2025
touc estinaced sample
Exploration estimaces sampre
Nardetindderhaate
HS raaMaattaaarrneeee/oo
Numiaa www.krtttaiiiiieeoooooooooo
leation
Marteuthades
Nartotuteetss
Nettereeeeet Bustin
boag vake mudet suppptt
wide vake divpact surpett
Ground tuuh explanation esterated Satsamppe.
Exploration estiaced in comppessedd somple
Aeropiett io
intrrudeckent nutr
Ha www.aacattttooeeeeeieaa..oo
Fecantruraliide
Marthaded Seeee We soller
Marthaks Wewee offire
MadDeggver
Figure 27: Comparison between all local PERMUTATION-SHAN explanations estimated on full (left), sampled (right top), and compressed (right bottom) subsets of the heloc dataset. MAE introduced by i..dd. sampling equals 0.0087, by CTE is 0.0053, and so the relative improvement of CTE is 38%.
37

---

Published as a conference paper at ICLR 2025
Feature taul
Feature tau2
Feature tauB
Feature toue
Festure effect
0.02
-1
Reature pl
Feature p2
Reature p3
Footurn ra p4
0.04
eeatureefect
Explanation
lid.
Feature gl
Feature g2
Feature g3
Feature = g4
0.94
Feature effect
0.00
Festure value
Feeture value
Festure value
Feature value
Figure 28: Comparison between FEATURE-EFFECTS explanation estimated on the full (Ground truth), sampled (i.i.d),, and compressed (CTE) subsets of the gi d s stability dataset. MAE introduced by i.i.d. sampling equals 0.0032, by CTE 0.0007, and so the relative improvement of CTE is 79%.
Feature LATITUDE
Feature LONGITUDE
Feature
LLD_ SOO.OOOOOOTOOO Feature TOT_IVG OOT_IV__ARFA ARFA
effect
600000
200000
Feature SPE C FEAT VAL
Feature RAIL_DIST
Feature OCEAN_DIST
Reature WWTEERDDSST
effect
600000
400000
200000
2
Explanation
CTE
SUBCNTR
age
iid.
truth
Feature effect
600000
400000
200000
Festure value
Feature avno60plus
Feature month, sold Feature = structure, quality
effect
600000
408000
200000
-2
Feature
Feature value
Festure
Figure 29: Comparison between PEATURE-EFFECTT explanation estimated on the full (Ground truth), sampled (i.id.), and compressed (CTE) subsets of the mi ami whousing inn dataset. MAE introduced by i...d. sampling equals 49766, by CTE is 14031, and so the relative improvement of CTE is 71%.
38

---

Published as a conference paper at ICLR 2025
Prediction: horse
Prediction: horse
lidd
truth
Ground
0.25
0.00
0.0202
0.0135
-13
-15
-10
Ground truth
CTE
0.5
Ground truth
CTE
0.0
0.0
MAE D. 0.0279
MAE dood
MAE 0.0207
-0.5
MAE 0.0151
MAE o 0000
MAE o 0.0092
-1.0
Prediction: car
Prediction: car
0.50
Ground truth
CTE
LLd.
Ground truth
CTE
0.25
MAE
MAE 0.0193
0.02440
0000
MAE 0.0177
Prediction:
Prediction: ship
1.0
1.0
Ground truth
Ground
--0.
0.0153
0.5
explanations estimated on the full (Ground truth), sampled (i.idd),, and compressed (CTE) subsets of the CIFAR.10 dataset. The bottom rows visualize the differences (MAE L) from the ground truth explanation. All predictions are correct.
Figure 30: Comparison between
39

---

Published as a conference paper at ICLR 2025
0.4
Ground truth
CTE
Ground truth
CTE
02
0.0
0.0
-02
MAE D. 02221
MAE 00o0
MAE 0.0141
MAE 0.0249
MAE o 0000
MAE 0.0172
-0.5
-0.4
Prediction: ship
Prediction: deer
0.4
1.0
LLd
Ground truth
CTE
0.5
L.d.
Ground truth
CTE
02
MAE 0.04122
MAE 0.0000
0.0323
MAE 0.0088
-15
Comparison between EXPECTED-GRADIENT explanations estimated on the full (Ground truth), sampled (i.i.d.), and compressed (CTE) subsets of the CIFAR_10 0 dataset. The bottom rows visualize the differences (MAE !) from the ground truth explanation. All predictions are wrong
Figure 31:
40


Reviews:
[{"review_id": "DRefZ9biMH", "reviewer": "Reviewer_fa33", "summary": "the paper introduces CTE uses distribution compression through kernel thinning to obtain a data sample to better and more efficiently approximate the marginal distribution. This method is recommend to significantly reduce the computational complexity of attribution-based methods such as SHAP and SAGE.", "questions": "line 184 - definition 4 - it is not clear what is the output f this function and how do you compare it with for calculation of MAE. how the explanation error is defined and how it is calculated? as far as I understand the mean absolute error is measured based on the difference between the assigned values to  features of explanation from the SHAP  with iid and CTE. but to it is not clear that without iid how do you calculate the feature values. if SHAP + i.i.d sampling is not the baseline, the please clearly explain how you calculated the baseline feature values? what is the baseline for that you compared the iid and cte sampling? (Table 1)", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This approach significantly reduces the computational complexity of SHAP and SAGE.", "weaknesses": "line 53 - \"We introduce a new paradigm for estimating post-hoc explanations based on a marginal distribution\" ---> The main contribution of paper is not clearly described. From the introduction, reader might get the idea that you are proposing a new explanation method that employs KT, but as we go further into the paper, the tone of authors changes and they focus on the effectiveness their approach for Kernel SHAP and SAGE. \n\n\nthe idea of this paper needs to be more clearly stated. From my understanding the paper attempts to improve the computation time of SHAP and SAGE using Kernel thinning. The Kernel Thinning is proposed to better select the samples for the feature attribution explanation. The idea seems interesting and this can help with the Shapely and Sage method, but this approach is only specific to these explanation method that are based on the selection of subsets of data. \n\nThe experimental evaluation is heavily focused on MAE with  the explanation as \"...\". I wonder if this approach is the main criteria that paper investigated, what is the main baseline that they compare with to obtain the explanation error. If the explanation error is calculated with the SHAP with the iid sampling, so what does Table 1 mean. because in this table the paper explains that from the iid sampling the MAE of explain improved to something that is achieved with CTE.\n\n\nAlso the paper only explored the Gaussian Kernel. Why that choice? why not exploring other kernels? What is the theoretical aspect of Gaussian that advantages your approach?\n\nalso, I wanted to see some examples of how the trained explainer using your method performs for image and examples of IMDB dataset. The paper heavily focuses on the MAE without providing any example to show the qualitative comparison of generated explanation\n\n\nThe main purpose of KT, is reducing the computational complexity and the quality of generated explanation, but since this method is focused on the data attribution concept, I was expecting see a comparison between the KT and Influence Function in extracted explanations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vgJeLhLgqA", "reviewer": "Reviewer_ry7y", "summary": "The paper proposes distribution compression as an alternative to iid sampling for explanation estimation. The proposed approach is supported by theoretical guarantees. It also improves computation cost while still achieving errors comparable with iid sample empirically.", "questions": "-", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is solid and supported by theoretical bounds on the error.\n\n- This topic is outside my expertise but I was able to follow the paper. So I think the authors did a good job summarizing the related work and providing relevant background information.", "weaknesses": "- I overall enjoyed reading this paper. \n\n- I am not an expert on this area. But it looks like going from iid sampling (the paper's main comparison point) to this more complicated CTE framework (based on kernel thinning) is a big step. I am wondering if there are any other baselines in between these two extremes. For instance, a sampling strategy but not exactly uniform? If there are such baselines, I think it would be good to see a comparison against them too to understand the tradeoff between how complicated the compression scheme is vs how much we can reduce the data size vs the error.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GsR218megZ", "reviewer": "Reviewer_dB4i", "summary": "This paper tackles the problem of efficiently approximating the marginal distribution that is often used in post hoc explanation methods. The authors propose using kernel thinning to obtain a compressed sample of the \"background\" samples that are used to empirically estimate the marginalization. The proposed compress then explain method is then empirically demonstrated to require orders of mangitude fewer samples to achieve on-par explanation approximation error compared to i.i.d sampling which is generally utilized.", "questions": "I'd be interested in hearing the authors' thoughts on the second \"weakness\" above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. The biggest strength of the paper is the thoroughness of the experiments. For a paper that is largely an empirical demonstration it is great to see the rigour that clearly went in to the experiment section. The proposal is a neat application of an existing technique in a new domain.", "weaknesses": "While the experiment section is rigorously presented, there's room for improvement in presentation - specifically the figures and figure captions. Most of the figures have multiple plots and a single caption. It'd be better to label the sub-plots in each figure as a, b, c,... and then use the caption to describe each figure succinctly. This allows the reader to look at the figures and understand them, rather than having to jump back and forth between the main text and figures.\n\nThe other weakness is the fact that this is largely an application of an existing method for efficient sampling. It *is* still a useful contribution to apply this method to explanations, this could be an even better publication if the sampling method was also improved specifically for post explanation methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)