Rethinking Shapley Value for Negative Interactions in Non-convex Games

Authors: Wonjoon Chang, Myeongjin Lee, Jaesik Choi
Primary area: interpretability and explainable AI
Keywords: Shapley value, Interaction, Feature Attribution, Interpretability

Abstract:
We study causal interactions for payoff allocation in cooperative game theory, including quantifying feature attribution for deep learning models. Most feature attribution methods mainly stem from the criteria of the Shapley value, which assigns fair payoffs to players based on their expected contribution in a cooperative game. However, interactions between players in the game do not explicitly appear in the original formulation of the Shapley value. In this work, we reformulate the Shapley value to clarify the role of interactions and discuss implicit assumptions from a game-theoretical perspective. Our theoretical analysis demonstrates that when negative interactions exist—common in deep learning models—the efficiency axiom can lead to the undervaluation of attributions or payoffs. We suggest a new allocation rule that decomposes contributions into interactions and aggregates positive parts for non-convex games. Furthermore, we propose an approximation algorithm to reduce the cost of interaction computation which can be applied to differentiable functions such as deep learning models. Our approach mitigates counterintuitive attribution outcomes observed in existing methods, ensuring that features critical to a model’s decision receive appropriate attribution.

Decision: accept (poster)
Reviewer scores: 5, 6, 8, 5

Reviews and discussion:
<thread>
creation date:
1729975002180

thread_type:
official_review

<thread_object>
creator: reviewer_fjo6

<content>
summary:
The paper reformulates the Shapley value as $\Delta(\emptyset)$  plus a sum of second-order derivatives, which are refered to as interactions in the paper, and argues that ignoring negative second-order derivatives in the summation can provide better feature attribution.

strengths:
Overall, the writing is clear, and the reformulation of the Shapley value seems interesting.

weaknesses:
- Theorem 2 is already a well-known result in the literature, e.g., proposition 2.1 in (Nemhauser et al., 1978).


- In lines 176-177, the authors suggest that a game has a non-empty core if and only if the game is convex.  However, a balanced game is not necessarily convex, and thus this statement is false. A counterexample is $v(\emptyset)=0, v(\\{1\\})=v(\\{2\\})=v(\\{3\\})=3, v(\\{1,2\\})=v(\\{1,3\\})=v(\\{2,3\\})=5$ and $v(\\{1,2,3\\})=10$; the game is not convex as $v(\\{1\\}) -v(\emptyset) > v(\\{1,2\\}) - v(\\{2\\})$, and its core contains $(10/3, 10/3,10/3)$.

- I did not find any *clear* evidence to support the claim that "Our theoretical analysis demonstrates that classical payoff allocation in a cooperative game assumes the convexity of the game" stated in the abstract, which seems to be an overstatment.

- I did not feel that the motivation is compelling enough, please refer to my question.

Minor:
- In lines 133-134, the statement that ''the Shapley value is a solution positioned at the center of the core'' is not strictly correct, because the Shapley value of a game always exists while its core may not if the game is not convex. Besides, I would recommend that the authors include a reference for this statement for those who are not familiar. I know that for a convex game, the Shapley value is the average of $n!$ marginal vectors (though there may be duplicates)  that constitute all the extreme points of the corresponding core, which is convex.

- I feel it may confuse researchers by referring to second-order derivatives as just interactions, because there are already several defined interactions in the literature (Tsai et al. 2023). To fit into the existing studies, I think it would be better to term them as *second-order* interactions.
 
- The proof of Theorem 1 can be greatly simplified using $\phi_i(v) = \frac{1}{n!}\sum_{\pi} (v(\pi\^{i} \cup \\{i\\}) - v(\pi\^{i}))$ where $\pi^i$ contains all players preceding $i$ in the permutation $\pi$. 

- I would recommend that the authors write down the proposed API results in the case study for clear comparison. 

- For the case study of sigmoid function, the Shapley values of player 1 and 3 are $2.51$ and $3.73$, respectively. 

Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical programming, 14, 265-294.

Tsai, C. P., Yeh, C. K., & Ravikumar, P. (2023). Faith-shap: The faithful shapley interaction index. Journal of Machine Learning Research, 24(94), 1-42.

questions:
My major concern is the motivation of filtering out negative second-order derivatives, which the authors refer to as interactions. I do not think that the two simple examples as well as a few experiment results are sufficient. For the Shapley value, it is deemed good because it uniquely satifies the axioms of linearity, null, symmetry and efficiency. For the proposed API, which properties make it desirable?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730226994889

thread_type:
official_review

<thread_object>
creator: reviewer_apx2

