acceptodds
Under review as a conference paper at ICLR 2027

Endpoint Sensitivities Guide Limited-Query Shapley Regression

Abstract

Shapley attribution needs every coalition of input groups, and for an implicit graph neural network each coalition costs an equilibrium solve. An affordable budget can fit a polynomial surrogate's pairwise interactions but not its three-way ones, so one three-way term must be chosen before the sampled values can fit its coefficient. We let the explained model make that choice. Its endpoint sensitivities, measured only at the empty and the full coalition, select the term at the cost of two linear solves, and we prove that the coalition values cannot make the choice themselves, since their own endpoint information reduces to a single number beyond pairwise structure. Across four graph-classification datasets and twenty independently trained models, sensitivity-informed cubic Shapley regression cuts low-budget attribution error by over 75% against second-order PolySHAP, and matched controls that choose the term differently all have higher error, 1.55 times ours when our choice is permuted across groups. More broadly, model derivatives can choose where to spend scarce representational capacity, while the costly evaluations that define the target decide how much of it to use.

Primary area:
interpretability and explainable AI
Keywords:
Shapley values, attribution, implicit graph neural networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_MeJrOpenReview ↗
Rating
2(−1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies limited-query Shapley regression for differentiable models with expensive coalition evaluations, especially implicit GNNs. It uses gradients at empty/full masks to choose one weighted cubic basis function e3(w⊙y), estimates its coefficient from sampled coalition values under efficiency, and regularizes the remaining cubic space. A theorem characterizes intrinsic multilinear-game endpoint information modulo quadratic additions; constrained partial regression yields exactness for a restricted quadratic-plus-supplied-direction class. Four graph-classification datasets, twenty trained models, balanced node-feature groups, and matched controls support an empirical benefit from assigning sensitivity weights to the correct groups.

Critical strengths
  1. The distinction between choosing a representation direction and estimating its coefficient is useful and clearly implemented. Model-derived information selects a column before reading interior coalition responses; the responses still determine the coefficient.
  2. The theory carefully distinguishes the model's fractional-mask extension from the game's intrinsic multilinear extension. I checked the endpoint-quotient argument in Appendix A and the constrained regression/exactness arguments in Appendix C and found their stated conditions important and plausible. Estimability of the attribution, rather than full coefficient rank, is handled explicitly.
  3. The controls are well designed. Uniform, group-size, label-permuted, and no-supplied-block controls share masks, values, and normalization. Averaging all 105 fixed-point-free involutions preserves the multiset of weights while removing their correct assignment and avoids dependence on arbitrary group labels.
  4. The paper reports a predeclared balanced estimand, hierarchical uncertainty, full cell-level results, leave-one-dataset-out analyses, and an official OddSHAP comparison. Appendix D quantifies derivative overhead rather than calling gradients free. Exact games at g=8 provide a strong evaluation reference.
  5. The evidence goes beyond the main aggregate: balanced feature groups address group-size confounding, the residual-angle diagnostics show genuinely different directions, and noisy-response experiments are explicitly distinguished from derivative-noise robustness.
Critical weaknesses
  1. The sensitivity-specific benefit is smaller and more heterogeneous than the main quadratic-baseline headline suggests ( Sec. 5, Appendix F). The full procedure improves the balanced error by 5.22-fold over quadratic regression, while the no-supplied-block cubic-ridge control is 1.35-fold worse than the full method and uniform weights are 1.29-fold worse. Thus the total improvement combines cubic regularization and sensitivity selection. IMDB-BINARY strongly enlarges the separation and interval upper tails; without it, sensitivity-specific control ratios are about 1.14–1.29. These remain useful gains, but the abstract/main text should separate them from the total gain and explain dataset heterogeneity.
  2. Practical scalability and equal-total-cost advantage remain incompletely demonstrated ( Sec. 5, Appendices D–E). All experiments use eight groups. This enables exact references but leaves unanswered how the selected direction and cubic matrices behave as group count increases. Also, the experiments computed gradients in forward mode: Appendix D reports 15.5 coalition-equivalent units for both endpoints versus 2.07 for the verified adjoint alternative. Comparisons match Boolean queries, not complete compute or wall time. The distinction is disclosed, but a concise total-cost comparison, including regression and baselines spending the saved derivative budget on additional coalitions, would strengthen practical claims.
  3. The negative theorem and exactness guarantee need consistently bounded interpretation (Theorems 1–3). Theorem 1 concerns endpoint-only, quadratic-invariant rules, not every estimator using the available interior coalition sample. It does not establish that game information in general cannot choose a useful cubic term. The exactness result concerns v in G_<=2 plus span{q}; it is not a general approximation-error guarantee for real implicit-network games. State these restrictions in the headline motivation as carefully as in the formal sections.
  4. Why endpoint magnitudes predict a useful Boolean interaction direction remains mostly empirical (Sec. 3, Appendix F). Fractional-mask derivatives depend on the extension and can change while all Boolean coalition values stay fixed. The paper recognizes this; it means the selected direction is an inductive bias tied to the mask parameterization rather than information determined by the Shapley game. The existing exact games could support a diagnostic relating selected directions to actual dividends or attribution corrections. Appendix F.5 also finds no clear advantage from using both endpoints over the empty endpoint alone, which deserves main-text visibility.
  5. Comparative and uncertainty scope could be sharper. ControlSHAP and regression-adjusted Monte Carlo are discussed but not evaluated; [ControlSHAP, Goldwasser and Hooker] (https://arxiv.org/abs/2310.07672) is particularly relevant to whether derivatives buy more accurate attribution at matched cost. OddSHAP changes native sampler and estimator jointly and is secondary evidence, as the appendix appropriately notes. Four datasets limit population-level generalization despite 100,000 bootstrap draws; the four aggregate intervals are marginal, without simultaneous correction. These qualifications should remain visible when describing all comparisons as supported.
Questions for authors
  1. Please distinguish the total gain over quadratic regression from sensitivity-specific gains, and report the quadratic-baseline aggregate with IMDB-BINARY removed. Is there an existing diagnostic explaining that dataset's especially large control separation?
  2. What is the practical total-cost comparison for the actually used forward-mode implementation and for the verified adjoint alternative, including regression time? Are results with the corresponding extra coalition budget already recorded?
  3. Can existing exact games quantify alignment with relevant cubic dividends or attribution corrections, and does that explain when the sensitivity prior helps? Please also summarize the empty-endpoint control.
  4. Are there existing larger-group or ControlSHAP comparisons, or should the claims explicitly remain scoped to g=8 implicit-model benchmarks? These are clarification questions, not a demand for a complete new benchmark suite during rebuttal.
4 comments
Reviewer_MeJrOpenReview ↗

follow-up and reconsideration

My main concern regarding the lack of theoretical justification for why first-order endpoint sensitivities should identify relevant third-order interactions remains unaddressed. Since the proposed method relies on this assumption, I am revising my rating from 3 (weak acceptance) to 2 (weak rejection).

AuthorsOpenReview ↗

Response to Reviewer MeJr (1/3)

Thank you for checking the arguments of Appendices A and C so closely and for your precise questions. We are sorry to have kept you waiting. Answering the reviewers' questions called for new proofs and experiments, which we have only now completed. Your follow-up asked why first-order sensitivities should indicate third-order interactions, and we answer that first. The theorems that you checked are unchanged in content, and new and substantively changed text is marked in red in the revised paper.

Theoretical justification for first-order sensitivities. First-order sensitivities point to the relevant third-order interactions when interactions grow out of main effects, as the effect-heredity principle of experimental design assumes. The revision states this assumption, proves that it holds in a class of single-index models, bounds the error on any game by the remaining misalignment and the dividends of degree four and higher, and measures that misalignment on the exact games of our models. At our budgets no estimator can be accurate for every game (Appendix C.1), so any guarantee of accuracy must rest on an assumption about the game, and we state ours explicitly.

Theorem 1 (Section 2.3) shows that an assumption is needed. Because the regression fits every degree-two term directly, a rule that looks for the cubic direction should be unaffected by adding a degree-two game. Such a rule, reading only endpoint data, depends on the game through a single number, so for g≥4g\ge4 it cannot return the cubic direction of every game, and if it treats the groups alike it returns the symmetric direction of our uniform-weight control. An instance-specific choice must therefore give up this invariance and tie the cubic part to information beyond that number, such as the magnitudes of the individual endpoint sensitivities, which distinguish the groups.

The assumption we make is an established principle of experimental design. By effect heredity, an interaction tends to matter only when its main effects do (Hamada and Wu, 1992; Chipman, 1996), and the prior of Joseph (2006) ties the scale of a three-factor interaction to the product of the scales of its three main effects. We read the sensitivity magnitudes as these scales and give each triple the product of its members' weights (Sections 1 and 3.2). Product weights also help when they enter the ridge penalty instead of one direction. Heredity ridge, which uses them in this way, improves on cubic ridge by a factor of 1.311.31 and on uniform weights by 1.251.25 (Appendix F.13).

The new Appendix B.4 proves the identification in a class of models and bounds the error outside it. Take a single-index model, where the mask enters only through a weighted sum with positive weights and a smooth link whose derivative is nonzero at one end at least. Proposition B.4 shows that the normalized endpoint magnitudes recover the normalized weights of the sum and that the cubic dividend of each triple is the product of its three weights times an average of the link's third derivative. The cubic direction built from these magnitudes, before the small uniform share is mixed in, therefore coincides with the game's cubic part when this derivative is a nonzero constant, and when it keeps one sign with absolute value between L>0L\gt0 and UU, the sine of the angle between the two is at most (U−L)/(U+L)(U-L)/(U+L). For every game, on designs where the quadratic stage is exact and the selected regressor has a nonzero residual, Corollary B.1 bounds the error of the unpenalized partial regression by a constant times the size of what the fitted model leaves out, namely the component of the game's cubic part orthogonal to the selected direction and the dividends of degree four and higher. The constant depends only on the design and the selected regressor.

The proposition concerns a class of models, and it makes a prediction that can be checked without any Shapley value. The two endpoint gradients of a single-index model are parallel, and on our models the median of ∣cos⁡(K0,K1)∣\lvert\cos(K_0,K_1)\rvert over targets is 0.9990.999 on IMDB-BINARY, 0.9860.986 on MUTAG, 0.9600.960 on NCI1 and 0.7800.780 on PROTEINS.

As you suggested, we used the exact games to check how well the selected direction matches the game's cubic part (Appendix F.8). We measure the alignment by the squared cosine between the centered Shapley vectors of the two. Within every dataset it is positively rank-correlated with the per-target gain over uniform weights, with Spearman correlations between 0.460.46 and 0.800.80 at g=8g=8, and in each dataset the median gain grows from the least to the most aligned third of the targets. With the thirds formed within each dataset and the targets of the four datasets pooled, the median gains are 0.990.99, 1.031.03 and 1.261.26, so the least aligned third shows no gain. At g=12g=12 the correlation is again positive within every dataset, and the most aligned third has median gain 1.191.19.

AuthorsOpenReview ↗

Response to Reviewer MeJr (2/3)

Total and sensitivity-specific gains. The revised abstract first states the gain over second-order PolySHAP and then reports that every matched control has higher error, 1.351.35 times ours when no direction is singled out and 1.551.55 times when the sensitivity weights are permuted across groups. Section 5.2 splits the total gain of 5.225.22 into a factor of 3.863.86 from keeping a regularized cubic block, which cubic ridge already achieves, and a factor of 1.351.35 from the selected direction with its own penalty. Without IMDB-BINARY, the total gain over second-order PolySHAP is 3.953.95, with interval [2.59,5.02][2.59, 5.02], of which cubic ridge accounts for a factor of 3.363.36 and the selected direction for 1.181.18 (Appendix F.1). The four control gains then lie between 1.141.14 and 1.291.29, and Section 5.2 reports this range.

An existing diagnostic accounts for the large separation on IMDB-BINARY. This dataset's groups differ most in size, and its sensitivity magnitudes grow almost linearly with group size, with a median over targets of 0.999950.99995 for the Pearson correlation across groups. Uniform and permuted weights ignore or misassign these sizes, and as Section 5.2 now states, group-size weights already account for most of our gain over uniform weights there, improving on them by a factor of 14.614.6. Beyond group size the sensitivities improve by a factor of 1.231.23 on IMDB-BINARY and by factors between 1.061.06 and 1.251.25 within every dataset, so the sensitivity-specific gain over group size is similar across the four datasets.

Total cost. In adjoint mode the two endpoint solves and the overhead of the regression over the quadratic estimator together cost about 2.782.78 coalition solves at g=8g=8, timed on the same machine, and the forward mode that we ran corresponds to about sixteen (Appendix D.3). The two modes compute the same endpoint gradient, agreeing to a relative difference of 9.1×10−109.1\times10^{-10} on all 480480 targets at g=8g=8, so the estimator can use either. The adjoint mode solves one system per endpoint at any gg, and on our graph-classification models the two endpoint solves cost about two cold-start coalition solves.

We therefore give each competing method two or four extra coalitions, two for the adjoint solves and four also allowing for the regression time (Appendix F.11). Our estimator stays ahead of second-order PolySHAP and OddSHAP with either number, in all 6060 model-seed-budget cells. Even with sixteen extra coalitions, the forward-mode count, it stays ahead of each in 5656 of the 6060 cells. Cubic ridge, uniform and group-size weights run the same regression as ours, so two extra coalitions put them at about equal total cost. Our gains over them then become 1.261.26, 1.211.21 and 1.101.10, with intervals that include one, and with the sixteen extra coalitions of the forward-mode count these three controls overtake our estimator. The most direct comparison at equal cost uses weights that need no solves at all. With weights from the game's own boundary marginals, read from the singleton and complement rows that our designs already contain, our estimator gains 1.361.36, 1.301.30 and 1.181.18 over the same three controls on exactly the same coalitions.

Mask extension. We agree that the selected direction is an inductive bias, and the revision states it as effect heredity. As you note, Theorem 1 constrains only rules that are unaffected by adding degree-two games. Once that invariance is given up, the game's own information can select a useful term, and the boundary-marginal weights above do exactly this. The boundary marginals v({i})−v(∅)v(\lbrace i\rbrace)-v(\varnothing) and v(N)−v(N∖{i})v(N)-v(N\setminus\lbrace i\rbrace) are the endpoint gradients of the game's own multilinear extension, so their magnitudes are determined by the Shapley game, and with weights from them the estimator is within four percent of the model-gradient version on MUTAG, PROTEINS and NCI1 at g=8g=8. The direction is then chosen from the singleton and complement rows, and its coefficient is still estimated from the residual of the whole sample. Model gradients remain the default because they work whether or not the design contains the 2g2g singleton and complement coalitions, with two solves at any gg, and on IMDB-BINARY they halve the error.

The empty-endpoint control. Weights built from the empty-mask gradient alone give 1.0061.006 times the balanced error of the two-endpoint rule at g=8g=8, with interval [0.991,1.034][0.991, 1.034], and 1.0071.007 times at g=12g=12 (Appendix F.5), and Section 5.2 now reports this in the main text. The agreement is consistent with Proposition B.4, since the two endpoint gradients of a single-index model are parallel. In practice, one adjoint solve at the empty mask gives nearly the same accuracy as two.

AuthorsOpenReview ↗

Response to Reviewer MeJr (3/3)

Scope of the theorems. The abstract and introduction now state Theorem 1 for rules that read only endpoint data and are unaffected by adding degree-two games, and the introduction states the exactness of Theorems 2 and 3 only for a quadratic game plus a multiple of the selected regressor. Outside that class, Appendix C.1 now shows that at our budgets every estimator that reads the sampled values and the endpoint data of a mask extension has unbounded error over all games, so a guarantee for an arbitrary game has to depend on the game, as the error bound of Corollary B.1 does. Theorem 2 holds for any supplied regressor, and Appendix C proves Theorem 3 for weights from model gradients and from boundary marginals alike.

Larger group counts and ControlSHAP. The revised paper adds both. The study with g=12g=12 groups reuses the twenty models, with 2424 explained graphs each, at five budgets from 9696 to 256256. The cubic model stays underdetermined at every budget, with at most 254254 interior rows for its 297297 free coefficients, and the complete game of 4,0964{,}096 coalitions gives the exact Shapley value (Appendices E.7 and F.15). The gain over second-order PolySHAP is 6.596.59, against 5.225.22 at g=8g=8. Our gains over the permutation, group-size and cubic-ridge controls are 1.231.23, 1.111.11 and 1.171.17, with intervals above one, and our gain over uniform weights is 1.101.10, with interval [0.97,1.70][0.97, 1.70], which includes one. The cubic matrices remain well conditioned (Table F.23). GCV leaves the coefficient of the selected regressor unshrunk in 8989 to 9595 percent of the fits. The median compact condition number of the penalized remaining block, over fits with a finite selected penalty, stays between 1515 and 154154 across the budgets. The per-target computation does not depend on the number of cubic terms (Appendix C.6).

Appendix F.14 shows that the partial-regression step is a control-variate correction with a least-squares coefficient. On designs where the quadratic stage is exact, a Taylor surrogate of degree at most two leaves the quadratic estimator unchanged, so we adapted ControlSHAP with the cubic Hermite interpolant of the same endpoint data. With a scalar coefficient its correction then moves the attribution along the same vector as our partial-regression step, the exact attribution of the selected regressor minus that of its quadratic fit, and only the coefficient differs. Given the same gradients and coalition budget, the best variant of ControlSHAP gains 3.253.25 over second-order PolySHAP and our partial regression alone gains 3.413.41. Adding the ridge on the remaining cubic directions, our full estimator gains 1.611.61 over the best ControlSHAP variant, with interval [1.45,1.70][1.45, 1.70]. If the coefficient is instead the one that the Hermite interpolant fixes from the endpoint data, the error is 1919 times that of second-order PolySHAP, so on these models calibrating the coefficient on coalition values is much more accurate. RegressionMSR, the implementation of regression-adjusted Monte Carlo in shapiq, has higher error than ours on each of the seven datasets of the paper.

Uncertainty and the scope of the comparisons. Section 5.1 now describes the four intervals as marginal. All four gains exceed one simultaneously in 98.998.9 percent of the bootstrap draws, a descriptive frequency that is not a classical pp-value. We agree that the OddSHAP comparison is secondary evidence, since it changes the sampler and the estimator jointly, and Appendix E.6 treats it as such. With our design drawn from a paired sampler uniform over coalition sizes, like OddSHAP's own, our estimator stays ahead in all 2020 model-seed cells at every budget of the g=8g=8 study. We also agree that four datasets limit how far the intervals generalize. The hierarchical bootstrap resamples datasets at its top level, but with four of them it can only give a coarse interval. Further evidence comes from three citation networks and five benchmark games of shapiq built on tabular, image and language models, and from the study with twelve groups, which repeats the primary comparison on the same models with a different grouping.

We hope that these answers address your questions, and we would be glad to discuss any of them further. Thank you again for the effort and expertise that you have devoted to our work in this review. The diagnostic that you suggested is now Appendix F.8, and your questions on cost and scope shaped Sections 5.2 and 5.5.

Reviewer_iZJeOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper considers the problem of estimating Shapley values. Shapley values are a property of a Boolean game v:2[g]→Rv: 2^{[g]} \to \mathbb{R}, i.e., ϕi(v)=∑S⊆[g]v(S∪{i})−v(S)g(g−1∣S∣).\phi_i(v) = \sum_{S \subseteq [g] } \frac{v(S \cup \{i\}) - v(S)}{g\binom{g-1}{|S|}}.

Of course, exactly computing Shapley values often (but not always) requires 2g2^g evaluations of vv so we must generally estimate them. Recent estimators learn a surrogate v^≈v\hat{v} \approx v on the samples then return ϕi(v^)\phi_i(\hat{v}) where, crucially, v^\hat{v} is structured enough that we can efficiently compute its Shapley values. The first methods (KernelSHAP, LeverageSHAP) in this line of work use a surrogate which is linear in the Harsanyi/Mobius basis. In the past year, PolySHAP has generalized this to fitting kk degree surrogates, e.g., quadratic, cubic, etc.

The current paper is interested in the regime where we have enough samples to fit the quadratic coefficients but not enough to fit the cubic coefficients. So they, quite naturally, ask how we should fit the cubic coefficients. Their answer is anything but natural:

  • they vaguely that the gradient of vv at the empty and full sets is useful. what they precisely say doesn't clear justify this stance, e.g., Theorem 1 establishes that the error in terms of the quadratic fit in some sense can be described with a single scalar
  • they approximate the gradients of the multilinear extension of vv with the gradients of the underlying machine learning model with respect to the continuous input masks
  • they then use these to get a coefficient wiw_i for each player ii and select a single degree-three functoin according to the weights wiwjwkw_i w_j w_k
  • they fit the linear and quadratic coefficients then fit the remaining residual on both the selected degree-three function and the remaining coefficients using different regularization parameters.

Finally, they use the fitted cubic as their surrogate and compare how it does relative to order-2 PolySHAP and some other non-SOTA heuristics on four datasets when g=8g=8.

Critical strengths

I think the problem of estimating Shapley values is important. I thought it was interesting to parse their Theorem 1.

Critical weaknesses

The paper is AI slop. Pretty much unreadable to me and I actively work in this space. Regardless of the content, I think this is grounds for rejection or, at the very least, requiring a complete human rewrite.

Unfortunately, the content is also poor. Their motivation comes from the PolySHAP shapley value estimator. PolySHAP fits polynomial regression of degree kk as a surrogate. As described in the original paper, the problem is two-fold: first, how do you select which higher order interactions to use? Second, how do you afford to fit all these higher order interactions? The current paper develops a sketchy heuristic for the first question and completely ignores the second.

I'll critique what this paper does in a moment. But I also want to add that the follow up work OddSHAP has a very successful solution to both the first and second questions. That is, they fit a tree ensemble, extract the highest-magnitude coefficients from the ensemble, and use these in their regression. The resulting algorithm gives, according to the authors, SOTA performance in the high budget regime. The current paper does not engage with this at all besides some AI phrase "our direction is instead read from the model before sampling" (similar AI hand-waving is done to avoid comparing to ControlSHAP and Regression MSR). Honestly, the argument that the fit comes from white-box access to the model is really a disadvantage of their method, and they certainly should compare to prior work in their experiments if they want to claim better performance.

Okay, so the paper ignores the prior work on this exact problem and instead makes a sequence of heuristic leaps which, to me, scream AI. Here are some glaring problems:

  • They want to use the gradient of the underlying model to fit a surrogate. They justify this with some technically interesting but tangential statements about an error metric DD for the distance between the full and empty set values and the integral approximation we'd get if the game were linear. Then they say okay let's not use the gradient of the multilinear extension they just analyzed, let's use the gradient of the model itself with respect to continuous inputs.
  • They then normalize the gradients to get a weight wiw_i for each player ii in a very convoluted and strange way. They then make the assumption (no justification anywhere that I could see) that a large magnitude cubic coefficient will have players with large wiw_i values. This justifies a selected direction that they add to the regression.
  • The authors (and I guess the AI model writing this) seem unaware that linear regression automatically fits directions to residual error. They do a multi-part linear regression: first, fit the low order terms, then get the residual then fit the cubic terms. They make the (strange) heuristic choice to have a regularization parameter for thier selected direction that differs from the other cubic terms. Note: it's very expensive to fit all cubic terms for the same reason they use to motivate the algorithm i.e., there are a lot of cubic terms.

For all the AI use writing the paper, I would've hoped they'd use AI to run some comprehensive experiments on lots of datasets where they compare to prior work. Unfortunately, they use only four datasets and do not compare to prior methods especially OddSHAP which solves the problem they motivate.

Questions for authors

Could you please rewrite the paper so it's readable?

Could you please compare to OddSHAP and other prior work implemented in the shapiq benchmark in your experiments?

Could you please expand your experiments beyond g=8g=8 and four datasets, and look at the time complexity of your method.

3 comments
AuthorsOpenReview ↗

Response to Reviewer iZJe (1/3)

Thank you for your review and for pointing us to the shapiq benchmark. We agree that some parts of the submitted version were not as clear as they should have been, and we have substantially rewritten the introduction and Sections 2 to 4. In response to your requests, we have also extended the comparison with OddSHAP, added the other approximators of shapiq, five of its benchmark games and a study with twelve groups, and analyzed the time complexity. New and substantively changed text is marked in red in the revised paper, and the theorems are unchanged in content.

Readability. The introduction now starts from the problem, Section 2 says in plain words what Theorem 1 shows, and Section 4 goes through the estimator step by step, with the algorithm in the main text. In brief, when each coalition value costs an equilibrium solve, as for the implicit graph neural networks we explain, the affordable number of sampled coalitions falls short of the number of free coefficients of a cubic surrogate, at most 7878 coalitions against 9191 coefficients at g=8g=8. The sampled values then determine the Shapley value of every quadratic game but not of every cubic one, so going beyond pairwise interactions takes a structural choice. Second-order PolySHAP sets the cubic part to zero, cubic ridge shrinks all cubic coefficients alike, and OddSHAP keeps the sparse odd interactions selected by a proxy trained on the sample. We single out one cubic direction, a weighted sum of all triples whose weights come from first-order magnitudes, and shrink the other cubic directions by ridge.

OddSHAP. At the same coalition budget our estimator has lower error than OddSHAP for every trained model at every budget, in all 6060 model-seed-budget cells at g=8g=8, all 100100 at g=12g=12 and all 2727 on the citation networks. OddSHAP is strongest at g=12g=12 with budgets of 160160 and more, which are large enough for it to add higher-order odd interactions. There it beats second-order PolySHAP on every dataset and budget, yet its error is still 5.355.35 times ours. We run OddSHAP in the configuration that gave it its lowest error (Appendix E.6). At g=8g=8 we also draw our design from a paired sampler uniform over coalition sizes, like OddSHAP's own, and our estimator again has lower error in every cell. The submitted version had a short comparison with OddSHAP at the end of Section 5.3. The revised paper gives external baselines their own Section 5.4.

Other approximators in shapiq. By the paper's main metric, the balanced relative error of Equation (13), every non-adaptive approximator in shapiq that runs at our budgets has higher error than ours on each of the seven datasets, and on the four graph-classification datasets at g=12g=12 as well. They include KernelSHAP, kADD-SHAP, PolySHAP, RegressionMSR, ProxySHAP, ProxySPEX, SVARM, and permutation, stratified and Owen sampling. The closest are paired KernelSHAP and paired second-order PolySHAP, which is our quadratic estimator, both with at least 3.383.38 times our error within a dataset at g=8g=8. SPEX needs at least 264264 coalition queries, more than any of our budgets and, at g=8g=8, more than the 256256 coalitions of the complete game.

On five benchmark games of shapiq with between 88 and 1414 groups, built on a neural regressor, an XGBoost regressor, a random forest, a vision transformer and a language model, only coalition values are available. There we run our estimator with weights computed from coalition values alone, the boundary marginals described below. It is more accurate than OddSHAP and than every polynomial-regression estimator, from KernelSHAP to third-order PolySHAP, on every game. Two methods that fit a gradient-boosted tree surrogate to the sampled values are more accurate on three of the games, RegressionMSR on Adult and California Housing and ProxySHAP on IMDb, while on the seven datasets above both have higher error than ours.

ControlSHAP and RegressionMSR. The best variant of ControlSHAP that we could build from the same endpoint data and coalition budget has 1.611.61 times our error (Appendix F.14). Its surrogate is the cubic Hermite interpolant of the endpoint values and gradients. A Taylor surrogate of degree at most two would change nothing, because on our designs the quadratic stage already returns the exact Shapley value of every degree-two game. RegressionMSR is among the shapiq approximators compared above, with higher error than ours on each of the seven datasets.

AuthorsOpenReview ↗

Response to Reviewer iZJe (2/3)

White-box access and Theorem 1. Our estimator does not need white-box access. Its weights can come from the boundary marginals v({i})−v(∅)v(\lbrace i\rbrace)-v(\varnothing) and v(N)−v(N∖{i})v(N)-v(N\setminus\lbrace i\rbrace), the endpoint gradients of the game's own multilinear extension, which any design containing each singleton and its complement provides. With these weights the errors at g=8g=8 are within four percent of those with model gradients on MUTAG, PROTEINS and NCI1, and we use this coalition-only version on the benchmark games above. Where the model's gradients are available we use them by default. They need no singleton or complement coalitions, take about as much computation as two coalition evaluations for an implicit model, and halve the error on IMDB-BINARY.

Theorem 1 shows that a game's endpoint data alone cannot determine its cubic direction, so the choice needs an assumption. The quadratic terms are fitted anyway, so adding a degree-two game should not change the chosen cubic direction. Once degree-two games are factored out in this way, the endpoint data retain only the scalar DD, the error of the trapezoidal rule for the integral of the directional derivative along the diagonal. A rule that ignores degree-two games therefore depends on the game only through DD, so for g≥4g\ge4 it cannot return the cubic direction of every game, and if it treats the groups alike it can return only the symmetric direction e3e_3, which our uniform-weight control uses.

The weights. The assumption we make is effect heredity, the principle of experimental design by which an interaction tends to matter only when its main effects do (Hamada and Wu, 1992; Chipman, 1996). We take the magnitudes of the endpoint gradients as the sizes of the main effects and give each triple the product of its members' weights, as in the prior of Joseph (2006), which ties the scale of an interaction to the product of the scales of its main effects (Sections 1 and 3.2). We normalize the magnitudes κi=(K0i2+K1i2)1/2\kappa_i=(K_{0i}^2+K_{1i}^2)^{1/2} of the two endpoint gradients and mix in a uniform share ε\varepsilon, so that the weights do not depend on the scale of the gradients and every triple has a positive coefficient.

The new Appendix B.4 proves a case in which the assumption holds exactly. Take a single-index model, where the mask enters only through a weighted sum with positive weights and a smooth link whose derivative is nonzero at one end at least. There the cubic dividend of each triple is the product of its three weights times an average of the link's third derivative, and the normalized endpoint magnitudes recover the normalized weights. The direction built from these magnitudes, before the uniform share is mixed in, therefore coincides with the game's cubic part when the third derivative is a nonzero constant. When it keeps one sign with absolute value between L>0L\gt0 and UU, the sine of the angle between the two is at most (U−L)/(U+L)(U-L)/(U+L). For every game, on designs where the quadratic stage is exact and the selected regressor has a nonzero residual, Corollary B.1 bounds the error of the unpenalized partial regression by a constant, fixed by the design and the selected regressor, times the combined size of the component of the game's cubic part orthogonal to the selected direction and the dividends of degree four and higher.

On the exact games we tested the assumption directly (Appendix F.8). Within every dataset, the alignment of the selected direction with the game's cubic part, measured by the squared cosine between their centered Shapley vectors, is positively rank-correlated with the error of uniform weights divided by ours, with Spearman correlations between 0.460.46 and 0.800.80 at g=8g=8. In the matched controls, permuting the weights among the groups gives 1.551.55 times our error, and uniform and group-size weights give 1.291.29 and 1.171.17 times.

AuthorsOpenReview ↗

Response to Reviewer iZJe (3/3)

Regression on residuals and the separate penalty. You are right that regressing the residual of the quadratic fit on that of the selected regressor gives the same coefficient and attribution as the joint efficiency-constrained regression on the quadratic terms and the selected regressor. This is the Frisch–Waugh–Lovell identity, which Theorem 2 extends to the efficiency constraint and to rank-deficient designs, and the paper now names it. We write the fit in this form because it gives the coefficient and the attribution in closed form, from which we prove exactness and efficiency.

The separate penalty lets the selected direction be fitted by least squares while the other cubic directions are shrunk. Generalized cross-validation leaves the coefficient of the selected regressor unshrunk in most fits, 7777 to 9595 percent on each dataset at g=8g=8 and 8989 to 9595 percent at each budget at g=12g=12 (Appendix F.2 and Table F.23). One ridge penalty on the whole residualized cubic space, the selected direction included, is our cubic-ridge control, and its error is 1.351.35 times ours. The smaller penalty on the selected regressor corresponds to a larger prior variance for its coefficient.

Fitting all cubic terms. The estimator keeps every cubic term in the model without needing as many coalitions as there are cubic terms, and its computation per explained instance does not depend on their number. The selected direction is fitted by partial regression and the remaining cubic directions are shrunk by generalized ridge (Section 4.3 and Algorithm 1), which works whenever the sampled coalitions outnumber the free coefficients of the quadratic surrogate. On one CPU thread the regression takes, in the median over designs at each budget, between 0.280.28 and 1.161.16 ms per instance at g=8g=8 and between 1.181.18 and 2.322.32 ms at g=12g=12, at most about the time of one cold-start coalition solve of our implicit models on the same machine. The reason is that the ridge fit can be computed in the space of the mm sampled coalitions, since it uses the cubic columns only through an m×mm\times m and a g×mg\times m matrix whose entries have closed forms. After a setup once per design, polynomial in mm and gg, each explained instance costs O(m3)O(m^3) operations, whatever the number of cubic terms (Appendix C.6 gives the full counts). The regression time does not depend on the explained model, while the time of a coalition solve grows with it.

More datasets and twelve groups. Besides the four graph-classification datasets, the paper evaluates on three citation networks, Cora, CiteSeer and PubMed, and the revision adds the five benchmark games above. We repeated the primary study with g=12g=12 groups on the same twenty models, at budgets from 9696 to 256256, where the complete game of 4,0964{,}096 coalitions still gives the exact Shapley value. There second-order PolySHAP has 6.596.59 times our error, against 5.225.22 at g=8g=8. Permuting the weights among the groups gives 1.231.23 times our error, and our estimator beats OddSHAP for every trained model at every budget.

We hope that the revised paper and these answers make clear what the paper does and how it compares with prior work. We would be glad to clarify any passage that you still find unclear. Thank you again for your time, and for the pointer to the shapiq benchmark, which made the comparison with prior work much more complete.

Reviewer_Rd9uOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates Shapley value estimation under limited coalition-query budgets, addressing the challenges of computationally expensive equilibrium solves for coalition evaluations in implicit graph neural networks and the difficulty of estimating higher-order interactions from insufficient observations. The authors propose a sensitivity-informed cubic Shapley regression framework that constructs a weighted cubic polynomial basis function using endpoint gradients at the empty and full coalitions. This basis function is incorporated into an efficiency-constrained quadratic regression model, while generalized ridge regularization is employed to estimate the remaining cubic interaction contributions. The main contributions of this paper include a theoretical characterization of endpoint values and gradient information, an efficient regression approach incorporating a selected cubic interaction direction, and theoretical guarantees of attribution efficiency, permutation equivariance, and exact recovery under specified conditions. Comparative experiments on four graph-classification datasets and three citation networks demonstrate that the proposed method improves Shapley attribution accuracy under limited query budgets, supporting the effectiveness of endpoint sensitivity information in guiding higher-order interaction modeling.

Critical strengths
  1. Innovative sensitivity-guided higher-order interaction modeling. The paper presents a valuable approach to addressing the underdetermined nature of higher-order Shapley regression under limited coalition-query budgets. By leveraging endpoint gradients to select a weighted cubic polynomial basis function, the proposed method incorporates model derivative information into polynomial Shapley regression without requiring additional coalition evaluations. The theoretical characterization of endpoint information and the exact-recovery guarantees under specific conditions further strengthen the theoretical contribution. This provides a promising direction for improving Shapley attribution accuracy in scenarios where coalition evaluations are computationally expensive.
  2. Well-designed comparative experiments with strong empirical support. The experiments are conducted on four graph-classification datasets (MUTAG, PROTEINS, NCI1, and IMDB-BINARY), involving 20 independently trained implicit graph neural networks and three coalition-query budgets (48, 64, and 80). Additional node-level explanation experiments are performed on three citation networks: Cora, CiteSeer, and PubMed. The authors establish several control baselines, including uniform weights, node-group-size weights, permuted sensitivity weights, and cubic ridge regression without a supplied cubic basis function. By maintaining identical coalition samples and observed values, these matched comparisons help isolate the contribution of the cubic direction selected by endpoint sensitivities. Under the aggregated squared attribution error metric, the permuted-sensitivity baseline yields 1.55 times the error of the proposed method, with a 95% hierarchical bootstrap confidence interval of [1.14, 4.37]. Compared with second-order PolySHAP, the proposed method achieves a 5.22-fold improvement in the reported error ratio. Furthermore, the node-level experiments employ nearly equal-sized feature groups, partially ruling out group size as an explanation for the observed improvements. These results provide targeted empirical evidence supporting the effectiveness of endpoint sensitivity information for guiding higher-order interaction modeling.
Critical weaknesses
  1. Insufficient theoretical justification for the relationship between endpoint sensitivities and higher-order Shapley interactions.The proposed framework constructs a weighted cubic polynomial basis function using endpoint gradients, but the theoretical justification for this design choice remains insufficient. In Section 3.1, Equations (4)–(5) determine cubic interaction weights through products of normalized endpoint sensitivity magnitudes. However, the authors do not adequately explain why these first-order sensitivities can reliably identify the cubic interaction directions most relevant to Shapley attribution. More importantly, as discussed in Section 2.2, different differentiable mask extensions may produce different endpoint gradients even when the underlying coalition game remains exactly the same. This indicates that the selected cubic interaction direction may depend on the specific form of the continuous mask extension rather than being determined solely by the underlying attribution problem. Theorem 1 characterizes the endpoint information contained in the multilinear extension, while Theorems 2 and 3 provide exact-recovery guarantees only under restrictive conditions, particularly when the target coalition game belongs to the function space spanned by quadratic terms and the selected cubic direction. These theoretical results do not establish that the sensitivity-guided construction can robustly identify appropriate cubic interaction directions for arbitrary coalition games. Furthermore, the manuscript lacks theoretical error bounds and robustness analyses that directly link endpoint sensitivities to attribution accuracy. This limitation substantially weakens the general applicability of the paper's central methodological claims.
  2. Insufficient computational-cost comparisons and limited validation of broader applicability. The existing experimental comparisons do not sufficiently demonstrate the claimed computational advantages of the proposed method under equivalent computational resource budgets. Specifically, in Section 5.3 and Appendix E.6, the authors compare their method with OddSHAP using the same number of Boolean coalition evaluations. However, the proposed method incurs additional computational overhead from endpoint gradient estimation. Appendix D.3 reports that, under the forward-mode implementation employed in the experiments, the median cost of computing endpoint gradients is equivalent to approximately 15.5 cold-start coalition solves. Although an adjoint-mode implementation can reduce this overhead to approximately 2.07 coalition solves, these results still indicate that equal coalition-query budgets do not necessarily imply comparable total computational costs. Moreover, the proposed method and OddSHAP employ their respective native sampling strategies in the comparative experiments, making it difficult to isolate the performance gains attributable specifically to the estimator under a strictly matched experimental protocol. In addition, all experiments are conducted with only eight input groups, leaving the effectiveness of the proposed approach under larger group counts and more complex interaction structures insufficiently validated. Given that reducing computational costs under limited budgets is one of the central motivations of this work, the absence of rigorously cost-matched comparisons and comprehensive scalability evaluations substantially weakens the evidence supporting the practical advantages of the proposed method.
Questions for authors
  1. Theoretical justification and robustness of sensitivity-guided cubic direction selection. In Equations (4)–(5), the cubic basis function is constructed using products of normalized endpoint sensitivity magnitudes. Could the authors provide a more rigorous theoretical justification for why these first-order sensitivities can identify the third-order interaction directions most relevant to Shapley attribution? Given that different differentiable mask extensions may produce different endpoint gradients while preserving the same underlying coalition game, could the authors clarify under what conditions the selected cubic direction remains stable, or provide experimental evidence demonstrating that such gradient variations do not significantly affect attribution accuracy?
  2. Fairness of computational-cost comparisons. Appendix D.3 reports that endpoint gradient computation incurs additional computational overhead equivalent to approximately 15.5 cold-start coalition solves under the forward-mode implementation used in the experiments, while an adjoint-mode implementation reduces this overhead to approximately 2.07 coalition solves. Could the authors clarify whether the proposed method maintains its reported performance advantages over OddSHAP when both methods are evaluated under equivalent total computational budgets, including the cost of gradient computation? Furthermore, given that the two methods employ different coalition sampling strategies, to what extent can the observed performance differences be attributed to the sampling strategies themselves?
  3. Scalability to larger input-group configurations. The existing experiments are conducted exclusively with eight input groups. Could the authors clarify how the proposed method performs as the number of input groups increases, particularly in terms of computational complexity, stability of the selected cubic direction, and attribution accuracy? Experimental results involving larger input-group configurations would help determine whether the reported performance improvements generalize beyond the specific settings investigated in the manuscript.
3 comments
AuthorsOpenReview ↗

Response to Reviewer Rd9u (1/3)

Thank you for your careful review and for your positive assessment of the clarity of the paper and of the matched controls. You asked about the theory behind the weights, about cost and about larger numbers of groups. In response, the revision adds a theoretical justification of the weights with an error bound and a stability result, comparisons at equal total cost and with a matched sampler, and a study with twelve groups. New and substantively changed text is marked in red in the revised paper, and the theorems are unchanged in content.

Why first-order sensitivities indicate the cubic direction. Theorem 1 shows that the choice of a cubic direction needs an assumption, and effect heredity is the assumption we make. The regression already fits every degree-two term, so a rule that looks for the cubic direction should not change when a degree-two game is added. Once such games are set aside, a game's own endpoint values and gradients reduce to a single number. A rule of this kind therefore depends on the game only through that number, so for g≥4g\ge4 it cannot return the cubic direction of every game, and if it treats the groups alike it can return only the symmetric direction. To match the cubic part of a particular game, a rule must use information that this reduction discards. We use the magnitudes of the individual endpoint sensitivities, which distinguish the groups, and we rely on effect heredity, the principle of experimental design that an interaction tends to matter only when its main effects do (Hamada and Wu, 1992; Chipman, 1996). The revised paper grounds the product weights of Equations (4) and (5) in this principle and in the prior of Joseph (2006), which ties the scale of an interaction to the product of the scales of its main effects (Sections 1 and 3.2).

The link between the endpoint sensitivities and attribution accuracy is an error bound (new Appendix B.4). Write h3(v)h_3(v) for the vector of cubic dividends of a game vv, ϑ\vartheta for the angle between it and the selected direction, and v≥4v_{\ge4} for the dividends of degree four and higher. On designs where the quadratic stage is exact and the selected regressor qq has a nonzero residual, Corollary B.1 shows for every game that the unpenalized partial regression ϕ^q\hat\phi_q satisfies

∥ϕ^q(v)−ϕ(v)∥2≤C(∥h3(v)∥22sin⁡2ϑ+∥v≥4∥22)1/2,\lVert\hat\phi_q(v)-\phi(v)\rVert_2\le C\left(\lVert h_3(v)\rVert_2^2\sin^2\vartheta+\lVert v_{\ge4}\rVert_2^2\right)^{1/2},

with a constant CC that depends only on the design and on qq. The exact recovery of Theorem 2 is the case ϑ=0\vartheta=0 and v≥4=0v_{\ge4}=0, and the bound grows continuously as the selected direction turns away from the game's cubic part.

Proposition B.4 shows when the angle is small. In a single-index model, where the mask enters only through a weighted sum with positive weights and a smooth link whose derivative is nonzero at one end at least, the direction built from the endpoint magnitudes, before the small uniform share is mixed in, coincides with the game's cubic part when the link's third derivative is a nonzero constant. When that derivative keeps one sign with absolute value between L>0L\gt0 and UU, the sine of the angle between the two is at most (U−L)/(U+L)(U-L)/(U+L). The reason is that the normalized endpoint magnitudes recover the normalized weights of the sum, and the cubic dividend of each triple is the product of its three weights times an average of the third derivative. The higher derivatives of the link bound v≥4v_{\ge4}.

Exactness is confined to a class of games because at these budgets no estimator can be accurate for every game. On a design that does not determine the Shapley value of every cubic game, as none of ours does at the three budgets of our primary study, there is a cubic game zz that vanishes on every sampled coalition and on the empty and full coalitions and has ϕ(z)≠0\phi(z)\neq0. Appendix C.1 now shows that for every game vv with a mask extension and every real tt, the game v+tzv+tz has a mask extension with the same endpoint values and gradients. It also has the same sampled values, while its Shapley value is ϕ(v)+tϕ(z)\phi(v)+t\phi(z). Every estimator that reads the sampled values and the endpoint data of a mask extension therefore errs by at least ∣t∣∥ϕ(z)∥2\lvert t\rvert\lVert\phi(z)\rVert_2 on one of the games v±tzv\pm tz, for every tt. For arbitrary games the appropriate guarantee is thus an error bound for each game, which Corollary B.1 provides.

AuthorsOpenReview ↗

Response to Reviewer Rd9u (2/3)

The experiments show that the gain depends on which group receives which weight and grows with the alignment of the selected direction. The permutation control keeps all eight weights but reassigns them among the groups, and its error is 1.551.55 times ours. On the exact games we measured the alignment as the squared cosine between the centered Shapley vectors of the selected direction and of the game's cubic part (Appendix F.8). Within every dataset it is positively rank-correlated with the gain over uniform weights, with Spearman correlations between 0.460.46 and 0.800.80 at g=8g=8. When the targets of each dataset are split into thirds by alignment and pooled, the median gain rises from 0.990.99 in the least aligned third to 1.261.26 in the most aligned.

Dependence on the mask extension. On three of the four datasets, two different mask extensions of the same games give nearly the same accuracy, and on the fourth the model's own gradients are the better source. Besides the explained model's extension, every game has its own multilinear extension, whose endpoint gradients are the boundary marginals v({i})−v(∅)v(\lbrace i\rbrace)-v(\varnothing) and v(N)−v(N∖{i})v(N)-v(N\setminus\lbrace i\rbrace), available whenever the design contains each singleton and its complement. We run the estimator with these weights as well (Sections 2.2 and 5.5). At g=8g=8 the errors with the two sources differ by under four percent on MUTAG, PROTEINS and NCI1, even though on PROTEINS the two selected directions differ markedly, with a median sine of 0.320.32 between them. On IMDB-BINARY, model gradients halve the error. Within the model's extension, which endpoint the weights read hardly matters, since weights from the empty-mask gradient alone change the error by a factor of 1.0061.006.

The selected direction also depends continuously on the gradients (Appendix B.5). Let ρ\rho be the change of the endpoint gradients, summed over the groups and divided by ∑iκi\sum_i\kappa_i. Then the weights of Equation (4) move by at most 2(1−ε)ρ2(1-\varepsilon)\rho in ℓ1\ell_1 norm, and the selected cubic direction turns by an angle of at most (1−ε)ρ/w‾(1-\varepsilon)\rho/\underline w, where w‾\underline w is the smallest of the weights before and after the change, which the uniform share keeps at least ε/g\varepsilon/g. This covers small perturbations, and for a change as large as a different extension the comparison above is the direct evidence.

Cost at equal total budgets and the sampler. Our estimator keeps its advantage over OddSHAP and second-order PolySHAP when they receive extra coalitions for the cost of the gradients. We give them two extra coalitions, matching the two endpoint solves, or four, also allowing for the regression time, and with either number our estimator has lower error than both in all 6060 model-seed-budget cells (Appendix F.11). The count of two comes from adjoint mode. Forward and adjoint modes compute the same endpoint gradient, agreeing to a relative difference of 9.1×10−109.1\times10^{-10} on all 480480 targets at g=8g=8, and in adjoint mode the two endpoint solves cost about two cold-start coalition solves at any gg. Timed on the same machine at g=8g=8, these solves and the extra regression time over the quadratic estimator together take about 2.782.78 coalition solves (Appendix D.3). Counted in forward mode, which our experiments ran and which corresponds to about sixteen extra coalitions, our estimator still has lower error than each of them in 5656 of the 6060 cells.

The version with boundary-marginal weights needs no solves at all. On exactly the same coalitions as cubic ridge, uniform and group-size weights, it gains between 1.181.18 and 1.361.36 over them at g=8g=8, with intervals above one against cubic ridge and uniform weights (Appendix F.11), so the gain from choosing the direction does not rest on the extra cost of the gradients.

Model gradients keep two advantages over boundary marginals. Their two adjoint solves suffice at any gg, whereas boundary marginals require the design to reserve 2g2g singleton and complement coalitions. Model gradients also halve the error on IMDB-BINARY.

AuthorsOpenReview ↗

Response to Reviewer Rd9u (3/3)

To separate the sampler from the estimator, we kept OddSHAP in the configuration that gave it its lowest error and drew our design from a paired sampler that is uniform over coalition sizes, like OddSHAP's own (Appendix F.6). The swap matters mainly at B=48B=48, where OddSHAP's error on MUTAG is 3.423.42 times ours instead of 5.615.61 times, and it changes little at the larger budgets. Our estimator keeps the lower error in all 2020 model-seed cells at every budget. Our sampler helps at the smallest budget, but the advantage does not depend on it.

Larger numbers of groups. We repeated the primary study with g=12g=12 groups. All five budgets from 9696 to 256256 still leave the cubic model underdetermined, and the complete game of 4,0964{,}096 coalitions still gives the exact Shapley value (Appendices E.7 and F.15). The gain over second-order PolySHAP grows from 5.225.22 at g=8g=8 to 6.596.59, and all four matched controls again have higher error than ours in the four-dataset aggregate, with gains between 1.101.10 and 1.231.23. OddSHAP is strongest in this study at budgets of 160160 and more, where it has room for higher-order odd interactions and beats second-order PolySHAP on every dataset and budget, and even there its error is 5.355.35 times ours. Our estimator has lower error than OddSHAP in all 100100 model-seed-budget cells, and every approximator of shapiq in the comparison has higher error than ours on every dataset. For other interaction structures, we evaluate on five benchmark games of shapiq, built on tabular, image and language models with between 88 and 1414 groups, where our estimator with boundary-marginal weights is more accurate than second-order PolySHAP and OddSHAP on every game.

The cost per target is set by the budget and does not grow with the number of cubic terms. The ridge fit can be computed in the space of the mm sampled coalitions (Appendix C.6), so after a setup once per design, each target costs O(m3)O(m^3) operations. At g=12g=12 the regression takes between 1.181.18 and 2.322.32 ms per target on one CPU thread, in the median over designs, about the time of one cold-start coalition solve of our implicit models, and the endpoint gradients still take two adjoint solves.

The selected direction remains informative at g=12g=12, and the accuracy is insensitive to the source of the weights. The alignment of the direction with the game's cubic part is again positively rank-correlated with the gain within every dataset, with median gain 1.191.19 on the most aligned third of the targets. In the four-dataset aggregate the error changes by under one percent with weights from the empty-mask gradient alone and by under two percent with boundary-marginal weights.

We hope that these answers address your questions, and we would be glad to discuss any of them further. Thank you again for the effort and expertise that you have devoted to our work in this review. Your questions on cost and scale led to the new Section 5.5, and the paper is stronger for them.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revision

We thank the reviewers for their careful reading and their questions. We have uploaded a revised paper, with new and substantively changed text marked in red, and the anonymous repository linked in the paper now also contains the code and the results of the new experiments. At the request of Reviewers iZJe and MeJr, we have substantially rewritten the introduction and Sections 2 to 4 to make the paper easier to follow. We have also added the theoretical justification, the comparisons and the studies of cost and scale that the reviews asked for. The three theorems are unchanged in content.

Presentation (Reviewers iZJe and MeJr). The introduction now explains why our budgets determine the Shapley value of every quadratic game but not of every cubic one, and which structural assumption each existing estimator makes. Section 2 explains Theorem 1 in plain words. Section 4 describes the estimator step by step, with the algorithm in the main text, and relates Theorem 2 to the Frisch–Waugh–Lovell identity. At the request of Reviewer MeJr, the abstract and introduction now state the restrictions of the theorems as carefully as the formal sections do.

Why first-order sensitivities indicate the cubic direction (Reviewers Rd9u, MeJr and iZJe). The revision states the assumption behind the product weights, proves a case in which it holds exactly and tests it. Section 3.2 grounds the weights in the effect-heredity principle of experimental design. The new Appendix B.4 proves that in single-index models the selected direction lies within an explicit angle of the game's cubic part (Proposition B.4) and bounds the error of the partial regression for every game in terms of this angle and of the dividends of degree four and higher (Corollary B.1). The new Appendix B.5 shows that the selected direction depends continuously on the gradients. Appendix C.1 now shows that at our budgets no estimator that reads the sampled values and the endpoint gradients can be accurate for every game, so the guarantees take the form of exactness on a class of games and an error bound outside it. The new Appendix F.8 shows that on our exact games the gain over uniform weights grows with the alignment of the selected direction.

Experiments (Reviewers Rd9u, iZJe and MeJr). The comparison with OddSHAP, which the submitted version gave at the end of Section 5.3, now has its own Section 5.4 and extends to the non-adaptive approximators of shapiq, to the three citation networks, to twelve groups and to five benchmark games of shapiq. Our estimator has lower error than OddSHAP for every trained graph model at every budget, and lower error than every shapiq approximator in the comparison on each of the seven datasets. The new Section 5.5 compares at equal total cost, introduces a version of the estimator that takes its weights from coalition values alone, and repeats the primary study with twelve groups. Section 5.2 separates the sensitivity-specific gains from the total gain. Appendix F.14 compares our estimator with ControlSHAP adapted to our endpoint gradients, and Appendix C.6 shows that the cost per explained instance does not depend on the number of cubic terms.

Equation (7) of the submitted version has moved to Appendix B, so Equations (8) to (14) are now (7) to (13). The algorithm of the former Appendix C.6 has become Algorithm 1 in Section 4.4, and Appendix C.6 now contains the computation of the ridge fit in the space of the sampled coalitions. The remaining changes keep the rest of the paper consistent with these revisions or adjust wording to improve clarity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.