RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks

Yuxiang Yao; Zijun Zhao

cs.LGSep 29, 2026

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

Abstract

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 $S_{v}^{*}$ 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 $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$
flat	RACE-per-edge	0.216 $\pm$ 0.072	0.159 $\pm$ 0.062	0.452 $\pm$ 0.111	0.305 $\pm$ 0.031	0.168 $\pm$ 0.008	0.378 $\pm$ 0.011
	PNS-hetero	0.216 $\pm$ 0.072	0.159 $\pm$ 0.063	0.450 $\pm$ 0.110	0.306 $\pm$ 0.031	0.168 $\pm$ 0.008	0.378 $\pm$ 0.010
	CF 2 -hetero	0.216 $\pm$ 0.072	0.195 $\pm$ 0.088	0.458 $\pm$ 0.110	0.342 $\pm$ 0.024	0.168 $\pm$ 0.008	0.434 $\pm$ 0.013
RACE-hier		0.224 $\pm$ 0.077 †	0.176 $\pm$ 0.067 †	0.484 $\pm$ 0.122 †	0.332 $\pm$ 0.024 †	0.182 $\pm$ 0.009 †	0.407 $\pm$ 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

\pm

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;

\dagger

p=0.002

before Holm correction (

{\leq}0.062

after). Bold : best value in each column; underlined : second best.


	ACM		Cora		ogbn-mag
Method	CSR $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$
CF-GNNExplainer	0.216 $\pm$ 0.072	0.159 $\pm$ 0.063	0.452 $\pm$ 0.110	0.305 $\pm$ 0.031	0.168 $\pm$ 0.008	0.379 $\pm$ 0.011
RC	0.148 $\pm$ 0.049	0.145 $\pm$ 0.059	0.400 $\pm$ 0.100	0.245 $\pm$ 0.013	0.088 $\pm$ 0.007	0.314 $\pm$ 0.012
NSEG	0.000 $\pm$ 0.001	0.139 $\pm$ 0.041	0.001 $\pm$ 0.001	0.224 $\pm$ 0.021	0.002 $\pm$ 0.001	0.192 $\pm$ 0.014
CF 2	0.216 $\pm$ 0.072	0.195 $\pm$ 0.088	0.458 $\pm$ 0.110	0.342 $\pm$ 0.024	0.168 $\pm$ 0.008	0.434 $\pm$ 0.013

