RAW-Explainer: Post-hoc Explanations of Path Reasoning Graph Neural Networks for Knowledge Graph Completion

Ryoji Kubo; Samyam Lamichhane; Djellel Difallah

cs.LGJun 14, 2025

RAW-Explainer: Post-hoc Explanations of Path Reasoning Graph Neural Networks for Knowledge Graph Completion

Authors: Ryoji Kubo, Samyam Lamichhane, Djellel Difallah

Organizations: New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

Abstract

Path reasoning graph neural networks have demonstrated state-of-the-art performance on knowledge graph completion tasks such as link prediction. However, interpreting their predictions remains a challenging open problem, as most GNN explainability methods target node-level or graph-level tasks. In this paper, we propose RAW-Explainer ( $\underline{Ra}$ ndom $\underline{W}$ alk Explainer), a novel explainability method tailored to path reasoning GNNs that generates connected, concise, and interpretable subgraph explanations for link prediction in knowledge graphs. Our method uses heterogeneous information to identify factual explanations and encourages connectivity through a random walk objective, using a parameterized model for efficient collective explanation. Furthermore, RAW-Explainer overcomes the distribution shift issue when evaluating explanatory subgraphs that are orders of magnitude smaller than the full graph by proposing a robust evaluator that generalizes to the subgraph distribution. Extensive results on standard knowledge graph completion benchmarks demonstrate that our approach strikes a balance between explanation quality and computational efficiency. Code and data are available at: https://github.com/colab-nyuad/RAWExplainer

Figures & tables

Method	Het.	Conn.	Path	OOD	Ind.	Scal.	LP
GNN-Expl. [ 9 ] NeurIPS’19	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	( $\checkmark$ )
PG-Expl. [ 23 ] NeurIPS’20	$\times$	$\times$	$\times$	$\times$	$\checkmark$	$\checkmark$	( $\checkmark$ )
PaGE-Link [ 12 ] WWW’23	$\checkmark$	$\checkmark$	$\checkmark$	$\times$	$\times$	$\times$	$\checkmark$
PowerLink [ 24 ] KDD’24	$\checkmark$	$\checkmark$	$\checkmark$	$\times$	$\times$	( $\checkmark$ )	$\checkmark$
RAW-Expl.	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$

Table 1: GNN explanation methods for KG completion. Het.: heterogeneous; Conn.: connectivity; Path: path-aware; OOD: OOD robust; Ind.: inductive; Scal.: scalable; LP: link prediction.

\checkmark

: supported; (

\checkmark

): non-trivial extension;

\times

: not supported.

Figure 1: End-to-end factual evaluation protocol for GNN explanations in KG completion.

Panel of Figure 2 — Figure 2: Performance evaluation of $\Phi$ and $\Phi_{eval}$ under different probabilities of random edge removal.

Panel of Figure 3 — Figure 3: Comparing evaluator variants $\Phi_{eval}^{unif}$ and $\Phi_{eval}^{dist}$ on different ego network sizes around the query.

Panel of Figure 4 — Figure 4: Test MRR vs. edge budget for each dataset.

Method	WN18RR	FB15k-237	NELL-995	YAGO3-10
GNN-Explainer	109	1663	90	429
PG-Explainer	6	48	4	28
PaGE-Link	172	940	700	2238
Power-Link	166	9577	127	183
RAW-Explainer	17	128	14	91

Table 2: Inference time (minutes) to generate test-set explanations. Best and second best are highlighted.

Method	25	50	75	100	300	500	1000
PGExplainer	1.49	1.57	1.68	1.80	2.73	3.74	8.66
RAWExplainer	1.39	1.25	1.21	1.19	1.22	1.28	1.39

Table 3: Average number of connected components on WN18RR across varying edge budgets.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

	FB15k-237	WN18RR	NELL-995	YAGO3-10
#Entity	14,541	40,943	75,492	123,182
#Relation	237	11	200	37
#Train	272,115	86,835	149,678	1,079,040
#Validation	17,535	3,034	543	5,000
#Test	20,466	3,134	2,818	5,000

Appendix

Table 4: Dataset statistics for KG completion.

