How Benchmark Graph Construction Shapes Multi-Hop KG Navigation: A Controlled Audit of PathQuestion and PathQuestion-Large

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

cs.CLOct 19, 2026

How Benchmark Graph Construction Shapes Multi-Hop KG Navigation: A Controlled Audit of PathQuestion and PathQuestion-Large

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

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

Abstract

Multi-hop knowledge-graph question answering (KGQA) benchmarks are often treated as fixed language-and-reasoning tasks, but for navigation-based methods, difficulty also depends on the graph in which those tasks are instantiated. This makes graph construction a consequential but often entangled part of the navigation task. To isolate this effect, we audit PathQuestion (PQ) and PathQuestion-Large (PQL) as graph-navigation benchmarks under a controlled intervention: we hold questions, topic entities, released answers, released path annotations, and family-level splits fixed while replacing each released task-filtered graph with the larger source KG distributed with the benchmark. Source restoration expands the effective navigation search space and graph-consistent answer and path multiplicity while sharply reducing unguided reachability to released answers. We evaluate whether these structural changes persist across navigation policies using structural references, frozen small-language-model navigation policies, and trained MINERVA policies. Across both frozen and trained policies, restoration substantially reduces released-answer accuracy and trajectory fidelity, while graph-consistent evaluation recovers only part of the loss. These results show that benchmark graph construction is part of the navigation task specification rather than merely an implementation detail and can materially shape measured behavior even when the released QA task is held fixed.

Figures & tables

A. Reconstructed QA Statistics
Statistic	PQ	PQL
Released QA records	7,106	2,625
Reconstructed QA instances	7,105	2,114
Structural QA families	2,923	1,530
A.1 - QA Hop Structure
2-hop families	611 [1,908]	584 [1,168]

Table 1: Reconstructed QA statistics and source-restoration effects under fixed released relation-chain semantics. Bracketed values in Panel A denote QA instances. Panel B reports the number of affected structural families or QA instances relative to the corresponding totals in Panel A.

Graph property	PQ		PQL
Graph property	$G_{F}$	$G_{S}$	$G_{F}$	$G_{S}$
Entities $\|\mathcal{E}\|$	2,256	75,043	6,505	416,249
Relations $\|\mathcal{R}\|$	13	13	411	3,076
Triples $\|\mathcal{T}\|$	3,377	375,444	5,597	831,940
WCCs	46	1	1,346	3,229
Largest WCC (%)	93.75	100.00	38.69	98.33

Table 2: Global graph statistics for the released filtered graphs and distributed source/original KGs.

Dataset	Hops	Paths	Revisited	Backtracked
PQ	2	1,908	120 (6.3%)	117 (6.1%)
	3	5,198	2,488 (47.9%)	2,416 (46.5%)
	All	7,106	2,608 (36.7%)	2,533 (35.6%)
PQL	2	1,594	822 (51.6%)	420 (26.3%)
	3	1,031	982 (95.2%)	858 (83.2%)
	All	2,625	1,804 (68.7%)	1,278 (48.7%)

Table 3: Entity revisits and immediate backtracking in the released PQ/PQL reference paths.

Method	Active KG	Tuning	$A_{\mathrm{released}}$	$P_{\mathrm{released}}$		$A_{\mathrm{graph}}$
Method	Active KG	Tuning	H@1 $\uparrow$	PED $\downarrow$	F1 SG $\uparrow$	H@1 $\uparrow$
Structural References
$\textsc{RW-Ans}_{\mathrm{MC}}$	Filtered	–	$0.175\,036$ $\pm$ $0.009\,632\,279\,065\,724\,788$	$2.054\,171\,666\,666\,667$ $\pm$ $0.037\,148\,837\,577\,148\,13$	$0.341\,040\,666\,666\,666\,7$ $\pm$ $0.010\,880\,194\,544\,829\,3$	$0.175\,319\,666\,666\,666\,7$ $\pm$ $0.009\,358\,495\,249\,415\,544$
$\textsc{RW-Ans}_{\mathrm{MC}}$	Source	–	$0.067\,950\,333\,333\,333\,33$ $\pm$ $0.002\,774\,208\,595\,858\,166$	$2.624\,403$ $\pm$ $0.016\,561\,850\,741\,991\,37$	$0.082\,576\,333\,333\,333\,33$ $\pm$ $0.009\,178\,258\,731\,008\,478$	$0.119\,921\,666\,666\,666\,7$ $\pm$ $0.008\,891\,036\,684\,961\,619$
Shortest Path Oracle	Filtered	–	$1.000$	$1.068\,027$	$0.720\,181$	$1.000$
Shortest Path Oracle	Source	–	$1.000$	$1.772\,109$	$0.464\,512$	$1.000$

