# GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 28 Jan 2022.

## Builds on (most cited first, 25 of 25)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [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)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Real Time Image Saliency for Black Box Classifiers](https://mlsanity.com/paper/1705.07857/) (2017)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (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)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data](https://mlsanity.com/paper/1808.02610/) (2018)
- [DIG: A Turnkey Library for Diving into Graph Deep Learning Research](https://mlsanity.com/paper/2103.12608/) (2021)
- [GraphSVX: Shapley Value Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.10482/) (2021)
- [Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks](https://mlsanity.com/paper/2105.08621/) (2021)
- [Knowing your FATE: Friendship, Action and Temporal Explanations for User Engagement Prediction on Social Apps](https://mlsanity.com/paper/2006.06427/) (2020)

## Built on by (most cited first, 30 of 42)

- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous Link Prediction](https://mlsanity.com/paper/2302.12465/) (2023)
- [Graph Neural Network Explanations are Fragile](https://mlsanity.com/paper/2406.03193/) (2024)
- [Distill n' Explain: explaining graph neural networks using simple surrogates](https://mlsanity.com/paper/2303.10139/) (2023)
- [Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks](https://mlsanity.com/paper/2310.01820/) (2023)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [GNNShap: Scalable and Accurate GNN Explanation using Shapley Values](https://mlsanity.com/paper/2401.04829/) (2024)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [Path-based Explanation for Knowledge Graph Completion](https://mlsanity.com/paper/2401.02290/) (2024)
- [Explaining Graph Neural Networks via Structure-aware Interaction Index](https://mlsanity.com/paper/2405.14352/) (2024)
- [GOAt: Explaining Graph Neural Networks via Graph Output Attribution](https://mlsanity.com/paper/2401.14578/) (2024)
- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [Factorized Explainer for Graph Neural Networks](https://mlsanity.com/paper/2312.05596/) (2023)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [Efficient GNN Explanation via Learning Removal-based Attribution](https://mlsanity.com/paper/2306.05760/) (2023)
- [Generating Explanations to Understand and Repair Embedding-based Entity Alignment](https://mlsanity.com/paper/2312.04877/) (2023)
- [EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time](https://mlsanity.com/paper/2405.01762/) (2024)
- [Generating Robust Counterfactual Witnesses for Graph Neural Networks](https://mlsanity.com/paper/2404.19519/) (2024)
- [Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks](https://mlsanity.com/paper/2402.02036/) (2024)
- [Towards Unified Attribution in Explainable AI, Data-Centric AI, and Mechanistic Interpretability](https://mlsanity.com/paper/2501.18887/) (2025)
- [Game-theoretic Counterfactual Explanation for Graph Neural Networks](https://mlsanity.com/paper/2402.06030/) (2024)
- [Automated Molecular Concept Generation and Labeling with Large Language Models](https://mlsanity.com/paper/2406.09612/) (2024)
- [eXpath: Explaining Knowledge Graph Link Prediction with Ontological Closed Path Rules](https://mlsanity.com/paper/2412.04846/) (2024)
- [GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability](https://mlsanity.com/paper/2509.18376/) (2025)
- [Message-passing selection: Towards interpretable GNNs for graph classification](https://mlsanity.com/paper/2306.02081/) (2023)
- [GRExplainer: A Universal Explanation Method for Temporal Graph Neural Networks](https://mlsanity.com/paper/2512.22772/) (2025)
- [PAGE: Parametric Generative Explainer for Graph Neural Network](https://mlsanity.com/paper/2408.14042/) (2024)
- [STX-Search: Explanation Search for Continuous Dynamic Spatio-Temporal Models](https://mlsanity.com/paper/2503.04509/) (2025)

## Abstract (arXiv)

Explaining machine learning models is an important and increasingly popular area of research interest. The Shapley value from game theory has been proposed as a prime approach to compute feature importance towards model predictions on images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for GNN explanation, where the task is to identify the most important subgraph and constituent nodes for GNN predictions. We claim that the Shapley value is a non-ideal choice for graph data because it is by definition not structure-aware. We propose a Graph Structure-aware eXplanation (GStarX) method to leverage the critical graph structure information to improve the explanation. Specifically, we define a scoring function based on a new structure-aware value from the cooperative game theory proposed by Hamiache and Navarro (HN). When used to score node importance, the HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, resembling message passing in GNNs, so that node importance scores reflect not only the node feature importance, but also the node structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity over strong baselines on chemical graph property prediction and text graph sentiment classification.