Interaction Tensor SHAP

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.