Table 4: Primary family-macro navigation results on PathQuestion (PQ). Structural references contextualize unguided answer reachability and shortest-path fidelity; frozen SLMs are evaluated without task-specific training, and MINERVA is trained on the active KG. The two Source MINERVA rows distinguish the matched filtered-dev configuration from a source-dev-tuned control.

Method	Active KG	Tuning	$A_{\mathrm{released}}$	$P_{\mathrm{released}}$		$A_{\mathrm{graph}}$
Method	Active KG	Tuning	H@1 $\uparrow$	PED $\downarrow$	F1 SG $\uparrow$	H@1 $\uparrow$
Structural References
$\textsc{RW-Ans}_{\mathrm{MC}}$	Filtered	–	$0.540\,638\,333\,333\,333\,3$ $\pm$ $0.015\,438\,912\,958\,279\,59$	$1.629\,047\,666\,666\,667$ $\pm$ $0.027\,525\,145\,473\,427\,27$	$0.549\,581\,333\,333\,333\,3$ $\pm$ $0.009\,426\,353\,130\,099\,323$	$0.540\,638\,333\,333\,333\,3$ $\pm$ $0.015\,438\,912\,958\,279\,59$
$\textsc{RW-Ans}_{\mathrm{MC}}$	Source	–	$0.077\,640\,666\,666\,666\,67$ $\pm$ $0.007\,472\,284\,345\,053\,616$	$2.482\,316$ $\pm$ $0.034\,338\,335\,719\,717\,11$	$0.131\,943\,333\,333\,333\,3$ $\pm$ $0.007\,812\,402\,532\,725\,343$	$0.111\,699$ $\pm$ $0.014\,179\,629\,755\,392\,06$
Shortest Path Oracle	Filtered	–	$1.000$	$1.681\,818$	$0.484\,848$	$1.000$
Shortest Path Oracle	Source	–	$1.000$	$1.779\,221$	$0.445\,887$	$1.000$

Table 5: Primary family-macro navigation results on PathQuestion-Large (PQL). Structural references contextualize unguided answer reachability and shortest-path fidelity; frozen SLMs are evaluated without task-specific training, and MINERVA is trained on the active KG. The two Source MINERVA rows distinguish the matched filtered-dev configuration from a source-dev-tuned control.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Hops	$e_{s}=A_{\mathrm{released}}$	$e_{s}\in A_{\mathrm{released}}$
PQ	2	117 (6.1%)	120 (6.3%)
	3	74 (1.4%)	78 (1.5%)
	All	191 (2.7%)	198 (2.8%)
PQL	2	420 (26.3%)	474 (29.7%)
	3	382 (37.1%)	392 (38.0%)
	All	802 (30.6%)	866 (33.0%)

Appendix

Table 6: Topic–answer identity in the released PQ/PQL annotations.

		Reachability to $A_{\mathrm{released}}$		Navigation Space		Graph-consistent Multiplicity
Dataset	Graph	RW-Ans p	RW-Ans MC	Avg. Actions	Reachability	$\boldsymbol{\|A_{\mathrm{graph}}\|}$	$\boldsymbol{\|P_{\mathrm{graph}}\|}$
PQ	Filtered	0.1754	$0.1750\pm 0.0010$	3.69	7.82	1.11	1.13
PQ	Source	0.0681	$0.0680\pm 0.0003$	10.70	57.41	3.17	7.48
PQL	Filtered	0.5395	$0.5406\pm 0.0015$	3.91	4.38	1.10	1.10
PQL	Source	0.0778	$0.0776\pm 0.0007$	154.28	38,107.71	8.41	8.66

Appendix

Table 7: Family-macro structural calibration on the mixed-hop test split. The columns distinguish random-walk reachability to the fixed released answer set