<content>
summary:
This paper proposes a modification to the Shapley value for its use in measuring feature attribution of deep learning models. This modification is based on an equivalent reformulation of the Shapley value formula as a weighted sum of pairwise interactions between players (features). When pairwise interactions are non-negative (i.e., a convex game by Theorem 2), Shapley value gives intuitive results and also satisfies desireable conditions from a cooperative game theory perspective, i.e., it lies at the center of the core and satisfies coalitional rationality. However, when interactions are negative, results can be counterintuitive as the authors show through examples; in addition, this coincides with a loss of coalitional rationality. Naturally, the authors suggest clipping interactions to always be non-negative and report the value of this formula instead of the Shapley value. This formula reduces to the Shapley value when the underlying game is convex, but gives more intuitive results in their examples when the game is non-convex. The authors also propose a more tractable estimate using a Taylor approximation and show their approach is competitive with baselines on explainable AI tasks for image and text domains.

strengths:
I think Theorems 1 and 2 that reformulate Shapley value in terms of interactions and relate non-negative interactions to convex games are very insightful. These form the core theoretical discovery that enables the rest of the work. In addition, the case study examples appealing to the reader’s intuition on how negative interactions result in counter-intuitive Shapley value are helpful. Lastly, the Taylor approximation of their approach is competitive with standard baselines and provides intuitive features attributions.

weaknesses:
I see opportunities for improvement both in writing / motivation as well as experiments.

**Writing / Motivation**:
- The 4 axioms that uniquely lead to the Shapley value are mentioned several times but never defined. Any modification to the Shapley value necessarily leads to the loss of one of these axiomatic properties and it should be discussed how this manifests as a limitation of the proposed approach.
- Generally, the paper attempts to argue that Shapley value implicitly assumes a convex game (or least the formation of the grand coalition). I wonder if there is a better argument for the proposed modification. While it is clear that the core makes the assumption of a grand coalition forming, all Shapley value assumes are the 4 axioms, none of which explicitly require any rationality or formation of the grand coalition. Note these axioms are always satisfied regardless of the convexity of the game, and so statements like “Shapley value becomes nothing but taking an expectation formula” on line 189 are hyperbole. In addition, the first remark on line 094 states that the formation of the grand coalition is implicit in cooperative game theory, which is also too strong a statement (for instance, the problem of coalition structure generation obviously does not assume this). It seems the authors are taking the existence of the core as an axiom (core existence <-> convexity <-> non-negative interactions), and that would better serve as the starting point for their argument. Deep learning models typically assume one would make use of all features (i.e., the grand coalition forms), and so it seems sensible to assume this. Continuing this line of thought, could you better argue that the natural characteristic function for DL is one that is convex (i.e., is consistent with the formation of the grand coalition) and your work can be used to implicitly define such an appropriate function via clipping interactions (see questions)?

**Experiments**:
- Given the discussion of the core and Shapley value’s relation to it, why not compare against least-core [1,2] which always exists?
- I would have liked to see a systematic study comparing your exact definition in (6) to your Taylor approximation in (9). How does the approximation degrade? Can you sample a subset of coalitions (features) T and compare the two?
- I would have also liked to see how results in one of the domains (image or text) changes as the number of permutations varies (not just 100 or 300 permutations). How did you select the number of samples?
- Given that computational efficiency was a motivation for the Taylor approximation, can you please report runtimes for the different methods? For instance, IG seemed to perform relatively well yet its unclear if it is generating these results in a runtime that is comparable to your proposed approach.

[1] Benmerzoug, Anes, and Miguel de Benito Delgado. "If You Like Shapley Then You’ll Love the Core." ML Reproducibility Challenge 2022. 2023.

[2] Gemp, Ian, et al. "Approximating the Core via Iterative Coalition Sampling." Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems. 2024.

minor:
- line 098: “forming the grand coalition N is **an** optimal strategy”, e.g., v(S) = 0 is convex yet any coalition is optimal.
- line 112: “from **this** perspective”
- line 175: “we introduce**d** the concept”
- line 266: “It is **the** extension” is too strong. Given Shapley value is derived to be unique from axioms, that is your baseline for strong statements. You would need to prove that API is the only formula satisfying some set of conditions.
- line 359: “we introduce**d** some”
- line 410: “ResNet 50 in Figure ?” missing reference
- Please include more informative captions: for example, lines 413 - 417 can be moved to the caption of Figure 2.

questions:
- Which of the 4 axioms underpinning the Shapley value does your approach no longer satisfy? can you discuss this as a limitation?
- Can applying a ReLU to the interactions also be interpreted as first projecting the game onto the set of convex games?
- Relatedly, can the characteristic function be rebuilt from interaction terms, I(T)? The I(T) matrix appears to be a discrete hessian, so a characteristic function only exists iff I(T) is symmetric for every subset of players T. I(T) appears to be symmetric by definition. Applying ReLU to entries of it should not break symmetry. Therefore, a characteristic function should exist.
- There is some loss of information when applying the ReLU. Do you foresee any limitations? Are there other approaches that might retain more information or have desireable tradeoffs, e.g., a leaky-ReLU?
- line 452: “highlighting the tokens with attribution in the top 20%” - I was expecting to see the same number of tokens highlighted in Figure 3. Line 465 suggests tokens are word level. Why do I not see the same number of words highlighted. If tokens aren’t word level, can you underline the actual tokens?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730710363998

