RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks
Authors: Yuxiang Yao, Zijun Zhao
Organizations: Project Management Department, Research Center, China Life Insurance Company Ltd. · School of Computer Science and Technology, Beijing Institute of Technology
Counterfactual explanations of graph neural networks identify edge deletions that flip a prediction. On heterogeneous graphs, however, existing methods first collapse the graph into untyped edges, so they cannot answer the question a domain expert actually asks: which relation type drives this prediction? We present RACE (Relation-Aware Counterfactual Explanations), which gives this question an exact, per-instance answer. For every explained instance, an exhaustive search over relation subsets returns the certified minimum relation-deletion set that flips the prediction -- or an explicit report that no such deletion exists; each relation-level answer is then refined into a typed edge set within the attributed relations, verified on the discrete model by single-edge restoration. The relation-level answer is exact and deterministic given the frozen backbone, whereas soft-mask baselines vary by 6-8 pp in success rate across runs differing only in random ordering. On ACM, a Cora-derived graph, and ogbn-mag, RACE improves counterfactual success rate over the strongest baseline by up to +2.7 pp while deleting fewer edges, and attains the highest success rate among all same-task baselines on every dataset; the advantage reproduces across four backbones on ogbn-arXiv and on DBLP, with cross-seed relation-set agreement up to 0.89. A synthetic study with known generating mechanisms confirms that the search recovers the relation the trained model actually relies on -- and reports infeasibility rather than fabricating an attribution when the model has learned none -- so the explanations stay trustworthy exactly where explanations matter.
Figures & tables
Figure 1: Pipeline of Race . Stage 1 builds the relation-aware backbone and freezes it. Stage 2 solves the instance-level exact search, returning the certified minimum relation deletion set Sv∗ or an explicit infeasibility report. Stage 3 refines each feasible answer into a certified, single-edge-restoration-irreducible typed edge set (or an explicit budget-limited status); relation-infeasible instances keep the flat verified explanation as a fallback. Stage 4 evaluates NF/SF, coverage, cost, stability, and runtime.
ACM
Cora
ogbn-mag
Method
CSR ↑
cost ↓
CSR ↑
cost ↓
CSR ↑
cost ↓
flat
RACE-per-edge
0.216 ± 0.072
0.159 ± 0.062
0.452 ± 0.111
0.305 ± 0.031
0.168 ± 0.008
0.378 ± 0.011
PNS-hetero
0.216 ± 0.072
0.159 ± 0.063
0.450 ± 0.110
0.306 ± 0.031
0.168 ± 0.008
0.378 ± 0.010
CF 2 -hetero
0.216 ± 0.072
0.195 ± 0.088
0.458 ± 0.110
0.342 ± 0.024
0.168 ± 0.008
0.434 ± 0.013
RACE-hier
0.224 ± 0.077 †
0.176 ± 0.067 †
0.484 ± 0.122 †
0.332 ± 0.024 †
0.182 ± 0.009 †
0.407 ± 0.011 †
vs. CF 2 -hetero
+0.8 pp
−1.9 pp
+2.7 pp
−1.0 pp
+1.4 pp
−2.7 pp
Table 1: Same-frozen-typed-backbone, instance-targeted comparison (10 seeds, mean ± std across seeds; CSR = success rate, cost = mean local deleted fraction over all targets). Paired sign-flip tests of the hierarchical method against each baseline; † : p=0.002 before Holm correction ( ≤0.062 after). Bold : best value in each column; underlined : second best.
ACM
Cora
ogbn-mag
Method
CSR ↑
cost ↓
CSR ↑
cost ↓
CSR ↑
cost ↓
counterfactual
CF-GNNExplainer
0.216 ± 0.072
0.159 ± 0.063
0.452 ± 0.110
0.305 ± 0.031
0.168 ± 0.008
0.379 ± 0.011
RC
0.148 ± 0.049
0.145 ± 0.059
0.400 ± 0.100
0.245 ± 0.013
0.088 ± 0.007
0.314 ± 0.012
NSEG
0.000 ± 0.001
0.139 ± 0.041
0.001 ± 0.001
0.224 ± 0.021
0.002 ± 0.001
0.192 ± 0.014
CF 2
0.216 ± 0.072
0.195 ± 0.088
0.458 ± 0.110
0.342 ± 0.024
0.168 ± 0.008
0.434 ± 0.013
Table 2: Same-task comprehensive comparison under one frozen checkpoint family (10 seeds, mean ± std). Cost annotations are restricted to the CSR columns, because a method that rarely flips can trivially attain low cost; the paper’s cost claim is the paired comparison against CF 2 -hetero (Table 1 ). RACE-hier additionally certifies every reported flip, provides relation-type attribution, and reports infeasibility per instance. Bold : best value; underlined : second best.
Dataset
hier CSR ↑
flat CSR
p
hier cost ↓
flat cost ↓
ACM
0.224 ± 0.077
0.174 ± 0.046
0.002
0.105
0.033
Cora
0.484 ± 0.122
0.246 ± 0.071
0.002
0.311
0.080
ogbn-mag
0.182 ± 0.009
0.165 ± 0.009
0.002
0.273
0.220
ogbn-arXiv
0.283 ± 0.005
0.230 ± 0.003
0.0625
0.287
0.139
DBLP
0.161 ± 0.035
0.104 ± 0.013
0.0625
0.157
0.030
Table 3: Relation switch (same machinery, scan budget, and target nodes; the only difference is the relation phase). CSR and feasible-success cost, mean ± std over seeds; p : exact paired sign-flip. The relation phase buys a significant CSR gain at a higher per-explanation edge cost; the pipeline-level cost advantage over CF 2 -hetero is the separate claim of Table 1 .
ACM
Cora
ogbn-mag
coverage ↑
0.182 ± 0.048
0.337 ± 0.096
0.167 ± 0.009
relation cost ↓
1.07 ± 0.03
1.14 ± 0.02
1.07 ± 0.01
edge cost ↓
0.574 ± 0.013
0.605 ± 0.044
0.838 ± 0.014
margin
−0.263±0.033
−0.459±0.042
−0.197±0.015
SF ↑
0.918 ± 0.031
0.858 ± 0.028
0.959 ± 0.009
attribution
PAP (10/10)
common-nbr (10/10)
citation (10/10)
Table 4: Instance-level relation search (10 seeds, mean ± std). Coverage = fraction of correctly-classified test instances with any feasible relation deletion.
CSR ↑
cost ↓
Backbone
RACE-hier
CF 2
RACE-hier
CF 2
Race -bb
0.283
0.267
0.287
0.385
HAN
0.255
0.245
0.284
0.379
HGT
0.288
0.275
0.286
0.430
R-GCN
0.490
0.464
0.315
0.510
Table 5: ogbn-arXiv: hierarchical vs. strongest baseline per backbone (5 seeds; all CSR/cost comparisons p=0.062 , the minimum attainable with five seeds). Race -bb is the relation-aware backbone of Sec. 3.2 . Bold : better value in each pairwise comparison.
Table 7: Diagnostic comparison (same checkpoints, 10 seeds, mean ± std). Factual objectives optimize prediction preservation, so near-zero CSR is by construction; the gradient attributions delete a single instance-blind global top- 5% edge budget and are not per-instance interventions; Random is a sanity floor. These rows are not same-task baselines and are excluded from win claims.
Figure 2: Success rate vs. mean local deletion cost across the compared methods (10 seeds; same-task counterfactual methods in filled markers, diagnostics in open markers). RACE-hier (star) is the highest-CSR point on all three datasets, Pareto-dominating the strongest baseline CF 2 (annotated).
Figure 3: Hierarchical vs. the strongest baseline (CF 2 -hetero): (a) counterfactual success rate and (b) mean local edge cost (10 seeds, mean ± 1 std; ∗ : paired sign-flip p=0.002 , Holm-corrected ≤0.062 ). The hierarchy improves both metrics at once on every dataset.
ACM
Cora
ogbn-mag
relation-phase answers (certified, n )
2546
1106
4185
CSR contribution (pp)
18.2 ± 4.8
33.7 ± 9.6
16.7 ± 0.9
mean edge cost (fraction)
0.105
0.311
0.273
fallback CSR (pp)
4.2 ± 2.9
14.7 ± 2.9
1.5 ± 0.3
total CSR
0.224
0.484
0.182
CF 2 mean cost (ref.)
0.195
0.342
0.434
Appendix
Table 8: Where the success rate comes from (10 seeds): relation-phase answers vs. the flat fallback. The relation phase delivers most of the CSR at roughly half the strongest baseline’s cost.
Variant
ACM
Cora
ogbn-mag
CSR ↑
cost ↓
CSR ↑
cost ↓
CSR ↑
cost ↓
full (budget 128)
0.224 ± 0.077
0.107
0.484 ± 0.122
0.313
0.182 ± 0.009
0.273
− fallback
0.182 ± 0.048
0.107
0.337 ± 0.096
0.313
0.167 ± 0.009
0.273
budget 64
0.182
0.176
0.322
0.390
0.167
0.273
budget 32
0.182
0.279
0.322
0.458
0.167
0.287
Appendix
Table 9: Component ablation of the hierarchical pipeline (10 seeds, mean ± std; CSR over all targets, cost = mean feasible edge cost at the given scan budget). full = saliency prior + CF 2 fallback + single-edge scan (budget 128).
Figure 4: Budget curves (10 seeds): mean feasible edge cost vs. the per-node scan budget for the hierarchical (solid) and flat-verified (dashed) pipelines, reconstructed from the per-node scan traces. The hierarchy’s cost decreases monotonically with budget at unchanged CSR; the flat variant saturates after ≤16 forwards. The default working point is budget 128 .
Figure 5: Single-relation flip rates (10 seeds, mean ± 1 std, dots: per-seed values): ACM (separable: co-authorship PAP dominates), Cora (common-neighbor wins with moderate separation), ogbn-mag (citation dominates).
Figure 6: Structure of the explanations (10 seeds): the certified edge sets are cheap (mean local cost 0.11 – 0.31 ); a single relation suffices for 86 – 93% of feasible instances; and the final margins separate flipped from refused instances.
Figure 7: Case studies (ACM, seed 0): the four archetypes of the output contract. (a) a single-relation flip; (b) a two-relation flip; (c) an explicit refusal—no relation deletion flips the prediction, reported as infeasible; (d) a relation-infeasible node that the flat verified edge set flips instead. Bars show the prediction margin before/after the intervention (hatched: no relation-level change exists); edge costs are the deleted fraction of the node’s receptive field.
Backbone
Method
ACM CSR ↑
Cora CSR ↑
ogbn-mag CSR ↑
HAN
RACE-hier
0.255
0.314
0.182
CF 2 -hetero
0.244
0.298
0.164
HGT
RACE-hier
0.384
0.611
0.205
CF 2 -hetero
0.355
0.581
0.185
R-GCN
RACE-hier
0.785
0.939
0.318
CF 2 -hetero
0.771
0.858
0.292
Appendix
Table 10: Cross-backbone study on ACM / Cora-derived / ogbn-mag (5 seeds; hierarchical vs. CF 2 -hetero, CSR = success rate; all CSR differences p=0.062 , the minimum attainable with five seeds). The CSR advantage holds in all 9/9 backbone–dataset cells; the paired cost advantage is established in the all-targets comparison of Table 1 and on ogbn-arXiv (Table 5 ). Bold : better value in each pairwise comparison.
Ablation
Setting
Result (ACM / Cora / ogbn-mag)
margin threshold κ
κ=0.05 vs. κ=0 ; coverage
0.159±0.044 vs. 0.182 ; 0.327±0.095 vs. 0.337 ; 0.135±0.009 vs. 0.167
cost criterion
type / edge / lexicographic; coverage
identical on all datasets ( 0.1818 / 0.3370 / 0.1674 )
edge perturbation
5% random add/remove; Sv∗ agreement
0.975±0.016 / 0.930±0.023 / 0.965±0.011
Appendix
Table 11: Sensitivity ablations (ACM/Cora/mag, 10 seeds): margin threshold and cost criterion, plus relation-set robustness under 5% random edge add/remove.
Quantity
Value
Note
scan = true minimum
102/120 ( 85% )
scan vs. full enum.
off by exactly one edge
5
only nonzero gaps
non-monotonic instances
60/120 ( 50% )
flip under S , not S∪{e}
Appendix
Table 12: Exact edge-level certification on enumerable subgraphs (120 instances). The certified heuristic equals the true minimum deletion count in 102/120 cases and is off by one edge in the five other feasible cases.
Config
exact
greedy
beam
bnb
time (ex./gr.)
standard K=3
0.529
0.634
0.633
—
0.07 s / 1.0 s
standard K=5
0.292
0.440
0.438
—
0.23 s / 2.5 s
standard K=10
0.151
0.286
0.285
—
7.0 s / 5.6 s
standard K=20
—
0.064
0.064
0.158
— / 33 s
synergistic K=5
0.018
0.018
0.021
—
0.17 s / 1.1 s
Appendix
Table 13: Synthetic SCM (10 data seeds; hit = data-causal recovery; model-dependence recovery coincides with it at K≤10 and is 0.089 at K=20 / 0.201 synergistic; exact at K≤10 , greedy/beam everywhere, bnb at K=20 ). Exact search certifies the minimum-cost answer and is the fastest search in the benchmark regime ( K≤10 ); greedy/beam are effect-ordered heuristics, and at K=20 the budgeted branch-and-bound (bnb) is the only approximation that improves over them.
Figure 8: Relation search as the vocabulary grows (synthetic SCM, 10 data seeds, mean ± 1 std; shaded: benchmark regime K≤10 ). (a) Data-causal hit rate: exact search certifies the minimum-cost answer at every feasible K ; the effect-ordered greedy/beam heuristics rank the causal relation higher because the lexicographic cost prefers cheaper noise relations; at K=20 the budgeted branch-and-bound (bnb) is the only approximation that improves over greedy/beam. (b) Wall-clock per seed: exact search is the fastest in the benchmark regime.
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
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