Technical Summary: TN-SHAP-G

Problem Statement

Explaining predictions of black-box graph neural networks (GNNs) requires attributing importance to individual nodes and their interactions. While Shapley values and higher-order interaction indices offer principled, axiomatic attributions, their exact computation is intractable for graphs, scaling as $O(2^n)$ where $n$ is the number of nodes. Existing approximation methods face significant trade-offs: architecture-specific explainers (e.g., GNNExplainer) do not apply to general black-box models, while sampling-based approaches (e.g., GraphSVX, SHAP-IQ) require thousands of model evaluations and suffer from high variance, particularly for higher-order interactions. Furthermore, these sampling methods often fail to scale to larger graphs where exact enumeration is impossible.

Methodology: TN-SHAP-G

The authors propose TN-SHAP-G, a framework that exploits the structural properties of graph-structured inputs to compute Shapley values and interactions efficiently and deterministically. The core idea is to learn a compact, graph-aligned tensor network (TN) surrogate that approximates the masked-input behavior of the predictor.

1. The Masked Graph Game

The method formalizes graph explanation as a cooperative game induced by node masking. For a fixed input graph $G=(V, E)$ with features $X$ and a baseline $X^0$, a coalition $S \subseteq V$ defines a masked feature matrix $X_S$ where nodes in $S$ retain their original features and nodes outside $S$ are replaced by baseline features. The game value is $\nu(S) = f(G, X_S)$, where $f$ is the black-box predictor.

2. Multilinear Extension and Tensor Contraction

Direct computation of Shapley values requires summing over $2^n$ coalitions. The authors utilize the multilinear extension $\hat{\nu}(z)$, a continuous relaxation of the discrete game defined on $z \in [0, 1]^n$.

• Tensor Formulation: The multilinear extension can be expressed exactly as a tensor contraction: $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$, where $T$ is the coalition tensor and $b_v(z_v)$ are Bernoulli selector vectors.
• Deterministic Recovery: Shapley values and interaction indices correspond to integrals of partial derivatives of $\hat{\nu}$ along the diagonal $z = t\mathbf{1}$. Because $\hat{\nu}$ is multilinear, these derivatives are univariate polynomials of degree at most $n-1$. Thus, exact attributions can be recovered via Vandermonde interpolation from a small number of probe points, eliminating Monte Carlo variance.

3. Graph-Aligned Tensor Network Surrogate

Since the full coalition tensor $T$ has $2^n$ entries, TN-SHAP-G learns a graph-aligned tensor network surrogate $\hat{\nu}$ to approximate the multilinear extension.

• Topology: The TN topology mirrors the input graph $G$. Each node $v$ corresponds to a core tensor $A^{(v)}$ with one physical index (encoding coalition membership) and bond indices connecting to neighbors.
• Expressivity: The bond dimension $\chi$ controls the capacity of information flow across graph separators. The authors prove that for games with low cut-rank across graph separators (a property of many local dependency patterns in GNNs), this graph-aligned structure achieves higher expressivity with fewer parameters than chain-based factorizations like Tensor Trains (TT), which suffer from rank inflation on cyclic or complex graphs.
• Training: The surrogate is trained via empirical risk minimization on a small set of sampled coalitions ($M \ll 2^n$). Theoretical guarantees show that the required query budget scales near-linearly with the number of nodes for bounded-degree graphs.

4. Inference

Once trained, the surrogate enables deterministic computation of:

• First-order Shapley values: Via 1D integration of the diagonal derivative.
• Higher-order interactions: Via mixed partial derivatives and integration.
  All quantities are computed from the single trained surrogate without additional queries to the black-box model.

Key Contributions

1. Principled Graph-Aligned Representation: Introduction of a tensor-network surrogate that compresses the exponential coalition-value table into a low-rank, graph-aligned multilinear representation. This aligns the surrogate's inductive bias with local dependency patterns in graph predictors.
2. Amortized Deterministic Computation: Leveraging the multilinear structure to compute Shapley values and interactions via closed-form Vandermonde interpolation. This requires only $O(n)$ surrogate evaluations and introduces no Monte Carlo variance. A single surrogate amortizes the computation of all first- and higher-order indices.
3. Theoretical Guarantees:
   • Proof that the learned surrogate uniquely determines the multilinear extension, ensuring exact recovery of attributions on the surrogate.
   • Characterization of expressivity via cut-rank arguments, proving that graph-aligned TNs outperform chain factorizations (like TT) for graph-structured games.
   • Near-linear teacher-query complexity bounds for bounded-degree graphs.
   • Stability guarantees linking game approximation error to Shapley error.
4. Empirical Performance: Demonstrated high accuracy and scalability on molecular benchmarks, achieving $>0.99$ cosine similarity to exact Shapley values with as few as 50 model evaluations (10–100$\times$ fewer than baselines) and scaling to graphs where sampling methods are infeasible.

Experimental Results

The authors evaluated TN-SHAP-G on molecular benchmarks (Mutagenicity, Benzene) and protein graphs (PROTEINS).

• Correctness: On small graphs ($n \le 20$), TN-SHAP-G closely matches exact Shapley values (O1) and interaction indices (O2), significantly outperforming GraphSVX and permutation sampling in both accuracy and variance.
• Query Efficiency: TN-SHAP-G achieves high attribution accuracy with 10–100$\times$ fewer model queries than sampling-based estimators (SHAP-IQ, GraphSVX).
• Scalability: The method scales efficiently to graphs with up to 600 nodes using a coarsening-based surrogate architecture, whereas exact enumeration and sampling-based methods become impractical.
• Structure Ablation: Graph-aligned TNs consistently outperform Tensor Train (TT) surrogates under parameter-matched conditions, confirming the theoretical advantage of topology-aligned factorizations.
• Fidelity Proxy: A strong correlation was observed between the surrogate's test $R^2$ and the cosine similarity of the recovered Shapley values, validating $R^2$ as a practical proxy for attribution accuracy.

Significance and Claims

The paper claims that TN-SHAP-G advances the state of the art in graph explainability by providing a principled, model-agnostic framework that overcomes the exponential complexity of Shapley computation. By exploiting the low-rank structure inherent in graph-structured cooperative games, the method enables deterministic, variance-free attribution with near-linear query complexity.

The authors emphasize that this approach democratizes access to rigorous explanation methods for practitioners with limited computational resources, particularly in high-stakes domains like drug discovery and molecular property prediction. The framework is flexible, supporting various game semantics (e.g., node masking, node removal, Myerson values) and feature types, and extends beyond standard message-passing GNNs to other graph predictors. The work positions tensor networks not just as compression tools, but as a fundamental mechanism for tractable game-theoretic analysis on structured data.