Pith. sign in

REVIEW 3 minor 53 references

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

T0 review · 0 major / 3 minor · reviewed 2026-06-28 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A graph-structured tensor network surrogate trained on few model queries allows deterministic recovery of Shapley values and interactions without further evaluations or sampling.

desk verdict TN-SHAP-G trains a graph-topology tensor network on few oracle queries to serve as a multilinear surrogate, then extracts first- and higher-order Shapley indices deterministically from its extension. read the letter →

arxiv 2606.01540 v1 pith:VEQOOWYB submitted 2026-06-01 cs.LG cs.AI

Farzaneh Heidari , Guillaume Rabusseau This is my paper · ORCID
classification cs.LGcs.AI
keywords ShapleyvaluestensornetworksexplainableAIgraph-structuredinputsmultilinearextensionsurrogatemodelsinteractionindicesmoleculargraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces TN-SHAP-G to address the exponential cost of computing Shapley values over all input subsets in black-box predictors. It learns a compact multilinear surrogate whose tensor network structure matches the topology of graph-structured inputs such as molecules. Once fit to a modest number of masked oracle calls, the surrogate directly supplies first- and higher-order Shapley indices through its multilinear extension. This replaces Monte Carlo sampling with exact arithmetic on the learned factors. Experiments indicate the approach recovers exact values on small graphs and remains tractable on larger ones where sampling methods fail.

What carries the argument

Graph-aligned multilinear surrogate realized as a tensor network whose topology matches the input graph, enabling deterministic extraction of Shapley indices from the multilinear extension.

What would settle it

On any small graph where exhaustive enumeration of subsets remains feasible, compare the surrogate-derived Shapley values against the exact values obtained by direct oracle summation; a statistically significant discrepancy would falsify the claim.

Watch

Extended reading notes

Core claim

TN-SHAP-G constructs a tensor network whose topology mirrors the input graph and whose factors form a multilinear surrogate for the predictor's masked-input behavior; after training on a small set of oracle queries under a fixed masking scheme, the surrogate yields exact first- and higher-order Shapley indices via the multilinear extension without any additional model calls or stochastic estimation.

Load-bearing premise

A tensor network whose structure follows the input graph can approximate the predictor's behavior under the chosen masking scheme closely enough for the recovered indices to be accurate.

Editorial extensions

If this is right

  • Shapley values and higher-order interaction indices become available by direct contraction of the trained tensor network rather than summation over an exponential number of subsets.
  • No additional predictor queries or Monte Carlo sampling are required after the initial training phase.
  • The method scales to graph sizes where sampling-based Shapley estimators become computationally prohibitive.
  • The same surrogate supplies both first-order attributions and all higher-order interaction terms in a single deterministic pass.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The approach could be tested on other graph-structured domains such as citation networks or protein contact graphs by swapping only the masking scheme and oracle interface.
  • If the tensor network ranks can be kept low, the method might extend to dynamic graphs by updating only local factors rather than retraining from scratch.
  • The deterministic nature opens the possibility of combining the surrogate with gradient-based optimization over the Shapley indices themselves.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 3 minor

Summary. The paper proposes TN-SHAP-G, a framework that learns a compact, graph-aligned multilinear surrogate via a tensor network whose topology mirrors the input graph. Trained on a small number of oracle queries under a fixed masking scheme, the surrogate permits deterministic recovery of first- and higher-order Shapley indices and interactions through its multilinear extension, without further model queries or Monte Carlo sampling. Experiments on molecular benchmarks report close numerical agreement with exact Shapley values on small graphs and favorable scaling on larger instances.

Significance. If the approximation quality holds, the method supplies an explicit algebraic route from a learned surrogate to exact interaction indices, eliminating sampling variance while keeping query cost low. The explicit construction of the surrogate, the linking identity to multilinear extensions, the training protocol that bounds query count, and the reported benchmark agreement on molecular graphs constitute concrete strengths that would be useful for structured-data explainability.

