Beyond Edge Deletion: A Comprehensive Approach to Counterfactual Explanation in Graph Neural Networks
Authors: Matteo De Sanctis, Riccardo De Sanctis, Stefano Faralli, Paola Velardi, Bardh Prenkaj
Organizations: Sapienza University of Rome, Rome, Italy · ISTC-CNR & Sapienza University of Rome, Rome, Italy · Technical University of Munich, Munich, Germany
Graph Neural Networks (GNNs) are increasingly adopted across domains such as molecular biology and social network analysis, yet their black-box nature hinders interpretability and trust. This is especially problematic in high-stakes applications, such as predicting molecule toxicity, drug discovery, or guiding financial fraud detections, where transparent explanations are essential. Counterfactual explanations - minimal changes that flip a model's prediction - offer a transparent lens into GNNs' behavior. In this work, we introduce XPlore, a novel technique that significantly broadens the counterfactual search space. It consists of gradient-guided perturbations to adjacency and node feature matrices. Unlike most prior methods, which focus solely on edge deletions, our approach belongs to the growing class of techniques that optimize edge insertions and node-feature perturbations, here jointly performed under a unified gradient-based framework, enabling a richer and more nuanced exploration of counterfactuals. To quantify both structural and semantic fidelity, we introduce a cosine similarity metric for learned graph embeddings that addresses a key limitation of traditional distance-based metrics, and demonstrate that XPlore produces more coherent and minimal counterfactuals. Empirical results on 13 real-world and 5 synthetic benchmarks show up to +56.3% improvement in validity and +52.8% in fidelity over state-of-the-art baselines, while retaining competitive runtime.
Figures & tables
Figure 1. (left) original graph G predicted mutagenic. (right) Counterfactual G′ predicted non-mutagenic with highlighted edge additions and removals, as well as potentially node additions to flip the prediction. Note that, although in this example, we illustrate valid chemical properties (see that the valence of atoms is respected), in practice, this might not happen as our method is domain-independent.
Symbol
Description
E,Φ
Counterfactual and oracle model
G,G′
Original and counterfactual graphs
A,A^
Adjacency matrices (original and counterfactual)
P,Pˉ
Original and new perturbation matrices for edges
N,Nˉ
Binary and continuous node feature perturb. matrices
X,W
Node feature and weight matrices
Table 1. Notation used in the Section 3 .
Figure 2. Illustration of counterfactual explanations in graph classification. a and d : The class changes only after an edge deletion (red, dashed). b and e : the predicted class changes only after an edge addition (green). c and f : Feature perturbation of the carbon-group illustrates benzene converting from neutral to cationic by electron loss. XPlore enables these types of perturbations, alone or in combination, offering a broader search space than edge deletion-only methods.
Step
Action
1
Initialize Pˉ←A+N(0,0.12) and optionally add Γ .
2
Initialize Nˉ←1n×f
3
Compute A^=max(T0.5(Pˉ),I)
4
Compute contribution of A^ and Nˉ to Lpred through the oracle’s prediction ( Equations 6 and 7 ).
5
Update Pˉ and Nˉ via gradient descent.
Table 2. XPlore steps to perturb edges and node features.
TCR
BAS
BZR
AIDS
ENZYMES
Fingerprint
COLORS-3
TG
MUTAG
COX2
BBBP
PROTEINS
COLLAB
TRIANGLES
DBLP
IMDB
TWITTER
MSRC
iRand
27.92
50.70
27.16
0.00
26.67
0.09
42.99
36.16
2.66
69.81
19.76
18.87
4.60
6.38
1.17
3.70
0.00
95.74
CF 2
50.04
45.78
19.75
0.10
68.33
24.52
52.07
49.86
0.00
24.20
25.26
16.35
52.66
37.13
5.76
50.60
38.82
90.94
CLEAR
50.68
50.96
60.49
16.75
83.17
72.73
0.00
58.40
35.11
22.06
22.90
0.00
0.00
89.99
0.68
56.20
7.65
23.98
RSGG-CE †
67.90
91.04
21.23
19.80
98.33
90.46
94.57
89.28
56.91
99.36
22.90
58.67
0.00
99.84
57.51
86.10
48.36
100.0
D4Explainer
44.82
35.16
20.00
0.10
68.00
24.52
0.00
49.86
9.57
22.06
21.24
0.00
0.00
31.11
7.02
49.60
23.45
90.94
CF-GNNExpl
50.04
44.18
19.75
0.10
68.33
24.52
52.07
49.86
10.11
22.06
22.31
16.35
52.66
37.13
5.76
50.60
38.82
90.94
Table 3. Comparison of XPlore with SoTA methods (validity ↑ – up; fidelity ↑ – down). Bold is best-performing; underline is second-best. XPlore is best in 17/18 on validity, and 17/18 on fidelity (of which 1/17 on par with RSGG-CE). Tables 7 and 8 show a detailed comparison of other metrics. † indicates the second-best explainer.
Figure 3. Metrics comparison over TCR dataset for different values of hyperparameter γ .
w/o freedom + gating
w/ gating
w/ freedom
CF-GNNExpl
TCR
99.680
65.580
100.00
50.040
TG
99.660
100.00
100.00
49.860
BAS
94.340
100.00
100.00
44.180
MUTAG
45.745
60.106
67.553
10.106
BZR
98.519
100.00
100.00
19.753
COX2
99.358
97.859
98.073
22.056
Table 4. Validity (%) for different variants of XPlore ( γ=0 .01). Bold values are best.
Figure 4. Validity and Fidelity results for node explanation.
Figure 5. t-SNE projection of Wavelet Characteristic embeddings for TCR, comparing CFs generated by CF-GNNExpl, XPlore, and RSGG for the Tree motif. CF-GNNExpl and RSGG find a close CF but fail to land in the Cycle distribution, while XPlore achieves this correctly.
Figure 6. Relationship between GED and CS. XPlore consistently achieves strong CS scores w.r.t. the competitors along with the same GED values in log-scale, indicating that counterfactuals retain meaningful semantic relations to original graphs, partially mitigating OOD.
Table 7. Extended comparison of XPlore with SoTA methods on the used datasets. Standard deviation is reported. Bold is best-performing; underline is second-best. Highlighted columns show the key metrics used to evaluate the explainer’s faithfulness in generating counterfactuals. When an explainer cannot produce valid counterfactuals in a dataset, it does not make sense to evaluate the other metrics (see − ).
Dataset
Method
Validity ↑
Fidelity ↑
Sparsity ↓
Oracle Calls ↓
iRand
3.70% ± 18.88%
0.026 ± 0.192
0.024 ± 0.013
10.865 ± 0.048
CF 2
50.60% ± 50.00%
0.366 ± 0.674
0.803 ± 0.038
0.000 ± 0.001
CLEAR
56.20% ± 49.61%
0.420 ± 0.696
34.773 ± 15.650
0.000 ± 0.022
RSGG-CE
86.10% ± 34.60%
0.664 ± 0.802
0.462 ± 0.122
34.890 ± 1.795
D4Explainer
49.60% ± 50.00%
0.358 ± 0.669
0.797 ± 0.037
0.000 ± 0.015
CF-GNNExpl
50.60% ± 50.00%
0.366 ± 0.674
0.902 ± 0.019
46.000 ± 0.230
Appendix
Table 8. Extended comparison of XPlore with SoTA methods on the used datasets. Standard deviation is reported. Bold is best-performing; underline is second-best. Highlighted columns show the key metrics used to evaluate the explainer’s faithfulness in generating counterfactuals. When an explainer cannot produce valid counterfactuals in a dataset, it does not make sense to evaluate the other metrics (see − ).
Figure 7. XPlore identifies more CFs, thus capturing harder instances. Elongated and bimodal distributions reflect competitive performance and semantic meaning retention.
Figure 8. Runtime (s) at inference across multiple datasets. XPlore (yellow) maintains a competitive runtime, making it the most reliable explainer in practice. Placeholders are used for explainers with 0% accuracy.
Figure 9. Comparison of XPlore and RSGG: t-SNE projection of Wavelet Characteristic embeddings (Tree-Cycle dataset)
Figure 10. Comparison of XPlore, CF-GNNExpl and RSGG: t-SNE projection of Wavelet Characteristic embeddings (Tree-Cycle dataset)
In this study, we propose a novel pipeline for generic, model-agnostic, local-level counterfactual explainability in graph neural networks (GNNs). Although counterfactual explainers capable of both adding and removing edges have emerged in recent years, the need for generic and efficient solutions remains unmet, particularly concerning qualitative explanation generation. Our approach couples progress in factual explainability with missing edge prediction models rooted in link prediction research, in order to enhance the quality, robustness and intuitiveness of explanations. A multi-faceted experimental analysis conducted on real-world and synthetic graph classification benchmarks, both binary and multi-label, demonstrates the advancements in comparison to state-of-the-art baselines across diverse metrics.
Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH), Heraklion, Greece · Computer Science Department, University of Crete, Greece
Graph Neural Networks (GNNs) achieve strong predictive performance on graph-structured data across domains such as chemistry, biology, and network analysis, yet they provide no intrinsic explanation of their predictions. This limits their adoption in high-stakes and safety-critical settings. Counterfactual explanations address this by revealing the minimal structural modifications that would change a model's prediction. On graphs, however, such a modification is hard to produce. The search space is discrete and combinatorial, and a valid answer must respect categorical node and edge types together with domain rules such as chemical valency in the case of molecular graphs. Existing explainers give up one of two things. Either edits are not held on the data manifold, or the search does not span the full edit space. We propose Graph Diffusion Counterfactual Explanation via Inversion (GDCE-I), which gives up neither. A discrete denoising diffusion model with a novel discrete inversion scheme enables distribution-aware edits leveraging the whole domain edit space. We further address the incomplete and inconsistent evaluation of graph counterfactuals by deriving a framework of explanation desiderata and applying it to every method under one shared protocol. Across four benchmarks, GDCE-I outperforms related work by a large margin on the defined framework. For the molecular domain, we further qualitatively show that GDCE-I attains interpretable in-distribution solutions.
David Bechtoldt, Sidney Bender
Machine Learning Group, TU Berlin, 10587 Berlin, Germany · BIFOLD–Berlin Institute for the Foundations of Learning and Data, Berlin, Germany
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.
Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece