# A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 40 references that are in the map.
- First posted on arXiv 20 Jun 2026.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [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)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2006.06830/) (2020)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Causal Machine Learning: A Survey and Open Problems](https://mlsanity.com/paper/2206.15475/) (2022)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [Explaining the Explainers in Graph Neural Networks: a Comparative Study](https://mlsanity.com/paper/2210.15304/) (2022)
- [MEG: Generating Molecular Counterfactual Explanations for Deep Graph Networks](https://mlsanity.com/paper/2104.08060/) (2021)
- [Inductive Link Prediction for Nodes Having Only Attribute Information](https://mlsanity.com/paper/2007.08053/) (2020)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [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)
- [D4Explainer: In-Distribution GNN Explanations via Discrete Denoising Diffusion](https://mlsanity.com/paper/2310.19321/) (2023)
- [L2XGNN: Learning to Explain Graph Neural Networks](https://mlsanity.com/paper/2209.14402/) (2022)
- [Robust Stochastic Graph Generator for Counterfactual Explanations](https://mlsanity.com/paper/2312.11747/) (2023)
- [HYPER: A Foundation Model for Inductive Link Prediction with Knowledge Hypergraphs](https://mlsanity.com/paper/2506.12362/) (2025)
- [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)

## Abstract (arXiv)

In this study, we propose a novel pipeline for generic, model-agnostic, local-level counterfactual explainability in graph neural networks (GNNs). Although counterfactual explainers capable of both adding and removing edges have emerged in recent years, the need for generic and efficient solutions remains unmet, particularly concerning qualitative explanation generation. Our approach couples progress in factual explainability with missing edge prediction models rooted in link prediction research, in order to enhance the quality, robustness and intuitiveness of explanations. A multi-faceted experimental analysis conducted on real-world and synthetic graph classification benchmarks, both binary and multi-label, demonstrates the advancements in comparison to state-of-the-art baselines across diverse metrics.