Research map / Learning theory and algorithms / Prediction and decision losses

Proxy-Based Approximation of Shapley and Banzhaf Interactions

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Shapley value attribution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ProxySHAP, which fits tree-ensemble proxies to a value function, extracts cardinal-probabilistic interaction indices exactly in polynomial time, and adds an MSR residual correction, achieving lower error than ProxySPEX and KernelSHAP-IQ.

Problem

Estimating higher-order Shapley and Banzhaf interaction indices is either fast but inaccurate or accurate but expensive, with prior proxy-based methods limited by exponential tree-depth dependence and MSR variance that grows with interaction size.

Approach

Decompose the target interaction into the exact interaction of a tree proxy plus an MSR-estimated interaction of the residual game, with a polynomial-time closed-form extraction of any cardinal-probabilistic interaction index from tree leaves, and a variance analysis telling when the residual correction helps.

Key results

• ProxySHAP achieves the lowest relative MSE in both small- and large-budget regimes across 47 benchmark games, outperforming ProxySPEX and KernelSHAP-IQ.
• On CLIP (FIxLIP game, MS COCO), ProxySHAP Pareto-dominates the FIxLIP linear regression baseline and ProxySPEX on AID for ViT-32 and ViT-16.
• MSR variance bound for Shapley interactions under leverage sampling is O(||nu||^2 n^{|S|-1}/|T|) for |S|>=2, so the residual correction can hurt higher-order estimates in larger games.

Surprising findings

• MSR residual adjustment can degrade higher-order interaction estimates despite improving singleton (Shapley value) estimates.
• On the CLIP task, ProxySHAP with residual adjustment did not improve the estimate over the unadjusted version while incurring about 10x more computation.

Limitations

• Approximation quality depends on the trained proxy; HPO helps but adds large overhead.
• MSR residual correction variance grows rapidly with interaction order, limiting benefit in high-dimensional settings.
• Only tree-based and linear proxies are studied.

Experimental setup

Datasets: TabArena MS COCO Mutagenicity Splice MarketingCamp

Benchmarks: TabArena MS COCO Mutagenicity Splice MarketingCamp

Metrics: relative MSE R^2 faithfulness area between insertion/deletion curves (AID) runtime model evaluations

Baselines: KernelSHAP-IQ ProxySPEX SHAP-IQ SVARM-IQ permutation sampling FIxLIP

Builds on: ProxySPEX RegressionMSR KernelSHAP-IQ SHAP-IQ Maximum Sample Reuse interventional TreeSHAP

Closest papers by meaning

• Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.88)
• KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.86)
• Fast Estimation of Partial Dependence Functions using Trees (ICML 2025 · similarity 0.85)
• shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
• Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithm (NeurIPS 2025 · similarity 0.84)
• A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.84)