Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation

Eduin E. Hernandez; Luis F. Garcia; Nurassyl Askar; Sergio A. Diaz; Stefano Rini

cs.CLSep 13, 2026

Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation

Authors: Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar, Sergio A. Diaz, Stefano Rini

Organizations: National Yang Ming Chiao Tung University, Hsinchu, Taiwan · Independent Researcher

Abstract

Multi-Hop Knowledge Graph Question Answering (KGQA) tasks require models to assemble relational evidence along paths in a KG to answer natural-language questions. However, existing KGQA systems typically focus on predicting the final answer without explicitly modeling or validating the intermediate reasoning steps, obscuring whether the correct answers arise from faithful multi-hop reasoning. To address this limitation, we re-frame multi-hop KGQA as a question-conditioned graph navigation problem. We refer to this formulation as THESEUS - Traceable Hop-wise Evidence SEarch in a Unified Semantics. In this setting, an agent receives a KG, a question, and a topic entity, and traverses a sequence of relations towards the answer, making the reasoning path explicit. To systematically study this formulation, we provide three key contributions. (i) We augment the existing KINSHIP and MQuAKE resources into navigation-ready KGQA datasets with annotated evidence paths and paraphrased questions. (ii) We design evaluation protocols to measure path fidelity, robustness to linguistic variation, and performance across multi-hop and multi-answer questions. (iii) We adapt established path-based KG completion agents - MINERVA, MultiHopKG, and SQUIRE - to operate on full question embeddings rather than symbolic single-relation queries, enabling their trajectories to be guided by natural-language semantics. Together, these contributions advance KGQA research toward systems where traceability is fundamental: answers are accompanied by explicit reasoning paths whose agreement with reference evidence can be systematically evaluated.

Figures & tables

Figure 1: Taxonomy of KG Navigation settings. Theseus lies at the intersection of KGQA and path-based KG reasoning, extending explicit KG navigation to natural-language questions and path-level evaluations.

Dataset	Kinship	MetaQA	MQuAKE-ST
Entities $\|\mathcal{E}\|$	24	43,234	38,516
Relations $\|\mathcal{R}\|$	12	9	665
Triples $\|\mathcal{T}\|$	112	134,741	724,141
Avg. Out-Degree	4.67	3.12	18.80
WCCs	2	30	1
Graph Density	$2.029\text{\times}{10}^{-01}$	$1.334\text{\times}{10}^{-04}$	$8.663\text{\times}{10}^{-04}$

Table 1: Structural KG statistics.

Dataset	Answer Type	Question Counts by Hop Length					Traversal Difficulty
Dataset	Answer Type	1-Hop	2-Hop	3-Hop	4-Hop	Total	$\textbf{RW-Ans}_{p}$	$\textbf{RW-Ans}_{\mathrm{MC}}$	Avg. Actions
Kinship	Single	112	248	420	–	780	$9.1447\text{\times}{10}^{-02}$	$\left($ 9.066 $\,\pm\,$ 2.688,234,364,782,952 $\right)\mathrm{e}{-2}$	$6.4189\text{\times}{10}^{00}$
MetaQA	Multi	116,045	148,724	142,744	–	407,513	$6.8742\text{\times}{10}^{-02}$	$\left($ 6.875,928,341,817,38 $\,\pm\,$ 0.079,025,449,396,079,55 $\right)\mathrm{e}{-2}$
MQuAKE-ST	Single	13,733	9,432	4,215	1,701	29,081	$5.6292\text{\times}{10}^{-03}$	$\left($ 5.627,333,333,333,333 $\,\pm\,$ 0.731,869,751,617,959,3 $\right)\mathrm{e}{-3}$	$4.5048\text{\times}{10}^{01}$
MQuAKE-ST	Multi	12,959	4,723	2,418	1,879	21,979	$6.0792\text{\times}{10}^{-03}$	$\left($ 6.046 $\,\pm\,$ 1.72 $\right)\mathrm{e}{-3}$	$8.3360\text{\times}{10}^{01}$

