# Graph Counterfactual Explainable AI via Latent Space Traversal

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 52 references that are in the map.
- First posted on arXiv 15 Jan 2025.

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

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [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)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Local Rule-Based Explanations of Black Box Decision Systems](https://mlsanity.com/paper/1805.10820/) (2018)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Learning Model-Agnostic Counterfactual Explanations for Tabular Data](https://mlsanity.com/paper/1910.09398/) (2019)
- [Algorithmic recourse under imperfect causal knowledge: a probabilistic approach](https://mlsanity.com/paper/2006.06831/) (2020)
- [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (2019)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [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)
- [Fast Diffusion-Based Counterfactuals for Shortcut Removal and Generation](https://mlsanity.com/paper/2312.14223/) (2023)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [The general theory of permutation equivarant neural networks and higher order graph variational encoders](https://mlsanity.com/paper/2004.03990/) (2020)
- [Understanding Isomorphism Bias in Graph Data Sets](https://mlsanity.com/paper/1910.12091/) (2019)
- [Diffusion-based Iterative Counterfactual Explanations for Fetal Ultrasound Image Quality Assessment](https://mlsanity.com/paper/2403.08700/) (2024)
- [Nonparametric Bayes Modeling of Populations of Networks](https://mlsanity.com/paper/1406.7851/) (2014)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [Counterfactual Explanations via Riemannian Latent Space Traversal](https://mlsanity.com/paper/2411.02259/) (2024)
- [CeFlow: A Robust and Efficient Counterfactual Explanation Framework for Tabular Data using Normalizing Flows](https://mlsanity.com/paper/2303.14668/) (2023)
- [Statistical Shape Analysis of Brain Arterial Networks (BAN)](https://mlsanity.com/paper/2007.04793/) (2020)
- [Interpreting Equivariant Representations](https://mlsanity.com/paper/2401.12588/) (2024)

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

- [Towards Desiderata-Driven Design of Visual Counterfactual Explainers](https://mlsanity.com/paper/2506.14698/) (2025)
- [Graph Diffusion Counterfactual Explanation](https://mlsanity.com/paper/2511.16287/) (2025)
- [Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion](https://mlsanity.com/paper/2608.12083/) (2026)

## Abstract (arXiv)

Explaining the predictions of a deep neural network is a nontrivial task, yet high-quality explanations for predictions are often a prerequisite for practitioners to trust these models. Counterfactual explanations aim to explain predictions by finding the ''nearest'' in-distribution alternative input whose prediction changes in a pre-specified way. However, it remains an open question how to define this nearest alternative input, whose solution depends on both the domain (e.g. images, graphs, tabular data, etc.) and the specific application considered. For graphs, this problem is complicated i) by their discrete nature, as opposed to the continuous nature of state-of-the-art graph classifiers; and ii) by the node permutation group acting on the graphs. We propose a method to generate counterfactual explanations for any differentiable black-box graph classifier, utilizing a case-specific permutation equivariant graph variational autoencoder. We generate counterfactual explanations in a continuous fashion by traversing the latent space of the autoencoder across the classification boundary of the classifier, allowing for seamless integration of discrete graph structure and continuous graph attributes. We empirically validate the approach on three graph datasets, showing that our model is consistently high-performing and more robust than the baselines.