arXiv:2609.05113v1 [cs.LG] 4 Sep 2026
A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edits Maria Myrto Villia
Filippos Gouidis
[email protected] Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) Heraklion, Greece Computer Science Department, University of Crete Greece
[email protected] Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) Heraklion, Greece Computer Science Department, University of Crete Greece
Theodore Patkos
Panos Trahanias
[email protected] Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) Heraklion, Greece
[email protected] Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) Heraklion, Greece Computer Science Department, University of Crete Greece
Abstract Counterfactual explanations for graph-structured data seek to determine minimal and realistic modifications required in an input graph to alter a model’s prediction to a predefined output. Although counterfactual explainers that support modifying the graph by both adding and removing edges have recently emerged, there is still a lack of general and efficient methods, especially when considering the quality of the generated explanations. Moreover, the problem remains far from solved, as existing methods exhibit different strengths and weaknesses, often trading off between explanation size, coverage and quality. For this reason, it is important to identify where each method performs well and where it falls short, so as to guide future research in the field. Thus, our study compares six state-of-the-art (SOTA) models on a diverse set of real-world and synthetic datasets, covering both binary and multi-class graph and node classification tasks, and evaluates their performance using diverse quantitative and qualitative metrics.
Keywords explainable AI, counterfactuals, graph neural networks
1
Introduction
Counterfactual explanations have emerged as a powerful paradigm in explainable Artificial Intelligence (AI), seeking to provide insight into the behavior of black-box, data-driven AI models [10, 15, 16]. This perspective is especially valuable for graph-structured data, where explainability is inherently difficult due to the complex interactions between nodes, edges, and features [35]. Thus, the demand for trustworthy AI systems has naturally extended to Graph Neural Networks (GNNs). Graphs are widely used to represent complex relationships in a variety of domains, including chemical molecules, social networks, and traffic systems. To capture complex and challenging graph structures, GNNs have been introduced as a powerful class of models capable of receiving graphs as input, learning representations, and
making predictions. GNNs are able to capture both the structure of the graph and the features of individual nodes to make predictions. Typical downstream tasks addressed by GNNs include graph classification, where an entire graph is assigned a label, e.g., whether a molecule represented as a graph is toxic or not; node classification, where each node is labeled individually, e.g., predicting the topic of a paper in a citation network, and link prediction, which aims to infer missing connections between nodes or complete patterns inside the graphs. Early approaches to explainability in GNNs focused on locallevel factual methods [1, 8, 35], which, given an already trained model and an input graph, aim to identify the most influential subgraph responsible for a specific prediction. These methods, which dominated the field of GNN explainability for years, typically assess how the prediction changes when certain components of the graph are removed, highlighting the elements that are crucial for the model’s decision. Counterfactual explanations (CfXs) on graphs have a much shorter history [10, 16, 26]. However, they provide a complementary advantage by going a step further than just identifying important graph features. They indicate not only why a prediction was made, but also what should be changed to alter it. Specifically, counterfactual explanation methods aim to identify the minimal modifications to the graph structure or node features required to alter the prediction of the model. In graph classification, these modifications aim to change the predicted label of the entire graph and may involve perturbations anywhere in the graph. In node classification, they are intended to change the label of a target node, typically by modifying its local neighborhood. Initial attempts of counterfactual GNN explainability borrow insights from the progress achieved in factual methods: in a style similar to factual explainers, they apply various techniques for edge and feature masking, limiting the search for counterfactuals to substructures of the input graph. This approach significantly hinders the informativeness of counterfactuals and often results in out-of-distribution explanations [4].
SETN 2026, September 09–11, 2026, Chania, Greece
To address these issues, a class of novel methods have been proposed recently, introducing more flexible perturbation strategies, including both edge additions and deletions. Although early works on CfX generation with the ability to both add and delete edges adopted domain-specific assumptions, more generic approaches started to emerge over the last few years, bringing insightful ideas from diverse, yet related fields, such as adversarial attacks [25, 37], diffusion models [4], even computer vision-inspired spectral style transfer [28]. Notably, due to the rapid advancement in the field, these systems have not been contrasted against each other yet, neither in recent survey articles [10, 16, 26] nor in the experimental evaluation of the individual systems. Yet, this new perspective introduces a significant paradigm shift in the context of counterfactual post-hoc GNN explainability. To this end, in this paper, we provide a comprehensive comparison of state-of-the-art CfX methods for GNNs. In particular, the contributions of this survey are summarized as follows: • We provide a comprehensive and in depth assessment of state-of-the-art methods for post-hoc, model-agnostic counterfactual explainability for GNNs addressing graph and node classification tasks, extending a recent initial evaluation given in [31]. • Our study spans a diverse set of commonly employed datasets, including both real-world and synthetic benchmarks, covering binary and multiclass classification settings. More importantly, it adopts a multi-faceted perspective, reporting evaluation metrics that assess not only the performance and efficiency of the explainers, but also the quality of explanations generated. • We offer valuable insights into the research challenges ahead, offering the potential to drive future exploration within a field that is still in its early stages, but has seen a sharp rise in attention over the past few years.
2 Literature Classification 2.1 Factual Explainability of GNNs The explainability of GNNs is less explored than that of deep neural models for images and text. Recent review articles paint the picture of the current progress [8, 18, 35]. The majority of GNN explainers are factual, instance-level, post-hoc models. GNNExplainer [33], one of the most popular models to date, optimizes soft masks on edges and attributes, aiming to maximize the number of those that can be eliminated while preserving original predictions as much as possible. Other explainers also employ similar perturbation techniques, including SubgraphX [36] which performs Monte Carlo tree search to find the most important subgraph, ZORRO [9] which uses fidelity to review the search process, or PGExplainer [20] and GraphMask [29] that train a deep neural network to predict effective edge perturbation masks. The emphasis on generating subgraphs is shared among all these models. GraphLime [12], on the other hand, employs a surrogate model, which can assign large weights to features that are important. Model-level post-hoc explanation, where the explanation is not tailored to a specific input graph, instead aims to identify generic rules that apply to any input, is more challenging. A notable example is XGNN [34] which applies a graph generation module to
Villia et al.
identify patterns in input graphs that lead to specific predictions. Recently, self-explainable GNNs, such as SE-GNN [7] and SES [14], have been proposed to provide explanations alongside predictions. Overall, the progress in factual GNN explainability is rapid, creating high expectations for future advancements in the field.
2.2
Counterfactual Explainability of GNNs
Contrary to factual GNN explainers, counterfactual explainability in graphs is a relatively recent field, as detailed in recent survey articles [10, 16]. Building off of the momentum gained in factual explainability, most approaches target local-level, post-hoc explanations. For instance, CF-GNNExplainer [19] iteratively optimizes a binary perturbation matrix, while RCExplainer [3] learns the shared decision region of the target GNN across multiple input graphs and generates edge masks trying to ensure that the input graph and the counterfactual graph reside on the opposite side of the decision boundary. MOO [17] and 𝐶𝐹 2 [30] balance mask learning between factual and counterfactual explanation generation using heuristically determined search algorithms. CFExplainer [6], on the other hand, optimizes mask perturbations to reduce the likelihood of producing the original prediction. These models adapt effectively the different strategies to the requirements of counterfactual explainability, but as already mentioned, they only consider edge removal, leading to explanations that are subgraphs of the input graph. Edge addition has been incorporated into LEGIT [2] and MEG [24], highlighting the benefits of generating CfXs. However, the specification of all possible states needed by their Reinforcement Learning module requires extensive domain knowledge, making it difficult to generalize the approach. CLEAR [21] adopts a different approach, based on a variational autoencoder architecture, whose regularization term enforces the model to make minimal changes to the graph structure. From a similar perspective, GREASE [5] adopts a Relational Graph Convolutional Architecture to learn a surrogate model to generate CfXs. Moreover, GREASE is domainspecific, particularly designed for recommendation tasks, while CLEAR requires the existence of an underlying causal model of the data, which often is not available. Finally, C2Explainer [22] employs domain-independent edge masking while limiting admissible additions to a predefined supergraph. Recently, the goal of generating CfXs that apply to large proportions of input graphs has been adopted by global counterfactual explainers, such as GCFExplainer [13] and GlobalGCE [11]. Despite the different focus, we again observe the same pattern: the former model both adds and removes edges, but adopts a random walks approach, while the latter, aiming to reduce complexity, implements an autoencoder, in order to generate important counterfactual graphs, yet concentrates on subgraph explanations only. Building on the above developments, various counterfactual explainers that allow both edge addition and deletion, enabling more general graph transformations and improved performance, have been proposed in recent years. RSGG-CE [25] is a model in which, during training, the generator learns to transform graphs from the explainee class into counterfactual graphs of the opposite class, while the discriminator distinguishes these generated graphs from real graphs belonging to the target class. RSGG-CE manages to
A Review of Counterfactual GNN Explainers
Figure 1: (a) Predictions on drug-drug interaction networks constitute a prominent application domain of Graph Neural Networks (b) subgraph-based explanations identify important edges of the input data (c) We argue that supergraphbased explanations can also offer useful insights
overcome the high complexity with an optimized sampling mechanism. More recently, ATEX-CF [37] also leverages adversarial attack strategies to jointly model edge additions and deletions to generate counterfactual explanations, focusing on node classification tasks. D4Explainer [4] employs a denoising diffusion model to model the underlying distribution of explanation graphs. The method demonstrates strong performance while supporting both factual and counterfactual explanations. However, its high computational complexity and restriction to diffusion over discrete features limit its applicability. Finally, GIST [28] proposes a backtracking mechanism to cross the oracle’s decision boundary, based on spectral style transfer. Although the approach improves performance in binary classification, it generates large explanations and fails to control predictions in multi-label settings. Notably, most state-of-the-art models, such as D4Explainer, RSGGCE and GIST, have been evaluated primarily against baselines that only allow edge removal. In our recent study [31], DR-CFGNN was introduced, adopting insights from the link prediction research, but focused exclusively on graph classification tasks. The current review offers an extended and more in depth comparative evaluation of recent frameworks for both graph and node classification tasks.
3
Preliminaries
To illustrate the limitations of counterfactual GNN explainers, which are only capable to remove edges, and the important new perspective that the new generation of counterfactual GNN explainers bring, we describe a use case from the domain of bioinformatics. Consider a classifier trained by means of a drug-to-drug interaction network to predict whether an adverse reaction would exist between two drugs if taken together. Such networks are largely incomplete, since examining all chemical reactions by performing clinical or laboratory experiments is impractical due to the potential harms to patients, in addition to being labor-intensive and requiring high financial resources. Recent advances in AI help predict missing edges (correlations), by studying for instance the molecular structure and chemical features of the ingredients. Let us assume that for a particular input graph (Fig. 1a), the classifier predicts that a combined medication scheme with drugs A and B would be safe; a typical subgraph-based explainer will output those nodes that influence the most the given prediction (Fig. 1b), and a CfX would
SETN 2026, September 09–11, 2026, Chania, Greece
aim to modify this subgraph, in order to change the prediction. Nevertheless, an explanation in the form of an expansion of the original graph data may reveal that if an interaction between drug A and drug C existed, the classifier would generate an increased risk of hypersensitivity reaction instead (Fig. 1c). Such an explanation may constitute a reason for further investigation if a patient is already under treatment with drug C and no definite medical data exist to eliminate such a possibility. In the sequel, let 𝐺 = {𝑉 , 𝐸} = {A, X} two alternative representations of a graph 𝐺, where 𝑉 = {𝑣 1, .., 𝑣 𝑁 } the set of nodes, 𝐸 ⊆ 𝑉 ×𝑉 the set of edges, A ∈ {0, 1}𝑁 ×𝑁 the binary adjacency matrix, and X ∈ R𝑁 ×𝑑 the feature matrix. Without loss of generality, we define below factual and counterfactual explanation for graph and node classification tasks, which are the most commonly explored tasks among most of the available explainers. Graph classification : Let Φ : G → Y denote a trained GNN classifier (oracle), where G is set of graphs and Y = 1, . . . , 𝐶 is the label space. Given a prediction Φ(𝐺) = 𝑦, where a single label is assigned to each graph, a factual GNN explainer ΨΦ,𝐹 (·) seeks to identify one or more subgraphs 𝐺 𝐹 ⊂ 𝐺 that explain the prediction of Φ, such that the predicted label remains unchanged, i.e., Φ(𝐺 𝐹 ) = Φ(𝐺). In contrast, a counterfactual explainer ΨΦ,𝐶𝐹 (·) seeks to identify one or more counterfactual graphs 𝐺 𝐶𝐹 that differ minimally from 𝐺 while remaining plausible, and yield a different prediction, i.e., Φ(𝐺 𝐶𝐹 ) ≠ Φ(𝐺). According to [27], a counterfactual for 𝐺 is within the distribution of valid counterfactuals given by 𝑎𝑟𝑔𝑚𝑎𝑥 𝑃 (𝐺 𝐶𝐹 |𝐺, Φ(𝐺), ¬Φ(𝐺))
(1)
𝐺 𝐶𝐹 ∈ G𝐶𝐹
where G C F is the set of all possible counterfactuals by perturbing 𝐺, and ¬Φ(𝐺) indicates any other class from Φ(𝐺). The problem is typically reformulated as an optimization problem that aims to identify minimal graph edits that change the prediction; yet, an acceptable CfX should exhibit satisfactory performance in other aspects too, including plausibility and robustness. Node classification : Let Φ : G × V → Y be a trained GNN classifier (oracle) that, given a graph 𝐺 = (V, E) and a node 𝑣 ∈ V, assigns a label in Y = 1, . . . , 𝐶 to 𝑣. Given a prediction Φ(𝐺, 𝑣) = 𝑦, a factual GNN explainer ΨΦ,𝐹 (·) seeks to identify a subgraph 𝐺 𝐹 ⊆ 𝐺 relevant to node 𝑣 that preserves the prediction, i.e., Φ(𝐺 𝐹 , 𝑣) = Φ(𝐺, 𝑣). Similarly, a counterfactual explainer ΨΦ,𝐶𝐹 (·) aims to identify a subgraph 𝐺 𝐶𝐹 ⊆ 𝐺 relevant to a node 𝑣 ∈ V that differs minimally from 𝐺 while remaining plausible, and changes the prediction for 𝑣, i.e., Φ(𝐺 𝐶𝐹 , 𝑣) ≠ Φ(𝐺, 𝑣).
4 Evaluation 4.1 Counterfactual Explainers For graph classification experiments, our study considers four state-of-the-art counterfactual explainers: CF2 [30], which generates explanations by only removing edges; D4Explainer [4], which leverages diffusion models; RSGG-CE [25], which is based on generative adversarial networks (GANs); and GIST [28], which relies on style transfer. In addition, we include GCFExplainer [13] as a reference. Unlike the other systems, GCFExplainer is a
SETN 2026, September 09–11, 2026, Chania, Greece
global-level explainer whose objective is to identify high-level rules that generalize across a large proportion of the input graphs. We also implement a naive exhaustive-search Random baseline that randomly adds and removes edges. For each graph, we explore all combinations of up to two edge deletions and up to two edge additions until a counterfactual example is found. Although this approach is computationally expensive and does not scale to larger graphs, it provides a useful reference point against which the performance of approximate methods can be compared, despite often producing implausible counterfactual explanations (CfXs). For node classification experiments, we compare D4Explainer and CF2 . We also use CF-GNNExplainer [19] as a baseline, which is designed specifically for node classification and generates counterfactual explanations by removing edges only. A Random baseline is not considered, as the search space is restricted to the local neighborhood of the target node. Under this setting, random edge perturbations are substantially more likely to affect the prediction, especially when the target node belongs to the ground-truth motif, making such a baseline less informative than in the graph classification setting. Since not all systems support both prediction tasks, the explainers are selected separately for graph and node classification according to their intended scope and available implementations. Notably, CF2 and D4Explainer are evaluated in both settings, enabling a direct comparison of their behavior across the two prediction tasks. Training configurations and dataset-specific hyperparameter selection used for all methods are given in the Appendix.
4.2
Datasets
For graph classification, we used 4 synthetic and 3 real-world datasets. The BA-2Motifs [20] dataset contains 1000 graphs. Each graph is formed by attaching a five-node cycle or a house motif to a Barabási–Albert (BA) graph. The motif determines the graph label (0 for the cycle and 1 for the house motif). We extend this to BA3Motifs and BA-4Motifs: the former introduces a five-node clique (label 2), while the latter additionally includes a four-node clique (label 2) and a five-node clique (label 3), alongside the original two classes. BA-2Motifs-3classes is introduced to evaluate the ability of models to handle incomplete motifs, by removing a single edge from the motif in one-third of the BA-2Motifs graphs and assigning them a third label (2). All node features are 10-dimensional vectors with constant value 0.1. Graph-SST5 and Graph-Twitter [35] are sentiment analysis datasets with 5 and 3 classes, respectively, reflecting the sentiment of the sentence. Each sentence is represented as a graph with word nodes and relational edges. BBBP [23] is a molecular graph classification dataset for the prediction of blood-brain barrier permeability. Molecules are represented as graphs with atoms as nodes and bonds as edges, 9-dimensional node features, and binary labels indicating whether a molecule can cross the barrier. Table 1 summarizes the statistics of the datasets used in graph classification experiments. For node classification, we used 2 synthetic and 2 real-world datasets. BA-Shapes consists of a Barabási–Albert (BA) graph with 80 attached house motifs, where nodes are labeled according to their position in the motif, or 0 otherwise. Tree-Cycles consists of a tree graph (nodes with label 0) with cycle motifs (nodes with
Villia et al.
Table 1: Dataset statistics. Avg. # Avg. # # of train # of val. # of test # of # of classes features of nodes of edges graphs graphs graphs
Dataset BA-2Motifs BA-2Motifs-3Classes BA-3Motifs BA-4Motifs BBBP Twitter Graph-SST5
2 3 3 4 2 3 5
10 10 10 10 9 768 768
25 25 25 25 24.06 21.103 19.849
25,49 25,23 27,06 27,09 25,35 20,35 18,66
800 800 800 800 1631 4,998 8,544
100 100 100 100 203 1,250 1,101
100 100 100 100 205 692 2,210
Table 2: Statistics of the node classification datasets.
Dataset BA-Shapes Tree-Cycles Cora PubMed
# of # of # of # of # of train # of val. # of test classes features nodes edges nodes nodes nodes 4 2 7 3
10 10 1433 500
700 871 2708 19717
2055 971 5278 44324
560 696 1647 13243
70 87 479 3000
70 88 479 3000
label 1). Cora and PubMed [32] are citation networks, where nodes represent publications, edges denote citations, and node labels correspond to research topics, with 7 and 3 node classes, respectively. Table 2 summarizes the statistics of the node classification datasets.
4.3
Evaluation Metrics
In the following, we present the evaluation metrics used to compare the state-of-the-art models. All experiments were run on a single workstation with an Intel Core i9-14900KS CPU (24 physical cores, 32 threads), 62 GB system RAM, and one NVIDIA GeForce RTX 4090 GPU. Validity. Validity measures the proportion of instances for which the explainer generates at least one counterfactual, noting that some explainers may produce multiple counterfactuals per instance. For graph classification, it corresponds to the fraction of the original input graphs for which a counterfactual graph is found. For node classification, it measures the fraction of nodes in the single input graph for which the explainer, by adding or removing edges to the local neighborhood of the node, changes its original predicted label. Explanation Size. Explanation Size is the total number of edge edits that generate a counterfactual instance. Fidelity. Fidelity captures the decrease in the probability of the model for the original prediction after counterfactual modifications are applied. For graph classification, this corresponds to the confidence change for the input graph, while for node classification, it is computed for the target node based on modifications in its local neighborhood. Motif Proximity. Motif Proximity measures the proportion of edge modifications in the counterfactual explanation that touch the ground-truth motif. This metric is applicable to synthetic datasets where ground-truth explanation motifs are known, and for node classification tasks only when the target node belongs to a motif. Minimality. Minimality measures the necessity of a counterfactual explanation. Specifically, the metric considers all subsets of
A Review of Counterfactual GNN Explainers
SETN 2026, September 09–11, 2026, Chania, Greece
Table 3: Validity (top left, ↑) / Fidelity (top right, ↑), Explanation Size (bottom left, ↓) / Explanation Size of the 1𝑠𝑡 cf (bottom right, ↓) for graph classification. Random
GCFEx
CF2
BA-2Motifs
1/ 0.82 1/ -
1/ 0.83 4.3/ 30.09
0.79/ 0.94 5.06/ -
0.88/ 0.73 36.72/ 50.74
0.96/ 0.78 8.53/ -
0.57/ 0.55 29.64/ -
BA-3Motifs3Classes
1/ 0.64 1/ -
1/ 0.56 1.44/ 32.48
0.49/ 0.79 1.8/ -
1/ 0.77 1/ 2.12
1/ 0.80 8.37/ -
0.73/ 0.55 29.86/ -
BA-3Motifs
1/ 0.69 1.27/ -
1/ 0.72 1/ 30.12
0.68/ 0.85 12.91/ -
1/ 0.87 8.39/ 19.47
0.76/ 0.78 8.44/ -
0.7/ 0.59 31.41/ -
BA-4Motifs
1/ 0.78 1.24/ -
1/ 0.75 1/ 29.66
0.61/ 0.95 6.82/ -
1/ 0.89 5.77/ 22.91
1/ 0.80 4.29/ -
0.79/ 0.75 31.09/ -
BBBP
0.65/ 0.39 1.57/ -
1/ 0.32 16.82/ 35.01
0.22/ 0.44 2.05/ -
0.90/ 0.85 10.49/ 18.97
0.34/ 0.12 4.67/ -
0.38/ 0.29 27.95/ -
0.44/ 0.19 1.42/ -
1/ 0.21 18.32/ 26.9
0.01/ 0.11 1.6/ -
0.82/ 0.69 8.15/ 12.86
0.38/ 0.12 7.87/ -
0.79/ 0.46 32.38/ -
Graph-sst5
0.54/ 0.16 1.36/ -
1/ 0.14 17.23/ 22.73
0.06/ 0.11 2.18/ -
0.86/ 0.56 9.01/ 12.72
0.45/ 0.08 8.74/ -
0.8/ 0.42 25.67/ -
D4Ex
RSGG-CE
GIST
the applied edits (edge additions and removals) and computes the proportion of subsets for which the prediction remains unchanged when applied to the original graph. In the tables, we report the average values of Explanation Size, Fidelity, Minimality, and Motif proximity across all instances for which a counterfactual was generated. In cases where multiple counterfactuals are produced per instance, the best is selected and considered in the average of Explanation Size, Fidelity, and Motif Proximity. For Minimality, we first average the scores over all counterfactuals per instance, and then average across all instances.
4.4
Results
Graph Classification. Table 3 shows the validity and average fidelity scores of all explainers on both synthetic and real datasets for graph classification tasks, along with the average explanation size for the optimal counterfactual (according to each method) and for the first counterfactual found. For explainers that generate only a single counterfactual, a ‘-’ is reported. Regarding validity, both the global GCFExplainer, which leverages cross-dataset rules, and the Random baseline, based on exhaustive search, achieve near-perfect scores. However, on real-world datasets, the validity of the Random baseline decreases due to the increased complexity of the graphs and the resulting timeouts, while GCFExplainer maintains perfect validity at the expense of substantially larger explanations, suggesting that more extensive graph modifications are required to achieve prediction flips in these datasets. GIST has moderate validity and fidelity, but its explanations are too large to be practical for human interpretation. D4Explainer produces counterfactuals of moderate size and achieves strong validity and fidelity scores, likely because it explores the search space extensively. However, this leads to very long execution times (see Table 6 later on). RSGG-CE also produces counterfactuals of moderate sizes while maintaining strong validity and fidelity scores in synthetic datasets. However, on more complex, real-world data, both validity and fidelity decrease. CF2 , on the other hand, consistently generates small explanations, but this often comes at the cost of lower validity and fidelity, particularly in real datasets. This suggests that while it favors minimal changes, these are not always sufficient to flip the prediction. Overall, the results highlight a trade-off between validity, fidelity, and explanation size. This trade-off also relates to the quality of
Table 4: Motif proximity evaluation (average score; higher is better, ↑) for graph classification.
BA-2Motifs BA-2Motifs-3Classes BA-3Motifs BA-4Motifs
Random
GCFExplainer
CF2
D4Explainer
RSGG-CE
GIST
0.6 0.24 0.6 0.65
0.45 0.4 0.53 0.57
0.59 0.59 0.6 0.97
0.44 0.39 0.41 0.42
0.32 0.26 0.27 0.27
0.27 0.27 0.31 0.3
Table 5: Average minimality score per graph (higher is better, ↑) for graph classification.
BA-2Motifs BA-2Motifs-3Classes BA-3Motifs BA-4Motifs BBBP Twitter Graph-sst5
Random
GCFExplainer
CF2
D4Explainer
RSGG-CE
GIST
1 1 1 1 1 1 1
0.55 0.5 0.5 0.5 0.67 0.71 0.72
0.38 0.42 0.44 0.29 0.89 0.99 0.96
0.4 0.5 0.4 0.39 0.73 0.97 0.94
0.73 0.44 0.63 0.74 0.99 0.91 0.91
0.46 0.28 0.36 0.24 0.7 0.88 0.79
the suggested changes: CfXs should focus on meaningful modifications within an entity’s local neighborhood, rather than arbitrary or distant edits that may lead to out-of-distribution effects. In other words, instead of systems that produce an answer in every case, it is preferable to develop models that generate explanations in as many cases as possible, while keeping explanation size small, maintaining high confidence (i.e., fidelity), and avoiding unnecessary (e.g., reflected by minimality) or unrealistic changes (e.g., reflected by motif proximity). We evaluated the generated CfXs using the Motif Proximity metric (higher is better) across all explainers and datasets (Table 4). There is a clear limitation in many explainers to suggest edits around the important neighborhood (motif). The random baseline achieves low scores, highlighting that despite its high validity and small explanation size, these metrics alone are insufficient to assess the quality of CfXs. CF2 outperforms the other methods on the majority of datasets, while RSGG-CE and GIST exhibit the lowest performance across datasets. Notably, while synthetic datasets, for which a single motif is embedded within an otherwise random graph, should constitute a relatively simple setting, as altering the prediction requires modifying the motif itself, it is revealed that most systems fail to consistently identify and operate within this critical region. Table 5 reports the average minimality (higher is better) of the explanations in all datasets. A minimal CfX consists of the smallest set of edge additions and removals required to induce a prediction flip, that is, it does not contain redundant changes. The Random baseline achieves the highest scores. This behavior stems from our implementation, where edges are incrementally modified (added or/and deleted) until a counterfactual is found. RSGG-CE demonstrates the best performance in all state-of-the-art explainers in several datasets. CF2 and D4Explainer achieve high minimality scores on real-world datasets such as Twitter and Graph-SST5, suggesting that their strategies are better aligned with real more complex datasets. In contrast, GCFExplainer and GIST tend to produce less minimal counterfactual explanations, likely due to the trade-off between minimality and other desirable properties of explainers, such as validity.
SETN 2026, September 09–11, 2026, Chania, Greece
Villia et al.
Table 6: Training time(s) / Avg Inference time per graph(s) for graph classification. Dataset
Random
GCFExplainer
CF2
D4Explainer
RSGG-CE
GIST
BA-2Motifs BA-2Motifs-3Class BA-3Motifs BA-4Motifs BBBP Twitter Graph-SST5
-/0.197 -/0.164 -/14.15 -/12.73 -/43.36 -/59.42 -/46.48
588.52/2.943 293.99/1.47 572.86/2.864 563.83/2.819 4529.8/11.381 2379.08/1.714 3853.75/1.625
101.829/0.509 114.55/0.573 105.568/0.528 104.216/0.521 617.822/1.552 641.166/0.462 3393.769/1.431
2341.463/7.899 2151.111/7.312 2133.333/7.887 2151.111/8.062 19360/6.862 47088.393/8.641 110568.979/7.146
0.612/0.033 1.011/0.009 1.032/0.123 1.433/0.005 1.286/0.591 8.765/0.556 14.453/0.133
89.099/0.029 88.747/0.018 85.367/0.019 89.033/0.019 208.886/0.108 10059.242/0.163 24098.251/0.245
Table 7: Validity (↑) / Fidelity (↑) (top) and GED (↓) / Min. CF Size (↓) (bottom) for node classification. CF-GNNExplainer
CF2
D4Explainer
BA-Shapes
1.00/ 0.493 1.10/ 1.03
0.686/ 0.792 22.85/ 20.22
0.530/ 1.000 34.9/ 34.9
Tree-Cycles
0.387/ 0.984 1.00/ 1.00
0.352/ 0.954 4.65/ 1.00
1.000/ 0.198 1.33/ 1.33
Cora
1.00/ 0.137 2.73/ 2.08
0.042/ 0.015 1.20/ 1.00
-/ -/ -
PubMed
1.00/ 0.471 2.26/ 2.12
0.881/ 6.61/ 6.00
-/ -/-
Table 8: Motif Proximity for node classification (higher is better, ↑).
Node Classification. Table 7 reports the validity, average fidelity, and average explanation size of all evaluated explainers across the considered node classification datasets, as well as the explanation size of the first counterfactual found for explainers that generate multiple counterfactuals. CF-GNNExplainer achieves exceptionally high validity on most datasets while consistently generating compact counterfactual explanations. This performance is primarily attributed to its simple edge-removal strategy, which directly disrupts the structural pattern responsible for the original prediction. Similarly to the graph classification setting, CF2 continues to favor compact counterfactual explanations in three out of the four datasets, with BA-Shapes being the only exception. However, this often comes at the expense of validity, particularly on Tree-Cycles and Cora. In BA-Shapes, CF2 and, especially, D4Explainer generate large explanations. This behavior is likely due to the increased complexity of BA-Shapes, which contains five node classes, resulting in a larger number of possible edge additions and removals around the ground-truth motif that can alter a node’s prediction. Table 8 reports the Motif Proximity scores for the node classification task. Overall, the explainers achieve only moderate scores, suggesting that they do not consistently focus their modifications around the ground-truth motif. CF2 is the only method that achieves
CF2
D4Explainer
0.635 0.589
0.521 0.984
0.637 0.723
BA-Shapes Tree-Cycles
Table 9: Minimality ratio for node classification (higher is better, ↑). CF-GNNExplainer
CF2
D4Explainer
0.513 0.500 0.066 0.223
0.011 0.004 0.098 0.039
0.000 0.904 – –
BA-Shapes Tree-Cycles Cora PubMed
Table 10: Training times / Avg. inference time per node(s) for node classification. Dataset
Finally, Table 6 reports the training and inference time of each explainer. RSGG-CE has the lowest training times across all datasets among all explainers. GIST and RSGG-CE compete for the lowest inference times; however, GIST suffers from an increased training cost, particularly on the two larger datasets. D4Explainer has the highest training times in all datasets and explainers. This makes it impractical even for relatively simple graphs, a limitation also acknowledged by its authors. GCFExplainer and CF2 have moderate training and inference times, although they remain considerably slower than RSGG-CE. Overall, these results underline the importance of considering runtime alongside performance.
CF-GNNExplainer
BA-Shapes Tree-Cycles Cora PubMed
CF-GNNExplainer
CF2
D4Explainer
93.87 / 2.35 76.66 / 2.47 434.63 / 1.04 2868.73 / 1.05
506.28 / 7.70 435.30 / 5.26 5855.64 / 14.25 2189.60 / 0.73
1932.58 / 13.48 4440.70 / 8.07 –/– –/–
a near-perfect score on Tree-Cycles, while also staying relatively close to the highest scores on BA-Shapes. This behavior is consistent with the graph classification results, where CF2 also achieved the highest or second-highest Motif Proximity across the synthetic datasets. Notably, Tree-Cycles is the simpler of the two datasets, containing only two node classes, which may explain why identifying and modifying the relevant motif is substantially easier. Table 9 reports the minimality scores of the counterfactual explanations generated for node classification. No single method consistently achieves the best performance across all datasets. CFGNNExplainer obtains the highest minimality on BA-Shapes and PubMed, outperforming the other methods considerably on both datasets. D4Explainer performs exceptionally well on Tree-Cycles, where the explanation size remains very small (Table 7). In contrast, its performance drops to zero on BA-Shapes, where the generated explanations are considerably larger. This suggests that the larger explanations reported in Table 7 contain more redundant modifications, resulting in low minimality. Finally, CF2 generally exhibits very low minimality scores across all node classification datasets in comparison to the graph classification setting. Table 10 reports training and inference times for the node classification tasks, drawing a similar picture with the corresponding performance for graph classification tasks.
5
Open Challenges
In this paper, we conducted a comprehensive analysis of a new generation of counterfactual, post-hoc GNN explainers, capable of both adding and removing edges, in the attempt to generate
A Review of Counterfactual GNN Explainers
valuable explanations. In doing so, we identify a number of open research challenges that can drive future research. For start, it is evident that going beyond just edge removal is a crucial ability, especially for the graph classification tasks. Yet, the multi-faceted nature of the problem renders a universally bestperforming approach difficult to achieve. To highlight this aspect, the comparative analysis elucidates the importance of exploring a variety of qualitative criteria. RSGG-CE, for instance, stands out for its capacity to generate compact CfXs with high validity, especially considering its time efficiency, but presents moderate performance in all qualitative metrics. D4Explainer, on the other hand, seems to owe its impressive performance on real data to the computationally very intensive diffusion process, which furthermore seems to hurt performance in smaller, simpler graphs. The GCFExplainer, with its design to offer a global view, achieves its goal for high coverage, but at the same time its poor qualitative scores make clear why a deeper view is crucial for CfXs. We expect in the near future to witness a growing interest in this field, probably bringing insights from diverse areas, in order to achieve a holistically acceptable performance. It is important to underline the lack of standardized benchmarks and the effort being made in the field to systematically organize the evaluation process. Most works we considered only include some of the most popular explainers as baselines in their comparative analyses, which are not necessarily the most powerful ones. They also apply evaluation metrics that vary significantly in scope. The quality and robustness of explanations are important aspects that, as our assessment showed, should not be overshadowed by good scores in validity and fidelity metrics. From a similar standpoint, the authors in [26] even suggest the organization of public competitions for counterfactual explainers, as is happening for example in the field of data mining, in order to encourage uniform and well-formatted benchmarks. We also notice a characteristic emphasis on exploring graph classification tasks, overlooking the complexities in addressing other tasks that currently GNNs exhibit notable performance. Counterfactual explanation of node classification or link prediction tasks is often not included in the evaluation of many systems, while for certain systems is not even supported by the underlying methodologies. For those frameworks that are applicable to both graph and node classification problems, the findings exhibit relatively consistent behaviours, although we notice a drop in performance in the ability to explain node classifications. The good performance of the CF-GNNExplainer in the less qualitative metrics (Table 7), despite its lack of edge addition exploration, is an indication that proper adaptations to the type of task can offer leverage to the explainers; yet, an in depth look to more detailed metrics is crucial in this case, too. In this survey we did not consider more complex structures, such as heterogeneous or dynamic graphs. This is an emerging research field in graph representation learning, with new and highly impactful GNN prediction models being suggested. We expect that future GNN explainers will need to be broad enough to accommodate a much wider variety of graph data.
SETN 2026, September 09–11, 2026, Chania, Greece
6
Conclusions
In this paper, we present a comparative study of counterfactual GNN explainers that go beyond edge removal by also allowing edge addition. Our results show that, although recent methods leverage more advanced approaches, such as generative models, and have improved performance across multiple metrics, no single explainer consistently performs best across validity, efficiency, explanation size, minimality, and motif proximity. These findings highlight the need for more general, efficient and qualitatively reliable counterfactual explainers, as well as more standardized benchmarks for evaluating them.
Acknowledgments This study is funded by the research project CARAML implemented in the framework of H.F.R.I. call “3𝑟𝑑 Call for H.F.R.I.’s Research Projects to Support Faculty Members Researchers” (H.F.R.I. Project Number: 25735).
References [1] Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. 2023. Evaluating explainability for graph neural networks. Scientific Data 10, 1 (2023). [2] Davide Bacciu and Danilo Numeroso. 2023. Explaining Deep Graph Networks via Input Perturbation. IEEE Transactions on NN and Learning Systems 34, 12 (2023), 10334–10345. [3] Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. 2021. Robust counterfactual explanations on graph neural networks. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NIPS ’21). Curran Associates Inc., Article 431, 12 pages. [4] Jialin Chen, Shirley Wu, Abhijit Gupta, and Rex Ying. 2023. D4Explainer: indistribution GNN explanations via discrete denoising diffusion. In 37th International Conference on Neural Information Processing Systems (NIPS ’23). [5] Ziheng Chen, Jin Huang, Fabrizio Silvestri, Yongfeng Zhang, Hongshik Ahn, and Gabriele Tolomei. 2025. Joint Factual and Counterfactual Explanations for Topk GNN-based Recommendations. ACM Transactions on Recommender Systems (2025). [6] Zhaoyang Chu, Yao Wan, et al. 2024. Graph neural networks for vulnerability detection: A counterfactual explanation. In ISSTA. [7] Enyan Dai and Suhang Wang. 2021. Towards Self-Explainable Graph Neural Network. In 30th ACM International Conference on Information & Knowledge Management. 302–311. [8] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. 2024. A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability. Machine Intelligence Research 21, 6 (2024), 1011–1061. [9] Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. 2023. Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks . IEEE Transactions on Knowledge & Data Engineering 35, 08 (2023), 8687–8698. [10] Zhimeng Guo, Zongyu Wu, Teng Xiao, Charu Aggarwal, Hui Liu, and Suhang Wang. 2025. Counterfactual Learning on Graphs: A Survey. Machince Intelligence Research 22 (2025), 17–59. [11] Yinhan He, Wendy Zheng, Yaochen Zhu, Jing Ma, Saumitra Mishra, Natraj Raman, Ninghao Liu, and Jundong Li. 2025. Global Graph Counterfactual Explanation: A Subgraph Mapping Approach. Transactions on Machine Learning Research (2025). [12] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. 2023. GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks. IEEE Transactions on Knowledge and Data Engineering 35, 7 (2023), 6968–6972. [13] Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2023. Global Counterfactual Explainer for Graph Neural Networks. In 16th ACM International Conference on Web Search and Data Mining (WSDM ’23). 141–149. [14] Zhenhua Huang, Kunhao Li, Shaojie Wang, Zhaohong Jia, Wentao Zhu, and Sharad Mehrotra. 2024. SES: Bridging the Gap Between Explainability and Prediction of Graph Neural Networks. In IEEE 40th International Conference on Data Engineering (ICDE). [15] Junqi Jiang, Francesco Leofante, Antonio Rago, and Francesca Toni. 2024. Robust counterfactual explanations in machine learning: a survey. In 33rd International Joint Conference on Artificial Intelligence (IJCAI ’24). 8086–8094. [16] Jean Kaddour, Aengus Lynch, et al. 2025. Causal Machine Learning: A Survey and Open Problems. Foundations and Trends in Optimization 9, 1-2 (2025), 1–247. [17] Yifei Liu, Chao Chen, Yazheng Liu, Xi Zhang, and Sihong Xie. 2021. Multiobjective Explanations of GNN Predictions . In 2021 IEEE International Conference
SETN 2026, September 09–11, 2026, Chania, Greece
on Data Mining (ICDM). 409–418. [18] Antonio Longa, Steve Azzolin, et al. 2025. Explaining the Explainers in Graph Neural Networks: a Comparative Study. Comput. Surveys 57, 5, Article 120 (2025). [19] Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. 2022. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In International conference on artificial intelligence and statistics. PMLR, 4499–4511. [20] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. 2020. Parameterized explainer for graph neural network. In 34th International Conference on Neural Information Processing Systems. Article 1646. [21] Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. 2022. CLEAR: generative counterfactual explanations on graphs. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NIPS ’22). [22] Jiali Ma, Ichigaku Takigawa, and Akihiro Yamamoto. 2025. C2Explainer: Customizable Mask-based Counterfactual Explanation for Graph Neural Networks. In ACM Conference on Fairness, Accountability, and Transparency (FAccT ’25). 137–149. [23] I. F. Martins, A. L. Teixeira, L. Pinheiro, and A. O. Falcao. 2012. A Bayesian approach to in silico blood-brain barrier penetration modeling. Journal of Chemical Information and Modeling 52, 6 (2012), 1686–1697. [24] Danilo Numeroso and Davide Bacciu. 2021. MEG: Generating Molecular Counterfactual Explanations for Deep Graph Networks. In 2021 International Joint Conference on Neural Networks (IJCNN). 1–8. [25] Mario Alfonso Prado-Romero, Bardh Prenkaj, and Giovanni Stilo. 2024. Robust stochastic graph generator for counterfactual explanations. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence (AAAI’24/IAAI’24/EAAI’24). AAAI Press, Article 2401, 9 pages. doi:10.1609/aaai.v38i19.30149 [26] Mario Alfonso Prado-Romero, Bardh Prenkaj, Giovanni Stilo, and Fosca Giannotti. 2024. A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation, and Research Challenges. ACM Comput. Surv. 56, 7 (2024). [27] Bardh Prenkaj, Mario Villaizán-Vallelado, Tobias Leemann, and Gjergji Kasneci. 2024. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’24). 2420–2431. [28] Bardh Prenkaj, Efstratios Zaradoukas, and Gjergji Kasneci. 2025. Graph Inverse Style Transfer for Counterfactual Explainability. In 42nd International Conference on Machine Learning (ICML ’25). [29] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. 2021. Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking. In ICLR. [30] Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. 2022. Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning. In Proceedings of the ACM Web Conference 2022 (WWW ’22). 1018–1027. [31] Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, and Panos Trahanias. 2026. A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD ’26). [32] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semisupervised learning with graph embeddings. In International conference on machine learning. PMLR, 40–48. [33] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019. Gnnexplainer: Generating explanations for GNNs. Advances in neural information processing systems 32 (2019). [34] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. 2020. XGNN: Towards ModelLevel Explanations of Graph Neural Networks. In KDD. [35] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2023. Explainability in GNNs: A Taxonomic Survey . IEEE Trans. on Pattern Analysis & Machine Intelligence 45, 5 (2023), 5782–5799. [36] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. 2021. On explainability of graph neural networks via subgraph explorations. In ICML. [37] Yu Zhang, Sean Bin Yang, Arijit Khan, and Cuneyt Gurcan Akcora. 2026. ATEXCF: Attack-Informed Counterfactual Explanations for Graph Neural Networks. In 14th International Conference on Learning Representations (ICLR ’26).
A
Hyperparameter Selection
The Appendix reports the training configurations and datasetspecific hyperparameters used for all methods included in our evaluation. Unless otherwise reported, we follow the original implementations and recommended settings of each method. It should be noted that while some explainers reported results on the same
Villia et al.
datasets used in our review, we re-trained all frameworks, due to differences in our train/validation/test splits compared to the original evaluations.
A.1
Graph Classification Hyperparameters
For CF2 , we use 𝛼 = 0.7, 𝛾 = 0.9, a binarization threshold of 0.5, and train for 500 epochs across all datasets. On BA-2motifs we set 𝜆 = 20 and 𝜂 = 0.02; on BA-3motifs and BA-4motifs we increase the sparsity penalty to 𝜆 = 100 (with 𝜂 = 0.02) to account for the larger number of motif classes. For the real-world datasets (BBBP, SST5, Twitter) we use 𝜆 = 20 and a higher learning rate 𝜂 = 0.05. For D4Explainer, we train the diffusion model for 800 epochs with learning rate 𝜂 = 10−3 , decay 𝛾 = 0.999, dropout = 0.001, 6 diffusion layers, hidden size 64, and instance normalization. The noise schedule uses 𝜎len = 10 steps with 𝑝 low = 0.0 and 𝑝 high = 0.4, and the CF loss weight is 𝛼 cf = 0.5 with sparsity level 2.5. For GIST we train for 50 epochs with a batch size of 16, hidden dimension 16, and 2 attention heads. The regularization coefficient is set to 𝛼 = 0.9. Optimization is performed with Adam using a learning rate of 10−3 and weight decay 10−5 . RSGG-CE is trained for 30 epochs. Edge candidates are drawn using a positive-and-negative edge sampler with 500 sampling iterations per step, and one GAN is trained per target class. The generator and discriminator are optimized with SGD (𝜂 = 10−3 , batch size 4) under binary cross-entropy loss. The embedding dimension is set to 4 for BA-2Motifs, BA-2Motifs-3Classes, BA-3Motifs, BA-4Motifs, and BBBP, and to 28 for Graph-SST5 and Twitter. For GCFExplainer the coverage trade-off is 𝛼 = 0.5. For BA2Motifs, BA-3Motifs and BA-4Motifs, the decision threshold is 𝜃 = 0.05, teleport probability 0.20, and neighborhood sampling size 40; per-class maximum steps are [4300, 5700], [3600, 3000, 3400], and [2100, 2700, 2800, 2400] respectively. BA-2Motifs-3Classes uses the same settings with steps [5000, 3300, 5000]. For BBBP, 𝜃 = 0.05, teleport 0.15, sample size 30, and steps [14700, 46800]. For GraphSST5 and Twitter, 𝜃 = 0.15, teleport 0.60, sample size 20, and 50000 steps per class.
A.2
Node Classification Hyperparameters
For CF-GNNExplainer, we use learning rate 10−2 , 𝛽 = 0.5 (sizeloss weight), and 500 optimisation epochs per node. For CF2 , the per-node counterfactual search runs for 2,000 epochs with 𝛼 = 0.6, 𝛾 = 0.5 and 𝜆 = 500. The learning rate is 10−2 for BA-Shapes, Cora and PubMed, and 5 × 10−2 for Tree-Cycles. For D4Explainer, the diffusion model is trained for 800 epochs with batch size 32, learning rate 10−3 (decay 0.999), dropout 0.001, and a noise schedule with 𝜎len = 10, 𝑝 low = 0.0, 𝑝 high = 0.4. For Tree-Cycles the𝛼 cf = 0.5 and the sparsity penalty is 𝜆𝑠 = 2.5 for Tree-Cycles; for BA-Shapes 𝛼 cf = 0.7 and 𝜆𝑠 = 5.0.