Table 2: Number of questions per hop length and KGQA traversal difficulty. Question counts are computed over the full QA set, while traversal difficulty is evaluated on the test split for the corresponding

n

-hop setting.

(a) Kinship , $N=3$
Model / Metric	Answer Metrics		Path-Fidelity Metrics
Model / Metric	MRR $\uparrow$	Hits@1 $\uparrow$	$\mathrm{RED}\downarrow$	$\mathrm{PED}\downarrow$	$\mathrm{F1_{Rel}}\uparrow$	$\mathrm{F1_{SG}}\uparrow$
Structural Calibration References
$\textsc{RW-Ans}_{\mathrm{MC}}$	$\dagger$	$\dagger$	$2.401\,353\,333\,333\,333$ $\pm$ $0.059\,457\,999\,742\,114\,89$	$2.546\,303\,666\,666\,667$ $\pm$ $0.052\,394\,442\,771\,474\,66$	$0.258\,610\,666\,666\,666\,7$ $\pm$ $0.020\,857\,910\,569\,693\,54$	$0.127\,675\,666\,666\,666\,7$ $\pm$ $0.007\,771\,681\,499\,735\,649$
Shortest Path Oracle	$\dagger$	$\dagger$	1.871	2.099	0.350	0.220
Direct Answer-Prediction Models

Table 3: Main performance results across Kinship and MQuAKE-ST (

n

-hop). Mean

\pm

std over three trials. The answer-oracle shortest-path reference is deterministic and is reported as a single value. Higher is better for MRR, Hits@1,

\mathrm{F1_{Rel}}

, and

\mathrm{F1_{SG}}

; lower is better for RED and PED. Best valid results are bolded within each model group and dataset setting.

Model / Metric	Kinship		MQuAKE-ST Single		MQuAKE-ST Multi
Model / Metric	Hits@1 $\uparrow$	PED $\downarrow$	Hits@1 $\uparrow$	PED $\downarrow$	Hits@1 $\uparrow$	PED $\downarrow$
Direct Answer-Prediction Models
EmbedKGQA	$0.173\,817$ $\pm$ $0.362\,033\,259\,798\,046\,7$		$0.560\,653\,333\,333\,333\,3$ $\pm$ $0.051\,947\,004\,084\,290\,89$		$0.846\,615\,666\,666\,666\,7$ $\pm$ $0.036\,211\,033\,309\,384\,23$
TransferNet	$0.4279$ $\pm$ $0.995\,667\,113\,045\,319$		$0.4428$ $\pm$ $0.113\,918\,567\,406\,722\,6$		$0.603\,433\,333\,333\,333\,3$ $\pm$ $0.181\,950\,661\,810\,649\,5$
ReaRev	$0.2651$ $\pm$ $0.439\,449\,655\,819\,639\,9$		$0.9534$ $\pm$ $0.039\,127\,995\,093\,027\,7$		$0.937\,433\,333\,333\,333\,3$ $\pm$ $0.086\,817\,816\,911\,814\,45$
Adapted Path-based Models

Table 4: Hits@1 and path edit distance (PED) performance under question rephrasing. Models are trained on the canonical questions and evaluated on their rephrased variants, using the settings reported in Tab. 3 . Higher is better for Hits@1; lower is better for PED. Best valid results are bolded within each model group.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Template family	Example realization
Possessive identity	“Who is $[A]$ ’s $[r_{1}]$ ’s $\cdots$ ’s $[r_{n}]$ ?”
Possessive name-seeking	“What is the name of $[A]$ ’s $[r_{1}]$ ’s $\cdots$ ’s $[r_{n}]$ ?”
Possessive conversational	“Can you tell me who $[A]$ ’s $[r_{1}]$ ’s $\cdots$ ’s $[r_{n}]$ is?”
Mixed final-relation form	“Who is the $[r_{n}]$ of $[A]$ ’s $[r_{1}]$ ’s $\cdots$ ’s $[r_{n-1}]$ ?”
Nested “of”-chain	“Who is the $[r_{n}]$ of the $\cdots$ of the $[r_{1}]$ of $[A]$ ?”
Nested “of” conversational	“Do you know who the $[r_{n}]$ of the $\cdots$ of the $[r_{1}]$ of $[A]$ is?”

