# TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions

arXiv: https://arxiv.org/abs/2606.01540 · HTML: https://mlsanity.com/paper/2606.01540/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 43 references that are in the map.
- First posted on arXiv 1 Jun 2026.

## Builds on (most cited first, 21 of 21)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [Faith-Shap: The Faithful Shapley Interaction Index](https://mlsanity.com/paper/2203.00870/) (2022)
- [GraphSVX: Shapley Value Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.10482/) (2021)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Quantum Entanglement in Deep Learning Architectures](https://mlsanity.com/paper/1803.09780/) (2018)
- [Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study](https://mlsanity.com/paper/2108.10521/) (2021)
- [Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles](https://mlsanity.com/paper/2401.12069/) (2024)
- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Tractable Shapley Values and Interactions via Tensor Networks](https://mlsanity.com/paper/2510.22138/) (2025)

## Abstract (arXiv)

Shapley values are a widely used tool for attributing importance and interactions among input variables in black-box models, but their computation involves a function defined over an exponentially large space of subsets. We propose TN-SHAP-G, a framework that exploits structure in graph-structured inputs to compute Shapley values and higher-order interaction indices efficiently. Given a predictor and a fixed masking scheme, TN-SHAP-G learns a compact, graph-aligned multilinear surrogate that approximates the masked-input behavior, represented as a tensor network whose topology mirrors the input graph. Once trained from a small number of oracle queries, the surrogate enables deterministic recovery of first- and higher-order Shapley indices via the multilinear extension, without additional model queries or Monte Carlo variance. Experiments on molecular benchmarks show that the learned factorization closely matches exact Shapley values on small graphs and scales efficiently to larger graphs where sampling-based methods become infeasible.