Technical Summary: PolySHAP – Extending KernelSHAP with Interaction-Informed Polynomial Regression

Problem Statement

Shapley values are a central game-theoretic tool in Explainable AI (XAI) for attributing a model's prediction to its input features. However, computing Shapley values exactly requires evaluating the model on all $2^d$ possible feature subsets, which is computationally infeasible for models with a large number of features $d$.

KernelSHAP (Lundberg & Lee, 2017) has emerged as a leading method to approximate Shapley values efficiently. It frames the problem as a weighted least-squares regression, approximating the cooperative game $\nu$ with a linear function fitted to a sample of random feature subsets. While effective, this linear approximation inherently assumes feature additivity, failing to capture non-linear interactions between features. Consequently, KernelSHAP may yield suboptimal estimates when the underlying game exhibits significant higher-order interactions.

Methodology: PolySHAP

The authors propose PolySHAP, a generalization of KernelSHAP that approximates the game $\nu$ using higher-degree polynomials rather than a linear function. This approach explicitly models non-linear feature interactions.

Core Mechanism

1. Interaction-Informed Representation: Instead of fitting a linear model $\sum \phi_i \mathbb{1}[i \in S]$, PolySHAP fits a polynomial of degree $k$ over the binary feature indicators $\mathbb{1}[i \in S]$. The approximation includes an "interaction frontier" $\mathcal{I}$, a subset of interaction terms (subsets of features with size $\ge 2$).
   $$\hat{\nu}(S) \approx \sum_{T \in \mathcal{D} \cup \mathcal{I}} \phi_T \prod_{j \in T} \mathbb{1}[j \in S]$$
   where $\mathcal{D}$ represents single features and $\mathcal{I}$ represents interaction terms.

2. Regression Formulation: PolySHAP solves a weighted least-squares problem similar to KernelSHAP but with an expanded design matrix containing columns for both main effects and selected interaction terms. The objective minimizes the weighted $\ell_2$ loss between the sampled game values $\nu(S_\ell)$ and the polynomial approximation.

3. Extraction of Shapley Values: A key theoretical result (Theorem 4.3) demonstrates that the Shapley values of the original game can be recovered directly from the coefficients of the polynomial approximation. Specifically, the Shapley value for feature $i$ is the sum of the coefficient for the main effect $\phi_i$ and the coefficients of all interaction terms containing $i$, divided by the size of those interaction sets:
   $$\phi_i^{SV} = \phi_i + \sum_{S \in \mathcal{I}: i \in S} \frac{\phi_S}{|S|}$$

4. Sampling Strategies: The method supports standard sampling and paired sampling (sampling subsets $S$ and their complements $D \setminus S$). The authors utilize leverage score sampling to improve estimation quality, noting that for higher-order interactions, order-1 leverage scores (uniform over subset sizes) perform well in practice.

Key Contributions

1. Theoretical Consistency and Extension

The paper proves that PolySHAP provides consistent estimates of Shapley values. As the number of samples $m$ approaches the total number of subsets $2^d$, the PolySHAP estimates converge exactly to the true Shapley values (Theorem 4.3). This contrasts with some tree-based approximation methods (e.g., RegressionMSR) that require additional regression adjustment steps to achieve consistency.

2. Theoretical Equivalence of Paired Sampling and 2-PolySHAP

A major theoretical contribution is the proof that KernelSHAP with paired sampling is mathematically equivalent to 2-PolySHAP (Theorem 5.1).

• When subsets are sampled in pairs ($S$ and $D \setminus S$), the linear regression solution of KernelSHAP yields the exact same Shapley value approximations as a second-order polynomial regression (2-PolySHAP).
• This finding provides the first strong theoretical justification for the empirical success of paired sampling, explaining that it implicitly captures all second-order interactions without explicitly fitting a degree-2 polynomial.

3. Empirical Performance

Extensive experiments across 15 local explanation games (covering tabular, image, and language domains) demonstrate that:

• Higher-order accuracy: Increasing the polynomial degree (e.g., 3-PolySHAP) consistently improves approximation quality (measured by MSE, Precision@5, and Spearman correlation) compared to KernelSHAP (1-PolySHAP) and Permutation Sampling, provided the sampling budget is sufficient.
• Paired Sampling Efficiency: Under paired sampling, KernelSHAP achieves performance comparable to 2-PolySHAP, validating the theoretical equivalence.
• State-of-the-art results: In low-to-moderate dimensional settings, PolySHAP (specifically 3-PolySHAP) often outperforms other baselines, including RegressionMSR (which relies on XGBoost approximations) and SVARM.

Significance and Claims

The paper claims to offer a principled extension of the widely used KernelSHAP framework. By moving from linear to polynomial approximations, PolySHAP addresses the limitation of ignoring feature interactions, leading to more accurate explanations for complex models.

Crucially, the work bridges a gap between heuristic practices and theory. By proving that the popular "paired sampling" heuristic is equivalent to second-order interaction modeling, the authors provide a rigorous foundation for why this sampling strategy works so well in practice. The authors modestly note that while higher-order interactions improve accuracy, they require larger sampling budgets, and in very high-dimensional settings ($d \ge 60$), the gains are more modest due to the combinatorial explosion of interaction terms.

The paper concludes that PolySHAP is a robust, consistent, and empirically superior method for Shapley value estimation, particularly when the underlying game involves non-linear feature interactions.