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

Farzaneh Heidari, Guillaume Rabusseau

The Challenge of Graph Explainability

In the realm of eXplainable AI (XAI), Shapley values are widely considered the gold standard for feature attribution. Rooted in cooperative game theory, they provide a mathematically "fair" way to determine exactly how much each input feature—such as a node in a molecular graph—contributes to a model's final prediction.

However, calculating exact Shapley values is computationally prohibitive, requiring $O(2^n)$ model evaluations for $n$ nodes. For graph-structured data, this challenge is particularly acute. While Monte Carlo sampling is often used to approximate these values, the variance explodes when attempting to calculate higher-order interaction indices (how two or more nodes synergize). Furthermore, many existing graph-specific explainers are "white-box," meaning they are hardcoded for specific architectures like Graph Neural Networks (GNNs). The field needs a model-agnostic, mathematically grounded approach to explain graph predictions efficiently.

Introducing TN-SHAP-G

To bridge this gap, researchers have introduced TN-SHAP-G, a novel framework that calculates Shapley values and interaction indices for graph-based models by distilling them into a "graph-aligned" tensor network surrogate.

By treating the black-box graph predictor as a "teacher" and a Tensor Network (TN) as a "student," TN-SHAP-G mirrors the input graph's topology. This structural alignment enables deterministic, high-accuracy attributions using 10 to 100 times fewer model queries than traditional sampling-based approaches.

How It Works: The Methodology

The TN-SHAP-G framework relies on four core methodological pillars:

  1. Graph-Aligned Topology: Standard tensor decompositions, such as Tensor Trains, assume a linear chain of variables. TN-SHAP-G instead builds a tensor network whose internal structure directly matches the edges of the input graph. This creates a powerful inductive bias: nodes that are close in the graph are allowed to interact more easily within the surrogate, preventing the "rank inflation" that plagues generic tensor surrogates.
  2. Multilinear Extension: The framework leverages the Owen multilinear extension, a mathematical technique that transforms the discrete "game" of node masking into a continuous, differentiable polynomial.
  3. Gate Replacement Principle: Calculating Shapley values requires taking derivatives of this polynomial. TN-SHAP-G accomplishes this efficiently by replacing specific "Bernoulli gates" in the tensor network and performing a standard tensor contraction.
  4. Deterministic Recovery: Once the surrogate is trained on a small number of oracle queries, all first-order (importance) and higher-order (interaction) indices can be recovered via closed-form integration using Vandermonde interpolation. This requires absolutely no further queries to the expensive black-box model and eliminates Monte Carlo variance.

Key Insights and Advantages

A major breakthrough of TN-SHAP-G is the concept of amortized explanations. In traditional sampling, computing second-order interactions incurs a massive computational penalty. With TN-SHAP-G, the surrogate is trained once; thereafter, any order of interaction can be extracted computationally for "free."

Additionally, the researchers proved that the surrogate's test $R^2$—how well it mimics the black-box model on unseen node coalitions—serves as a highly reliable proxy for the accuracy of the resulting Shapley values. This allows practitioners to confidently gauge explanation quality without needing ground-truth Shapley values.

Experimental Results

The framework was rigorously evaluated across several standard graph classification and regression benchmarks, including Mutagenicity (molecular graphs), Benzene (ring structure detection), PROTEINS (secondary structure elements), and MAGE (continuous feature regression).

  • Unprecedented Efficiency: On small graphs, TN-SHAP-G achieved a >0.99 cosine similarity to exact Shapley values using merely 50 model evaluations. This represents a $10\times$ to $100\times$ reduction in queries compared to state-of-the-art methods like SHAP-IQ or permutation sampling.
  • High Scalability: The method scales gracefully to graphs with over 600 nodes. In stark contrast, competing methods like GraphSHAP-IQ frequently run out of memory or become computationally intractable once a node's local neighborhood exceeds 15 to 17 nodes.
  • Structural Robustness: The graph-aligned approach consistently outperformed chain-aligned (Tensor Train) surrogates, which proved highly sensitive and brittle to the arbitrary ordering of nodes.

Limitations and Future Directions

While highly effective, TN-SHAP-G does have limitations. The current implementation assumes a fixed masking scheme (e.g., replacing a node's features with a mean baseline). Although the underlying mathematics supports alternative schemes like complete node removal, the choice of baseline inherently impacts the semantic "meaning" of the resulting explanation.

Furthermore, if a model relies heavily on global, long-range interactions that ignore graph distance—such as a Graph Transformer—the graph-aligned tensor network may require a significantly higher "bond dimension" (complexity) to remain accurate.

Future work will likely explore adaptive tensor network topologies that can learn the optimal structure for the surrogate dynamically, as well as extending the framework to explain edge-level or motif-level importance in complex networks.

Summary updated

Abstract

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.
BibTeX
@inproceedings{heidari2026tn,
  author = {Farzaneh Heidari and Guillaume Rabusseau},
  title = {{TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=M4bE60aa1C},
}
Figure