ComRecGC : Global Graph Counterfactual Explainer through Common Recourse
Gregoire Fournier, Sourav Medya · 2025
Read ComRecGC : Global Graph Counterfactual Explainer through Common Recourse by Gregoire Fournier, Sourav Medya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07081.txt.
Introduction
Gregoire Fournier and Sourav Medya tackled in 2025 a gap in explaining graph neural networks: finding one small set of fixes that flips every rejected graph to accepted. Such networks sort graphs in fields from social data to drug design, but their choices are opaque. A global counterfactual explains a model by showing the changes that would flip its verdicts. A common recourse is a shared handful of such changes that works for all inputs.
The pair formalize that problem and build an algorithm to solve it. On four real graph datasets, their method beat strong rivals. Its shared explanations matched or beat per-graph ones in quality. The authors suggest common recourse could help drug hunters see what a model demands before trusting it.
Catalog record
| CREATOR | Gregoire Fournier, Sourav Medya |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07081
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ComRecGC : Global Graph Counterfactual Explainer through Common Recourse Gregoire Fournier, Sourav Medya Abstract Graph neural networks ( Gnn s) have been widely used in various domains such as social networks, molecular biology, or recommendation systems. Concurrently, different explanations methods of Gnn s have arisen to complement its black-box nature. Explanations of the Gnn s’ 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 Gnn s. 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. 1 Introduction Graph Neural Networks ( Gnn s) have been widely used for graph classification across various domains such as electrical design ( Mirhoseini et al., 2020 ) , physical simulation ( Bhattoo et al., 2022 ) , or drug discovery ( Jiang et al., 2020 ; Cao et al., 2016 ; Hamilton et al., 2017 ) . Despite their popularity and their good performance, the predictions of Gnn s are not yet fully understood, and explaining Gnn ’s behavior has become a central focus of recent research efforts ( Armgaan et al., 2024 ; Kosan et al., 2024 ; Kakkad et al., 2023 ; Yuan et al., 2022 ) . Our work focuses on the concept of Counterfactual Explanation (CE) in the context of binary classification (e.g., ‘reject’ vs. ‘accept’ classes). This involves designing the minimal changes required in each ‘reject’, or undesirable graph, to be able to change to an ‘accept’ graph, or counterfactual graph, that is often similar in structure. A global CE, in particular, aims to identify a small set of ‘accept’ graphs relevant to all ‘reject’ graphs, thereby providing insights into the critical decision regions recognized by the base Gnn model. This global explanation approach highlights the model-level behavior as opposed to an instance level or local one ( Verma et al., 2024 ) . Another important aspect of CE explanation is the implicit provision of recourse—graph transformations that convert a ‘reject’ graph into an ‘accept’ graph ( Verma et al., 2022 ; Karimi et al., 2020 ) . This is particularly valuable in applications where it is possible to take action to reverse a decision, such as in loan applications or in modifying a compound to change physical or chemical properties of molecules (e.g., mutagenicity ( Riesen & Bunke, 2008 ) ). The instance-specific or local counterfactual explanations are insightful and capable of providing recourse for each instance ( Abrate & Bonchi, 2021 ; Bajaj et al., 2021 ; Lucic et al., 2022 ; Tanyel et al., 2023 ; Chhablani et al., 2024 ) . However, the explanations generated are generally large in number and not straightforward to interpret at the model level. Global counterfactual explainers have been proposed to address these issues ( Huang et al., 2023 ; Ley et al., 2023 ) . We present additional related work in Appendix A . In ( Huang et al., 2023 ) , the authors build global counterfactuals for Gnn s. However, a major limitation of their approach is its generalizability when considering recourse. A single counterfactual can lead to significantly different recourse depending on the specific graph it explains, making it unsuitable as a local explanation ( Verma et al., 2024 ) . In ( Ley et al., 2023 ) , translation directions are learned by a counterfactual explanation algorithm and used with variable magnitudes to generate a global explanation. While this approach improves generalization, it decouples the process of identifying translation directions from fitting to a specific data distribution, which may limit robustness in some settings. Moreover, this method has not yet been applied to graph data. To answer these shortcomings, our work considers the problem of finding common recourse ( FCR ) graph explanation, which seeks to generate a small set of recourse that is capable of converting every ’reject’ graph into an ’accept’. This essentially means that one or more graphs use the same recourse to achieve a counterfactual. To the best of our knowledge, this problem has not been studied before from a graph machine learning perspective. FCR offers both high-level interpretability and instance level insights. Moreover, in some cases, more input graphs can be explained with fewer common recourse compared to global counterfactuals. Our main contributions are the following: • Novel problem setting. We formalize the FCR problem. We prove that the FCR problem is NP-hard. We provide a generalized version of the FCR problem, called FC (Finding Counterfactual), and derive an approximation algorithm to a constrained version of FC . • ComRecGC . We design the ComRecGC algorithm to extract high quality common recourse as an explanation, which provides a solution to both problems. • Experiments. We experiment on real-world datasets and benchmark our algorithm against popular counterfactual explainers on the Common recourse task. ComRecGC outperforms the next best solution on the FCR problem by more than 20\%,30\%,20\% , and 10\% in total coverage on the NCI1 , Mutagenicity , AIDS , and Proteins datasets respectively. We show that ComRecGC common recourse explanation offers a comparable and sometimes higher coverage than the best baseline global counterfactual explanation. 2 Background and Problem Formulation Counterfactual Explanation. A graph is defined as G=(V,E) , where V is the set of vertices and E the set of edges. Consider a binary graph classification model—such as a Gnn —where the prediction function is be denoted by \Phi . A graph is predicted in the ‘reject’ class if \Phi(G)=0 and in the ‘accept’ class if \Phi(G)=1 . For any reject graph G , we call a graph H counterfactual if \Phi(H)=1 and d(G,H)\leq\theta , where \theta is a given normalized distance value such that 0<\theta<1 and d is a distance function. In other words, we say H covers G . In the rest of the paper, we consider our input to be solely constituted of reject or ‘undesirable’ graphs, denoted by \mathbb{G} , and we denote by \mathcal{C}(G) the set of counterfactual graphs that cover G . Common Recourse. Given a reject graph G covered by H , we call recourse a transformation (a function, r ) which converts G into H . Note that the cost of the recourse is the distance between G and H . Upon defining a common recourse, an obvious question is how to define it on different graphs. For instance, if the recourse