Table 2: Same-task comprehensive comparison under one frozen checkpoint family (10 seeds, mean

\pm

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 $\uparrow$	flat CSR	$p$	hier cost $\downarrow$	flat cost $\downarrow$
ACM	0.224 $\pm$ 0.077	0.174 $\pm$ 0.046	0.002	0.105	0.033
Cora	0.484 $\pm$ 0.122	0.246 $\pm$ 0.071	0.002	0.311	0.080
ogbn-mag	0.182 $\pm$ 0.009	0.165 $\pm$ 0.009	0.002	0.273	0.220
ogbn-arXiv	0.283 $\pm$ 0.005	0.230 $\pm$ 0.003	0.0625	0.287	0.139
DBLP	0.161 $\pm$ 0.035	0.104 $\pm$ 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

\pm

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 $\uparrow$	0.182 $\pm$ 0.048	0.337 $\pm$ 0.096	0.167 $\pm$ 0.009
relation cost $\downarrow$	1.07 $\pm$ 0.03	1.14 $\pm$ 0.02	1.07 $\pm$ 0.01
edge cost $\downarrow$	0.574 $\pm$ 0.013	0.605 $\pm$ 0.044	0.838 $\pm$ 0.014
margin	$-0.263{\pm}0.033$	$-0.459{\pm}0.042$	$-0.197{\pm}0.015$
SF $\uparrow$	0.918 $\pm$ 0.031	0.858 $\pm$ 0.028	0.959 $\pm$ 0.009
attribution	PAP (10/10)	common-nbr (10/10)	citation (10/10)

Table 4: Instance-level relation search (10 seeds, mean

\pm

std). Coverage = fraction of correctly-classified test instances with any feasible relation deletion.

	CSR $\uparrow$		cost $\downarrow$
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.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	#Nodes	#Classes	Features	Relation types
ACM (HAN)	12,499	14	1,903-d BoW	PAP, PTP
ogbn-mag (sub)	30,000	20	128-d emb.	PAP, citation
ogbn-mag (sub, 4-rel)	30,000	20	128-d emb.	PAP, citation, PFP, PAIP
Cora-derived	2,708	7	1,433-d BoW	citation, common-neighbor
ogbn-arXiv (sub)	30,000	20	128-d emb.	citation, co-citation
DBLP	4,057	4	334-d BoW	co-authorship, shared-term

Appendix

Table 6: Datasets used in the experiments.

factual
		ACM		Cora		ogbn-mag
	Method	CSR $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$
	GNNExplainer	0.000 $\pm$ 0.001	0.139 $\pm$ 0.041	0.001 $\pm$ 0.001	0.224 $\pm$ 0.021	0.002 $\pm$ 0.001	0.192 $\pm$ 0.014
	PGExplainer	0.038 $\pm$ 0.058	0.250 $\pm$ 0.354	0.022 $\pm$ 0.048	0.039 $\pm$ 0.080	0.056 $\pm$ 0.062	0.358 $\pm$ 0.412
gradient (global top-5% edge budget, instance-blind)
	Saliency	0.142 $\pm$ 0.026	0.103 $\pm$ 0.006	0.158 $\pm$ 0.037	0.181 $\pm$ 0.030	0.150 $\pm$ 0.007	0.611 $\pm$ 0.012

Appendix

Table 7: Diagnostic comparison (same checkpoints, 10 seeds, mean

\pm

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

\pm

1 std;

*

: paired sign-flip

p=0.002

, Holm-corrected

{\leq}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 $\pm$ 4.8	33.7 $\pm$ 9.6	16.7 $\pm$ 0.9
mean edge cost (fraction)	0.105	0.311	0.273
fallback CSR (pp)	4.2 $\pm$ 2.9	14.7 $\pm$ 2.9	1.5 $\pm$ 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 $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$	CSR $\uparrow$	cost $\downarrow$
full (budget 128)	0.224 $\pm$ 0.077	0.107	0.484 $\pm$ 0.122	0.313	0.182 $\pm$ 0.009	0.273
$-$ fallback	0.182 $\pm$ 0.048	0.107	0.337 $\pm$ 0.096	0.313	0.167 $\pm$ 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

\pm

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

\leq 16

forwards. The default working point is budget

128

Figure 5: Single-relation flip rates (10 seeds, mean

\pm

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 $\uparrow$	Cora CSR $\uparrow$	ogbn-mag CSR $\uparrow$
HAN	RACE-hier	0.255	0.314	0.182
HAN	CF 2 -hetero	0.244	0.298	0.164
HGT	RACE-hier	0.384	0.611	0.205
HGT	CF 2 -hetero	0.355	0.581	0.185
R-GCN	RACE-hier	0.785	0.939	0.318
R-GCN	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 $\kappa$	$\kappa{=}0.05$ vs. $\kappa{=}0$ ; coverage	$0.159{\pm}0.044$ vs. $0.182$ ; $0.327{\pm}0.095$ vs. $0.337$ ; $0.135{\pm}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; $S_{v}^{*}$ agreement	$0.975{\pm}0.016$ / $0.930{\pm}0.023$ / $0.965{\pm}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\cup\{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{\leq}10

and is

0.089

K{=}20

0.201

synergistic; exact at

K\leq 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\leq 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

\pm

1 std; shaded: benchmark regime

K{\leq}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.

Explore similar work

A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit
Sep 4, 2026Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1Counterfactual Explanations GNN Explainability
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece
A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks
Jun 20, 2026Maria Myrto Villia, Filippos Gouidis, Theodore Patkos +1Counterfactual Explanations GNN Explainability
Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH), Heraklion, Greece · Computer Science Department, University of Crete, Greece
Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion
Aug 12, 2026David Bechtoldt, Sidney BenderCounterfactual Evaluation Counterfactual Explanations
Machine Learning Group, TU Berlin, 10587 Berlin, Germany · BIFOLD–Berlin Institute for the Foundations of Learning and Data, Berlin, Germany

Sep 4, 2026, cs.LGJ/K move · Enter open · S save

A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit

Maria Myrto Villia, Filippos Gouidis, Theodore Patkos, Panos Trahanias

Institute of Computer Science, Foundation for Research and Technology - Hellas (FORTH) · Computer Science Department, University of Crete Greece

Counterfactual Explanations GNN Explainability Explainability Evaluation

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

A Comparative Study of Counterfactual Explainers for Graph Neural Networks Enabling Multiple Types of Graph Edit

A Completion-Aware Framework for Impactful Counterfactual Explainability in Graph Neural Networks

Faithful, Sufficient and Understandable: Rethinking Graph Counterfactual Explanations via Discrete Diffusion Inversion