Research map / Graph learning / GNN architectures
Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces GraphSHAP-IQ, which exactly computes any-order Shapley interactions for GNN graph predictions by exploiting receptive-field invariance under linear pooling and readout, and evaluates approximations against baselines on chemical and water-network datasets.
Problem
Explaining GNN graph predictions with Shapley values and interactions is exponentially expensive in the number of nodes, and existing methods are approximate, subgraph-based, or model-agnostic.
Approach
Under linear global pooling and output layer, a GNN-induced node game is invariant to masking outside the receptive field, so Möbius interactions vanish for node subsets not contained in any l-hop neighborhood; this sparsity reduces exact SI computation to the number of non-trivial subsets, scaling roughly linearly with graph size.
Key results
- Exact any-order SIs on 1-2 layer GNNs need fewer than 10^5 model calls for many graphs with more than 100 nodes, where the model-agnostic baseline needs over 10^30.
- Complexity grows approximately linearly with graph size, with high R^2 for log-linear fits across the benchmark datasets.
- For MTG with 30 nodes, GraphSHAP-IQ needs 7,693 model calls versus 2^30 (about 10^9) for exact computation by brute force.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraphSHAP-IQ instead of model-agnostic exact computation | Exact Shapley interactions on graph classification benchmarks · BNZ, FLC, MTG, ALC, PRT, ENZ, CX2, BZR | model-call speedup | Helped |
| Use GraphSHAP-IQ instead of model-agnostic computation | Exact Shapley interactions on large graphs · Graphs with more than 100 nodes | model calls: over 10^30 model calls; fewer than 10^5 evaluations | Helped |
| Use interaction-informed variants of baselines | Approximation methods for Shapley interactions · MTG, PRT, BZR | approximation quality and runtime | Helped |
| Use GraphSHAP-IQ rather than approximation baselines | Approximation of Shapley interactions with a majority of lower-order Möbius interactions · MTG, PRT, BZR | MSE | Helped |
| Increase the explanation order | GraphSHAP-IQ · Approximation at the ground-truth budget | runtime | No clear effect |
| Use a nonlinear two-layer perceptron readout instead of a linear readout (ablation) | 2-layer GCN trained on MTG · MTG | interaction support outside receptive fields | Mixed |
Surprising findings
- Non-linear readouts (2-layer perceptron) produce Möbius interactions outside the receptive field, breaking the sparsity property.
Limitations
- Requires linear global pooling and linear output layer (Assumption); non-linear readouts break the sparsity guarantee.
- Complexity still grows exponentially with receptive-field size and node degree, so dense graphs or deep GNNs can remain infeasible.
- Relies on a fixed baseline masking strategy (baseline imputation) rather than alternatives like subgraph removal.
Experimental setup
Datasets: BNZ FLC MTG ALC PRT ENZ CX2 BZR Hanoi WDS water quality dataset (WAQ)
Benchmarks: MTG PRT BZR BNZ FLC ALC ENZ CX2 WAQ
Metrics: number of model calls MSE of interaction approximation runtime test accuracy
Baselines: KernelSHAP Unbiased KernelSHAP k-additive SHAP Permutation Sampling SVARM L-Shapley KernelSHAP-IQ SHAP-IQ SVARM-IQ GraphSVX SubgraphX
Builds on: Shapley values Shapley interactions (SII, k-SII, STII, FSII) TreeSHAP L-Shapley KernelSHAP
Closest papers by meaning
- Explaining Graph Neural Networks via Structure-aware Interaction Index (ICML 2024 · similarity 0.90)
- Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.89)
- Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation (ICLR 2025 · similarity 0.87)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.86)
- GOAt: Explaining Graph Neural Networks via Graph Output Attribution (ICLR 2024 · similarity 0.86)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.86)
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.