Appendix

Table 5: Representative Kinship paraphrase-template families.

Dataset	WC2014-M	PQ-M	PQL-M
Entities $\|\mathcal{E}\|$	1,127	2,256	6,505
Relations $\|\mathcal{R}\|$	10	13	411
Triples $\|\mathcal{T}\|$	6,482	3,377	5,597
Avg. Out-Degree	5.7516	1.4969	0.8604
WCCs	1	46	1,346
Graph Density	$6.258\text{\times}{10}^{-03}$	$1.240\text{\times}{10}^{-03}$	$2.634\text{\times}{10}^{-04}$

Appendix

Table 6: Structural statistics of prior path-oriented KGQA benchmarks under the released navigation graphs used in our analysis.

Dataset	Answer Type	Evaluation Instances by Hop Length				Traversal Difficulty
Dataset	Answer Type	1-Hop	2-Hop	3-Hop	Total	$\textbf{RW-Ans}_{p}$	$\textbf{RW-Ans}_{\mathrm{MC}}$	Avg. Actions
WC2014-M	Multi	6,482	1,472	–	7,954	$1.4742\text{\times}{10}^{-01}$	$\left($ 1.474,403,333,333,333 $\,\pm\,$ 0.017,378,243,102,607,74 $\right)\mathrm{e}{-1}$	$3.4439\text{\times}{10}^{01}$
PQ-M	Multi	–	1,908	5,198	7,106	$1.8009\text{\times}{10}^{-01}$	$\left($ 1.804,126,666,666,667 $\,\pm\,$ 0.074,033,393,366,327,16 $\right)\mathrm{e}{-1}$	$3.8605\text{\times}{10}^{00}$
PQL-M	Multi	–	1,168	954	2,122	$5.8266\text{\times}{10}^{-01}$	$\left($ 5.852,11 $\,\pm\,$ 0.159,003,993,660,536,7 $\right)\mathrm{e}{-1}$	$3.5536\text{\times}{10}^{00}$

Appendix

Table 7: Evaluation-instance counts and traversal difficulty of prior path-oriented KGQA benchmarks under the released navigation graphs used in our analysis.

	Kinship		MQuAKE-ST
