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

Apr 13, 2026

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

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.

Yingxu Wang, Jiaxin Huang, Mengzhu Wang +1

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

Ask PDF

Jun 26, 2026

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

Knowledge graph question answering (KGQA) aims to answer natural-language questions by reasoning over structured facts. Existing multi-hop KGQA methods mainly rely on topic-centered expansion, which faces two key challenges: the search space rapidly grows with noisy mixed-type paths, and retrieved paths may fail to satisfy the semantic constraints of complex questions. To address these challenges, we propose OPI, an ontology-guided evidence path inference framework for multi-hop KGQA. OPI introduces a relation-centric ontology graph to capture the head-tail type constraints of relations, providing a compact interface for answer-side constraints. Based on this ontology graph, OPI first introduces a bidirectional retrieval mechanism by mapping the predicted answer type to compatible final-hop relations and combining topic-side prefix expansion with answer-side final-hop matching, thereby suppressing noisy mixed-type expansion. OPI further adopts an iterative refinement strategy to reassess retrieved paths and candidate answers under the question context, filtering type-compatible but question-irrelevant evidence for more reliable answer prediction. Experiments on WebQSP, CWQ, and MetaQA show that OPI substantially reduces the search space, improves Hit@1/F1 by 4.6/5.0 points on WebQSP and 8.9/3.3 points on CWQ over the strongest prior results, and achieves near-saturated Hit@1 on MetaQA with the retrieval module alone.

Yongxue Shan, Meihan Wu, Cundi Fang +2

National University of Defense Technology · Changsha, China · Pengcheng Laboratory +1

Multi-Hop QA Graph-Based Retrieval Knowledge Graph Question Answering Knowledge Graphs

Ask PDF

Apr 24, 2026

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

Knowledge Graph-based Question Answering (KGQA) plays a pivotal role in complex reasoning tasks but remains constrained by two persistent challenges: the structural heterogeneity of Knowledge Graphs(KGs) often leads to semantic mismatch during retrieval, while existing reasoning path retrieval methods lack a global structural perspective. To address these issues, we propose Structure-Tracing Evidence Mining (STEM), a novel framework that reframes multi-hop reasoning as a schema-guided graph search task. First, we design a Semantic-to-Structural Projection pipeline that leverages KG structural priors to decompose queries into atomic relational assertions and construct an adaptive query schema graph. Subsequently, we execute globally-aware node anchoring and subgraph retrieval to obtain the final evidence reasoning graph from KG. To more effectively integrate global structural information during the graph construction process, we design a Triple-Dependent GNN (Triple-GNN) to generate a Global Guidance Subgraph (Guidance Graph) that guides the construction. STEM significantly improves both the accuracy and evidence completeness of multi-hop reasoning graph retrieval, and achieves State-of-the-Art performance on multiple multi-hop benchmarks.

Peng Yu, En Xu, Bin Chen +2

AI Product Center, Kingsoft Corporation, Beijing, China

Graph Neural Networks Graph Retrieval-Augmented Generation Knowledge Graph Question Answering Multi-Hop Reasoning

Ask PDF