# Interaction Tensor SHAP

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 5 Dec 2025.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [Using Shapley Values and Variational Autoencoders to Explain Predictive Models with Dependent Mixed Features](https://mlsanity.com/paper/2111.13507/) (2021)
- [SVARM-IQ: Efficient Approximation of Any-order Shapley Interactions through Stratification](https://mlsanity.com/paper/2401.13371/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Efficient Leverage Score Sampling for Tensor Train Decomposition](https://mlsanity.com/paper/2406.02749/) (2024)
- [FINCH: Locally Visualizing Higher-Order Feature Interactions in Black Box Models](https://mlsanity.com/paper/2503.16445/) (2025)

## Built on by (most cited first, 1 of 1)

- [TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train](https://mlsanity.com/paper/2601.01903/) (2026)

## Abstract (arXiv)

This study proposes Interaction Tensor SHAP (IT-SHAP), a tensor algebraic formulation of the Shapley Taylor Interaction Index (STII) that makes its computational structure explicit. STII extends the Shapley value to higher order interactions, but its exponential combinatorial definition makes direct computation intractable at scale. We reformulate STII as a linear transformation acting on a value function and derive an explicit algebraic representation of its weight tensor. This weight tensor is shown to possess a multilinear structure induced by discrete finite difference operators. When the value function admits a Tensor Train representation, higher order interaction indices can be computed in the parallel complexity class NC squared. In contrast, under general tensor network representations without structural assumptions, the same computation is proven to be P sharp hard. The main contributions are threefold. First, we establish an exact Tensor Train representation of the STII weight tensor. Second, we develop a parallelizable evaluation algorithm with explicit complexity bounds under the Tensor Train assumption. Third, we prove that computational intractability is unavoidable in the absence of such structure. These results demonstrate that the computational difficulty of higher order interaction analysis is determined by the underlying algebraic representation rather than by the interaction index itself, providing a theoretical foundation for scalable interpretation of high dimensional models.