Research map / Learning theory and algorithms / Prediction and decision losses
Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles
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 TreeSHAP-IQ, an algorithm that computes any-order Shapley interaction indices (SII, and general CIIs) exactly for tree ensembles in a single recursive tree traversal using polynomial arithmetic, extending Linear TreeSHAP.
Problem
Exact local Shapley interactions of any order are exponentially expensive to compute for tree-based models, and prior tree-based methods only handled SV or pairwise interactions.
Approach
Extends the summary polynomial of Linear TreeSHAP to interaction polynomials and quotient polynomials so that all any-order SII (and general cardinal interaction indices via modified weights in psi) are computed in one traversal per explanation point, with complexity scaling by binomial(n-1, s-1) instead of exponential in n.
Key results
- TreeSHAP-IQ gives speed-ups over naive computation ranging from about 10^4 on German Credit to about 1 on California housing (Table 1).
- Interaction-based explanations reveal, e.g., that the credit amount impacts the prediction mainly through interactions with installment rate and duration on German Credit.
- n-SII plots on German Credit suggest interaction effects vanish by order 5 and orders 6 and 7 are virtually absent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · Credit | speed-up: ∼ 10^4 | Helped |
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · Bank | speed-up: ∼ 10^3 | Helped |
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · Adult | speed-up: ∼ 10^3 | Helped |
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · Bike | speed-up: ∼ 10^1 | Helped |
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · COMPAS | speed-up: ∼ 10^2 | Helped |
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · Titanic | speed-up: ∼ 10^1 | Helped |
| Use TreeSHAP-IQ instead of naive computation | Shapley interaction computation · California | speed-up: ∼ 1 | Helped |
Surprising findings
- On the California dataset the reported speed-up over naive computation is only about 1x, so the gain is small for low-dimensional data.
Limitations
- For FSI the weighted-sum representation is only explicitly known for top-order interactions, limiting generality for that index.
- Results depend on the path-dependent feature perturbation; the interventional variant increases cost by the background sample size.
- Interaction scores are exponentially many, so visualization and interpretation remain challenging; no user study was conducted.
Experimental setup
Datasets: German Credit Bank Adult Census Bike COMPAS Titanic California housing
Benchmarks: German Credit Bank Adult Census Bike COMPAS Titanic California housing
Metrics: speed-up over naive computation n-SII attribution values
Baselines: TreeSHAP Linear TreeSHAP naive exact computation
Builds on: TreeSHAP Linear TreeSHAP Shapley Interaction Index n-SII
Closest papers by meaning
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.89)
- Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks (ICLR 2025 · similarity 0.89)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.88)
- Proxy-Based Approximation of Shapley and Banzhaf Interactions (NeurIPS 2026 · similarity 0.88)
- Fast Estimation of Partial Dependence Functions using Trees (ICML 2025 · similarity 0.86)
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.