- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the computation of Shapley values on so-called product games, which are games where the coalition value is expressed as a product over fixed individual player contributions (Def 1). The paper establishes an integral representation using the Owen's multilinear representation of the Shapley value, which then involves an integral over a -order polynomial (Prop 1). This integral can be solved via Gauss-Legendre quadrature via evaluations, and approximately with less, for which an error bound is given (Prop 2). Using the error bound, the authors establish a certificate for an -close approximation (Prop 3), and establish a sequential and parallel computation schemes (Prop 4). The authors then proceed to identify product games in multiplicative models (Def 2), and demonstrate that baseline and interventional value functions in these models are defining weighted sum of product games (Prop 5), which can be solved the same way through linearity of Shapley values (Prop 6). The multiplicative models includes a diverse range of models (Table 1). Finally, the method is evaluated on product-kernel methods and other applications against exact numeration, and the benefits of -approximated solutions are highlighted, which further increase the runtime. Lastly, the scalability is illustrated on a high-dimensional Cox model.
Critical strengths
- Scope: The paper is written very general using the broad class of product games, which extends exact Shapley value computation to a diverse range of (multiplicative) models, including product-kernel methods, trees, and Cox models, which enables new applications such as survival analysis. Moreover, the value functions are clearly linked to the model predictions and abstractly viewed as instances of product games or weighted product games. This is often overlooked in related literature e.g. on TreeSHAP, and beneficial for future research in this domain.
- Approximation guarantee: In contrast to concurrent/previous methods, the authors provide a guaranteed -approximation of the Shapley values using fewer evaluation points of the integral representation
Critical weaknesses
- Limited technical depth and novelty: The tools used were mostly known and there is limited novelty in each separate contribution. TreeGrad and Quadrature SHAP have proposed similar methods via Gauss-Legendre integration. Its exact computation and approximation guarantee (Prop 2) follows directly from previous results. The bound appears to be novel (Prop 3) and most significant novel contribution. The results on multiplicative models and representation of value functions as weighted product games (Prop 5, Prop 6) are also modest. The overall novelty of the approach is to combine these results to solve the computation of Shapley values for new types of models. I think, though, that the authors have presented their approach in a transparent way, which is sufficiently linking to prior discoveries.
- Limited discussion on optimal complexity and distinction between product games and special case of tree-based product games: The product game formulation is universal and includes the most-relevant practical application, namely tree-based models and TreeSHAP. However, the underlying structure of a tree-based model is richer in its presentation, since several paths (products) are shared between leaves. It seems that this underlying structure is crucial in the computation of the trees. I think it would be beneficial to spend additional time on the special case of tree-based games (as a special case of product games), and outline the algorithmic details that are required to solve this computation more efficiently than simply treating it as weighted sum of isolated product games. Related to this is a discussion on a lower bound of the complexity for such game structures, separately for tree-based games and product games (see questions below). For future research, it would be beneficial to know if lower complexities can be achieved. While the current quadrature approach is known to be optimal for solving the integral, it remains unclear if there could be faster ways for computing Shapley values in these types of structures. A separate discussion on computational complexities and possible lower bounds would be helpful for future research, and are currently missing. This extended discussion would also strengthen the theoretical contribution mentioned in W1.
Questions for authors
- considering W1, an extension of the theoretical contribution would be to additionally provide the Möbius and Fourier spectrum of the given product game value functions, can you state these, and contrast tree-based product games with other product games?
- considering W1, could the newly established computations of Shapley value be used to enrich benchmarks of Shapley value approximators? Do these model types exhibit different structure than existing benchmarks, which are often tree based?
- considering W2 above, where does the implemented QuadraSHAP approach for tree-based models exploit the tree structure explicitly? What are the implications for its computation on trees? Is it really just an average over several weighted product games as described in the theoretical result?
- considering W2, does there exist a lower complexity-bound that is achievable for general product games, which is lower than QuadraSHAP's ? If not, why not? If yes, why is it less preferable or stable than QuadraSHAP's approach? Is there any sort of "optimal" complexity for these types of games?
3 comments
followup
Dear Reviewer hzeg,
Thank you again for your review and your positive assessment of the paper. As the discussion period closes on November 18, we would like to ask whether our response has addressed your concerns. We would be glad to clarify any remaining points.
I thank the authors for their effort to address my concerns. While I still believe that the technical depth is not too strong, I believe that this paper should be accepted and will increase my score accordingly.
response
We thank the reviewer for the careful assessment and for recognizing the scope of the product-game framework and its approximation guarantees. Our responses to the concerns are provided below.
W1. Technical contribution. Proposition 2 uses the standard Gauss–Legendre error bound. Proposition 3 turns this bound into a sufficient node budget computed directly from the factors of the product game. Specifically, the Bernstein-ellipse bound in Proposition 2 depends on the maximum of a polynomial of degree d−1 over an ellipse, a quantity that is not readily available. Lemma 1 in Appendix C.1 bounds this maximum using two quantities computed from the factor table in O(d) time: the absolute scale ∣ui−1∣Πi and the total relative variation Λi. The bound holds for every admissible ellipse parameter, which we optimize by solving a scalar equation. This yields a node budget for a prescribed accuracy before quadrature evaluation. Appendix C presents the full procedure, including its extension to weighted sums of product games. This factor-based budget for general product games distinguishes our contribution from the cited tree quadrature methods, with a significant impact in practice: we can compute ϵ-exact Shapley values for problems with tens of thousands of features in a fraction of a second. Identifying product structure in different value functions of several well-known models also extends the practical applicability of QuadraSHAP.
W2 and Q3. Tree structure. We agree that tree structure enables more efficient computation by reusing work along paths shared by multiple leaves. We derive this tree-specific computation in Appendix F. Since it is closely related to the computations in TreeGrad-Shap and Quadrature-TreeSHAP, we present the derivation in the appendix and keep the main text focused on the general framework. We have added an explicit reference to Appendix F in Section 4.
In Appendix G.5, we compare QuadraSHAP with existing tree explainers on CPU and GPU. On the GPU benchmarks, QuadraSHAP is faster than Quadrature-TreeSHAP in 17 of 18 settings. Both use GL quadrature with the same asymptotic tree complexity, so the timing differences reflect implementation choices, including GPU kernel development.
Q1. Möbius and Fourier spectra. We agree that the Möbius and Fourier spectra provide important ways to characterize interactions among features. In Appendix D, we derive closed-form expressions for both spectra of product games and explain how they extend to weighted sums by linearity. We also show how the Möbius coefficients recover our integral representation of the Shapley values. Section 2 now refers to these results.
In a tree leaf game, every off-path factor equals one. Consequently, a subset can contribute to either spectrum of the tree only if all its features occur together on at least one root-to-leaf path. A general product component can involve all input features, so its coefficients can be nonzero at every interaction order. We have added these formulas and the comparison to Appendix D.
Q2. Benchmarks for Shapley approximators. Product-kernel, log-link, and survival models can complement small-game and tree-based benchmarks with high-dimensional games that exhibit interactions across many features and orders. Full-degree quadrature provides reference attributions in exact arithmetic. We added a discussion about this benchmark application in the Conclusion, including the need to document the background set and numerical precision.
Q4. Complexity lower bound. In a sequential model where each attribution occupies one memory word, explicitly returning all d Shapley values requires Ω(d) work. Given the quadrature rule, our evaluation requires O(dmq) work. It is therefore optimal up to the node budget and matches the linear output lower bound in regimes where the certified node count mq remains bounded as d grows. For general product games, we do not establish a stronger lower bound or claim that the O(d2) work of the full-degree regime is optimal.