Answer Type	Single		Single			Multi
Hop Size	2-hop	3-hop	2-hop	3-hop	4-hop	2-hop	3-hop	4-hop
KGQA Baselines
EmbedKGQA	$0.964\,912$ $\pm$ $0.151\,935\,496\,839\,941\,9$	$0.936\,508$ $\pm$ $0.549\,856\,849\,370\,815\,8$	$0.505\,873\,666\,666\,666\,7$ $\pm$ $0.121\,314\,530\,182\,222\,4$	$0.607\,936\,666\,666\,666\,7$ $\pm$ $0.107\,365\,236\,614\,713\,1$	$0.751\,894$ $\pm$ $0.086\,793\,983\,662\,463\,61$	$0.810\,989$ $\pm$ $0.100\,715\,193\,987\,799\,1$	$0.911\,680\,666\,666\,666\,7$ $\pm$ $0.024\,675\,950\,505\,164\,61$	$0.979\,742$ $\pm$ $0.063\,791\,431\,242\,761\,75$
TransferNet	$0.886$ $\pm$ $0.845\,997\,044\,912\,096\,6$	$0.899\,466\,666\,666\,666\,7$ $\pm$ $0.458\,416\,113\,736\,562\,8$	$0.590\,333\,333\,333\,333\,3$ $\pm$ $0.177\,743\,363\,682\,961$	$0.3032$ $\pm$ $0.157\,673\,935\,702\,766$	$0.3106$ $\pm$ $0.230\,134\,895\,224\,518\,3$	$0.673\,966\,666\,666\,666\,7$ $\pm$ $0.219\,979\,756\,644\,408\,9$	$0.554\,133\,333\,333\,333\,3$ $\pm$ $0.177\,926\,398\,640\,936\,2$	$0.537\,766\,666\,666\,666\,7$ $\pm$ $0.274\,408\,278\,543\,730\,1$
ReaRev	$0.9035$ $\pm$ $0.167\,142\,902\,930\,396\,7$	$0.8307$ $\pm$ $0.111\,478\,607\,813\,337\,9$	$0.9923$ $\pm$ $0.011$	$0.963\,466\,666\,666\,666\,7$ $\pm$ $0.059\,936\,077\,059\,925\,55$	$0.988\,633\,333\,333\,333\,3$ $\pm$ $0.056\,500\,737\,458\,314\,06$	$0.976\,533\,333\,333\,333\,3$ $\pm$ $0.070\,720\,105\,580\,615\,02$	$0.9473$ $\pm$ $0.197\,453\,792\,062\,852$	$0.9466$ $\pm$ $0.064\,085\,879\,880\,048\,46$

Appendix

Table 8: Per-hop Hits@1 performance of models trained on the mixed

n

-hop settings in Tab. 3 . Best valid results are bolded within each model group.

Model / Metric	MRR $\uparrow$	Hits@1 $\uparrow$
Model / Metric	MRR $\uparrow$	n-hop	1-hop	2-hop	3-hop
KGQA Baselines
EmbedKGQA	$0.814\,125\,333\,333\,333\,3$ $\pm$ $0.013\,919\,828\,782\,471\,91$	$0.759\,507\,333\,333\,333\,3$ $\pm$ $0.326\,160\,053\,092\,547\,3$	$0.735\,373$ $\pm$ $0.037\,690\,545\,233\,519\,77$	$0.781\,295$ $\pm$ $0.030\,725\,336\,450\,558\,19$	$0.699\,400\,666\,666\,666\,7$ $\pm$ $0.009\,968\,381\,680\,761\,09$
TransferNet	$0.9383$ $\pm$ $0.854\,791\,202\,575\,225\,4$	$0.923\,833\,333\,333\,333\,3$ $\pm$ $0.103\,238\,816\,989\,218\,4$	$0.966\,166\,666\,666\,666\,7$ $\pm$ $0.077\,358\,472\,925\,293\,29$	$0.946\,133\,333\,333\,333\,3$ $\pm$ $0.769\,541\,638\,466\,258$	$0.871\,133\,333\,333\,333\,3$ $\pm$ $0.200\,858\,067\,633\,175\,6$
ReaRev	$0.873\,166\,666\,666\,666\,7$ $\pm$ $0.109\,203\,174\,557\,030\,8$	$0.864\,233\,333\,333\,333\,3$ $\pm$ $0.098\,083\,297\,932\,590\,62$	$0.487\,033\,333\,333\,333\,3$ $\pm$ $0.380\,008\,333\,241\,961\,2$	$0.9989$ $\pm$ $0.001\,732\,050\,807\,568\,877$	$0.986\,733\,333\,333\,333\,3$ $\pm$ $0.015\,044\,378\,795\,195\,68$
Adapted Path-based Models

Appendix

Table 9: Performance on MetaQA (

n

-hop) with hop budget

N=3

. Mean

\pm

std over three trials. Higher is better for MRR and Hits@1. Per-hop results are obtained from the same mixed-hop model. Best valid results are bolded within each model group.

Model / Answer Type	Single Answer	Multi Answer
LLama3.1-Instruct	0.930	0.988
Qwen2.5-Instruct	0.909	0.963
Gemma4	0.997	0.985

