PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

AI summary

Overview

Research area: Explainable AI (XAI), specifically game-theoretic feature attribution via Shapley values and the KernelSHAP estimation framework.

Technical level: Advanced. The paper assumes familiarity with cooperative game theory, weighted least squares, leverage scores, and pseudoinverse-based regression. The high-level intuition is accessible, but the theorems and proofs require a strong mathematical background.

Scope: The paper introduces PolySHAP, a polynomial-regression extension of KernelSHAP that models feature interactions, proves consistency of its Shapley value estimates, and proves that the widely used paired sampling heuristic is exactly equivalent to second-order PolySHAP.

What This Paper Is About

Computing exact Shapley values requires 2^d game evaluations for a model with d features, which is infeasible for most practical models. KernelSHAP avoids this exponential cost by approximating the game as a linear function fit from a small number of sampled feature subsets, then reading Shapley values off that linear approximation. This paper's goal is to replace that linear approximation with a higher-degree polynomial that captures non-linear interactions between features, and to explain theoretically why a common sampling trick (paired sampling) works so well in practice.

Key Contributions

1. PolySHAP method. The authors propose PolySHAP, which approximates the game ν via a higher-degree polynomial in the binary feature indicators 1[i ∈ S], where the polynomial terms are chosen by an "interaction frontier" ℐ. They prove (Theorem 4.3) that PolySHAP returns the Shapley values exactly as the number of samples m goes to 2^d, i.e., that the estimator is consistent, and demonstrate empirically that it yields more accurate Shapley value estimates than KernelSHAP and Permutation sampling.

2. Theoretical equivalence of paired sampling and second-order PolySHAP. They prove (Theorem 5.1) that KernelSHAP with paired sampling (subsets sampled in complementary pairs S and D ∖ S) outputs exactly the same Shapley value approximations as second-order (2-)PolySHAP, without ever fitting a degree-2 polynomial. This generalizes a recent result of Mayer and Wüthrich (2025), who showed paired KernelSHAP exactly recovers Shapley values when the game has interactions of at most degree 2.

3. General convergence for k_ADD-SHAP. Proposition 4.6 extends Theorem 4.2 of Pelegrina et al. (2025), showing that k_ADD-SHAP converges to the Shapley value for k = 1, …, d, and simplifying that method.

4. Practical design guidance. They define the k-additive interaction frontier ℐ_{≤k}, show that k-PolySHAP corresponds to order-k Faith-SHAP (Corollary 4.5) and that 1-PolySHAP equals KernelSHAP, and introduce partial interaction frontiers and a "PolySHAP (log)" variant for high-dimensional settings.

Main Findings

