# Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Flow matching, time series and science, one of 14 directions in Diffusion models.
- Builds on 43 of its 64 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Placed in

- Diffusion models / [Flow matching, time series and science](https://mlsanity.com/diffusion/flow-matching-time-series-and-science/)

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Sparse Autoencoders Find Highly Interpretable Features in Language Models](https://mlsanity.com/paper/2309.08600/) (2023)
- [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)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Evaluating the visualization of what a Deep Neural Network has learned](https://mlsanity.com/paper/1509.06321/) (2015)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Unmasking Clever Hans Predictors and Assessing What Machines Really Learn](https://mlsanity.com/paper/1902.10178/) (2019)
- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [An Edit Friendly DDPM Noise Space: Inversion and Manipulations](https://mlsanity.com/paper/2304.06140/) (2023)
- [Disentangling Adversarial Robustness and Generalization](https://mlsanity.com/paper/1812.00740/) (2018)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (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)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Diffusion Visual Counterfactual Explanations](https://mlsanity.com/paper/2210.11841/) (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)
- [Diffusion Models for Counterfactual Explanations](https://mlsanity.com/paper/2203.15636/) (2022)
- [Beyond Trivial Counterfactual Explanations with Diverse Valuable Explanations](https://mlsanity.com/paper/2103.10226/) (2021)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [Adversarial Counterfactual Visual Explanations](https://mlsanity.com/paper/2303.09962/) (2023)
- [Fast Diffusion-Based Counterfactuals for Shortcut Removal and Generation](https://mlsanity.com/paper/2312.14223/) (2023)
- [MEG: Generating Molecular Counterfactual Explanations for Deep Graph Networks](https://mlsanity.com/paper/2104.08060/) (2021)
- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)

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

- [Towards Fast and Disentangled Counterfactuals for Visual Foundation Models](https://mlsanity.com/paper/2610.00895/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) achieve strong predictive performance on graph-structured data across domains such as chemistry, biology, and network analysis, yet they provide no intrinsic explanation of their predictions. This limits their adoption in high-stakes and safety-critical settings. Counterfactual explanations address this by revealing the minimal structural modifications that would change a model's prediction. On graphs, however, such a modification is hard to produce. The search space is discrete and combinatorial, and a valid answer must respect categorical node and edge types together with domain rules such as chemical valency in the case of molecular graphs. Existing explainers give up one of two things. Either edits are not held on the data manifold, or the search does not span the full edit space. We propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), which gives up neither. A discrete denoising diffusion model with a novel discrete inversion scheme enables distribution-aware edits leveraging the whole domain edit space. We further address the incomplete and inconsistent evaluation of graph counterfactuals by deriving a framework of explanation desiderata and applying it to every method under one shared protocol. Across four benchmarks, GDCE-I outperforms related work by a large margin on the defined framework. For the molecular domain, we further qualitatively show that GDCE-I attains interpretable in-distribution solutions.