Model	Data	Dep	1-hop	$p_{e}$	DD
$\Phi$	WN18RR	N	N	0.0	N
	FB15k-237	Y	Y	0.0	N
	NELL-995	N	N	0.0	N
	YAGO3-10	N	N	0.0	N
$\Phi_{\text{eval}}^{\text{unif}}$	WN18RR	N	N	0.15	N
	FB15k-237	Y	Y	0.15	N

Appendix

Table 5: Evaluator-specific hyperparameters across datasets.

Parameter	Value
Top- $k$ tails	0
Teleport prob.	0.2
Adj. aggregation	max
Ego network	No

Appendix

Table 6: Hyperparameters used across all datasets.

Parameter	WN18RR	FB15k-237	NELL-995	YAGO3-10
Optimizer	Adam	Adam	Adam	Adam
Learning rate	$1\times 10^{-2}$	$1\times 10^{-3}$	$1\times 10^{-2}$	$1\times 10^{-2}$
Size regularization	1	4	1	1
Entropy regularization	1	3	1	1
Top- $k$ tails	1	1	1	1
Ego network	No	No	No	No

Appendix

Table 7: Hyperparameters used for GNN-Explainer on each dataset.

Parameter	WN18RR	FB15k-237	NELL-995	YAGO3-10
Optimizer	Adam	Adam	Adam	Adam
Learning rate	$1\times 10^{-3}$	$5\times 10^{-5}$	$1\times 10^{-3}$	$5\times 10^{-5}$
Size regularization	2	5	2	4
Entropy regularization	4	2	4	2
Temp. (start)	4	2	4	2
Temp. (end)	3	2	3	2

Appendix

Table 8: Hyperparameters used for PG-Explainer on each dataset.

Parameter	WN18RR	FB15k-237	NELL-995	YAGO3-10
Optimizer	Adam	AdamW	Adam	Adam
Learning rate	$5\times 10^{-5}$	$3\times 10^{-1}$	$5\times 10^{-5}$	$5\times 10^{-5}$
LR decay	-	$5\times 10^{-3}$	-	-
Size reg.	4	1	4	4
Entropy reg.	2	4	2	2
Temp. (start)	2	2	2	2

Appendix

Table 9: Hyperparameters used for RAW-Explainer on each dataset.

Parameter	WN18RR	FB15k-237	NELL-995	YAGO3-10 $\dagger$
Optimizer	Adam	Adam	Adam	Adam
Learning rate	$1\times 10^{-2}$	$1\times 10^{-2}$	$1\times 10^{-2}$	$1\times 10^{-2}$
Prune graph	Yes	Yes	Yes	Yes
Path loss	Yes	Yes	Yes	Yes
Top- $k$ tails	1	1	1	1
Prune max deg.	200	30	200	200

Appendix

Table 10: Hyperparameters used for PaGE-Link on each dataset.

Parameter	WN18RR	FB15k-237	NELL-995	YAGO3-10 $\dagger$
Optimizer	Adam	Adam	Adam	Adam
Learning rate	$5\times 10^{-3}$	$5\times 10^{-3}$	$5\times 10^{-3}$	$5\times 10^{-3}$
Prune graph	Yes	Yes	Yes	Yes
Prune max deg.	20	30	20	30
Path loss	Yes	Yes	Yes	Yes
Top- $k$ tails	1	1	1	1

Appendix

Table 11: Hyperparameters used for Power-Link on each dataset.

	WN18RR		FB15k-237		NELL-995		YAGO3-10
Drop Prob.	$\Phi$	$\Phi_{\mathrm{eval}}$	$\Phi$	$\Phi_{\mathrm{eval}}$	$\Phi$	$\Phi_{\mathrm{eval}}$	$\Phi$	$\Phi_{\mathrm{eval}}$
0.00	0.551	0.553	0.422	0.427	0.462	0.472	0.578	0.572
0.05	0.488	0.524	0.411	0.419	–	–	–	–
0.10	0.437	0.496	0.402	0.412	0.130	0.455	0.514	0.532
0.20	0.353	0.444	0.383	0.396	0.099	0.436	0.464	0.489
0.30	0.288	0.389	0.361	0.382	0.087	0.414	0.407	0.437

