GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

1. Problem Statement

Agentic Knowledge Graph Question Answering (KGQA) aims to enable Large Language Models (LLMs) to iteratively interact with global Knowledge Graphs (KGs) to answer complex questions. While traditional methods (Information Retrieval and Semantic Parsing) are limited by static scopes, existing agentic approaches face two critical bottlenecks:

1. Training Data Scarcity: High-quality, diverse interaction trajectories for training agents are scarce. Most methods rely on prompting (lacking parameter updates for robust navigation) or training on predefined, narrow trajectories that fail to generalize.
2. Reasoning Generalization: Current training pipelines often confine reasoning to predefined workflows or pre-extracted subgraphs. Agents struggle with "out-of-distribution" (OOD) reasoning paths, noisy KG environments, and long-tail entity distributions. Furthermore, Reinforcement Learning (RL) optimization often fails without a strong Supervised Fine-Tuning (SFT) prior that establishes a robust exploration capability.

2. Methodology: GraphWalker Framework

GraphWalker proposes a novel framework that addresses these issues through Automated Trajectory Synthesis and a Stage-wise Fine-tuning paradigm, followed by lightweight RL.

A. Agentic Environment

The agent interacts directly with a global KG (Freebase) via a SPARQL endpoint, rather than pre-extracted subgraphs. It utilizes two primitive tools:

• get_relations(e): Retrieves all relations connected to an entity.
• get_triples(e, R'): Retrieves specific triples based on a subset of relations.
  The agent operates in a loop: observe state $\to$ reason (Chain-of-Thought) $\to$ execute action (query or answer) $\to$ receive observation.

B. Data Construction Pipeline

The framework constructs two complementary datasets to support a two-stage curriculum:

1. GraphSynth-15k (Exploration Prior):

   • Goal: Establish a broad exploration prior over diverse KG structures.
   • Method: Uses Constrained Random Walks (CRW) on the KG to generate 15k structurally diverse reasoning paths (including multi-hop chains and conjunction graphs).
   • Synthesis: An LLM generates natural language questions for these paths (masking intermediate entities to prevent leakage) and simulates environment feedback.
   • Filtering: A semantic filter (GPT-4o-mini) ensures question-path relevance and coherence.

2. GraphRoll-6k (Reflection & Recovery):

   • Goal: Equip the agent with error detection, reflection, and recovery capabilities.
   • Method: A curated set of 6k "expert" trajectories derived from complex questions.
   • Selection: Uses outcome-based rejection sampling. Trajectories are only kept if the agent successfully corrects errors (backtracking from dead ends) and the final answer is factually grounded in the retrieved observations (Exact Match = 1).

C. Training Paradigm

GraphWalker employs a Three-Stage Training Pipeline:

1. Stage 1 (SFT on GraphSynth): The agent is trained on the diverse 15k trajectories to learn robust navigation, tool invocation, and broad exploration strategies under realistic retrieval noise.
2. Stage 2 (SFT on GraphRoll): The model is fine-tuned on the 6k expert trajectories to learn reflection (identifying uninformative observations) and error recovery (backtracking and correcting course).
3. RL Stage (GRPO): A lightweight Reinforcement Learning phase using Group Relative Policy Optimization (GRPO). It uses a sparse, trajectory-level Exact Match (EM) reward. Crucially, the two-stage SFT provides a strong "exploration prior," allowing the sparse RL reward to effectively push the policy beyond the SFT performance ceiling without needing dense intermediate supervision.

3. Key Contributions

• Identification of Data Scarcity: The paper identifies the lack of diverse, high-quality agentic trajectories as the primary bottleneck for KGQA generalization.
• Synthetic Curriculum (GraphSynth & GraphRoll): Introduction of two datasets: a large-scale, structurally diverse corpus for exploration (15k) and a smaller, high-quality corpus for reflection (6k).
• Stage-wise SFT + RL: A novel training curriculum where Stage 1 builds exploration breadth, Stage 2 instills self-correction, and RL optimizes the policy. This order is critical; mixing data or skipping stages significantly degrades performance.
• State-of-the-Art Performance: The framework achieves SOTA results on standard benchmarks while demonstrating strong zero-shot generalization to unseen reasoning structures.

4. Experimental Results

Experiments were conducted on CWQ (Complex WebQuestions) and WebQSP, with zero-shot evaluations on GrailQA and a new benchmark, GraphWalkerBench.

• Performance: GraphWalker (using a 7B backbone) achieves 79.6% EM on CWQ and 91.5% EM on WebQSP, outperforming previous prompting methods (e.g., ToG, GoG) and training-based baselines (e.g., KG-Agent, KBQA-o1).
• Comparison with Proprietary Models: Even when using strong proprietary models (GPT-4o-mini, DeepSeek-V3.2) as the backbone, GraphWalker's training framework significantly outperforms their zero-shot "IO Prompt" counterparts.
• Generalization:
  • Zero-Shot: Achieves 86.3% EM on GrailQA (zero-shot split) and 63.5% EM on GraphWalkerBench (unseen structures), proving the agent can handle reasoning paths not seen during training.
  • Ablation Studies: Removing Stage 1 (GraphSynth) drops performance by ~5% EM, confirming its role in exploration. Removing Stage 2 (GraphRoll) drops performance by ~9% EM, confirming its role in error recovery. Removing RL drops performance by ~10% EM, showing the value of policy optimization.
• Pass@k Analysis: GraphWalker demonstrates significantly higher Pass@k scores, indicating a much larger effective search space compared to models trained without the synthetic curriculum.

5. Significance

• Scalability: The approach demonstrates that high-quality agentic KGQA can be achieved without massive human annotation, relying instead on automated trajectory synthesis and curriculum learning.
• Robustness: By training on the global KG rather than subgraphs, GraphWalker is more robust to the noise and long-tail distributions of real-world knowledge bases.
• RL Efficiency: The paper provides empirical evidence that a well-structured SFT curriculum (exploration + reflection) is a prerequisite for sparse-reward RL to be effective in complex reasoning tasks, solving the "cold start" problem for agentic RL.
• Generalization: The framework successfully bridges the gap between training data and unseen reasoning topologies, making it a promising direction for autonomous agents in complex, structured environments.

The code and datasets are publicly available, facilitating further research in agentic reasoning over knowledge graphs.