# Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 16 Jun 2021.

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

- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [ERASER: A Benchmark to Evaluate Rationalized NLP Models](https://mlsanity.com/paper/1911.03429/) (2019)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (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)
- [Regularisation of Neural Networks by Enforcing Lipschitz Continuity](https://mlsanity.com/paper/1804.04368/) (2018)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (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)
- [One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques](https://mlsanity.com/paper/1909.03012/) (2019)
- [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)
- [Inherent Tradeoffs in Learning Fair Representations](https://mlsanity.com/paper/1906.08386/) (2019)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [Fairwashing: the risk of rationalization](https://mlsanity.com/paper/1901.09749/) (2019)
- [Robust and Stable Black Box Explanations](https://mlsanity.com/paper/2011.06169/) (2020)
- [Towards the Unification and Robustness of Perturbation and Gradient Based Explanations](https://mlsanity.com/paper/2102.10618/) (2021)
- [To trust or not to trust an explanation: using LEAF to evaluate local linear XAI methods](https://mlsanity.com/paper/2106.00461/) (2021)

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

- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Rethinking Stability for Attribution-based Explanations](https://mlsanity.com/paper/2203.06877/) (2022)
- [Encoding Time-Series Explanations through Self-Supervised Model Behavior Consistency](https://mlsanity.com/paper/2306.02109/) (2023)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [On the Robustness of Removal-Based Feature Attributions](https://mlsanity.com/paper/2306.07462/) (2023)
- [PowerGraph: A power grid benchmark dataset for graph neural networks](https://mlsanity.com/paper/2402.02827/) (2024)
- [Distill n' Explain: explaining graph neural networks using simple surrogates](https://mlsanity.com/paper/2303.10139/) (2023)
- [A Comprehensive Survey on Self-Interpretable Neural Networks](https://mlsanity.com/paper/2501.15638/) (2025)
- [GInX-Eval: Towards In-Distribution Evaluation of Graph Neural Network Explanations](https://mlsanity.com/paper/2309.16223/) (2023)
- [L2XGNN: Learning to Explain Graph Neural Networks](https://mlsanity.com/paper/2209.14402/) (2022)
- [Towards Training GNNs using Explanation Directed Message Passing](https://mlsanity.com/paper/2211.16731/) (2022)
- [DT+GNN: A Fully Explainable Graph Neural Network using Decision Trees](https://mlsanity.com/paper/2205.13234/) (2022)
- [A Sea of Words: An In-Depth Analysis of Anchors for Text Data](https://mlsanity.com/paper/2205.13789/) (2022)
- [Analyzing Explainer Robustness via Probabilistic Lipschitzness of Prediction Functions](https://mlsanity.com/paper/2206.12481/) (2022)
- [Rethinking Explainability in the Era of Multimodal AI](https://mlsanity.com/paper/2506.13060/) (2025)
- [Explainable Graph Neural Networks Under Fire](https://mlsanity.com/paper/2406.06417/) (2024)
- [ViGAT: Bottom-up event recognition and explanation in video using factorized graph attention network](https://mlsanity.com/paper/2207.09927/) (2022)
- [Graph AI in Medicine](https://mlsanity.com/paper/2310.13767/) (2023)
- [Iterative Graph Neural Network Enhancement via Frequent Subgraph Mining of Explanations](https://mlsanity.com/paper/2403.07849/) (2024)
- [Quantifying Explanation Quality in Graph Neural Networks using Out-of-Distribution Generalization](https://mlsanity.com/paper/2602.07708/) (2026)
- [Evaluating Link Prediction Explanations for Graph Neural Networks](https://mlsanity.com/paper/2308.01682/) (2023)
- [Explaining GNN Explanations with Edge Gradients](https://mlsanity.com/paper/2508.01048/) (2025)
- [Uncertainty Quantification for Local Model Explanations Without Model Access](https://mlsanity.com/paper/2301.05761/) (2023)
- [GNNBleed: Inference Attacks to Unveil Private Edges in Graphs with Realistic Access to GNN Models](https://mlsanity.com/paper/2311.16139/) (2023)
- [Introducing Diminutive Causal Structure into Graph Representation Learning](https://mlsanity.com/paper/2406.08709/) (2024)
- [On the Feasibility of Fidelity^- for Graph Pruning](https://mlsanity.com/paper/2406.11504/) (2024)
- [Database Views as Explanations for Relational Deep Learning](https://mlsanity.com/paper/2509.09482/) (2025)
- [On Discprecncies between Perturbation Evaluations of Graph Neural Network Attributions](https://mlsanity.com/paper/2401.00633/) (2024)

## Abstract (arXiv)

As Graph Neural Networks (GNNs) are increasingly being employed in critical real-world applications, several methods have been proposed in recent literature to explain the predictions of these models. However, there has been little to no work on systematically analyzing the reliability of these methods. Here, we introduce the first-ever theoretical analysis of the reliability of state-of-the-art GNN explanation methods. More specifically, we theoretically analyze the behavior of various state-of-the-art GNN explanation methods with respect to several desirable properties (e.g., faithfulness, stability, and fairness preservation) and establish upper bounds on the violation of these properties. We also empirically validate our theoretical results using extensive experimentation with nine real-world graph datasets. Our empirical results further shed light on several interesting insights about the behavior of state-of-the-art GNN explanation methods.