Appendix

Table 12: MRR under different random edge-drop probabilities.

	WN18RR		FB15k-237		NELL-995		YAGO3-10
Hops	$\Phi_{\mathrm{eval}}^{\mathrm{unif}}$	$\Phi_{\mathrm{eval}}^{\mathrm{dist}}$	$\Phi_{\mathrm{eval}}^{\mathrm{unif}}$	$\Phi_{\mathrm{eval}}^{\mathrm{dist}}$	$\Phi_{\mathrm{eval}}^{\mathrm{unif}}$	$\Phi_{\mathrm{eval}}^{\mathrm{dist}}$	$\Phi_{\mathrm{eval}}^{\mathrm{unif}}$	$\Phi_{\mathrm{eval}}^{\mathrm{dist}}$
1	0.348	0.348	0.005	0.005	0.269	0.277	0.272	0.281
2	0.376	0.382	0.141	0.171	0.307	0.321	0.333	0.377
3	0.398	0.458	0.401	0.406	0.377	0.416	0.479	0.496
4	0.369	0.479	0.422	0.419	0.435	0.469	0.554	0.572
5	0.381	0.485	–	–	0.464	0.482	0.570	0.581

Appendix

Table 13: MRR at different hop distances.

Method	25	50	75	100	300	500	1000
WN18RR
RW	0.384	0.434	0.451	0.462	0.489	0.501	0.515
BFS	0.047	0.054	0.058	0.059	0.070	0.074	0.084
GNN-Explainer	0.420	0.434	0.436	0.438	0.449	0.452	0.453
PG-Explainer	0.459	0.459	0.467	0.470	0.476	0.479	0.483
PaGE-Link	0.428	0.450	0.445	0.442	0.441	0.441	0.441

Appendix

Table 14: Test MRR across different edge budgets on all four datasets. Best and second best results are highlighted.

Method	25	50	75	100	300	500	1000
RW	0.384	0.434	0.451	0.462	0.489	0.501	0.515
RAWExplainer	0.455	0.489	0.494	0.499	0.509	0.515	0.521
RAWExplainer ( $\Phi$ )	0.454	0.479	0.490	0.494	0.506	0.510	0.521
RAWExplainer ( $\Phi^{unif}_{eval}$ )	0.462	0.483	0.492	0.496	0.507	0.511	0.522
RAWExplainer (-RW)	0.420	0.436	0.443	0.446	0.439	0.433	0.435
RAWExplainer (-RelEmb)	0.453	0.481	0.491	0.497	0.504	0.511	0.521

Appendix

Table 15: WN18RR test MRR across edge budgets for the ablation study.

Method	25	50	75	100	300	500	1000
WN18RR
RW	0.391	0.439	0.455	0.466	0.495	0.508	0.518
BFS	0.027	0.031	0.032	0.033	0.039	0.042	0.051
GNNExplainer	0.227	0.334	0.367	0.382	0.397	0.401	0.403
PGExplainer	0.234	0.312	0.345	0.359	0.396	0.408	0.423
PaGELink	0.343	0.360	0.362	0.362	0.362	0.362	0.362

Appendix

Table 16: Test MRR across edge budgets on WN18RR and NELL-995 with the RED-GNN backbone. Best and second best results are highlighted within each dataset.

Method	25	50	75	100	300	500	1000
RW	0.180	0.150	0.148	0.148	0.166	0.174	0.185
BFS	0.505	0.500	0.499	0.498	0.493	0.491	0.484
GNNExplainer	0.151	0.148	0.151	0.154	0.158	0.159	0.164
PGExplainer	0.148	0.136	0.136	0.136	0.158	0.169	0.179
PaGELink	0.139	0.139	0.139	0.139	0.139	0.139	0.139
PowerLink	0.149	0.150	0.150	0.150	0.150	0.150	0.150

Appendix

Table 17: WN18RR test

\mathrm{fid}_{-}

across edge budgets. Lower is better.

