# On Explainability of Graph Neural Networks via Subgraph Explorations

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

## Key facts

- Cited by 281 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 52 references that are in the map.
- First posted on arXiv 9 Feb 2021.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Learning Deep Features for Discriminative Localization](https://mlsanity.com/paper/1512.04150/) (2015)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [Striving for Simplicity: The All Convolutional Net](https://mlsanity.com/paper/1412.6806/) (2014)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (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)
- [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)
- [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)
- [Large-Scale Learnable Graph Convolutional Networks](https://mlsanity.com/paper/1808.03965/) (2018)
- [L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data](https://mlsanity.com/paper/1808.02610/) (2018)
- [Advanced Graph and Sequence Neural Networks for Molecular Property Prediction and Drug Discovery](https://mlsanity.com/paper/2012.01981/) (2020)
- [XFake: Explainable Fake News Detector with Visualizations](https://mlsanity.com/paper/1907.07757/) (2019)
- [Layerwise Relevance Visualization in Convolutional Text Graph Classifiers](https://mlsanity.com/paper/1909.10911/) (2019)
- [Towards Explanation of DNN-based Prediction with Guided Feature Inversion](https://mlsanity.com/paper/1804.00506/) (2018)
- [Node2Seq: Towards Trainable Convolutions in Graph Neural Networks](https://mlsanity.com/paper/2101.01849/) (2021)

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

- [Discovering Invariant Rationales for Graph Neural Networks](https://mlsanity.com/paper/2201.12872/) (2022)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Causal Attention for Interpretable and Generalizable Graph Classification](https://mlsanity.com/paper/2112.15089/) (2021)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [ProtGNN: Towards Self-Explaining Graph Neural Networks](https://mlsanity.com/paper/2112.00911/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [Debiasing Graph Neural Networks via Learning Disentangled Causal Substructure](https://mlsanity.com/paper/2209.14107/) (2022)
- [DIG: A Turnkey Library for Diving into Graph Deep Learning Research](https://mlsanity.com/paper/2103.12608/) (2021)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Improving Subgraph Recognition with Variational Graph Information Bottleneck](https://mlsanity.com/paper/2112.09899/) (2021)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [A Survey on Graph-Based Deep Learning for Computational Histopathology](https://mlsanity.com/paper/2107.00272/) (2021)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks](https://mlsanity.com/paper/2105.08621/) (2021)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [Reinforced Causal Explainer for Graph Neural Networks](https://mlsanity.com/paper/2204.11028/) (2022)
- [GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks](https://mlsanity.com/paper/2209.07924/) (2022)
- [OrphicX: A Causality-Inspired Latent Variable Model for Interpreting Graph Neural Networks](https://mlsanity.com/paper/2203.15209/) (2022)
- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [Joint Learning of Label and Environment Causal Independence for Graph Out-of-Distribution Generalization](https://mlsanity.com/paper/2306.01103/) (2023)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [Interpretable Geometric Deep Learning via Learnable Randomness Injection](https://mlsanity.com/paper/2210.16966/) (2022)
- [DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks](https://mlsanity.com/paper/2303.02448/) (2023)
- [TempME: Towards the Explainability of Temporal Graph Neural Networks via Motif Discovery](https://mlsanity.com/paper/2310.19324/) (2023)
- [A Survey of Explainable Graph Neural Networks: Taxonomy and Evaluation Metrics](https://mlsanity.com/paper/2207.12599/) (2022)

## Abstract (arXiv)

We consider the problem of explaining the predictions of graph neural networks (GNNs), which otherwise are considered as black boxes. Existing methods invariably focus on explaining the importance of graph nodes or edges but ignore the substructures of graphs, which are more intuitive and human-intelligible. In this work, we propose a novel method, known as SubgraphX, to explain GNNs by identifying important subgraphs. Given a trained GNN model and an input graph, our SubgraphX explains its predictions by efficiently exploring different subgraphs with Monte Carlo tree search. To make the tree search more effective, we propose to use Shapley values as a measure of subgraph importance, which can also capture the interactions among different subgraphs. To expedite computations, we propose efficient approximation schemes to compute Shapley values for graph data. Our work represents the first attempt to explain GNNs via identifying subgraphs explicitly and directly. Experimental results show that our SubgraphX achieves significantly improved explanations, while keeping computations at a reasonable level.