# Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 51 references that are in the map.
- First posted on arXiv 18 May 2021.

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

- [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)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [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)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (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)
- [Layer-wise Relevance Propagation for Neural Networks with Local Renormalization Layers](https://mlsanity.com/paper/1604.00825/) (2016)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [Learning to Deceive with Attention-Based Explanations](https://mlsanity.com/paper/1909.07913/) (2019)
- [Aligning Faithful Interpretations with their Social Attribution](https://mlsanity.com/paper/2006.01067/) (2020)
- [GraphSVX: Shapley Value Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.10482/) (2021)
- [What made you do this? Understanding black-box decisions with sufficient input subsets](https://mlsanity.com/paper/1810.03805/) (2018)

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

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Private Graph Extraction via Feature Explanations](https://mlsanity.com/paper/2206.14724/) (2022)
- [GNNShap: Scalable and Accurate GNN Explanation using Shapley Values](https://mlsanity.com/paper/2401.04829/) (2024)
- [BAGEL: A Benchmark for Assessing Graph Neural Network Explanations](https://mlsanity.com/paper/2206.13983/) (2022)
- [Graph Neural Network Causal Explanation via Neural Causal Models](https://mlsanity.com/paper/2407.09378/) (2024)
- [DINE: Dimensional Interpretability of Node Embeddings](https://mlsanity.com/paper/2310.01162/) (2023)
- [L2XGNN: Learning to Explain Graph Neural Networks](https://mlsanity.com/paper/2209.14402/) (2022)
- [MEGAN: Multi-Explanation Graph Attention Network](https://mlsanity.com/paper/2211.13236/) (2022)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [AGMN: Association Graph-based Graph Matching Network for Coronary Artery Semantic Labeling on Invasive Coronary Angiograms](https://mlsanity.com/paper/2301.04733/) (2023)
- [Privacy and Transparency in Graph Machine Learning: A Unified Perspective](https://mlsanity.com/paper/2207.10896/) (2022)
- [Learnt Sparsification for Interpretable Graph Neural Networks](https://mlsanity.com/paper/2106.12920/) (2021)
- [ViGAT: Bottom-up event recognition and explanation in video using factorized graph attention network](https://mlsanity.com/paper/2207.09927/) (2022)
- [On the Limit of Explaining Black-box Temporal Graph Neural Networks](https://mlsanity.com/paper/2212.00952/) (2022)
- [On Pitfalls of textitRemOve-And-Retrain: Data Processing Inequality Perspective](https://mlsanity.com/paper/2304.13836/) (2023)
- [Coronary Artery Semantic Labeling using Edge Attention Graph Matching Network](https://mlsanity.com/paper/2305.12327/) (2023)
- [Semantic Interpretation and Validation of Graph Attention-based Explanations for GNN Models](https://mlsanity.com/paper/2308.04220/) (2023)
- [Counterfactual Explanations for Graph Classification Through the Lenses of Density](https://mlsanity.com/paper/2307.14849/) (2023)
- [Multi-graph Graph Matching for Coronary Artery Semantic Labeling](https://mlsanity.com/paper/2402.15894/) (2024)
- [SparCAssist: A Model Risk Assessment Assistant Based on Sparse Generated Counterfactuals](https://mlsanity.com/paper/2205.01588/) (2022)
- [EMaP: Explainable AI with Manifold-based Perturbations](https://mlsanity.com/paper/2209.08453/) (2022)
- [On the Feasibility of Fidelity^- for Graph Pruning](https://mlsanity.com/paper/2406.11504/) (2024)
- [Disentangled and Self-Explainable Node Representation Learning](https://mlsanity.com/paper/2410.21043/) (2024)
- [Statistical Test for Saliency Maps of Graph Neural Networks via Selective Inference](https://mlsanity.com/paper/2505.16893/) (2025)
- [Explainable Graph Neural Networks via Structural Externalities](https://mlsanity.com/paper/2507.17848/) (2025)
- [GRExplainer: A Universal Explanation Method for Temporal Graph Neural Networks](https://mlsanity.com/paper/2512.22772/) (2025)
- [InteractiveGNNExplainer: A Visual Analytics Framework for Multi-Faceted Understanding and Probing of Graph Neural Network Predictions](https://mlsanity.com/paper/2511.13160/) (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)

## Abstract (arXiv)

With the ever-increasing popularity and applications of graph neural networks, several proposals have been made to explain and understand the decisions of a graph neural network. Explanations for graph neural networks differ in principle from other input settings. It is important to attribute the decision to input features and other related instances connected by the graph structure. We find that the previous explanation generation approaches that maximize the mutual information between the label distribution produced by the model and the explanation to be restrictive. Specifically, existing approaches do not enforce explanations to be valid, sparse, or robust to input perturbations. In this paper, we lay down some of the fundamental principles that an explanation method for graph neural networks should follow and introduce a metric RDT-Fidelity as a measure of the explanation's effectiveness. We propose a novel approach Zorro based on the principles from rate-distortion theory that uses a simple combinatorial procedure to optimize for RDT-Fidelity. Extensive experiments on real and synthetic datasets reveal that Zorro produces sparser, stable, and more faithful explanations than existing graph neural network explanation approaches.