• Higher-degree approximations improve accuracy. Adding any number of interactions in PolySHAP improves approximation quality as measured by MSE across the benchmark games. 3-PolySHAP outperforms 2-PolySHAP, which outperforms KernelSHAP (1-PolySHAP) — provided there is enough sampling budget, since performance is only plotted for m ≥ d'.
• PolySHAP is consistent. Theorem 4.3 states that the Shapley values of ν are recovered from the PolySHAP representation as φ_i^SV[ν] = φ_i^ℐ + Σ_{S ∈ ℐ : i ∈ S} φ_S^ℐ / |S|, so consistent estimation of the PolySHAP representation implies consistent estimation of the Shapley value, with exact recovery as m goes to 2^d. This contrasts with RegressionMSR, which requires an additional "regression adjustment" step for consistency.
• Paired KernelSHAP equals paired 2-PolySHAP. Under paired sampling, KernelSHAP and 2-PolySHAP produce identical approximations (overlapping curves in their experiments). However, the two differ in cost: KernelSHAP can be computed already with d + 1 samples, while 2-PolySHAP requires a larger budget.
• Paired sampling partially collapses the PolySHAP hierarchy. Under paired sampling, 3-PolySHAP substantially improves its approximation quality and is equivalent to 4-PolySHAP in their experiments. The authors conjecture that paired (k+1)-PolySHAP returns the same approximate Shapley values as paired k-PolySHAP for all odd k with 1 ≤ k < d, but leave the proof to future work.
• Practical gains require order-3 interactions. Because of the paired sampling equivalence, PolySHAP's practical benefit over KernelSHAP becomes apparent only when order-3 interactions are included. In low-dimensional settings 3-PolySHAP yields the best performance on the Housing, Adult, Estate, Forest, and Cancer datasets.
• High dimensions give smaller gains. For d ≥ 60, only a small number of order-3 interactions can be added, resulting in more modest improvements. Partial inclusion (3-PolySHAP (50%), 3-PolySHAP (log)) already provides substantial gains in budget-restricted cases.
• Baseline comparison. Among all baselines, only RegressionMSR achieves comparable performance, though it depends strongly on XGBoost (indicated by poor results on CG60) and has an inherent advantage because all tabular games rely on tree-based models.
• Sampling guidance. For KernelSHAP the leverage score is ℓ_S = 1 / binom(d, |S|), meaning leverage score sampling is equivalent to sampling subsets uniformly by their size. For k-additive frontiers, a closed-form leverage score remains unknown, but the authors observed little variation between order-1 and higher-order leverage scores and recommend order-1 leverage scores.
• Computational cost. Solving the regression scales as O(m·(d')² + (d')³) and converting the PolySHAP representation to Shapley values as O(d·d'), where d' is the number of polynomial terms. Complexity scales linearly with the budget m and quadratically with d'; in practice game evaluations (model predictions) usually dominate.

Methodology in Plain English

Shapley values can be written as the coefficients of the best weighted linear fit to the game ν, where each subset S ⊆ D gets a weight μ(S) = 1/binom(d-2, |S|-1) for 0 < |S| < d and 0 otherwise. KernelSHAP approximates that weighted least squares problem using only m sampled subsets, drawing subsets according to a distribution p and reweighting each observation by μ(S)/p(S).

PolySHAP keeps this machinery but adds extra columns to the regression: alongside the d individual features, it includes product terms for a chosen set ℐ of multi-feature interactions. Each term contributes only when all of its features are present in the sampled subset. The design matrix and target vector are scaled by sqrt(μ(S_ℓ)/p(S_ℓ)), and the efficiency constraint (coefficients summing to ν(D)) is handled by projecting off the all-ones vector, turning the constrained problem into an ordinary least squares solve. The fitted interaction coefficients are then folded back into Shapley values using the closed-form mapping of Theorem 4.3. The proof of this mapping, and of the paired-sampling equivalence, relies on a new "projection lemma."

For sampling, the authors use order-1 leverage scores (uniform over subset sizes), sampling without replacement, and a "border trick" that exhaustively enumerates subsets of a given size when the expected number of samples exceeds the number of available subsets. They compare k-PolySHAP for k ∈ {1,2,3,4}, partial frontiers covering 50% of k-order interactions, and a PolySHAP (log) variant that adds d log(binom(d,3)) order-3 interactions.

Experiments cover 15 local explanation games across 30 randomly selected instances, with m ranging from d+1 to min(2^d, 20000). The games span tabular data (random forests, with ground-truth Shapley values from TreeSHAP via path-dependent perturbation), image data (ResNet18 with 14 superpixels, and vision transformers with 3×3 (ViT9) and 4×4 (ViT16) super-patches on ImageNet and CIFAR-10), and language data (a fine-tuned DistilBERT predicting IMDB sentiment with review excerpts of length 14). For non-tabular datasets, baseline imputation with exhaustive Shapley value computation provides ground truth. Metrics are MSE, top-5 precision (Precision@5), and Spearman correlation with standard error of the mean (SEM).

Why This Matters

Impact on research. Paired sampling is used in all state-of-the-art Shapley value estimators, yet its superior performance had not been well understood. Theorem 5.1 gives, to the authors' knowledge, the first strong theoretical justification for the heuristic, and it explains why paired sampling is effective for all games, not just those with at most degree-2 interactions. The paper also connects PolySHAP to the Faithful Shapley interaction index and simplifies and generalizes k_ADD-SHAP. The consistency guarantee (no post-hoc regression adjustment needed) places PolySHAP on firmer theoretical footing than tree-based RegressionMSR.

Real-world applications:

• Explaining tabular risk and credit-style models (e.g., the Housing, Adult, Estate, Forest, Cancer games studied here), where accurate per-feature attributions support regulatory or audit requirements.
• Image model explanation through superpixel or super-patch attributions (ResNet18, ViT9, ViT16 on ImageNet and CIFAR-10).
• Language model explanation, such as attributing sentiment predictions from a fine-tuned DistilBERT on IMDB review excerpts.
• High-dimensional scientific and public-health tabular data, such as the NHANES (d = 79) and Crime (d = 101) games.

Industry relevance. KernelSHAP is one of the most widely used model-agnostic explanation methods, so a drop-in extension that reuses the same sampling infrastructure is directly relevant to teams already shipping Shapley-based explanations. Because PolySHAP's parameter transform costs only O(d·d') and the regression dominates at O(m·(d')² + (d')³), the method fits into existing pipelines where model evaluations are the dominant cost. The finding that paired sampling implicitly captures second-order interactions also means that many existing deployments already benefit from part of what PolySHAP formalizes — and that upgrading to order-3 interactions is where new accuracy gains lie.

