# Beyond Edge Deletion: A Comprehensive Approach to Counterfactual Explanation in Graph Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 4 Mar 2026.

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

- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [Understanding Attention and Generalization in Graph Neural Networks](https://mlsanity.com/paper/1905.02850/) (2019)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Geometric Scattering for Graph Data Analysis](https://mlsanity.com/paper/1810.03068/) (2018)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [MEG: Generating Molecular Counterfactual Explanations for Deep Graph Networks](https://mlsanity.com/paper/2104.08060/) (2021)
- [A Simple Baseline Algorithm for Graph Classification](https://mlsanity.com/paper/1810.09155/) (2018)
- [Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization](https://mlsanity.com/paper/2109.07016/) (2021)
- [Effective Feature Learning with Unsupervised Learning for Improving the Predictive Models in Massive Open Online Courses](https://mlsanity.com/paper/1812.05044/) (2018)
- [COMBINEX: A Unified Counterfactual Explainer for Graph Neural Networks via Node Feature and Structural Perturbations](https://mlsanity.com/paper/2502.10111/) (2025)

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

- [Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion](https://mlsanity.com/paper/2608.12083/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are increasingly adopted across domains such as molecular biology and social network analysis, yet their black-box nature hinders interpretability and trust. This is especially problematic in high-stakes applications, such as predicting molecule toxicity, drug discovery, or guiding financial fraud detections, where transparent explanations are essential. Counterfactual explanations - minimal changes that flip a model's prediction - offer a transparent lens into GNNs' behavior. In this work, we introduce XPlore, a novel technique that significantly broadens the counterfactual search space. It consists of gradient-guided perturbations to adjacency and node feature matrices. Unlike most prior methods, which focus solely on edge deletions, our approach belongs to the growing class of techniques that optimize edge insertions and node-feature perturbations, here jointly performed under a unified gradient-based framework, enabling a richer and more nuanced exploration of counterfactuals. To quantify both structural and semantic fidelity, we introduce a cosine similarity metric for learned graph embeddings that addresses a key limitation of traditional distance-based metrics, and demonstrate that XPlore produces more coherent and minimal counterfactuals. Empirical results on 13 real-world and 5 synthetic benchmarks show up to +56.3% improvement in validity and +52.8% in fidelity over state-of-the-art baselines, while retaining competitive runtime.