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

Abstract:

While Shapley values are a prevalent method for quantifying the significance and interplay of input variables in black-box models, their calculation is computationally demanding due to the need to evaluate a function across an exponentially vast space of subsets. To address this, we introduce TN-SHAP-G, a novel framework designed to efficiently derive Shapley values and higher-order interaction metrics by leveraging the inherent structure of graph-based inputs.

TN-SHAP-G constructs a compact, graph-aligned multilinear surrogate to approximate how the model behaves under a specified masking scheme. This surrogate is represented as a tensor network, with a topology that directly reflects the input graph’s structure. After being trained using only a limited number of oracle queries, the surrogate allows for the deterministic extraction of first- and higher-order Shapley indices through the multilinear extension. This process eliminates the need for further model queries and avoids the statistical noise associated with Monte Carlo methods.

Our experiments on molecular benchmarks demonstrate that the learned factorization aligns closely with exact Shapley values for small graphs. Furthermore, the approach scales effectively to larger graphs, where traditional sampling-based techniques are often impractical.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC