GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

Shuwen Xu; Yao Xu; Jiaxiang Liu; Chenhao Yuan; Wenshuo Peng; Jun Zhao; Kang Liu

cs.CLMar 30, 2026

GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

Authors: Shuwen Xu, Yao Xu, Jiaxiang Liu, Chenhao Yuan, Wenshuo Peng, Jun Zhao, Kang Liu

Organizations: School of Artificial Intelligence, University of Chinese Academy of Sciences · The Key Laboratory of Cognition and Decision Intelligence for Complex Systems, Institute of Automation, Chinese Academy of Sciences · Department of Electronic Engineering, Tsinghua University

Abstract

Agentic knowledge graph question answering (KGQA) requires an agent to iteratively interact with knowledge graphs (KGs), posing challenges in both training data scarcity and reasoning generalization. Specifically, existing approaches often restrict agent exploration: prompting-based methods lack autonomous navigation training, while current training pipelines usually confine reasoning to predefined trajectories. To this end, this paper proposes GraphWalker, a novel agentic KGQA framework that addresses these challenges through Automated Trajectory Synthesis and Stage-wise Fine-tuning. GraphWalker adopts a two-stage SFT training paradigm: First, the agent is trained on structurally diverse trajectories synthesized from constrained random-walk paths, establishing a broad exploration prior over the KG; Second, the agent is further fine-tuned on a small set of expert trajectories to develop reflection and error recovery capabilities. Extensive experiments demonstrate that our stage-wise SFT paradigm unlocks a higher performance ceiling for a lightweight reinforcement learning (RL) stage, enabling GraphWalker to achieve state-of-the-art performance on CWQ and WebQSP. Additional results on GrailQA and our constructed GraphWalkerBench confirm that GraphWalker enhances generalization to out-of-distribution reasoning paths. The code is publicly available at https://github.com/XuShuwenn/GraphWalker.

Figures & tables

Figure 1: Comparison of three KGQA paradigms.

Type	Method	Global KG	Autonomous Interaction	RL Optimization
Prompting	ToG ( Sun et al., 2024 )	✓	✓	✗
Prompting	GoG ( Xu et al., 2024 )	✓	✓	✗
Training	RoG ( Luo et al., 2024b )	✗	✗	✗
	KBQA-o1 ( Luo et al., 2025 )	✓	✓	✗
	KG-Agent ( Jiang et al., 2025 )	✓	✓	✗
	KG-R1 ( Song et al., 2025 )	✗	✓	✓

Table 1: Comparison of GraphWalker with existing agentic KGQA methods across three key properties: Global KG (operating on global KGs rather than pre-extracted subgraphs), Autonomous Interaction (interacting autonomously rather than via pre-defined workflows), and RL Optimization (incorporating reinforcement learning to optimize reasoning policies).

Figure 2: Overview of our proposed GraphWalker. (a) Data Construction: a multi-phase pipeline for GraphSynth-15k and outcome-based rejection sampling for GraphRoll-6k. (b) Two-Stage SFT: Stage 1 establishes a broad exploration prior, while Stage 2 instills reflection and error recovery. (c) RL Optimization: GRPO with a simple exact-match reward unlocks a higher performance ceiling enabled by the two-stage SFT prior.

Figure 3: Representative interaction paths generated by constrained random walks.

Method	Backbone	CWQ		WebQSP
Method	Backbone	EM	F1	EM	F1
Vanilla LLMs
IO Prompt	Qwen2.5-3B-Instruct	22.0	17.7	44.6	30.3
IO Prompt	Qwen2.5-7B-Instruct	25.7	20.7	50.9	33.2
IO Prompt	GPT-4o-mini	45.5	33.6	47.1	39.3
IO Prompt	DeepSeek-V3.2	50.1	43.5	63.8	55.7

Table 2: Performance comparison (in percentage) of KGQA methods on CWQ and WebQSP. The best and second-best results are shown in bold and underlined , respectively. † denotes models evaluated under the GraphWalker interaction framework with full global KG.

Figure 4: Pass@

k

comparison.

Table 7

Panel of Figure 5 — Figure 5: Behavioral comparison between GraphWalker and GraphWalker w/o RL across all benchmarks. Each axis is independently scaled to highlight per-benchmark differences. Fine-grained per-reasoning-type EM analysis is shown in Appendix E.1 .

Figure 6: Ablation study on the quality filter .

Figure 7: Impact of data scale on performance. Left : scaling GraphSynth data improves EM and Retrieval Rate . Right : scaling GraphRoll data improves EM and Recovery Rate .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Threshold	Overall	CWQ	WebQSP	GrailQA
0.80	25.97% (3960)	23.30% (3553)	5.27% (804)	2.67% (407)
0.85	2.57% (392)	2.13% (325)	0.56% (85)	0.09% (13)
0.90	0.15% (23)	0.12% (18)	0.03% (4)	0.01% (1)

Appendix

Table 5: Contamination rates at three similarity thresholds (BGE-M3).

Panel of Figure 8 — Figure 8: Data contamination analysis between GraphSynth and downstream benchmarks.

Structure Type	Composition				Conjunction	Total
Structure Type	2-hop	3-hop	4-hop	5-hop	2I	Total
Count	1,982	4,920	1,778	576	5,599	14,855
Ratio (%)	13.34	33.12	11.97	3.88	37.69	100.00

Appendix

Table 6: Structure distribution of the GraphSynth-15k dataset.

Figure 9: t-SNE visualization of GraphSynth, CWQ, and WebQSP question embeddings, illustrating the broad semantic coverage of the synthesized corpus.

Dataset	API Calls	Input Tokens	Output Tokens	Cost
GraphSynth	6.673	11,533.56	796.53	$0.0110
GraphRoll	5.680	9,296.93	553.87	$0.0086

Appendix

Table 7: Average per-sample API usage and cost for GraphSynth and GraphRoll data construction.

Structure Type	Composition			Conjunction			Total
Structure Type	3-hop	4-hop	5-hop	2I	IP	PI	Total
Count	347	209	180	344	337	349	1766

Appendix

Table 8: Structure distribution of GraphWalkerBench.

Type	Annotated path(s)	Question
2I	(1) Korean War $\rightarrow$ films $\rightarrow$ MASH; (2) Ring Lardner, Jr. $\rightarrow$ writer.film $\rightarrow$ MASH	What film about the Korean War was written by Ring Lardner, Jr.?
PI	(1) Czech Republic $\rightarrow$ Central Europe $\rightarrow$ Europe; (2) Continental Celtic languages $\rightarrow$ geographic distribution $\rightarrow$ Europe	What continent that includes the Czech Republic is also the geographic home of the Continental Celtic languages?
4-hop	Classic rock $\rightarrow$ Rock music $\rightarrow$ Rock and Roll Hall of Fame $\rightarrow$ I. M. Pei $\rightarrow$ Pei Cobb Freed & Partners	What architectural firm was a partner of the architect who designed a hall of fame for a parent genre of classic rock?
5-hop	Rotokas Language $\rightarrow$ Papuan languages $\rightarrow$ New Guinea $\rightarrow$ Malay Archipelago $\rightarrow$ Lost Continent $\rightarrow$ Angelo Francesco Lavagnino	Who composed the music for a film about the island group home to the Rotokas language family?

Appendix

Table 9: Representative manually audited examples from GraphWalkerBench.

Panel of Figure 10 — Figure 10: Fine-grained EM performance on GraphWalkerBench across question types and ablation variants. Left : grouped bar chart. Right : heatmap. IP and PI are unseen conjunction structures not present in GraphSynth training data.

Figure 11: Fine-grained effect of RL across GraphWalkerBench reasoning structures. Each axis is independently scaled.

Method	CWQ		WebQSP
	EM	F1	EM	F1
w/ Reranking Top-20	79.6	74.2	91.5	88.6
Ablations
w/ Reranking Top-10	78.4	73.5	89.4	86.1
w/ Reranking Top-15	78.7	74.6	89.8	86.5
w/ Reranking Top-30	76.9	72.0	87.0	84.4

Appendix

Table 10: LLM-based Relation Reranking Ablation Study. The best and second-best results are shown in bold and underlined , respectively.

Question: Where is the home stadium of the team who won the 1946 World Series championship?

Initial Entities: 1946 World Series

<think> Since I need to determine the home stadium of the team that won the 1946 World Series, I will start by querying the relations for the entity "1946 World Series". This will help me identify relevant connections to the winning team and its stadium. Gathering these relations is essential for finding the necessary information to answer the question. </think>

<kg-query> get_relations("1946 World Series") </kg-query>

<information> sports.sports_championship_event.champion, sports.sports_championship_event.result, sports.sports_team.championships, time.event.locations, … </information>

<think> The relations obtained for "1946 World Series" include "sports.sports_championship_event.champion," which is crucial for identifying the winning team, and "time.event.locations," which may provide information about the home stadium. By querying the triples with these relations, I can gather detailed information about the champion team and its associated stadium, which is necessary to answer the question accurately. </think>

<kg-query> get_triples("1946 World Series", ["sports.sports_championship_event.champion", "sports.sports_championship_event.result", "sports.sports_team.championships", "time.event.locations", …]) </kg-query>

Appendix

Table 21

Question: Where is the home stadium of the team who won the 1946 World Series championship?

Initial Entities: 1946 World Series

<think> To find the home stadium of the team that won the 1946 World Series championship, I will start by querying the relations of the entity "1946 World Series". This should provide information about the winning team and potentially its home stadium. After retrieving the relations, I will look for relevant details regarding the championship and the winning team. </think>

<kg-query> get_relations("1946 World Series") </kg-query>

<information> sports.sports_championship_event.champion, sports.sports_championship_event.result, sports.sports_team.championships, time.event.locations, … </information>

<think> The relations retrieved for the "1946 World Series" include information about the champion, result, championships associated with the team, locations, start date, end date, and runner-up. To find the home stadium of the winning team, I will focus on the "champion" relation first, as it should indicate which team won the championship. Once I identify the champion, I can then look for its home stadium. I will proceed to retrieve the triples for the "1946 World Series" using the top relevant relations. </think>

Appendix

Table 22

Question: Where is the home stadium of the team who won the 1946 World Series championship?

Initial Entities: 1946 World Series

<think> To find the home stadium of the team that won the 1946 World Series championship, I will start by querying the relations of the "1946 World Series" entity. This should provide information about the winning team and potentially lead to details about their home stadium. </think>

<kg-query> get_relations("1946 World Series") </kg-query>

<information> sports.sports_championship_event.champion, sports.sports_championship_event.result, sports.sports_championship_event.runner_up, … </information>

<think> The relations returned for the "1946 World Series" include several relevant ones, particularly "champion," which likely indicates the winning team. I will also consider "runner_up" as it may provide context about the teams involved. To gather more detailed information, I will query the triples for the "1946 World Series" using these relations. </think>

<kg-query> get_triples("1946 World Series", ["sports.sports_championship_event.champion", "sports.sports_championship_event.runner_up", "sports.sports_championship_event.result"]) </kg-query>

Appendix

Table 23

Parameter	Value
SFT settings
Batch size	32
Learning Rate	1e-5
Max Response Length	4096
Epoch	2
RL settings

Appendix

Table 14: Key parameters during the training process.

Knowledge Graph Question Answering

Knowledge Graph Question Answering answers natural-language questions by finding and reasoning over entities and relations in structured knowledge graphs.

See all 164 papers

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning
Jul 20, 2026Jia Ao Sun, Hao Yu, Fengran Mo +4LLM Reasoning with Graphs RL for Language Model Reasoning
Université de Montréal · Mila – Québec AI Institute · McGill University +2
RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering
Mar 20, 2026Bo Yuan, Hexuan Deng, Xuebo Liu +1Knowledge Graph Question Answering LLM Reasoning with Graphs
Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen, China · Zhongguancun Academy, Beijing, China
GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation
Apr 2, 2026Taraneh Ghandi, Hamidreza Mahyar, Shachar KlaimanLLM Reasoning with Graphs LLM Tool Use
Faculty of Science, McMaster University · BASF Digital Solutions

Jul 20, 2026J/K move · Enter open · S save

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

Jia Ao Sun, Hao Yu, Fengran Mo, Zhan Su+3

Université de Montréal · Mila – Québec AI Institute · McGill University+2

LLM Reasoning with Graphs RL for Language Model Reasoning Graph-Based Retrieval LLM Tool Use Knowledge Graph Question Answering

Open paper AskPDF arXiv

Knowledge graph question answering (KGQA) requires navigating from topic entities to an answer several relations away. Recent methods prompt a frontier LLM to explore the graph through a retrieval tool, but their reliance on frontier-scale inference makes them costly to deploy. We present Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL). Our central idea is to scaffold a frontier teacher with each question's gold SPARQL query, so the teacher traverses a known answer-bearing path with a live Search tool rather than having to discover the path itself. Since every call executes against a live Freebase server, the resulting trajectories are grounded in the knowledge graph by construction. On WebQSP, CWQ, and GrailQA, \sogrone{} at 8B surpasses every frozen frontier-LLM system in our comparison and posts the strongest results on CWQ of any system we compare against. It does so using no auxiliary module at inference and no LLM judge during training. Isolating each training stage shows that SFT and RL contribute complementary gains, our approach transfers across model families, and RL learns to reach answers in fewer Search calls than its SFT initialization.

Abstract

Knowledge Graph Question Answering

Explore similar work

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering

GraphWalk: Enabling Reasoning in Large Language Models through Tool-Based Graph Navigation