Towards Attributions of Input Variables in a Coalition
Authors: Xinhao Zheng
Huiqi Deng
Quanshi Zhang
Venue: ICML 2025 poster (2025)
Keywords: Attribution methods
Shapley value
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: This paper proves the internal mechanism for the conflict of attributions computed under different partitions of input variables.

Abstract: This paper focuses on the fundamental challenge of partitioning input variables in attribution methods for Explainable AI, particularly in Shapley value-based approaches. Previous methods always compute attributions given a predefined partition but lack theoretical guidance on how to form meaningful variable partitions. We identify that attribution conflicts arise when the attribution of a coalition differs from the sum of its individual variables' attributions. To address this, we analyze the numerical effects of AND-OR interactions in AI models and extend the Shapley value to a new attribution metric for variable coalitions. Our theoretical findings reveal that specific interactions cause attribution conflicts, and we propose three metrics to evaluate coalition faithfulness. Experiments on synthetic data, NLP, image classification, and the game of Go validate our approach, demonstrating consistency with human intuition and practical applicability.

Towards Attributions of Input Variables in a Coalition
Xinhao Zheng'
Huiqi Deng'
Quanshi Zhang'
Abstract
S2 Face interaction
Sq
Ear interaction
Mouth
1(52)
((S))
1(Sa)
This paper focuses on the fundamental challenge of partitioning input variables in attribution meth- ods for Explainable AI, particularly in Shapley value-based approaches. Previous methods al- ways compute attributions given predefined par- tition but lack theoretical guidance on how to form meaningful variable partitions. We identify that attribution conflicts arise when the attribution of coalition differs from the sum of its individ- ual variables' attributions. To address this, we analyze the numerical effects of AND-OR interac- tions in Al models and extend the Shapley value to a new attribution metric for variable coalitions. Our theoretical findings reveal that specific inter- actions cause attribution conflicts, and we pro- pose three metries to evaluate coalition faithful- ness. Experiments on synthetic data, NLP, image classification, and the game of Go validate our approach, demonstrating consistency with human intuition and practical applicability.
interaction
AND
AND
AND
X1
X2
X3
X4
((x.) 7 (65)) ((5)
7
(ks))
(6)) (0%) (0%)
(
(x)))))
(OS) (xx)++(5))
AND-OR 0R interactioss eacoded by
The term causes the conflict
that Chatretamm the
Figure f. (a)AND-OR interaction: Let the Al model encode three interactions S = f 22)) S2 = { 22, Iz, 25, ze and S. Ta respectively. In this way, the Shapley value of 21 can be decomposed as 6(x1) = 1/2 [(S; + 1/6 I(S2). (b) Conflict of attributions: Let us consider another example with three interactions, w.r.f, S₁ {z1, 22, I3, 24). ), S2 {21, x2). and S3 = {222, v3, 74). The attribution of coalition (x1, 22) is not equal to the sum of attributions of input variable 21 and 222 i... spS = {21, x2)) + <(x1) + 6(x2).
processing. In other words, evaluating whether grouped variables in partition can form faithful basic unit or coalition, remains challenge.
1. Introduction
Estimating the attributoo/immprtaneesslleee of input vari- ables (Selvaraju et al., 2017; Sundararajan et al., 2017; Lund- berg & Lee, 2017) for an Al model represents one of the most typical direction in explainable AI. In particular, the Shapley value (Weher, 1988) is widely considered as a stan- dard attribution method, because it is the unique attribution metric that satisfies the axioms of anonymity, symmetry, dummyy, additivity, and efficiency.
Essentially, this problem of the partition of input variables is rooted in the conflict of attributions computed under dif- ferent partitions of input variables. Consider the full set of input variables N = {I1, (21, 23, x4), as Figure 1(b) shows, we can directly compute the attribution of each i-th input variable, denoted by s(i), under the partition { (<a)), ) {x2), ) {23), {xa)]. Alternatively, we also apply new partition {1 { { by grouping set of input variables (x1, and we consider the entire set (01, as a singleton variable, S, called a coalition of input variables. In this way, the attribution method may estimate the attribution of the coalition S, ss(). Thus, the conflict of attributions means that the attribution of the coalition S is not necessarily equal to the sum of attribu- tions of the input variables in S, ie., (o)) + Eies o(i).
However, many studies (Ren et al., 2023a; Li & Zhang, 2023) have pointed out that one major challenge in this area is how to define the partition of input variables. For example, there is no theory to determine whether to take pixels or local regions as input variables for image classification and take words tokens as input variables for natural language
'Shanghai Jiao Tong University. Correspondence to: Quanshi Zhang Ezgs10226 jtt.eesuu.uu...........
Therefore, the core task of this research is to derive the fundamental mechanism for such a conflict and to provide clearer guidance on whether variables grouped together can form faithful basic unit or coalition.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Towards Attributions of Input Variables in Coalition
First, we discover the breakthrough point for proving the conflict is to disentangle all numerical effects in comput- ing attributions. We prove that the Shapley and Banzhaf values can be computed by reallocating the numerical ef- fects of AND-OR interactions in the Al model to different input variables. The AND-OR interaction (Li & Zhang, 2023) measures the non-linear relationship between input variables, as shown in the toy example in Figure I(a).
aries (Ribeiro et al., 2016; Plumb et al., 2019), while others integrated gradients w.r.t. inputs (Sundararajan al., 2017) or used gradient strength for feature attribution (Selvaraju et al., 2019). MUSE (Lakkaraju et al., 2019) analyzed de- cisions in lower-dimensional subspaces, and LRP (Bach et al., 2015) propagated model outputs to assign feature importance. DeepLIFT (Shrikumar et al., 2017) estimated imput impacts by propagating differences from baseline pre- dictions. Many works (Lundberg & Lee, 2017; Alshebli et al., 2019; Sundararajan & Najmi, 2020; Mitchell et al., 2022) used the Shapley value (Shapley et al., 1953), a stan- dard attribution metric satisfying key axioms. (Covert et al., 2020) modified it for global efficiency, and (Mitchell et al., 2022) introduced efficient sampling methods. (Lundstrom & Razaviyayn, 2023) also proposed unified framework for thme-theoretic attribution methods, including the Shapley value, based on the Möbius transform. However, the above attribution methods do not focus on explaining the partition of input variables but rather compute the attribution value given a predefined partition.
Second, considering the interaction explains the internal mechanisms for the Shapley value, we extend the defini- tion of the Shapley value and design new attribution metric (SS) for a coalition S of multiple variables. More importantly, we find that AND-OR interactions clarify the essential mechanism that causes the conffict between individual variables' attributions oit) and the coalition S's attribution (SS). Essentially, for each coalition S, the attribution of the coalition is computed using two types of interactions: (1) the interaction Ti containing all variables in S (i.e., Ti 2 S), and (2) the interaction T/2 containing partial variables in S (i.e., T. + 0 and nS + S). The interaction Ti is used to compute both Shapley values (ii), E S. and the coalition attribution c(S). Whereas, the interaction T2 is exclusively used compute the Shapley value (()). E S. Specifically, the interaction T3 is only used to compute the Shapley value o(i), i E S, but is not used to compute the attribution of the coalition (SS). Thus, the second type of interaction, i.e., T2 is the direct reason for the conflict of attributions.
Interaction. Unlike attribution methods estimating the im- portance of each input variable, the interaction usually pro- vides more fine-grained explanation, i.e., the importance of each specific collaboration between a set of input variables. Some studies (Tsang et al., 2017) measured feature inter- actions in neural networks by considering salient weights between features. (Singh et al., 2019) created hierarchical explanations in feed-forward networks, while (Cui et al., 2019; Janizek al., 2021) focused on pairwise interactions in Bayesian and second-order derivative neural networks. Inspired by the Shapley value, recent research measured fea- ture group interactions by calculating marginal importance (v(S) - =(0)). (Sundararajan et al., 2020) introduced the Shapley Taylor interaction index, while (Lundberg et al., 2020) applied the Shapley interaction index (Grabisch & Roubens, 1999) to tree-based models. Archipelago (Tsang et al., 2020) provided post-hoc explanation method, evalu- ating feature groups as a whole. (Tsai et al., 2023) proposed the Faithful Shapley Interaction index, extending the four standard Shapley axioms. (Harris et al., 2021) proposed the Joint Shapley value to assess feature sets' average con- tributions across different explanation orders. However, previous methods face the conflict between a coalition's attribution and the attributions of its individual variables (or sub-coalitions), in engineering manner, without offering theoretical explanation. Further explanation on coalitions and interactions can be found in Appendix A.
Third, we further propose three metrics evaluate the faithfulness of the coalition and construct experiments under different scenarios. Specifically, we evaluated our criteria on both synthetically generated function data and real-world tasks, including NI.P and image classification, demonstrating consistency with human intuition. Further- more, we applied our approach to the game of Go, where we found that it aligns with the understanding of Go players and can assist them in discovering new interpretations of standard opening patterns.
Contributions. (I) We clarify the internal mechanism for the common conflict between individual variables' attribu- tions and a coalition's 's attribution by using interactions to reformulate the attribution. (2) We propose a new coalition attribution metric with a clear explanation for such a conflict. (3) We further propose three metrics to assess coalition faith- fulness and conduct experiments across various scenarios.
2. Related works
3. Algorithm
Attribution methods. Estimating the attribution of input variables for inference is classic direction in the field of Explainable Al (Zhou et al., 2024; Ren et al., 2025). Some studies explained AI models using local decision bound-
3.1. Preliminaries: AND-OR interactions
Given Al model and input sample [x1, T2, .2, xn] with n input variables, N = (I,....7) represents the index
2

---

Towards Attributions of Input Variables in Coalition
set of all input variables and the model output on the input sample is represented v(x)) TR. There are various settings for v(z) when the model has multiple output dimen- sions. In multi-category classification tasks, v(z) is usually defined below, following (Deng et al., 2022).
of any word in S will disrupt the AND relationship and remove the effect (S)..
(S) represents the OR relationship among input vari- ables in S. The presence of any variable in S contributes an effect of Tor to the model's output. Given the sen- tence "This movie is boring and disappointing" for senti- ment classification, the OR interaction between variables in T {-] boring, 22 = disappointing) represents a negative sentiment with (T)) < O. If any words in T are present, then this pattern is activated and contributes Iar (T) to the model output v(N). Only masking all words in 'I can deactivate the interaction and remove the effect Tor (T).
p = y xz)
(x)) = log 1- p(y = y" x))
(1)
where yy denotes the ground-truth label of the input x.
Shapley value (Shapley et al., 1953) is a well-known game- theoretic metric to measure the attribution/imporaacce of each input variable to the output of the Al model. The Shapley value has been considered as the unique attribution method that satisfies the axioms of anonymity, symmerry, dummy, additivity, and efficiency. In this way, the Shapley value of the i-th variable is computed as follows:
Universal-matching property. The output of an Al model can always be explained as numerical effects of AND-OR in- teractions. In particular, the faithfulness of interaction-based explanation is ensured by the universal-matee
(61)= = Σ SENVE
[5
|S| 1)! [e(Su(()) (2)
property (Lii & Zhang, 2023). Given each randomly masked sample 2g (S C )), we can always use AND-OR interactions to mimic the network output uSS) on 2g. No matter how we randomly mask the input and obtain a masked sample &g s.f. S S N, the masking operation deactivates some AND-OR interactions, but it proven that the network output on each randomly masked sample v(5) can be always accurately estimated as the sum of numerical effects of the remaining AND-OR interactions. Please see Appendix B for details.
72
where | denotes the cardinality of the set. Here, we use vS)) to simplify the notation of v(2ss) and v(as)) denotes the model output on a masked sample øg. In the masked sample ø3, variables in S are present, and variables in N S are masked. In this way, e0) represents the model output when all input variables are masked, and v(N) denotes the model output on the original input sample x.
AND-OR interactions. Given an Al model v(.) and a set S C N (S + 0), the AND interaction effect (S)) and the OR interaction effect (S)) between input variables in can be computed, as follows.
3.2. Revisiting attributions from interactions
In this section, we will revisit the conflict problem in the attribution method and reformulate classical attribution met- rics from the perspective of interactions.
(Sn)(S) = Eiga(-1) 91-121 Vand (
(3)
[e(S)= = - (-11((1)) var(A (N Lt)
(4)
What is a coalition? Given an Al model v with n in- put variables in N, the estimation of the numerical attribu- tion of each i-th input variable o(i) depends on the parti- tion of input variables. For example, given an input sen- tence "raining cats and dogs", some people choose to take each token as an input variable and compute the attribu- tions of different tokens, N == =rain, [rain,,ing, cats, and, dogs), while other people use words as input variables, P = { (rain, -ing), cats, and, [ogg)..huss the combination of coalition, just like the coalition of S = (rain,- -ing) } in the second case. As Figure I shows, people may manually select set of input variables with actual semantics to construct a coalition.
where Vand (L)= 0.5v(L) and vor = (L) 7L
represent output components exclusively for AND interac- tions and OR interactions, respectively, subject to v(L)= = Vana( ( [)) + Une (T.). In this way, the extraction of all AND- OR interactions is determined by learning optimal param- eters }. (Li & Zhang, 2023) have proposed to learn parameters } via LASSO-like loss achieve sparsest interactions, Le.. EsgN ITama (S)) + (S).
input variables can be considered
How to understand AND-OR interactions. (S) mea- sures the non-linear relationship (AND relationship) be- tween input variables in 5 C N. The presence of all vari- ables in contributes an effect (S) to the model's out- put. For example, we consider the slang term S {a1 = raining, x22 = cats, = and, 244 = dogs} in the input sen- tence "It was raining cats and dogs outside." An Al model may encode the AND relationship between the variables in S as an inference pattern of "heavy rain." If all four words exist in the input sentence, the DNN will detect this infer- ence pattern and make a numerical effect (S)())) to push the output towards the meaning of "heavy rain." The masking
Compared to estimating a scalar attribution of a coalition S, the interaction usually represents more disentangled effects. For example, for a coalition S = fa, b, c). different inter- action effects T({a)), I((b)), I((c)), T(fa, b)), I(fa, c)), I({b, ()) b, b, may affect the attribution of the coali- tion S. Please see Appendix A for a detailed comparison between coalition attribution and interaction effeett.
Conflict of attributions. Definition 3.1 introduces the con-
3

---

Towards Attributions of Input Variables in Coalition
flict of attributions between coalition and variables.
value of the i-th variable, the effects of the interactions (S) and (S) subject to i S are allocated to B()) with a constant weight 2|--T.-
Definition 3.1. Given two partitions of input variables N 21.2..... ....,, n and P- (Si, S2..., S,.,,,...,,,,, subject to N = , S, Vi * j. n S] = 0. the conflict of attributions means that there exists a coalition Sy such that the attribution of the coalition Sk is not equal to the sum of attributions of its compositional variables, i.e. (S.) # Exes, ox (i).
3.3. Attribution value for coalition
The Shapley value is widely recognized standard attri- bution method with a relatively solid theoretical foundation, and Section 3.2 has explained the internal mechanism for the Shapley value from the perspective of AND-OR interac- tions. Based on this, in this subsection, we further extend the Shapley value of each individual input variable to define the attribution of a coalition.
The above conflict is common in practical applications. In particular, there does not exist a universally accepted par- tition of input variables. To this end, neither the Shapley value nor the Banzhaf value can eliminate the conflict of the attributions calculated under different partitions of variables.
As mentioned in Definition 3.1, the core problem is that different partitions of input variables may lead to conflicts of attributions. To this end, previous studies usually apply an additional loss to force the method to extract attributions without suffering much from the conflict. For example, the Shath (Tsai et al., 2023) used the minimum squared loss to push attribution of coalition S towards the sum of attribution of individual variables in S, i.e., pushing (S)) towards > ies (i). Please see Table I for detailed com- parison of previous methods.
Reformulating attributions. As the theoretical foundation to explain the conflict of attributions, let us first revisit classical game-theoretic attributions, such as the Shapley value (Shapley et al., 1953) and the Banzhaf value (Lehrer, 1988). We find that both two attribution metrics can be explained as an allocation of AND-OR interaction effects.
Theorem 3.2. (Reformulation of the Shapley value, proved in Appendix C) The Shapley value <01) of each input variable F; can be explained as Φ(1)
EscrieS [S] [and + (S)].
As the same shown in Section 2, methods in Table are designed to solve the conffict an engineering manner. In comparison, we focus on the mathematical factor that causes the conflict of attributions. To this end, we are inspired by Theorem 3.2, which explains the Shapley value uniform re-allocation of each interaction effect (S) or (S) to each input variable i in S. Just like that, we can similarly define the attribution of a coalition S, (SS), as the re-allocation of AND-OR interactions, as follows:
Theorem 3.2 explains the internal mechanism of the Shapley value, ie., the Shapley value is computed by evenly allocat- ing each interaction effect to all its compositional input vari- ables. For example, in the sentence "It was raining cats and dogs outside.", the DNN may encode the AND interaction S1 = {x1 raining. 22 = cats, F3 = and, = dogs} to represent a heavy rain. Because these four variables T1, 22, T3, 24 play the same role in the interaction S1, it is supposed to allocate the numerical effect (S)) uniformly to each variable, i.e., allocating (S) to the variable u2 cats. Besides, the variable 22 cats may also be involved in other interactions, such as (S2 = x2)) and (Sg = {xn, I3, I.)). Then the Shapley value of u2 = cats can be computed as the accumulation of all allo- cated effect ((x1) = } Lnna(S (S:) + } (Sa)) - (.ss).
|S| T
AS C N, ((S) = Σ
[T (T) (T)) (6)
For example, in an input sentence "It was raining cats and dogs outside.", we may annotate coalition S = (2) rain, = -ing]- Let us suppose that the model has en- coded an AND interaction T = (21 = rain, 22 = ing I3 cats, xy = and, mı dogs). The numerical effect (T) de- pends on all the five variables. Thus, 3 and is supposed to be assigned with the coalition S containing two input variables and be added to ((S). In this way, the attribution of the coalition (S))(S). can be explained an allocation of all interactions Jana(T) and T (T)) that cover all variables in S, i.e., T 2 S.
The Banzhaf value (Penrose, 1946) is another classical attribution metric, and we find that the mechanism of the Banzhaf value can also be explained as specific allocation of interaction effects. Specifically, the Banzhaf value of i-th variable is formulated as follows.
B(i) = ESS [c(SU us)) (5)
3.4. Explaining the conflict of attributions
Theorem 3.3. (Reformulation of the Banzhaf value, proved in Appendix D) The Banzhaf value B(i) of
Instead of forcibly eliminating the conflict in an engineer- ing manner (Tsai et al., 2023), we find that the conflict (P(ss) # *iEs, (i) in Definition 3.1 naturally exists in different Al models. Thus, we need to face and accept such conflict, instead of forcibly eliminating such an ob-
each input variable I; can be reformulated as B()=
EsCNiES य [S) + Lor(
Theorem 3.3 shows that when we compute the Banzhaf
4

---

Towards Attributions of Input Variables in Coalition
Table 1. Comparison between the solutions of the conflict of attributions in different attribution methods
Attribution methods
Solutions for the conflict of attributions
Shapley value (Shapley et al., 1953)
Efficiency axiom e(N) Eie @(1). but cannol ensure efficiency property, w.k. any arbitrary set S C N. Le.. ((S) & Eies 0(1)
Banzhaf value (Penrose, 1946)
2 2-efficiency axiom: B(i) + B )- - B(fi,))
but do not satisfy B(5)
ii. B(i)
Joint Shapley value (Harris et al., 2021)
Joint linearity, dummy, efficiency, anonymity, symmetry axioms, but estimating the attribution of of features/interactions, like (Sundararajan al., 2020)
Faith-Shap (Tsai et al., 2023)
Using loss [|e(() Eies (())]l to alleviate the conflict
Our method
Proving the conflict is naturally unavoidable. and quantifying the essential cause for the conffict
jective existence. The theoretical explanation and clear disentanglement of effects responsible for the conflict is usually considered as a more faithful solution to the coalition's 's attribution. To this end, Theorem 3.4 disen- tangles Shapley values of all input variables in S into two components, i.e., (I) the attribution component Ostared (S) shared by both the coalition and the individual variables, and (2) the conflicting attribution component (ccomtica)
location of (PS) to its constituent input variables, [ST (SS), as the attribution of the i-th variable. Theorem 3.6 explains the difference between ((i) and उ (SS). It shows that the Shapley value (bi) can be decomposed into two parts. (1) The first part U1. is component of coalition attribution TST i.e., the uniform allocation of (sS) to its con- stituent input variables. (2) The second part U2,5 comes from all interactions {T') which cover just partial but not all variables in S, (T I S N Tii,ETSSTTr & S).
Theorem 3.4. (proved in Appendix E) For any coalition S SEN, we have Exes p(i) = @shared(S) (S) + &comtica (S). @shama(S) def
Theorem 3.6. (proved in Appendix F) ViE 6 Ergrrrs [T [T) + lor(
(pS) is the attribution component exist- ing in both the coalition's attribution sp(S and indi- vidual inpur variable's 's attribution ((i). thereby being termed the shared attribution component. (So [TnS]
EICNTZSTT Im] [nnd (T) [T)]
1
p())+
(maa(T) + [T)(
T
TENT28TT
(T) + [T)( represents the conflict (or difference) between the coalition attribution and the individual variables' attribution.
ETEN.TnSyO.TnS
TI
U
U.S
Corollary 3.7 further shows that if = {i) only contains a single variable Iú, then the attribution of the coalition S is equal to the Shapley value o(i).
Theorem 3.4 shows that the conflict between individual variables' attributions and the attribution of the coali- tion S comes from numerical effects of all interactions T that contain just partial but not all variables in S, subject to 6 * T n S # S. This well fits the human un- derstanding of the conflict, i.e., not all interactions take S as singleton coalition. In particular, Corollary 3.5 shows that if the DNN always considers all variables in S as a coalition without encoding interactions covering partial but not all variables in S, iee. VT E (T: : S Z T, T S. N, E $}, (T)) = (T)) = O, then there will be no conflict of attributions, W.E.t. the coalition S.
Corollary 3.7. s05 {t}) 6(i)
Verifying whether we can use coalition attributions to compute the Shapley value. We conducted experiments to examine Theorem 3.6, L.e., whether we could use the coali- tion S's attribution to calculate the Shapley value of the i-th input variable, E S. We used Aø(i)s <(i) @(i) to measure the approximation error between the true Shapley value computed based on Equation (2), @(i), and the Shap- ley value estimated by Theorem 3.6, d(i). We conducted experiments the DNNs introduced in Section 4.1. Table 2 reports the average estimation error E, ==,15|=m [F] (())s) over all samples through all potential combinations of (i, S) s.l., i E S of a specific order |.|] = m.. The small errors proved the correctness of our theory.
Corollary 3.5. If a set of imput variables in S are always encoded by the DNN as coalition without any interactions containing partial variables in S, i.e., VT E (T S g T, T.T&S C N,i E S}, (T) = (T) = O, then the attribu- tion of the coalition S can fully determine the Shapley value ((1). i... (ii = (SS) and ((S)) = Eies (i)).
3.5. Properties/axioms for the attribution of a coalition
Explaining Shapley values. Let us use the coalition attri- bution (S)) to explain the Shapley value of each variable in S. (1).. Specifically,, we can simply take the uniform al-
Just like in the Shapley value, the following five axioms have been widely considered as standard requirements for reliable attributions (Lundberg & Lee, 2017). Although
5

---

Towards Attributions of Input Variables in Coalition
there are slight differences in axioms for the Shapley value, the coalition attribution also satisfies these axioms, which are proven in Appendix G. Appendix H introduces a more detailed understanding of these axioms.
Table 2. Approximate error Fa.1s]=m [E] (1)ss) of using coali- tion attribution to mimic the Shapley value ((1)
m
m
2
m 3
m
m =
3.6 10
1111 10
222x 10 1.22 x 10 20.677766 10-7
1. Anonymity axiom:
Let us consider a permutation operation a on all input varaibles in N. av denotes the permutated function subject to (S)) = v(S), for all 5 C N and (S) = (i( : S}. Then, it has (S) (S)).
m=
==
m
m
m 10
9.1 x 10 7/14 10 6.3
10 8.8 10 22.88 x 10-7
Table 3. Approximate error Er, -5 [ Aes || of using coalition attribution mimic the model output N(N)
2. Symmetry axiom-a: If two input variables i and j have the same effect, i.e. AS S N (t,5), ((SU(i)) v(S U (i)), then VS S N ((,)) (i)) ( 1 (i}).
m =
m =
2
m = 3
m =
m =
2.3 x 10 7 10 9.1 x 10 11..8 x 10 76.3 10
m
m
m
m
m = 10
2.1 x 10-075.11111 10 3.6 x 10 7
3.1 x 10 4.7 x 10-7
3. Symmetry axiom-3: If two coalitions S and T [(|)-
(D have the same effect, i.e. VT C T,YS' _ S.
attribution. We computed Aus = ((N) ((VS)) mea- sure the approximation error. Table 3 reports the average estimation error =m [ over all samples. The settings of neural networks and datasets was introduced in Section 4.1. We found that no matter how the coalition S was selected, the model output v(N) could be well mim- icked by the coalition attribution ((S) and the effect of interactions T covering partial but not all variables in S.
| = VL S (S" (LLS') = ( = v(LUT). then it has 7L S (SUTT)
(LUU))
4. Additivity axiom: If the output of DNN can be divided into two independent parts, i.e. AS C N, v(S) vi (S) + 02 (S), then the attribution of any coalition S can also be decomposed to two parts, i.e. AS C
N, (S)) sr, (5) - PPng (S).
4. Experiment
5. Dummy axiom: If a coalition S is a dummy coalition, L.e. 3i E S. C N \ {i), U(TUUU {i))= = v(T), then it has no attribution to the DNN output, iee. (sS)= = O.
4.1. Evaluating faithfulness of a coalition
In this study, we prove the essential mechanism behind the conflicts of attributions computed on different partitions of input variables (see Theorem 3.6). The decomposition of the Shapley value into two terms U,, and Ug. in Theorem 3.6 also enables to evaluate the faithfulness of the coalition. Specifically, (1) the U,, term reflects the confidence of the coalition, because Urs measures effects of all interactions T (T 2 S) that take S as a singleton variable; (2) In comparison, U.S reflects the significance of variables in S that do not act as a singleton variable, because UgS measures the effect of interactions T that cover just partial but not all variables in S. In this way, we propose three metrics to evaluate the faithfulness of the coalition.
Efficiency axiom. The overall model output can be de- composed into attributions of coalitions and attributions of individual variables. Theorem 3.6 can directly derive the following corollary.
Corollary 3.8. (Efficiency) For any coalition S S. N, the output score of a model can be decomposed into the attibution of the coalition S and the atrriutiio of each input variable in N \ S and the utilities of the interactions covering partial variables in S. i.c.,
VS I (N) v(0) ((S) EiENYs $(1) ITnSl [T" + (T))
ETENITSHOIISSS ITI
The first metric R(i) is designed to evaluate for each specific coalition S C N. whether the U.S term dominates the major effect of @(i). If so, we consider the set of variables in S faithful coalition.
Corollary 3.8 shows another type of efficiency property. Le.., an Al model's output on the input x can be accurately mimicked by the sum of the coalition S's attribution, the Shapley value of each variable N \ S, and the numerical effects of the interaction covering partial variables in S.
U
R(i) |Us + U.sl!'
i S
(7)
Verifying whether we can coalition attributions to ex- plain the network output. According to Corollary 3.8, we can use the coalition attribution to mimic the output v(N) of neural networks on any arbitrary sample. Therefore, given a coalition S, we followed Corollary 3.8 to compute ((V) (S) to represent the model output mimicked by the coalition
The second metric R' E [0. 1] defined to measure the significance of the variable participating in the coalition S, in a more fine-grained manner, as follows.
Eros (T) H (m)) (T))
R'(1) = Er'Ss 174 (Iann) + (1r()))
iES S
(8)
6

---

Towards Attributions of Input Variables in Coalition
fit the target function (xx), then our metries were supposed to identify these purely faithful/purely unfaithfullppatially faithful coalitions.
Table 4. Coalition faithfulness metries on toy functions
[[() E (i) [
purely faithful coalitions
0.944
0.936
0.948
In practice, we trained the MLP (Ren et al., 2023b) to regress the functions. Table showed that the regression of a purely faithful coalition S had Q(S), (i), R(ii) close to 1, and the regression of purely unfaithful coalition S always had Q(S), (i), R(i) close to 0. A partially faithful coalition S always had 0 (SS), (1), R(i) < 1 which means that variable in S existed in the true interactions containing the whole coalition S, and also existed in other interactions.
partially faithful coalitions
0.471
0.608
0.590
purely unfaithful coalitions
0.031
0.016
0.013
denotes the strength of interaction effects that are allocated from the coalition S to the variable i, E S. Er 17 (T") + [Trr(T")) ) denotes the strength of interaction effects allocated to the variable i, no matter whether or not the variable collabo-
where Erss + (T))+ (4)) (I'))
Experiments on DNNs trained for NLP tasks. We con- ducted experiments to evaluate whether the Al model faith- fully encoded such natural coalitions in human cognition. We finetuned the pre-trained BERT-large (Devlin et al., 2018) and LLaMA (Touvron et al., 2023) model on SST-2 dataset (Socher et al., 2013) for sentiment classification. We divided the input sentence into words and manually selected 10 words as input variables. Given an input sentence x, we annotated some natural coalitions according to human cognition. For example, in the sentence "It was raining cats and dogs outside," the phrase "raining cats and dogs" was annotated as a natural coalition. In comparison, we randomly selected coalitions as false coalitions.
rates with other variables in S \ {i} as coalition.
Unlike the first two metrics focusing on the effect of single variable i, the third metric Q(S) E [0. 1] is defined to measure the significance of the entire coalition S.
1S1 Q(S)- Erys
T (Tama (T) + (T))
IT'88 TTSSO [T ((Lnna(T)) (T"))
where the numerator measures the overall strength of effects allocated to the coalition S, and the denominator denotes the overall strength of effects of all variables in S, no matter whether these variables construct the entire coalition.
Experiments on toy functions. We conducted two experi- ments to use three metries in Equations (7)-(9) to evaluate the faithfulness of different coalitions encoded by a DNN. However, the core problem was that it was difficult to ob- tain ground-truth interactions encoded by a DNN because true/ideal interactions that were supposed to be learned for a task were not necessarily equivalent to the real interactions that a DNN had learned. Thus, we trained DNNs to regress
Table 5 shows that in the sentence (a), the coalition "mesmerizing performances" represented the positive emo- tions with high Q(S). R(i), R' R'ii values Bert-large and I. LLMM models, thereby being considered as faithful coali- tion. In comparison, in the sentence (b), the selected coali- tion S "rivaling blair" separated the phrase "blair witch," so S was considered as an unfaithful coalition, which was also reflected by the low Q(S), R(i), R'(i) values. It provides new insights that if a coalition contains both tokens related to the generated language and irrelevant tokens, then this coalition usually represents representation flaw.
the following toy function (ax = Ei= W; II Iser; Ty with clear interactions to determine ground-trui truth interactions, where x = 12. ...., =n]] E {0, 1)", Vi + j. T; # TT. The function fx) was determined by m different true interac- tions [T. i = 1, 1,2,...,m7. m). We designed a set of 20 target functions f (x) for testing by applying different sets of {Ti).
Experiments on DNNs trained for image classification. We conducted experiments on VGG-11 (Simonyan & 7is- serman, 2014) and ResNet-20 (He et al., 2016) on the MNIST (LeCun et al., 1998) and CIFAR-10 (Krizhevsky, 2012) datasets and verified that these DNNs represented natural coalitions that fit human cognition. Please see Ap- pendix I for experimental settings and results.
Specifically, we evaluated the faithfulness of the following three types of coalitions.
(1) Given the target function (ar)
w.r.f. m true interactions {Ti] i = 1,... m). each of the first type of coalitions, S, was fully contained by some true interactions T; 2 S. without being partially covered by any interactions T; (T; n S # 0, TV n S + 5). Thus, the first type of coalition was supposed to be the most purely faith- ful coalitions. (2) In contrast, each of the second type of coalition, S. was partially covered by some true interactions T, (T₃ n5 + 0, T2 S + S) without being fully contained by any interactions T; These coalitions were supposed to be purely unfaithful coalitions. (3) The third type of coali- tions were termed partially faithful coalitions, i.e., being contained by some interactions T, 2 S and partially cov- ered by other interactions T,. If the DNN was well trained to
4.2. Application: explaining the Go game
Computing the attribution value of coalition is of signifi- cant value in practice, and our method can be widely used. A typical application is to explain shape patterns memorized by a DNN to play the game of Go, which is inspired by the previous work (Zhou et al., 2023b). The shape patterns correspond to coalitions between input stones. Specifically, people usually use a value network to estimate the advantage
7

---

Towards Attributions of Input Variables in Coalition
Table 5. Coalition attrihution metrics SST-2 dataset
Sentences
Bert-large
Q [m performances)) = 0.743
(a) the mesmerizing performances the leads keep the film grounded and keep the audience riveted.
R {mesmerizingg) = 0.690, R ((msmmerriziig) 0.682
Ri (performances) 0.677, R ((performmance)) 0.685
(rvivaling blair)) = 0.425
(b) one of creepiest, scariest movies come along in long.
R( [((rivaling) ) 0.145, R (rivaling]] - 0.391
long time, easily rivaling blair witch or the others
R (((baiir)) 0.250, ('(bl,ir ((blair)) 0.466
Sentences
I.L.MA
(mmemmeriiingg performances)) = 0.746
(a) the mesmerizing performances the leads keep the film grounded and keep the audience riveted.
R( (memmeriiii))) 0.611, R²' (((mmmmeeriizing)) 0.652
R (ppefforrances) 0.726, R' ((performanccs)) 0.739
Q (frivaalnng blair)) = 0.312
(b) one of creepiest, scariest movies come along in long. long time, easily rivaling blair witch or the others
R((rivaling)) 0.238, R ((((vaaalnn))) = 0..49
R( 0.277, R² ((blair)) 0.286
Input Go Games from KataGo
Top-ranked coalitions selected by professional Go players
Top-ranked coalitions selected by the interaction strength
666. 8.8. 10)1
-0.93
c< =1.00
33 m -0.04
MEC 7,8.77.83 3:41
vL(2.4 1.335
-
ct -15)
etcs. 9,100 -1.6
(2)
18
Figure 2. Visualization of two approaches for the selection of coalitions in KataGo. For coalition S, (p(S) > 0 means the coalition S of stones makes a positive numerical effect for the white, while it makes negative effect when (sS) <
score of white stone in Go. The advantage score depends on complex coalitions (shape patterns) between white stones and black stones. However, there are no metrics evaluate the true attribution of each shape pattern.
2023a) to set v(S) = log( (atue((x)) + ags S.f. aj = --Panne
E,,BrgN:e==aa((T))- -ma)a (T) coyl Petur((27) ( measures the advantage score of white stones, where Tewhie is the number of white stones in T. Pwhite (#)) represents the score of white stones on input æs, where stones in N \ S n-2 were removed from the board. ag, k = 2 2 .....
Therefore, we conducted experiments to quantify the at- tribution of each shape pattern encoded by the KataGo model (Wu, 2020), which was an open-source Go engine, and was known for its strong performance in playing the game of Go. The KataGo incorporated the Monte Carlo Tree Search and a value network to play the game, and we evaluated shape patterns encoded by the value network.
represents a bias of the network output on a certain input.
Notably, although KataGo's capabilities surpassed those of human players, was not necessary for the coalition//nterac- tions modeled by KataGo to reflect human cognition of the Go game. Therefore, used two strategies select coali- tion candidates. The first strategy was to let professional human players annotate classical shape patterns, accord- ing to human understanding of the Go game. The second strategy was to select top-k interactions selected by the inter- action strength (IT(T) as coalition candidates suggested by the DNN. Then, given each coalition candidate, we cal- culated the attribution (eS)) of selected coalitions. Figure 2 shows that coalitions that boosted the advantage score
We had KataGo execute 40 moves against each other. Due to the significantly high computational cost of interactions, we only explained a local board state consisting of n = 10 stones (i.e.. 5 white stones and 5 black stones). These 10 stones were selected by professional Go players as in- put variables N, between which interactions were com- puted. The remaining stones the board were treated constant background. Then, we followed (Zhou et al.,
8

---

Towards Attributions of Input Variables in Coalition
of white stones s.t. (SS) O and coalitions that reduced the advantage score of white stones s.I. sp() 0. These results help expert Go players learn shape patterns to play the Go game. Furthermore, we analyze the fitness between the extracted coalitions and human intuition on many more game boards. Please refer to Appendix J for details.
Cui, T., Marttinen, P., and Kaski, S. Learning global pair- wise interactions with bayesian neural networks. arXiv preprint 1rXiv:190..08320 2019.
Deng, H., Ren, Q.. Zhang, H., and Zhang, Q. Discovering and explaining the representation bottleeck of DNNS. In The Tenth International Conference on Learning Repre- sentations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
5. Conclusion
In this paper, we find and formulate the conflict between individual variables' attributions and the attribution of the coalition S. In order to explain the internal mechanism for such a conflict, we discover that both the Banzhaf value and the Shapley value can be formulated as a specific allocation of AND-OR interactions. Inspired by that, we extend AND- OR interactions define the coalition attribution, and we prove that the conflict of attributions comes from numerical effects of all interactions T that contain just partial but not all variables in S. Furthermore, the new coalition attribution enables us to evaluate the faithfulness of a coalition.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding, CoRR, aww//a//..//////a 180004800 2018. URL http://arxivv org/ abs 1 810. 04805.
Grabisch, M. and Roubens, M. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of game theory, 28:547- 565, 1999.
Harris, C., Pymar, R., and Rowat, C. Joint shapley values: a measure of joint feature importance. arXiv preprint arXiv:2107. 11357, 2021.
Impact Statement
Harsanyi, J. C. 17. A Bargaining Model for the Cooperative n-Person Game, pp. 325-356. Princeton University Press, Princeton, 1959. ISBN 978 9781400882168.
This paper aims explain the internal mechanism for the conflict between individual variables' attributions and the attribution of the coalition S. We extend AND-OR interac- tions to define the coalition attribution, and we prove that the conflict of attributions comes from numerical effects of all interactions that contain just partial but not all variables in S. Furthermore, the new coalition attribution could help researchers evaluate the faithfulness of coalition.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. doi: 10. 10.1109/CVR.22066..
Janizek, J. D., Sturmfels, P., and Lee, S. Explaining explana- tions: Axiomatic feature interactions for deep networks.
Acknowledgements
J. Mach. Learn. Res., 22:104: 2021.
This work is partially supported by the National Science and Technology Major Project 10212201116022 the National Nature Science Foundation of China (92370115, 15, 62276165), and Shanghai Natural Science Foundation (242R1491700).
Krizhevsky, A. Learning multiple layers of features from tiny images. University of Toronto, 05 2012.
Lakkaraju, H., Kamar, E., Caruana, R., and Leskovee, J. Faithful and customizable explanations of black box mod- els. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 131-138. 2019.
References
Alshebli, B. K., Michalak, T. P... Skibski, O., Wooldridge, M., and Rahwan, T. A measure of added value in groups
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, Gradient- based learning applied to document recognition. Proc. IEEE, 86(11):2278-233) 1998. doi: 10.1109/5.726791.
ACM Transactions Autonomous and Adaptive Systems (TAAS), 13(4):1-46, 2019.
Lehrer, E. An axiomatization of the banzhaf value. Interna- tional Journal of Game Theory, 17:89-99, 1988.
Bach, S., Binder, A., Montavon, G., Klauschen, F., Müller, K.-R., and Samek, W. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e0130140, 2015.
Li, M. and Zhang, Q. Technical note: Defining and quanti- fying and-or interactions for faithful and concise explana- tion of dnns. arXiv preprint arXiv:2304.13312. 2023.
Covert, I., Lundberg, S. M., and Lee, S.-I. Understand- ing global feature contributions with additive importance measures. Advances in Neural Information Processing Systems, 13:17212-11223, 2020.
Lundberg, S. M. and Lee, S. A unified approach to inter- preting model predictions. In Guyon, L. von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan,

---

Towards Attributions of Input Variables in Coalition
S. V. N., and Garnett, R. (eds.), Advances in Neural In- formation Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 17764477,, 2017.
Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra, D. Grad-cam: Visual explana- tions from deep networks via gradient-based localization. In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pp. 618- 626. IEEE Computer Society, 2017.
Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., and Lee. S.-I. From local explanations to global under- standing with explainable ai for trees. Nature machine intelligence, 2(1):56-67, 2020.
Selvaraju, R. R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., and Batra, D. Grad-cam: Visual explana- tions from deep networks via gradient-based localiza- tion. International Journal of Computer Vision, 128 33:336-359, October 2019. ISSN 1573-1405. doi: 10. 10.10077/111263--01-0002223 7. URL http: / /ddiioii. ozg/10.1007/s111
Lundstrom, D. and Razaviyayn, M. A unifying frame- work to the analysis of interaction methods using syn- ergy functions. In Krause, A.. Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Pro- ceedings of the 40th International Conference Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 23005-23032. PMLR, 23-29 Jul 2023. URL pttettpss//proceeddeee egg.oeeeddngg...o.. wwr...r... press// v202 htt///unndttomm3aaa html.
019 01228-7.
Shapley, L. S. et al. A value for n-person games. 1953.
Shrikumar, A., Greenside, P., and Kundaje, A. Learning important features through propagating activation differ- ences. In International conference on machine learning, pp. 3145-3153, PMLR, 2017.
Mitchell, R., Cooper, J., Frank, E., and Holmes, G. Sam- pling permutations for shapley value estimation. The Journal of Machine Learning Research, 23(1):2882-212) 2022.
Simonyan, K. and Zisserman, A. Very Deep Convolutional Networks for Large-Scale Scale Image Recognition. arXiv e- prints, art. 1cXIv:1149.1155 2014.
Penrose, L. S. The elementary statistics of majority voting. Journal of the Royal Statistical Society, 109(1):53-51) 1946.
Singh, C., Murdoch, W. J., and Yu, B. Hierarchical inter- pretations for neural network predictions. In 7th Inter- national Conference on Learning Representations, ICLR, 2019.
Plumb, G., Molitor, D., and Talwalkar, A. Model agnostic supervised local explanations, 2019.
Socher, R.. Perelygin, A., Wu, J., Chuang. J., Manning, C. D., Ng. A., and Potts, C. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Meth- ods in Natural Language Processing, pp. 1631-1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics.
Ren, J., Zhou, Z., Chen, Q., and Zhang, Q. Can we faithfully represent masked states compute shapley values on dnn? 2023a.
Ren, J., Zheng, X., Liu, J., Lizarraga, A., Wu, Y. N., Lin, L., and Zhang, Q. Monitoring primitive interactions during the training of dnns. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 39, pp. 20183- 20191, 2025.
Sundararajan, M. and Najmi, A. The many shapley values for model explanation. In International conference on machine learning, pp. 9269-9278. PMLR, 2020.
Ren, Q. Deng, H., Chen, Y., Lou, S., and Zhang, Q. Bayesian neural networks tend to ignore complex and sen- sitive concepts. In Proceedings of the 36th International Conference on Machine Leurning, ICML 2023, 23-29 July 2023.. Proceedings of Machine Learning Research. PMLR, 2023b.
Sundararajan, M., Taly, A., and Yan, Q. Axiomatic at- tribution for deep networks. In Precup, D. and Teh, Y. W. ), Proceedings of the 34th International Con- ference on Machine Learning. ICML 2017, Sydney, NSW Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 3319-3328. PMLR, 2017. Sundararajan, M., Dhamdhere, K., and Agarwal, A. The shapley taylor interaction index. In Proceedings of the 37th International Conference on Machine Learning. ICML, volume 119 of Proceedings of Machine Learn- ing Research, pp.
Ribeiro, M. T., Singh. S., and Guestrin, C. "wwy should trust you?": Explaining the predictions of any classifier. In Krishnapuram, B., Shah, M., Smola, A. J., Aggarwal, C. C., Shen, D., and Rastogi, R. (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA. USA, August 13-17, 2016, pp. 1135 144. ACM, 2016.
PML.R, 2020.
10

---

Towards Attributions of Input Variables in Coalition
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lam-
ple, G. Llama: Open and efficient foundation language models, 2023.
Tsai, C.-P, Yeh, C.-K., and Ravikumar, P. Faith-shap: The faithful shapley interaction index, 2023.
Tsang, M., Cheng, D., and Liu, Y. Detecting statistical interactions from neural network weights. arXiv preprint arXiv: 70770050097777 2017.
Tsang. M., Rambhatla, S., and Liu, Y. How does this in- teraction affect me? interpretable attribution for feature interactions. Advances in neural information processing systems, 33:6147-6159, 2020.
Weber, R. J. Probabilistic values for games, pp. 101-120. Cambridge University Press, 1988.
Wu, J. Accelerating self- elay learning in go, 2020.
Zheng, X., Li, Y., Fan, C., Wu, H., Song, X., and Yan, Learning plaintext-cippertexx cryptographic problems via unf-based sat instance representation. Advances in Neural Information Processing Systems, 37:41649 41669, 2024.
Zhou, H., Tang, H., Li, M., Zhang, H., Liu, Z.., and Zhang, Q. Explaining how a neural network play the go game and let people learn, 2023a.
Zhou, H., Tang, H., Li, M., Zhang, H., Liu, Z., and Zhang, Q. Explaining how a neural network play the go game and let people learn, 2023b. URL https: //arxiv. org/ abs/ 2310.000200 09838.
Zhou, Z., Shen, W., Chen, H., Tang, L., Chen, Y., and Zhang, Q. Batch normalization is blind to first and second derivatives of the loss. Proceedings of the AAAI Conference Artificial Intelligence, 38(18): 20010-20018, Mar. 2024. doi: 10. 11.60//aa..v8ii.. 29978. URL /tttps://ojs.ast org/ index. Dtt//AAt/arriclle//ie/////9

---

Towards Attributions of Input Variables in Coalition
A. Coalition attribution vs interaction effect
Unlike the coalition attribution, interaction metrics (Harsanyi, 1959; Grabisch & Roubens, 1999; Sundararajan et al., 2020; Tsai et al., 2023) usually disentangle explicit effect I(S) of each specific subset S Ç N away from the effect [(S") of its overlapping neighbor subset S", instead of considering how merge effects of overlapping subsets into the attribution of coalition T S S,S'. For example, the Harsanyi interaction (Harsanyi, 1959) separately calculates the interaction effects [(S) = (-1, H, T(22 (I1, 22, F3 }), and (S33 = (æ1, ; 22, 43, x44) }). There are direct connections between these interaction effects. In contrast, the coalition attribution focuses on how to reasonably summarize these interaction effects into a single scalar importance score (Si) of the coalition S₁. In practice, both approaches can be applied to various types of applications, the analysis of byte blocks in cryptographic round functions (Zheng et al., 2024).
B. Universal-matching property of AND-OR interactions
(Li & Zhang, 2023) have proven that the output of an Al model can always be explained by AND-OR interactions. For each input sample æ, we can randomly mask and generate 2" different masked samples (æs), w.r.f. $ S N. Given each randomly masked sample ss, we can always use AND-OR interactions to mimic the network output v(S) on ds. as follows.
u(5) = v(0) + E EE (L) + E L (L)(L)
(10)
Furthermore, (Ren et al., 2023a) have shown that the effects of interactions in most DNNs are usually very sparse. The majority of interaction effects are nearly zero, and only few of the most salient interaction effects are sufficient to approximate the network's 's output u (NN).
C. Proof of Theorem 2
Proof. According to the definition of Shapley values, have: s(1) EscNyB [S|(n=(11-11 [u(SU(t)) v(S)]
Esçry0 [u(S U (i}) - r((5)]-
Then, according to Equation (10) in the paper, we have: VS C es)(S) = v(0) Eiss,no (Lna(L) Einsyo Lor(L). Thus, we have:
USU (i)) vSS)
v00) +
Σ
lana(L) +
Σ
Lor(L)
- v(0) + Σ (L) Σ lor(L)
rC(S
(
I.S,L
LOS
Σ (Lnd
Σ Lmna(L)
+
Σ
LorlL)
Σ Lo((L)
LC(SUHi),L
LCS,L40
LO(Sufi))
LN5#0
Jana (T. ( (1))+
Σ (LU
LCS
LnS=0
This allows us to break down the Shapley value into @(1) EEs (0C [A B..
12

---

Towards Attributions of Input Variables in Coalition
In the subsequent proof, first prove that the sum of AND interactions Esçayt [A] is equal to ESCNNES [S| (S).
Escautl [A]
(B)
Σ
(L
{i))
LC8
Σ n-1
Σ
Σ
and U (i))
Th m=0
m
SCNYA LCS
=m
33
E
11
(1)
m=0
m
SOL. SCN
[
-
Σ
(L // since $ L, 1S| 2 [L]
n
LCN
M=|L|
SDT. SCNWO IS =m
3
n 1 - -111)
Tana (L)
m [T,]
LCNV()
M=
m
x-1-14
nn- 1-11-10 |L]
Σ
Σ
Iama (i)) M m m-L
n
n-1 (L++
LEN((1)
k=
0z.
Σ
(
[1| +
LCN((})
Σ SCN.iES
[m)a(S)
Lets = (i).
[
13

---

Towards Attributions of Input Variables in Coalition
Then, for the of OR interactions, have
EsgNv0l (8]
=ESCNUA
E (t)()
LnSØ0
E
Σ
(LU
n-
SCN LOS#0 19|m
EEL
Σ (LU
LCN m= m
SO SCN
=m
Σ ΣE
E
(LU
LEN m==
SCNMINL 18 =
R-1-44
Σ
Σ
// Since S N (1) L. |S| Sn 1 [Z]
ICN(D)
m=0
m
SEN.O 18|=m
R-1ー
Σ
-
1- I (i)(
LCNVO)
M=0
M4|
1- |b|
(TT(L. (i))
Meak = n [T]] m.
n-1
n2 - |L| - k:
LCN((
11-1-141-
1-1-14 4
Σ
1 (L
1- 14) Tor
k
LCN(O)
k=
Σ
+++1 (
n
LCN
= Σ
L UL (i))
(C)
Σ SCNNEe
Tor(S) 1et LU(1)
S
Therefore, @(1) + EscN.es 1 (Sn (S)).
D. Proof of Theorem 3
Proof. According to the definition of the AND/OR interaction, we can get:
(S) = El5s(-1)55 -14| ( (L) Elgrr [vand (L U {i}) - Vand (L)]
lor(S) - (N \L) (-1))11)(11)))511114 [vor(N L) vor(N L- [i])]
where v(..) Vandl (T.) + vorl (T.).
14

---

Towards Attributions of Input Variables in Coalition
Then have:
Σ 21 (S) + [S)
(-1)181-14(44
Σ
E
E
{Vand (L {i}) - Vand + [For(N \ L) - vor - - - ((})1}
LCS)())
218|-1
(-1)181-14
Σ
Σ
{Vana [ (i}) Vand [T]] + [Va L) Tor - 1, (1))1}
LES
2|8|
{EN
(-1) [1
= E
(-1)44
{[vand (L {it) Vand [L]] + [V \ L) - Vor - L - (
SCNVA).2EL 2|s]
(gM(()
(-1)
E
(-1)14
{[uana (L U (2}) (L)) + [Nr L) - -N
- - (+)))}
2|
LEMDE
(-1)1s)
(-1)14
Σ
SCNMO,S2L 2 -I
Σ
2 {[uand (L (+}) Vand [I)] + [No L) Vor(N LL - -f})]}
(C)
Σ
Pand (S [i]) Vand [S)] +
Σ
1
[oo([N \ 5) - cor(N -S - // L S.
2
2
SCNV()
SCN
Σ
[Mand (SU (i}) (S)] +
2 US - (S)
1
2
(CN)(:)
SCN
Σ SCN
N A[ (SU {i)) Uor US {+})
(aad (S) + Vor (5)}
Σ
- JUSSUB (i)) x(S]
SCNV(
B())
Therefore, B(i) = EscN,ss - (S) + (S)).
E. Proof of Theorem 4 & Corollary 5
Proof. According to Theorem 2, we have: <(i) ETENNET 1 [Aand lor (T)).
Then, according Equation (6) in the paper, we have: (pS) Engs
[8]
[maa (T) I [T)]
[T)
Thus, we have:
Σ
o(1)
SES
Σ
Lnnd (T) + [o)
1E TEN.
Σ
Iand IT) +
Σ
[Tan (T) + Ioe (T)]
T
T
ES TEN,TDS
TEN.TSSTT3
IS|
(T) + [T) +
Σ
(T)aa(T) + [ur(
[S]
T
T
IES
T2S
TSN.T2S.T3
15

---

Towards Attributions of Input Variables in Coalition
(()
E
[T|
(und(T) + (or(T))
1ST
IES
TSN.72S/79
((() + Σ Σ
[ana(T) + [ar(T)
iES
iES TCN,
T2S.
13i
= SS|--
[S] (()+
+
E
Tnn (T) + Ior [T)
T
TEN.TNS7U.TT5//
// For any T,
annd [T)) will only be counted [T S| times.
+ (())
Σ
TnS
[Land (T) + (T')
[T'
Therefore, we prove that: Eies (11) + EreNesH#MMss
Ind + Tor (T))
Especially, if set of input variables in S are always encoded by the DNN coalition without any interactions containing
partial variables in ie. vT E (7: 5 z T,T N, S), (T) = (7) 0, then we have:
Tns
Σ 6(1) = ((S) + KES
Σ
Tnnd (T) + [ar(T)) = (s(S
(
TSNSInS40.7TS4
Besides, we have:
(i1)
((5)+
Σ
1
(Tn + Lor [T)) |s| p(S)
[8]
[8]
T
TEN,728,T9
Therefore, we further prove Corollary 3.5.
F. Proof of Theorem 6 & Corollary
Proof. According Theorem 3.2, have: (0i)= ΣTENJET 1 [nand + [or(T))
Then, according to Equation (6) the paper, we have: s(S) =Er2s |8| TT (man(()) + Tor (T))
Thus, we have: Vi E S,
(i)
Σ
aand (T) + [T)
TEN
Σ
(T) + (T)] +
Σ
(T) + Ion (T)]
[T7
[T|
TENTT2S
TEN.7S.TT.
|S|
[nnd (T) + [o)
Σ
Vnnd (T) + Tor (T))
SS|
TENT2S
TENTZSTT9
p(S)+
Σ
1
(Lnd (and (T) + [T))
|S|
[T'
TENT2S
Therefore, we prove that @(1) = - +I EEENNTSSTT Hand (T) Lor (T)).
16

---

Towards Attributions of Input Variables in Coalition
Specially, let {i} and then have:
((1)
(5))
1 +
Σ
(T) Tor (T)
[T]
TEN.T28.T3i
(((()
1
Σ
1
an (T)
(T) + [T)
(
TCNT
=(() +0(5 {i))
Therefore, we further prove Corollary 3.7: (p( {i}) d()).
G. Proofs of axioms for the attribution of a coalition
In this section, we will prove the axioms for the attribution of a coalition in the main paper and Corollary 8.
G.1. Proof of Anonymity axiom
Proof. According the definition of the AND/OR interaction, we can get:
lndd, (T) = - (L). for. (T) = -E (N L)
Innde. (o(T) (11)occ((1)) (L),
I (T( = (-1 (-10) L)
Due to (v( U(S,, we have: d'ama (S) and (o))(((())) Uoo (S).
Thus, we have:
land, (o(T))
Σ (-)oor( (r
(-10)))a0mm1))))7)- o (K))
(n (-1) Uand K))
-KKET (-1))71-11/mmal = Land, (T)
Tor,. Ior.. (a(T)) (-)ee(-a))
- c(K) (k) [(K))
= (-=aakkssrrr (-1) o(K)
K))
EKCr (-1) ba K) = Ioc. (T)
|S| Then, according to Equation (6) in the paper, we have: (o(S) = Erps a(S)
[Tadd (T) + Ior, (T) and (oo(a
[2'
Σr
[T1 [under (T) + Iaroo [T)).
Thus, we have:
[o())
[o(S)
Pou (o))) Σ
[Tand, (T) + Toe.o
Σ
[o([.)] [Tan, (a([)) + (o..
(T)
(Sa(S)
(=o(L)2o(())
|
|
Σ
andd (L) + Ior. [o)] =
[Tnd (T.) + Ior. (I)) = = (P(()
L
(L)
L28
Therefore, we prove the Anonymity axiom.
17

---

Towards Attributions of Input Variables in Coalition
G.2. Proof of Symmetry axiom-cx
Proof. According the definition of the AND/OR interaction, we can get:
and U {i)) -usmuuo) Band (L), lor (TU (-) ul L)
Innd( (TU (i]))= =
Vand L). oor (T U (i)) = - --
L)
Due to AS _ N
=((U(())) we have: AS S NN WV(,)) Vana (SU(i)) = Unnd ( (or (S))
(S (S
Then, we have:
Lana U - land lad
=E (
(1 (-1) Vand (L)
E E (-1))Tu(311144 Vama(()
-Euer (-1))20401-144emmml (L) Σ LCT (- (-1))(((4)-120)))) and (L U {i})
(- (-1) -14 aane + Eisr( (-)) and ((3))
E1Sr( (1i)) (L {i})
Unnd
La (UU())) (TUU())
E Maa
(N (N L.) + EE (-1) (
Mor (N L.)
Exco (1 L) Σ
LCT (-) DO (N (LU))))
(- (N L) (-)---1100 (N \ (L (()))
Σ Engo (-1 (LU (2,1))) ((N (L.())))))))))))))))) (M) 0
Besides, according to Equation (6) in the paper, have: ( U {i}) Erz(sU(a) SUftH [Lad (T) + Ioc [T)(T) and
U ((SU()) Ere(sU()) |SuliH
[Lndd (T) [T))
(
Then, we have:
(SU (i)) - (i)
ISU (i))
[SU
Σ
(T) + In((T)
Σ
[Tand (T) Ioe [T)
[T]
(T]
(2(SU(H))
(2(SU(H)
SS| +1
S
+|+1
(T) + (T)) +
Σ
Hnnd (T) + Lar (T))
[T]
[
T2(SU((())
T2(
|S++1
+1
SS|
Σ
[Tand (Tn)TT++A))) [or
Σ
[Tad (T)) + Too Ior
[T]
|T|
(265))
T2(SUG))TT
JS| +1
| +
= Σ
Laaa (T) + lor))
Σ
[und (T) + [T)]
[T'
[
T2(SU6))T73
T2(SU(h).T
|S|
+
|
Σ
[Iand U (1)) I
( ( (1))
(
U {iH
(UU
T2STCNM))
T2STCN
|S|
Σ 128TCNM())
(T (TU (i)) (T (7) + (1)) I (T)) 0
T
18

---

Towards Attributions of Input Variables in Coalition
Therefore, prove the Symmetry axiom-o axiom.
G.3. Proof of Symmetry axiom-3
Proof. Without loss of generality, we assume S CNT= 6.
According to the definition of the ANDIOR interaction, can get.VK 2 L, K N (SUT), ST,T + 9 S,5' # |8 IT",
m = (- (
(UUK)) = (-I) ( (--SSTII- worl (N J)
UUUSUT (-1 (
(K UT) E
(-1) ( (N {
Then, have:
(Ta L (-1) /anda (
(-I))KUSiUTI-- Vana(
E
Σ (-1))KuS(r)-1UUM aand (JUA)- E (-1)
Hand (JU B))
JE(KUSIUT)
AES'SS' APSYS'
BET
BYT/
Σ
Σ
(-1))Rss(TT--JJUB [anna [aad (J U UU Vand (J (JUB))
JC(KUSIUT))
AES'S' AYS BET BT" |
=0
(KUUSTT) - Lo UT)
= --ECCcKuurry (-1) (-I))KUSUTI-- (N J) + Σ JC(KUS'UM)
(-1))kusUU1-14400dl (N (J
E
Σ
(-1])KUSTUT/-LNBBBB (N (N)UBB)
(-1) (-) (NNUJA))
JC(KUS'UT))
BETVT'
AESTS'
B$TVT"
A4SiS5'
Σ
Σ
(-1) ( (N (JUB)) - (or (N
(N
JE(KUS'UT))
AESYS A AASYS BET BETVT",BT((' BT ||||88|
Σ
Σ
( (NN(AAUUUB (UUAAUN
JC(KUS'UT) AES A AS
TE B |
Σ
Σ
0=0
JC(KUS'U')
RES BET B |
Besides, according to Equation (6) in the paper, we have: (pLUS)- Exquury [LUT [K]
Σ ΣKS(US)
LUSI
[Land (K) + for and p(LUT)
[
(K) (K) for (K)).
19

---

Towards Attributions of Input Variables in Coalition
Then, have:
- -(UU)))p(LUTT)
[LUT| [
Σ
(K) (K) + [T)( - Σ
[Tana (K) + [Tr(
K2(LUS)
(2(LU))
ILUS|
LUSI|
Σ
[Tana (K) + (or))o((K))) [K]]+ +
Σ
[Tan((K) + [K]
[K]
[K]
(2(LUSUT)
K2(LUS),K2T
Σ (2(LUSUT)
LUT
(K)
+ [o[[K]] +
Σ
LUT
ana (K) + [k)
|K]
K2(LUT),
LUS
TUTTI
E
(K)) + [or(
Σ
[Tand (K) + [ar(
|K]
K
K2(
K2(LUT),K25
LUS
E
Σ
[Tand (K + (u
(S.. KUSUT
LUTTI
Σ
Σ
T
KUSUU
(QLACM((SUT) S'SS
LUT KUS
= Σ
Σ
[nd - + L. -
ROL T' (SU)( S' |S'
=0
Therefore, we prove the Symmetry axiom-3 axiom.
G.4. Proof of Additivity axiom
Proof. According to the definition of the AND/OR interaction, we can get:
lndd, (T' =
Vand ( L), Lor (T) = - --
\ L)
land., (T) -1sr(-1))7-1111 (L), Lor., (T) - (-sr(-1)171-14 Vora (N L)
aand., (T) = (-))((1))(11-))))
(T.), T Tor.y. (T) = -ESST (11)271-14 Vorz (N I.)
where uLL Vand (L) Vor (L), 21 (L) Vand, (L) + Vor, (L) and v2(L) Unndz (L) + Vorz (L).
Due to v(L) U1 (L) + v2(L), (D), have: Land, (T") land., (T') Landur (T) and Lor, (T) Lor., (T) + Lor.. (T).
According to Equation (6) in the paper, we have: (o(S) = Erys [T| Hund, (T)) + Lur, (T)], Po, (8) = Erps
[S] [T] [Tand., (T) + Jarv, (T) IS) [T] [andd., (T) Tarn, (T)), (S) Erys
Then, have:
|8|
(S) Σ
[ and, (T') Loc. (T))
'
T23
IS
Σ
(Jand.y (I') + Land.ng (T') + (Lor., (T) + Lor.y (T))
[T'
T29
|S|
S
Σ T2$
Innd_, (T) + lor., (T)
Σ
Land.p (T) Iorog (T)
[
T2S
Pv. (S) + Ge,, (S)
Therefore, we prove the Additivity axiom.
20

---

Towards Attributions of Input Variables in Coalition
G.S. Proof of Dummy axiom
Proof. According the definition of the AND/OR interaction, we can get:
vT 3 i, Jar (T)= -- - L) = E- [Vand (L U {i}) Vand(L) (L))
VT i, Land (T) -Esr(-1)) (T)
=
[oor L) - Upe (N - -- [1))
Due to AT (() (2t) - u(T), we have: AI _ CN) (i), Vand (TU = v'and (T), ( (T}) = Uor (T).
Thus, we have:
land (T) = E LCTV11 (-1) 21+1 [aaa U {i}) - Vand [L] 0
(T) EI (-1) [No \ -orlN( - L {{}}]]
Then, according Equation (6) in the paper, we get:
(SS)
Σ
S Tnna (T) + [o(T]]
E
SS|
Tand (T) + [T)( 0
T
T28
T28T9
Therefore, we prove the Dummy axiom.
G.6. Proof of Corollary 8
Proof. According to the Efficiency axiom the Shapley value, we have: v(N) - v(0) EiEN 6(i).
Then, according Theorem 4, we have: Eies (11) (p() ErcNams40.mn4s
[TnS]
[Ind (T) + Ioe (T)].
1T
Thus, we have:
n(N) - v(0) Σ 61)
Σ
((1) + Σ
(1i)
iES
iEN
((()+ +
Σ
Φ(1) +
Σ
NNS
[nad (T) + Ioe (T)
T
iEN'S
TENTASHOTTNSyS
Therefore, we prove Corollary 8.
H. Detailed introduction about the axioms for the coalition attribution
The anonymity axiom shows that the order of input variables does not essentially affect the coalition's 's attribution (pS). The symmetry axiom shows that if two coalitions always have the same roles, then they have exactly the attributions. The additivity axiom shows if the model output v(S) can be represented
the sum of outputs of two sub-models vSS) = U1 (S) + e2(),, then a coalition's 's attribution can be decomposed into attributions computed on the two sub-models. The dummy axiom shows that if the coalition S contains a dummy input variable i, which does not contribute to the model output, then the coalition S has zero attribution (but the coalition \ {t} may have non-zero attribution ((S {i)).
I. Results of coalition faithfulness metrics on the image data
We evaluated whether these DNNs accurately represented natural coalitions in human cognition. We trained VGG- 11 (Simonyan & Zisserman, 2014) and ResNet-20 (He et al., 2016) on the MNIST (LeCun et al., 1998) and CIFAR- 10 (Krizhevsky, 2012) datasets. We divided an image sample into 8 x 8 regions and manually selected 10 image regions, which included some neighboring regions with specific semantics and some other random regions. The set of regions that represented clear visual concepts was annotated as a true coalition. In comparison, a random set of image regions was annotated as a false coalition.
21

---

Towards Attributions of Input Variables in Coalition
Game1
FIC 3.5 05
00
00
((B)577)) and vG1,A,57 3) advantage in shape patton, Honeeer, white opportinity for stones lmok union white stones, (hr..iom.p(1.....5)) < (EB.5..))
shope "Shoulder-hi"" pstiem, fiaeefonn,
et -014
(3.7.101-225
CL K.R 10)
wi 2.A 8.100)-088
2011
Game 2
(1) <(17, 101) 0.74 and (1 10)) 255. The combinatioon of white stanes 7 and 10 not good strategy. Howerer, the move black stune makes Eie comitnation white stoues {7. 10) form combut condigurtion. The shape patteen (37,100
as typical sactical patten known "shoulder-hii" Theeefore, shape pantm (3,7.10)
advanngeous white
shape patter (7, 17)10)
(2) ((1, 10)) = 0.74 and (14,77 10) = 1339 Likewise, the zove black stoae 6 also mikes the comsimation of white stooes 17. 101 ferm comber contiguratio. The shape pastem (4,7.10] is also a "st pattern, and more advantageous for white stanes than stape patter 12. 10) Hovererr the postbon of black shone in the pattor (4. 7, 10) supense to the block
the patter (3. 7, 10). Therrfrre (114, 7, 70]) 9. 101). (83 7,10))=
and ( 0,303) 0.06 Althouhh stotes get opportunity to spiit white combinations (?, 8 10). Themfore
shape pattem 13,7,00) is "Shoulder-hc" partem,
problemaae placement white
shape pamom (3.7.0.10) have lower advantgge scom finn shape patten (3.7,10).
(4) s6t 7, 7,10) = 1.39 and p 7,0,00) = 0.80 Although the stape patters (4.7.00) is "shoulder hif" pattera, dae the problenarce placement of whith stree 8, black stotes get the opporinity to splitite white combinations (?&& 10). Therfore
shape pattmm (4.7.010) have lower adrantage than shape pattora (4.7100)
Game 3
#ELL 2.4 2aw -0.5
Game 4
WITS 2.11 -
000030
(1) ((11.2AA.5)) = -0.11 The shape pottom (1.2,4.5) is advantagmuu for black stones, because in this white stoces form combot configumation too slody.
(3) ( (1) = 3.41. The shape polleta (23,0) as advantagoous for white because it typical focttalized moves (Dinpáhi), known da "cumer regulae funn""
Figure 3. Analysis of shape patterns in Go compared to human intuition
Figure and 5 respectively show the results of coalition attribution faithfulness metrics of VGG-11 and ResNet-20 model on the CIFAR- 10 dataset. Figure 6 and 7 respectively show the results of coalition attribution faithfulness metrics of VGG-11 and ResNet-20 model on the MNIST dataset. In these figures, 21, #1u represent the selected image regions, and the image regions marked in yellow represent the selected coalition S. These results show that the manually selected coalitions, like (oo, T4} } on the left side of the top row in Figure 4, which represents the head of the horse, had high Q(S), R(i), (i) values and were considered as faithful coalitions. In comparison, the randomly selected coalitions with low high Q(S), R(i), (i) values, were considered as unfaithful coalitions.
J. Comparison with human intuitions in Go game
This experiment applies our theoretical framework to uncover shape patterns implicitly learned by the network, many of which go beyond traditional human knowledge.
We hired 5 expert Go players to analyze the fitness between the extracted coalitions and human intuition on many more game boards. Under their guidance, we focused on explaining shape patterns involving a limited number of stones, as determined by the experts. Specifically, we excluded coalitions with more than six stones, such complex configurations were often found to have a negligible impact and likely reflect noise. Figure J shows the detailed analysis of shape patterns in Go compared to human intuition. As shown in Figure J, some automatically learned coalitions do not fit human intuition. As a possible explanation for this, human players typically assess patterns based on short-term tactical search and a few-step lookahead, but the value network implicitly captures long-term statistical regularities from many more games. Although these long-term patterns are difficult to interpret directly, they may reveal new shape patterns. Expert Go players say they have learned some new knowledge from these patterns.
22

---

Towards Attributions of Input Variables in Coalition
R(()
6466
500
0.554
0,32
6:355
X1
2512
0.639
Xg
0.418
6:229
6.628
Xy
0:234
Xy
Xa
0.73
0.228
X5
0 S77
6.575
Xp
0.207
6:255
Xg
6:266
Xa
X;
X
Figure 4. Coalition attrihution faithfulness metrics of VGG-11 CIFAR- 10 dataset
R'(3)
R(O)
0,71
6.381
X7
605
6.677
X6
0313
6:344
X1
0.614
8.652
X2
6:38
0C Xy, Xx,
6.648
Xy
6:366
Xa
0.786
0,279
X5
0 .577
8.589
X
0.305
6:350
X:
X4
X>
X
Figure 5, Coalition attribution faithfulness metrics of ResNet-20 on CIFAR-10 dataset
23

---

Towards Attributions of Input Variables in Coalition
R(()
6465
6.083
0,364
6:300
0.797
0.791
0,309
6.39
Xo
602
6.659
0.312
0.441
8.470
0,399
Xg
X5
Xp
0:225
X
X4x
6.469
X
0.728
6.606
0,319
0:57
Figure 6. Coalition attribution faithfulness metrics of VGG-11
MNIST dataset
6256
X2
673
0.715
0.384
6:300
Xis
0.751
6.738
X2
03312
6:306
693
6.610
0.782
0.397
6:366
0,278
Xn
X5
X
X
Y;
0.703
6.757
0.301
6:366
Figure 7. Coalition attribution faithfulness metrics of ResNet-20 MNIST dataset
24


Reviews:
[{"review_id": "9b6PL5jsjQ", "reviewer": "Reviewer_MfBL", "summary": "This paper attempts to provide insights into an issue in attributions. The issue is when one computes an attribution method, such as the Shapley value, for a coalition of inputs, it does not equal the sum of the individual input values when they are attributed to separately. This effect is explained by analyzing interactions between inputs in terms of AND-OR interactions. The paper presents results showing that the difference between the sum of individual input attributions and a group attribution can be expressed entirely in terms of a weighted sum of AND-OR interactions of non-identical coalitions that intersect with the attributed coalition. The paper provides experiments applying their explanation method on synthetic, NLP, image, and Go-related domains.\n\n## update after rebuttal\nAfter reviewing the rebuttal, we will maintain our score. Contrary to reviewer ZrgL, we believe the theoretical analysis the paper provides is sufficient to merit an accept. In concord with reviewer ZrgL, we believe that adding some practical applications of the theoretical results would significantly increase the impact of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your appreciation of this work. We would like to answer all your concerns. Please let us know if you have further questions or if you are not satisfied with the current responses. Thanks a lot.\n\n---\n\n**Q1: In some experiments, it is not clear how faithfulness is being measured. I might suggest an insertion/deletion metric.**\n\nA: Thanks for your suggestion. In fact, there are two types of faithfulness in this research.\n\n*The first type is the faithfulness of a coalition.* In this study, we propose a new theory to analyze the faithfulness of a coalition from the perspective of attribution conflict. We propose metrics of $Q(S),R(i),R’(i)$ for evaluation. If a set of input variables mainly participate in most interactions as a group, then they will exhibit a large value of $Q(S),R(i),R’(i)$, and they can be taken as a faithful coalition; otherwise not. This evaluation strategy is motivated by the fact that the attribution conflict is a ubiquitous problem with different attribution methods, but has not been well investigated. Therefore, we propose metrics of $Q(S),R(i),R’(i)$ to evaluate the faithfulness of a coalition in terms of attribution conflict.\n\n*The second type is the faithfulness of the attribution value.* To this end, some recent theoretical studies [cite1,cite2] have mentioned that it is difficult to determine the ground-truth attribution for a DNN, so it is not a solid choice to use the network output changed by inserting/deleting a variable as the ground-truth attribution for evaluation. Specifically, these studies have pointed out that it is difficult to annotate the ground-truth attribution for the DNN. In fact, this can also be explained by our interaction theory, i.e., the inserting/deleting order significantly affects the tested attribution of a variable. For example, if the attribution mainly comes from an AND interaction S, then the deleting strategy usually assigns the interaction’s attribution to the first deleted variable in S. The inserting strategy will allocate the interaction’s attribution to the last inserted variable in S. Nevertheless, we would like to discuss more about this in the paper. Thank you very much for your constructive comments.\n\n[cite 1] Yang et al. “Benchmarking attribution methods with relative feature importance”\n\n[cite 2] Rao et al. “Towards Better Understanding Attribution Methods”\n\n---\n\n**Q2: Another paper on attribution of coalitions, although in the gradient based context, is given in \"A Unifying Framework to the Analysis of Interaction Methods using Synergy Functions\".**\n\nA: Thank you very much. We are glad to cite this paper and discuss its relationship with our work. This paper introduces a unifying framework for game-theory-inspired attribution methods, analyzing feature interactions and synergy distribution to help understand which attribution method is suitable for the target model. In comparison, our study focuses on a different problem, i.e., using AND-OR interactions derived from the Möbius transform to clarify the cause for the conflict within a coalition’s attribution.\n\n\n---\n\n**Q3: It appears that the decomposition of a model into AND-OR interactions is heavily sensitive to the choice of $\\gamma_L$. … Additionally, the use of LASSO is only a suggestion, meaning it is not settled how to determine, and by extension, how to determine I_and, I_or, and derivative values.**\n\nA: This is a very good point, and the extraction of AND-OR interactions does depend on the choice of $\\gamma_L$. We follow lots of previous studies[cite 1, cite 2, cite 3] to use LASSO to learn sparest AND-OR interactions, because [cite 4] has proven that if we exclusively use AND interactions for explanation, we need to use a total of $2^m$ different AND interactions to represent a single m-order OR relationship. Similarly, we need to use $2^m$ OR interactions to represent an m-order AND relationship. This theorem motivates us to use LASSO to learn sparest AND-OR interactions, and the sparest interactions are believed to capture the intrinsic representation logic of a DNN. Meanwhile, the simplicity of an explanation is another reason for us to use LASSO.\n\nNevertheless, the optimization of $\\gamma_L$ does bring some noise to the computation of interaction effects. Fortunately, we can use some optimization technologies[cite 5, cite 6] to help solve the optimization problem.\n\n[cite 1] Ren et al. “Defining and quantifying the emergence of sparse concepts in DNNs”\n\n[cite 2] Li et al. “Does a neural network really encode symbolic concepts?”\n\n[cite 3] Ren et al. “Where we have arrived in proving the emergence of sparse symbolic concepts in AI models”\n\n[cite 4] Ren et al. “Can we faithfully represent masked states to compute shapley values on a dnn?”\n\n[cite 5] Diamond et al. “CVXPY: A Python-Embedded Modeling Language for Convex Optimization”\n\n[cite 6] Agrawal et al. “A Rewriting System for Convex Optimization Problems", "claims_and_evidence": "Insightful theorems are provided with rigorous proofs provided in the appendix.\n\nA variety of experimental evidence is provided.", "methods_and_evaluation_criteria": "In some experiments, it is not clear how faithfulness is being measures. I might suggest an insertion/deletion metric.", "theoretical_claims": "No", "experimental_designs_or_analyses": "No", "relation_to_broader_scientific_literature": "The paper is firmly situated in the literature body regarding theoretical analysis of perturbation-based and game-theoretic attribution methods. The paper mentions Shapley value, Banzhaf value, Shapley-Taylor, Faith-SHAP, which are important background to these results.", "essential_references_not_discussed": "Another paper on attribution of coalitions, although in the gradient based context, is given in \"A Unifying Framework to the Analysis of Interaction Methods using Synergy Functions\". This paper decomposes interaction methods based purely on \"AND\" interactions, and characterizes gradient based interactions based on their action on monomials.", "other_strengths_and_weaknesses": "Strengths:\nRigorous and appropriate analysis of interactions.\nThis reviewer generally agrees with the direction of the paper (mathematical analysis and theorem production to gain insight of interactions among coalitions).\nGenerally clear writing, no typos spotted.\n\nWeaknesses:\nIt appears that the decomposition of a model into AND-OR interactions is heavily sensitive to the choice of $ \\gamma_L$. For example, $ \\gamma_L = 0.5 v(L)$, causes all OR interactions are 0, while $ \\gamma_L = -0.5 v(L)$ causes all AND interactions to be 0.\n\nThe definition of AND and OR interactions themselves are a function of the model if the LASSO method is used, which sets this method apart from other methods insofar as finding interactions now requires an optimization over the inputs for each input attributed to, as well as the calculation after $\\gamma_L$ is found.\n\nAdditionally, the use of LASSO is only a suggestion, meaning it is not settled how to determine $\\gamma_L$, and by extension, how to determine I_and, I_or, and derivative values.", "other_comments_or_suggestions": "The above weaknesses are not necessarily killer for the paper. I recommend mentioning them and either attempting to address them or acknowledge that how to choose $\\gamma_L$ still needs to be determined, but does not affect the theoretical results here.", "questions_for_authors": "Please respond to \"Strengths and Weakness\"", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A5dO1bpU25", "reviewer": "Reviewer_ZrgL", "summary": "This paper proposes a new perspective on common attribution methods such as Shapely values and Banzhaf values. The paper does so in a quite theoretical way illustrating that one can reformulate the computation of these attribution methods in terms of \"AND\" and \"OR\" interactions. The AND interactions are \"hot\" when all players of this interaction are present in a coalition and the OR interaction is \"hot\" when at least one player of this interaction is present in a coalition. Once an interaction is \"hot\" it contributes to the worth of a coalition (is part of the value functions output).\n\n## update after rebuttal\nThe rebuttal did not alleviate my concerns with the paper. I still like the theoretical work this paper is doing and the novel representation decomposing the value function into I_and and I_or interactions.\n\n- I still see issues with this work's Go experiment. I do not see how this work's \"explanations\" or better attributions **(a)** help expert Go players (as the work claims but _does not provide any evidence for_) or **(b)** shows how only with the novel representation we can come to new insights we otherwise could not have come to by using other explanation methods (which might be flawed but still get the job done). \n- Likewise, I still think that this method is not well compared and put into context with the current stream of attribution methods. The criticisms towards the current state-of-the-art and the papers novel interpretation of interactions are not compared to the current explanation literature. The paper is spending a lot of time on arguing that current attribution methods are flawed but **does not provide enough evidence where current attribution methods fail or how big this problem practically is**. \n- After checking the replies by the authors, I was left with more questions regarding the empirical evaluation and wanted to check this work's implementation. However, the authors **do not provide any code** for review.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. **Please feel free to contact us if you have any further concerns as soon as possible.**\n\n--- \n\n**Q1: Ask for the significant value of our method. Why not focus on computational efficiency or design new methods?**\n> “I do not understand how … community”\n\n> “I think that the paper is … right now.”\n\nA: A good question. Analyzing and debugging mathematical problems with attribution methods represents a newly emerging research direction of attribution methods[1,5,6]. Compared to boosting computational efficiency or explanation accuracy, *people gradually realize that the lack of a clear explanation for inherent mathematical limitations in attribution methods have hampered the future development of attribution methods, as follows*\n\n$\\bullet$ **Background 1:** Most attribution methods are designed empirically, previous explanation theories cannot obtain mutual consistency between them or clarify their theoretical foundations [4].\n\n$\\bullet$ **Background 2:** Most evaluation metrics for attributions have been found to have obvious flaws (see discussion in [4]). More crucially, constructing a benchmark model with a ground-truth attribution for evaluation also presents a significant challenge [2,3].\n\n**Therefore, besides designing a new attribution method, debugging the mathematical problem of different attribution methods represents a new challenge for XAI.** [5,6] all attempt to explain or unify the underlying mechanisms of different attribution methods.\n\nTo this end, our study explores a new perspective, i.e., explaining the mathematical factor that causes the conflict of attributions. This is one of the most common issues that are shared by almost all attribution methods, but have not been sophisticatedly investigated.\n\n**New experiments to show the commonness of the conflict problem on various DNNs.**\n\nWe demonstrate attribution conflicts by comparing 6 attribution methods across BERT-large, LLaMA, and VGG-11. Most attribution methods all exhibit conflicted attributions, but they fail to explain the internal mechanism. In comparison, our attribution method first clarifies a set of interaction effects as the hidden cause for the attribution conflict, and helps people identify representation flaws (incorrect attributions/interactions) in a DNN.\n\nPlease see the results (conflict.pdf) in https://gofile.io/d/0azDsA.\n\n---\n\n**Q2: \"However, the experimental evaluation\", ... \"how the new representation actually helps feature attribution ...\"**\n\nA: Thanks. First, our theory of explaining the internal conflict of attributions **does** help us design a new attribution method for coalitions, which first clarifies the intrinsic cause of the conflict problem. Please see Section 3.4 for details.\n\nSecond, our theory also provides a new mathematical metric to evaluate the faithfulness of coalitions, because breaking a faithful coalition will cause lots of internal conflicts. Thus, we conduct different experiments to use our theory to evaluate the coalition.\n\n(1) We build up a benchmark to evaluate whether our metrics could effectively evaluate the coalition discovery, i.e., distinguishing the faithfulness of a coalition (see Table 4).\n\n(2) Table 5  in the main text and Figure 3-5 in the Appendix evaluate the faithfulness of the coalitions for both NLP models and vision models. These all provide new insights into the attribution.\n\n(3) The experiment in Figure 2 uses our theory to explain shape patterns used by the DNN to play the Go game. Our method helps expert Go players learn new shape patterns (beyond traditional knowledge of the game) to play the Go game.\n\n---\n\n**Q3: About paper writing**\n\nA: Thanks a lot. We follow your suggestions to carefully polish the language.\n\n---\n\n**Q4: Can we disentangle the AND and OR interactions from each other in some methodologically novel way?**\n\nA: The definition and decomposition of AND-OR interactions (see Eq. 3-4) has been a well-established research direction. We have followed the standard methods widely used by [7,8] to extract AND-OR interactions. To this end, Kang et al.[9] at UC Berkeley have developed a more efficient but approximate way to compute AND interactions, but this method can only extract AND interactions.\n\n---\n\n[1] Kumar et al. “Problems with Shapley-value-based explanations as feature importance measures”\n\n[2] Yang et al. “Benchmarking attribution methods with relative feature importance”\n\n[3] Rao et al. “Towards Better Understanding Attribution Methods”\n\n[4] Deng et al. “Unifying fourteen post-hoc attribution methods with taylor interactions”\n\n[5] Lundberg et al. “A unified approach to interpreting model predictions”\n\n[6] Sixt et al. “When explanations lie: Why many modified bp attributions fail”\n\n[7] Li et al. “Does a Neural Network Really Encode Symbolic Concept?”\n\n[8] Ren et al. “Towards the Dynamics of a DNN Learning Symbolic Interactions“\n\n[9] Kang et al. “Learning to Understand: Identifying Interactions via the Möbius Transform”", "claims_and_evidence": "The main contribution of this work is that it illustrates that the worth of coalition can be represented with AND and OR interactions. It summarizes the current stream of literature about Shapley Interactions and shows that all contribution methods to some extend are not so intuitive. This in my opinion is a nice perspective and research question to take. The paper contains many examples (some more and some less easy to follow) showing where their perspective makes sense and is reasonable. The paper contains a few theoretical results.\n\nHowever, the experimental evaluation, does not really help and advocate why the new perspective on attribution methods is important for the general machine learning community. Yes, Shapley values and Banzhaf values are important for many machine learning settings. However, this paper spends a lot of time on the game \"Go\" and very little on machine learning models. After reading the paper and especially the empirical sections, I still do not understand how the new representation actually helps feature attribution, data valuation or other important application settings of the Shapley/Banzhaf value. Yet, this would be this paper's most important job.", "methods_and_evaluation_criteria": "I do not understand how the methods evaluation criteria helps the general machine learning community to make use of the new representation of the attribution methods presented here.", "theoretical_claims": "The theoretical claims of this work are interesting and up-to my knowledge novel. I very much appreciate the perspective this paper takes on Shapley values and their interpretation of different kind of interactions. I checked Theorem 3.2 and Theorem 3.3 in detail. While, the proofs could actually benefit from some comments (especially when sets in summations are getting restructured), I could follow along quite well. They seem to be correct.", "experimental_designs_or_analyses": "I checked the experiments, but do not see how they should convince the general machine learning community to make use of the new representation of the attribution methods presented here.", "relation_to_broader_scientific_literature": "Since this work focuses on game theoretic foundations on how to represent attribution scores, it touches on many machine learning applications. Most predominantly, explainable AI or data valuation. Specifically this work touches on the domain of interaction quantification, which currently is getting more attention.", "essential_references_not_discussed": "Seems fine.", "other_strengths_and_weaknesses": "### Strengths\n- I like the perspective of the paper and the theoretical work and I think it studies a very nice research problem.\n\n### Weaknesses\n- I think that the paper is from a methodology standpoint quite limited as it stands right now. The work should focus much more on the new representation of these attribution methods and use them for something meaningful like either a) computing attribution values more efficiently or b) creating more faithful explanations for machine learning applications.\n- I find this paper very hard to read and follow. It took me quite some time to get the gist of it (more on that in other comments or suggestions).", "other_comments_or_suggestions": "The paper is actually very interesting. However, in its current form it is very hard to follow and does not present a clear and convincing argument for your method. I strongly suggest to take a step back and revise the paper from the beginning. There are way too many examples with toy value functions and data modalities across the sections (starting off with vision + synthetic interactions in Fig. 1, then the natural text examples with the sentiment analysis, then the \"raining cats and dogs examples\" then the game of Go). This is just too much and takes away from your actual contribution. I am not saying you should forfeit all these examples. It is good to show that your method is generally applicable to a wide range of machine learning scenarios, but as it stands right now it is just all over the place and needs to be streamlined.\n\nI recommend to start of with one motivating example in the beginning and then taking a more abstract view throughout your methodology and theoretical background section, such that you can expand again in the experimental section at the end. There, clear examples from different ML domains are very much appreciated.\n\n__Sidenote__: Use less boldface and repetition in the sentences.", "questions_for_authors": "- Can we disentangle the AND and OR interactions from each other in some methodologically novel way? Currently the paper just argues for this new representation, but can this also be used either a) more efficiently compute attribution values or b) be used to more efficiently _explain_ machine learning models with different kinds of attribution scores?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rns9MpWGTD", "reviewer": "Reviewer_mhJ5", "summary": "This paper studies the partitioning of input variables in feature attribution methods. The central issue is that existing attribution methods compute importance scores of single features or predefined partitions, but they are not very good at attribution for meaningful coalitions of variables. The paper identifies fundamental conflicts in coalition attributions and provides a new method with theoretical guarantees. In particular, it analyzes AND-OR interactions ti reveal how feature interactions impact attributions and extends the Shapley value to define a new coalition attribution metric that accounts for interactions among variables. This method is validated on synthetic functions, NLP, image classification, and the game of Go, demonstrating consistency with human intuition.\n\n## update after rebuttal\nThe rebuttal addressed my concerns, so I kept my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your great efforts in reviewing this paper. We would like to answer all your concerns. **Please let us know if you have further questions or if you are not satisfied with the current responses.**\n\n**Q1: “No time complexity or scalability analysis.”**\n> The experiments involve small coalitions … feature-interaction explanation.\n\nA: A good question. We have followed your suggestions to provide a comprehensive analysis of the time complexity and scalability of our method.\n\n**Computational complexity:** First, the computational complexity of computing a coalition’s attribution is $O(2^n)$, which is the same as the computational complexity of the Shapley value and the Banzhaf value. Second, the computational complexity of computing AND-OR interactions is $O(2^n)$.\n\n**Scalability:** The large computational complexity is a common issue for many attribution methods (e.g., Shapley value and Banzhaf value) to scale up. To this end, we can apply the fast approximation sampling method proposed by Kang et al. at UC Berkeley [cite 1], which is the only method to speed up the extraction of AND interactions, to the best of our knowledge. Extending this method to extract AND-OR interaction is the next issue in future work. Nevertheless, this fast approximation sampling strategy provides a new hope to speed up the computation of the attribution. We will discuss in the revised paper.\n\nAs another widely-used strategy for scalability, previous studies[cite 2, cite 3 cite 4] usually define each input variable as a larger image or a longer phrase in a sentence to reduce the number of input variables, thereby reducing the computational cost. However, the attribution conflict problem is usually more serious when we use larger but less input variables. To this end, our theory naturally discovers the interactions that cause the attribution conflict, which help people understand the coalition attribution.\n\n[cite 1] Justin S. Kang, Yigit E. Erginbas, Landon Butler, Ramtin Pedarsani, Kannan Ramchandran “Learning to Understand: Identifying Interactions via the Möbius Transform”\n\n[cite 2] Ren et al. “Defining and quantifying the emergence of sparse concepts in DNNs”\n\n[cite 3] Li et al. “Does a neural network really encode symbolic concepts?”\n\n[cite 4] Ren et al. “Where we have arrived in proving the emergence of sparse symbolic concepts in AI models”\n\n\n---\n\n**Q2: It is unclear about the direct use case of this method in NLP and image domains. My understanding is that users always need to predefine coalitions rather than having the model identify the top important ones.**\n**What are some concrete applications of NLP and Vision?**\n\nA: A good question. Because our theory clarifies in mathematics the underlying cause for the attribution conflict problem ubiquitously appearing in different attribution methods, we can simply use our theory to automatically distinguish faithful coalitions and unfaithful coalitions. \n\nSpecifically, we can extract all AND-OR interactions between different elementary input variables. Because the attribution conflict w.r.t. the coalition $S$ is caused by numerical effects of all interactions $T$ that contain just partial but not all variables in $S$, we can identify faithful coalitions, i.e., most input variables in a faithful coalition $S$ are supposed to appear together in different interactions, instead of appearing separately. Therefore, our theory provides an essential perspective to identify natural coalitions automatically learned by an NLP model or a vision model.\n\nIn other words, the mining of faithful coalitions can be formulated as the discovery of common subgroups in the extracted interactions. In particular, the proven sparsity property of AND-OR interactions significantly reduces the computational cost of mining faithful coalitions.\n\nBesides, our theory can also evaluate the representation quality of a DNN. Given a set of faithful coalitions (with large values of $Q(S),R(i),R’(i)$) discovered by our theory, we can examine whether these coalitions encode interaction between obviously irrelevant input variables. If so, it can be considered as a representation flaw of a DNN. For example, if a coalition contains both foreground image patches and background image patches, or if a coalition contains both tokens related to the generated language and tokens irrelevant to the generated language, then this coalition usually represents a representation flaw.", "claims_and_evidence": "Yes.\n\n- Thoeretical part: the paper reformulates the Shapley and Banzhaf values in terms of AND-OR interactions (Theorems 3.2 and 3.3). The new coalition attribution method is then shown to be consistent with these formulations.\n\n- Empirical part: Three proposed faithfulness metrics (R(i),  R'(i), and Q(S)) are introduced to effectively measure the validity of a coalition. They are first verified on models fitting synthetic functions and then experiments on NLP tasks, image classification, and Go game.", "methods_and_evaluation_criteria": "Yes. The proposed metric makes sense and the evaluation is relatively thorough.", "theoretical_claims": "Yes, theoretical claims are provided in App Appendix. I scanned through the the proof of Thm 2 and 3 in the Appendix. Seems to be correct.", "experimental_designs_or_analyses": "Yes, the experiment design is reasonable, including NLP tasks, image classification, and the Go game. One issue might be these evaluations are more like case studies, where only certain coalitions can be covered, so the generalization is completely guaranteed.", "relation_to_broader_scientific_literature": "The paper is well-situated within the explainable AI (XAI) and feature interaction literature. It builds upon: Shapley value-based attributions, feature interaction explanations, and general game-theoretic approaches.", "essential_references_not_discussed": "The coverage of related work is reasonable, for feature interaction explanations. The XAI literature is too huge to cover comprehensively.", "other_strengths_and_weaknesses": "Strengths\n - The paper has a strong theoretical grounding. It provides a rigorous mathematical explanation for attribution conflicts.\n - The proposed method applies to multiple real-world tasks (NLP, images, and Go), and has been verified on all of them.\n - The AND-OR interaction framework offers an intuitive way to understand feature interactions, which I really like.\n\nWeaknesses\n - No time complexity or scalability analysis. The experiments involve small coalitions (≤10 variables). It is unclear whether the method scales to larger feature sets, which is a big concern for feature-interaction explanation.\n - Although the Go application is interesting, it is unclear how about the direct use case of this method in NLP and image domains. My understanding is that users always need to predefine coalitions rather than having the model identify the top important ones.", "other_comments_or_suggestions": "None.", "questions_for_authors": "- Time Complexity or Scalability: What is the computational complexity of the method? How does the method perform when applied to high-dimensional feature spaces?\n\n- What are some concrete applications of NLP and Vision?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a theoretical framework for analyzing coalition attributions in feature importance methods, identifying conflicts that arise when the attribution for a coalition of features does not equal the sum of the attributions of its individual components. The authors propose a formal decomposition of attribution conflicts using AND-OR interactions, offering new insights into how interactions between features result in attribution behavior. The framework generalizes to both Shapley and Banzhaf values and proposes a new metric for evaluating coalition-level faithfulness. The work is supported by theoretical analysis and experiments across synthetic functions, NLP tasks, image classification, and Go gameplay.

Strengths:
* The theoretical contribution seems strong, providing a new decomposition of attribution values using AND and OR interactions.
* The formalization reveals a common source of conflict in existing attribution methods and offers a framework for quantifying the faithfulness of feature coalitions.
* The paper unifies and extends previous formulations of Shapley and Banzhaf values,
* Reviewers MfBL and mhJ5 praised the rigor of the formalism and proofs, noting that it addresses an underexplored problem in explainable AI.
* The authors engaged deeply during the rebuttal phase, conducting new experiments (e.g., with Faith-Shap, expert validation in Go) and addressing reviewer questions about scalability, practical relevance, and potential applications.

Limitations:
* The empirical evaluation is somewhat limited in scope, especially for convincing a broader ML audience of the practical value of the theoretical results. Case studies are small-scale, largely synthetic, and not sufficient to demonstrate impact on real-world attribution workflows (though this can be argued about much of the XAI literature, too).
* Reviewer ZrgL (Reject) remains mostly unconvinced, despite the detailed rebuttal (though they did not elaborate after the authors' last comments). Their primary concerns are that:
  * The paper lacks comparisons to recent attribution methods designed for faithfulness (e.g., Faith-Shap - but this was addressed by the authors in their rebuttal),
  * The experiments are not sufficient to demonstrate utility or quantify the severity of the “attribution conflict” problem in practical settings,
* The Go experiments are anecdotal and lack evidence of benefit to expert users (but this was addressed by the authors in the rebuttal in an impressive addition).
* The definition of interactions relies on a hyperparameter optimization (via LASSO), which can bring questions about sensitivity and interpretability of the results.

Reviewer Discussions/Opinions:
* Reviewer MfBL (Accept) found the theoretical insights meaningful and believes the paper makes a valuable contribution to the understanding of attribution methods.
* Reviewer mhJ5 (Weak Accept) supports the paper for its formal strength and clear presentation of an underexplored problem, while noting that scalability and application in NLP/Vision are still open questions.
* Reviewer ZrgL (Reject) remained unconvinced after rebuttal, primarily due to limited empirical validation, lack of implementation/code, and unclear practical utility of the proposed framework. However, to my understanding, these were indeed addressed by the authors.


**Summary**
This paper offers an interesting and relevant theoretical contribution to the attribution literature, providing a novel view of coalition-level conflicts through an AND-OR interaction lens. While reviewer opinions diverged, I feel confident recommending this paper be accepted.
Decision: Accept (poster)