# Explaining Graph Neural Networks via Structure-aware Interaction Index

arXiv: https://arxiv.org/abs/2405.14352 · HTML: https://mlsanity.com/paper/2405.14352/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 75 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 30 of 48)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [AllenNLP: A Deep Semantic Natural Language Processing Platform](https://mlsanity.com/paper/1803.07640/) (2018)
- [Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud](https://mlsanity.com/paper/2003.01251/) (2020)
- [On the (In)fidelity and Sensitivity for Explanations](https://mlsanity.com/paper/1901.09392/) (2019)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Discovering Invariant Rationales for Graph Neural Networks](https://mlsanity.com/paper/2201.12872/) (2022)
- [Vision GNN: An Image is Worth Graph of Nodes](https://mlsanity.com/paper/2206.00272/) (2022)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Not All Points Are Equal: Learning Highly Efficient Point-based Detectors for 3D LiDAR Point Clouds](https://mlsanity.com/paper/2203.11139/) (2022)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)

## Built on by (most cited first, 11 of 11)

- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [Towards Understanding Sensitive and Decisive Patterns in Explainable AI: A Case Study of Model Interpretation in Geometric Deep Learning](https://mlsanity.com/paper/2407.00849/) (2024)
- [Towards Faithful Class-level Self-explainability in Graph Neural Networks by Subgraph Dependencies](https://mlsanity.com/paper/2508.11513/) (2025)
- [TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration](https://mlsanity.com/paper/2510.05102/) (2025)
- [The Representational Limit of Scalar Interactions: An Interventional Decomposition](https://mlsanity.com/paper/2606.19410/) (2026)
- [MBExplainer: Multilevel bandit-based explanations for downstream models with augmented graph embeddings](https://mlsanity.com/paper/2411.00287/) (2024)
- [Model-Level GNN Explanations via Rule-to-Graph Readout for Logit Reconstruction](https://mlsanity.com/paper/2503.09051/) (2025)
- [ARM-Explainer -- Explaining and improving graph neural network predictions for the maximum clique problem using node features and association rule mining](https://mlsanity.com/paper/2511.22866/) (2025)
- [Beyond Soft Masks: Hard-Perturbation Mixup Explainer for Robust GNN Explainability](https://mlsanity.com/paper/2606.05756/) (2026)
- [Automorphism-Induced Non-Canonicity in Top-k Explanations of Graph Neural Networks](https://mlsanity.com/paper/2607.26344/) (2026)
- [Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark](https://mlsanity.com/paper/2610.03526/) (2026)

## Abstract (arXiv)

The Shapley value is a prominent tool for interpreting black-box machine learning models thanks to its strong theoretical foundation. However, for models with structured inputs, such as graph neural networks, existing Shapley-based explainability approaches either focus solely on node-wise importance or neglect the graph structure when perturbing the input instance. This paper introduces the Myerson-Taylor interaction index that internalizes the graph structure into attributing the node values and the interaction values among nodes. Unlike the Shapley-based methods, the Myerson-Taylor index decomposes coalitions into components satisfying a pre-chosen connectivity criterion. We prove that the Myerson-Taylor index is the unique one that satisfies a system of five natural axioms accounting for graph structure and high-order interaction among nodes. Leveraging these properties, we propose Myerson-Taylor Structure-Aware Graph Explainer (MAGE), a novel explainer that uses the second-order Myerson-Taylor index to identify the most important motifs influencing the model prediction, both positively and negatively. Extensive experiments on various graph datasets and models demonstrate that our method consistently provides superior subgraph explanations compared to state-of-the-art methods.