minor comments (3)
  1. [Abstract] The abstract states 'close agreement' and 'scales efficiently' but supplies no quantitative error metrics, training hyperparameters, or validation protocol; these details appear in the full text but should be summarized with specific numbers (e.g., mean absolute error on Shapley values) already in the abstract.
  2. [§2] Notation for the masking scheme and the precise definition of the multilinear extension should be introduced with an equation number in §2 or §3 to make the algebraic identity in the central claim immediately verifiable.
  3. [Figures 3-5] Figure captions for the molecular-graph experiments should explicitly state the number of oracle queries used for training and the exact baseline method against which agreement is measured.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The description accurately captures the TN-SHAP-G framework, its use of graph-aligned tensor networks for multilinear surrogates, and the experimental results on molecular graphs. No specific major comments appear in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The derivation chain consists of (1) defining a graph-aligned tensor network surrogate whose topology matches the input graph, (2) training its parameters on a small set of oracle queries under a fixed masking scheme to approximate masked-input behavior, and (3) recovering Shapley and interaction indices exactly via the standard multilinear-extension identity applied to the trained surrogate. None of these steps reduces to its inputs by construction: the surrogate parameters are learned from data rather than defined in terms of the target indices; the multilinear-extension identity is an external algebraic fact, not derived within the paper; and no uniqueness theorem, self-citation chain, or ansatz smuggling is invoked to force the result. The method is explicitly an approximation technique whose accuracy is validated empirically on benchmarks, not a first-principles derivation that tautologically reproduces its training data. This is a standard surrogate-model workflow and receives the default non-circularity finding.

Assumptions & free parameters 1 free parameters · 1 assumptions · 1 invented entities

The method rests on learning a surrogate whose accuracy is not independently guaranteed; the ledger therefore records the fitted parameters and the domain assumption that multilinear recovery works once the surrogate is accurate.

free parameters (1)
  • tensor network parameters
    Core tensors of the network are fitted to oracle queries to approximate the masked function.
assumptions (1)
  • domain assumption Shapley values and interaction indices can be recovered exactly from the multilinear extension of a value function.
    Standard result from cooperative game theory invoked to convert the trained surrogate into attribution scores.
invented entities (1)
  • graph-aligned multilinear surrogate
    purpose: Compact approximation of masked-input behavior whose topology matches the input graph.
    Central new object introduced by the framework; no independent evidence of its existence outside the learned model is supplied.

how reviews work

0 comments
Cite this review

Pith. "Pith review of TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions." pith.science (2026). https://pith.science/paper/VEQOOWYB

@misc{pith2026260601540,
  author       = {Pith},
  title        = {Pith review of: TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VEQOOWYB}},
  note         = {Machine review of arXiv:2606.01540}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2606.01540 by the authors.