Future Directions

1. Structured interaction frontiers. The authors propose exploring more structured variants, for example detecting important interactions (citing Tsang et al., 2020) or leveraging inherent interaction structure in graph-structured inputs (citing Muschalik et al., 2025).
2. Proving the higher-order paired-sampling conjecture. The empirical observation that paired (k+1)-PolySHAP matches paired k-PolySHAP for odd k > 1 (with 1 ≤ k < d) lacks a proof; the authors note the difficulty is finding an explicit mapping from (k+1)-PolySHAP representations to k-PolySHAP representations.
3. Closed-form or better-justified leverage scores for interaction frontiers. The paper states that a closed-form solution for k-additive frontiers remains unknown, and only recommends order-1 leverage scores based on observed small variation.
4. Scaling to high dimensions. Since improvements are modest for d ≥ 60 because few order-3 interactions can be modeled, further work is needed on frontier selection under tight budgets — the partial frontier and PolySHAP (log) variants are first attempts.

Target Audience

This paper is most valuable to XAI researchers working on Shapley value estimation and feature attribution, particularly those familiar with KernelSHAP, LeverageSHAP, RegressionMSR, and sampling-based estimators. It also suits theoretically inclined machine learning researchers interested in game-theoretic attribution, interaction indices, and antithetic sampling. Practitioners who deploy KernelSHAP in production will benefit from the practical guidance on paired sampling and order-3 interactions, though they should expect to engage with the formal statements in Sections 4 and 5 to follow the arguments fully. Readers seeking the accessible core should focus on the introduction, the definition of the interaction frontier, the two headline theorems (4.3 and 5.1), and the experiments in Section 6; the proofs, including the projection lemma, are confined to Appendix A.

Authors’ abstract

Shapley values have emerged as a central game-theoretic tool in explainable AI (XAI). However, computing Shapley values exactly requires $2^d$ game evaluations for a model with $d$ features. Lundberg and Lee's KernelSHAP algorithm has emerged as a leading method for avoiding this exponential cost. KernelSHAP approximates Shapley values by approximating the game as a linear function, which is fit using a small number of game evaluations for random feature subsets. In this work, we extend KernelSHAP by approximating the game via higher degree polynomials, which capture non-linear interactions between features. Our resulting PolySHAP method yields empirically better Shapley value estimates for various benchmark datasets, and we prove that these estimates are consistent. Moreover, we connect our approach to paired sampling (antithetic sampling), a ubiquitous modification to KernelSHAP that improves empirical accuracy. We prove that paired sampling outputs exactly the same Shapley value approximations as second-order PolySHAP, without ever fitting a degree 2 polynomial. To the best of our knowledge, this finding provides the first strong theoretical justification for the excellent practical performance of the paired sampling heuristic.