# Global Counterfactual Explainer for Graph Neural Networks

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

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (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)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (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)
- [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)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Chip Placement with Deep Reinforcement Learning](https://mlsanity.com/paper/2004.10746/) (2020)
- [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)
- [Learning from Counterfactual Links for Link Prediction](https://mlsanity.com/paper/2106.02172/) (2021)
- [Counterfactual Graphs for Explainable Classification of Brain Networks](https://mlsanity.com/paper/2106.08640/) (2021)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Learning Articulated Rigid Body Dynamics with Lagrangian Graph Neural Network](https://mlsanity.com/paper/2209.11588/) (2022)
- [QGTC: Accelerating Quantized Graph Neural Networks via GPU Tensor Core](https://mlsanity.com/paper/2111.09547/) (2021)
- [TIGGER: Scalable Generative Modelling for Temporal Interaction Graphs](https://mlsanity.com/paper/2203.03564/) (2022)
- [POLE: Polarized Embedding for Signed Networks](https://mlsanity.com/paper/2110.09899/) (2021)
- [A Broader Picture of Random-walk Based Graph Embedding](https://mlsanity.com/paper/2110.12344/) (2021)
- [GraphReach: Position-Aware Graph Neural Network using Reachability Estimations](https://mlsanity.com/paper/2008.09657/) (2020)
- [An Exploratory Study of Stock Price Movements from Earnings Calls](https://mlsanity.com/paper/2203.12460/) (2022)
- [Event Detection on Dynamic Graphs](https://mlsanity.com/paper/2110.12148/) (2021)

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

- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [Graph Neural Networks for Vulnerability Detection: A Counterfactual Explanation](https://mlsanity.com/paper/2404.15687/) (2024)
- [Graph Neural Networks in Modern AI-aided Drug Discovery](https://mlsanity.com/paper/2506.06915/) (2025)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [A Cross Attention Approach to Diagnostic Explainability using Clinical Practice Guidelines for Depression](https://mlsanity.com/paper/2311.13852/) (2023)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)
- [Recent Advances in Malware Detection: Graph Learning and Explainability](https://mlsanity.com/paper/2502.10556/) (2025)
- [GLANCE: Global Actions in a Nutshell for Counterfactual Explainability](https://mlsanity.com/paper/2405.18921/) (2024)
- [Generating Explanations to Understand and Repair Embedding-based Entity Alignment](https://mlsanity.com/paper/2312.04877/) (2023)
- [Topological Structure Learning Should Be A Research Priority for LLM-Based Multi-Agent Systems](https://mlsanity.com/paper/2505.22467/) (2025)
- [When Graph Neural Network Meets Causality: Opportunities, Methodologies and An Outlook](https://mlsanity.com/paper/2312.12477/) (2023)
- [Generating Robust Counterfactual Witnesses for Graph Neural Networks](https://mlsanity.com/paper/2404.19519/) (2024)
- [Graph Counterfactual Explainable AI via Latent Space Traversal](https://mlsanity.com/paper/2501.08850/) (2025)
- [Game-theoretic Counterfactual Explanation for Graph Neural Networks](https://mlsanity.com/paper/2402.06030/) (2024)
- [Fast Inference of Removal-Based Node Influence](https://mlsanity.com/paper/2403.08333/) (2024)
- [Graph Inverse Style Transfer for Counterfactual Explainability](https://mlsanity.com/paper/2505.17542/) (2025)
- [GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability](https://mlsanity.com/paper/2509.18376/) (2025)
- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [Counterfactual Graph Transformer for Traffic Flow Prediction](https://mlsanity.com/paper/2308.00391/) (2023)
- [Adapting to Change: Robust Counterfactual Explanations in Dynamic Data Landscapes](https://mlsanity.com/paper/2308.02353/) (2023)
- [Attribute-Enhanced Similarity Ranking for Sparse Link Prediction](https://mlsanity.com/paper/2412.00261/) (2024)
- [Interpretability of Graph Neural Networks to Assess Effects of Global Change Drivers on Ecological Networks](https://mlsanity.com/paper/2503.15107/) (2025)
- [COMRECGC: Global Graph Counterfactual Explainer through Common Recourse](https://mlsanity.com/paper/2505.07081/) (2025)
- [Towards Faithful Class-level Self-explainability in Graph Neural Networks by Subgraph Dependencies](https://mlsanity.com/paper/2508.11513/) (2025)
- [UNR-Explainer: Counterfactual Explanations for Unsupervised Node Representation Learning Models](https://mlsanity.com/paper/2605.17285/) (2026)
- [Global Graph Counterfactual Explanation: A Subgraph Mapping Approach](https://mlsanity.com/paper/2410.19978/) (2024)
- [Explainable Graph Representation Learning via Graph Pattern Analysis](https://mlsanity.com/paper/2512.04530/) (2025)
- [Advancing Edge Classification through High-Dimensional Causal Modeling of Node-Edge Interplay](https://mlsanity.com/paper/2605.00374/) (2026)
- [Where Privacy Belongs: Placement Diagnosis and Certified Selection for Private Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2609.37667/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) find applications in various domains such as computational biology, natural language processing, and computer security. Owing to their popularity, there is an increasing need to explain GNN predictions since GNNs are black-box machine learning models. One way to address this is counterfactual reasoning where the objective is to change the GNN prediction by minimal changes in the input graph. Existing methods for counterfactual explanation of GNNs are limited to instance-specific local reasoning. This approach has two major limitations of not being able to offer global recourse policies and overloading human cognitive ability with too much information. In this work, we study the global explainability of GNNs through global counterfactual reasoning. Specifically, we want to find a small set of representative counterfactual graphs that explains all input graphs. Towards this goal, we propose GCFExplainer, a novel algorithm powered by vertex-reinforced random walks on an edit map of graphs with a greedy summary. Extensive experiments on real graph datasets show that the global explanation from GCFExplainer provides important high-level insights of the model behavior and achieves a 46.9% gain in recourse coverage and a 9.5% reduction in recourse cost compared to the state-of-the-art local counterfactual explainers.