# Counterfactual Explanations for Graph Classification Through the Lenses of Density

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 72 references that are in the map.
- First posted on arXiv 27 Jul 2023.

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

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (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)
- [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)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [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 survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [Causal Interpretability for Machine Learning -- Problems, Methods and Evaluation](https://mlsanity.com/paper/2003.03934/) (2020)
- [RelEx: A Model-Agnostic Relational Model Explainer](https://mlsanity.com/paper/2006.00305/) (2020)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks](https://mlsanity.com/paper/2105.08621/) (2021)
- [Reinforced Causal Explainer for Graph Neural Networks](https://mlsanity.com/paper/2204.11028/) (2022)
- [Counterfactual Graphs for Explainable Classification of Brain Networks](https://mlsanity.com/paper/2106.08640/) (2021)
- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [Explainable Classification of Brain Networks via Contrast Subgraphs](https://mlsanity.com/paper/2006.05176/) (2020)
- [Recent Advances in Graph Partitioning](https://mlsanity.com/paper/1311.3144/) (2013)
- [A Simple Baseline Algorithm for Graph Classification](https://mlsanity.com/paper/1810.09155/) (2018)

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

- [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)

## Abstract (arXiv)

Counterfactual examples have emerged as an effective approach to produce simple and understandable post-hoc explanations. In the context of graph classification, previous work has focused on generating counterfactual explanations by manipulating the most elementary units of a graph, i.e., removing an existing edge, or adding a non-existing one. In this paper, we claim that such language of explanation might be too fine-grained, and turn our attention to some of the main characterizing features of real-world complex networks, such as the tendency to close triangles, the existence of recurring motifs, and the organization into dense modules. We thus define a general density-based counterfactual search framework to generate instance-level counterfactual explanations for graph classifiers, which can be instantiated with different notions of dense substructures. In particular, we show two specific instantiations of this general framework: a method that searches for counterfactual graphs by opening or closing triangles, and a method driven by maximal cliques. We also discuss how the general method can be instantiated to exploit any other notion of dense substructures, including, for instance, a given taxonomy of nodes. We evaluate the effectiveness of our approaches in 7 brain network datasets and compare the counterfactual statements generated according to several widely-used metrics. Results confirm that adopting a semantic-relevant unit of change like density is essential to define versatile and interpretable counterfactual explanation methods.