SHAP-IQ: Unified Approximation of any-order Shapley Interactions
Authors: Fabian Fumagalli
Maximilian Muschalik
Patrick Kolpaczki
Eyke Hüllermeier
Barbara Hammer
Venue: NeurIPS 2023 poster (2023)
Keywords: Explainable Artificial Intelligence
Feature Interaction
Shapley Interaction
Shapley Value
TL;DR: A novel model-agnostic, sampling-based approximation technique for any Shapley Interaction Index that satisfies the linearity, symmetry and dummy axiom.

Abstract: Predominately in explainable artificial intelligence (XAI) research, the Shapley value (SV) is applied to determine feature attributions for any black box model. Shapley interaction indices extend the SV to define any-order feature interactions. Defining a unique Shapley interaction index is an open research question and, so far, three definitions have been proposed, which differ by their choice of axioms. Moreover, each definition requires a specific approximation technique. Here, we propose SHAPley Interaction Quantification (SHAP-IQ), an efficient sampling-based approximator to compute Shapley interactions for arbitrary cardinal interaction indices (CII), i.e. interaction indices that satisfy the linearity, symmetry and dummy axiom. SHAP-IQ is based on a novel representation and, in contrast to existing methods, we provide theoretical guarantees for its approximation quality, as well as estimates for the variance of the point estimates. For the special case of SV, our approach reveals a novel representation of the SV and corresponds to Unbiased KernelSHAP with a greatly simplified calculation. We illustrate the computational efficiency and effectiveness by explaining language, image classification and high-dimensional synthetic models.

SHAP-IQ: Unified Approximation of any-order Shapley Interactions
Fabian Fumagalli" Bielefeld University, CITEC D-33619, Bielefeld, Germany ffumaalll@ttchhaak imi-bielefeld.de
Maximilian Muschalik LMU Munich, MCML Munich D-80539, Munich, Germany 1mu de
maximiliam htt.mmiw........aaaa.a.a.....aa.
Patrick Kolpaczki Paderborn University D-33098, Paderbom, Germany patrick. kolpaczki @upb. de
Eyke Hüllermeier LMU Munich, MCML Munich D-80539, Munich, Germany eyke@ifi. 1mm.dd de
Barbara Hammer Bielefeld University, CITEC
D-33619, Bielefeld, Germany
bhamme@@tehffak mii-bielefelddde
Abstract
Predominately in explainable artificial intelligence (XAI) research, the Shapley value (SV) is applied to determine feature attributions for any black box model. Shapley interaction indices extend the SV define any-order feature interac- tions. Defining unique Shapley interaction index is an open research question and, so far, three definitions have been proposed, which differ by their choice of axioms. Moreover, each definition requires a specific approximation technique. Here, we propose SHAPley Interaction Quantification (SHAP-IQ), an efficient cumpling-bssed approximator to compute Shapley interactions for arbitrary car- dinal interaction indices (CII), i.e. interaction indices that satisfy the linearity, symmetry and dummy axiom. SHAP-IQ is based on novel representation and, contrast to existing methods, we provide theoretical guarantees for its approx- imation quality, as well as estimates for the variance of the point estimates. For the special case SV, our approach reveals novel representation of the SV and corresponds to Unbiased KemelSHAP with greatly simplified calculation. We illustrate the computational efficiency and effectiveness by explaining language, image classification and high-dimensional synthetic models.
Introduction
Feature attributions a prevalent approach interpret black box machine learning (ML) models 7 However, in many real-world applications, such as understanding drug-drug interactions, mutational events complex language models, quantifying interactions between features is essential, too
48
23 43 Feature interactions provide a more comprehensive explanation, which can be
seen as enrichment feature attributions B 39 40). While feature attributions quantify the contribution of single features to the model's prediction or performance, feature interactions quantify the contribution of a group of features the model's prediction or performance.
denotes equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

