# Robust Counterfactual Explanations on Graph Neural Networks

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

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 54 references that are in the map.
- First posted on arXiv 8 Jul 2021.

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

- [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)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (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)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Top-down Neural Attention by Excitation Backprop](https://mlsanity.com/paper/1608.00507/) (2016)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Adversarial Attacks and Defenses in Images, Graphs and Text: A Review](https://mlsanity.com/paper/1909.08072/) (2019)
- [One-Shot Imitation Learning](https://mlsanity.com/paper/1703.07326/) (2017)
- [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)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Maxout Networks](https://mlsanity.com/paper/1302.4389/) (2013)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Causal Interpretability for Machine Learning -- Problems, Methods and Evaluation](https://mlsanity.com/paper/2003.03934/) (2020)
- [DIG: A Turnkey Library for Diving into Graph Deep Learning Research](https://mlsanity.com/paper/2103.12608/) (2021)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [Certifiable Robustness and Robust Training for Graph Convolutional Networks](https://mlsanity.com/paper/1906.12269/) (2019)
- [Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints](https://mlsanity.com/paper/1311.2106/) (2013)
- [Exact and Consistent Interpretation for Piecewise Linear Neural Networks: A Closed Form Solution](https://mlsanity.com/paper/1802.06259/) (2018)

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

- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [Transport-based Counterfactual Models](https://mlsanity.com/paper/2108.13025/) (2021)
- [A Survey of Explainable Graph Neural Networks: Taxonomy and Evaluation Metrics](https://mlsanity.com/paper/2207.12599/) (2022)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [FlowX: Towards Explainable Graph Neural Networks via Message Flows](https://mlsanity.com/paper/2206.12987/) (2022)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation](https://mlsanity.com/paper/2309.12545/) (2023)
- [A Framework and Benchmarking Study for Counterfactual Generating Methods on Tabular Data](https://mlsanity.com/paper/2107.04680/) (2021)
- [PowerGraph: A power grid benchmark dataset for graph neural networks](https://mlsanity.com/paper/2402.02827/) (2024)
- [Encoding Concepts in Graph Neural Networks](https://mlsanity.com/paper/2207.13586/) (2022)
- [Distill n' Explain: explaining graph neural networks using simple surrogates](https://mlsanity.com/paper/2303.10139/) (2023)
- [F-Fidelity: A Robust Framework for Faithfulness Evaluation of Explainable AI](https://mlsanity.com/paper/2410.02970/) (2024)
- [Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks](https://mlsanity.com/paper/2310.01820/) (2023)
- [MotifExplainer: a Motif-based Graph Neural Network Explainer](https://mlsanity.com/paper/2202.00519/) (2022)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [GOAt: Explaining Graph Neural Networks via Graph Output Attribution](https://mlsanity.com/paper/2401.14578/) (2024)
- [A.I. Robustness: a Human-Centered Perspective on Technological Challenges and Opportunities](https://mlsanity.com/paper/2210.08906/) (2022)
- [GInX-Eval: Towards In-Distribution Evaluation of Graph Neural Network Explanations](https://mlsanity.com/paper/2309.16223/) (2023)
- [Deep Backtracking Counterfactuals for Causally Compliant Explanations](https://mlsanity.com/paper/2310.07665/) (2023)
- [D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion](https://mlsanity.com/paper/2310.19321/) (2023)
- [Cardinality-Minimal Explanations for Monotonic Neural Networks](https://mlsanity.com/paper/2205.09901/) (2022)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)
- [TABCF: Counterfactual Explanations for Tabular Data Using a Transformer-Based VAE](https://mlsanity.com/paper/2410.10463/) (2024)
- [Robust Stochastic Graph Generator for Counterfactual Explanations](https://mlsanity.com/paper/2312.11747/) (2023)

## Abstract (arXiv)

Massive deployment of Graph Neural Networks (GNNs) in high-stake applications generates a strong demand for explanations that are robust to noise and align well with human intuition. Most existing methods generate explanations by identifying a subgraph of an input graph that has a strong correlation with the prediction. These explanations are not robust to noise because independently optimizing the correlation for a single input can easily overfit noise. Moreover, they do not align well with human intuition because removing an identified subgraph from an input graph does not necessarily change the prediction result. In this paper, we propose a novel method to generate robust counterfactual explanations on GNNs by explicitly modelling the common decision logic of GNNs on similar input graphs. Our explanations are naturally robust to noise because they are produced from the common decision boundaries of a GNN that govern the predictions of many similar input graphs. The explanations also align well with human intuition because removing the set of edges identified by an explanation from the input graph changes the prediction significantly. Exhaustive experiments on many public datasets demonstrate the superior performance of our method.