Method	25	50	75	100	300	500	1000
RW	0.472	0.508	0.516	0.520	0.528	0.531	0.541
BFS	0.063	0.069	0.071	0.071	0.080	0.085	0.097
GNNExplainer	0.424	0.450	0.458	0.467	0.483	0.489	0.496
PGExplainer	0.484	0.507	0.516	0.523	0.538	0.540	0.547
PaGELink	0.438	0.444	0.447	0.449	0.451	0.451	0.451
PowerLink	0.404	0.407	0.410	0.410	0.410	0.410	0.410

Appendix

Table 18: WN18RR test

\mathrm{fid}_{+}

across edge budgets. Higher is better.

Method	25	50	75	100	300	500	1000
RW	0.094	0.054	0.045	0.040	0.031	0.027	0.017
BFS	0.490	0.485	0.482	0.482	0.475	0.471	0.463
GNNExplainer	0.157	0.132	0.119	0.114	0.090	0.083	0.075
PGExplainer	0.088	0.060	0.048	0.042	0.025	0.018	0.011
PaGELink	0.133	0.126	0.124	0.121	0.120	0.120	0.120
PowerLink	0.166	0.163	0.162	0.162	0.161	0.162	0.161

Appendix

Table 19: WN18RR test

\mathrm{MRR}(\mathcal{G}_{\setminus S})

across edge budgets. Lower is better.

Figure 5: Comparison of explanation subgraphs for a sample WN18RR query with a 50-edge budget (shown in blue; multi-relational and inverse edges are collapsed; the red square and red circle denote the query source and target entities, respectively). (a) PG-Explainer yields a fragmented explanation with 13 connected components. (b) RAW-Explainer produces a denser subgraph with a single connected component, concentrated around the query head and tail entities.

GNN Explainability

Graph neural network explainability studies how to identify and communicate the features, nodes, edges, and subgraphs behind graph-model predictions.

See all 81 papers

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling
Feb 25, 2026Shiqi Yan, Yubo Chen, Ruiqi Zhou +8LLM Reasoning with Graphs Knowledge Graph Question Answering
Zhongguancun Laboratory, Beijing, China · Department of Electronic Engineering, Tsinghua University, Beijing, China · Ant International, Ant Group, Hangzhou, Zhejiang, China +1
Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark
Oct 2, 2026Steve Azzolin, Francesco Paolo Nerini, Stefano Teso +4GNN Explainability Explainability Evaluation
University of Trento Trento, Italy
RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks
Sep 29, 2026Yuxiang Yao, Zijun ZhaoGraph Counterfactual Explanations GNN Explainability
Project Management Department, Research Center, China Life Insurance Company Ltd. · School of Computer Science and Technology, Beijing Institute of Technology

Feb 25, 2026J/K move · Enter open · S save

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao+7

Zhongguancun Laboratory, Beijing, China · Department of Electronic Engineering, Tsinghua University, Beijing, China · Ant International, Ant Group, Hangzhou, Zhejiang, China+1

LLM Reasoning with Graphs Knowledge Graph Question Answering RL for Language Model Reasoning Reward Shaping

Open paper AskPDF arXiv

The reasoning process of Large Language Models (LLMs) is often plagued by hallucinations and missing facts in question-answering tasks. A promising solution is to ground LLMs' answers in verifiable knowledge sources, such as Knowledge Graphs (KGs). Prevailing KG-enhanced methods typically constrained LLM reasoning either by enforcing rules during generation or by imitating paths from a fixed set of demonstrations. However, they naturally confined the reasoning patterns of LLMs within the scope of prior experience or fine-tuning data, limiting their generalizability to out-of-distribution graph reasoning problems. To tackle this problem, in this paper, we propose Explore-on-Graph (EoG), a novel framework that encourages LLMs to autonomously explore a more diverse reasoning space on KGs. To incentivize exploration and discovery of novel reasoning paths, we propose to introduce reinforcement learning during training, whose reward is the correctness of the reasoning paths' final answers. To enhance the efficiency and meaningfulness of the exploration, we propose to incorporate path information as additional reward signals to refine the exploration process and reduce futile efforts. Extensive experiments on five KGQA benchmark datasets demonstrate that, to the best of our knowledge, our method achieves state-of-the-art performance, outperforming not only open-source but also even closed-source LLMs.

Abstract

GNN Explainability

Explore similar work

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark

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