Proxy-Based Approximation of Shapley and Banzhaf Interactions

Technical Summary: Proxy-Based Approximation of Shapley and Banzhaf Interactions

Problem Statement
Modern machine learning applications increasingly rely on cooperative game theory to interpret model behavior, specifically using Shapley and Banzhaf values to attribute contributions to individual features. However, understanding complex, non-linear dynamics often requires analyzing higher-order interactions (subsets of features) rather than just singleton effects. Computing exact cardinal-probabilistic interaction indices is computationally intractable for large numbers of features ($n$) due to the exponential growth of the coalition space ($2^n$).

Existing estimators face a critical trade-off between speed and accuracy:

• Sampling-based methods (e.g., SHAP-IQ, KernelSHAP-IQ) are often accurate but require impractical sample budgets to fit the vast number of higher-order terms, suffering from high variance that scales poorly with interaction order.
• Proxy-based methods (e.g., ProxySPEX) offer speed but rely on Fourier-based extraction from tree surrogates. This approach suffers from exponential complexity relative to tree depth and often requires aggressive truncation that compromises accuracy. Furthermore, existing proxy methods typically return interactions of the proxy rather than the underlying value function, introducing bias.

Methodology: ProxySHAP
The authors propose ProxySHAP, a framework that reconciles the sample efficiency of tree-based proxy models with a principled path to consistency via residual correction. The method decomposes the target interaction index $\phi^p_S(\nu)$ into two components:
$$\phi^p_S(\nu) = \underbrace{\phi^p_S(\hat{\nu}_T)}_{\text{Exact Proxy}} + \underbrace{\phi^p_S(\nu - \hat{\nu}_T)}_{\text{Residual}}$$

1. Proxy Fitting (Phase 1): A tree-based model (e.g., XGBoost, LightGBM) or a linear model with interaction features is trained on sampled coalitions to approximate the underlying value function $\nu$.
2. Exact Proxy Extraction (Phase 2): Unlike previous methods that extract Fourier coefficients, ProxySHAP introduces a polynomial-time generalization of interventional TreeSHAP. This allows for the exact computation of any cardinal-probabilistic interaction index (including Shapley and Banzhaf) directly from the tree structure.
   • The method leverages the Möbius representation of indicator games defined by tree leaves.
   • It avoids the exponential $O(4^d)$ complexity of Fourier-based extraction (where $d$ is tree depth), achieving $O(n_{nodes})$ runtime per interaction.
3. Residual Adjustment: To correct for the bias introduced by the proxy not perfectly matching $\nu$, the method estimates the interactions of the residual game $(\nu - \hat{\nu}_T)$ using Maximum Sample Reuse (MSR).
   • The paper provides a theoretical analysis showing that the variance of the MSR estimator for interactions of order $k$ scales as $O(n^{k-1}/|T|)$.
   • Consequently, the authors derive conditions under which MSR adjustment is beneficial: primarily for low-dimensional settings ($n < 30$) or when the sampling budget $|T|$ is sufficiently large relative to $n^{k-1}$. For high-order interactions in large games, the variance of the correction can outweigh the bias reduction.

Key Contributions

1. ProxySHAP Framework: A novel estimation strategy that combines a tree-based proxy with residual correction, enabling efficient and accurate approximation of higher-order interactions.
2. Theoretical Advancement:
   • Derivation of a closed-form, polynomial-time algorithm to extract exact cardinal-probabilistic interaction indices from tree ensembles, bypassing the exponential depth dependency of prior Fourier-based methods.
   • Formal characterization of the variance growth of MSR for higher-order interactions, establishing explicit conditions (in terms of $n$, budget, and interaction order $k$) under which residual adjustment improves or degrades performance.
3. Empirical Performance: Extensive benchmarking across 47 datasets (tabular, vision, language, graph, and vision-language) demonstrates that ProxySHAP sets a new state-of-the-art standard. It achieves the lowest error in both small-budget regimes (where it outperforms ProxySPEX) and large-budget regimes (where it outperforms KernelSHAP-IQ).

Results

• Accuracy: ProxySHAP consistently outperforms baselines (KernelSHAP-IQ, ProxySPEX, SHAP-IQ) in terms of Relative Mean Squared Error (MSE). In large-scale applications with thousands of features (e.g., Bioresponse with $n=1776$), ProxySHAP remains effective where other methods become computationally infeasible or inaccurate.
• Efficiency: The polynomial-time extraction algorithm provides speedups of orders of magnitude (10x to 1000x) compared to Fourier-based extraction, particularly as tree depth increases.
• Downstream Tasks: In a specific application to explaining the SigLIP-2 vision-language model (FIxLIP game), ProxySHAP demonstrated superior faithfulness (measured by Area under the Insertion-Deletion curve) compared to linear regression baselines and ProxySPEX.
• Hyperparameter Sensitivity: The study highlights that the quality of the proxy is critical. Hyperparameter optimization (HPO) significantly improves performance, and an "HPO-informed" default configuration (using many shallow trees) is proposed to balance cost and accuracy.

Significance and Claims
The paper claims that ProxySHAP resolves the long-standing trade-off between speed and accuracy in interaction estimation. By providing an exact extraction mechanism for tree proxies and a theoretically grounded strategy for residual correction, it enables the scalable quantification of complex dependencies in modern AI systems. The authors emphasize that their method is particularly valuable for:

• Large-scale applications: Handling datasets with thousands of features where exact computation is impossible.
• High-order interactions: Providing reliable estimates for interactions beyond pairwise effects, which are crucial for understanding cross-modal dependencies (e.g., in vision-language models) and complex feature synergies.
• Practical deployment: Offering a "state-of-the-art" estimator that is robust across varying budget constraints and model types, supported by a scalable C++ implementation.

The authors modestly note limitations, specifically that the approximation quality depends on the fitted proxy (requiring careful hyperparameter tuning) and that the variance of residual correction limits its utility in very high-dimensional settings for high-order interactions. Future work is suggested to explore alternative proxy classes and residual estimators that scale more gracefully.