Figure 1
Figure 1. TN-SHAP-G overview. (A) Masked graph game with baseline replacement (x 0 v). (B) Black-box teacher queried on coalitions. (C) Graph-aligned tensor network surrogate. (D) Exact Shapley values, and interactions via interpolation. game approximation error to Shapley error (Lemma 3.7). • Theoretical guarantees for expressivity, correctness, and complexity. We show that the learned surrogate uniquely determines the multi… view at source ↗
Figure 2
Figure 2. From graph game to graph-aligned tractable surrogate. 3.1. Graph-Aligned Surrogates and Rank-Based Expressivity The coalition tensor T ∈ R 2×···×2 defined in (8) contains 2 n entries, and constructing it explicitly would require 2 n black-box evaluations of f(G, XS), which is prohibitive even for moderate n. We therefore construct a compact surrogate by imposing a tensor network (TN) structure on T whose topology mi… view at source ↗
Figure 3
Figure 3. Deterministic Shapley from a TN surrogate via diagonal interpolation. (a) Restrict to the diagonal z = t1 and evaluate gu(t) = ∂zu νˆ(t1) at probe points tj . (b) Multilinearity implies gu is a degree-≤ n−1 polynomial. (c) Interpolate coefficients via a Vandermonde design (or a stable equivalent) and integrate exactly: ϕb(u) = R 1 0 gu(t) dt. 3.2.1. DISTILLATION We train a graph-aligned TN surrogate νˆ(·; Θ) : [0, 1… view at source ↗
Figures from the paper (8 more)
Figure 6
Figure 6. Figure 6: Structure ablation: graph-aligned TN vs. tensor train (TT). Attribution accuracy under parameter matching and a low query budget (10 n coalitions per graph). Different colors correspond to Different TT node orderings. 100 200 300 400 600 Number of Nodes 10 2 10 3 Train…
Figure 5
Figure 5. Figure 5: Surrogate R2 predicts Shapley accuracy. Each point is one (graph, epoch) pair; color indicates training progress. a single learned surrogate supports both O1 and O2 re￾covery, whereas sampling-based methods require separate Monte Carlo budgets and exhibit high variance…
Figure 8
Figure 8. Figure 8: Tensor train (TT) representation of a 4-way tensor. Physical indices xi are shown as dangling legs; internal edges correspond to bond indices. Evaluating g(x1, . . . , xn) using a TN representation corresponds to contracting all bond indices after attaching the vectors…
Figure 9
Figure 9. Figure 9: Accuracy at budget 500. TN-SHAP-G has higher median and 3−5× lower variance than sampling methods. • Permutation sampling (Castro et al., 2009) for O1 (and, when applicable, for O2 via the standard inclusion–exclusion marginal on sampled permutations). • SHAP-IQ (Fumag…
Figure 10
Figure 10. Figure 10: Scalability on PROTEINS. T(a) Surrogate test R 2 remains above 0.8 across graph sizes up to 600 nodes. (b) Shapley efficiency gap | P i ϕi − (ν(V ) − ν(∅))| stays small (10−7 –10−5 ), confirming numerical stability of the deterministic recovery [PITH_FULL_IMAGE:figur…
Figure 11
Figure 11. Figure 11: TN-SHAP-G explanations on Mutagenicity. Top: Organophosphorus compound (prediction 0.96). Bottom: Fluoroaniline (prediction 0.86). Left: node-level Shapley values. Center: pairwise Shapley interaction matrix. Right: molecular graph colored by node attribution. For Ben…
Figure 12
Figure 12. Figure 12: Structure ablation with parameter-matched surrogates. GA-TN (TN-SHAP-G) consistently achieves higher surrogate fidelity (Train/Test R 2 ) and higher attribution recovery (O1/O2 cosine similarity) than TT surrogates across different orderings at comparable parameter bu…
Figure 13
Figure 13. Figure 13: Ablation studies. (a) O2-aware sampling achieves highest accuracy for both O1 and O2 indices by preferentially sampling intermediate-size coalitions. (b) O1 Shapley values saturate at ∼100 epochs while O2 interactions require ∼500 epochs (budget: 500 samples, N=10 gra…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 7 canonical work pages

  1. [1]

    Contributions to the Theory of Games , volume=

    A value for n-person games , author=. Contributions to the Theory of Games , volume=. 1953 , publisher=

    1953

  2. [2]

    Mathematics of Operations Research , volume=

    Graphs and cooperation in games , author=. Mathematics of Operations Research , volume=

  3. [3]

    Management Science , volume=

    Multilinear extensions of games , author=. Management Science , volume=

  4. [4]

    International Journal of Game Theory , volume=

    An axiomatic approach to the concept of interaction among players in cooperative games , author=. International Journal of Game Theory , volume=

  5. [5]

    Advances in Neural Information Processing Systems , volume=

    A unified approach to interpreting model predictions , author=. Advances in Neural Information Processing Systems , volume=

  6. [6]

    The many

    Sundararajan, Mukund and Najmi, Amir , booktitle=. The many

  7. [7]

    Tsai, Che-Ping and Yeh, Chih-Kuan and Ravikumar, Pradeep , journal=. Faith-

  8. [8]

    Advances in Neural Information Processing Systems , volume=

    Fumagalli, Fabian and Muschalik, Maximilian and Kolpaczki, Patrick and H. Advances in Neural Information Processing Systems , volume=

Show all 53 references
  1. [9]

    Ribeiro, Marco Tulio and Singh, Sameer and Guestrin, Carlos , booktitle=. ``

  2. [10]

    2025 , eprint=

    Tractable Shapley Values and Interactions via Tensor Networks , author=. 2025 , eprint=

    2025

  3. [11]

    Ying, Rex and Bourgeois, Dylan and You, Jiaxuan and Zitnik, Marinka and Leskovec, Jure , booktitle=

  4. [12]

    Advances in Neural Information Processing Systems , volume=

    Parameterized explainer for graph neural network , author=. Advances in Neural Information Processing Systems , volume=

  5. [13]

    International Conference on Machine Learning , pages=

    On explainability of graph neural networks via subgraph explorations , author=. International Conference on Machine Learning , pages=

  6. [14]

    IEEE Transactions on Pattern Analysis and Machine Intelligence , volume=

    Explainability in graph neural networks: A taxonomic survey , author=. IEEE Transactions on Pattern Analysis and Machine Intelligence , volume=

  7. [15]

    Duval, Alexandre and Malliaros, Fragkiskos D , booktitle=

  8. [16]

    Annals of Physics , volume=

    A practical introduction to tensor networks: Matrix product states and projected entangled pair states , author=. Annals of Physics , volume=

  9. [17]

    Advances in Neural Information Processing Systems , volume=

    Supervised learning with tensor networks , author=. Advances in Neural Information Processing Systems , volume=

  10. [18]

    Advances in Neural Information Processing Systems , volume=

    Tensorizing neural networks , author=. Advances in Neural Information Processing Systems , volume=

  11. [19]

    Advances in Neural Information Processing Systems , volume=

    Expressive power of tensor-network factorizations for probabilistic modeling , author=. Advances in Neural Information Processing Systems , volume=

  12. [20]

    Wahl, ... and ... , booktitle=. 2024 , note=

    2024

  13. [21]

    Lower and Upper Bounds on the Pseudo-Dimension of Tensor Network Models , volume =

    Khavari, Behnoush and Rabusseau, Guillaume , booktitle =. Lower and Upper Bounds on the Pseudo-Dimension of Tensor Network Models , volume =

  14. [22]

    1999 , publisher=

    Neural network learning: Theoretical foundations , author=. 1999 , publisher=

    1999

  15. [23]

    Morris, Christopher and Kriege, Nils M and Bause, Franka and Kersting, Kristian and Mutzel, Petra and Neumann, Marion , booktitle=

  16. [24]

    Journal of Medicinal Chemistry , volume=

    Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds , author=. Journal of Medicinal Chemistry , volume=

  17. [25]

    arXiv preprint arXiv:2410.03572 , year=

    Compressing multivariate functions with tree tensor networks , author=. arXiv preprint arXiv:2410.03572 , year=

    arXiv

  18. [26]

    Oseledets, Ivan and Tyrtyshnikov, Eugene , journal=

  19. [27]

    International Conference on Learning Representations , year=

    How powerful are graph neural networks? , author=. International Conference on Learning Representations , year=

  20. [28]

    Learning to understand: Identifying interactions via the M

    Kang, Justin and Erginbas, Yigit Efe and Butler, Landon and Pedarsani, Ramtin and Ramchandran, Kannan , journal=. Learning to understand: Identifying interactions via the M

  21. [29]

    1959 , publisher=

    A bargaining model for the cooperative n-person game , author=. 1959 , publisher=

    1959

  22. [30]

    Advances in Neural Information Processing Systems , volume=

    On the ability of graph neural networks to model interactions between vertices , author=. Advances in Neural Information Processing Systems , volume=

  23. [31]

    arXiv preprint arXiv:1606.05535 , year=

    Tensor ring decomposition , author=. arXiv preprint arXiv:1606.05535 , year=

    arXiv

  24. [32]

    Physical review letters , volume=

    Quantum entanglement in deep learning architectures , author=. Physical review letters , volume=. 2019 , publisher=

    2019

  25. [33]

    Computers & operations research , volume=

    Polynomial calculation of the Shapley value based on sampling , author=. Computers & operations research , volume=. 2009 , publisher=

    2009

  26. [34]

    doi:10.22331/q-2021-03-15-410 , url =

    Hyper-optimized tensor network contraction , author =. doi:10.22331/q-2021-03-15-410 , url =

    2021 doi

  27. [35]

    Hu, Edward J and Shen, Yelong and Wallis, Phillip and Allen-Zhu, Zeyuan and Li, Yuanzhi and Wang, Shean and Wang, Lu and Chen, Weizhu , booktitle=

  28. [36]

    IEEE Transactions on Pattern Analysis and Machine Intelligence , year=

    A Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study , author=. IEEE Transactions on Pattern Analysis and Machine Intelligence , year=

  29. [37]

    SIAM Review , volume =

    Tensor Decompositions and Applications , author =. SIAM Review , volume =. 2009 , publisher =

    2009

  30. [38]

    Evaluating Attribution for Graph Neural Networks , url =

    Sanchez-Lengeling, Benjamin and Wei, Jennifer and Lee, Brian and Reif, Emily and Wang, Peter and Qian, Wesley and McCloskey, Kevin and Colwell , Lucy and Wiltschko, Alexander , booktitle =. Evaluating Attribution for Graph Neural Networks , url =

  31. [39]

    2003 , Journal =

    Distinguishing enzyme structures from non-enzymes without alignments , Author =. 2003 , Journal =. doi:10.1016/s0022-2836(03)00628-4 , Number =

    2003 doi

  32. [40]

    arXiv preprint arXiv:1609.02907 , year=

    Semi-supervised classification with graph convolutional networks , author=. arXiv preprint arXiv:1609.02907 , year=

    arXiv

  33. [41]

    Advances in neural information processing systems , volume=

    Do transformers really perform badly for graph representation? , author=. Advances in neural information processing systems , volume=

  34. [42]

    RDKit: Open-source cheminformatics , author =

  35. [43]

    Scientific Data , volume=

    Evaluating explainability for graph neural networks , author=. Scientific Data , volume=. 2023 , publisher=

    2023

  36. [44]

    SMILES, a chemical language and information system. 1. Introduction to methodology and encoding rules , author=. Journal of chemical information and computer sciences , volume=. 1988 , publisher=

    1988

  37. [45]

    International Conference on Learning Representations , volume=

    Exact computation of any-order Shapley interactions for graph neural networks , author=. International Conference on Learning Representations , volume=

  38. [46]

    Bioinformatics , volume=

    Protein function prediction via graph kernels , author=. Bioinformatics , volume=. 2005 , publisher=

    2005

  39. [47]

    Yuriel Núñez Fernández and Marc K. Ritter and Matthieu Jeannin and Jheng-Wei Li and Thomas Kloss and Thibaud Louvet and Satoshi Terasaki and Olivier Parcollet and Jan von Delft and Hiroshi Shinaoka and Xavier Waintal , journal=. 2025 , publisher=. doi:10.21468/SciPostPhys.18.3...

    2025 doi

  40. [48]

    Oseledets, I. V. , title =. SIAM Journal on Scientific Computing , volume =. 2011 , doi =. https://doi.org/10.1137/090752286 , abstract =

    2011 doi

  41. [49]

    Advances in Neural Information Processing Systems , volume=

    Regression-adjusted monte carlo estimators for Shapley values and probabilistic values , author=. Advances in Neural Information Processing Systems , volume=

  42. [50]

    Advances in Neural Information Processing Systems , volume=

    Proxyspex: Inference-efficient interpretability via sparse feature interactions in LLMs , author=. Advances in Neural Information Processing Systems , volume=

  43. [51]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Beyond TreeSHAP: Efficient computation of any-order Shapley interactions for tree ensembles , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  44. [52]

    Advances in Neural Information Processing Systems , volume=

    Linear tree SHAP , author=. Advances in Neural Information Processing Systems , volume=

  45. [53]

    Advances in Neural Information Processing Systems , volume=

    SHAP meets tensor networks: Provably tractable explanations with parallelism , author=. Advances in Neural Information Processing Systems , volume=

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.