Appendix

Table 10: Oracle answer-generation performance on MQuAKE-ST under the gold-evidence setting. For single-answer questions, the LLM is given the annotated gold path; for multi-answer questions, it is given all semantically valid evidence paths. Correctness is evaluated by exact match against the answer set. Full model descriptions are provided in Tab. 11 .

Model	# Params	Trainable Params	Precision
KGQA Baselines
EmbedKGQA	7.54M	3.69M	FP32
TransferNet	6.14M	2.59M	FP32
ReaRev	1.69M	1.69M	FP32
Adapted Path-based models
MINERVA	4.60M	4.60M	FP32

Appendix

Table 11: Model sizes. For KGQA models, parameter counts are reported after instantiating each model on MQuAKE-ST . Language encoders and LLMs are kept frozen throughout our experiments. For LLM baselines, parameter counts and weight formats follow the Ollama checkpoints used for inference.

Model	1-Hop	2-Hop	3-Hop
EmbedKGQA (Reported)	0.975	0.988	0.948
EmbedKGQA (Reproduced)	0.739	0.783	0.698

Appendix

Table 12: Performance on MetaQA_FULL (Hits@1).

Explore similar work

TRACE: An Experiential Framework for Coherent Multi-hop Knowledge Graph Question Answering
Apr 13, 2026Yingxu Wang, Jiaxin Huang, Mengzhu Wang +1Knowledge Graph Question Answering Multi-Hop QA
Mohamed bin Zayed University of Artificial Intelligence · Hebei University of Technology · City University of Hong Kong
Ontology-Guided Evidence Path Inference for Multi-hop Knowledge Graph Question Answering
Jun 26, 2026Yongxue Shan, Meihan Wu, Cundi Fang +2Multi-Hop QA Graph-Based Retrieval
National University of Defense Technology · Changsha, China · Pengcheng Laboratory +1
STEM: Structure-Tracing Evidence Mining for Knowledge Graphs-Driven Retrieval-Augmented Generation
Apr 24, 2026Peng Yu, En Xu, Bin Chen +2Graph Neural Networks Graph Retrieval-Augmented Generation
AI Product Center, Kingsoft Corporation, Beijing, China

Apr 13, 2026J/K move · Enter open · S save

TRACE: An Experiential Framework for Coherent Multi-hop Knowledge Graph Question Answering

Yingxu Wang, Jiaxin Huang, Mengzhu Wang, Nan Yin

Mohamed bin Zayed University of Artificial Intelligence · Hebei University of Technology · City University of Hong Kong

Knowledge Graph Question Answering Multi-Hop QA LLM Reasoning with Graphs

Open paper AskPDF arXiv

Multi-hop Knowledge Graph Question Answering (KGQA) requires coherent reasoning across relational paths, yet existing methods often treat each reasoning step independently and fail to effectively leverage experience from prior explorations, leading to fragmented reasoning and redundant exploration. To address these challenges, we propose Trajectoryaware Reasoning with Adaptive Context and Exploration priors (TRACE), an experiential framework that unifies LLM-driven contextual reasoning with exploration prior integration to enhance the coherence and robustness of multihop KGQA. Specifically, TRACE dynamically translates evolving reasoning paths into natural language narratives to maintain semantic continuity, while abstracting prior exploration trajectories into reusable experiential priors that capture recurring exploration patterns. A dualfeedback re-ranking mechanism further integrates contextual narratives with exploration priors to guide relation selection during reasoning. Extensive experiments on multiple KGQA benchmarks demonstrate that TRACE consistently outperforms state-of-the-art baselines.

Abstract

Explore similar work

TRACE: An Experiential Framework for Coherent Multi-hop Knowledge Graph Question Answering

Ontology-Guided Evidence Path Inference for Multi-hop Knowledge Graph Question Answering

STEM: Structure-Tracing Evidence Mining for Knowledge Graphs-Driven Retrieval-Augmented Generation