# A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 93 of its 199 references that are in the map.
- First posted on arXiv 21 Oct 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning](https://mlsanity.com/paper/1602.07261/) (2016)
- [Understanding intermediate layers using linear classifier probes](https://mlsanity.com/paper/1610.01644/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Attention is not Explanation](https://mlsanity.com/paper/1902.10186/) (2019)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Deep Reinforcement Learning that Matters](https://mlsanity.com/paper/1709.06560/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)

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

- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [How Interpretable Are Interpretable Graph Neural Networks?](https://mlsanity.com/paper/2406.07955/) (2024)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [A Systematic Literature Review of Spatio-Temporal Graph Neural Network Models for Time Series Forecasting and Classification](https://mlsanity.com/paper/2410.22377/) (2024)
- [Generative Explanations for Graph Neural Network: Methods and Evaluations](https://mlsanity.com/paper/2311.05764/) (2023)
- [When Graph Neural Network Meets Causality: Opportunities, Methodologies and An Outlook](https://mlsanity.com/paper/2312.12477/) (2023)
- [On Explaining Unfairness: An Overview](https://mlsanity.com/paper/2402.10762/) (2024)
- [Counterfactual Explanations for Deep Learning-Based Traffic Forecasting](https://mlsanity.com/paper/2405.00456/) (2024)
- [Heterogeneous Graph Neural Networks with Post-hoc Explanations for Multi-modal and Explainable Land Use Inference](https://mlsanity.com/paper/2406.13724/) (2024)
- [Unstructured and structured data: Can we have the best of both worlds with large language models?](https://mlsanity.com/paper/2304.13010/) (2023)
- [Counterfactual Explanations for Graph Classification Through the Lenses of Density](https://mlsanity.com/paper/2307.14849/) (2023)
- [CoDy: Counterfactual Explainers for Dynamic Graphs](https://mlsanity.com/paper/2403.16846/) (2024)
- [Towards Fair Graph Neural Networks via Graph Counterfactual without Sensitive Attributes](https://mlsanity.com/paper/2412.09947/) (2024)
- [Graph Inverse Style Transfer for Counterfactual Explainability](https://mlsanity.com/paper/2505.17542/) (2025)
- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [Adapting to Change: Robust Counterfactual Explanations in Dynamic Data Landscapes](https://mlsanity.com/paper/2308.02353/) (2023)
- [Introducing Diminutive Causal Structure into Graph Representation Learning](https://mlsanity.com/paper/2406.08709/) (2024)
- [Improving Counterfactual Truthfulness for Molecular Property Prediction through Uncertainty Quantification](https://mlsanity.com/paper/2504.02606/) (2025)
- [Injecting Falsehoods: Adversarial Man-in-the-Middle Attacks Undermining Factual Recall in LLMs](https://mlsanity.com/paper/2511.05919/) (2025)
- [Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion](https://mlsanity.com/paper/2608.12083/) (2026)
- [Introducing Expertise Logic into Graph Representation Learning from A Causal Perspective](https://mlsanity.com/paper/2301.08496/) (2023)
- [Global Graph Counterfactual Explanation: A Subgraph Mapping Approach](https://mlsanity.com/paper/2410.19978/) (2024)
- [Analysis of Customer Journeys Using Prototype Detection and Counterfactual Explanations for Sequential Data](https://mlsanity.com/paper/2505.11086/) (2025)
- [UGCE: User-Guided Incremental Counterfactual Exploration](https://mlsanity.com/paper/2505.21330/) (2025)
- [Learning Marked Temporal Point Process Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2508.11943/) (2025)
- [Counterfactual Explanation for Multivariate Time Series Forecasting with Exogenous Variables](https://mlsanity.com/paper/2511.06906/) (2025)
- [GradCFA: A Hybrid Gradient-Based Counterfactual and Feature Attribution Explanation Algorithm for Local Interpretation of Neural Networks](https://mlsanity.com/paper/2603.15373/) (2026)
- [Advancing Edge Classification through High-Dimensional Causal Modeling of Node-Edge Interplay](https://mlsanity.com/paper/2605.00374/) (2026)
- [Counterfactuals for Feature-Weighted Clustering](https://mlsanity.com/paper/2607.14719/) (2026)
- [From Explanations to Interventions: Execution-Guided Counterfactual Synthesis in Temporal Graphs](https://mlsanity.com/paper/2609.11170/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) perform well in community detection and molecule classification. Counterfactual Explanations (CE) provide counter-examples to overcome the transparency limitations of black-box models. Due to the growing attention in graph learning, we focus on the concepts of CE for GNNs. We analysed the SoA to provide a taxonomy, a uniform notation, and the benchmarking datasets and evaluation metrics. We discuss fourteen methods, their evaluation protocols, twenty-two datasets, and nineteen metrics. We integrated the majority of methods into the GRETEL library to conduct an empirical evaluation to understand their strengths and pitfalls. We highlight open challenges and future work.