GraphDancer combines a graph-aware curriculum with multi-round reasoning, executable graph calls, and PPO updates from outcome and format rewards.
Introduction
Scholarly indexes, product catalogs and other knowledge sources contain heterogeneous graphs. Answering questions about them requires precise calls over typed relations and the ability to combine evidence across multiple steps.
GraphDancer trains language models to explore these graphs by alternating reasoning with executable graph calls. Its graph-aware curriculum organizes PPO training by the graph operations a question requires, moving from easier questions to harder ones while maintaining practice at every level.
We train Qwen2.5-3B-Instruct and Qwen3-14B on Academic and Biomedical graphs from GRBench. Evaluation covers held-out questions from these domains and unseen E-commerce, Literature and Legal graphs. Both trained models exceed Graph-CoT and Graph Counselor using the same backbone on ROUGE-L and GPTScore in all four evaluation settings.
Contributions
Learning graph interaction. PPO trains the policy to reason, execute graph functions, use returned observations and produce an answer, with rewards for answer correctness and valid interaction format.
Graph-aware curriculum. An operation-based hierarchy separates single-anchor access, composition and set-level selection. A moving Gaussian schedule shifts the training focus from easy to hard, while a positive-coverage mixture keeps all levels in practice.
Transfer across domains. Experiments with both 3B and 14B backbones test held-out in-domain questions, three unseen graphs and question types absent from training. Trajectory analyses examine protocol validity, evidence retrieval and correctness after retrieval.
Method
Reasoning with Graph Functions
Given a question and the graph schema, the policy reasons, calls a graph function and reads the returned observation. It repeats this process until it answers or reaches the interaction limit. The graph environment supplies four functions:
RetrieveNode[keyword]: find candidate nodes from a textual query.
NodeFeature[Node, feature]: read a named field of a node.
NeighbourCheck[Node, neighbor_type]: retrieve neighbors under a typed relation.
NodeDegree[Node, neighbor_type]: count neighbors under a typed relation.
PPO uses a learned critic and a terminal reward that prioritizes answer correctness, with additional credit for a valid interaction format. Environment observations are excluded from the policy and value losses.
Structural Difficulty
Questions are labeled by the graph operations needed by their templates, independently of the model's realized number of calls:
Easy — Single-anchor access: retrieve fields, neighbors or degree for one anchor.
Medium — Composition: combine multiple anchors or constraints.
Hard — Set-level selection: aggregate or rank an expanded set of candidates.
Easy-to-Hard Training with Continued Practice
A Gaussian distribution moves the sampling focus from Easy toward Hard as training progresses. It is mixed with a fixed distribution that assigns positive probability to every difficulty level. The mixture maintains practice across levels rather than relying only on the tails of the moving Gaussian.
Both backbones use the same partition, difficulty labels, reward and curriculum. Training runs for 200 PPO updates with 128 trajectories per update; checkpoints are selected on validation questions.
Experiments
Dataset and Evaluation
We train only on Academic and Biomedical graphs. Their 1,070-question pool is split 70:10:20 into 749 training, 107 validation and 214 held-out test questions. In-domain evaluation pools the two domains with equal weight per question.
The unseen-domain tests contain 200 E-commerce, 240 Literature and 180 Legal questions. Together with the held-out in-domain partition, they form 834 test questions. They include 70 OOD questions whose types are absent from training; these are evaluated separately from the operation-based Easy, Medium and Hard labels.
Baselines and Metrics
We compare GraphDancer with Graph-CoT and Graph Counselor using the original Qwen2.5-3B-Instruct or Qwen3-14B backbone. The paper also reports closed-source graph-agent baselines using GPT-4.1-mini and GPT-5-nano, and prior results for TextRAG, GraphRAG, Graph-MCTS and Graph-O1.
ROUGE-L (R-L) measures answer overlap; GPTScore (GS) uses the LLM-judge protocol from prior work. Scores are reported as percentages. The main-result AVG gives equal weight to four settings: pooled in-domain, E-commerce, Literature and Legal. It is neither an unseen-only average nor a mean pooled over all 834 questions.
Results
Main Results
ROUGE-L (R-L) and GPTScore (GS), averaged with equal weight over pooled in-domain, E-commerce, Literature, and Legal evaluation settings. Graph-CoT and Graph Counselor use the same backbones before GraphDancer training.
Equal-weight average over four evaluation settings (%, Tables 2 and 9)
Backbone
Method
AVG R-L
AVG GS
Qwen2.5-3B-Instruct
Graph-CoT
36.22
39.28
Qwen2.5-3B-Instruct
Graph Counselor
31.74
35.15
Qwen2.5-3B-Instruct
GraphDancer
45.02
48.59
Qwen3-14B
Graph-CoT
48.54
52.71
Qwen3-14B
Graph Counselor
40.72
45.40
Qwen3-14B
GraphDancer
55.96
58.64
With either Qwen backbone, GraphDancer scores above both same-backbone baselines on both metrics in every evaluation setting. At 14B, its average across the three unseen domains also exceeds the reported graph-agent baselines powered by GPT-4.1-mini and GPT-5-nano; this does not imply a win in every individual column. See the paper for full domain-level results.
Curriculum Analysis
Holding the 3B backbone, PPO optimizer, reward and interaction protocol fixed, curriculum sampling raises the four-setting average ROUGE-L from 42.07 with Vanilla PPO (uniform sampling) to 45.02 with GraphDancer, a gain of 2.95 points. The paper also compares static mixtures, hard-to-easy ordering, faster pacing and pure easy-to-hard sampling.
Graph-Interaction Outcomes
Outcomes over all 834 test questions. Episodes are assigned in order to correct answer, unfinished at the interaction limit, invalid protocol, or other wrong. Graph-CoT uses the backbone before GraphDancer training; Vanilla PPO uses uniform sampling and GraphDancer uses curriculum sampling.
At 3B, GraphDancer answers 334 of 834 questions correctly, compared with 261 for Graph-CoT and 309 for Vanilla PPO. Invalid-protocol outcomes fall to 46, versus 229 and 179, respectively. At 14B, correct answers rise from 370 for Graph-CoT to 426 for GraphDancer, while invalid-protocol outcomes fall from 160 to 59.
These counts and the stacked-bar percentages pool all 834 episodes. They use a different aggregation from the four-setting AVG above. Categories are mutually exclusive: correct, unfinished at the limit, invalid protocol, then other wrong.
Evidence-Grounded Accuracy
Evidence hit (EH) checks whether the normalized gold answer occurs in a returned tool observation. P(EM | EH) measures strict exact-match accuracy after such a hit. Both quantities are higher for GraphDancer than for the same-backbone Graph-CoT and Graph Counselor baselines.
Evidence-grounded accuracy pooled over 834 questions (%, Table 6)
Backbone
Method
EH
P(EM | EH)
EM
Qwen2.5-3B-Instruct
Graph-CoT
47.12
61.58
31.29
Qwen2.5-3B-Instruct
Graph Counselor
48.68
48.52
24.58
Qwen2.5-3B-Instruct
GraphDancer
53.36
70.11
40.05
Qwen3-14B
Graph-CoT
60.31
69.98
44.36
Qwen3-14B
Graph Counselor
58.39
60.57
38.61
Qwen3-14B
GraphDancer
63.91
74.67
51.08
EH is a lexical diagnostic, not a guarantee that an answer used valid supporting evidence. The full paper also reports joint correctness-and-hit rates and accuracy after a miss.
Conclusion
GraphDancer combines PPO with a curriculum matched to the graph operations a question requires. Training on Academic and Biomedical graphs improves reasoning and graph interaction on held-out questions and three unseen domains with both 3B and 14B backbones.
The curriculum combines progression toward harder questions with continued practice across levels. The results and trajectory analyses show improvements in answer quality, protocol validity and the retrieval of answer-bearing information.
Additional Analysis
The v3 paper and appendix include difficulty-wise results, unseen question types, search behavior and complete case-study trajectories. The Easy, Medium and Hard labels describe required graph operations; OOD question types are assessed separately.
BibTeX
@misc{bai2026graphdancertrainingllmsexplore,
title={GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning},
author={Yuyang Bai and Zhuofeng Li and Ping Nie and Jianwen Xie and Yu Wang and Yu Zhang},
year={2026},
eprint={2602.02518},
archivePrefix={arXiv},
primaryClass={cs.LG},
url={https://arxiv.org/abs/2602.02518},
}
GraphDancer: Training LLMs to Explore and Reason over Graphs via Curriculum Reinforcement Learning
