Within Machine Learning, Graph Neural Networks (GNNs) have emerged as prominent techniques, particularly excelling in tasks tailored for graph structures. Due to the intricate nature of GNNs and the essential role in conveying outcomes to users, there is a pressing demand to enhance the explainability of these approaches. Among state-of-the-art explanation strategies, counterfactual explanation provides intuitive and easily understandable insights into model predictions by showing how a small change in the input would lead to a diferent outcome. However, the absence of benchmarks and standardized tasks hampers the evaluation of such approaches. Moreover, there has not been an empirical comparison of counterfactuals and adversarial examples, both aiming to alter model outputs with minimal perturbations. This reproducibility study rigorously analyzes prominent GNNbased counterfactual explanation methods, contrasting them against established adversarial attack baselines. Our objective is to look into counterfactual methods through the lens of adversarials and thereby, explore the interconnectedness of these techniques and foster a deeper understanding of their combined utility and implications. We validate five selected GNN-based counterfactual explanation methods in two levels of local and model-level explanation and compare them to two well-established adversarial attack methods. Our findings reveal that adversarial methods can serve as a competitive baseline for counterfactual explanation on node classification, and in certain tasks, they may even outperform them.
Graph Neural Networks (GNNs) [
Addressing the need for transparency and interpretability, Explainable Artificial Intelligence (XAI)
has garnered substantial interest across various communities. Among these approaches, counterfactual
explanation (CE) [
CEUR Workshop
ISSN1613-0073 methods, the absence of established tasks, widely used metrics, and standardized benchmarks, has impeded comprehensive evaluations, hindering the establishment of robust and widely used baselines.
The exploration of adversarial attacks intersects with the study of counterfactuals (in fact, they have
even been shown to be equivalent [
Motivated by the lack of quantitative study and analysis of CE methods and also quantitative
comparison of AE and CE, our study conducts a thorough reproducibility analysis of prominent GNN-based
counterfactual explanation methods, juxtaposing their performance against established adversarial
attack baselines. Our investigation systematically validates five selected GNN-based counterfactual
explanation methods, namely C 2 [
We emphasize the significance of transparency and reproducibility in scientific research. Accordingly, we have made our code publicly accessible2, providing comprehensive details of all comparative experiments.
Perturbation
Matrix CF-GNNExplainer CF2 Generative
The field of interpretable ML has advanced significantly [ 20, 21, 22], particularly in local interpretability
with early methods like LIME [23] and SHAP [22]. These works laid the foundation for post-hoc
explainability, treating models as black boxes. Initial studies primarily focused on improving the
1https://www.theverge.com/2017/11/2/16597276/google-ai-image-attacks-adversarial-turtle-rifle-3d-printed
2https://github.com/amirreza-m95/CE_vs_AE
interpretability of the models themselves [24, 25]. In the context of GNNs, GNNExplainer [26] marked
a breakthrough by identifying subgraphs responsible for node-level predictions, though it focused
on factual explanations. The shift toward counterfactual explanations (CEs), as introduced by
CFGNNExplainer [16], enabled reasoning over “what-if” scenarios and inspired a range of new methods [
From a high-level view, CEs seek minimal perturbations that flip model predictions, closely resembling
adversarial examples (AEs). While [
We denote a graph as = ( , ℰ ) , where represents the set of nodes and ℰ denotes the set of edges. Each node ∈ is characterized by a feature vector ∈ ℝ .
The existing body of literature on GNN explainability has predominantly concentrated on scenarios
involving graph classification and node classification, with a focus on categorical output spaces (see [
In a message-passing GNN with layers, the embedding of a node is intricately tied to its -hop neighborhood. We introduce the term “neighborhood subgraph” to characterize this -hop neighborhood. Henceforth, for the sake of clarity, we will employ the term “graph” to denote the neighborhood subgraph when referring to node classification.
Counterfactual Reasoning: Let be the input graph and Φ( ) the prediction on . The task of the counterfactual approach is to introduce the minimal set of perturbations to distinguish a new graph ∗ such that Φ ( ) ≠ Φ ( ∗). Mathematically, this entails solving the following optimization problem. ∗ = arg min dist ( , ′) .. { ′ ∈ Φ( ) ≠ Φ ( ′) (1) where dist ( , ′) quantifies the distance between graphs and ′ and is the set of all graphs one may construct by perturbing . Typically, distance is measured as the number of preformed edge perturbations while keeping the node set fixed.
In the following, we detail the experimental setup for our studies.
Given our overall goals of (i) reproducing state-of-the-art counterfactual explanation methods, and (ii) comparing counterfactual explanation approaches to adversarial learning baselines, we address the following research questions in this paper:
(RQ1) How feasible is it to reproduce the outcomes of the state-of-the-art CE methods? To what degree do the underlying assumptions in these approaches withstand scrutiny? Which insights can be gained regarding the error modes associated with these methods?
(RQ2) What distinguishes counterfactual examples from adversarial examples within the framework of GNNs? How can these two directions mutually benefit each other?
(RQ3) Which CE performance evaluation metrics hold more promise? What are the respective advantages and drawbacks of each?
We evaluate the algorithms on a diverse set of datasets, encompassing both synthetic and real-world
scenarios. Specifically, we employ two synthetic datasets, BA-shapes and Tree-Cycles, introduced
by [26], adhering to the same setup as outlined in their work. BA-Shapes and Tree-Cycles are employed
for node classification, featuring predefined motifs (“house” and “cycle” structures) for interpretability.
For real-world contexts, we utilize Mutagenicity [
This study aims to replicate the most impactful and enduring methods from the CE era and timetested approaches from the AE community. The selection of approaches is guided by the following considerations:
(a) The chosen methods must have a significant influence and highly known by community through being used as the SOTA baseline (see Table 2). (b) We prioritize methods with diverse representation techniques to enhance the generalizability of our research. This diversity is crucial for capturing a comprehensive understanding of GNN explanation methodologies, as illustrated in Figure 1. (c) The selected methods are specifically drawn from the GNN context to maintain consistency within the framework of this study. 4.3.1. Counterfactual Methods We selected five representative counterfactual explanation methods (see Table 2) based on their influence and diversity.
CF2 [
GCFExplainer[17] is a model-level method for graph classification. It constructs a meta-graph of candidate counterfactuals and selects diverse explanations using vertex-reinforced random walks[36] and a greedy algorithm.
CF-GNNExplainer [16] is designed for node classification and learns a binary perturbation mask to sparsify the graph’s adjacency matrix, minimizing changes needed to alter the prediction.
CLEAR [18] uses a variational autoencoder to generate counterfactuals in latent space. It outputs complete graphs with edge weights reflecting uncertainty, closely resembling the original input.
RCExplainer [19] identifies linear decision boundaries via an unsupervised strategy, enhancing robustness by generalizing across instances. It generates concise counterfactuals by selecting edge subsets guided by a boundary-based loss. 4.3.2. Adversarial Methods We evaluate two widely used adversarial attack methods for graph-structured data [37]:
Nettack [30] targets node-level predictions by iteratively perturbing node features to deceive the GNN, while preserving the graph structure. It computes gradients to identify minimal changes that flip the model’s output.
Meta Attack [38] uses a meta-learning approach to generate global adversarial attacks. Trained on various graph datasets and models, it can eficiently poison graph classifiers without requiring gradient access during inference. 4.3.3. Configuration We employed the adversarial attack methods outlined earlier by utilizing the implementations available in the DeepRobust open-source project3. Subsequently, we seamlessly integrated these methods into our pipeline. We adhere to the recommended hyper-parameter settings provided by DeepRobust. It is important to highlight that certain modifications were necessary to harmonize these adversarial attack methods with counterfactual techniques, enabling a meaningful comparison of results on the same datasets. A noteworthy example is the Nettack method, which, by default, tends to both add and remove edges as a perturbation of the graph but to ensure a fair comparison with CE methods that primarily involve edge removal, we introduced constraints to the optimization method. These constraints guide the Nettack method to focus solely on edge removal, aligning it with the nature of CE methods. Further elaboration on these adjustments and their implications will be provided in Section 5.3. All the training is performed using an AMD Ryzen 2950X with 128GB RAM and a GeForce RTX 2070 with 8GB memory. 3https://github.com/DSE-MSU/DeepRobust We repeat our experiments 3 times and report the average performance. We share both our dataset processing scripts, the source code, and the hyper-parameters using an anonymous repository4.
In this section, we discuss diferent evaluation metrics used in the community and compare them to clarify the rationale behind the metrics of our choice for this study.
Necessity [
Necessity( ) =
∑|=|1 (Φ (ℛ ) ≠ Φ ( ))
Where is a graph set of , ℝ is a residual graph set of ℛ , Φ ( ) is the prediction of the model on , is explanation subgraph of and ℛ = − . In the same setting of variables, Fidelity [16] is the exact opposite metric:
Fidelity(ℱ ) =
∑|=|1 (Φ (ℛ ) = Φ ( ))
As a result, in the context of counterfactual reasoning, we want lower values for Fidelity and higher values for Necessity and Validity.
Suficiency is defined as the percentage of generated explanations that prove to be suficient for an instance to achieve the same prediction as using the entire graph. In essence, Suficiency intuitively quantifies the percentage of graphs where the explanation subgraph alone is capable of maintaining the GNN prediction unchanged.
Suficiency ( ) = ∑|=|1 (Φ ( ) = Φ ( )) ||
Explanation size serves as a minimality evaluation metric which refers to the count of removed edges, representing the disparity between the original graph and the counterfactual graph ′. Given our aim to minimize explanations, a smaller value for this metric is preferable.
Coverage is a metric for evaluating recourse representation ℂ for the graph classification task [ 17] which is the percentage of input graphs that possess nearby counterfactuals from , within a specified distance threshold .
Coverage(ℂ) = |{ ∈ ∣ min{(, )} ≤ }| /|| (5)
∈ℂ
In this context, [17] used the metric Cost which is recourse cost, representing the distance between each input graph and its respective counterfactual within the dataset. || || Cost(ℂ) = agg {min{(, )} ∈ ∈ℂ } This metric also closely resembles with the explanation size from local CE. (2) (3) (4) (6)
In this section, we present the results of our empirical study, shedding light on the performance and efectiveness of both adversarial examples and counterfactual explanations. Our experiments aim to provide insights into the comparative aspects of these methodological paradigms, addressing their impact.
We assess the reproducibility of each counterfactual explanation method by replicating their experiments and evaluating consistency with reported results.
CF2: All experiments ran smoothly except for the NCI1 dataset, due to missing code and data. We observed large fluctuations in the Necessity metric (0.58–0.90), depending on classifier performance and preprocessing. This suggests high sensitivity to the underlying model. Using the original Mutagenicity dataset (vs. Mutag0) also caused a drop in classification accuracy, though explanation performance remained stable.
CF-GNNExplainer: Reproduced results successfully despite minor code deprecations. Model performance was sensitive to hyperparameters, requiring re-optimization to match reported values.
GCFExplainer: As the only model-level method, it reproduced well using both pretrained and freshly trained models. However, its pretraining phase (VRRW) was resource-intensive, requiring a 256GB RAM machine due to memory constraints.
CLEAR: Results were partially reproducible. We matched the validity score on IMDB-M (0.91 vs. 0.96 reported) but could not evaluate the Community dataset due to unavailable data. On larger datasets (e.g., Mutagenicity), CLEAR failed due to memory issues, though it worked on the smaller Mutag0.
RCExplainer: The original code link was inactive, but we obtained a working version from the authors5. With that, we reproduced the results using both pretrained models and our own training.
In this section, we undertake a comparative analysis of the methods within the two primary categories of node and graph classification tasks. The evaluation is based on metrics outlined in Section 4.4, specifically Necessity, Suficiency, Explanation Size, Coverage and Cost. For node classification, we utilize the BA-shapes and Tree-Cycles datasets, while for graph classification, we employ the Mutagenicity and NCI1 datasets. These datasets were chosen due to their widespread adoption in the field, as indicated in Table 2. To ensure a thorough comparison, we attempted to use the most commonly adopted datasets and metrics. As a result, for some of the methods, we employed metrics and datasets that difer from those originally used in their respective research. We believe this approach opens up new possibilities for integrating various metrics and datasets, potentially enhancing the robustness of evaluations across diferent methodologies. The only exception to this approach is CLEAR, which utilized metrics and datasets not used in other papers. To ensure a fair comparison, we adapted the CLEAR method to the Mutag0 (non-original for CLEAR) dataset and also adapted C 2 to the Ogbg-molhiv dataset (from CLEAR), facilitating a more comprehensive evaluation of the method. For an overview of this experiment, we refer to Tables 3 to 4.
Our comparison for the graph classification task is shown in Table 3. The evaluation is based on the suficiency and explanation size metrics, with higher suficiency and lower size values indicating better performance. RCExplainer demonstrates strong performance on the Mutagenicity dataset with a suficiency score of 0.64. On the other hand, C 2 (Opt.) displays a lower suficiency score on both datasets compared to RCExplainer and GCFExplainer since it notably exhibits a much larger size, particularly on the NCI1 dataset with a size of 17.70, indicating a less concise explanation. Similarly, C 2 ( = 0) also shows lower suficiency scores on both datasets as expected and reported by authors. While C 2 ( = 0) achieves competitive suficiency scores, its larger explanation size makes it less concise than RCExplainer and GCFExplainer. In contrast, RCExplainer, which provides moderate suficiency scores and slightly better performance on NCI1, consistently produces smaller explanations, indicating higher conciseness across both datasets.
In summary, RCExplainer stands out for its balance of high suficiency and consistent size across datasets, making it a strong candidate for applications where interpretability and eficiency are paramount. Conversely, while C 2 (Opt.) and C 2 ( = 0) ofer competitive suficiency scores, their larger sizes may indicate more complex explanations. GCFExplainer, with its moderate suficiency scores and consistently low sizes, presents a viable alternative for scenarios where a balance between interpretability and complexity is desired. We also have to consider that GCFExplainer is the only model-level explanation method.
In Table 4, we include the Necessity metric to compare node classification methods. Suficiency values for CF-GNNExplainer are not presented in the paper as this method does not incorporate suficiency in its optimization process. CF-GNNExplainer primarily concentrates on minimizing perturbations to change the class label without explicitly optimizing for generating a concise summary of the graph. However, CF-Explainer demonstrates moderate performance with Necessity scores of 0.61 and 0.79 on BA-Shapes and Tree-Cycles datasets respectively, indicating its capability to identify essential features for classification. CF-Explainer exhibits relatively low sizes on both datasets, with values of 2.39 and 2.09, suggesting concise explanations.
C 2 ( = 0) and C 2 ( = .) outperform CF-GNNExplainer in terms of Necessity on both datasets. However, both variants of C 2 display larger sizes compared to CF-Explainer, with values ranging from 3.6 to 7.76, suggesting potentially more complex explanations. To facilitate a more comprehensive comparison between these two methods while maintaining a fixed explanation value, we evaluated their performance on the Necessity metric. This analysis revealed that CF-GNNExplainer exhibits superior performance at lower explanation size values. However, as we progress towards higher explanation size values, CF2 outperforms CF-GNNExplainer. We refer to the results depicted in Figure 2 for further insights into the comparison between these two methods.
Overall, CF-Explainer ofers concise explanations with moderate Necessity scores, but lacks at suficiency. C 2 variants provide more comprehensive explanations with higher Necessity and suficiency scores, albeit at the cost of larger sizes, indicating potentially more complex explanations. Depending on the specific requirements of the application, practitioners may choose between CF-Explainer for its simplicity and C 2 variants for their comprehensiveness. These findings are novel, as no prior studies have conducted such evaluation and comparison of these methods.
Table 3 compares CF2, CLEAR, and others across Mutag0 and Ogbg-molhiv. CF2 ofers compact, high-suficiency explanations, while CLEAR sufers from scalability issues, failing on larger datasets due to memory limitations. These results emphasize the need to balance accuracy, explanation size, and scalability in real-world graph classification tasks.
Building on the theoretical connections between counterfactual explanations (CEs) and adversarial examples (AEs), we compare two representative methods from each: Nettack vs. CF2 on the BA-Shapes dataset (node classification) and Meta Attack vs. GCFExplainer on Mutagenicity (graph classification). Results are summarized in Figures 2 and 3.
To ensure fair comparison, we adapted Nettack to align with CF2’s constraints by limiting it to edge deletions within 3-hop neighborhoods and using the same evaluation pipeline. As shown in Figure 2, Nettack achieves higher Necessity scores at low perturbation levels, consistent with its goal of minimal changes. This supports its role as a strong baseline when minimal perturbations are desired.
In graph classification, Figure 3 shows that GCFExplainer outperforms Meta Attack in both coverage and cost, indicating that AEs are less efective for generating diverse, interpretable explanations. Meta Attack introduces larger changes while remaining less competitive, highlighting the trade-ofs in global adversarial perturbations.
In this section, we delve into the metrics used for comparing and analyzing methods, as outlined
in Table 2. It’s noteworthy that none of the papers we studied used the same metrics for evaluation,
posing challenges when comparing methods. Additionally, conflicts in the interpretation of these
metrics further complicate matters. For example, regarding suficiency, [
Moreover, there are limitations in these metrics’ ability to guide model improvement. For instance, in the case of the Fidelity metric, [16] showed that the Random algorithm outperforms all other methods with 0.0 percent accuracy, leaving no room for enhancement. This misconfiguration arises since the metric evaluates correctness based on ground truth labels rather than predictions, resulting in random perturbations failing to impact model performance, leading to a minimum fidelity score. Additionally, as observed in the Necessity metric for C 2, results fluctuate depending on classifier performance, underscoring the need for benchmarked metrics within the CE community. These insights underscore the complexities in metric interpretation and stress the importance of standardized evaluation protocols in CE research.
In this reproducibility paper, we conducted a comprehensive empirical study on prominent GNN-based counterfactual explanation methods, juxtaposing their performance against established adversarial attack baselines. Through our investigation, we systematically validated five selected GNN-based CE methods, namely C 2, CF-GNNExplainer, GCFExplainer, CLEAR, and RCExplainer, shedding light on their strengths, limitations, and contextual relevance.
Our comparative analysis revealed nuanced insights into the performance of these methods across various datasets and tasks. Notably, RCExplainer emerged as a standout performer in graph classification tasks, exhibiting a balance of high suficiency and consistent explanation size. Conversely, while C 2 variants displayed competitive suficiency scores, they often presented larger explanation sizes, potentially indicating more complex explanations.
Our study lays the groundwork for several avenues of future research aimed at advancing the field of XAI and GNNs. Here, we outline potential directions for further exploration: (a) The intersection of CE and adversarial attacks presents opportunities for developing hybrid approaches that leverage the strengths of both paradigms. Future work could explore the integration of CE and adversarial defense strategies to develop more robust and interpretable AI systems. (b) Future research could explore the development of context-aware counterfactual explanation methods tailored to specific application domains. Context-awareness involves considering additional contextual information such as user preferences, domain-specific constraints, and situational factors when generating explanations. (c) Future research could focus on unifying and standardizing metrics used for evaluating counterfactual explanation methods.
The author(s) have not employed any Generative AI tools. network explanations based on counterfactual and factual reasoning, in: F. Laforest, R. Troncy, E. Simperl, D. Agarwal, A. Gionis, I. Herman, L. Médini (Eds.), WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, ACM, 2022, pp. 1018–1027. URL: https://doi.org/10.1145/3485447.3511948. [16] A. Lucic, M. A. ter Hoeve, G. Tolomei, M. de Rijke, F. Silvestri, Cf-gnnexplainer: Counterfactual explanations for graph neural networks, in: G. Camps-Valls, F. J. R. Ruiz, I. Valera (Eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, PMLR, 2022, pp. 4499–4511.
URL: https://proceedings.mlr.press/v151/lucic22a.html. [17] Z. Huang, M. Kosan, S. Medya, S. Ranu, A. K. Singh, Global counterfactual explainer for graph neural networks, in: T. Chua, H. W. Lauw, L. Si, E. Terzi, P. Tsaparas (Eds.), Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM 2023, Singapore, 27 February 2023 - 3 March 2023, ACM, 2023, pp. 141–149. URL: https://doi.org/10.1145/3539597. 3570376. [18] J. Ma, R. Guo, S. Mishra, A. Zhang, J. Li, CLEAR: generative counterfactual explanations on graphs, in: S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh (Eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022. URL: http://papers.nips.cc/paper_files/paper/2022/hash/ a69d7f3a1340d55c720e572742439eaf-Abstract-Conference.html. [19] M. Bajaj, L. Chu, Z. Y. Xue, J. Pei, L. Wang, P. C. Lam, Y. Zhang, Robust counterfactual explanations on graph neural networks, in: M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, J. W. Vaughan (Eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, 2021, pp. 5644–5655. URL: https://proceedings.neurips.cc/paper/2021/hash/ 2c8c3a57383c63caef6724343eb62257-Abstract.html. [20] A. Ghorbani, J. Wexler, J. Y. Zou, B. Kim, Towards automatic concept-based explanations, in: H. M.
Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, R. Garnett (Eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019, pp. 9273–9282. URL: https://proceedings.neurips.cc/paper/2019/hash/77d2afcb31f6493e350fca61764efb9a-Abstract. html. [21] A. R. Mohammadi, A. Peintner, M. Müller, E. Zangerle, Are we explaining the same recommenders? incorporating recommender performance for evaluating explainers, in: RecSys ’24, ACM, 2024, p. 1113–1118. [22] A. Ghorbani, J. Y. Zou, Neuron shapley: Discovering the responsible neurons, in: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/hash/ 41c542dfe6e4fc3deb251d64cf6ed2e4-Abstract.html. [23] M. T. Ribeiro, S. Singh, C. Guestrin, ”why should I trust you?”: Explaining the predictions of any classifier, in: B. Krishnapuram, M. Shah, A. J. Smola, C. C. Aggarwal, D. Shen, R. Rastogi (Eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, ACM, 2016, pp. 1135–1144. URL: https://doi.org/10.1145/2939672.2939778. [24] A. Peintner, A. R. Mohammadi, E. Zangerle, SPARE: shortest path global item relations for eficient session-based recommendation, in: J. Zhang, L. Chen, S. Berkovsky, M. Zhang, T. D. Noia, J. Basilico, L. Pizzato, Y. Song (Eds.), Proceedings of the 17th ACM Conference on Recommender Systems, RecSys 2023, Singapore, Singapore, September 18-22, 2023, ACM, 2023, pp. 58–69. URL: https://doi.org/10.1145/3604915.3608768. [25] A. Peintner, A. R. Mohammadi, E. Zangerle, Eficient session-based recommendation with contrastive graph-based shortest path search, ACM Trans. Recomm. Syst. 3 (2025). URL: