GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

Probleemstelling

Agentic Knowledge Graph Question Answering (KGQA) vereist dat een agent iteratief interacteert met een kennisgrafiek (KG) om complexe vragen te beantwoorden. Bestaande methodes kampen echter met twee fundamentele beperkingen:

1. Schaarste aan trainingsdata: Er is een gebrek aan hoogwaardige, diverse trainingsdata die agents leren hoe ze autonoom door grote, ruisige KG's moeten navigeren.
2. Beperkte generalisatie: Prompting-methodes (zoals ToG, GoG) missen vaak specifieke parameterupdates voor robuuste navigatie, terwijl trainingsgebaseerde methodes vaak vastzitten aan vooraf gedefinieerde trajecten of subgrafieken. Dit leidt tot oppervlakkige patroonimitatie en een gebrek aan vermogen om fouten te herstellen of zich aan te passen aan ongeziene structuren (out-of-distribution).

De centrale vraag is: Hoe kan een agent een robuuste exploratiebasis opbouwen op KG's om de grenzen van zijn redeneercapaciteit te verleggen?

Methodologie: GraphWalker Framework

GraphWalker is een nieuw raamwerk dat deze uitdagingen aanpakt via Automated Trajectory Synthesis en een Stage-wise Fine-tuning (SFT) paradigma, gevolgd door een lichte Reinforcement Learning (RL) fase. Het systeem opereert op een globale KG (in plaats van vooraf geëxtraheerde subgrafieken) en gebruikt twee primitieve tools: get_relations en get_triples.

Het trainingsproces bestaat uit drie fasen:

1. Data Constructie: Twee Complementaire Corpora

De auteurs bouwen twee specifieke datasets om verschillende vaardigheden te trainen:

• GraphSynth-15k (Exploratie): Een corpus van 15.000 synthetische trajecten gegenereerd via Constrained Random Walks (CRW) op de KG. Deze paden omvatten diverse structuren (compositieketens van 2-5 hops en conjunctiegrafieken). Vragen worden automatisch gegenereerd en gefilterd op semantische coherentie. Dit corpus dient om een brede exploratie-prior te vestigen.
• GraphRoll-6k (Reflectie & Herstel): Een kleiner corpus van 6.000 hoogwaardige "expert" trajecten. Deze worden gegenereerd door een expert-model dat expliciete foutdetectie, reflectie op oninformatieve observaties en backtracking van doodlopende paden demonstreert. Dit leert de agent zelfcorrectie.

2. Twee-Fase SFT Training (Supervised Fine-Tuning)

• Fase 1 (GraphSynth): De agent wordt getraind op GraphSynth-15k. Het doel is het internaliseren van robuuste navigatiegedragingen en betrouwbare tool-gebruikspatronen onder realistische retrieval-ruis. De KG-resultaten worden hierbij behandeld als omgevingsobservaties.
• Fase 2 (GraphRoll): Het model wordt verder fijntuned op GraphRoll-6k. In tegenstelling tot Fase 1, focust deze fase op het ontwikkelen van bewuste interactiestrategieën, foutdetectie en het herstellen van redeneerfouten.

3. Reinforcement Learning (RL) Optimalisatie

Op basis van het twee-fase SFT-model wordt een lichte RL-fase toegepast (Group Relative Policy Optimization - GRPO) met een spare exact-match (EM) beloning. Omdat de twee SFT-fases al een sterke exploratie- en reflectie-prior hebben gelegd, is deze simpele beloning voldoende om het beleid verder te optimaliseren en de prestatieplafond te doorbreken zonder complexe tussentijdse supervisie.

Belangrijkste Bijdragen

1. Identificatie van Data Schaarste: Het paper identificeert training data schaarste als de belangrijkste bottleneck voor agentic KGQA en lost dit op met twee gesynthetiseerde datasets (GraphSynth en GraphRoll).
2. Stage-wise SFT Curriculum: Een innovatieve trainingsvolgorde waarbij eerst brede exploratie wordt aangeleerd, gevolgd door gespecialiseerde reflectie en foutherstel. Dit creëert een robuuste basis die essentieel is voor effectieve RL.
3. State-of-the-Art Prestaties: GraphWalker bereikt nieuwe topprestaties op de CWQ en WebQSP benchmarks en toont sterke generalisatie op out-of-distribution taken (GrailQA en GraphWalkerBench).

Resultaten

• Prestaties op Benchmarks: GraphWalker behaalt de beste resultaten (SOTA) op CWQ en WebQSP. Bijvoorbeeld, op CWQ scoort de 7B-versie 79.6% EM, wat een aanzienlijke verbetering is ten opzichte van bestaande methodes zoals KG-Agent (72.2%) en ToG (69.5%).
• Zero-Shot Generalisatie: Zelfs zonder training op WebQSP data, presteert GraphWalker uitzonderlijk goed op deze dataset (91.5% EM), wat aantoont dat het trainen op de complexe, diverse paden van CWQ leidt tot zeer overdraagbare exploratiestrategieën.
• Ablatie Studies:
  • Het verwijderen van GraphSynth (Fase 1) leidt tot een daling van ~5% in EM, wat het belang van brede exploratie bevestigt.
  • Het verwijderen van GraphRoll (Fase 2) leidt tot een daling van ~9% in EM, wat aantoont dat reflectie en foutherstel cruciaal zijn.
  • Het verwijderen van RL leidt tot een daling van ~10%, wat aantoont dat RL de SFT-capaciteiten consolideert.
  • Een "Mixed" training (alle data in één fase) presteert significant slechter dan de gestructureerde stage-wise aanpak, wat het belang van de trainingsvolgorde benadrukt.
• Pass@k Analyse: GraphWalker met de volledige pipeline toont een hogere Pass@k, wat betekent dat de agent in meer pogingen het juiste antwoord vindt, dankzij de uitgebreide zoekruimte die door GraphSynth is gecreëerd.

Significantie

GraphWalker biedt een oplossing voor het fundamentele probleem van data-schaarste en generalisatie in agentic KGQA. Door een synthetisch curriculum te gebruiken dat eerst exploratie en vervolgens reflectie leert, slaagt het erin om een agent te creëren die niet alleen beter presteert dan bestaande methodes, maar ook robuuster is tegenover ruis en ongeziene grafiekstructuren. De methode bewijst dat een goed ontworpen SFT-cursus een noodzakelijke voorwaarde is om de effectiviteit van Reinforcement Learning in complexe redeneertaken te maximaliseren. Dit opent de weg voor schaalbare, autonome redeneersystemen die werken op volledige, wereldwijde kennisgrafieken.