# Generating Robust Counterfactual Witnesses for Graph Neural Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 30 Apr 2024.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (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)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [AllenNLP: A Deep Semantic Natural Language Processing Platform](https://mlsanity.com/paper/1803.07640/) (2018)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (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)
- [Certifiable Robustness to Graph Perturbations](https://mlsanity.com/paper/1910.14356/) (2019)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [Accelerating Large Scale Real-Time GNN Inference using Channel Pruning](https://mlsanity.com/paper/2105.04528/) (2021)
- [Layerwise Relevance Visualization in Convolutional Text Graph Classifiers](https://mlsanity.com/paper/1909.10911/) (2019)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)

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

- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [COMRECGC: Global Graph Counterfactual Explainer through Common Recourse](https://mlsanity.com/paper/2505.07081/) (2025)
- [Towards Comprehensive and Prerequisite-Free Explainer for Graph Neural Networks](https://mlsanity.com/paper/2505.14005/) (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)

This paper introduces a new class of explanation structures, called robust counterfactual witnesses (RCWs), to provide robust, both counterfactual and factual explanations for graph neural networks. Given a graph neural network M, a robust counterfactual witness refers to the fraction of a graph G that are counterfactual and factual explanation of the results of M over G, but also remains so for any "disturbed" G by flipping up to k of its node pairs. We establish the hardness results, from tractable results to co-NP-hardness, for verifying and generating robust counterfactual witnesses. We study such structures for GNN-based node classification, and present efficient algorithms to verify and generate RCWs. We also provide a parallel algorithm to verify and generate RCWs for large graphs with scalability guarantees. We experimentally verify our explanation generation process for benchmark datasets, and showcase their applications.