# Counterfactual Graphs for Explainable Classification of Brain Networks

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 16 Jun 2021.

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

- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Learning Important Features Through Propagating Activation Differences](https://mlsanity.com/paper/1704.02685/) (2017)
- [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)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Explainable deep learning models in medical image analysis](https://mlsanity.com/paper/2005.13799/) (2020)
- [DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification](https://mlsanity.com/paper/1906.02319/) (2019)
- [RelEx: A Model-Agnostic Relational Model Explainer](https://mlsanity.com/paper/2006.00305/) (2020)
- [Explainable Classification of Brain Networks via Contrast Subgraphs](https://mlsanity.com/paper/2006.05176/) (2020)
- [Explaining Deep Graph Networks with Molecular Counterfactuals](https://mlsanity.com/paper/2011.05134/) (2020)

## Built on by (most cited first, 30 of 33)

- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges](https://mlsanity.com/paper/2210.12089/) (2022)
- [A Survey on Explainability of Graph Neural Networks](https://mlsanity.com/paper/2306.01958/) (2023)
- [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)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [Comprehensible Artificial Intelligence on Knowledge Graphs: A survey](https://mlsanity.com/paper/2404.03499/) (2024)
- [GRAPHSHAP: Explaining Identity-Aware Graph Classifiers Through the Language of Motifs](https://mlsanity.com/paper/2202.08815/) (2022)
- [GRETEL: A unified framework for Graph Counterfactual Explanation Evaluation](https://mlsanity.com/paper/2206.02957/) (2022)
- [Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction](https://mlsanity.com/paper/2211.08378/) (2022)
- [From Nodes to Narratives: Explaining Graph Neural Networks with LLMs and Graph Context](https://mlsanity.com/paper/2508.07117/) (2025)
- [CS-MLGCN : Multiplex Graph Convolutional Networks for Community Search in Multiplex Networks](https://mlsanity.com/paper/2210.08811/) (2022)
- [CS-TGN: Community Search via Temporal Graph Neural Networks](https://mlsanity.com/paper/2303.08964/) (2023)
- [Bridging Trustworthiness and Open-World Learning: An Exploratory Neural Approach for Enhancing Interpretability, Generalization, and Robustness](https://mlsanity.com/paper/2308.03666/) (2023)
- [When Graph Neural Network Meets Causality: Opportunities, Methodologies and An Outlook](https://mlsanity.com/paper/2312.12477/) (2023)
- [Explaining Graph Neural Networks with Large Language Models: A Counterfactual Perspective for Molecular Property Prediction](https://mlsanity.com/paper/2410.15165/) (2024)
- [SurfGNN: A robust surface-based prediction model with interpretability for coactivation maps of spatial and cortical features](https://mlsanity.com/paper/2411.05825/) (2024)
- [Counterfactual Explanations for Graph Classification Through the Lenses of Density](https://mlsanity.com/paper/2307.14849/) (2023)
- [Towards Non-Adversarial Algorithmic Recourse](https://mlsanity.com/paper/2403.10330/) (2024)
- [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)
- [Adapting to Change: Robust Counterfactual Explanations in Dynamic Data Landscapes](https://mlsanity.com/paper/2308.02353/) (2023)
- [Global Human-guided Counterfactual Explanations for Molecular Properties via Reinforcement Learning](https://mlsanity.com/paper/2406.13869/) (2024)
- [COMRECGC: Global Graph Counterfactual Explainer through Common Recourse](https://mlsanity.com/paper/2505.07081/) (2025)
- [Finding Counterfactual Evidences for Node Classification](https://mlsanity.com/paper/2505.11396/) (2025)
- [Empowering Counterfactual Reasoning over Graph Neural Networks through Inductivity](https://mlsanity.com/paper/2306.04835/) (2023)
- [Global Graph Counterfactual Explanation: A Subgraph Mapping Approach](https://mlsanity.com/paper/2410.19978/) (2024)

## Abstract (arXiv)

Training graph classifiers able to distinguish between healthy brains and dysfunctional ones, can help identifying substructures associated to specific cognitive phenotypes. However, the mere predictive power of the graph classifier is of limited interest to the neuroscientists, which have plenty of tools for the diagnosis of specific mental disorders. What matters is the interpretation of the model, as it can provide novel insights and new hypotheses. In this paper we propose counterfactual graphs as a way to produce local post-hoc explanations of any black-box graph classifier. Given a graph and a black-box, a counterfactual is a graph which, while having high structural similarity with the original graph, is classified by the black-box in a different class. We propose and empirically compare several strategies for counterfactual graph search. Our experiments against a white-box classifier with known optimal counterfactual, show that our methods, although heuristic, can produce counterfactuals very close to the optimal one. Finally, we show how to use counterfactual graphs to build global explanations correctly capturing the behaviour of different black-box classifiers and providing interesting insights for the neuroscientists.