GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

1. Problemstellung

Das Paper adressiert die Herausforderungen beim Agenten-basierten Knowledge Graph Question Answering (KGQA). Bei dieser Aufgabe muss ein Agent iterativ mit einem globalen Knowledge Graph (KG) interagieren, um komplexe Fragen zu beantworten. Bisherige Ansätze leiden unter zwei Hauptproblemen:

• Mangel an Trainingsdaten: Es gibt einen Mangel an hochwertigen, strukturierten Trainingsdaten, die das autonome Navigieren durch große, verrauschte KGs lehren.
• Eingeschränkte Generalisierungsfähigkeit:
  • Prompting-basierte Methoden (z. B. ToG, GoG) nutzen oft starre Workflows und fehlt es an parametrischem Lernen für robustes Navigieren.
  • Training-basierte Methoden beschränken sich häufig auf vordefinierte Trajektorien oder vorab extrahierte Subgraphen, was die Fähigkeit des Agents einschränkt, eigenständig neue Pfade zu erkunden.
  • Reinforcement Learning (RL) allein ist oft ineffektiv, wenn der Agent keine ausreichende „Explorations-Basis" (SFT-Prior) besitzt, um belohnende Trajektorien zu finden.

2. Methodik: GraphWalker Framework

GraphWalker ist ein neues Framework, das diese Lücken durch Automatisierte Trajektorien-Synthese und ein Stufenweises Fine-Tuning (Stage-wise Fine-tuning) schließt. Der Ansatz besteht aus drei Hauptkomponenten:

A. Agentic Umgebung

Der Agent interagiert direkt mit dem globalen KG (Freebase) über einen SPARQL-Endpunkt, nicht nur mit vordefinierten Subgraphen. Er verfügt über zwei primitive Tools:

