COMRECGC: Global Graph Counterfactual Explainer through Common Recourse
Authors: Gregoire Fournier
Sourav Medya
Venue: ICML 2025 poster (2025)
Keywords: Graph-based Machine Learning
Transparent
Interpretable
Explainable ML
Primary area: deep_learning->graph_neural_networks
TL;DR: The paper provides a method for global counterfactual explanations for GNNs with common recourse.

Abstract: 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 blackbox 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.

COMRECGC: Global Graph Counterfactual Explainer through Common Recourse
Grégoire Fournier' Sourav Medya? 2
Abstract
1. Introduction
Graph Neural Networks (GNNs) have been widely used for graph classification across various domains such elec- trical 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 popu- larity and their good performance, the predictions of GNNS are not yet fully understood, and explaining GNN'S behav- ior has become a central focus of recent research efforts (Armgaan al., 2024; Kosan al., 2024; Kakkad et al., 2023; Yuan et al., 2023). Our work focuses on the concept of Counterfactual Explanation (CE) in the context of bi- nary classification (e.g.. 'reject" vs. "accept' classes). This involves designing the minimal changes required in each 'reject', or undesirable graph, to able to change to an 'accept' graph, or counterfactual graph, that often similar in structure. A global CE, in particular, aims to identify 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).
Graph neural networks (GNNS) have been widely used in various domains such as social networks, molecular biology. 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 factual and counterfactual. Given GNN trained on binary classification into "accept" and "reject" classes, a global counterfactual explanation consists in gen- erating small set of "accept" graphs relevant to all of the input "reject" graphs. The transforma- tion of a "reject" graph into an "accept" graph is called a recourse. common recourse explana- tion is 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 expla- nation remains unexplored, particularly for GNNS. In this paper, we formalize the common recourse explanation problem, and design an effective algo- rithm, COMRECGC, solve it. We benchmark our algorithm against strong baselines on four dif- ferent real-works 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 ex- planations are either comparable or superior, mak- ing them worth considering for applications such as drug discovery computational biology.
Another important aspect of CE explanation is the implicit provision of gooourre-ggaph transformations that convert 'reject" graph into an 'accept' graph (Verma al., 2022; Karimi et al.). 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 GNNS. However, a major limitation of their approach is its generalizability when considering recourse. A single
'Department of Mathematics, Statistics and Computer Science, University of Illinois Chicago, Chicago, USA DDeparmment of Computer Science, University of Illinois Chicago, Chicago, USA. Correspondence to: Grégoire Fournier <gfoomm@@uic.duu
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
counterfactual can lead significantly different recourse depending on the specific graph it explains, making it un- suitable as 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, decouples the process of identifying translation directions from fitting to a specific data distribution, which may limit robustness in some set- tings. Moreover, this method has not yet been applied to graph data.
d(G, H) S 0. where 0 is a given normalized distance value such that 0 < 0 < 1 and d is 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 G and we denote by 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 common recourse, an obvious question is how to define it on dif- ferent graphs. For instance, if the recourse is 'adding' a vertex connected to some specific vertices that do not exist in different graphs, it will lead to some sort of ambiguity. However, a GNN always gives a latent representation (em- bedding). Thus, we use graph embedding 2 from the space of graphs into TR' for some constant / to define common recourse. Note that these embeddings can also be used to measure the distance between two graphs, such as the graph edit distance (Ranjan et al., 2023).
To answer these shortcomings, our work considers the prob- lem of finding common recourse (FCR) graph explanation, which seeks to generate small set of recourse that ca- pable of converting every 'reject' graph into an 'accept'. This essentially means that one more graphs use the same recourse to achieve a counterfactual. To the best of our knowledge, this problem has not been studied before from 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:
Suppose H covers G, and let be the recourse that turns G into H (i.e., r(G) = H), then we define the embedding of in the space of vectors of R to be F,, the vector from 2G)
to 2 ()), i.e., 2(G)2 (H). Given two recourse r1, r2, we say that they form a common recourse if there exists V. a vector in IR, such that | - ri S A and || r ll2 I A, for fixed < A 1. The idea is that there exists a center recourse which is close both recourse and can be used as summary.
Novel problem setting. We formalize the FCR prob- lem. 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 ap- proximation algorithm to a constrained version of FC.
COMRECGC. We design the COMRECGC algorithm to extract high quality common recourse as explana- tion, which provides a solution to both problems.
Please refer to the Appendix for the proofs of the Claims and Theorems of this section.
2.1. The Problem of Common Recourse
Experiments. We experiment on real-world datasets and benchmark our algorithm against popular coun- terfactual 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 comparable and sometimes higher coverage than the best baseline global counterfactual explanation.
Our goal is to have a small representative set of common recourse, F, and the cost of these should be small. Before formalizing our problem, we define the following:
COVERAGE(F) = HG E GEH E C(G), E F such that ||F- ( S AH//G|; the fraction of the input graphs for which at least one counterfactual is obtained through one of the recourse in F. Note that the center recourse are being chosen from F.
cFst(F) = AGGGEG (mink 11 E F and 3H E C(G) such that || - = S A}); the total distance from the covered input graphs to their closest attained counterfactual through F. The AGG function used in the experiments is the summation.
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 mooell-such as where the prediction function is be denoted by 4. A graph is predicted in the 'reject' class if (G)) = 0 and in the "accept' class if (G) = 1. For any reject graph G, we call a graph H counterfactual if (H) = and
(F)) |F]
Problem (Finding Common Recourse (FCR)). Given input graphs G and a budget R, the goal is to find a set of
2

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
recourse of size R that maximizes the coverage:
is not hard to see that g is monotone and does not possess any local submodularity ratio (Santiago & Yoshida, 2020).
maze coverage(IF) such that size(F) S R.
Theorem 2. is not pseudo-modular. (Appendix C.4)
Recourse are derived from the nearby counterfactual graphs. For a set of counterfactuals H. we define its associated recourse set as FE {=(G)=(H) G G, H )) Subsequently, another way to formalize the problem would be to look at the common recourse that can be extracted from a set of counterfactuals.
2.3.1. APPROXIMATION FOR THE FC PROBLEM
Since the function g is monotone but not- not-pseudo modular (Theorem 2), finding an approximation algorithm with some guarantees is non trivial. To make the problem tractable for
approximation, we add the following constraint: Constraint 1: (C1) To be considered as valid solution, a set of T counterfactuals, GI.... must verify:
Problem 2 (Finding Counterfactual (FC)). Given input graph E and two budgets R and T, the goal is to find a set of counterfactuals HI such that its associated common recourse set has size R:
vp < T. a( U G.) - G.) 0. 1Sp+1
(I)
maze coverage s.t. (Fz) S R, (Ize < T,
zSp
where F denotes the common recourse set that achieves the maximum coverage from selecting R recourse of Fu.
Intuitively, this means that there exists a "series" (in the sense of the union of sets) of counterfactuals that increases the objective function at each step. Such a constraint does not seem too abstract, most approximation algorithms look add one element a time. We obtain the following:
Note that the FCR problem is specific case of the FC problem by setting 7' to [G], the number of input graphs to cover. The FC problem corresponds to a max multi-budger multi-cover problem, where we have separate budgets for counterfactuals and for recourse. To count an input graph as covered, must covered by both of these budgets. We give an example for the FC problem in Appendix
Theorem 3. There is a 1 - -e 1/R approximation algorithm in expectation for the FC problem with C1. (Appendix C.5)
The above theoretical results have important implications: (1) FCR problem: The - (1-1/e) approxima- tion guarantee of the greedy algorithm consists in selecting the best common recourse at each step once the counter- factuals have been found. It is featured our method for solving the FCR problem. (2) FC problem: The 1-e 1 1/n approximation for the FC problem might be less useful in practice, as typically we want to allow numerous (R ~ 100) recourse to explain dataset. Although the corresponding randomized greedy algorithm provides a guarantee, instead of using this algorithm, we will assess the importance of each counterfactual with its number of visits through a "com- mon recourse random walk".
Discussions.
Although the cost is not constraint an objective in both the FCR and FC problems, it remains, alongside coverage, valuable metric for assessing the relevance of counterfactual explanations (Rawal& & Lakkaraju, 2020), and by extension, the recourse explanation derived from them.
2.2. Analysis: The FCR problem
The FCR problem (Problem 1) consists in finding the best common recourse set of size It in terms coverage from a list of common recourse.
Theorem I. The FCR problem is NP-hard. (Appendix C.I)
Let us define f as the function that associates to a set of common recourse its coverage. We claim that f is monotone and submodular (Appendix C.2), hence the common greedy algorithm yields - 1/e) approximation to selecting the R best recourse, which is the best poly-time approximation unless P-NP (Feige, 1998).
3. Our Method: COMRECGC
To find good counterfactual for common recourse, Cоm- RECGC operates in different stages.
A graph embedding algorithm: First, COMRECGC maps each graph from the set of input graphs into R' an embedding space. From the representation of an input graph and one of its counterfactual, we derive the recourse embedding.
2.3. Analysis of the FC problem
The FC problem (see Problem 2) is an extension of the FCR problem where
no longer given the full com- mon recourse set, and we are required to pick at most T counterfactuals to form R recourse for best coverage. In Ap- pendix C.3, we present a budget version of the FC problem.
COMRECGC finds counterfactuals for common re- course through multi-head vertex reinforced ran- dom walk in the graph edit space. This is a variation of vertex reinforced random walk (Pemantle, 2004).
Let g be the function that associates to a set of counterfactu- als its best coverage through building common recourse. It
3

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
A clustering algorithm for common recourse: we form clusters the embeddings of the generated recourse. Each cluster of certain radius (A) corre- sponds to a common recourse. Finally. we aggregate the common recourse greedily to obtain the maximum coverage.
our walk keep track of the graph from which each head started or was teleported to. We represent the state of the k-heads random walk as (u,)isk.
In each step, we randomly select one of the heads as the lead, denoted by the index e, then proceed as follows:
First, we move the lead head. The goal for the walker is to go towards potential counterfactual graph with the following transition rule, for v E N(we):
3.1. Graph embedding algorithm
One of the essential notions for defining the counterfac- tual is the distance function, as mentioned earlier. Our method, COMRECGC, begins with the efficient computa- tion of distance (or similarity) between two graphs. To assess distance between graphs, we use the graph edit dis- tance (GED) (Sanfeliu & Fu, 1983) that accounts for the minimal number of transformations- suchh as edge/vertex deletion/addition and label change-too make the graphs iso- morphic. For graph G, we denote (G) the neighbor set of graphs that only one edit distance away from G. We use the normalized GED distance GED(G1, G2) GED(G1, G2V/(( + [V2] + [E + |E2l) for our frame- work, which has the advantage compare two graphs of different sizes.
p(ue, v) x pe(v)C(v)
(2)
Where C(v) is one plus the number of visits to graph v, and (v) is the probability, assigned by the GNN, of v being a counterfactual.
Each non-lead head moves to the next state based on the recourse available among its neighbors that is closest to the lead's recourse. More formally, if the lead head is in state un after the previous step, then the next state for the i-th head is:
=GG)== z(G.))(v))) ll2
Since the GED is NP-hard to compute, we use graph embedding algorithm, GREED from (Ranjan et al., 2023), as a proxy, which aims to Iearn a GED metric through a projection of the graph dataset in RR. Note that it is possible to employ any other embedding algorithm that can estimate the GED between two graphs, to be able to validate the closeness of counterfactuals, and to define common recourse on the space of graphs through vectors in R'. We denote as GG) the embedding of a graph G in the rest of the paper.
Teleportation. The graph edit space is exponentially large. Thus, to explore the search space around small neighbor- hoods of the input graphs, we restrict the random walk by adding a probability of returning to input graphs of at each step. We call this operation telepor- tation, and each head state is reset to one of the input graphs optimizing for coverage as follows: define t(G) be the number of walks started from the input graph G. Then the probability of a head to teleport to G E G is:
0 < T
3.2. Multi-head vertex reinforced random walk
exp(-t(G))
pr (G) = Ecrea exp(-t(G"))
To identify counterfactuals, we explore the graph edit map through a random walk. The random walk occurs in the space of graphs, where each state is a distinct (non- isomorphic) graph. Two states are connected if and only if their corresponding graphs can be transformed into one another by single edit.
The pseudo code of the rundom walk procedure and some elements of analysis are presented in the Appendix (D.1 and D.2).
Counterfactual Candidates. After M steps, the random walk is terminated. For the next phase, we select the coun- terfactuals that have been visited at least a certain number of times, referring to these as the counterfactual candidates that represent the outcomes of the walk.
COMRECGC uses variation of a vertex reinforced random walk (VRRW). VRRW (Pemantle, 2004) performs random walks on a finite state space where the transition probability depends on the number of visits. This family of random walks has the advantage of experimentally converging, as well as providing an interpretation of the diversity and ex- ploration performances (Mei et al., 2010). We now describe how COMRECGC uses random walks:
3.3. Aggregation with clustering
Once counterfactuals have been found, COMRECGC forms clusters among the resulting recourse to find common re- course. For this task, we use a spatial clustering algorithm, DBSCAN (Ester et al., 1996) to find high density areas to aggregate recourse with close embedding representation. We associate common recourse to each cluster of radius
Initially, the random walk begins with k-heads each placed on different input graphs randomly, (Gt)sşk C G. At each step, we either continue the walk or, with a small probability, all heads teleport back to starting graphs. is crucial for

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
A. Finally, we pick R common recourse to be our expla- nation using greedy approach. Algorithm 1 summarizes this method on set GG of input graphs, with set of coun- terfactuals S, where grin FF) is the gain in coverage from adding the recourse r to
ones in the clustering step. Algorithm 3 represents COM- RECGC's solution to the FC problem. Line is specific to the FC framework. In particular, we select T |G] counterfactuals. This allows our method to be compared to the existing local explainers, where one counterfactual is given per input graph (Ying et al.). The complexity of this extra step is (n [G], hence COMRECGC's solution to the FC problem has complexity of O(Mhk + n² G|?)
Algorithm 1 CR CLUSTERING(G, 8, R)
1: C f- A-clusterize (z(G)=(v) ( GE
2: FF <-
3: for i 1: :: do
Algorithm 3 COMRECGC for FC (Ø. G, h: M, R)
4: r+ arg maxxee gain(r; F)
1: + MULTI-HEAD VRRW( G, k, M)
5: F+++ (r}
2: 3 + top n frequently visited counterfactuals in 8
6: end for
3: S < Ugee arg arg min (|x(l)=(Vllla
7: return
4: return CR CLUSTERING(G, 3, R)
3.4. COMRECGC: algorithm and complexity
4. Experiments
Finally, in Algorithm/ 2 we present COMRECGC's solution to the FCR problem, which consists of Multi-head VRRW, selection of counterfactual candidates for recourse, and clustering process for identifying common recourse. Line 2 is the filtering based on the number of visits, where is threshold set as a hyperparameter for the dataset.
We evaluate COMRECGC on four real-world datasets against the recourse from benchmark explainers, and show:
COMRECGC produces global common recourse that are of higher quality than those of the baselines on both the FCR and FC problems.
Algorithm 2 COMRECGC(O, G, k, M, T, R. n)
I: 8 + MULTI-HEAD VRRW(ó, G, k. M,
2: S + top a frequently visited counterfactuals S
The explanations produced by COMRECGC are signif- icantly less costly in terms of recourse than the ones generated by the baseline counterfactual explainers.
3: return CR CLUSTERING(C, &, It)
Complexity Analysis. The complexity of the random walk is O(Mhk), where M is the number of steps in the VRRW, I is the number of heads in the VRRW, and is the maxi- mum node degree in the graph-edit space map. The com- plexity of using DBSCAN clustering on n|G recourse is (G2))))), where n is the number of top-visited counter- factuals, and |G| is the number of input graphs. In practice, we have small constant due to being in R for / = 64. Finally, the complexity of the greedy summary of m/Gl re- course over [G] features R times is O(nR(G/)) 3), where R the size of the recourse set. The overall complexity is
The common recourse from COMRECGC can explain a similar, and in some cases higher, number of input graphs compared to the counterfactual graphs gener- ated by a global counterfactual explainer.
Reproducibility. We make our code available https: //github. com/ htw.:/wwww..c.ggggg/g/e/eee//e/e htt////gggre/////GG...//
4.1. Datasets
O(Mhk + (2)
We consider the datasets MUTAGENICITY (Riesen & Bunke, 2008; Kazius et al., 2005), NCII (Wale & Karypis, 2006), AIDS (Riesen & Bunke, 2008), and PROTEINS (Borgwardt et al., 2005; Dobson & Doig, 2003). In the first three, each graph accounts for a molecule, where nodes represent atoms and edges chemical bonds between them. The molecules are classified by whether they are mutagenic, anticancer, or active against HIV, respectively. The PROTEINS dataset is composed of different proteins classified into enzymes and non-enzymes, with nodes representing secondary structure elements and edges representing structural proximity, For each dataset, we remove graphs containing rare nodes (with a label count less than 50). The statistics of the datasets are detailed in Table
3.5. Variation of CECG for the FC problem
Our goal is to build a generic framework to solve both the FCR and FC problems. We can also use COMRECGC to generate solutions the FC problem. In the counterfactual candidates step, we need to significantly reduce the number of counterfactuals used to generate common recourse in order to match the constraints in FC. COMRECGC selects the counterfactuals that are closest to the input graphs. In- tuitively. this is because the common recourse threshold A is geometrically tight, so we want recourse (cost) to be as small as possible to increase the chance of getting common
5

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
4.3. Results for the FCR problem
Table 1. Datasets overview.
NC11
MUTAGENICITY
AIDS PROTEINS
Baselines. Since the FCR problem does not constrain the number of counterfactuals used to generate common re- course, explainers used for benchmarking this problem must be able to generate large number of counterfactuals. In the literature, we find that only GCFEXPLAINER(Huung) ct al., 2023) aims at generating global counterfactuals on a large scale. This is also the only global method to generate counterfactual. To generate common recourse with GCFEX- PLAINER counterfactuals, ing algorithm (Algorithm 1) that is part of COMRECGC, For COMRECGC, its number of heads variants, and GCFEX- PLAINER. we limit the number of counterfactuals entering the clustering stage to 100, 000 graphs.
#Graphs
3978
4308
1837
1113
#Nodes
118714
130719
28905
43471
#Edges
128663
132707
29985
81044
#Node Labels
10
10
4.2. Experimental set up
We train base GNN model (GCN) (Kipf& & Welling, 2017) for a binary classification task, consisting of three convo- lutional layers, a max pooling layer, and a fully connected layer, following best practices from the literature (Vu & Thai, 2020). The model is trained with the Adam opti- mizer (Kingma & Ba, 2014) and learning rate of 0.001 for 1000 epochs. The training/validaiionnesttg split is 80%\/1%%/10% and the corresponding accuracy measures are presented in Table 2.
use the same recourse cluster-
Results. The results are presented Table 3. We observe that the common recourse explanation from COMRECGC yields better coverage by significant margin on all datasets, thus providing better solution for the FCR problem than the baselines. The cost of the common recourse is also lower on the NCII, MUTAGENICITY datasets, comparable on the AIDS dataset, and slightly above on the PROTEINS dataset. This difference coverage is explained by the multi-heas random walk used to generate counterfactuals in COMRECGC, which tends facilitate forming common recourse afterwards. The lower cost is also explained by the fact that finding common recourse with similarity threshold A 0.02 is difficult, and is easier on small recourse than on larger ones.
Table Accuracy GCN on the graph binary classification task on NCII, MUTAGENICITY. AIDS and PROTEINS.
NC11
MUTAGENICITY
AIDS
PROTEINS
Training 0.844
0,882
0.998
0.780
Validation
0.816
0.830
0.973
0.820
Testing 0.781
0,800
0.978
0.730
Choice of the parameters 0 and A. The parameter 0 ac- counts for the distance to graph G E G within which graph with an accepted prediction can be used as coun- terfactual explanation for G. There is a trade-off: a small provides instance-wist -wie explanations, if they exist, and coun- larger allows for more effective summaries, terfactuals tend to cover broader range of input graphs. Following (Huang al., 2023), we set 0 0.1 in the exper- iments on the NCI1, MUTAGENICITY and AIDS datasets. However, we set 0 = 0.15 for the PROTEINS dataset, as we have found experimentally that counterfactuals tend to more distant from their input graphs.
On the other hand, the parameter A accounts for the max- imum difference between two recourse to be considered common. A larger A yields better summaries but the in- sights become less precise. We set A = 0.02, although this may seem large compared to the value of 0, the em- bedding space dimension used for the datasets is 7 = 64, making the margin for common recourse sensibly smaller than the one for finding counterfactuals, as expected. An example illustrating common recourse explanation with those parameters is provided in Figure 1.
Figure I. Common Recourse MUTAGENICITY: Removing
COMRECGC parameters. Across all of our experiments, COMRECGC uses l: = 5 heads, has probability telepor- tation 7 = 0.05, performs the random walk for M = 50000 steps, and selects R = 100 common recourse.
NO₃ complex. On the left two mutagenetic molccules from the input, the right resulting non-mulagenetic molecules.
6

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Table Results on the FCR problem. Higher coverage corresponds to generating common recourse shared by more input graphs. The cost (lower is better) refers to the total length of the recourse. COMRECGC and its variants outperform the baseline in almost all settings,
NCI1
MUTAGENICITY
AIDS
PROTEINS
Coverage
Cost
Coverage
Cost
Coverage
Cost
Coverage
Cost
GCFEXPLAINER
21.4%
5.75
20.6%
6,91
14.2%
6.97
32.8%
10.65
COMRECGC 2-HEAD
40.5%
5.12
45.9%
5.74
32.8%
6.71
45.9%
11.44
COMRECGC 3-HEAD
44.5%
5.07
52.6%
5.61
33.6%
6.62
45.9%
11.51
COMRECGC 4-HEAD
44.6%
4.70
52.0%
5.81
34.8%
6.71
46.2%
11.47
COMRECGC 5-IIAD
42.9%
4.95
51.8%
5.63
34.7%
6.74
46,4%
11.59
COMRECGC 6-HEAD
44.9%
4.51
52.0%
5.68
35.2%
6.66
47.3%
11.59
Table 4. Results on the FC problem. Higher coverage and lower cost are dosirable. COMRECGC performs better than the basclines on all datascts and metrics except for the on the AIDS and PROTEINS datasets.
NCI1
MUTAGENICITY
AIDS
PROTEINS Coverage
Coverage
Cost
Coverage
Cost
Coverage
Cost
Cost
DATASET COUNTERFACTUALS 8.52%
9.02
10.4%
8.34
0.41%
0.97
29.0%
12.95
ROCALRWEXPLATE GCFEXPLAINER
19.0%
5.89
18.2%
7.19
12.9%
7.31
22.1% %
11.33
14.7%
7.12
11.9%
7.80
14.2%
7.07
29.8%
11.13
COMRECGC
33.4%
5.60
46.7% %
6.56
24.3%
6.59
39.6%
12.04
4.4. Results for the FC problem
than the recourse from other method, except on the Pro- teins dataset, where they are comparable. The low cost of the dataset counterfactuals common recourse for the AIDS dataset explained by the low number of common recourse formed, as few f-close counterfactuals are in the dataset.
Baselines. The FC problem constraints the number of coun- terfactuals used to form common recourse, which allows us compare our method common local counterfactual explainers. To evaluate the performance of our method compared to baselines, we construct common recourse explanation for counterfactual explainer follows: counterfactual explainer takes the set of input graphs G and returns a set S of counterfactuals of the same cardinality. We form clusters on using Algorithm to generate a common recourse explanation. The baseline counterfactual explain- ers are GCFEXPLAINER and local random walk explainer. The second one performs random walk around each input graph to find close counterfactuals; we select the closest counterfactual to each input graph to be part of the set of counterfactual candidates used to generate recourse. We have not used explainers such as CFF EXPLAINER (Bajaj al., 2021), RCEXPLAINER (Tan al., 2022), as they mainly focus on local explanation, and GCFEXPLAINER al- ready outperforms these methods (Huang et al., 2023). They also only generate subgraph counterfactual explanations, whereas random walk can also add elements to the graph to find counterfactuals, Finally, we also add a baseline that corresponds to Algorithm processing the counterfactual graphs given in the original dataset.
This difference in coverage is even more striking in the FC problem than in the FCR problem. When the number of counterfactuals is reduced from 100, 000 to 2000, mostly close counterfactuals are grouped together; this is why the local RW explainer performances are better than the GCF- EXPLAINER global counterfactual for forming common recourse the NCII and MUTAGENICITY datasets.
4.5. Common recourse explanations vs global counterfactual explanations
Lastly, we compare common recourse explanations and global counterfactual explanations in terms of coverage. Since COMRECGC is the only method designed to ex- plain through common recourse, we will compare the com- mon recourse explanation generated by COMRECGC to the global graph counterfactuals generated by GCFEX- PLAINER(Huang et al., 2023), CFF EXPLAINER (Bajaj et al., 2021), and RCEXPLAINER (Tan et al., 2022). We also add the global graph counterfactual explanation generated by the counterfactual given in the dataset.
Table 4 presents the outcome. We show more detailed results for different numbers of recourse in Figure 2. We observe that COMRECGC generates the best coverage compared to all the baselines on the FC problem across all datasets. The cost of the common recourse is also lower
Results.
For the definition of coverage for set of counterfactual graphs S, we refer to (Huang et al., 2023) and define it as the ratio of the input graphs covered by at least one coun- terfactual in S. More formally COVERAGE(S) == [[G

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Table Common recourse explanation vs global counterfactual explanation for 10 explanations. COMRECGC's common recourse
explanations outperform the baselines' graph counterfactual explanations most of the datasets.
NCI1
MUTAGENICITY
AIDS
PROTEINS Coverage
Coverage
Coverage
Coverage
DATASET COUNTERFACTUALS
16.5%
29.0%
0.4%
8.5%
RCEXPLAINER 15.2%
32.0%
9.0%
8.7%
CFF
17.6%
30.4%
3.4%
3.8%
GCFEXPLAINER
27.9%
37.1%
14.7%
10.9%
COMRECGC
26.1%
39.4%
15.2%
18.0%
NCI1
Mutagenicity
AIDS
Proteins
150
Coverage
600
1000
300
400
200
100
500
200
100
50
0
0
50
100
100
100
7.5
7.5
10
Cost
5.0
5.0
5
2.5
2.5
0.0
0
0
50
100
50
100
0
50
100
0
50
100
SIZE (R)
Dataset Counterfactuals
LocalRWEXplainer
GCFExplainer
COMRECGC
Figure 2. Common Recourse coverage and cost comparison between COMRECGC and baselines for the FC problem where 0.02, T = |G] and R = 1 to 100 common recourse.
G|mingesll((G)-- (S)) S 0////
able cover close to the whole of MUTAGENICITY and NCII datasets, and follows the same trend for the AIDS dataset. However, is quite surprising that the coverage the PROTEINS dataset went down by 1%. An explanation for this is a possible issue with the clustering algorithm DBScan, which may be caused by a too big overlap on some common recourse clusters.
The results, shown in table 5 for 10 explanations, indi- cate that the common recourse explanations from COM- RECGC are comparable to the best graph counterfactual method, GCFEXPLAINER, on the NCI1, MUTAGENICITY, and AIDS datasets, while being significantly more com- prehensive on the PROTEINS dataset. This difference may be due to the sparsity of the Proteins dataset, which makes challenging identify central counterfactual graph to explain the sparse neighborhood. Common recourse seems to be more suitable explanation for this dataset, at least under the conditions of our experiments.
Increasing the counterfactual threshold proven to be challenging, as raising from 0.1 to 0.15 across datasets dramatically increased the number of recourse entering the clustering stage. For example, on the MUTAGENICITY and NCII datasets, the number of recourse increased by fac- tor of 100, making DBScan intractable in its current form. As expected, increasing 9 results in greater coverage the common recourse explanations produced by COMRECGC. but also raises the cost, as longer recourse are allowed. In particular, the AIDS dataset, the increase in coverage minimal, suggesting a potential bottleneck in the effec- tiveness of common recourse explanations for that dataset with common recourse threshold set at A = 0.02.
4.6. Experiments on different values of 0, A
Setting, We experiment on different values of 0, A. Those parameters are only used in the clustering algorithm part of COMRECGC. The results are presented in Table 6, for COMRECGC with parameters M 50, 000, k = 5, 0.05.
Results. We do not run into issues with increasing the value of A, the common recourse threshold. As expected, the
In Table 7 we experiment with a finer variation A and its effect on the coverage variation. We observe that higher A
coverage goes up, and so does the cost as COMRECGC is
8

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Table Results on the FCR problem COMRECGC for different values 0 and A. find that increasing the common recourse and counterfactual threshold tends to improve coverage, particularly for more dense datasets, such as MUTAGENICITY and NCII. The effect on more sparse datasets such as PROTEINS and AIDS is more contrasted, with moderate to no added coverage. The cost rises as we allow more distant counterfactuals. For configurations where 0 = 0.15 and A = 0.02, the number of recourse entering the clustering stage is large, making the DBScan clustering algorithm intractable, resulting in missing values (xx).
NCI1
MUTAGENICITY
AIDS
PROTEINS
Coverage
Cost Coverage
Cost
Coverage
Cost Coverage
Cost
0 = 0.1, A = 0.02
42.9%
4.95
51.8%
5.63
34.7%
6.74
42.8%
7.21
0 0.1, A- 0.04
86.5% x
8.05
90.0%
8.11
47.0%
8.4
41.5%
6.36
0.15, A- 0.02
x
X
x
34.8%
7.65
46.4%
11.59
of common recourse in E.4. In Appendix E.5 we present results on the different types of GNNs. In Appendix E.6 we test our method on a network dataset and add a comparison of our method to a local CE explainer in Appendix E.7.
Table 7. Results on the FCR problem of COMRECGC for different values of and A on the Mutagenicity dataset.
MUTAGENICITY Coverage Cost
0 = 0.1, A = 0.02
51.8%
5.63
5. Conclusion
= 0.1, A- = 0.025
67.15%
6.99
0 0.1, A 0.03
75.35%
7.59
In this work, we have formalized the problem of generating global counterfactual explanations for GNNS with common recourse. This novel problem setting includes the FCR and FC problems. These problems are NP-hard and thus, we have designed COMRECGC, a method specifically tai- lored extract high-quality common recourse explanations. Through extensive experiments on real-world datasets, we have benchmarked COMRECGC against popular counter- factual explainers in the common recourse task. Our results demonstrate that COMRECGC produces global common recourse of significantly higher quality than the baselines across both the FCR and FC problems. Finally, COM- RECGC's s common recourse explanations can account for a similar number of input graphs as those generated by global counterfactual explainers, providing a robust and scalable alternative to global graph counterfactual explanation.
0 0.1, A = 0.035
83.88%
8.03
0 = 0.1, A 0.04
90.0%
8.11
allows for a more comprehensive explanation, as we allow similar recourse to be considered "coomon"' more easily. The cost naturally rises as more explanations are covered.
4.7. Discussions
We make a few important observations, including a few limitations of COMRECGC. Thee observations will be help- ful in practice. First, since the FCR and FC problems are novel, our method is the only one specifically designed to generate common recourse. It is therefore unsurprising that we outperform the existing counterfactual explainers. Second, determining the appropriate parameters 0 and A for the FCR problem is challenging and application de- pendent. Since these parameters serve as thresholds for a normalized distance, larger graphs generally work well with smaller values of 0 and A, while smaller graphs require larger values. Third, we believe that relaxing the values of 0 and A could lead to richer and more diverse explanations. However, as more common recourse would be generated in that process, we need an appropriate filtering system to select the most meaningful ones. Fourth, we explore the graph edit map without considering the physical feasibility of the changes, especially if the domain has specific con- straints (e.g., chemical bonds in molecules). As result, the generated counterfactual graphs may not correspond to the real-world entities depending on the domain.
A Acknowledgmen
We would like to thank György Turán for his generous sup- port, patience, and care throughout this project, and for initiating this collaboration. We also thank Sayan Ranu for the helpful discussions. The work has been supported in part by NSF grant edge the National Artificial Intelligence Research Resource (NAIRR) Pilot and the Texas Advanced Computing Center (TACC) Vista for contributing to this research result.
The authors also acknowl-
Impact Statement
This paper presents work to advance the field of explain- able Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We discuss the choice of the random walk parameters in Appendix E. We present running times of our method in Appendix E.2, an ablation study in E.3, and other examples

---

COMRECGC C Global Graph Counterfactual Explainer through Common Recourse
References
Dobson, P. D. and Doig, A. Distinguishing enzyme struc- tures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Abrate, C. and Bonchi, F. Counterfactual graphs for ex- plainable classification of brain networks. In SIGKDD, 2021.
Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. density-
based algorithm for discovering clusters in large spatial databases with noise. In Knowledge Discovery and Data Mining, 1996.
Abrate, C., Preti, G., and Bonchi, F. Counterfactual explana- tions for graph classification through the lenses of density. In Explainable Artificial Intelligence - First World Con- ference, xAI 2023, Proceedings.
Feige, U. A threshold of In for approximating set cover. J. ACM, 45(4):634 652, 1998.
Armgaan, B., Dalmia, M., Medya, S., and Ranu, S. Graphtrail: Translating gnn predictions into human- interpretable logical rules. Advances in Neural Infor- mation Processing Systems, 37:123443-123470 2024.
Gorgi, A., Ouali, M. E., Srivastav, A., and Hachimi, M. Approximation algorithm for the multicovering problem. J. Comb. Optim., 2021.
Hall, N. G. and Hochbaum, D. S. fast approximation algorithm for the multicovering problem. Discret. Appl. Math., 1986.
Bajaj. M., Chu, L.,, Xue, Z. Y., Pei, J., Wang, L., Lam, P. C.-H., and Zhang, Y. Robust counterfactual explanations on graph neural networks. In NeurlPS, 2021.
Hamilton, W. W.,., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. In NeurIPS, 2017.
Barman, S., Fawzi, O., Ghoshal, S., and Gürpinar, E. Tight approximation bounds for maximum multi-coverage. CoRR, 2019.
He, K., Liu, L., Zhang, Y., Wang. Y., Liu, Q., and Wang, G. Learning counterfactual explanation of graph neural networks via generative flow network. IEEE Transactions on Artificial Intelligence, 5(9):4607-4619, 2024. doi: 10.1 0..1109/TA1.2024333744444
Benaïm, M. and Tarres, Dynamics of vertex- reiex--reifoorce random walks. The Annals of Probability, 39(6), Novem- ber 2011.
Bhattoo, R., Ranu, S., and Krishnan, N. Learning articu- lated rigid body dynamics with lagrangian graph neural network. In NeurlPS, 2022.
Hua, Q., Yu, D., Lau, F. C. M., and Wang, Y. Exact algo- rithms for set multicover and multiset multicover prob- lems. ISAAC, 2009.
Borgwardt, K. M., Ong, C. S., Schönauer, S., Vishwanathan, S., Smola, A. J., and Kriegel, H.-P. Protein function prediction via graph kernels. Bioinformatics, 21(uupl 1): i47-i56, 2005.
Huang, Z., Kosan, M., Medya, S., Ranu, S., and Singh, A. K. Global counterfactual explainer for graph neural networks. In WSDM, 2023.
Jiang, M.. Li, Z., Zhang, S., Wang, S., Wang, X., Yuan, Q. and Wei, Z. Drug-targe affinity prediction using graph neural network and contact maps. RSC advances, 10(35); 20701-20712, 2020.
Buchbinder, N., Feldman, M., Naor, J., and Schwartz, R. Submodular maximization with cardinality constraints. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Port- land, Oregon, USA, January 5-7, 2014, pp. 1433-1452. SIAM, 2014.
Kakkad, J., Jannu, J., Sharma, K., Aggarwal, C., and Medya, S. A survey on explainability of graph neural networks. IEEE Data Eng. Bull., 2023.
Cao, S., Lu, W., and Xu, Q. Deep neural networks for learn- ing graph representations. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI'66. AAAI Press, 2016.
Kang, H., Han, G., and Park, H. Unr-explainer: Counterfac- tual explanations for unsupervised node representation learning models. In The Twelfth International Conference on Learning Representations, 2024.
Cellinese, F., D' Angelo, G., Monaco, G., and Velaj, Y. The multi-budget maximum weighted coverage problem. In Algoritiums and Complexity, 2021.
Karimi, A., Schölkopf, B., and Valera, I. Algorithmic re- course: from counterfactual explanations to interventions. FAceT '21: 2021 ACM Conference on Fairness, Ac- countability, and Transparency.
Chhablani, C., Jain, S., Channesh, A., Kash, I. A., and Medya, S. Game-theorets counterfactual explanation for graph neural networks. In Proceedings of the ACM Web Conference 2024, pp. 503-514, 2024.
Kazius, J., McGuire, R., and Bursi, R. Derivation and validation toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312-320 2005.
10

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Khuller, S., Moss, A., and Naor, J. S. The budgeted maxi- mum coverage problem. Information Processing Letters, 1999.
Riesen, K. and Bunke, H. Jam graph database repository for graph based pattern recognition and machine learn- ing. In Joint IAPR International Workshops Statistical TeFchniques in Pattern Recognition (SPR) and Structural and Syntactie Pattern Recognition (SSPR), pp. 287-297. Springer, 2008
Kingma, D. P. and Ba, Adam: A method for stochastic optimization. arXiv:1412.6985) 2014.
Kipf. T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICIRR, 2017.
Sanfeliu, A. and Fu, K.-S. A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3):353- 362, 1983.
Kosan, M., Verma, S., Armgaan, B., Pahwa, K., Singh, A., Medya, S., and Ranu, S. Gnnx-bench: Unravelling the utility of perturbation- based gnn explainers through in-depth benchmarking. In ICIR, 2024.
Santiago, R. and Yoshida. Weakly submodular function maximization using local submodularity ratio. In ISAAC, volume 181 of L/PIcs, 2020.
Ley, D., Mishra, S., and Magazzeni, D. Globe-ce: A trans- lation based approach for global counterfactual explana- tions. In ICML, 2023.
Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y., and Zhang, Y. Learning and evaluating graph neural network expla- nations based on counterfactual and factual reasoning. In WebConf, 2022.
Lovász, L. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
Tanyel, T., Ayvaz, S., and Keserci, B. Beyond known real- ity: Exploiting counterfactual explanations for medical research. CoRR, abs/2307.02131 2023.
Lucic, A.,
Ter Hoeve, M. A., Tolomei, G., De Rijke, M., and Silvestri, F. Cf-gnnexplainer: Counterfactual expla- nations for graph neural networks. In AISTATS, 2022.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, Conference Track Proceedings, 2018
Magister, L. C., Kazhdan, D., Singh, V., and Liò, P. GCEX- plainer: Human-in corman-in-the-leee the-loop concept- explanations for graph neural networks, 2021.
Mei, Q., Guo, J., and Radev, D. R. Divrank: the interplay of prestige and diversity in information networks. In SIGKDD, 2010.
Verma, S., Boonsaanogg V., Hoang, M., Hines, K. E., Dick- erson, J. P., and Shah, C. Counterfactual explanations and al algorithmic recourses for machine learning: A review, 2022.
Mirhoseini,
A., Goldie, A., Yazgan, M., Jiang, J. W. J., Songhori, M., Wang, S., Lee, Y., Johnson, E.,, Pathak, O., Bae, S., Nazi, A., Pak, J., Tong, A., Srinivasa, K., Hang, W., Tuncer, E., Babu, A., Le,, Q. V., Laudon, J., Ho, R., Carpenter, R., and Dean, J. Chip placement with deep reinforcement learning. CoRR, abs/2004. 107466 2020.
Verma, S., Armgaan, B., Medya, S., and Ranu, S. Induce: Inductive counterfactual explanations for graph neural networks. Transactions on Machine Learning Research, 2024.
Pemantle, R. Vertex-reinforced random walk, 2004.
Volkov, S. Vertex-reinforeed random walk on arbitrary graphs. The Annals of Probability, 2001.
Pemantle, R. A survey of random processes with reinforce- ment. Probubility Surveys, 2007.
Vu, M. and Thai, M. T. Pgm-explainer: Probabilistic graph- ical model explanations for graph neural networks. In NeurIPS, 2020.
Qiu, D., Wang, M., Khan, A., and Wu, Y. Generating robust counterfactual witnesses for graph neural networks. In Proceedings- 2024 IEEE 40th International Conference on Data Engineering, ICDE 2024, 2024.
Wale, N. and Karypis, G. Comparison of descriptor spaces for chemical compound retrieval and classification. In ICDM, 2006.
Ranjan, R., Grover, S., Medya, S., Chakaravarthy, V., Sab- harwal, Y., and Ranu, S. Greed: A neural framework for learning graph distance functions, 2023.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How pow- erful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019.
Rawal, K. and Lakkaraju, H. Beyond individualized re- course: Interpretable and interactive summaries of action- able recourses. In NewrIPS, 2020.
Yanardag, P. and Vishwanathan. Deep graph kernels. Proceedings of the 2/th ACM SIGKDD international