thread_type:
official_review

<thread_object>
creator: reviewer_yps5

<content>
summary:
The paper identifies negative interactions to be an issue for methods that quantify feature attribution by approximating the Shapley value. The paper establishes the equivalency between the convexity of the game and the absence of negative interactions between features, and that the Shapley value can only meaningfully represent the causal effect of a feature’s contribution for convex games. The paper proposes Aggregated Positive Interactions, an extension of the Shapley value to non-convex games that only accounts for positive interactions between features. The papers proposes to estimate Aggregated Positive Interactions using sampling interactions, and show empirical evidence on a few examples in image classification (VGG19 and ResNet50 trained on ImageNet) and sentence classification (BERT trained on the IMDB Review dataset).

strengths:
- The paper is well-written. The problem with using Shapley value for deep learning is rigorously discussed, and the proposed approach is well-motivated.
- A proposed method is simple and intuitive. An efficient estimator (using gradient) is presented to lower the computation cost.

weaknesses:
- The experimental evidence for the effectiveness the proposed Aggregated Positive Interactions is not strong enough. For the image classifiers, only results on a few image examples are shown for two models.. In the language model experiment, only one positive and negative sentence examples are shown for one model. Although the examples are quite illustrative, it’s unclear if they are cherry-picked.
- It’s unclear how scalable the approach is. See questions about its computation cost and sample efficiency.

questions:
- In Algorithm 1, it’s not exactly uniform sampling all permutations $\pi$, as each sample is reused for all $t$. How much of a computation burden is it to resample $\pi$ in the inner loop? And how much effect does it have in the performance?
- Could you discuss the computation cost & sample efficiency for the proposed approach? Since you are using gradient information to approximate the interaction, I would expect the estimator to be quite scalable. It’s odd that you have to convert the images to 20x20 patches for feasible computation.

Minor comments:

- Line 296: I think it’s inaccurate to call (7) an unbiased estimator of the Shapley value. The expectation represents the exact Shapley value. You might want to explicitly provide the Monte Carlo estimator in equation.
- It will be helpful to briefly define what “feature” refers to in this paper. It seems to refer to components of the data in this paper, but in other literature feature often refers to learned representations.
- Line 410: the reference to Figure 2 is not displayed properly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730833072445

thread_type:
official_review

<thread_object>
creator: reviewer_ke5c

<content>
summary:
This paper extended Shapley Value from convex games into non-convex games. The paper argues that traditional Shapley Value is only a fair and reasonable allocation when then underlying game is balanced or in other words, convex. Therefore, it is not a well-defined concept when non-convexity is involved. To address this issue, the paper proposed a variation of traditional Shapley Value called Aggregated Positive Interaction (API) that decomposes the total utility into pairwise interactions between players. The authors then provided an approach to estimate API using permutation sampling, which proves to be an unbiased estimator. Furthermore, the authors provided approximated method to compute API more efficiently. Experiments demonstrated the effectiveness of the proposed approach.

strengths:
The paper extended traditional Shapley Value to non-convex games, which provided a way for the community to attribute contributions of features in non-convex settings. Given that deep learning models are widely used so far, the method in this paper would of be great importance to general AI and ML community.

The paper provided theoretical justification of the proposed API attribution method, including proof of relationship between traditional Shapley Value and convexity, unbiasedness of API estimation etc. The theoretical contribution of this paper is novel.

The presentation of this paper is nice - easy to read and understand. The case study is interesting and really helps readers understand why traditional Shapley Value has certain limitations.

weaknesses:
The major weakness of the paper is that I don't see a clear and strong justification for why the API is designed this way, specifically why we need to take max with 0. Does the number 0 really matter? Can we take other numbers here? Traditional Shapley Value is supported by those 4 axioms, and they serve as a strong justification for the design of Shapley Value. However, for API, the utility of each individual may not sum up to the total utility. In this case, I am wondering why API has to be designed as in this paper? Does other design work like taking max with another number?

questions:
I am wondering why API has to be designed as in this paper? Does other design work like taking max with another number instead of 0?
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a modification to the Shapley value for its use in measuring feature attribution of deep learning models. This modification is based on an equivalent reformulation of the Shapley value formula as a weighted sum of pairwise interactions between players (features). The authors suggest clipping interactions to always be non-negative and report the value of this formula instead of the Shapley value. This approach gives same results for convex settings (as the standard Shapley value) but also gives more intuitive results even when the game is non-convex (the authors provide extensive examples). The reviewer with the highest expertise championed the paper and the other reviewers were either slightly positive or slightly negative (i.e., the rest of the reviewers believed that this is a borderline paper). We recommend weak acceptance and suggest the authors to address all the comments of reviewer ApX2 in the camera ready version.