# COMRECGC: Global Graph Counterfactual Explainer through Common Recourse

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 51 references that are in the map.
- First posted on arXiv 11 May 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Chip Placement with Deep Reinforcement Learning](https://mlsanity.com/paper/2004.10746/) (2020)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Counterfactual Graphs for Explainable Classification of Brain Networks](https://mlsanity.com/paper/2106.08640/) (2021)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [GLOBE-CE: A Translation-Based Approach for Global Counterfactual Explanations](https://mlsanity.com/paper/2305.17021/) (2023)
- [Learning Articulated Rigid Body Dynamics with Lagrangian Graph Neural Network](https://mlsanity.com/paper/2209.11588/) (2022)
- [GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking](https://mlsanity.com/paper/2310.01794/) (2023)
- [Beyond Known Reality: Exploiting Counterfactual Explanations for Medical Research](https://mlsanity.com/paper/2307.02131/) (2023)
- [Weakly Submodular Function Maximization Using Local Submodularity Ratio](https://mlsanity.com/paper/2004.14650/) (2020)
- [Tight Approximation Bounds for Maximum Multi-Coverage](https://mlsanity.com/paper/1905.00640/) (2019)
- [Generating Robust Counterfactual Witnesses for Graph Neural Networks](https://mlsanity.com/paper/2404.19519/) (2024)
- [Counterfactual Explanations for Graph Classification Through the Lenses of Density](https://mlsanity.com/paper/2307.14849/) (2023)
- [Game-theoretic Counterfactual Explanation for Graph Neural Networks](https://mlsanity.com/paper/2402.06030/) (2024)
- [Approximation algorithm for the Multicovering Problem](https://mlsanity.com/paper/2003.06936/) (2020)

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

- [From Nodes to Narratives: Explaining Graph Neural Networks with LLMs and Graph Context](https://mlsanity.com/paper/2508.07117/) (2025)

## Abstract (arXiv)

Graph neural networks (GNNs) have been widely used in various domains such as social networks, molecular biology, or recommendation systems. Concurrently, different explanations methods of GNNs have arisen to complement its black-box nature. Explanations of the GNNs' predictions can be categorized into two types--factual and counterfactual. Given a GNN trained on binary classification into ''accept'' and ''reject'' classes, a global counterfactual explanation consists in generating a small set of ''accept'' graphs relevant to all of the input ''reject'' graphs. The transformation of a ''reject'' graph into an ''accept'' graph is called a recourse. A common recourse explanation is a small set of recourse, from which every ''reject'' graph can be turned into an ''accept'' graph. Although local counterfactual explanations have been studied extensively, the problem of finding common recourse for global counterfactual explanation remains unexplored, particularly for GNNs. In this paper, we formalize the common recourse explanation problem, and design an effective algorithm, COMRECGC, to solve it. We benchmark our algorithm against strong baselines on four different real-world graphs datasets and demonstrate the superior performance of COMRECGC against the competitors. We also compare the common recourse explanations to the graph counterfactual explanation, showing that common recourse explanations are either comparable or superior, making them worth considering for applications such as drug discovery or computational biology.