# CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks

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

## Key facts

- Cited by 119 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 61 references that are in the map.
- First posted on arXiv 5 Feb 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (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)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (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)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Local Rule-Based Explanations of Black Box Decision Systems](https://mlsanity.com/paper/1805.10820/) (2018)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [The Hidden Assumptions Behind Counterfactual Explanations and Principal Reasons](https://mlsanity.com/paper/1912.04930/) (2019)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [Training Sparse Neural Networks](https://mlsanity.com/paper/1611.06694/) (2016)
- [Inverse Classification for Comparison-based Interpretability in Machine Learning](https://mlsanity.com/paper/1712.08443/) (2017)
- [The Intriguing Relation Between Counterfactual Explanations and Adversarial Examples](https://mlsanity.com/paper/2009.05487/) (2020)
- [FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles](https://mlsanity.com/paper/1911.12199/) (2019)

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

- [Benchmarking and Survey of Explanation Methods for Black Box Models](https://mlsanity.com/paper/2102.13076/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [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)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Position: Topological Deep Learning is the New Frontier for Relational Learning](https://mlsanity.com/paper/2402.08871/) (2024)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [Does Invariant Graph Learning via Environment Augmentation Learn Invariance?](https://mlsanity.com/paper/2310.19035/) (2023)
- [Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods](https://mlsanity.com/paper/2106.09078/) (2021)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (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)
- [Counterfactual Explanations for Neural Recommenders](https://mlsanity.com/paper/2105.05008/) (2021)
- [Fairness in Recommendation: Foundations, Methods and Applications](https://mlsanity.com/paper/2205.13619/) (2022)
- [ReLAX: Reinforcement Learning Agent eXplainer for Arbitrary Predictive Models](https://mlsanity.com/paper/2110.11960/) (2021)
- [PaGE-Link: Path-based Graph Neural Network Explanation for Heterogeneous Link Prediction](https://mlsanity.com/paper/2302.12465/) (2023)
- [GREASE: Generate Factual and Counterfactual Explanations for GNN-based Recommendations](https://mlsanity.com/paper/2208.04222/) (2022)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [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)
- [DEGREE: Decomposition Based Explanation For Graph Neural Networks](https://mlsanity.com/paper/2305.12895/) (2023)
- [A Meta-Learning Approach for Training Explainable Graph Neural Networks](https://mlsanity.com/paper/2109.09426/) (2021)
- [Exploring Faithful Rationale for Multi-hop Fact Verification via Salience-Aware Graph Learning](https://mlsanity.com/paper/2212.01060/) (2022)
- [Illuminati: Towards Explaining Graph Neural Networks for Cybersecurity Analysis](https://mlsanity.com/paper/2303.14836/) (2023)
- [Graph Neural Networks in Particle Physics: Implementations, Innovations, and Challenges](https://mlsanity.com/paper/2203.12852/) (2022)

## Abstract (arXiv)

Given the increasing promise of graph neural networks (GNNs) in real-world applications, several methods have been developed for explaining their predictions. Existing methods for interpreting predictions from GNNs have primarily focused on generating subgraphs that are especially relevant for a particular prediction. However, such methods are not counterfactual (CF) in nature: given a prediction, we want to understand how the prediction can be changed in order to achieve an alternative outcome. In this work, we propose a method for generating CF explanations for GNNs: the minimal perturbation to the input (graph) data such that the prediction changes. Using only edge deletions, we find that our method, CF-GNNExplainer, can generate CF explanations for the majority of instances across three widely used datasets for GNN explanations, while removing less than 3 edges on average, with at least 94% accuracy. This indicates that CF-GNNExplainer primarily removes edges that are crucial for the original predictions, resulting in minimal CF explanations.