---

COMRECGC C Global Graph Counterfactual Explainer through Common Recourse
conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Ying, Z., Bourgeois, D., You, J., Zitmik. M., and Leskovec, GNNExplainer: Generating explanations for graph neural networks. In NeurIPS 2019.
Yuan, H., Yu, H., Gui, S., and Ji, S. Explainability in graph neural networks: A taxonomic survey. IEEE Trans. Puttern Anal, Mach. Intell., 2023.
12

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Appendix
A. Additional Related Work
summarize recent approaches for counterfactual explanations. (Abrate et al.) propose counterfactual explanations by sparsifying and densifying graphs, find counterfactuals through pattern deletion generation. ARES (Rawal & Lakkaraju. 2020) produces actionable two-level recourse summaries non-graphical datasets through optimization problem. Lastly, in (Magister et al., 2021), the "Human-in-the-LLon. framework integrates human feedback to enhance the relevance and interpretability of counterfactual explanations. Recent advancements include (He et al., 2024) generative flow network, (Qiu et al., 2024) robust counterfactual witnesses, et al., 2024) focus on unsupervised node representation learning.
B. Example for the FC problem
Setup. We follow the setting described below.
Given of input graphs: G
And counterfactual graphs: H 1H,, H2, H3, H4).
Each counterfactual H obtained by applying recourse f. i.e. a graph transformation, to an input graph G according to the following table:
Finding Counterfactuals to Maximize Common Recourse Coverage. follows:
Suppose the recourse transforms the input graph
Input Graphs Recourse
Counterfactual Graphs
G
S1
H
G1
f2
H2
G2
fa
H3
G3
fi
HA
G3
f3
H
We will write fiG) = H, to denote that the recourse fi applied to the input graph G₁ yields the counterfactual graph Hi. We say that an input graph G e G is covered by recourse f if:
both H and f have been chosen within the budget, and
(ii) f(G) = H.
Given budgets At = 2 (recourse) and T = 2 (counterfactuals), the goal of the FC problem is to select 2 counterfactuals in H that yield the best coverage on using at most recourse.
Application. Suppose choose counterfactual graphs Hi and H3. then the best recourse to pick are: Fg- [f, which allows to cover the three input graphs as follows:
((())) = Hi, fi(Ga) = H1, fa(G2) = H33
An intuitive way to see this problem is as "max 2-budget 2-cover problem", where 2-cover means that to "cover" an element, one has to cover it in the two budgets.
C. Additional Proofs and Analyses for Section 2
C.1. Proof of Theorem
Proof. We prove that the FCR problem is NP-Hard through a reduction from the maximum coverage problem. Consider the problem of covering U using the sets (S.) we build the following instance of the FCR problem:
13

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Let X be a graph binary classifier that accepts graph if and only if the graph has two nodes of the same color. To each My U. associate Gj. star graph with unlabelled central node and peripheral vertices. If uj is in k elements of S, we one-color & peripheral vertices with the colors {i uj E S.J. We define the common recourse Ti, for i S
follows: colors the middle vertex of a star graph using color i, and we take the corresponding counterfactuals as the inputs to this FCR problem.
Thus (G,) = 0 for all j and X (r.( = 1 if and only if uj E S, Hence from an optimal solution to this FCR problem. we derive an optimal solution for the maximum coverage problem (U, (S.).). Therefore FCR is NP-hard.
C.2. Analysis for The FCR problem
Let us define f as the function that associates to a set of common recourse its total coverage. is not hard to see that f is monotone, i.e f(F U {r}) 2 S(IF) for every set of recourse F, and recourse r. We recall the definition submodularity (Santiago & Yoshida, 2020), function is submodular if for any two sets A S B and for any element et
M(AU (e)) M(A) 2 M(BU (e)) - h(B)
(4)
In the rest of the paper, we denote by (B) the marginal gain of adding the set B to A, i. M(UB)) - -(A).. We now prove that f is submodular:
Proof. Let A S B be sets of recourse, and let be recourse. Suppose G is a counterfactual graph covered by r but no the any recourse in B, since A S B, is not covered by any elements of A. Therefore fa((r) fz(r))..
C.3. Budget Version of the FC problem
When we assume that the counterfactuals and recourse are all known, the FC problem becomes a budget problem: Problem (max 2-budget 2-cover problem). Given two budgets kn and 22 and two families of sets Si, S2, the goal is to find S C Sr. S2 C S2 verifying:
mazs, S. S1 S st. (S1) S k and size(S2) S k2.
where S, UsES; S.
To the best of our knowledge, this problem has not been studied. This is a variation of the maximum coverage problem. The budgeted maximum coverage problem (Khuller et al., 1999) another budget variation, where only one budget is considered, there no constraint about the intersection, but the sets costs and the rewards for covering elements can be different from 1. The multi-budget maximum coverage problem is another variation between knapsack and maximum coverage (Cellinese al., 2021), but there is only one family of sets to pick from, and we do not require double coverage. Another variation of the maximum coverage problem is called multi-coverage (Barman et al., 2019), where covering multiple times one element raises the objective value.
Another variation is called multi-set multi-cover, which uses one budget, and each element must be covered a certain number of times (Hall& Hochbaum, 1986; Hua et al., 2009; Gorgi et al., 2021).
C.4. Proof of Theorem 2
function h is called pseudo- if there exists 7 E (0, 1] such that for any pair of disjoint sets A, B:
Σ (e) 2 (B) cEB
(5)
Note that this y the minimum over all the YA for all sets A, B, where YA.B is a specific value of y for given A, B in equation We now proceed to the proof of Theorem 2:
Proof. Recall g is the function that associates set of counterfactuals with its best coverage through building common recourse.
We give an instance of the FC problem, and two sets A, B such that equation 5 is only true for 7A,B = 0. which means that there is no local sucuuu-submodularity bound. Consider the instance of the FC problem where R = 2, T > 4 and (54) some counterfactual graphs such that they each cover a different input graphs, G, is part of R, (recourse 1), G2 part of R2 (recourse 2), Gg. G4 parts of R3 (recourse 3). We set A to (G1, G2} and to (G,, G.). Then 9 (G3) = (G4) and g (B) =.
14

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
C.5. Proof of Theorem 3
We first prove that g, the optimization function for the FC problem with the added constraint C1, is pseudo-modular.
Proof. For every set A, and for every graph e in the problem space we have that R 2 ga(e) by problem definition, we also have that ga(e) by C1. So for two disjoint sets A, B part of the solution:
Σ ga(e) 2 91 eEB
Hence, g is gpeudo-modulle
The pseudo code of the Greedy algorithm for the FC problem with C1 is follows, where g denotes the function that associates to a set of counterfactual its best coverage through building common recourse and selecting the R best for coverage, and T is the maximum number of counterfactuals to use for the explanations. This algorithm was first introduced
Algorithm 4 GREEDY FC(g, 7)
I: Initialize the set of counterfactuals: So t-
2: for i 1 T do
3: Let M, C E' S be a subset of size T maximizing EeEM, 98, (e)
Let
an element uniformly chosen random of M,
5: S. <- S.-1 e
6: end for
7:
return ST
in the work of (Buchbinder et al., 2014). Applying Theorem 1.10 of (Santiago & Yoshida, 2020) the monotone and pseudo-modular function y (Theorem 3), shows that Algorithm 4 yields e1/R approximation in expectation the FC problem, where R is the maximum number of common recourse of the FC problem.
D. Detail of our method, COMRECGC for Section 3
D.1. The Pseudocode of MULTI-HEAD VRRW
The pseudo code for our multi-head VRRW is presented in Algorithm 5, where G; denotes the input graph where the random walk started or was last teleported for the i-th head, and H; denotes the current graph head is occupying: Lines 1-2 describe the initialization of the random walk, where S represents the set of counterfactuals we aim find. Lines 5-12 outline the regular behavior of the random walk as it moves towards counterfactuals. Lines 13-15 cover the teleportation process. Finally, lines 17-21 detail the update of the counterfactual set. In line 23, advance step in the random walk, and in line 24, we update the visit count of the graphs reached by the k heads during this step, following the principles of VRRW. This visit count influences the transition probabilities in Equation 2.
D.2. Analysis of the Random Walks
VRRW. A vertex reinforced random walk is random process with reinforcement that focuses on the number of visits of vertices (Pemantle, 2004) (Pemantle, 2007). To the best of our knowledge, theorical guarantees have only been derived for the special case where the initial transition matrix is symmetric (Volkov, 2001) (Benaïm & Tarrès, 2011), which not relevant for our application, as we want to identify counterfactuals with the random walk, as described in Equation 2.
RW. Let us consider classic, non-reinforeed, random walk with the following transition rule:
plue v) x (v())
(6)
Where pa(v) is the probability, assigned by the GNN, of vertex v being counterfactual, and uniform teleportation:
Pr (G)
G
We refer to (Lovász, 1993) for the theoretical results. The main purpose of the analysis for our application is to determine the mixing time and mixing rate of our walk, to tune the parameter M, the number of steps. We add the random walk the
15

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Algorithm 5 MULTI-HEAD VRRW(Ø, G, k, M,
1: GG.....CC Gk) <- random input graph from G, 0
2: (Hi..... H3) f- (G1,...,
3: fortel :M do
4: Let ~ Bernoull(()), u(1,.......
if then
6: for e E((,) do
7: Compute P(He, u) based on equation 2. end for
8:
Ve +- random neighbor of based on p(He, for : k do
11:
+ -rrgmingeN = (aam)))-((c44 2(G.)=(v)12
12:
end for
13:
else
14:
(GI..... Ga) f- random input graphs from G based on equation 3.
15:
(#i...., Ux) + (Gi...., "al....,Gra Gk).
16:
end if
17:
for i E 1: do
18:
C(u) C(v) +1
if (v.. > 0.5 then
20:
S - S { end if
21:
22:
end for
23:
(HI...., Hk) + (V1y-.., mk). N(H)) N(H)) ) 1,..., N(H)) N(Hkk) +
25:
end for
26:
return S
following constraint: the maximum distance of the head from its starting point is at most 30/2, to make the space of the random walk finite. By Corollary 5.2 in (Lovász, 1993), the mixing rate of the walk max([>2), (Aul), where A; is the i-th largest eigenvalue of the matrix D 1/2 M D)1/2, where My the transition matrix associated to our random walk and D the diagonal matrix with value 1/ l/degree(i).
Unfortunately, there two main obstacles that make this approach untractable: (1) of the graph which we do the random walk, is of size O[ (eG), 0), hence making it hard to extract the eigenvalues of the matrix Mre (2) Each node's 's transition rule is determined by the GNN's prediction, making the construction of the matrix Myn difficult.
The search space, the number of nodes
E. Additional Details on Experiments & Results
E. Choice of the random walk parameters M,
The values of parameters & and 7 have been chosen through experiments on the Mutagenicity datasets. We chose т, the probability of teleportation, to be compromise between the random walk being able to look far enough to find counterfactuals, while still being able to explore a good number of paths. Although higher values of & seem to yield slightly better coverage, as seen in Table 3, & increases the running time, the number of steps for the random walk to converge, and the memory usage. Hence, we decide to limit to 5 heads and to set M to relatively low 50, 000 steps.
E.2. Running time
We show the running time of COMRECGC, its VRRW (Algorithm 5) and Clustering (Algorithm 1) components, for the FCR problem in the datasets of our study Table 8. The running time follows the complexity given Section 3, with shorter running times for small datasets such as AIDS compared to Mutagenicity. The sparsity and size of the graphs in the datasets also play role, allowing the walk to explore more graphs in dataset such as Proteins.
16

---

COMRECGC C Global Graph Counterfactual Explainer through Common Recourse
Table 8. The running time in minutes of the different parts of COMRECGC for the experiments of Table 3.
NCI1 MUTAGENICITY
AIDS
PROTEINS
Algorithm
172
152
Algorithm
23
27
14
14
COMRECGC 124
199
75
166
E.3. Ablation Study
We give the performance the variation COMRECGC without some of its features on the FCR problem for the datasets in our study. We find the clustering be very important on large datasets such as MUTAGENICITY, but less the smaller PROTEINS. This is possibly explained by the ability of the VRRW to spend longer time pairing the same elements through different recourse, hence somewhat harmonizing some recourse.
Table 9. Results on the FCR problem of different variations of COMRECGC, in the same parameters setting as Section 4.
NCI1
MUTAGENICITY
AIDS
PROTEINS
Coverage
Cost Coverage
Cost
Coverage
Cost Coverage
Cost
COMRECGC
42.9%
4.95
51.8%
5.63
34.7%
6.74
46.4%
11.59
COMRECGC w/o clustering
10.1%
X
8.2%
x
13.6%
X
33.9%
x
COMRECGC w/o multi-head
21.4%
5.75
20.6%
6.91
14.2%
6.97
32.8%
10.65
E.4. Additional examples of common recourse
We provide additional examples of common recourse identified through COMRECGC, in the settings 0.1 and A 0.02., Figures 3 and 4.
In Figure observe larger molecules, which allow for 'larger recourse' consisting of three transformations. This is because transformations on larger molecules correspond to smaller variations in the embedding for the "same transformation", which is capped by A.
In Figure 4, on smaller molecules, we observe two types of transformations in the recourse, likely due to the increased value of the parameter compared to Figure 1. Indeed, a larger 0 allows for more distant counterfactuals.
E.5. Experiments with GAT, SAGE, GIN types of GNN
We train GAT(Velickovic et al., 201 GraphSAGE(Hamiloo et al., 2017), GIN (Xu et al.) GNNS model for binary classification task, consisting of three convolutional layers, a max pooling layer, and a fully connected layer, following best practices from the literature (Vu & Thai, 2020). The model trained with the Adam optimizer (Kingma & Ba, 2014) and learning rate of 0.001 for 1000 epochs. The vainiin//iidaaiionnessingg split is 80%/10%/10%, and the corresponding accuracy measures presented in Tables 10, 11, and 12.
Table 10. Accuracy of GAT on the graph binary classification task on NCII, MUTAGENICITY, AIDS and PROTEINS.
NCII MUTAGENICITY AIDS PROTEINS
Training 0.788
0.845
0.991
0.780
Validation 0.741
0.802
0.973
0.820
Testing 0.748
0.781
0.973
0.730
We experiment on COMRECGC and get the results for the FCR problem in Tables 13, 14 and 15. The parameters for COMRECGC are the same as for the experiments in Section and Table 3, in particular 0 0.1 and A 0.02.
17

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Figure 3. Common Recourse the MUTAGENICITY dataset: removing Hydrogen and Carhon, on the left mutagenetic input graphs, on the right two non mutagenetic graphs.
Table Accuracy of GraphSAGE graph binary classification on NCII, MUTAGENICITY, AIDS and PROTEINS.
NCI1 MUTAGENICITY
AIDS
PROTEINS
Training 0.854
0.896
0.992
0.825
Validation 0.783
0.856
0.978
0.847
Testing 0.809
0.795
0.940
0.748
E.6. Additional Dataset
study the MDB-BINARY and MDB-MULTI datasets (Yanardag Vishwanathan, 2015). The MDB-BINARY features movies from two genres (Action and Romance), where each graph represents co-occurrence network of actors in movie, recourse represents a way change the prediction from action movie romance movie. The IMDB-MULTI includes movies from three genres (Comedy, Romance, and Sci-Fi). Since current method is only interested in binary classification, we consider the following labels: Comedy and non-Comedy (i.e, Romance and Sci-fi). A recourse represents a way to change the prediction from comedy movie to a non-comedy movie.
The parameters for COMRECGC are the same as for the experiments Section 4 and Table 3, in particular = 0.1 and 0.02. The results are presented in Table 16.
E.7. Comparison to local CE explainer
We compare our method and GCFE to the popular local counterfactual baseline CF-GNNEXxlaainer (Lucic et al., 2022) in Table E.7.
The coverage of building common recourse explanations using only CF- CF-GNNEExpainneegeeennte counterfactuals is noticeably worse than the counterfactual mining methods, such ours or GCFFxplainer. This is likely explained by a number of reasons, such as (i) generating fewer counterfactual graphs (around 2k5 graphs for CT-GNNexplainer on Mutagenicity vs 50k+ for GCFExplainer and our method), (ii) only considering subgraphs of input graphs and (iii) not taking into account the and A parameters of the CR explanation.
18

---

COMRECGC Global Graph Counterfactual Explainer through Common Recourse
Figure 4. Common Recourse the MUTAGENICITY dataset: removing one Nitrogen, one Hydrogen, adding one Oxygen and one Carbon, on the left two mutagenetic input graphs, on the right two non-mutagenctic graphs
Table 12. Accuracy of GIN on the graph binary classification task on NCII, MUTAGENICITY, AIDS and PROTEINS.
NCT1
MUTAGENICITY
ATDS
PROTEINS
Training 0.863
0.849
0.999
0.810
Validation 0.826
0.800
0.951
0.847
Testing 0.789
0.784
0.946
0.748
Table 13. Results on the FCR problem for the task of explaining the GAT trained model. The parameters for recourse are the same as for
the experiments Section and Table 3, in particular 0.1 and A 0.02.
NCI1
MUTAGENICITY
AIDS
PROTEINS Coverage Cost
Coverage Cost Coverage Cost
Coverage
Cost
GCFEXPLAINER 24.4%
5.26
47.3%
5.82
27.6%
7.12
42.6%
10.54
COMRECGC (Ours)
35.6%
5.02
55.7%
6.05
30.7%
6.89
42.9%
10.27
Table Results on the FCR problem task of explaining the GraphSAGE trained model. The parameters for recourse are the same as for the experiments in Section and Table 3, in particular = 0.1 and A = 0.02
NCII
MUTAGENICITY
AIDS
PROTEINS Coverage
Coverage Cost Coverage
Cost
Coverage
Cost
Cost
GCFEXPLAINER 32.8%
4.86
46.5%
5.46
20.3%
7.38
68.6%
11.53
COMRECGC (Ours)
47.9%
4.76
50.9%
5.90
21.5%
7.16
69.4%
11.51
Table 15. Results the FCR problem for the task of explaining the GIN trained model. The parameters for recourse are the same as for
the experiments Section and Table 3, in particular 0.1 and A 0.02
NC11
MUTAGENICITY
AIDS Coverage
PROTEINS Coverage
Coverage Cost Coverage Cost
Cost
Cost
GCFEXPLAINER
31.2%
5.13
30.4%
6.05
14.7%
7.68
47.3%
12.21
COMRECGC (Ours)
45.6%
4.58
33.7%
6.41
16.6 %
7.34
48.6%
11.32
19

---

COMRECGC C Global Graph Counterfactual Explainer through Common Recourse
Table 16. Results on FCR problem task explaining the GIN trained model. The parameters for recourse are the same as for
the experiments in Section 4 and Table 3, in particular 0.1 and A 0.02.
IMDE-BINARY (Yanardag & Vishwanathan, 2015)
IMDB-MUULTT((aarrddg & Vishwanathan, 2015)
Coverage
Cost
Coverage
Cost
GCFEXPLAINER
76.5%
8.33
19.9%
7.65
COMRECGC
80.9 %
8.10
21.9%
7.70
Table Results on the FCR problem. Higher coverage corresponds generating common recourse that is shared by more input graphs. The cost (lower is better) refers to the total length of the recourse.
NCII
MUTAGENICITY
AIDS Coverage
PROTEINS Coverage
Coverage Cost Coverage
Cost
Cost
Cost
CF-GNNEXPLAINER
9.1%
7.5
8.4%
8.90
0.1%
0.35
0%
0
GCFEXPLAINER
21.4%
5.75
20.6%
6.91
14.2%
6.97
32.8%
10.65
COMRECGC (OURS)
42.9%
4.95
51.8%
5.63
34.7% %
6.74
46.4 %
11.59
20


Reviews:
[{"review_id": "wRvkYK9OIT", "reviewer": "Reviewer_pBUz", "summary": "This paper designs an algorithm COMRECGC for global graph counterfactual explanation (CE). It considers the finding common recourse (FCR) explanation to address the limitations of existing graph CE methods (relying on experts for recourse directions; separating the process of funding recourse direction from data fitting). \n\nThe paper includes a complexity analysis, and the code is publicly available. The experiment compares common recourse explanations and graph CE, and shows COMRECGC provide a comparable performance in global CE. Evaluations on benchmark datasets demonstrate strong performance.\n\n## update after rebuttal\nI appreciate the authors for their response, which addresses some of my concerns. I stick to the original score of weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your remarks and we appreciate the support for our work.\n\n>Q1: Could you include additional evaluations on efficiency, particularly in terms of time and space complexity?\n\n**Answer:** We make the following notes:\n* **Time complexity** We have provided the time complexity analysis of our method in Section 3.4 of the paper, and the running time in Appendix D.3. \n\n* **Space complexity:** The space complexity is upper bounded by the number of recourse we are generating through the random walk. The resulting complexity is $O(n|G|)$ where $|G|$ is the number of input graphs and $n$ is the number of top-visited counterfactuals during the random walk. We will add this discussion in the paper.\n\n>Q2: Could the authors provide any (empirical) evaluation for the model efficiency?\n\n**Answer:** \n\nWe would like to mention that we have provided time complexity in the paper (see the above answer). If you mean efficiency as effectiveness, we have performed extensive experiments (please Sec. 4 and Appendix D). To strengthen the claim of our model efficiency (or effectiveness) further, we provide the following **additional experiments**:\n\n- **Experiments on different GNN architectures:** GAT, GraphSAGE and GIN on the datasets of the paper for solving the FCR problem.\n\n-  **Experiments on 2 additional datasets, IMDB-BINARY and IMDB-MULTI:** we have compared our method to the GCFE counterfactual mining baseline for solving the FCR problem.\n\nThe results and methodology are available in **our response to Reviewer oYnL**, the tables are also available at: https://anonymous.4open.science/r/COMRECGC-3E4E/tables_additional_experiments.pdf.\n\n>Remark 1: Few typos are found and perhaps need a further proofread.\n\n**Answer:** We will go over the paper and fix the typos. Thanks!", "claims_and_evidence": "The claims in the submission are generally well supported.", "methods_and_evaluation_criteria": "It would be beneficial for the experiment to include additional evaluations on efficiency, particularly in terms of time and space complexity. Providing a more detailed analysis of computational cost would help assess the practical feasibility and scalability of the proposed approach.", "theoretical_claims": "The paper provides theoretical analysis for the FC problem and the complexity of the proposed method.", "experimental_designs_or_analyses": "The experimental design and analysis appear generally sound, with appropriate methodologies used to validate the proposed approach. However, the improvement in terms of cost does not seem significant. \n\nA more in-depth evaluation of efficiency, such as a detailed comparison of efficiency and robustness with baselines, would strengthen the analysis and further enhance the impact of the results.", "relation_to_broader_scientific_literature": "The paper is related to some graph-related scientific discovery and explanation fields.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The point of involving FCR and FC problems is novel, and the source code link is provided. \nBut in general, the improvement compared with existing GCE baselines does not seem very significant.", "other_comments_or_suggestions": "Few typos are found and perhaps need a further proofread.", "questions_for_authors": "Could the authors provide any (empirical) evaluation for the model efficiency?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ooePysyeSw", "reviewer": "Reviewer_dyVU", "summary": "The paper introduces COMRECGC, a framework for generating global counterfactual explanations for graph neural networks through common recourse. Unlike local counterfactual explanations which are instance-specific, this approach seeks to find a small set of transformations (recourse) that can convert multiple \"reject\" graphs into \"accept\" graphs, thereby providing model-level insights. The authors formalize two novel problem settings - FCR and FC - and prove their NP-hardness. COMRECGC combines a multi-head vertex reinforced random walk to explore the graph edit space for counterfactuals with a clustering approach to identify common recourse patterns. The method is evaluated on four real-world datasets where it substantially outperforms baseline approaches in terms of coverage (the fraction of input graphs explained) while maintaining comparable or lower recourse cost.\n\n## update after rebuttal\nI have updated my scores", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: Some part of the analysis of the FCR problem is missing.\n\n**Answer:** We will add the following in Appendix B.2:\n\nLet us define $f$ as the function that associates to a set of common recourse its total coverage. We prove that $f$ is submodular:\nLet $A \\subseteq B$ be sets of recourse, and let $r$ be a recourse. Suppose $G$ is a counterfactual graph covered by $r$ but not by any recourse in $B$. Since $A \\subseteq B$, $G$ is not covered by any elements of $A$. Therefore $f_A(\\{r\\}) \\geq f_B(\\{r\\})$.\n\n\n\n>Q2: Different GNN architectures.\n\n**Answer:** We provide the following **additional experiments**:\n\n- Experiments on different GNNs: GAT, GraphSAGE and GIN for solving the FCR problem.\n\n-  Experiments on 2 additional datasets, IMDB-BINARY and IMDB-MULTI\n\nThe results and methodology are available in **our response to Reviewer oYnL**.\n\n\n>Q3: Comparison with GCFExplainer with incorrect setting. \n\n**Answer:**\n- The results of GCFExplainer are different from the original paper since GCFExplainer aims at identifying global counterfactuals to explain, while the FCR and FC problems consist in finding common recourse, i.e graph transformations, to explain a GNN.\n\n- The comparison between our method and GCFExplainer is valid, because we define counterfactuals and recourse in the same way, with the same values for the parameters $\\theta$ and $\\Delta$ that define counterfactuals and common recourse.\n\n- We think comparison between our method and typical CE baselines are unfair. A typical CE explainer associates to each reject graph a single CE graph, which is often a subgraph. Both our method and GCFExplainer mine at least 10 times more  counterfactuals, and are not limited to subgraphs. Those counterfactuals are then used to build common recourse through clustering(see Algorithms 1,2,3 page 5 of the paper for more details). Therefore, adding classical CE explainer baselines is not relevant.\n\n>Q4: Table 8.\n\n**Answer:** Thank you! Although both the AIDS and Proteins dataset contain 1837 and 1113 graphs respectively, the number of \"reject\" graphs is 1473 in AIDS, while it is 366 for Proteins. We are explaining those reject graphs by providing 100 recourse in table 8. So the difference between the two datasets when looking at COMRECGC with or without clustering is possibly explained by the \"sparsity\" of Proteins reject graphs, and the difficulty to explain the whole dataset in only 100 recourse.\n\n\n\n>Q5: Fixed values for key parameters\n\n**Answer:** You are right! We have two values of each parameters ($\\theta=0.1$ or $0.15$, $\\Delta=0.02$ or $0.04$).\n\nThe parameters $\\theta$ and $\\Delta$ are crucial in the common recourse definition, and in the FCR and FC problem.\n\nWe agree that a finer sensitivity analysis is interesting, specially when the coverage for the NCI1 and Mutagenicity dataset almost double when the common recourse parameter $\\Delta$ goes from $0.02$ to $0.04$. The choice of $\\theta$ and $\\Delta$ is specific to each dataset and application, and we provide a few values to showcase their impact.\n\nA systematic sensitivity analysis is relevant for the overall method and comprehensive experiments will be included in the revision. \n\nWe provide new experiments for the sensitivity of $\\Delta$. **We observe that a higher $\\Delta$ allows for a more comprehensive explanation, as we are allowing similar recourse to be considered \"common\" more easily. The cost naturally rises as more explanations are covered.**\n\n**Table 1: Results of our method on the FCR problem for the task of explaining the GCN model on the Mutagenicity dataset for different values of $\\Delta$.**\n\n| $\\theta$       | $\\Delta$       | Coverage | Cost  |\n|---------|--------|----------|-------|\n| 0.1     | 0.02   | 51.8%    | 5.63  |\n| 0.1     | 0.025  | 67.15%   | 6.99  |\n| 0.1     | 0.03   | 75.35%   | 7.59  |\n| 0.1     | 0.035  | 83.88%   | 8.03  |\n| 0.1     | 0.04   | 90.0%    | 8.11  |\n\n\n\n\n>Q6: Key references are missing.\n\n**Answer:** We will include the references to the **global factual and local CE literature**:\n\nRecent advancements in counterfactual explanations (CE) for GNNs include He et al.'s (2024) generative flow network, Chhablani et al.'s (2024) game-theoretic approach, and Qiu et al.'s (2024) robust counterfactual witnesses. Verma et al. (2024) introduce InduCE, an inductive method for unseen data, while Kang et al. (2024) focus on unsupervised node representation learning. *While these approaches address local counterfactuals, the task of generating global counterfactual explanations for GNNs remains relatively unexplored.*\n\n>Q7: Paper is not self contained.\n\n**Answer:** We will add the related work section in the main body of the paper. The page limit for the paper is definitely a hard constrain, and we chose to prioritize the definition of the FCR and FC problem, as well as the concept of common recourse in our paper.", "claims_and_evidence": "I found the following main claims in this paper. \n1. FCR and FC are Np hard.  these are well supported with theoretical analysis. \n2. the proposed method outperforms baseline methods on the FCR and FC problems.  It is supported by experiments. However, only GCN is used.  So it could be more convincing. \n3.  They also mention that  the method worth considering for applications such as drug discovery or computational biology.  there is no much evidence like case study to support that.", "methods_and_evaluation_criteria": "Yes. The methods and evaluation approach are suitable for the counterfactual explanation problem.  The multi-head vertex reinforced random walk effectively explores the graph edit space, while the clustering approach sensibly identifies common patterns among recourse.", "theoretical_claims": "I briefly checked the proofs. I don't see problems, although some parts are missing, like the analysis of the FCR problem", "experimental_designs_or_analyses": "The authors use four benchmark datasets and provide both quantitative and qualitative results.     I have the following concerns. \n1. Only a single GNN model (3-layer GCN) is used throughout all experiments. Testing the approach on different GNN architectures (such as GraphSAGE, GAT, or GIN) would have strengthened the generalizability claims of the method.\n2. The authors only compare with GCFEXPLAINER and mention that it outperforms other baselines already. However, I think the settings are different, since the results of GCFEXPLAINER on these datasets are different from those in the original paper. So it is not clear whether in the new setting, GCFEXPLAINER is still the best baseline. A direct comparison with other counterfactual explainers under the same experimental conditions would provide stronger evidence.\n3. The ablation study in Table 8 effectively demonstrates component contributions but doesn't fully analyze why clustering is more important for some datasets than others. They briefly mention that clustering is \"important on large datasets such as MUTAGENICITY, but less so on the smaller PROTEINS.\" However, the PROTEINS dataset is not significantly smaller than AIDS, yet shows different behavior. This inconsistency is not adequately addressed.\n4. The paper uses fixed values for key parameters (θ=0.1 or 0.15, Δ=0.02) across most experiments, with limited sensitivity analysis in the appendix. More extensive parameter tuning would strengthen the robustness claims.", "relation_to_broader_scientific_literature": "The paper builds upon several research threads in the broader explainability and graph neural network literature. Its concept of global counterfactual explanations extends work on local counterfactual explanations for GNNs to the model level, addressing the interpretability gap when dealing with numerous local explanations. \nThe common recourse framework connects to actionable recourse research but innovates by identifying patterns across instances rather than just instance-specific actions. The multi-head vertex reinforced random walk ia from classic reinforcement random walk.", "essential_references_not_discussed": "There are some papers not discussed in the paper. \n\n[1] He, Kangjia, et al. \"Learning counterfactual explanation of graph neural networks via generative flow network.\" IEEE Transactions on Artificial Intelligence (2024).\n[2] Chhablani, Chirag, et al. \"Game-theoretic counterfactual explanation for graph neural networks.\" Proceedings of the ACM Web Conference 2024. 2024.\n[3] Qiu, Dazhuo, et al. \"Generating robust counterfactual witnesses for graph neural networks.\" 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024.\n[4] Verma, Samidha, et al. \"InduCE: Inductive counterfactual explanations for graph neural networks.\" Transactions on Machine Learning Research (2024).\n[5] Kang, Hyunju, Geonhee Han, and Hogun Park. \"Unr-explainer: Counterfactual explanations for unsupervised node representation learning models.\" The Twelfth International Conference on Learning Representations. 2024.", "other_strengths_and_weaknesses": "Strengths:\n\n1. new prpoblem formulation of the common recourse problem for graph counterfactual explanations.\n2. The theoretical framework is well-developed, with clear problem definitions and complexity analysis.\n3. effectively combines random walk exploration with clustering to produce useful explanations, and the empirical results demonstrate clear improvements over existing approaches.\n\nWeakness:\n1. The organization needs to improve. I think a significant weakness is that the paper is not self-contained. Several important concepts and algorithms are only briefly described with details relegated to appendices, making it difficult to fully understand the method without constantly referring to other sections.  The related work part is also put in the appendix. \n2. Some key references are missing\n3. experiments are not that comprehensive to support the effectiveness of the proposed method.", "other_comments_or_suggestions": "I think the factual global methods like XGNN and PGExplainr are also related to this topic.  I suggest the authors also add some discussion on that.", "questions_for_authors": "I don't have specific questions.   Please correct me if my understanding in the above sections is wrong.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DHPnBgz9s3", "reviewer": "Reviewer_yQhN", "summary": "In this study, the authors have formalized the problem of generating global counterfactual explanations for Graph Neural Networks (GNNs) with common recourse. Considering the NP-hard nature of the FCR and FC problems, the authors have developed COMRECGC, a method specifically designed to extract high-quality common recourse explanations. Experiments on real-world datasets show that COMRECGC consistently generates global common recourse explanations of significantly higher quality compared to the baseline methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your strong support and encouragement!\n\n>Q1: Testing the approach on different GNN architecture.\n\n**Answer:** We provide the following **additional experiments**:\n\n- **Experiments on different GNN architectures:** GAT, GraphSAGE and GIN on the datasets of the paper for solving the FCR problem.\n\n-  **Experiments on 2 additional datasets, IMDB-BINARY and IMDB-MULTI:** we have compared our method to the GCFE counterfactual mining baseline for solving the FCR problem.\n\nThe results and methodology are available in **our response to Reviewer oYnL**, the tables are also available at: https://anonymous.4open.science/r/COMRECGC-3E4E/tables_additional_experiments.pdf.\n\n>Q2: The writing of the authors needs to be improved. Since this paper involves many new concepts, the authors should illustrate them by giving more examples.\n\n**Answer:** We will add examples in the appendix, in particular for the FCR and FC problems introduced.\n\n>Q3: The authors have analyzed the Complexity Analysis. Then, what is the actual running efficiency of the model.\n\n**Answer:** We provide the time complexity analysis of our method in Section 3.4, and the running time in Appendix D.3. We will emphasize the reference to the Appendix in the complexity analysis section.\n\n>Q4: What does ”x” in Table 6 represent? \n\n**Answer:** The Table illustrates raising $\\theta$ from $0.1$ to $0.15$, which dramatically increased the number of recourse entering the clustering stage, making DBScan, the clustering algorithm we use for our experiment, intractable. Thank you, we will add this comment to the caption.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The key contributions of the paper is important to the broader scientific literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "1. The idea of this paper is very novel. The authors formalize the FCR problem. They provide a generalized version of the FCR problem, named FC, and derive an approximation algorithm for a constrained version of FC.\n\n2. Sufficient experimental results have proven the effectiveness of the method proposed by the authors.\n\n3. The authors have made the source code publicly available.", "other_comments_or_suggestions": "1. Besides GCN, the authors could attempt more GNN architectures to verify the generalizability of the method.\n2. The writing of the authors needs to be improved. Since this paper involves many new concepts, the authors should illustrate them by giving more examples.", "questions_for_authors": "1. The authors have analyzed the Complexity Analysis. Then, what is the actual running efficiency of the model?\n2. What does \"x\" in Table 6 represent?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d6ATBJipWr", "reviewer": "Reviewer_oYnL", "summary": "The authors focus on the question of generating global counterfactual explanations. They introduce the problem from a theoretical perspective. They introduce the problem of FCR and FC which correspond to Finding Common Recourse and Finding Counterfactual problems, respectively. They introduce these problems from a high-level theoretical perspective. They provide several theoretical guarantees such as: proving that FCR is a NP-hard problem, and that there exists an approximation for the FC problem with the given constraints. This motivates their algorithm, which uses a graph embedding, a multi-head vertex reinforced random walk to find CFs, and finally clustering to obtain common recourses.\nAfter designing their algorithm they implement it on several real-world datasets. They use the data sets MUTAGENICITY, NCI1, AIDS, PROTEINs. In particular, most of these datasets are in molecules. They train a base GNN (GCN) and experiment with parameters $\\theta$ and $\\Delta$. They then compute the coverage with respect to the cost.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: validity and sparsity metrics are missing.\n\n**Answer:** These two metrics have been considered, but under a different form in the definition of common recourse (in page 2 of our paper).\n\n**Validity:** It measures how often the recourse suggestion changes the model’s prediction. In our definition of recourse we access the oracle, so every counterfactual candidate is a counterfactual, and the validity of all our recourse is $1$.\n\n\n**Sparsity:** It measures how many edges or nodes need to be altered to reach a common recourse.\n\n- We used a normalized GED  in the paper. The sparsity is exactly equal to $Sparsity(G,G') = 1 - Normed GED (G,G')$ for $G,G'$ two graphs. Therefore sparsity is directly embedded in the definition of common recourse, where we explicitly limit the counterfactual to have sparsity at least $1-\\theta$, which in our experiments is typically a lower $0.90$ to $0.85$.\n\n-  We use the cost metric in our experiments, defined in Section 2.1, which accounts for the total distance from the covered input graphs to their closest attained counterfactual. Therefore the cost measure an aggregation over $1-Sparsity$.\n\n\n>Q2: Add more datasets, networks, graphs with many more nodes.\n\n**Answer:** As suggested, we provide additional experiments.\n\nWe study the IMDB-BINARY and IMDB-MULTI datasets (Yanardag & Vishwanathan, 2015). The IMDB-BINARY features movies from two genres (Action and Romance). The IMDB-MULTI includes movies from three genres (Comedy, Romance, and Sci-Fi). Since our current method is only interested in binary classification, we change the consider the following labels: Comedy and non-Comedy (i.e Romance and Scifi). The parameters for COMRECGC are the same as for the experiments in Section 4 and Table 3.\n*The results show that our method outperforms the baseline GCFExplainer in coverage on both datasets, while preserving a similar cost (higher coverage and lower cost are better).*\n\n**Table 1: Results on the FCR problem for the task of explaining the GIN trained model.**\n\n|  | **IMDB-BINARY** | **IMDB-BINARY** | **IMDB-MULTI** | **IMDB-MULTI** |\n|-|-|-|-|-|\n|  | Coverage | Cost | Coverage | Cost |\n| **GCFExplainer** | 76.5% | 8.33 | 19.9% | **7.65** |\n| **COMRECGC(Ours)** | **80.9%** | **8.10** | **21.9%** | 7.70 |\n\n\n\n\n>Q3: Testing the approach on different GNN architecture\n\n\n**Answer:** As suggested, we provide experiments with different architectures. \n\nWe train GAT(Velickovic et al., 2018), GraphSAGE(Hamilton et al., 2017), GIN (Xu et al., 2019) GNN model for a binary classification task, consisting of three convolutional layers, a max pooling layer, and a fully connected layer, following the literature (Vu & Thai, 2020). The model is trained with the Adam optimizer (Kingma & Ba, 2014) and a learning rate of 0.001 for 1000 epochs. The training/validation/testing split is 80%/10%/10%.\n\nThe training/validation/testing accuracy tables, alongside the result tables for the experiments are available at: https://anonymous.4open.science/r/COMRECGC-3E4E/tables_additional_experiments.pdf.\n\nWe test COMRECGC against the GCFE baseline. The parameters for the experiments and methods are the same as in Section 4 and Table 3 of the paper, in particular $\\theta = 0.1$  ($0.15$ for Proteins) and $\\Delta = 0.02$.\n**The results show that our method outperforms GCFExplainer in terms of coverage on all datasets for the GIN model explanation, while often offering a lower cost (higher coverage and lower cost are better).**\n\n**Table 2: Results on the FCR problem for the task of explaining the GAT trained model.**\n\n||**NCI1** | **NCI1** | **Mutagenicity** | **Mutagenicity** |   **AIDS** | **AIDS** | **Proteins** |**Proteins**|\n|-|-|-|-|-|-|-|-|-|\n|| Coverage | Cost | Coverage | Cost | Coverage | Cost | Coverage | Cost |\n| **GCFExplainer** | 24.4% | 5.26 | 47.3% | **5.82** | 27.6% | 7.12 | 42.6% | 10.54 |\n| **COMRECGC(Ours)** | **35.6%** | **5.02** | **55.7%** | 6.05 | **30.7%** | **6.89** | **42.9%** | **10.27** |\n\n\n---\n\n**Table 3: Results on the FCR problem for the task of explaining the GraphSAGE trained model.**\n\n|| **NCI1** | **NCI1**  | **Mutagenicity** | **Mutagenicity** | **AIDS** |**AIDS**  | **Proteins** | **Proteins**|\n|-|-|-|-|-|-|-|-|-|\n|| Coverage | Cost | Coverage | Cost | Coverage | Cost | Coverage | Cost |\n| **GCFExplainer** | 32.8% | 4.86 | 46.5% | **5.46** | 20.3% | 7.38 | 68.6% | 11.53 |\n| **COMRECGC(Ours)** | **47.9%** | **4.76** | **50.9%** | 5.90 | **21.5%** | **7.16** | **69.4%** | **11.51** |\n\n---\n\n**Table 4: Results on the FCR problem for the task of explaining the GIN trained model.**\n\n|  | **NCI1** | **NCI1** | **Mutagenicity** | **Mutagenicity** | **AIDS** | **AIDS** | **Proteins** ||\n|-|-|-|-|-|-|-|-|-|\n||  Coverage | Cost | Coverage | Cost | Coverage | Cost | Coverage | Cost |\n| **GCFExplainer** | 31.2% | 5.13 | 30.4% | **6.05** | 14.7% | 7.68 | 47.3% | 12.21 |\n| **COMRECGC(Ours)** | **45.6%** | **4.58** | **33.7%** | 6.41 | **16.6%** | **7.34** | **48.6%** | **11.32** |", "claims_and_evidence": "S1. The paper is well written and well founded. The main idea is novel and uses theoretical justification to motivate their framework. \nS2. Their reasoning behind design choices is mostly sound.\n\nS3. They provide initial experiments that showcase some of the promising behavior of their framework.\n\nO1. Their is a glaring lack of experiments. It is understandable the authors introduce a novel problem and emphasize that in their experiments however the main metrics are coverage and cost. These experiments are good at showing their methods desired properties but they do not showcase mainstream metrics and experiments such as validity, sparsity, and potentially some other metrics. All these metrics are not necessary but they bolster their framework's strengths. \n\nO2. Another issue is the lack of experiments. There are numerous types of datasets that have not been experimented on. Focusing primarily on molecular data leaves a glaring question for the readers: experimentally how does this framework work on other types of graphs (such as networks, etc.)? Not addressing this question also raises questions of how their framework works on graphs with many more nodes, edges, etc. This reviewer believes, in the current state of this paper, that these experiments do not prove this method's superiority over existing Counterfactual methods nor do it showcase the full behavior of their framework on graphs it is likely to encounter in the real world.", "methods_and_evaluation_criteria": "As stated before, several issues with their experimentation or lack thereof are:\nO1. Their is a glaring lack of experiments. It is understandable the authors introduce a novel problem and emphasize that in their experiments however the main metrics are coverage and cost. These experiments are good at showing their methods desired properties but they do not showcase mainstream metrics and experiments such as validity, sparsity, and potentially some other metrics. All these metrics are not necessary but they bolster their framework's strengths. \n\nO2. Another issue is the lack of experiments. There are numerous types of datasets that have not been experimented on. Focusing primarily on molecular data leaves a glaring question for the readers: experimentally how does this framework work on other types of graphs (such as networks, etc.)? Not addressing this question also raises questions of how their framework works on graphs with many more nodes, edges, etc. This reviewer believes, in the current state of this paper, that these experiments do not prove this method's superiority over existing Counterfactual methods nor do it showcase the full behavior of their framework on graphs it is likely to encounter in the real world.", "theoretical_claims": "no issues.", "experimental_designs_or_analyses": "For the graph embedding algorithm why did the authors just use a standard backbone of a GCN. It would be interesting to see various architectures trained and how they affect the framework.\n\nThe design of the current experiments are correct", "relation_to_broader_scientific_literature": "This paper works on generating global counterfactual explanations. Specifically extending this to the notion of common recourses which add several benefits.  Most existing works use local counterfactual explanations so the authors explore a relatively under-explored area.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Please refer to comments above.", "other_comments_or_suggestions": "Please address the weaknesses.", "questions_for_authors": "Can the authors address why they chose not to include experiments on other types of graphs such as networks, or with a larger scale. Also why did the authors not include more metrics to assess the counterfactual nature of their explanations such as validity. There are several standard metrics in graph interpretability papers that are absent here.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "n/a"}}]

Author rebuttal:

Meta-review: Post-rebuttal, all reviewers have converged on an acceptance recommendation, with their primary concerns addressed. After reviewing the paper and rebuttal, I agree that the work makes a meaningful contribution to global graph counterfactual explanation. I recommend acceptance. Please ensure that the necessary revisions are incorporated into the final version.
Decision: Accept (poster)