1. get_relations(e): Gibt alle Relationen einer Entität zurück (zur Erkundung des Nachbarschaftsraums).
2. get_triples(e, R'): Gibt Tripel zurück, die eine bestimmte Teilmenge von Relationen betreffen.

B. Datenkonstruktion (Synthetisches Curriculum)

Das Kernstück ist die Erstellung zweier komplementärer Datensätze:

1. GraphSynth-15k (Exploration):
   • Methode: Nutzung von Constrained Random Walks (CRW) auf dem KG, um strukturell diverse Pfade (2–5 Hops, Konjunktionen) zu generieren.
   • Synthese: Für jeden Pfad werden natürliche Fragen generiert (unter Maskierung intermediärer Entitäten), um Informationslecks zu vermeiden.
   • Ziel: Schaffung eines breiten „Explorations-Priors", damit der Agent lernt, sich in komplexen, verrauschten Graphstrukturen zurechtzufinden.
2. GraphRoll-6k (Reflexion & Fehlerkorrektur):
   • Methode: Sammlung von „Experten-Trajektorien" durch ein großes LLM (GPT-4o-mini), das Fragen löst und dabei explizit Fehler erkennt, zurückverfolgt (Backtracking) und sich korrigiert.
   • Filterung: Nur Trajektorien mit korrekter Antwort (Exact Match) und vollständiger Begründung durch KG-Evidenz werden behalten.
   • Ziel: Vermittlung von Fähigkeiten zur Selbstkorrektur und Reflexion bei falschen Pfaden.

C. Trainingsparadigma (Stufenweises Fine-Tuning + RL)

GraphWalker verwendet ein dreistufiges Training:

1. SFT Stage 1 (GraphSynth): Der Agent lernt robustes Navigieren und Tool-Nutzung auf den 15k synthetischen Trajektorien. Dies etabliert die Basis für die Erkundung des Suchraums.
2. SFT Stage 2 (GraphRoll): Der Agent wird auf den 6k Experten-Trajektorien feinabgestimmt, um Reflexionsfähigkeiten und Fehlerkorrektur zu erlernen.
3. RL Optimization (GRPO): Auf Basis des zweistufigen SFT-Modells wird Reinforcement Learning mit Group Relative Policy Optimization (GRPO) angewendet.
   • Belohnung: Ein spärlicher Reward (Exact Match = 1, sonst 0).
   • Vorteil: Da das SFT bereits eine starke Explorationsbasis geschaffen hat, reicht der spärliche Reward aus, um die Leistung über das SFT-Limit hinaus zu heben, ohne dichte Zwischen-Belohnungen zu benötigen.

3. Schlüsselbeiträge

• Identifikation des Engpasses: Das Paper identifiziert die Knappheit an Trainingsdaten für die Exploration als Hauptbottleneck für die Generalisierung von KGQA-Agenten.
• Neue Datensätze: Einführung von GraphSynth (15k strukturell diverse, synthetische Trajektorien) und GraphRoll (6k kuratierte Experten-Trajektorien mit Fehlerkorrektur).
• Zweistufiges SFT-Paradigma: Ein neuartiger Trainingsansatz, der erst eine breite Explorationsfähigkeit aufbaut und dann Reflexionsfähigkeiten hinzufügt. Dies dient als „Scaffold" für nachfolgendes RL.
• State-of-the-Art Performance: Demonstration, dass dieses Curriculum es ermöglicht, leichte Modelle (z. B. 3B/7B Parameter) so zu trainieren, dass sie proprietäre Modelle (wie GPT-4o) übertreffen.

4. Ergebnisse

Die Evaluation erfolgte auf den Benchmarks CWQ (Complex WebQuestions), WebQSP und GrailQA, sowie einem neu erstellten GraphWalkerBench.

• Leistungsfähigkeit: GraphWalker erreicht auf CWQ und WebQSP State-of-the-Art (SOTA) Ergebnisse.
  • Beispiel CWQ: GraphWalker-7B-SFT-RL erreicht 79,6% EM (Exact Match), was deutlich über dem vorherigen SOTA (z. B. KG-Agent mit 72,2% oder GoG mit 75,2%) liegt.
  • Selbst mit einem 3B-Modell (Qwen2.5-3B) übertrifft GraphWalker größere Baselines.
• Zero-Shot Generalisierung: Das Modell zeigt starke Zero-Shot-Leistung auf GrailQA (86,3% EM) und dem neuartigen GraphWalkerBench, was beweist, dass es auf ungesehene Graph-Strukturen generalisiert.
• Ablationsstudien:
  • Das Entfernen von Stage 1 (GraphSynth) führt zu einem signifikanten Rückgang der Generalisierung (−6,8% EM), was die Wichtigkeit der strukturellen Vielfalt für den Suchraum unterstreicht.
  • Das Entfernen von Stage 2 (GraphRoll) führt zu einem starken Abfall (−11,1% EM), was die Notwendigkeit von Reflexions- und Korrekturfähigkeiten zeigt.
  • Eine gemischte SFT-Phase (ohne Stufen) performt schlechter als die stufenweise Reihenfolge, was die Bedeutung des Curriculums bestätigt.

5. Bedeutung und Fazit

GraphWalker löst das Problem der Datenknappheit und der eingeschränkten Generalisierung im agentic KGQA durch eine innovative Kombination aus synthetischer Datengenerierung und einem gestuften Trainingsansatz.

• Technische Implikation: Es zeigt, dass RL für komplexe Reasoning-Aufgaben effektiver ist, wenn es auf einem starken SFT-Prior aufbaut, der durch synthetische, diverse Daten geschaffen wurde.
• Skalierbarkeit: Der Ansatz ermöglicht es, auch kleinere, open-source Modelle (3B–8B Parameter) so zu trainieren, dass sie komplexe Reasoning-Aufgaben auf globalen Knowledge Graphen besser lösen als große, proprietäre Modelle ohne spezifisches Training.
• Zukunftsperspektive: Das Framework bietet einen neuen Weg, um Agenten robustes Navigationsverhalten und Fehlerkorrektur beizubringen, was für autonome Systeme in komplexen Wissensumgebungen essenziell ist.

Der Code ist öffentlich verfügbar, was die Reproduzierbarkeit und Weiterentwicklung des Ansatzes fördert.