A_{\mathrm{released}}

, local navigation-space size, and the multiplicity of graph-consistent answers

A_{\mathrm{graph}}

and paths

P_{\mathrm{graph}}

. RW-Ans MC reports the mean

\pm

sample standard deviation over seeds 0, 42, and 100 using 100 walks per question.

Dataset	Graph	PED $\downarrow$	RED $\downarrow$	F1 REL $\uparrow$	F1 SG $\uparrow$
PQ	Filtered	1.068	0.986	0.795	0.720
PQ	Source	1.772	1.381	0.686	0.465
PQL	Filtered	1.682	1.682	0.485	0.485
PQL	Source	1.779	1.753	0.456	0.446

Appendix

Table 8: Family-macro path fidelity of the answer-oracle shortest path against

P_{\mathrm{released}}

. The oracle reaches a released answer for every evaluated question.

Dataset	Method	PED $\downarrow$	F1 SG $\uparrow$
PQ	Qwen3 (8B)	$1.583\,333\,333\,333\,333\,3$	$0.520\,126\,915\,708\,812\,2$
	Ministral 3 (8B)	$1.287\,698\,412\,698\,412\,6$	$0.604\,771\,352\,985\,638\,7$
	Gemma 4 (E4B)	$1.239\,229\,024\,943\,310\,7$	$0.608\,730\,158\,730\,158\,8$
	MINERVA	$1.5225$ $\pm$ $0.498\,635\,137\,149\,399$	$0.530\,933\,333\,333\,333\,3$ $\pm$ $0.149\,587\,209\,791\,924\,8$
PQL	Qwen3 (8B)	$1.925\,324\,675\,324\,675\,3$	$0.420\,129\,870\,129\,870\,13$
	Ministral 3 (8B)	$1.633\,116\,883\,116\,883\,2$	$0.527\,056\,277\,056\,277\,1$

Appendix

Table 9: Source-graph trajectory evaluation against

P_{\mathrm{graph}}

references for PQ and PQL. MINERVA uses the source-dev-selected configuration.

Method	Setting	PQ $\uparrow$	PQL $\uparrow$
IRN Zhou et al. (2018)	PQ+ / PQL+ Chen et al. (2019)	$0.536$	$0.529$
HR-BiLSTM + UHop + DQ Chen et al. (2019)	PQ+ / PQL+	$0.9958$	$0.9183$
ABWIM + UHop + DQ Chen et al. (2019)	PQ+ / PQL+	$0.9944$	$0.9237$
SRN Qiu et al. (2020)	PQ-M / PQL-M	$0.893$	$0.783$
MINERVA	Family-controlled, filtered KG	$0.828\,733\,333\,333\,333\,3$ $\pm$ $0.122\,915\,960\,449\,948\,6$	$0.940\,566\,666\,666\,666\,7$ $\pm$ $0.071\,793\,685\,887\,641\,51$

Appendix

Table 10: Historical context for mixed-hop PQ/PQL performance (Hits@1). Prior values use their respective published mixed-hop splits and preprocessing, whereas MINERVA is evaluated on our family-controlled reconstruction of the filtered KG. Values are not directly comparable and are shown only for orientation.

Train $\rightarrow$ Eval	H@1 $\uparrow$	PED $\downarrow$	F1 SG $\uparrow$
$G_{F}\rightarrow G_{F}$	$0.835\,066\,666\,666\,666\,7$ $\pm$ $0.125\,953\,695\,195\,231\,7$	$0.519\,733\,333\,333\,333\,3$ $\pm$ $0.621\,151\,618\,635\,364\,5$	$0.8409$ $\pm$ $0.195\,900\,484\,940\,696\,4$
$G_{F}\rightarrow G_{S}$	$0.430\,633\,333\,333\,333\,3$ $\pm$ $0.186\,446\,596\,464\,868$	$1.699\,066\,666\,666\,667$ $\pm$ $0.169\,193\,183\,471\,833$	$0.4299$ $\pm$ $0.046\,604\,720\,790\,924\,17$
$G_{S}\rightarrow G_{S}$	$0.560\,266\,666\,666\,666\,7$ $\pm$ $0.152\,280\,443\,042\,871\,8$	$1.880\,966\,666\,666\,667$ $\pm$ $0.086\,315\,313\,434\,716\,41$	$0.3928$ $\pm$ $0.045\,210\,618\,221\,829\,26$
$G_{S}\rightarrow G_{F}$	$0.572\,366\,666\,666\,666\,7$ $\pm$ $0.189\,394\,649\,695\,637\,8$	$1.249\,966\,666\,666\,667$ $\pm$ $0.543\,465\,116\,942\,507\,5$	$0.6373$ $\pm$ $0.097\,892\,798\,509\,389\,85$

