Research map / Graph learning / Graph self-supervised learning
Explaining Graph Neural Networks via Structure-aware Interaction Index
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 the Myerson-Taylor interaction index, a connectivity-aware generalization of the Shapley-Taylor index, and the MAGE explainer that uses it to find multiple positive and negative motifs in GNN predictions.
Problem
Shapley-based explanations of GNNs ignore graph connectivity when perturbing inputs (producing disconnected, OOD coalitions), focus on node-wise importance, and find only positive motifs, so they fail to capture multiple interacting explanatory substructures.
Approach
Replace the model with an interaction-restricted function that sums over connected components, so the second-order Shapley-Taylor interaction is computed only over connected coalitions (Myerson-Taylor index); then select multiple connected motifs by maximizing the sum of absolute pairwise group attributions via a MILP.
Key results
- MAGE improves F1 by 58.64% on single-motif datasets and AMI by 28.11% on multi-motif datasets relative to the best baseline.
- MAGE achieves about 12.5% higher AUC on average across datasets with ground-truth explanations.
- On sentiment datasets without ground truth, MAGE achieves about 14% higher fidelity than the best baselines while using fewer GNN queries than other game-based methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAGE instead of the best baseline | GNN explanations · Single-motif datasets | F1: 58.64% | Helped |
| Use MAGE instead of the best baseline | GNN explanations · Multi-motif datasets | AMI: 28.11% | Helped |
| Use MAGE instead of the best baseline | GNN explanations · All datasets with ground-truth explanations | AUC: 12.51% | Helped |
| Use MAGE instead of the best baseline | GNN explanations · GraphSST2 and Twitter | Fidelity: 14% | Helped |
| Use MAGE instead of GradCAM | GNN explanations · Datasets with ground-truth explanations | AUC: 17% | Helped |
| Use MAGE instead of GradCAM | GNN explanations · Single-motif datasets | F1: 65% | Helped |
| Replace the second-order Myerson-Taylor index with the second-order Shapley-Taylor index (ablation) | MAGE · BA-2Motifs and BA-HouseGrid | explanation accuracy | Hurt |
| Remove the connectivity constraint on explanatory motifs (ablation) | MAGE · BA-2Motifs and BA-HouseGrid | explanation accuracy | Hurt |
Surprising findings
- Explanations that include negative motifs (e.g., a five-cycle that misleads toward the house class) can be identified, providing counterfactual-style reasoning.
Limitations
- Exact computation is exponential in the number of nodes; Monte Carlo sampling is needed in practice.
- Treating the GNN as a black box permits information sharing among nodes in a connected component, which does not match layer-restricted message passing.
- Motif optimization relies on a MILP solver (MOSEK/Gurobi), which adds cost.
Experimental setup
Datasets: BA-2Motifs BA-HouseGrid SPMotif MNIST75SP BA-HouseAndGrid BA-HouseOrGrid Mutagenic Benzene GraphSST2 Twitter
Benchmarks: BA-2Motifs BA-HouseGrid SPMotif MNIST75SP BA-HouseAndGrid BA-HouseOrGrid Mutagenic Benzene GraphSST2 Twitter
Metrics: F1 AMI AUC Fidelity Fidelity-alpha number of GNN queries
Baselines: GNNExplainer PGExplainer Refine MatchExplainer SubgraphX GStarX SAME GradCAM
Builds on: Shapley value Shapley-Taylor interaction index Myerson value SubgraphX GNNExplainer
Closest papers by meaning
- Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks (ICLR 2025 · similarity 0.90)
- Higher Order Structures for Graph Explanations (AAAI 2025 · similarity 0.90)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.89)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.87)
- Factorized Explainer for Graph Neural Networks (AAAI 2024 · similarity 0.87)
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.87)
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.