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)
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH), Heraklion, Greece · Computer Science Department, University of Crete, Greece