COMRECGC: Global Graph Counterfactual Explainer through Common Recourse

Q1: validity and sparsity metrics are missing.

Answer: These two metrics have been considered, but under a different form in the definition of common recourse (in page 2 of our paper).

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$.

Sparsity: It measures how many edges or nodes need to be altered to reach a common recourse.

• 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$.

• 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$.

Q2: Add more datasets, networks, graphs with many more nodes.

Answer: As suggested, we provide additional experiments.

We 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. 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).

Table 1: Results on the FCR problem for the task of explaining the GIN trained model.

Q3: Testing the approach on different GNN architecture

Answer: As suggested, we provide experiments with different architectures.

We 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%.

The 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.

We 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$. 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).

Table 2: Results on the FCR problem for the task of explaining the GAT trained model.

---

Table 3: Results on the FCR problem for the task of explaining the GraphSAGE trained model.

---

Table 4: Results on the FCR problem for the task of explaining the GIN trained model.

Thank you for your strong support and encouragement!

Q1: Testing the approach on different GNN architecture.

Answer: We provide the following additional experiments:

• Experiments on different GNN architectures: GAT, GraphSAGE and GIN on the datasets of the paper for solving the FCR problem.

• 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.

The 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.

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.

Answer: We will add examples in the appendix, in particular for the FCR and FC problems introduced.

Q3: The authors have analyzed the Complexity Analysis. Then, what is the actual running efficiency of the model.

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.

Q4: What does ”x” in Table 6 represent?

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.

Q1: Some part of the analysis of the FCR problem is missing.

Answer: We will add the following in Appendix B.2:

Let us define $f$ as the function that associates to a set of common recourse its total coverage. We prove that $f$ is submodular: Let $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\})$.

Q2: Different GNN architectures.

Answer: We provide the following additional experiments:

• Experiments on different GNNs: GAT, GraphSAGE and GIN for solving the FCR problem.

• Experiments on 2 additional datasets, IMDB-BINARY and IMDB-MULTI

The results and methodology are available in our response to Reviewer oYnL.

Q3: Comparison with GCFExplainer with incorrect setting.

Answer:

• 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.

• 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.

• 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.

Q4: Table 8.

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.

Q5: Fixed values for key parameters

Answer: You are right! We have two values of each parameters ($\theta=0.1$ or $0.15$, $\Delta=0.02$ or $0.04$).

The parameters $\theta$ and $\Delta$ are crucial in the common recourse definition, and in the FCR and FC problem.

We 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.

A systematic sensitivity analysis is relevant for the overall method and comprehensive experiments will be included in the revision.

We 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.

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$.

Q6: Key references are missing.

Answer: We will include the references to the global factual and local CE literature:

Recent 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.

Q7: Paper is not self contained.

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.

Thank you for your remarks and we appreciate the support for our work.

Q1: Could you include additional evaluations on efficiency, particularly in terms of time and space complexity?

Answer: We make the following notes:

• 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.

• 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.

Q2: Could the authors provide any (empirical) evaluation for the model efficiency?

Answer:

We 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:

• Experiments on different GNN architectures: GAT, GraphSAGE and GIN on the datasets of the paper for solving the FCR problem.

• 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.

The 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.

Remark 1: Few typos are found and perhaps need a further proofread.

Answer: We will go over the paper and fix the typos. Thanks!