Research map / Graph learning / Graph algorithms and clustering
TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions
Farzaneh Heidari, Guillaume Rabusseau
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use structure-aware coalition sampling (edge-flip and triangle-flip neighbors) instead of uniform (ablation) | TN-SHAP-G · higher-order (O3) interaction recovery | O3 cosine similarity: 0.48 -> 0.91 | Improved |
| use graph-aligned tensor network instead of tensor train (TT) under parameter matching (ablation) | TN-SHAP-G · molecular graphs, low query budget (10n coalitions) | O1/O2 cosine similarity | Improved |
| vary TT node ordering (default, BFS, random) in the tensor train baseline (ablation) | TT surrogate · molecular graphs | attribution cosine similarity | Hurt |
| replace GraphSVX with TN-SHAP-G for first-order Shapley on small graphs | Benzene · Benzene | O1 cosine similarity: 0.30 -> 0.9979 | Improved |
| replace GraphSVX with TN-SHAP-G for first-order Shapley on small graphs | Mutagenicity · Mutagenicity | O1 cosine similarity: 0.45 -> 0.9933 | Improved |
| use TN-SHAP-G instead of permutation sampling and SHAP-IQ at matched budgets | molecular benchmarks · Mutagenicity, Benzene, PROTEINS | queries to reach 0.95 cosine: 10-100x fewer queries | Improved |
| amortize one trained surrogate over repeated explanation queries vs GraphSHAP-IQ | TN-SHAP-G · Mutagenicity (20 graphs, n<=20) | total time: K=1: 197.8 s vs 11.6 s; K=100: 406.7 s vs 1158.1 s | Mixed |
| increase surrogate test R2 (more epochs/capacity) | TN-SHAP-G · molecular graphs | Shapley cosine similarity | Improved |
| use coarsening architecture to scale to larger graphs | TN-SHAP-G · graphs of 100 to 600 nodes | training time scaling: T ~ n^2.30 training; T_Shapley ~ n^0.57 | Improved |
Closest papers by meaning
- SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism (NeurIPS 2025 · similarity 0.88)
- Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks (ICLR 2025 · similarity 0.88)
- Explaining Graph Neural Networks via Structure-aware Interaction Index (ICML 2024 · similarity 0.86)
- Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation (ICLR 2025 · similarity 0.85)
- Proxy-Based Approximation of Shapley and Banzhaf Interactions (NeurIPS 2026 · similarity 0.85)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
