Technical Summary: Tractable Shapley Values and Interactions via Tensor Networks

Problem Statement

Explaining machine learning predictions via Shapley values and their higher-order generalizations (Shapley Interaction Indices, SII) is fundamental for decision support and interpretability. However, computing these indices is computationally prohibitive for models with $n$ features, as it traditionally requires enumerating $O(2^n)$ coalitions. Existing solutions face significant trade-offs:

• Structural Assumptions: Methods like TreeSHAP or those for Generalized Additive Models (GAMs) are exact only for specific architectures (e.g., trees, linear models).
• Sampling-Based Approximations: Approaches like KernelSHAP or SHAP-IQ rely on heavy sampling, requiring delicate variance tuning and often failing to scale to higher-order interactions without massive computational costs.
• Amortized Estimation: Methods that train auxiliary models often incur significant training overhead and may lack theoretical guarantees on the fidelity of the explanation.

The core challenge is to compute Shapley values and interactions exactly (or with controlled error) for general predictors without exponential enumeration or excessive sampling.

Methodology: TN-SHAP

The authors propose TN-SHAP, a method that replaces exhaustive coalition enumeration with a few-evaluation scheme on a Tensor Network (TN) surrogate. The approach leverages three key insights to reduce complexity from $O(2^n)$ to $O(n \cdot \text{poly}(\chi))$, where $\chi$ is the maximal bond dimension of the tensor network.

1. Multilinear Representation and Coefficient Extraction

The method assumes the predictor $f$ can be well-approximated by a multilinear function $g$ in a lifted feature space. In a multilinear expansion, $f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$, coalition values correspond to linear combinations of tensor coefficients. Crucially, Shapley values depend only on size-aggregated marginal contributions (sums of contributions for coalitions of size $s$), rather than specific coalition memberships.

2. Diagonal Selectors and Polynomial Interpolation

Instead of querying $2^n$ coalitions, TN-SHAP uses diagonal selector matrices $S_r(t) = \text{Diag}(t, 1)$ applied to lifted features $\tilde{x}_r = [\phi(x_r), 1]^\top$.

• By evaluating the surrogate $g$ at points where features are scaled by a parameter $t$, the method aggregates all coalitions of size $s$ into the coefficient of $t^s$ in a resulting polynomial $P(t)$.
• Specifically, for a target feature $i$, a probe function $G_i(t)$ is constructed to isolate the marginal contribution of $i$ across all subsets of other features.
• This transforms the combinatorial problem into polynomial interpolation. By evaluating $G_i(t)$ at $n$ distinct points (e.g., Chebyshev-Gauss nodes), the system solves a Vandermonde linear system to recover the size-aggregated marginal contributions $\{m_s^{(i)}\}$.
• The Shapley value is then computed as a weighted sum of these recovered coefficients.

3. Tensor Network Surrogates

To make the evaluation of the multilinear map tractable at scale, the coefficient tensor is factorized into a Tensor Network (TN) (e.g., Tensor Train or Hierarchical Tree) with bond dimension $\chi$.

• Feature Maps: To handle non-linear real-world data, scalar features are lifted via learned or hand-crafted maps $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ before entering the TN. This preserves multilinearity in the lifted space while allowing the surrogate to model non-linearities in the original input space.
• Efficiency: Each forward pass through the TN costs $O(\text{poly}(\chi))$. Since only $O(n)$ evaluations are required for interpolation, the total complexity for computing order-$k$ interactions becomes polynomial in $n$.

Key Contributions

1. Unified Probe-Interpolation Scheme: An exact algorithm for computing Shapley values and $k$-way interactions on a multilinear TN surrogate using only $O(n)$ structured forward passes, avoiding $O(2^n)$ queries.
2. Feature-Map-Enhanced Surrogates: A framework demonstrating how learned feature lifts preserve the multilinearity required for exact computation while improving surrogate fidelity for non-linear models.
3. Theoretical Guarantees:
   • Exactness: The method computes Shapley values exactly on the fitted multilinear surrogate.
   • Approximation Error: The error relative to the original model is bounded by the surrogate's worst-case coalition approximation error ($\epsilon$). For Shapley values, $|\phi^g_i - \phi^f_i| \leq 2\epsilon$.
   • Tractability: Proven reduction from exponential to polynomial time complexity $O(n \cdot \text{poly}(\chi) + n^2)$.

Experimental Results

The authors evaluated TN-SHAP on synthetic multilinear functions and real-world UCI regression datasets (Concrete, Diabetes, Energy) using MLP teachers.

• Synthetic Validation: On exactly multilinear functions, TN-SHAP achieved theoretical exactness with runtimes in the millisecond scale, outperforming KernelSHAP-IQ by orders of magnitude (e.g., 3.5ms vs 18.7ms for $n=10$; 19.7ms vs 447.3ms for $n=50$).
• Real-World Accuracy: On UCI datasets with MLP teachers:
  • TN-SHAP achieved 25–1000× wall-clock speedups over KernelSHAP-IQ at comparable accuracy.
  • For first-order ($k=1$) attributions, TN-SHAP achieved near-perfect cosine similarity (0.994) with the ground truth.
  • For higher-order interactions ($k=2, 3$), TN-SHAP maintained competitive accuracy while sampling-based baselines struggled with variance or required significantly more compute time to reach similar fidelity.
• Rank Ablation: Experiments showed that a student TN rank of $r=5-6$ was sufficient to recover all interaction orders with $R^2 > 0.99$ when the teacher had a rank of 16. Lower ranks underfit higher-order interactions.
• High-Dimensional Stability: In high-dimensional synthetic settings ($D=50, 100$), TN-SHAP maintained high surrogate fidelity ($R^2 > 0.95$) and strong Top-$k$ feature recovery under linear-cost query budgets.

Significance and Claims

The paper claims that TN-SHAP bridges the gap between the theoretical rigor of exact Shapley computation and the practical necessity of efficiency. By leveraging the algebraic structure of multilinear functions and the efficiency of tensor networks, the method:

• Turns an exponential enumeration problem into a small number of structured evaluations.
• Provides structural guarantees (via rank bounds) that address faithfulness issues common in unconstrained local surrogate methods like LIME.
• Unifies local Shapley explanations with global additive structures (GAMs), as fitting an order-$k$ surrogate yields exact $k$-SII coefficients matching corresponding GAM terms.
• Offers a scalable alternative to sampling-based methods, particularly for higher-order interactions where sampling variance is typically high.

The authors note that the method's performance depends on the quality of the TN surrogate fit and the choice of feature maps, but empirical results suggest that even modest feature lifts and tensor ranks are sufficient to capture complex coalitional structures in practice.