Appendix

Table 11: Cross-graph transfer of MINERVA on PQ under a shared entity/relation vocabulary. Each checkpoint is tuned on the development split of its training KG and evaluated on both graph conditions without retuning.

G_{F}\rightarrow G_{S}

and

G_{S}\rightarrow G_{F}

therefore measure graph-expansion and graph-contraction transfer, respectively.

Train $\rightarrow$ Eval	H@1 $\uparrow$	PED $\downarrow$	F1 SG $\uparrow$
$G_{F}\rightarrow G_{F}$	$0.9405$ $\pm$ $0.049\,426\,713\,425\,029\,59$	$1.282\,466\,666\,666\,667$ $\pm$ $0.149\,152\,047\,700\,771\,9$	$0.726\,233\,333\,333\,333\,3$ $\pm$ $0.087\,231\,492\,784\,047\,52$
$G_{F}\rightarrow G_{S}$	$0.325\,733\,333\,333\,333\,3$ $\pm$ $0.698\,324\,661\,839\,558\,3$	$2.3333$ $\pm$ $0.412\,228\,092\,201\,392\,8$	$0.226\,933\,333\,333\,333\,3$ $\pm$ $0.141\,288\,121\,699\,360\,6$
$G_{S}\rightarrow G_{S}$	$0.8355$ $\pm$ $0.195\,928\,558\,408\,415\,8$	$1.954\,533\,333\,333\,333$ $\pm$ $0.767\,642\,060\,685\,404$	$0.402\,466\,666\,666\,666\,7$ $\pm$ $0.448\,994\,803\,236\,444\,3$
$G_{S}\rightarrow G_{F}$	$0.872\,266\,666\,666\,666\,7$ $\pm$ $0.270\,616\,579\,930\,597\,3$	$1.441\,533\,333\,333\,333$ $\pm$ $0.129\,756\,708\,240\,203\,7$	$0.673\,566\,666\,666\,666\,7$ $\pm$ $0.497\,105\,957\,853\,387$

Appendix

Table 12: Cross-graph transfer of MINERVA on PQL under a shared entity/relation vocabulary. Each checkpoint is tuned on the development split of its training KG and evaluated on both graph conditions without retuning.

G_{F}\rightarrow G_{S}

and

G_{S}\rightarrow G_{F}

measure expansion and contraction transfer, respectively.

Graph Construction

See all 15 papers

Theseus in the Graph: Towards Traceable Multi-Hop Graph Navigation
Sep 13, 2026Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar +2Multi-Hop QA Knowledge Graph Question Answering
National Yang Ming Chiao Tung University, Hsinchu, Taiwan · Independent Researcher
S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering
Mar 5, 2026Rong Fu, Yemin Wang, Tianxiang Xu +5Knowledge Graph Question Answering Multi-Hop QA
University of Macau · Xiamen University · Peking University +3
The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA
Sep 23, 2026Eduin E. Hernandez, Sergio A. Diaz, Luis F. Garcia +2Small Language Models Knowledge Graph Question Answering
NYCU, Taiwan · National Yang Ming Chiao Tung University (NYCU), Taiwan

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

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

Eduin E. Hernandez, Luis F. Garcia, Nurassyl Askar, Sergio A. Diaz+1

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

Multi-Hop QA Knowledge Graph Question Answering Multi-Hop Reasoning Knowledge Graphs CoT Faithfulness

Open paper AskPDF arXiv

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.

Abstract

Graph Construction

Explore similar work

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

S-Path-RAG: Semantic-Aware Shortest-Path Retrieval Augmented Generation for Multi-Hop Knowledge Graph Question Answering

The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA