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

• URL: http://arxiv.org/abs/2606.01540v1
• Date: Mon, 01 Jun 2026 01:41:29 GMT
• Title: TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions
• Abstract summary: We propose a framework that exploits structure in graph-structured inputs to compute Shapley values and higher-order interaction indices efficiently.<n>We 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.
• Score: 6.149584741927582
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  Shapley Interactions (SIs) quantify node contributions and interactions among multiple nodes.<n>By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction.<n>We introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly.
  arXiv  Detail & Related papers  (2025-01-28T13:37:44Z)
• From Primes to Paths: Enabling Fast Multi-Relational Graph Analysis [5.008498268411793]
  Multi-relational networks capture intricate relationships in data and have diverse applications across fields such as biomedical, financial, and social sciences. This work extends the Prime Adjacency Matrices framework, which employs prime numbers to represent distinct relations within a network uniquely.
  arXiv  Detail & Related papers  (2024-11-17T18:43:01Z)
• ShapG: new feature importance method based on the Shapley value [3.411077163447709]
  We propose a new Explainable Artificial Intelligence (XAI) method called ShapG (Explanations based on Shapley value for Graphs) for measuring feature importance.<n>At the first stage, it defines an undirected graph based on the dataset, where nodes represent features and edges are added.<n>At the second stage, it calculates an approximated Shapley value by sampling the data taking into account this graph structure.
  arXiv  Detail & Related papers  (2024-06-29T18:19:55Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• MTS2Graph: Interpretable Multivariate Time Series Classification with Temporal Evolving Graphs [1.1756822700775666]
  We introduce a new framework for interpreting time series data by extracting and clustering the input representative patterns. We run experiments on eight datasets of the UCR/UEA archive, along with HAR and PAM datasets.
  arXiv  Detail & Related papers  (2023-06-06T16:24:27Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• Optimising for Interpretability: Convolutional Dynamic Alignment Networks [108.83345790813445]
  We introduce a new family of neural network models called Convolutional Dynamic Alignment Networks (CoDA Nets) Their core building blocks are Dynamic Alignment Units (DAUs), which are optimised to transform their inputs with dynamically computed weight vectors that align with task-relevant patterns. CoDA Nets model the classification prediction through a series of input-dependent linear transformations, allowing for linear decomposition of the output into individual input contributions.
  arXiv  Detail & Related papers  (2021-09-27T12:39:46Z)
• T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs [0.0]
  In graph-structured data, structured sparsity and smoothness tend to cluster together. We propose a new prior for high dimensional parameters with graphical relations. We use it to detect structured sparsity and smoothness simultaneously.
  arXiv  Detail & Related papers  (2021-07-06T10:10:03Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Supervised Learning for Non-Sequential Data: A Canonical Polyadic Decomposition Approach [85.12934750565971]
  Efficient modelling of feature interactions underpins supervised learning for non-sequential tasks. To alleviate this issue, it has been proposed to implicitly represent the model parameters as a tensor. For enhanced expressiveness, we generalize the framework to allow feature mapping to arbitrarily high-dimensional feature vectors.
  arXiv  Detail & Related papers  (2020-01-27T22:38:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.