movie review excerpt (imput)
sentiment (output)
I have never forgot this movic. All these years and has remained in my life.
0.990
(positive)
interactions
interaction scores
never
forgot
this
(order I)
0.85
1.30
0.17
never
Torgot
(order 2)
1.993
never this
(order
0.924
forgot this
(order 2)
0.080
never forgot this
(order 3)
0.412
Figure Interaction scores for movie review excerpt presented sentiment analysis model.
In this work, we are interested in feature interactions that make use of the Shapley value (SV) and its extension to Shapley interactions. The SV is concept from cooperative game theory that has been used, apart from feature attributions [7]. as a basis for many Shapley-ban -hased explanations [21 15 49 It distinguishes itself through uniqueness given set of intuitive axioms. A number of approaches extend Shapley-based explanations to feature interactions 17 39 40 Yet, in contrast to the SV, "natural" extension of the intuitive set of axioms for unique Shapley interaction index is less clear. Moreover, its efficient computation is challenging and, so far, approximation approaches are specifically tailored to the particular definition.
In this paper, we consider a more general class of interaction indices, known as cardinal interaction indices (CII) (17). which covers all currently proposed definitions and all other that satisfy the (generalized) linearity, symmetry and dummy axiom. We present SHAPley Interaction Quantification (SHAP-IQ). sampling- based unified approximation method. It is substantiated by mathematical guarantees and can be applied to any CII to approximate any-order interaction scores efficiently.
Contribution. Our main contributions include:
We consider general form of interaction indices, known as CII (Definition 333 and establish a novel representation (Theorem 4.1), which we utilize to construct SHAP-IQ (Definition
4.7
efficient sampling- -aased estimator
We show that SHAP-IQ is unbiased, consistent and provide a general approximation bound (Theorem 4.3). We further prove that SHAP-IQ maintains the efficiency condition for and the Shapley Taylor Interaction Index (39 (Theorem
n-Shapley Values 3
For the SV, we find a novel representation (Theorem 4.4 We further prove that SHAP-IQ is linked to Unbiased KernelSHAP 8 (Theorem 4.5) and greatly simplifies its representation.
We use SHAP-IQ to compute any-order n-Shapley Values on different ML models and demonstrate that it outperforms existing bascline methods. We further contrast different existing CIIs and compare SHAP-IQ to the corresponding baseline approximation method.
2
Related Work
The Shapley Interaction Index (SII) 17 its efficiency preserving aggregation as n-Shapley Values (n-SII) 3] the Shapley Taylor Interaction (STI) 39 and the Faithful Shapley Interaction Index (FSI) 40 offer different ways of extending the SV interactions, which extend on the linearity, symmetry and dummy axiom to provide uniquely defined interaction index. SII and STT extend on axiomatic properties the weighted sum for SV [35) whereas FSI extends on the axiomatic properties the
Shapley interaction the solution to weighted least square solution 32 33
"The shapig package extends on the well-known shap library and can be found at httttps://yypi... org/ project/shapiq/

---

In the field of cooperative game theory, interactions have also been studied from theoretical perspective as the solution of a weighted least square problem and the sum of marginal contributions with constant weights, which both yield a generalized Banzhaf value [18 16
In the MI. community, interactions of features have been studied from a practical perspective for text
[29] and image [4]] data, for specific models, such as neural networks [42 10
36 20 or tree based
models [25]. Other concepts of interactions have been discussed in [43 using marginal contributions,
from a statistical perspective with functional decomposition with interaction terms
28 and improved white box models
24
To approximate SII and STI, a permutation-basee method 39 40 as an extension of ApproShapley was suggested, whereas FSI relies on kernel-bused approximation, similar to KemelSHAP
[
26 which utilizes a representation of the SV as the solution of a weighted least square problem consider general CIIs, which subsume all of the above mentioned measures, and we propose a generie approximation technique, which can be accompanied by mathematical guarantees. In case of the SV, our approximation of the CII is related to Unbiased KemeeSHHP [8), which is a variant of KernelSHAP [26). It is further related to stratified sampling approximations for the SV and our sampling approach can be seen as flexible framework find the optimum allocation for each stratum 4
6 Unlike these specific approaches,
3 The Cardinal Interaction Index (CII) and Shapley-based Explanations
In this section, review Shapley-based explanations and introduce the CII, which we aim to approximate in Section 4 We further introduce existing baseline methods for specific CIIs and Unbiased KemelSHAP for the SV, which is linked to our proposed method.
Notations. We refer to the model behavior on a set of features D = (1,...,,d as function v: P(D) - R. where PDD) refers to the power set of D. We denote vo (T) == ((T) =(0), which is the default setting in game theory and also known as set function [17] The subsets S S D refer to the set of features (or players in game theory) of which the interaction is computed, where we use lower case letters for the cardinality, i.e. ;= SS]. The maximum order interaction of interest is denoted with sy and we use the set To == {T C D k S t S d - kJ and the set of interactions Sa, = (S C D s I sp. S + 0}. For a subset T S D. we refer to the binary representation as ZT = (2.....,. za) E 1J, with 2; = 1(i T) for 1,.....4. d, where refers to the indicator
function. We further denote the Shapley kernel
26 as ((() = (1=)
Removal-based explanations [9] consider model that is trained on d features, where the goal to examine model behavior that is defined on a subset of features. The model behavior for a subset of features could, for instance, be particular model prediction for one input (local explanation) or an overall measure of model performance (global explanation), if only this subset of features is known [9]. To quantify the contribution for individual features, the change in model behavior is evaluated, if the feature is removed from the model. To restrict a ML model on a subset of features, different feature removal techniques have been proposed, such marginalization of features or retraining the model [9] To quantify the impact of a single feature i E D on the model behavior it is then intuitive to compute the difference 0% (T) u(T U {i}) - ((T) for subsets T C D \ (i). For a distinct pair of features (i.j) with i.j E D, a natural extension is %1, (7)= U (i,j)) ((T) (T) K for T E DV (i,5), i.e. subtracting the contribution of single features from the joint impact of both features. The following definition
generalizes this recursion and is known as discrete derivative or S-derivative [14.
Definition 3.1 (Discrete Derivative [4). For S C D the S-derivative of v at T C D S
8% (T) = E(-I)-
LCS
To obtain an attribution score, the marginal contributions on different subsets T C D S are aggregated using a specific summary technique. In this work, we are interested in the approximation and extension of one particular summary technique for single features i D. called the Shapley value (35), independent of model behavior and feature removal.
Definition 3.2 (Shapley Value (SV) (35). The is (5) ΣTSDA() (d-t-1)!4 8% (T)( ie) D.
3

---

The SV is the unique attribution method that fulfills the axioms: symmetry (attributions are inde- pendent of feature ordering). linearity (in terms of the model behavior v), dummy (if feature does not change then its attribution is zero) and efficiency (the sum of attributions are equal to vo (D) 35 However, the SV does not give any information about the interactions between two or more features. A suitable extension of the SV for interactions of features S S D remains an open question, as different axiomatic extensions have been proposed [17 39 40]. this work, we thus consider a broad class of interaction indices, known as CIIs [1 40 which subsumes popular choices.
Definition 3.3 (Cardinal Interaction Index (CII) 17 ). A CII is an interaction index of the form
TTh (S)
Σ (,(()''(TT) with weights mt(() (t) ,,...,80 80 and = =....., 8. TCDYS
Remark 3.4. It was shown that every interaction index satisfying the generalized linearity, symmetry and dummy axioms be represented CHI (17]. If Ei= (d=") 1, then the CII is also referred to as a cardinal-probabiii interaction index (CPII) [4).
In this paper, we present unified approximation technique for arbitrary CIIs.
3.1 Shapley Interaction Index (SIT) and other CITs
In the following, we introduce prominent examples of ClIs. For further details on the axioms and exact definitions, refer to the appendix. The SII [17] is a direct extension of the SV, that relies on an additional recursive axiom to obtain a unique CII.
Definition 3.5 (Shapley Interaction Index (7I) The SH is CHI defined as
m (T) and my m()(()= (d (d-t-s)ll (d 1)!
(S)
Σ TEDYS
has been shown that the SII is a CPII [4]. In contrast to the SV, the SII does not fulfill the efficiency axiom, which is desirable property in the context of ML. Therefore extension of SII, well as other interaction indices have been proposed.
n-Shapley Values (n-SII) and other interaction indices. The efficiency axiom for interaction indices of maximum interaction order S So < d requires that the sum of (S)(S) up to order 8o equals (D).
Definition 3.6 (Efficiency 13 40
A CII is efficient of order sp, if EsEs, Im(()= = vo(D). where
Sap is the of interactions up order 80-
In 3. an aggregation of SII was proposed to obtain n- n-SII (") of order so that satisfies efficiency. Other axiomatic approaches directly require efficiency together with the linearity, symmetry and dummy axioms, and omit the recursive axiom of SII. However, in contrast to the SV, this axiom alone does not yield a unique interaction index 39 40 The STI 39 requires the efficiency axiom and an additional interaction distribution axiom. On the other hand, the FSI 44 requires the efficiency axiom and the faithfulness property, that relates the interaction index to solution of a constrained weighted least square problem. The choice of axioms of SII (n-SII), STI and FSI yield a unique interaction index that reduces to the SVs for 8q = 1. For FSI, it was shown that the top-order interactions define CPII 44) Proposition 21], which is also easily verified for STI. All orders of interactions of FSI and STI can general be represented as a CII, as they fulfill the linearity, symmetry and dummy axioms [17 Proposition 5]. However, it was noted that for FSI simple closed-form solution for lower-order interactions terms of discrete derivatives remains unclear [40] Lemma 70].
3.2 Baseline Approximations of SII, STI and FSI.
By definition, the number of evaluations of in I, which constitutes the limiting factor in ML, grows exponentially with d and thus, in practice, approximation methods are required. Currently, there does not exist an approximation for the general CII definition, as each index (SII, STI, FSI) requires specifically tailored technique. Approximations of CII can be distinguished into permutation-bant approximation (SII and STI) and kernel-basee approximation (FSI). Both extend on existing methods

---

for the SV, namely permutation sampling [5] for SII and STI, and KerneISHAP (26 for FSI. For a comprehensive overview of the original SV methods, we refer to the appendix. We now briefly discuss existing approaches, which will be used as baselines in our experiments.
The permutation- cermutation-based (PB) approximation computes estimates of SII and STI based on representation of uniformly sampled random permutations p where G is the set of all permutations, i.e. the set of all ordered sequences of the elements in D. Then,
Permutation-based (PB) Approximation for STI and SII 39 40).
(S) = (1SS T766 (1)(1)) and (S) = (x=uni(((@))
[ (x)(
Here, us (iT) refers to the set of indices in æ preceding the first occurrence of any element of S in and S E ı is fulfilled, if all elements of S appear as a consecutive sequence in æ. The estimators for SII and STI then compute an approximation by Monte Carlo integration by sampling и unif(@p).
Kernel based (KB) approximation estimates FSI based on the representation of I as a solution to a constrained weighted least square problem
Kernel-based (KB) Approximation for ESI 40 8).
FSL arg min BI-p())(((T) - Σ
B(S)) s.t.
Σ SES...
B(S) = (D) and ((0) = v()), (1)
BER
SES
SCT
where p(T) p(t). is probability distribution over Ti and da, SS KB approximation for FSI estimates the expectation using Monte Carlo integration by sampling from p(T") and solves the approximated least-squares problem explicitly, similar to KernelSHAP 26 g 40 For more details and pseudo code, we refer to the appendix.
3.3 Unbiased KernelSHAP (U-KSH) for the SV
U-KSH constitutes variant of KernelSHAP (KSH) (6). which relies on KB approximation for the SV. In contrast KSH, U-KSH is theoretically well understood and was shown that the estimator unbiased and consistent [8] U-KSH finds exact solution to ( with = 1 as
- Aー - (1)
Sv A-1 6
where A = ==[ZZ" -0]=B(Z and p(%) p(t)-
1TA-11
U-KSH then approximates this solution using Monte Carlo integration.
Definition 3.7 (Unbiased KernelSHAP (U-KSH) (8). Given T Tı....,
......,Ty Tk ~ p(T) p(t) with binary
representation Zi....; Zx 10, U-KSH defined as
psy = A-1 i 1 A vo(1)
1
K Zevo (Zx)-
where i
1TA-11
The main idea of U-KSH is that A can be computed explicitly independent of v and only has be estimated [8) By linking U-KSH to our method (Theorem 4.5 we will show that isy can be greatly simplified to a weighted sum.
4 SHAP-IQ: Unified Approximation of any-order CII
So far, there exists no unified approximation technique for the general CII. In particular, is unknown if existing approximation techniques, such PB and KB, generalize to other indices [39] 40 [3]. Furthermore, PB approximation for SII and STI very inefficient each update of all estimates requires significant number of model evaluations. KB approximation for FSI efficiently computes estimates, where one model evaluation can be used update all interaction scores. is, however, impossible to compute only selection of interaction estimates and theoretical results for the estimator are difficult to establish. In the following, we introduce SHAP-IQ (Section 4.1.. a unified sampling- based approximation method that can be applied to any CII. SHAP-IQ is based on a Monte Carlo estimate of a novel representation of the CII and well-known statistical results are applicable. the special case of SV, we find novel representation of the SV and show that SHAP-IQ is linked to
5

---

U-KSH (Section 4.2). SHAP-IQ therefore greatly reduces the computational complexity of U-KSH. We further show (Section 4.3). that the sum of interaction estimates of SHAP-IQ remains constant and therefore maintains the efficiency property for STI and SII. Interestingly, for FSI this property does not hold, which should be investigated in future research. All proofs can be found in the appendix.
4.1 SHAPley Interaction Quantification (SHAP-IQ)
A key challenge in approximating the CII efficiently is that the sum changes for every interaction subset S. We thus first establish novel representation of the CII. Based on this representation, we construct SHAP-IQ, an efficient estimator of the CII. We show that SHAP-IQ is unbiased, consistent and provide a general approximation bound.
Our novel representation of the CII is defined as a sum over all subsets 7' C D. In previous works, it was shown that such a representation does exist for games with (0) if the linearity axiom is fulfilled [7 Proposition 1J. We now explicitly specify this representation and show that the weights, for a CII, only depend on the sizes of T and the intersection T s
Theorem 4.1. It holds (S) Erep (TT) (t, (T SI) with 7 (t, k)) = (-1)"==mol k.).
Theorem 4.1 yields a novel representation the CII, where the model evaluations vo (T) are indepen- dent of S. This allows to utilize every model evaluation to compute all CII scores simultaneously by properly weighting with 75"h Notably, our representation relies on vy instead of v, which constitutes an important choice for approximation, which we elaborate in the appendix.
To approximate 1, we introduce sampling order ko 2 so. for which we split the sum in Theorem 4.1 to subsets with T E Tho and T & TTk and rewrite
25th (t, (1
cko (S)) Br po (T) 1T (S) cko
with Ckp (S)
Σ voo(T) TNS)),
Pko (T)
T&TKo
where Pko is over Tho- SHAP-IQ then estimates the CII by Monte Carlo integration.
Definition 4.2 (SHAP-IQ). The Shapley Interaction Quantification (SHAP-IQ) of order ko with K samples is
K
(S) = Cko (S) +
1
Σ
vo
2/ (tk, ()) (Tx)
with Ti...., Tk ~ Pko (T).
K
Pko (Ta)
SHAP-IQ is outlined in the appendix and we establish the following important theoretical guarantees.
Theorem 4.3. SHAP-IQ is unbiased, E Pm (S) = (S),,, and consistent, in (S) K k= (Tn(S).
With (S) = V Pn (T) ( ( (17..InS)) and > O, holds
- > (
(S)
(T)
SHAP-IQ provides efficient estimates of all CII scores with important theoretical guarantees. The sample variance 8² can further be used for statistical analysis of the estimates.
Finding the sampling order ko and distribution Pk. In line with KSH and U-KSH 26 g we
find ko in an iterative procedure, outlined in the appendix. We consider sampling weights g 2 0
for 0 < < d that grow symmetrically towards the center and consider distribution pk., (T)) x (t).
Given a budget M and initial ko 0, we consider 1 (S) ET (T) PD (T) x" (1.1 and
Pkg (T)
iteratively increase ko, if for a subset T of size ko and d kg, the condition M Pk,, (T) 2 1 is fulfilled.
The budget is then decreased by the number of subsets of that size, i.e. 2 2(()) This essentially verifies
iteratively, if the expected number of subsets exceeds the total number of subsets. For more details and possible choices of sampling weights q, we refer to the appendix.
Computational Complexity. In contrast to PB approximations, SHAP-IQ allows to iteratively update all interaction estimates with one single model evaluation for any-order interactions. The
Our representation generalizes result for SII 16 Table functions with (00) 0 and the class of Clls.

---

weights (t. k) used for the updates can be efficiently precomputed. The updating process can be implemented efficiently using Welford's s algorithm 45 where estimates have be maintained for all interactions sets, i.e. dsp in total. In contrast to KB approximation, which requires to solve weighted least square optimization problem with d.s, variables, the computational effort per interaction increases linearly for SHAP-IQ. Furthermore, SHAP-IQ even allows to update selected interaction estimates, whereas, for instance, KB approximation for FSI requires to estimate all interactions. For more details on the implementation and computational complexity of the baseline methods, we refer to the appendix.
4.2 SHAP-IQ for the Shapley Value
In this section, we show that SHAP-IQ, in the special case of single feature subsets = 1. yields novel insights into the SV. Furthermore, SHAP-IQ corresponds to U-KSH and greatly simplifies its calculation. Utilizing Theorem 4.1 we find novel representation of the SV for every feature i E D.
Theorem 4.4. With (i)
Mi the SV is (s)(i) - ei (i) + Erer, (T())(()) [) l
SHAP-IQ admits a similar form (see appendix) and corresponds to U-KSH PY
Theorem 4.5 (SHAP-IQ simplifies U-KSH), For p(T)) p(t) it holds that 1 1TT.
Theorem 4.5
implies that the U-KSH estimator can be computed using the SHAP-IQ estimator, which greatly simplifies the calculation to a weighted sum. The main idea of the proof relies on the observation that not only A can be explicitly computed, but also A-1, cf. the appendix.
4.3 The Sum of Interaction Scores and SHAP-IQ Efficiency
In this section,
interested in the of CII scores, which we link to property of SHAP- IQ estimates to maintain the efficiency axiom. By Theorem 4.1, we have Eses.. (S) =
ETED (T) Eses., (t, [T n SI). For the SV, by Theorem 4.4 this sum is zero for every TE T. For higher order Clls, we introduce the following definition.
Definition 4.6. A CII is s-efficient, if EscD. 7 (t, IT' S|) 0 for every T E Tau Theorem 4.7. SII and STI are s-efficient. particular, SHAP-IQ estimates maintain efficiency for n-SII and STI.
Further, if CIT is s-efficient, then the of SHAP-IQ estimates remains constant. Although we did not provide a rigorous statement, it is easy to validate numerically that FSI is not s-efficient. This finding suggests that there are conceptional differences between these indices, that should be further investigated in future work. Using s-efficiency it is also possible to find an explicit formula for the sum of interaction scores for SII, which we give in the appendix.
5 Experiments
We conduct multiple experiments to illustrate the approximation quality of SHAP-IQ compared to current baseline approaches STI and FSI. For each interaction index, we use its specific approximation method as baseline. For SII and STI, we use the PB approximation and for FSI the KB approximation, further described in the appendix. We then compute n-SII based on the estimated SII values. We compare the baseline methods with SHAP-IQ using ((T) x p(t). For each iteration we evaluate the approximation quality with different budgets up to maximum budget of 24 model evaluations. To account for variation, we randomly evaluate the approximation method on 50 randomly chosen instances, further described below. To quantify the approximation quality, we compute multiple evaluation metrics for each interaction order: mean-squared error (MSE), MSE for the top-K interactions (MSE@) K) and the ratio (precision) of estimated top-K interactions (Prec@K, K). The top-K interactions are determined in regards to their absolute value.
Fl We showease SHAP-IQ estimates on any-order SII (n-SII), on top-order
*All code and implementations for conducting the experiments can be found at https:: //gg githuu........ com/ FFng (Fmgl1/shal /happi Running the experiments required a computational cost of approximately 2 200 CPU hours. For more details refer the appendix.
7

---

0.3
4l for 141
forthe 14)
14
Si forthe ICM Id 14)
Metked Eeadrr
Order
Metked Reaedre
Order
0.4
0.2
0:6
Mettel
6.08
Buoedine
0.6
0.4
02
646
3200
4006
33900 12008 34539 LOCCE m6der wwkaatir Sasukie withio
6313
3323
4033
10600 3200 S1600 36000 coparies bi Inanee
4000
34000 3006 10. MntoRU Haghee
6302 6939 32600 3200
Figure 2: Approximation quality of SHAP-IQ and the baseline for orders 1, of SII measured by MSE for the LM (left) and Prec 10 for orders $ = 2,3 for the LM (middle) and ICM (right).
Models. For a language model (LM), we use a fine-tuned version of the DistilBERT transformer architecture [44] on movie review sentences from the original IMDB dataset 22 22 analysis, i.e. y has values in [-1, 1]. In the LM, for given sentence, different feature coalitions are computed by masking absent features in a tokenized sentence. The implementation is based on the transformers API [47]. We randomly sample 50 reviews of length d = 14 and explain each model prediction. For an image classification model (ICM), we use ResNet18 19 pre-trained on ImageNet 11 as provided by torch [30]. We randomly sample 50 images and explain the prediction of the corresponding true class. To obtain the prediction of different coalitions, we pre-compute super-pixels with SLIC [
for sentiment
44 to obtain function on d 14 features and apply mean imputation on absent features. For a high-dimensional synthetic model with d = 30, we use a sum of unanimity model (SOUM) (T) == Σn= O₂ 1QQn S 7), where N = 50 interaction subsets Q1....,Q QN C D are chosen uniformly from all subset sizes and ....... aN R generated uniformly on ~ unif( [0, 1])- Note that the SOUM could also be viewed as an extension of the induced subgraph game [1] for a hypergraph with edges of different order. We randomly generate 50 instances of such SOUMs.
Ground- Trouhd-Truth (GT) Values. For the LM and the ICM we compute the ground- (GT) values explicitly using the representation from Theorem 4.1 For the high-dimensional SOUM it impossible to compute the GT values naively. However, due to the linearity of the CII and the simple structure of SOUM, can compute the exact GT values of for any CII efficiently, cf. the appendix.
5.1 Approximation of any-order SII and n-SII scores using SHAP-IQ
In this experiment, we apply SHAP-IQ on SII and compute estimates for the LM and the ICM up to order s = 4. We then compare the estimates with the baseline using the GT values for each order. The results are shown in F We display the MSE for the LM (left) and the Prec@ 10 for the LM (middle) and ICM (right). We further compute the n n-SII estimates by aggregating the SII estimates with 8p = 4 and visualize positive and negative interactions on single individuals as proposed in 3. Thereby, interactions are distributed equally among each participating feature, which was justified in 3 Theorem 6]. This representation amplifies the variance of our sampling-based estimator. We thus also present SHAP-IQ without sampling, i.e. Ckp The results are shown in Figure (left) and from left to right: GT values, SHAP-IQ, SHAP-IQ without sampling and baseline. Lastly, we illustrate the n-SII scores estimates for 8p of movie review excerpt classified by the LM (right), where the interactions ("is", ("iss",nntt") ("not", "bad"). and (""II""" "love", "love",""hhis" yield a highly positive score.
The results show that SHAP-IQ outperforms the bascline methods across different models and metrics. For the n-SII visualization, we conclude that the SHAP-IQ estimator without sampling is preferable, which yields more accurate results than SHAP-IQ and the baseline methods. In general, SHAP-IQ without sampling performs surprisingly strong, and we encourage further work in this direction.
5.2 Approximation of different CIIs using SHAP-IQ
In this experiment, we apply SHAP-IQ on different CIIs, namely SII, STI and FSI. We compute top-order interactions for 8p = 3 and compare the results with the baselines. Our results are shown in Figure 4 (left) and further experiments and results can be found in the appendix. For the LM,
8

---

n-Sil values for sentence provided to the LM
20
sentiment: (pueltio)
Harnital
-20
A18
reerr
baarre
rodd
this
and
shaught
thl
bony
Figure 3: Visualization of n-SII and 8g SHAP-IQ without sampling, and baseline. Estimated n-SII scores (sp = 3) for a movie review (right).
(left) with (from left right): GT, SHAP-IQ.
S1 STL and FSI for LM Ci 3,0
54. STL and FSI for SOUM Esp 22. 300
511. STL and FSI for SOUM Iss 2 2. 363
6:16
6:34
sHPPig 2
Seasline
SndPlo Seadiia
PM
0:32
6:10
Hetked
Order
2 c
3.4
0.04
8:2
5:0
250
250
#009
1990 12/00 18559 LIEES
2232 4603
Js00 Lake Libce
4600 6203 s0l0 us0ee 1240s 1460e 10660
eveluterr Arsoiile withvo
Tode evilaaioos
eveluatoos
Figure 4: Approximation quality for top-order interactions of SII, STI, and FSI of the LM with 80 (left) and the SOUM with 80 = 2 (middle and right).
SHAP-IQ clearly outperforms the baseline for SII and STI. For FSI, SHAP-IQ is outperformed by the KB approximation of the baseline. As SII and STI rely on PB approximation, our results indicate that KB approximation is more effective than PB approximation for this setting, which is in line with the strong performance of KernelSHAP (26) for the SV. However, SHAP-IQ, in contrast to KB approximation, provides a solid mathematical foundation with theoretical guarantees and we now consider a high-dimensional synthetic game, where SHAP-IQ outperforms all baselines.
SHAP-IQ on high-dimensional synthetic models. For the SOUM we compute the average and standard deviation of each evaluation metric for SHAP-IQ and the baselines for pairwise interactions (su 2) of each index. Our results are shown in Figure (middle and right) and further experiments and results can be found in the appendix. SHAP-IQ outperforms all baseline methods in this setting, in particular, the KB approximation of FST that performed strongly in MI. context. The experiment highlights that there exists no approximation method that performs universally best.
Runtime Analysis. The runtime of SHAP-IQ is affected by different parameters. The computation of the sampling order ko a constant time operation given number of features (cf. Algorithm 2 in the appendix). While the pre-computation of the weights (m,) scales linearly with the number of features, the additional computational burden negligible it does not depend on vy- The main computational cost stems from the model evaluations (access to the value function 1o), which is bounded by model's 's inference time. To illustrate the runtime performance, we compare SHAP-IQ with the baseline methods on the LM using different number of model evaluations K. Figure 5 displays the runtime of SHAP-IQ and the corresponding baseline approaches, including all pre-computations. With increasing K the runtime complexity scales linearly, but the overhead of SHAP-IQ remains low. Note that the difference in STI can be attributed to less than K model evaluations, which is required to maintain efficiency, ef. lines 15- 16 in Algorithm 6 of the appendix.

---

6 Limitations
We presented SHAP-IQ, unified approximation al- gorithm for any-order CIIs with important theoretical guarantees. SHAP-IQ relies on the specific structure in terms of discrete derivatives from Definition [3.3 This representation exists for every interaction indices that fulfills the linearity, symmetry and dummy axiom
Run-time
173
Nethod
SH6P--0
Baneline
nuntire-h secunda
T7 Proposition 5]. However, for FSI, which has been defined as the solution to the weighted least square problem, closed-form representation for lower-order interactions in terms of discrete derivatives remains difficult to establish 440, Lemma 70]. This limits the applicability of SHAP-IQ to top-order interactions of FSI, for which this representation given [40] The- orem 19J. The FSI baseline performs strongly in ML context, in line with empirical findings for KemelSHHA (26 for the SV. However, the estimator is theoretically not well understood [8] and we have shown that it is not universally best. Moreover, for other ClIs, such as SII and STI, it unlikely [33 that such an explicit form in terms of weighted least square problem can be found, which limits the applicability of KB approx- imation FSI. SHAP-IQ outperforms the baselines of SII and STI by a large margin, is generally applicable and supported by a solid mathematical foundation.
Daneline
203
75
25-
2000
4000
6000
8:00
10000
budget
Figure 5: For each interaction index (SII: solid, STI: dashed, FSI: dashdotted), we compare the run-time (in seconds) of SHAP- IQ (pink) compared baseline estimators (violet) of one instantiation of the LM (16 words) over five independent runs at differ- ent levels of K.
7 Conclusion
How to extend the SV to interactions an open research question. In this work, we considered ClIs, broad class of interaction indices, which covers all currently proposed indices, well all indices that fulfill the linearity, symmetry and dummy axiom. We established a novel representation of the CII, which used to introduce SHAP-IQ, efficient sampling-based approximation algorithm that is unbiased and consistent. For the special case of SV, SHAP-IQ can be seen as a generalization of U-KSH [8] and greatly simplifies its calculation as well as providing a novel representation of the SV. Furthermore, for n-SII and STI, SHAP-IQ maintains the efficiency condition, which is direct consequence of specific property, which we coin s-efficiency for Clls. We applied SHAP-IQ in multiple experimental settings to compute any-order interactions of SII and n-SII, where SHAP-IQ consistently outperforms the baseline method and showcased the applicability of feature interaction scores understand black-box language and image classification models. SHAP-IQ further benefits from a solid statistical foundation, which can be leveraged to improve the approximation quality.
Future work. Applying SHAP-IQ to real-world applications, such as NLP tasks 43 and genomics 48 233, could yield valuable insights. However, the exponentially increasing number of interactions requires human-centered post-po post-processing to enhance interpretability for practitioners and MI. engi- neers, e.g. through automated dialogue systems (37]. Further, it would be beneficial to discover the statistical capabilities of SHAP-IQ to provide confidence bounds or approximate interaction scores sequentially. Beyond model-agnostic approximation, model-specific variants could substantially reduce computational complexity. For instance, it is likely that ideas of TreeSHAP 255 for tree-based models can be extended to Shapley-base interactions.
Acknowledgements
We sincerely thank the anonymous reviewers for their work and helpful comments. We gratefully acknowledge funding by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation): TRR 318/1 2021 438445824. Patrick Kolpaczki is supported by the research training group Dataninja (Trustworthy Al for Seamless Problem Solving: Next Generation Intelligence Joins Robust Data Analysis) funded by the German federal state of North Westphaaa..
10

---

References
[1] Achanta, R., Shaji, A., Smith, k., Lucchi, A., Fua, P., and Süsstrunk, S. (2012). Slic superpixels compared state-of-the-art superpixel methods. IEEE Transactions Pattern Analysis and Machine Intelligence, 34(11))2274-2282.
[2] Adadi, A. and Berrada, M. (2018). Peeking inside the black-box: A survey explainable artificial intelligence (xai). IEEE Access, 6:52138-52166
[3] Bordt, S. and von Luxburg, U. (2023). From shapley values to generalized additive models and back. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, (AISTATS 2023), volume 206 of Proceedings of Machine Learning Research, pages 709-745. PMLR.
[4] Castro, J., Gómez, D., Molina, E., and Tejada, J. (2017). Improving polynomial estimation of the shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 82:180-188.
[5] Castro, J., Gómez, D., and Tejada, (2009). Polynomial calculation of the shapley value based on sampling. Computers & Operations Research, 3666):1726
[6] Charnes, A., Golany, B., Keane, M., and Rousseau, (1988). Extremal Principle Solutions of Games in Characteristic Function Form: Core, Chebychev and Shapley Value Generalizations. volume 11 of Advanced Studies in Theoretical and Applied Econometrics, page 123-133. Springer Netherlands.
[7] Chen, H., Covert, I. C., Lundberg, S. M., and Lee, S.-L. (2023), Algorithms to estimate shapley value feature attributions. Nature Machine Intelligence, 5(6):590-601.
[8] Covert, I. and Lee, S.-I. (2021). Improving kernelshap: Practical shapley value estimation using linear regression. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, (AISTATS 2021), volume 130 of Proceedings of Machine Learning Research, page 3457-3465. PMLR.
[9] Covert, I., Lundberg, S. M., and Lee, S. (2021). Explaining by removing: A unified framework for model explanation. Journal of Machine Learning Research, 22:209:1-209::::
[10] Cui, T., Marttinen, P., and Kaski, S. (2020). Learning global pairwise interactions with bayesian neural networks. In 24th European Conference on Artificial Intelligence, (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, pages 1087-1094. IOS Press.
[11] Deng, J., Dong, W., Socher, R., Li, L., Li, K., and Fei-Fei, L. (2009). Imagenet: A large-scale hierarchical image database. In 2009 IEEE Computer Sociery Conference on Computer Vision and Pattern Recognition, (CVPR 2009), pages 248-255. IEEE Computer Society.
[12] Deng, X. and Papadimitriou, C. H. (1994). On the complexity cooperative solution concepts. Mathematics of Operations Research, 19(2):257-266
[13] Ding, G., Lax, R. F., Chen, J., and Chen, P. P. (2008). Formulas for approximating pseudo- boolean random variables. Discrete Applied Mathematics, 156(10):1511-1597
[14] Fujimoto, K., Kojadinovic, I., and Marichal, J. (2006). Axiomatic characterizations of proba- bilistic and cardinal- interaction indices. Games Econ. Behav, 55(1):72-99.
[15) Ghorbani, A. and Zou, Y. (2019). Data shapley: Equitable valuation of data for machine learning. In Proceedings of the 36th International Conference on Machine Learning, (ICML.2019) volume 97 of Proceedings of Machine Learning Research, pages 2242-2251. PMLR.
[16] Grabisch, M.. Marichal, J., and Roubens, M. (2000), Equivalent representations of set functions. Mathematics of Operations Research, 25(2):157-178.
[17] Grabisch, M. and Roubens, M. (1999). An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 2844)5547-565.
11

---

[18] Hammer, P. L. and Holzman, R. (1992). Approximations of pseudo-boolean functions; applica- tions game theory. ZOR Mathematical Methods of Operations Research, 36(1):3-21.
[19] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, (CVPR 2016), pages 770-778. IEEE Computer Society.
[20] Janizek, J. D., Sturmfels, P., and Lee, S. (2021). Explaining explanations: Axiomatic feature interactions for deep networks. Journal of Machine Learning Research, 12:10::1-10
[21] Jia, R., Dao, D., Wang. B., Hubis. F. A., Hynes, N., Gürel, N. M., Li, B., Zhang, C., Song. D., and Spanos, J. (2019). Towards efficient data valuation based on the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, (AISTATS 2019), volume 89 of Proceedings of Machine Learning Research, pages 1167-1176. PMLR.
[22] Lhoest, Q. Villanova del Moral, A., von Platen, P., Wolf, T., Šaško, M., Jernite, Y., Thakur, A., Tunstall, L.,, Patil, S., Drame, M., Chaumond, J., Plu, J., Davison, J., Brandeis, S., Sanh, V., Le Scao, T., Canwen Xu, Patry, N., Liu, S., McMillan Majaaa A., Schmid, P., Gugger, S., Raw, N., Lesage, S., Lozhkov, A., Carrigan, M., Matussière, T., von Werra, L., Debut, L.,, Bekman, S., and Delangue, C. (2021). Datasets: A community library for natural language processing. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, (EMNLP 2021), ), pages 175-184. Association for Computational Linguistics.
[23] Liu, G., Zeng, H., and Gifford, D. K. (2019). Visualizing complex feature interactions and feature sharing genomic deep neural networks. BMC Bioinformatics, 20(1):401:1441111
[24] Lou, Y., Caruana, R., Gehrke, J., and Hooker, G. (2013). Accurate intelligible models with pairwise interactions. In The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (KDD 2013), pages 623-631. ACM.
[25] Lundberg, S. M., Erion, G. G., Chen, H., DeGrave, A. J., Prutkin, J. M.. Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee, S. (2020). From local explanations to global understanding with explainable ai for trees. Nature Machine Intelligence, 2(1):56 6666
[26] Lundberg, S. M. and Lee, S. (2017). A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, (NeurIPS 2017), pages 4765-4774, Curran Associates, Inc.
[27] Maas, A. L.., Daly, R. F.,, Pham, P. T., Huang, D., Ng. A. Y., and Potts, C. (2011). Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, (HLT 2011), pages 142-150. Association for Computational Linguistics.
[28] Molnar, C., Casalicchio, G., and Bischl, B. (2019). Quantifying model complexity via functional decomposition for better post-hoe interpretability. In Machine Learning and Knowledge Discovery in Databases- International Workshops of ECML PKDD 2019, pages 193-204.
[29] Murdoch, W. J., Liu, P. J., and Yu, B. (2018). Beyond word importance: Contextual de- composition to extract interactions from Istms. In 6th International Conference on Learning Representations, (ICLR 2018).
[30] Paszke, A., Gross, S., Massa, F. Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang. E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. (2019). Pytorch: An imperative deep learning library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, (NeurIPS 2019), pages 8024-8033 Curran Associates, Inc.
style,
[31] Rabitti, G. and Borgonovo, E. (2019). A shapley-owen index for interaction quantification. SIAM/ASA Journal on Uncertainty Quantification, 1000:066-
[32] Ruiz, L. M., Valenciano, F., and Zarzuelo, J. M. (1996). The least square prenucleolus and the least square nucleolus. two values for tu games based on the excess vector. International Journal of Game Theory, 25-1):113-134
12

---

[33] Ruiz, L. M.. Valenciano, F., and Zarzuelo, J. M. (1998). The family of least square values for transferable utility games. Games and Economic Behavior, 24(1):109-130.
[34] Sanh, V., Debut, L., Chaumond, J., and Wolf, T. (2019). Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. CoRR, abs/1910.01108.
[35] Shapley, S. S. (1953). A value for n-person games. In Contributions to the Theory of Games (AM-28), Volume II, pages 307-318. Princeton University Press.
[36] Singh, C., Murdoch, W. J., and Yu, B. (2019). Hierarchical interpretations for neural network predictions. In 7th International Conference on Learning Representations, (ICLR 2019).
[37] Slack, D., Krishna, S., Lakkaraju, H., and Singh, S. (2023). Explaining machine learning models with interactive natural language conversations using talktomodel. Nature Machine Intelligence, 5(8):873-883.
[38] Spivey, M. Z. (2007). Combinatorial sums and finite differences. Discrete Mathematics, 307(24):3130-344
[39] Sundararajan, M., Dhamdhere, K., and Agarwal, A. (2020). The shapley taylor interaction index. Proceedings of the 37th International Conference on Machine Learning, (ICML 2020), volume 119 of Proceedings of Machine Learning Research, pages 9259-99 2269. PMLR.
[40] Tsai, C.,, Yeh, C., and Ravikumar, P. (2023). Faith-shap: The faithful shapley interaction index. Journal of Machine Learning Research, 24(94):1-42.
[41] Tsang, M., Cheng, D., Liu, H., Feng, X., Zhou, E., and Liu, Y. (2020a). Feature interaction interpretability: A case for explaining ad ad-rrcommeedaation systems via neural interaction detection. In 8th International Conference on Learning Representations, (ICLR 2020).
[42] Tsang, M., Cheng, D., and Liu, Y. (2018). Detecting statistical interactions from neural network weights. In 6th International Conference on Learning Representations, (ICLR 2018).
[43] Tsang, M., Rambhatla, S., and Liu, Y. (2020b). How does this interaction affect me? in- terpretable attribution for feature interactions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, (NeurIPS 2020), pages 6147-6159 Curran Associates, Inc.
[44] van der Walt, S., Schönberger, J. L., Nunez-Iglesias, J., Boulogne, F., Warner, J. D., Yager, N., Gouillart, E., Yu, T., and the scikit-image contributors (2014). seikit-image: image processing in python. PeerJ, 2(6)).553.
[45] Welford, B. P. (1962). Note on method for calculating corrected sums of squares and products. Technometrics, 4(3):419443
[46] Williamson, B. D. and Feng, J. (2020). Efficient nonparametric statistical inference on popula- tion feature importance using shapley values. In Proceedings of the 37th International Conference on Machine Learning, (ICML 2020), volume 119 of Proceedings of Machine Learning Research, pages 10282-10291. PMLR.
[47] Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Scao, T. I.., Gugger, S., Drame, M., Lhoest, Q., and Rush, A. M. (2020). Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, (EMNLP 2020), pages 38-45. Association for Computational Linguistics.
[48] Wright, M. N., Ziegler, A., and König, I. R. (2016). Do little interactions get lost in dark random forests? BMC Bioinformatics, 17(155).
[49] Yeh, C., Kim, J. S., Yen, I. E., and Ravikumar, (2018). Representer point selection for explaining deep neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, (NeurIPS 2018), pages 9311-9321. Curran Associates, Inc
13

---

Appendix of "SHAP-IQ: Unified Approximation of any-order Shapley
Interactions"
Organisation of the Appendix
We provide further theoretical and experimental results for SHAP-IQ. The appendix organized as follows: In Appendix [A] we formally introduce specific ClIs, such as SII, n-SII, STI and FSI and their axiomatic foundation and theoretical results and provide novel theoretical result for the sum of SII scores. In Appendix B we provide all proofs of theoretical results from the main paper. In Appendix C we give further insights into the implementation of SHAP-IQ. Appendix [ we provide further experimental results, information about the used models, explicit formulas for the SOUM interaction scores, and pseudo-code code and information on the computational complexity of baseline implementations. In Appendix D provide further theoretical results for the special case of SV, in particular the explicit form of the covariance matrix from 8 and simplified representation, similar to Theorem 4,4] of SHAP-IQ in this case. In Appendix Fi we describe the approximation
methods ApproShapley [ and KernelSHAP 26 for the SV on which our baseline methods are built.
Shapley-based Interaction Indices and further theoretical Results
15
A.I Shapley-based Interaction Indices
15
A.2 Explicit Formula for Sum of SII Scores
16
Proofs
18
B. Proof of Theorem 4.
18
B.2 Proof of Theorem
18
Proof of Theorem
19
4 Proof of Theorem
19
B.5 Proof of Theorem
21
Algorithmic Details of SHAP-10
23
C.I
Algorithm of SHAP-IQ
23
C.2 Sampling Weights q((
23
Welford's s Algorithm
23
D
Experiments
25
D.I Baseline Algorithms for SII. STI, and FSI
25
D.2 Further Information about the Models
D.3
Hardware Details and Environmental Impact of the Experiments
................................
29
D.4
Further Experimental Results
29
Further theoretical Results for the Shapley Value
34
E.
Explicit Inverse of Covariance Matrix of Unbiased KerneISHA
..........
34
Simplified Representation of SHAP-IQ for the Shapley Value
34
Approximation Methods for the SV
36
Permutation-basel (PB) Approximation
36
Kernel-based (KB) Approximation)
36
14

---

A Shapley-based Interaction Indices and further theoretical Results
In this section, we review the axiomatic structures of n-SII, SII, STI and FSI. We further provide an additional result for the sum of SII interaction scores.
A.1 Shapley-based Interaction Indices
We consider G as the set of all games P(D) + R. In the following, we formalize the axioms for the Shapley interaction indices I, : PPD) -k
Definition A.1 (Linearity Axiom [7].. Iu linear, for any two games 1/,, V2 E G and any S S D. it holds [, +u (8) = Te, (S) + To (S).
Definition A.2 (Dummy Axiom [17]). For a dummy player i E D for a game v E G. i.e. constant contribution c(i) added to any coalition v(T U {i] (TT)) + c(t), then for every T D \ {i), the dummy axiom requires [,(S U {i}) for any S S DDV (i}- That is, a dummy player has no interaction with any coalition.
Definition A.3 (Symmetry Axiom 17 Tu is said to fulfil the symmetry axiom, if for any permula- tion v. on holds (S) = (T(), where nu(=S)= == uSS) and a = {T(() i $} changes
the ordering of the players.
Definition A.4 (Recursive Axiom 17 fulfills the recursive axiom, ffr any S C D with [S] >
and any game E g
I(S) = Inss ((S))
Σ
( K),
KCS,K#
where Vis] is the game, where all players in S is considered as one player, and DDJ is game defined on the subset of players D K.
The recursive axiom defines higher order interactions using lower order interaction. For pairwise interactions it can be stated as (z(i) = Lrnn (lii)) - LyPGG y (i) Luovon (j), i.c. the pairwise interaction is the difference of the value for the reduced player [ij] and the individual player values for the reduced game.
Definition A.5 (Shapley Interaction Index (77). The Shapley interaction index (SII) is the unique interaction index that satisfies the linearity, dummy,, symmetry and recursive axiom, where the values for |S| = correspond to the Shapley value. It can be represented as a ClI as
m (T) and m (t) = (d - 1-f--s(!d s)!t!
(S) = Σ
(d - -d--tt + 1)!
TCD(S
In contrast to the SV, the SII does not yield an efficiency property, which is desirable in ML context. The efficiency axiom was therefore introduced for interactions. The following axioms rely on maximum interaction order sg, where the values of the interaction indices change for different maximum interaction orders.
Definition A.6 (Efficiency Axiom 39
For all E G, it holds Eses,, L=S)= = v(D) -()))
The efficiency axiom an extension of the SV efficiency axiom and requires that all interaction scores up to the maximum order sum up to v(D) (() For SII there exists unique recursive aggregation, such that the efficiency axiom fulfilled. This novel interaction index referred as n-Shapley Values (n-SII) 3
Definition A.7 (n-Shapley Values (n-SII) 3
Given so the n-Shapley Values (n-SIl) are defined as
S (S);
for | = 8g for |.|| < s0-
Sm (5) = so (S) + B
I (SUK), k+a=d
Besides n-SII, there have been two axiomatic extensions to CHSs that directly require the efficiency axiom together with the linearity, symmetry and dummy axiom. However, unlike for the SV, it is not sufficient require efficiency for unique interaction index. The Shapley Taylor Interaction Index (STI) further specifies the interaction distribution axiom, which then yields unique index [39
15

---

Definition A.8 (Interaction Distribution Axiom (39). For an interaction function parametrized by T [ D it holds (T( = 0, if & S and a constant value (T((S) = c. I S and e R. The interaction distribution axiom requires for all S S D with S < T and 8 < that Fur (5)= Definition A.9 (The Shapley Taylor Interaction Index (9). The Shapley Taylor interaction index (STI) is the unique interaction index that satisfies the linearity, dummy, symmetry, efficiency and interaction distribution axiom.
The STI yields unique interaction index by introducing the interaction distribution axiom, which favors the maximum order interactions as discussed in [40]. was thus argued that instead the representation of the interaction index solution weighted least square problem preferable 40). which yields the Faith- Interahnteaatoon Index.
Definition A.10 (Faith--nteraction Index
) called Faith-interaction index if can be
expressed as
I= arg min BER
Σ ((T)
v(T) Σ B(S)
TCD:p(T)o0
TCS
$5
s.t. (()) =
Σ SCT,1S0
B(S), VT: (( = oc.
Definition A.11 (Faithful Shapley Interaction Index (40). The Faithful Shapley interaction index (FSI) is the unique faith intteriiteaaction index that satisfies the linearity, dummy, symmetry and efficiency axiom.
While nIIII, SII, STI and FSI offer differnt ways characterizing an interaction index, it was shown in [7 that every interaction index satisfying the linearity, symmetry and dummy axiom admits CII representation.
Proposition A.12. Every interaction index satisfying the linearity, symmetry and dummy axiom can be represented as a Cll
(S)
Σ m,(1)8
TEDYS
Furthermore, the weights mag for the top-order interaction indices, i.e. 80 are defined as
m TO (t) = (d - t St
(d. 80 1)!
STI (f) = (d - 1)!!!
d!
Fll (t) = (280 - 1)! (d-t- 1)1(t so 1)!
m
((so 1)!}² (d + 8o 1)!
The definitions for lower order interactions can be found [I7] for SHI in (39) for STI and (40)
for FSI. Note that for FSI closed-form solution for lower-order interactions in terms of discrete derivatives remains unknown [40) Lemma 70].
Proof. For the proofs, we refer to the corresponding paper of each index. The general statement is proven in 117 Proposition 5].
A.2 Explicit Formula for Sum of SIT Scores
Using s-efficiency, is easy to calculate the sum of SII scores, which provide an explicit representation of formula considered in 33 Theorem 4.2].
Proposition A.13 (Sum of SII Scores). For SII it holds
(S) Σ (-))))(((-)))))))------))))))))- (T),
SCD 18
TCD
1-350
16

---

where r(t): := _
80 ( (c0=--)) and m² == (d-t-so)lt) y!
(1)
Proof. For SII, we let == m (1)= = -- (77 -1 and have by Theorem 4.7 and the definition of s-efficiency
(S)
coo(S) = Σ (T)
Σ (( + Σ (
1 (t, (T)))
SCD |8|
SCD 18|=50
TCD
SCD
TCD b>d-
SCD |S|=s0
15:00
[8] 8
Fort t < so we have
P(()= =
th (TISS))) = Σ
k
80 k.
L
Ta
m (4, (T, S))
SCD
k=
$|=#0
(1)
())()=) - b) (d 80 800
( (-1)
d
80 + 1
k
k=
Fort > d there are at least Kmin
t (d 8) elements in the intersection of [T n S| and thus
with f := d - t < So and Kmin = Su - E
k - k.
Σ
m (t, (nS)) = Σ
m
(T
SCD 15|=50
A= Amin
50 Σ
(-1)so-k
d
d 80
-1
d - 50 +1
k)
80 k) - k
k=kmii
8p
d t
88 - k) ))
f
( d 90
d - 80 +1
k
d - [ --k
k=
i
d d i
i
d 80
d - 80
+1
80 k
k
d - [ - 80 + k)
k=
i
d d [
1
d 88
1)
d 80 +1
80 k
1:
k=
(-11"*p(t).
We can explicitly compute p(t) as
p(t) d - 80 +1
1
1)
1
d - t
d so)
k
50 k)
- k
k=0
t!(d t)!
= (-1)a0
(d -1-60 50 + 1)! k=
(so k)kk!
t!(d - t)!
(-1)* (0
(-1) so!(d - + 1)!
kk)
k=U
t((d- -t)! t)!
1)a 50 11)
(-1)sott ( d=t (d=t)
= 1-1) 80 so!(d 80 + 1)!
-1-1)
80
80
where we have used that Ek (-1)* (*)) = (- (-1) (10 for t < sp- Hence,
1
d d-t (-)(()))))))))))))))))))))))))) (
Σ (m = - Σ
60 --11) -b-1
50 TCD
SCD
|8|=80
1::00
17

---

B Proofs
This section contains the proofs of the claims made in the main paper.
B.1 Proof of Theorem 4.1
Proof. By definition, the sum (S) Ercoys m(t) ranges over all subsets T D, where every subset is exactly once evaluated. On the hand, it is easy to that every evaluated subset in (S) is different, as T L is unique. Furthermore, given any subset T S D, we decompose T = 7' U L, where T S D S and L == Tns C S. The corresponding weight is m(t) = mt - 1) m(t (T)S)) and the sign from 85( is (-1)a-1= (-1)*-17ns), This yields with vo (TT) v(0)
(S) Σ v(Th (t.
E 10(T) (t,
(TS)) (t, + +0(
1s (t, (TS))
TED
TED
TCD
Σ TCD
vol (T (,,ns())
as the sum over all nm is zero, if the dummy axiom is fulfilled.
Remark B.1. It important note, that the sum ETED (t, is not zero, not all subsets are considered, which makes it crucial to use vo instead of v. In fact, the estimates of T would be heavily skewed by v(0). While the estimator would still be unbiased, its variance would scale with v(0)².
B.2 Proof of Theorem
Proof. We aim to show that (S)( unbiased and consistent, i.e.
im
(S) = (S)(S) and No
lim -00 im = (S). Given
K
m (tk. [T SS)
(S) = Cko (S) +
vo
(Tk)
K
Pko (Tk)
it is clear that due to the linearity of the expectation
Ey Er-ppn (T) [S) cksa (S) +
1
E Erappn (T)
(T
2 ([T), (T
(S).
K
Pko (T)
Furthermore, let o2(S)= = V VT (T) (vo(T) 22 (ITTTTTTTTS)) (T)
be the variance of each estimate, then,
by the law of large numbers
(42, Th S1)
K K-gg E BINpe (T) (T) De (IT), (TS)
(Th)
K
Pho (Tk)
Pko (T)
and thus lim im (S) IT' Lastly, i'm(S) is unbiased, we have for e > 0 by Chebyshev's inequality
7m (S)
Ko²
1 (S
PIII (S) > e) 5
2
K2
2
K
2
18

---

B.3 Proof of Theorem 4.4
Proof. We let m(t) [d-t-1]le! and apply Theorem 4.1 d!
With (0,00 mm(0,, y (d. 1)
m(d - 1) and m(0) m(d 1) =
we have
v(D) v(0)
7sy Theorem 41
Σ ((T)"((1(1E7))
d
TCD
TEN
= (i) + Σ
(T (t (t.
TET
cii + Σ
> (t. 0)]
TET
(1) Σ (TT
m()) m()
(d- (d- - 1)! + (d-t- (d-t-1) 1)16! I(iET)
(d- 1)
= (i) + Σ (T)
d!
d!
d!
TET
(d (d-1-1)!(t- 1)((1-
(d-1)! I(ieT) 4
=i + Σ v(T)
TET
= ci) + Σ ((T)(tt) I(iET) 4
TET
B.4
Proof of Theorem 4.5
Proof. According to Proposition
B.3
our goal is to show that
2h
tx Σ vo(TT) T(i
ci)
+
K
=
iid with Ty ~ p()(h))))()))) where y probability distribution over Ti and hn : Em 1-1
The proof is structured in the following steps:
1. Exact computation of A-1 using the exact structure of A with diagonal entries μ4 and off-diagonal entries μ22 cf. [8] Appendix A].
2. Exact computation of isy. which yields with Proposition E.3 12)2ha-1 = 1.
(T" if (M
3. We show that (μ1 #2 22) =1
Calculation of A-1 It has been shown in 8 Appendix A] that all off- entries equal and all diagonal entries are equal, i.e. A may be written as A = JzzJ + (μ² (22) with off-diagonal entries #42 p(Z,- Z, = 1) and diagonal entries μn p(Z; = 1), where Z; refers the i-th component of the binary vector Z and J is a matrix of ones and I is the identity matrix. The simple structure of A allows compute the inverse exactly by using the following Lemma.
Lemma B.2, Let 11,442 > O with * p2, then
[2n] + (M1 42) 1) -1 [ + (fi ib2)I
with
- 112
f12 = (11 (22 + (d 1)112)
11 + (d 2)
A (N) (2) + (d 1)l22
19

---

Proof. We compute
I (uz + (#1 p2)1) (#2g + (Āg - 12)11)
= ((1 + (d - 1) + (ï1 N2)
+ (m) - 12) - 1
which yields (m - (2) (12) 1 and uajazd (mn - u2)im (in - 22) 0. From the first equation we have far f/2 1/ (22 and thus by the second equation
Ø (w) - 10-122m11 + (d 12)22)
and hence
11 + (d 2)112 (M) 12) + (d 1)p2)
A1
Calculation of 7sy.
By Lemma B.2 we proceed to compute the different components of
1 A- 10:00=100 -vo(1)
By = A-1 7y -
1TAA-1
First,
A ((d-1))i + 11)
1s.
#I + (d - 1)
Then the denominator yields 1-'A-11- Idtl-11/a"
We then obtain
1 A (1) 11 bz l11 (d 1)12
uo vo _ by + Mn + (d 11)p2 vo(1) 1,
1"A--1 d
which, with A-11 = (ī=1 + (d - -1)122)11- #1+(d-1)pz 1, yields
= 1 by.)
vo(1)
1 ci + A -b.)
d
remains show that
(A-1(G, zJ b1)).
K
1s (tk: 1 E Th))
=
K
un (Tx)
p(Ta)
k=1
With br. = K Σズ=1 =x(((zx) follows
K
A- 1br
1 1 bz)
1
Σ
A-12z
1 -J vo(z)).
d'
K
d
k=
Then A-1 12,,221 + (it Îu2)zz where la is the subset size, i.e. le is the sum of all entries in Zk. It follows with A (d-
A-1 2k
-- = ty (22 d (wr + (d 1)pz)
1 (5i - (12)
2/
tx
u12
For the i-th component, we have with set notation Ta and for the SV weights m(t)
(d- 1)1e! then
(1) (A (A (br to-
b2) (2266))
1
K
tx 1(iE Th)
(Th)
=
K
MI u1
d
1
(im -1 (i)
( U2 22ha-1
where we have used Proposition E.3 for 7 (i). It remains to show that (Mi 42) 22) 1.
20

---

Show that (f1 22))hh-11 = 1. le ((T)) := p(t)/Rt R be probability distribution over Ti. By definition, and as subsets of size have equal probability, we have
d-1
N1 = =
Σ p(z - 1- -
d-1
d x==1 1)
p((1)
Σ
t 1- R
R
and
d-1
12 = = 2j =1
Σ
pZz =
t 2 -
d-1 2 ultt)
Σ
R
2
Hence,
111) R
d-1 m() ΣΣ R
- i ((-1)--
-1--
Σ R 1 1-1) R'
(()
p(l)
d - 2
1
11 11
where we have used the recursion for the binomial coefficient and p(1) - (ー,) Lastly, we have seen in the proof of Proposition E.3 that R 2h which finishes the proof.
B.5 Proof of Theorem 4.7
Proof. We prove the statements in separate subsections. We consider interactions of maximum order
80 2 1, summarized in I := {S C D s = 5o To show that SII and STI are s-efficient, by
Theorem 4.1 it suffices to show that Σsez Y (t, [T, S1) = 0 for all T E Too Given subset
T E To with |T O SI k and k E {0, (0,...,80)) we have
Σ Thhh (4,TTT)))) SEI
Σ k 80 k)
t
7/" 71"h (t, = -
- (1)
( d (d-t) m(t k).
k 80 k)
k=U
k=0
B.5.1
Proof of s-efficiency for SII.
We let m(t) == m Se (t)
(d-t- 90> Mel
(d=00) -1
and obtain
(d 50 +Iy
d0 T
Σ (t, T n S1)
1
k
1
d --t
( 80)
d 80
k
80 k - k.
SET
k=0
We now consider
E-1
d
(d 50
-1
t!
(d t)
(t k)l(d
80 + k)!
k
k
k)
t k
kl(1 k)) (80 k)) 1 80 + k:)!
(d - 80)
K=
k=
Elddd t)!
80
1) (sp k)
(d - (d-s))!
1!(d 1)!
80
880
1))
sol(d su)!
l
k=
t!(d t)!
sol(d so)! (1 1) 80
0,
where we have used the binomial expansion for (1 - 1) Hence,
Th (t. ( 0, Σ
SEI
which finishes the proof of SII s-efficiency.
21

---

B.5.2 Proof of s-efficiency of STI.
For STI, i.. map
STT = Su
(dlt-1)l!! 1]
we have
d!
Σ (TS))
Σ
(-1 80
-
(d L
k 1)!(1 - k)! d!
80
k.
8u - k)
SEZ
k=0
so 50(- 1)
t)!
(d
t k: 1)!
11
sold!
k
(d - t
30 + k))
As (d-i+k-1)! is a polynomial with orders less than so, we can use Σ 20
(50)
0 for m < 80
dd-- to obtain
k=0
38
sol so(-1))ot((d t)!
su (d - k - 1)!
(-))
0,
so!d!
(d 50 +
k=0
which finishes the proof of STI s-efficiency.
B.5.3 Proof efficiency for STI.
clear that s-efficiency of CII implies by Theorem 4.1 of top-order interaction estimates is
with sampling order k: 2 8o that the sum
ssn
(t)
(S).
50
50
SET
SEZ
On the other hand, it also implies that the sum of STI scores for the top-order interactions are
Σ
s
STI
(S).
40
80
SEZ
While lower-order estimates computed exactly for STI, follows that the of STI scores and sum of SHAP-IQ estimates over all interaction sets S., are equal. Furthermore, due to the definition of STI, they must fulfill the efficiency axiom, which finishes the proof.
B.5.4 Proof of efficiency for n-SII.
This result follows from the aggregation suggested by n-SII, which is independent of the index. The efficiency condition follows directly from the SV efficiency and the Bernoulli numbers, independent of higher-order interaction values, cf. proof in [3] Proposition 12]. The proof is based on induction, starting from the SV, where the efficiency condition holds. The specific aggregation based on the Bernuuli numbers then ensures that this efficiency condition is maintained. To apply this observation SHAP-IQ estimates of n-SII, we observe that due to Proposition E.3] SHAP-IQ maintains the efficiency condition for order estimates of higher orders then immediately implies that this efficiency condition always preserved, as the arguments presented therein hold independent of the interaction index, ef. 3 Proof of Proposition 12].
i.e. the SV estimates. The aggregation of n-SII for the SHAP-IQ
22

---

C Algorithmic Details of SHAP-IQ
In this section, we decribe further algorithmic details that are used in the SHAP-IQ implementation.
C.1 Algorithm of SHAP-IQ
The pseudo-code for SHAP-IQ is outlined in Algorithm 1
Algorithm SHAP-IQ for any-order interactions Sap up order 8p Require: Budget K > 0, weights g(t) 2 0 with t [d], precomputed weights (t, E) for 3 ,,..., 80, 0... and & = O,..., K)
1: ko t CETS GETSAMPLINGORDER
2: for T & Tho do
Deterministic
3:
1) + Po (T)
4:
for S E Sso do
5:
Ckp (S) t- Cho (S) + 1 (4, (7,175))
D. Update deterministic part for all S
6:
end for
7: K + K -
8: end for
9: for t = ku...., d ko do
10: p(t) - q(t)/ (Er=Ro g(A))
compute probabilitics Pko ((T) = t)
11: end for
12: for l...., K do
Sampling
13:
T SAMPLE(P, kin)
14: 7 + (T)
for S Sao do
A(S) + 7 (t. (()
Use probabilities
PRo = Pk =)/ x a(t) end for
18: p. 82 < WELFORDUPDATE((i s2, A)
end for
20: mean In + Cкo + ft and variance 8² + s2/(n
21: return i and 6²
C.2 Sampling Weights q(!)
In our implementation, we rely on q(t) & u(t) for 13 - where the weights g(0) = ((d) =
40 0 set to high positive constant, which favors these subsets before weighting the remaining subsets in Ti These weights ensure that SHAP-IQ is equal to U-KSH for the SV. Another choice of weights is (t)) (d=t=so)(t==ol) for t d so and g(t) go otherwise. which prefers all [d- orders up 8q and from d to d 8n- This choice of subset weights may be beneficial for very low budgets, as is important to ensure that Ko 2 8o for SHAP-IQ to maintain the efficiency condition.
The algorithm find ko given weight q and budget K outlined Algorithm 2 The sampling
procedure to generate a subset according to p(T" is outlined in Algorithm
C.3
Welford's Algorithm
Welford's algorithm 45 allows iteratively update the mean and variance using single pass. The algorithm is outlined in Algorithm
23

---

Algorithm 2 Determine the the sampling order ky for the deterministic part
Require: weights q over O,...,d, d, budget K
initialize ku
2: for t = -0....,,OOOH. FFOOR(d/) do
3: = Lk=ko ((b)(H)
b. Normalization
4:
p[t] t (t)((()) /R
5:
pld I1 & qld - (c) R
6:
if K { > and K qld 1) > R then
7:
Ko - kn +1
8:
K K (()
9:
end if
10:
end for
11: return ko
Algorithm 3 Sample a subset 7 p(T)
Require: p with -d- p[k] 1, sampling order ko
for kg...., Ko do
2: p([T] + (i)
3: end for
4: choose subset size to with probability p([T) 1)
5: choose subset T of size la with probability (9)
6: return T
Algorithm Welford Algorithm for Mean and Variance 45
Require: 82, A n n
2: A + A
p p+ A/n
4: 1
5: s2 s2 A,
6: return s2
24

---

D Experiments
For the interested reader, we provide more detailed view on our empirical evaluation of Section We give descriptions and pseudocode of the baseline algorithms approximating the three considered interaction indices SII, STI, and FSI, formal definitions of our synthetic games, and finally further obtained results that we omitted in the main part due to space constraints.
D.1 Baseline Algorithms for SII, STI, and FSI
In this section, we describe our baseline algorithms for SII, STI and FSI. We distinguish between permutation-basee approximation (SII and STT) and kernel-based approximation (FSI).
D.1.1 Permutation-based (PB) Approximation
The algorithm for SII is outlined in Algorithm 5
Note that with each permutation only d +
interaction estimates of order are updated.
Algorithm 5 Permutation-basee sampling for SII for all orders up to so [40]
Require: maximum interaction order $o, interaction set Say- budget K
1: sum[S] + 0 for all S E Sx,
2: count[S] 0 for all S E Sxp
3: permutationCost <- 0
4: for = 1,..., So do
5: permutationCoss + permutationCost +2"
(d- -2
P Evaluate costs per permutation
6: end for
7: while 2 permutationCost do
8: π {i.... ( id) random permutation of D
9: for = 1, ,,....8) 8o do
for = d + do
11:
5 - {i
im - }
T (i,,.... mm 1 the set of predecessors of im
13:
sum[S] - sum[S] (T)
(T) costs 2 evaluations
count[S] count[S]+1
15:
end for
16: end for
17:
K +- K- permutationCost
b. Update budget
18:
end while
19:
SI][S] sum[S]/coun[[] for all S Sag
20:
return SII
The sampling based algorithm for top-order interactions of STI is outlined in Algorithm 6 Note that with each permutation all top-order interaction estimates can be updated. However, the update requires significant amount (permutationCost) of model evaluations.
D.1.2 Kernel-based (KB) Approximation
Given budget of K, we first find the sampling budget by identifying Ko according Algorithm| with weights (t) := (ut)) and subtracting the number of subsets used for the deterministic part. We then sample the remaining subsets according p(T)) x p(l) according Algorithm
25

---

Algorithm 6 Permutation- sampling for STI for all orders up to so 33
40
Require: maximum interaction order $o, interaction set Sag= budget K
1: sum[S] f 0 for all 5 E Sxy
2: count[S] 0 for all 5 E Seg
3: Compute exact (trivial) lower-order interactions
4: eval[S] 0 for all S E Sap-1
Model evaluations for lower-order STI values
5: for S E Sxp do
Precompute model evaluations for lower-order STI
6: eval[[] (SS
7: K + K -
8: end for
9: for S E - do
b Lower-order interactions
for L E (SS) do
SII[S] SI[[S] (-v)--_.vva[[]] eval[L]
Exact lower-order STI values
12: end for
end for
14: Compute sampling-based top-order interaction estimates
15: permutationCost + 20
i> Every S requires to compute 6% with 2 evaluations b Evaluate one permutation
16: while K permutationCost do
æ (i1,...,fd) idd random permutation of D
18: for all top-order interactions S do
im the leftmost element of in 8m-1 the set of predecessors of im in π sum[S] - sum[S] (T')
20:
T - f
8g(T') costs 2 evaluations
22:
count[S] = count[S]+1
end for
24:
K t K- permutationCost
b Update budget
25:
end while
26:
STI[S] +- sum[S]/count[S] for all top-order interactions.
return STI
Given the collection of K subsets (deterministic and sampled), we solve approximated weighted least square objective as
2
ETwp(T)
((T) - Σ B(S)
SES SCT
2
27
v(T) ( Σ B(S)
Σ P(T)
v(T) Σ
B(S)
+ p(T E Tho LT (T)
TETO
SES..
SES.,
SCT
SCT
where ko is found similar to SHAP-IQ and Ph, is probability distribution over Tho with Pko (T) oc (t)), which related to p with pko (T) = p(T)/p(( Tx,). The expectation over Pks then found by Monte Carlo integration. Approximating this objective yields a weighted sum of sampled subsets that approximates the weighted least square problem. This approximated least-square problem is then computed explicitly using
FSI (Z WZ) -izZ))-'" Wy.
(3)
where Z {0. 10.1)xxd is a matrix that represents binary encoding for each sampled subset where
an entry in column S E S., is equal to one, if the subset contains S and zero otherwise. The matrix W К contains the weights for each subset on the diagonal, e.g. p(T) for subsets of deterministic part or p(T E Thg 1/m for subsets of the sampled part, where refers to the number of sampled subsets for Monte Carlo integration. The vector y consists of all model evaluations uo (T), where 7' is in the collection of subsets. To include the optimization constraint, add D to the
26

---

collection with weight set to a high positive constant (mimicking infinite). The algorithm is outlined in Algorithm 7
Algorithm 7 Kernel-based approximation of FSI [26] 40]
Require: maximum interaction order so, budget K, high constant Co >> >> 0.
Weight vector w[''] with one row and column per distinct subset T.
2: Binary subset matrix Z[T; with one row per distinct subset T and one column per interaction subset S.
3: Model evaluation vector BT] with model evaluations v(T) per distinct subset T.
4: Index array: per distinct subset T
5: Initialize constraints
6: w <- APPEND w. co)
7: Z <- APPENDROW( Z, 1T) with 1s of length dxg
8: y < APPEND(y. vo
9: K <- --
10: Deterministie Part
11: for trt= l,..,, do
Initialize subset size probabilities as Pi = t)
d-1 12: p(t) + qtt)/ Ex=l (1+)
13: end for
PUTSAMPLINGORDEE (g. K) 15: for T E Ti and & The do
14: ko
Deterministic
16: Z + APPENDROW(2 BINARY(T))
17: 3 + ApPEND(y. (T))
18: W. < APPEND (0, p(t) (i)
Weight with probability Pı(7) = PP:(
19: K --1
20: end for
Sampling Part
22: we - swm (p()) for Ko < 5 d- ko-
D. Remaining probability weight Sampling
for l.....K K do
24: T + SAMPLE(P, ko)
if E I then
26:
7 <- APPENDROW( Z, BIN)
27:
Y < APPEND(JL , vo (T)
28:
< APPEND w 1)
29:
INDDINDEX
30: else
31:
w|[[T]] + w [[[[]]][+]]
32: end if
33: end for
34: w[[[T]] [ wo K for all T E
Rescaling b Diagonal matrix with diagonal w
35: + DI)G(W)
36: FSI <- SOLVEWLS W.y).
37: return FSI
D.1.3 Computational Complexity of Baseline Methods
To evaluate one permutation for STI, the PB algorithm requires 2 model evaluations per interaction, ie. in total (a) 20 for all top-order interactions. With each evaluated permutation all interaction estimates can be updated. For lower order interactions, STI requires to compute model evaluations for all subsets with |S] Sp- For SII, the complexity is interaction estimates with S E can be updated per permutation, i.e. d + interaction estimates with one permutation. This constitutes significant drawback over the approximations for SV, which iterates only once through the permutation requiring 1 evaluations to update all estimates of the SV. contrast, as for SV, the KB approach FSI allows to update all interaction estimates using single model evaluation. However, the KB approach of FSI always requires estimate all interactions with order S 8q and its computational effort increases non-linear with the number of subsets used, solving the weighted least square problem requires inverting K deg matrix.
+ 1) 2" per permutation and only
27

---

D.2
Further Information about the Models
This section contains detailed information about the models (SOUM, LM, and ICM) used in our experiments.
D.2.1 Sum of Unanimity Model (SOUM)
Definition D.1 (Sum of Unanimity Model (SOUM)). For subsets Q1..... QN S D and coeffi- cients 01 aN E R the sum of unanimity model (SOUM) is defined as
N
((T)
an 1Q,, ST).
For SOUMs, it possible to efficiently compute the ground -ruth values for CII. Proposition D.2 (Ground-truth values for SOUM). For SOUM, it holds
(S) Σ anu |Sn Qnl);
with
d
Amaz (r)
k: (d (s m))
( (5-1) (t,
r( = Σ
1 q k
l=
k=0
and kman(T) (T) min(t q,
Proof. Due to the linearity of the CII, it suffices to compute the CII for vQ( == 1(Q S T). By
Theorem 4.1 we have
mme (S) Σ IQET))"(((
TCD
kmux
d q- (s (s- (5) (s-1s
( ( (t*
t 9 -
k=
=: w; Q!),
where used that Qns C TNS due 1Q C and [Tn ISQ (1 where h : [[" n 8) (S ( Q) ranges from 0 to kmaz == min(1 - g, 8 - S Since n is fixed, we need to count the number of subsets T of size f, given k. such that [Tn = |S
We count (*-IsnQ)) ways to choose subsets of elements that are not S Q but are in S. Then q - (s n Q1) elements T are fixed. We thus select from d d- q - (s |S Q)) elements exactly (. k elements, as q and & elements are already contained in T.
Finally, the CII value is given
N Σ
anw |S
where the weights be precomputed with |Sn Qnl (0,
8]. 8).
D.2.2 Language Model (LM)
For a language model (LM), we use fine-tuned version of the DistilBERT transformer architecture
34 on movie review sentences from the original IMDB dataset (27 for sentiment analysis, i.c. has values in [-1, 1]. The IMDB data stems from the dataser library 22 In the LM, for a given sentence, different feature coalitions are computed by masking absent features in a tokenized sentence. The
implementation is based on the transformers API 47
'The model can be found http:://wgggnngge...ccocalllllls
28

---

D.2.3 Image Classifier (ICM)
The image classification model (ICM) is a ResNet18 [9 pre-trained on ImageNet [1] as provided by torch [30]. We randomly sample 50 images from ImageNet []] and explain the prediction the highest probability class given the original image. To obtain the prediction of different coalitions, we pre-compute super-pixels with SLIC 1 44] to obtain a function on d = 14 features and apply mean imputation on absent features.
D.3 Hardware Details and Environmental Impact of the Experiments
Running the experiments required approximately 2 2000 CPU hours in total. The experiments concern- ing the approximation quality of SHAP-IQ compared to the baselines were run on computation cluster on hyperthreaded Intel Xeon E5-2697 v3 CPUs clocking with 2.6Ghz. To further increase the efficiency of the experiments, the outputs of the LM and ICM were pre-computed given the powerset of all features. Around 500 CPU hours were consumed for these experiments on cluster. Before running the experiments on the cluster, the implementations were validated on Dell XPS 9510 containing an Intel i7- 1800H at 2.30GHz. For this and further small-scale experiments like the n-SII values approximately 500 CPU hours were consumed.
D.4 Further Experimental Results
This section describes the further results and experiments omitted in the main body of the work.
D.4.1
Approximation Quality of top Order Interactions.
We further compute interaction scores for = 1, su 2, = 3, and So = 4 of all three interaction indices SII. STI, and FSI on the LM. We plot the MSE and Prec 10 based on g 50 independent iterations for these settings. All results are summarized in Figure Moreover, we compute interaction of all three interaction indices SII, STI, and FSI on the ICM. The MSE and Prec 10 based on g = 50 independent iterations for these settings are shown in Figure Further results to the plots show in Section 5.2 for the SOUM are presented in Figure
scores for 8p 1, 80 8g 3, and &g
D.4.2 n-SII Estimation on Example Sentences.
We further probe the LM with randomly selected sentences from the IMDB dataset and estimate the scores up to order 4. For the example sentence "It a gruesome cannibal movie. But it's not bud. If you like Hannibal, you'l 'Il love this." in Section 5.2 all orders of n-SII with are illustrated in Figure 9 Another example sentence have never forgot this movie. All these years and it has remained in my life." with all orders of n SII up to the maximum interaction order 80 = 1, 3, 4 is shown in Figure 10 Lastly, for four sentences n- n-SII for all orders with sg = 4 are visualized in Figure]
1, 3,
29

---

BIL ST, and FSI for is 44
SIL STL and F3I LMG d=16
ST. SEL
and
LM (Ay
Nethod
Order
Neched
Onder
2.5
0.50
Mathos
Order
1
Maae 13
0.26
1000
2238
0.32
0.37
2.66
26:
0.22
0:27
0.89
241
6-72
3.00
0.32
0.24
6-22
6.8.
5I STL and FSI te 33, 144
SIL STL and for WW 110
1.00
58, STL and FSI for LM (So 3. 141
0.90
Methoal
Orein
54-P 10
Pa
SHAPP- Emasiina
Eeaidine
0.5
0.3
2035
0100
6183
R0D0 I6GO 33300 1800 3400
0.
2015 d008
6300
HAG6 12550 1860 34003
0.08
2003
5030
4003
13030 12153 14000 H400
modd crabetona naaatred
modd arabetore toauditte nilatie
Tode wwikuttoo (abiekon
2:0
for tsy
for
ST. and FSI IM
Nethol Deadine
1.75
1.5
1.20
0.90
0.75
0.58
0.5
SHANO Buddii
3202
4003
+2830 12003 36600
2202
4250
1000
22380 LATDE 38600
moee coluaatioa (ibiilit, vilivs
model cuakuatione (ibakka,, BEAEE
26.3
(S
Mathed
Order
2.5
2.-
1.0
022 5.69
oxtatira
Figure 6: Approximation Quality for LM with interaction order 80 = for y = 50 iterations (first row), with interaction order 80 = 3 for 50 iterations (second row), with interaction order so = 2 for g = 50 iterations (third row), and with interaction order sg 1 (Shapley Value) for = 50 iterations (fourth row).
30

---

2:30 26-2 Sli STI, and FSiifrricM is, md, 14)
Jecs Si. STI, and FSi ION Is
14)
SEL and DAg
Nathod
Order
Nethod
Order
Nechod
Order
1.75
1.80
1.25
0.50
1.8
0.75
0.22
0.20
0.25
2007
6:32
0.2
331
8:00
9.10
3.00
0.22
1.50
0.32
0.4 4A1
640 3al
6-22
6.6.
S)L STI, and for (ng 3 141
SI. STI, and FSI for IOM Ity 3. 14)
1.00
SL 5T), and ISI for ICN (s. 3. 3.d 14)
SHUP-1 Beadiie
S46-40
Deadite
0.90
MIDE
SHAR1
0.0
2005
4000
6003
5100
16:00
19300
1860 34500
2003
4230
4000
U0000 1,00 18030 14003
0.0
2003
5030
4003
13030
32153
14566
3640
modd wrabetone laaadita ndaaied
evauudeTa rublivl
TOde ewicutior (abiekos
SIL STI, and LCM
and for
SU and
Nethol Ocadine
Order
Nethod
Onder
Desdine
20-
15.
0.80
14-
0.2
SHANO
Duddii
2203
32303
30000
2008
22300 1800
22280 LATDE 38600
mudil mekkatons paodute ndateo
modil mualution Boaddaaee vilate)
model cunkuatione (Sbakka,, BEAEE
Co.
Mathed
Order
3.24
mode
Figure 7: Approximation Quality for ICM with interaction order 8o for g = 50 iterations (first row), with interaction order 80 3 for 50 iterations (second row), with interaction order so = for g = 50 iterations (third row), and with interaction order 5g 1 (Shapley Value) for = 50 iterations (fourth row).
31

---

2e-1 511,, SOUM Lig 2. 30)
Nathoa
Order
Methoe
Onter
2.30
1.75
1.50
0.40
0.75
0.58
0.28
0.2
0.38
2307
4058
6080
59130
32397
34000 30000
2000
4500
5500
#233
L0000
12000
3.000 18300
0.08
2307
4020
1607
1200
59030
32500
14500 36600
1e-1 STL and FSI for SOUM (s d1 31)
SHOP10
2.0
Dassiiie
1.5
1.-
0.5
3.0
3006
4003
6005
9993 19359 12000
34630 38000
Figure 8: Approximation Quality for SOUM order so 2 (first row) and so 1 (Shapley value, second row) for g = 50 iterations on the SOUM with N 100 interactions, 30 features, and mmax = 30.
n-S1l valluss sentence provided
n-Sli vallues for sentence provided to the LM
0.30
Order
Order 1
= Order 2
0.25
0.20
0.15
m-5 values
0.5
0.05
0.00
-05-
6.05
0010
#ebbll
you
hamotlaa
Hammntial
youy
n-Sll vallues for sentence provided to the
n-Sil values sentence provided
Order
Order 2
Order 3
40-
Order
Order
Order
Order
30
20
1.0
metiel
wil
hanoipal
Figure 9: Estimated SII values with orders s = 2,2,3, for the sentence "It is a gruesome cannibal movie. But it's not bad. If you like Hannibal, you 'll love this." (d 23) provided to the LM. The plots show all orders of S-III with maximum interaction order so = 1 (top left), so = 2 (top right), so (bottom left), and so (bottom right).
32

---

n-SIl values for sentence provided the LM
n-Sii values for sentence provided the
0.75
0.50
5
0.25
0.00
-0.1
022
-0.0
-0.5
-0.3
have
rorver
Hurpor
chis
mosle
All thew
yeiry
ard
remairent
In
have
Iarger
the movil
al rheee
yeurs
liss Rimalten
in
n-Sll values for 3 sentence provided to the LM
n-5li values for sentence provided to the LM
Order
Order
Order2
Order
20-
tave
cxever
furget
Hid
movi
of
pent
and
renareed
have
never
forpet
Help
tiesee
yours
ienatted
Figure 10: Estimated SII values with orders 1,2,3, 4 for the sentence "I have never forgot this movie. All these years and it has remained in my life." " (d = 16) provided to the LM. The plots show all orders of n-SIl with maximum interaction order sg 1 (top left), so 2 (top right), so 3 (hottom left), and 80 = 4 (bottom right).
n-511 values for sentence provided to the LM
n-Sill vallues for a sentence provided to the LM
Order 1
Order 2
Order 3
Order 4
Order 1
Order 2
Order 3
Order 4
10-
15
nothing
1x
selog
about
Intel
of
frem
-15
actuadty
the
entiigg
even
dtd
nat
serss
Sil values sentence provided
n-5ll values sentence provided
30
Order
Order
Order
Order
40-
Order
Order
Order
30-
20
20
10w
-10
howeeer
the
na
march
rreited
and
creer
ererg
of
let
mud
cun
nasmiaal
pnll
live
Figure 11: Estimated S-III values with so = 4 for the sentences provided to the LM: "Absolutely nothing is redeeming about this total piece of trash." (d 12, top left), "I actually liked the ending even though it did not make a lot of sense." " (d = 15, top right), "However, really liked the ending so much, I actually smiled and cried tears joy. I felt good." with (d = 19, bottom left), and "It is gruesome cannibal movie. But it's s's not bad. If you like Hanmibal, you'l Ill love this." (d = 23, bottom right).
33

---

E Further theoretical Results for the Shapley Value
In this section, give two additional results for the special case of the SV. We explicitly state the inverse the covariance matrix from g and further present simplified representation SHAP-IQ. if applied on the SV, which aligns with Theorem 4.4
E.1 Explicit Inverse of Covariance Matrix of Unbiased KernelSHAP
The covariance matrix has been explicitly computed 8 Appendix A]. In this section, we provide the explicit form of the inverse A This inverse admits the same structure and is a central element in the explicit calculation of U-KSH as a weighted sum, which is linked to SHAP-IQ.
Proposition E.1 (Explicit covariance matrix (8). For the covariance matrix it holds
A = Elzzzi = u2dJ + (11 - 12)
with i.j E D and constants
d-1 2k
A = := P(z: = 1)
Ag = P2 = PIZ: = Z3 = =) d(d - Di Md-A)
2
Proof.
The proof is given in 8 Appendix A].
We have for Eiel k(d- = 2h where h, is the n-th harmonic number. Furthermore Y1 122 2ha-1' We now give the explicit form of A-
Proposition E.2 (Explicit inverse of covariance matrix). Let A B|ZZ"]. explicit form of the inverse A as
Then, we have
A- = i + (in i
with constants
(a- := 2h in + (d - 22
(A == f12 = -2
-H2 + (d - 1)
#1 + (d - 1)H²
Proof.
The proof follows directly from Proposition E.1 and Lemma B.2
E.2 Simplified Representation of SHAP-IQ for the Shapley Value
In this section, give explicit form of SHAP-IQ for the SV that admits a similar form as the SV representation in Theorem 4.4 We consider the SV weights m(f) == (d-t-1)tt Proposition E.3 (SHAP-IQ for SV). For SHAP-IQ with p(T) x p(t) and sampling order ko 1, it holds
d!
K
2ha-1 (1) = c1) +
Σ (TTTT ((1E 4x
K
d
where bn is the n-th harmonic number.
Proof. Recall the definition of SHAP-IQ of order 1
(TT)) th (1R, Th n (i)l)
fre()) (=))==c(1)
Σ
p(Tx)
with p(Tx) := p(t))/R & ((tx). We proceed by rewriting "n (tz, [T n {i))) = (t, 1 Tx))
for T3 E T1 as
2 (4,, 1(i Tx)) (-1) ( (d-t- 1+ 1(2
d!
=((t) E (w) - 1(i TW)a
= =((t) ((1ET)))
4
d
34

---

Hence,
k
((t) [1 E Tx)
4/
(1) +
(Ta)
K
p(Tk)
k=1
(i) +
R
Σ (Tx:)
((iEE
Tx) -d
1/
K
For the normalizing constant, we have
R=
p(t) x(t
E p(t)
d-1
())
1)
Σ
d-1
t(d
d
t)
Σ
d-1
d-t)
1
2ha-1
TETI
which finishes the proof.
35

---

Approximation Methods for the SV
There are two prominent representations the SV, which used for sampling-based based approximation. Both allow to update all SVs simultaneously with one sample as well as maintaining the efficiency property.
F.1 Permutation-based (PB) Approximation
Permutation-basee (PB) approximation was introduced for SV [5] It based on the observation that the marginal contributions (T) U ((T) be computed by using permutations the sets that consist of all elements preceding in æ with and without i, respectively. For for each subset C {i) of size
E GD of D and v(u, (T)) (m),(T)), where u, (Tr), u, (Ir)
there are exactly (!(d L 1)! permutations with = uq (T) and thus
T (1) d!
1
Σ TEED
8f (w) Ex-uni((e (f
This expectation be efficiently approximated by sampling ग unif(@p) and using Monte Carlo estimate for the expectation. As EieD 6, (x)) v(D) v(0) for arbitrary permutations т, the efficiency constraint is maintained throughout the sampling procedure. The Monte Carlo estimates allows to apply well-established statistical results obtain bounds the approximation error
F.2 Kernel-based (KB) Approximation
Kernel Shapley Additive Explanation Values 26 short KernelSHAP (KSH), and Unbiased Ker- neISHAP (U-KSH) & make use of the representation of the SV the solution constrained quadratic optimization problem [6]
Sv
arg min B
Σ u(t) (o(TT) - Σ
3:
TET
TE
(4)
Σ IED
& vo(D)
with vo(2) == -(T) -(0)), Ts (TCD D k
and p(t) == - This quadratic optimization problem can be solved explicitly using the weighted least square solution
sv wZ) -'z,Wy.
(5)
where {0, (0,1)2 is wose binary encoding of all subsets 7f S D, W E x2*x2 is diagonal matrix with the subset weights μ and y consists of the evaluations of no (T) for each subset. To include the optimization constraint, the (otherwise undefined) weights p(d), (0) of and 0 high positive constant. Solving (5) still requires 2d model evaluations and thus KSH (26 approximates SSV by considering
(5) as an expectation
2
[( -1
2
E() (o(T) Σ - SE
x ET
Σ SET
3,
TET
with p(T) ptt). Note that the optimization problem is invariant in terms of scaling. This expectation the approximated similarly to SHAP-IQ, by computing high and low subset sizes explicitly and using Monte Carlo integration for the center sizes. The KSH estimator is difficult to analyze and is only known that is asymptotically unbiased [46].
KSH constructs collection of subsets by determining a sampling order ko. such that subsets with kn < S hi are sampled from p(T) x p(t) and for kn or > - ko all possible subsets are used. The value of ko is thereby found by successively comparing the expected number of subsets with the total number of subsets of that size. As the number of subsets (o) for fixed d is symmetric
36

---

log-con log-concave sequence of positive terms. it has maximum at the middle term(s) 1/ [ and grows monotonically and symmetrically (t) _ towards this maximum from both sides. Thus, the implementation starts the comparison at kg = 0 and iteratively increases the ko candidate.
37


Reviews:
[{"review_id": "rZCBTiRuSH", "reviewer": "Reviewer_wrD8", "summary": "**Context.** This paper aims at quantifying the contribution of a set of features to the prediction of a machine learning model by leveraging the Shapley value (SV), a principled tool coming from cooperative game theory. Previous works either focused on (i) estimating the contribution of a single feature (via feature importance scores) or on (i) estimating the contribution of a group of features (via feature interaction scores) through different extensions of the SV to features interaction (e.g. SII, STI or FSI). As of today, no unified framework or methodology to compute feature interaction scores has been proposed. This paper tries to fill this gap.\n\n**Contributions.** The authors made the following set of contributions.\n* They propose a novel perspective and representation of the cardinal interaction index, agnostic to the size of the features' group to be valued. This representation leads to the SHAP-IQ function unifying previously proposed feature interaction scores.\n* They propose a theoretical analysis of SHAP-IQ with both statistic properties (bias, consistency) and non-asymptotic theoretical guarantees in the form of high-probability deviation bounds.\n* They illustrate the benefits of their approach on several experiments.\n", "questions": "See previous section.", "limitations": "Yes, done at the end of the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper and contributions are timely and of interest for the ML community.\n* The paper is clear and well-written.\n* I did not fully check in details the Appendix but the first derivations (first 5 pages) in the Appendix are correct and well detailed.\n* The related work part spanning both the Introduction and Section 3 is clear and relevant. I appreciated the links made between SHAP-IQ and previous works.\n* SHAP-IQ (based on Monte Carlo integration) allows to re-use the same sample for all groups of features.\n* Experiments are convincing and well-chosen.", "weaknesses": "* Theorem 4.3 is quite classical since SHAP-IQ stands for a Monte Carlo approximation and proofs techniques to obtain high-probability deviation bounds via Chebyshev inequalities have been commonly used in works on Shapley value. Could the authors go beyond this simple theoretical analysis and provide more insights on the impact of key quantities of the problem (e.g. $\\nu_0$ and $S$)?\n* Full computational complexity and benchmark with competitors: The computational complexity of SHAP-IQ depends on several things: number of Monte Carlo draws, finding the right sampling order $k_0$, pre-computing of the weights $\\gamma_s^m$,... Could the authors clarify the full cost and compare it to previous approaches competing with SHAP-IQ?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the anonymous reviewer for carefully reading and evaluating our submitted manuscript.\n\n- Theorem 4.3 is quite classical since SHAP-IQ stands for a Monte Carlo approximation and proofs techniques to obtain high-probability deviation bounds via Chebyshev inequalities have been commonly used in works on Shapley value. Could the authors go beyond this simple theoretical analysis and provide more insights on the impact of key quantities of the problem (e.g. $\\nu_0$ and $S$)?\n\nIn our work, we present a novel representation of the CII, which we approximate by a modified Monte Carlo approach (using a sampling order $k_0$).\nWe support this method by classical and meaningful theoretical results related to Monte Carlo sampling, such as unbiasedness and consistency. These properties have not been shown for the baselines.\nWe further provided a deviation bound that requires as little assumptions as possible.\nIn a model-agnostic setting, we suspect that robustness assumptions on $\\nu_0$ are required to obtain stronger results, which, in ML context, would imply assumptions on the estimate of the conditional distribution that is used to define $\\nu_0$, cf. [3].\nAnother promising approach is to restrict the analysis to model-specific games, such as the seminal work on TreeSHAP [24] that computes the Shapley value in polynomial time.\nFor tree-based models, we believe that it is possible to exactly compute the CII in polynomial time, which we are interested to study in future work.\n\n\n- Full computational complexity and benchmark with competitors: The computational complexity of SHAP-IQ depends on several things: number of Monte Carlo draws, finding the right sampling order , pre-computing of the weights,...Could the authors clarify the full cost and compare it to previous approaches competing with SHAP-IQ?\n\nFor an extensive discussion on the run-time efficiency of the baseline methods we refer to appendix~D.1.3.\n\n1. **Sampling order $k_0$:** The computation of the sampling order $k_0$ is a constant time operation given a number of features $d$ (it scales linearly with $d$ but this is negligible), cf. Algorithm 2 in the appendix. \n2. **Weights $\\gamma_{s}^{m}$:** The additional computational burden from a pre-computation of the weights $\\gamma_{s}^{m}$ is also negligible since it scales linearly with the number of features (number of possible subset sizes) and, in particular does not depend on $\\nu$, cf. line 220-221.\n3. **Main computational costs:** The main computational cost stems from the model evaluations (access to the value function $\\nu_{0}(S)$), which is bounded by a model's inference time / scale. \n    We ran a run-time test for the language model (LM) showing how the run-time increases slightly compared to baseline approaches (please see Fig.~1 of the pdf document uploaded under ``Author Rebuttal''). With increasing $K$ the run-time complexity scales linearly, but the overhead of SHAP-IQ is quite low. Note that all pre-computations of SHAP-IQ are included in our evaluation. The difference in STI is a result of less than $K$ model evaluations , cf. lines 15-16 in Algorithm 6 (in the appendix), which is required to maintain efficiency.\n\nThe small run-time analysis will be added to the appendix of the manuscript."}, {"review_id": "ZdlHEvTs5v", "reviewer": "Reviewer_JZ6i", "summary": "The paper proposes a new sampling-based approximation method called Shapley interaction quantification(SHAP-IQ) for the cardinal interaction index(CII), which is a generalization of the Shapley interaction index. To this end, the authors give a novel representation, and showed that SHAP-IQ is an unbiased and provide a general  approximation bound for the quality and variances of the point estimates. Finally, they demonstrated that SHAP-IQ provides the effectiveness and nice explanations for language model and image classification models.\n", "questions": "- In Figure 2, how are the top-k interactions determined? Are they based on the largest absolute value or some other criterion?\n- How should the illustration on the left of Figure 3 be understood?  Each word is assigned both positive and negative values. What does this mean?\n", "limitations": "Yes.\n\nBelow are the comments for improvements.\n- SOUM is known as the induced subgraph game[1]. The interaction subsets correspond to hyperedges of a graph G and  a is its weight. The value of a subset T is given by the summation of edge weights of a subgraph induced by T.\n- In Definition 4.2, K -> k_0? or K seems not be defined.\n\n[1] Deng, Xiaotie, and Christos H. Papadimitriou. 1994. “On the Complexity of Cooperative Solution Concepts.” Mathematics of Operations Research 19 (2): 257–66.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Provide a unified approach for CII, which is a generalization of unbiased KernelSHAP, and so on. \n- SHAP-IQ is an unbiased and its quality and variance are guaranteed to bound theoretically.\n- SHAP-IQ empirically provides lowest mean square error compared with other baseline algorithms. ", "weaknesses": "- The results are solid, but they are not particularly surprising. The contributions are somewhat limited to achieve an unbiased method and theoretically bounding the accuracy.\n\n- Shapley interaction index implies that the number of features to be observed exponentially increases, which in turn may make interpretation more difficult. In some cases, multiple sets of features may have similar importance scores. In such situations, selecting specific sets of features may not be done in a naive way. It would be better to provide a measure to choose them or an approach to reduce the number of feature subsets to be observed. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the anonymous reviewer for carefully reading and providing helpful feedback.\n\n- Shapley interaction index implies that the number of features to be observed exponentially increases, which in turn may make interpretation more difficult. In some cases, multiple sets of features may have similar importance scores. In such situations, selecting specific sets of features may not be done in a naive way. It would be better to provide a measure to choose them or an approach to reduce the number of feature subsets to be observed.\n\nYes, higher order interaction scores need to be filtered or post-processed.\nHuman-centered post-processing techniques of feature importance or interaction scores are an interesting and important line of research.\nYet, in our work, we focused on an efficient and reliable approach to approximate these scores as a foundation.\nThe theoretical properties of SHAP-IQ can be used to detect ``significant'' non-zero feature interaction scores sequentially using statistical tools, e.g. hypothesis tests on the estimates, cf. line 209-210.\nIn particular, SHAP-IQ allows to selectively estimate interaction scores of interest, in contrast to the baselines of FSI and SII, cf. line 225-226.\n\n- In Figure 2, how are the top-k interactions determined? Are they based on the largest absolute value or some other criterion?\n\nThe top-k interactions were determined in regards to absolute value. We will make this clearer by adding a description to line 260-261. \n\n- How should the illustration on the left of Figure 3 be understood? Each word is assigned both positive and negative values. What does this mean?\n\nThis visualization of n-SII was introduced in [5], cf. line 284-285.\nFor each feature, it displays the sum of positive and negative interaction scores, where this feature is present.\nThe interaction scores are thereby distributed equally onto each feature in the feature subset $S$.\nThis was theoretically justified in Theorem 6 in [5] and yields that the sum of all bars of each feature are equal to the Shapley value of that feature. We will include an additional line of description of this visualization in line in 284-285.\n\n- SOUM is known as the induced subgraph game [1]. The interaction subsets correspond to hyperedges of a graph G and a is its weight. The value of a subset T is given by the summation of edge weights of a subgraph induced by T.\n\nIndeed, the SOUM could be viewed as an extension of this subgraph game on a hypergraph with edges of different order, i.e. different number of connected nodes. \nWe will add this note in the manuscript.\n\n- In Definition 4.2, $K -> k_0$? or K seems not be defined.\n\n$K$ is the number of drawn Monte Carlo samples. We would further clarify this in Definition 4.2."}, {"review_id": "OQXyQrtw2F", "reviewer": "Reviewer_xK2B", "summary": "This paper presents a novel method, SHAPley Interaction Quantification (SHAP-IQ), for efficiently computing Shapley interaction indices in the context of explainable artificial intelligence (XAI). Shapley interaction indices extend the concept of Shapley values, a method from cooperative game theory, to measure the contribution of interactions between features in a model. The authors propose SHAP-IQ as a unified sampling-based approximation method that can be applied to any Cardinal Interaction Index (CII). They provide theoretical guarantees for SHAP-IQ, showing that it is unbiased and consistent, and provide a general approximation bound. They also discuss the computational complexity of SHAP-IQ and how it compares to other methods. The paper also presents a new representation for the Shapley value (SV) and shows that in the special case of single feature subsets, SHAP-IQ provides novel insights into the SV and greatly simplifies the calculation of Unbiased KernelSHAP (U-KSH). The authors conducted multiple experiments to illustrate the approximation quality of SHAP-IQ compared to current baseline approaches. They compare the baseline methods with SHAP-IQ using different evaluation metrics. The paper concludes with an appendix that provides further theoretical and experimental results for SHAP-IQ, including additional results for specific CIIs such as SII, n-SII, STI, and FSI. The appendix also includes all proofs of theoretical results from the main paper, further insights into the implementation of SHAP-IQ, and additional experimental results. In summary, this paper presents a novel method for computing Shapley interactions, provides theoretical guarantees for this method, and demonstrates its effectiveness through a series of experiments.", "questions": "Could the authors discuss some future works about the SHAP-IQ?", "limitations": "Yes, the authors have discussed limitations well.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: The authors propose a novel method, SHAPley Interaction Quantification (SHAP-IQ), for computing Shapley interactions for arbitrary cardinal interaction indices (CII). This is a unique contribution to the field of explainable artificial intelligence (XAI), particularly in the context of black box models. The paper not only presents the new method but also includes a detailed comparison with existing methods, an exploration of its theoretical properties, and a demonstration of its practical application. This comprehensive approach strengthens the authors' claims about the effectiveness of SHAP-IQ.\n\n**Quality**: The paper provides a rigorous theoretical foundation for SHAP-IQ, including proofs of its properties such as being unbiased and consistent. The authors also provide a general approximation bound for SHAP-IQ.\n\n**Clarity**: The paper is well-structured and clearly written. The authors provide a clear explanation of their method and its theoretical underpinnings, making it accessible to readers with a background in the field. The appendix provides additional theoretical and experimental results, further supporting the claims made in the main paper. It also includes all proofs of theoretical results, providing transparency and allowing readers to fully understand the theoretical foundation of SHAP-IQ.\n\n**Significance**: The authors demonstrate the practical application of SHAP-IQ through a series of experiments. They show that it can be applied to different machine learning models and datasets, and that it outperforms existing methods in terms of approximation quality and computational efficiency. This suggests that SHAP-IQ could have a significant impact on the practice of XAI.", "weaknesses": "This paper has no obvious weakness. The main concern from me is the reproducibility of the experiments, which seems like requiring too many computational resources.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the anonymous reviewer for their thoughtful and thorough assessment of our submitted work. We greatly appreciate the detailed list of strengths and contributions of our submitted manuscript.\n\nWe strongly believe that the utilization of feature interaction scores will improve the quality of explanations in many application domains.\nOur additional ideas for future work include the following areas:\n\n- **Real-world applications:** Applying SHAP-IQ across different domains, such as NLP and bio-medicine to improve understanding.\n- **Human-centered post-processing:** Post-processing of interaction scores to enhance interpretability for practitioners and ML engineers. For instance, viewing the interaction scores as a local Shapley GAM [5] constitutes an interpretable model that could be further distilled into human-readable code [Ravina.2021].\n-  **Model-specific variants:** Improving the computation of SHAP-IQ, especially in model-specific settings, such as tree-based models, cf. TreeSHAP [24].\n-  **Sequential Evaluation:** Utilize the statistical properties of SHAP-IQ to further improve estimation and generate confidence bounds or conduct hypothesis tests. Possibly, computing SHAP-IQ scores sequentially for tasks such as feature selection or detection of relevant interactions.\n\n**Reference:** [Ravina.2021] Walker Ravina, Ethan Sterling, Olexiy Oryeshko, Nathan Bell, Honglei Zhuang, Xuanhui Wang, Yonghui Wu, Alexander Grushetsky: Distilling Interpretable Models into Human-Readable Code. CoRR abs/2101.08393 (2021)"}, {"review_id": "ZdOVRKduTx", "reviewer": "Reviewer_cGA2", "summary": "This paper presents a unified approximation technique for Shapley interaction indices. It reformulates the general form of various Shapley interaction methods (Shapley interaction index, Shapley-Taylor, Faith-Shap) from a sum involving the set in question to a sum not involving the set, but instead a computation involving the method weights. This allows one call of the function to be a Monte Carlo integration sample of every set of inputs the method is calculating a value for. Theoretical guarantees of unbiasedness and efficiency are provided, as well as probabilistic error bounds.", "questions": "-Could you clarify, is this method an application of a technique used to approximate Shaley Values, but applied to interaction indices? If so, would you point out where this is is stated. If not, could you elaborate on the novel contributions?\n\nMinor issues:\n(153) Please define $\\mathcal{G}_D$.\n(130-132)_ Please clarify, this secion is dificult to follow.\n(174) - the commas and grammar are off in this sentence.", "limitations": "Application to Faith-Shap as mentioned above.\nThe method applies to to a type of interaction form that is fairly general.\n", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Clear writing, very easy to follow and presented plainly.\nInteresting and practical results which apply to multiple methods.\nimprovements over baseline is apparent in experiments.\nThe results are general enough that they are likely to apply to future methods.\n", "weaknesses": "Faith-Shap not fully addressed. But this seems to be in part to the inherent differences of that method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the anonymous reviewer for carefully reading and appreciation of our submitted work as highly relevant in terms of theoretical and empirical contributions.\n\n- Could you clarify, is this method an application of a technique used to approximate Shaley Values, but applied to interaction indices? If so, would you point out where this is is stated. If not, could you elaborate on the novel contributions?\n\nSHAP-IQ is directly motivated as a Monte Carlo approximation of the novel representation of the CII in Theorem 4.1.\nWe found that in the special case of Shapley values, it directly corresponds to Unbiased KernelSHAP (U-KSH), cf. Theorem 4.5, and can, thus, be seen as a generalization of U-KSH with a greatly simplified computation (cf. line 330-332).\nHowever, our motivation based on Monte Carlo sampling differs fundamentally from the motivation of U-KSH, which relies on the weighted least squares representation, similar to KernelSHAP.\nWe would further like to point out that in case of CIIs the motivation of U-KSH, similar to KernelSHAP, is impossible to utilize, as the representation as a weighted least square problem is unclear (cf. line 321-323).\n\n- Minor issues: (153) Please define $\\mathfrak{G}_D$. (130-132) Please clarify, this secion is dificult to follow. (174) - the commas and grammar are off in this sentence.\n\nThank you for pointing out the minor improvements in our manuscript, which we will address."}, {"review_id": "pL6cYtCk7N", "reviewer": "Reviewer_VdQo", "summary": "This paper provided an unified perspective to several existing Shapley-based interaction attribution methods as Cardinal Interaction Index (CII), in addition provide a more efficient sampling based approximation method. Connection between their formulation with unbiased KernelSHAP is established and they showed that their formulation can also improve the standard SHAP algorithm.", "questions": "Not really from my side.", "limitations": "Not really from my side. Potential improvements are stated in the weakness section.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The unified formulation of several interaction attribution methods as CII is novel to the best of my knowledge in the X-AI literature. The authors made their claims and novelty very clear as well. ", "weaknesses": "I think the content of the paper is very well written so not much weakness to comment. One thing that tricked me a bit is in line 33-34 when first mentioned CII it would be nice to have a citation to show that this is not your original contribution. Also in line 129 the \\mathcal{S}_{s_0} notation is not defined properly so that stopped my flow a bit too.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the anonymous reviewer for carefully reading and appreciation of our submitted work.\n\nWe will follow your suggestions and add the reference for CII [11] already in line 33-34 and refer to the definition of $\\mathcal S_{s_0}$ (given in line 84) in line 129 to improve readability."}]

Author rebuttal:
We would like to thank the anonymous reviewers for carefully reading and evaluating our manuscript. As a response to reviewer wrD8, we have uploaded a run-time plot showing the computational effort of SHAP-IQ compared to baseline methods on varying budgets.

Meta-review: This paper looks at evaluating the importance of the interactions of features in a model, an approach sometimes used with the Shapley value technique without the interacting perspective.

It is a good first step toward a nice and formal model of the problem and the reviewers are all positive !
Decision: Accept (poster)