Reasoning over text-attributed graphs (TAGs) requires large language models (LLMs) to combine a node's text with evidence distributed across its neighbourhood. Existing methods fix the set of accessible neighbours before generation, forcing reasoning to operate over a static context and preventing the model from acquiring missing evidence during inference. We argue that neighbour selection should itself be part of the reasoning process. To this end, we propose Call Neighbours Yourself (CNY), a framework that enables LLMs to proactively explore graph neighbourhoods through topology-constrained graph-walk actions. Instead of reasoning over a pre-selected neighbour set, CNY exposes lightweight neighbour previews and learns when to expand candidate neighbours for additional evidence. To address the delayed-credit challenge of neighbour exploration, we introduce destination-conditioned on-policy self-distillation, which retrospectively evaluates a selected neighbour after its content is revealed and converts the resulting change in action preference into an action-level training signal. Experiments on standard TAG reasoning benchmarks under a unified raw-text setting show that CNY consistently outperforms fixed-context post-training baselines. Furthermore, the learned exploration policy transfers to unseen graphs and to a graph-level task not encountered during training. Code is available at https://github.com/superallen13/CNY.
Figures & tables
Figure 1: CNY at a glance. (a) On WikiCS targets whose full neighbourhood fits in a 32 K context, a frozen Qwen2.5-32B that selects neighbours during generation ( Walk ) outperforms a retrieval-augmented generation pipeline ( RAG ) that embeds the target’s text, retrieves its top- 10 neighbours and concatenates them as context, at 6.3× fewer tokens. (b) CNY learns this selection as a graph-walk action, replacing the fixed pre-selected neighbour context of prior work.
Figure 2: CNY graph walk trajectories and OPSD credit. (A) The LLM emits a <thinking> span and a <walk> X </walk> action; the environment returns destination text and expands the frontier. The credit applies only to the node-ID tokens of successful walks. (B) OPSD replays the walk under πθ as a destination-blind student and a recap-conditioned teacher; their per-token reverse KL shifts the GRPO advantage at walk tokens (red box).
Node-level
Edge-level
Graph-level
Task
Cora
WikiCS
Products
FB15K237
Expla-Graph
7-way
2-way
10-way
5-way
10-way
5-way
10-way
Llama2-7B
47.92
73.45
40.10
58.77
58.71
64.33
48.32
57.76
Mistral-7B
60.54
88.39
63.63
71.90
70.16
74.94
62.48
68.77
OFA (7B)
28.65
56.92
21.20
35.15
30.43
39.31
–
51.36
UniGraph (7B)
69.53
89.74
43.45
60.23
66.07
75.73
–
–
Table 1: Zero-shot accuracy (%, ↑ ). LLM and graph-foundation rows are from Graph-R1 Wu et al. (2025b) ; Graph-R1 is re-evaluated under the protocol of § 5.1 . Bold : best; underline : second-best. CNY’s lead over the runner-up reasoner is significant at p≤0.05 (paired t -test on per-instance correctness, Bonferroni-corrected).
Settings
Hits@ 1
CNY-14B, walk ( Tmax=5 )
58.4
CNY-14B, full 1-hop context
49.0
CNY-14B, question only (no graph)
44.0
CNY-14B, direct from previews
38.5
Table 3: Zero-shot multi-hop KGQA on WebQSP. One frozen checkpoint, no question-answering training; all variants share subgraphs, prompts and scoring.
Figure 3: Effectiveness of OPSD (CNY-7B). (a) Held-out accuracy (mean of WikiCS and Cora) over training for β=0.03 vs. the β=0 GRPO ablation. (b) OPSD walk-action reverse-KL signal −δt on walk-action tokens; band: 1 st– 99 th percentile, line: mean.
OPSD coefficient β
Dataset
0 (GRPO)
0.005
0.01
0.02
0.03
WikiCS
69.5
72.7
73.0
74.2
75.1
Cora
58.5
60.0
62.5
62.0
65.5
Table 4: β -sweep, held-out accuracy (Qwen3-4B-Instruct-2507). β=0 is the GRPO ablation. Bold : best per row.
Frozen checkpoint
mean ∣δ∣
frac δ>0
mean ∣βδ∣
Qwen3-4B (sweep)
0.45
79%
0.013
Qwen2.5-7B
0.56
77%
0.017
Qwen2.5-14B (main)
0.91
89%
0.027
Table 5: The OPSD signal across backbone scales , in nats over the <walk> id tokens (Cora, N=536 per backbone). The credit strengthens with capacity while β=0.03 keeps its per-token magnitude well below reward scale.
Full
Rescaled
Removed
WikiCS
79.2±1.2
79.2±0.8
–
Cora
61.9±1.3
62.9±1.4
–
Walk attempts/rollout
2.3
2.0
2.3→13.7
Budget-exhaust.
0%
0.4%
0.4→75%
Answer rate
100%
98%
99.6→25%
Table 6: Component-wise reward ablation (Qwen3-4B, n=200 held-out, matched data and rollouts). Tiers: 1.0/0.6/0.3/0.2/0.1 (Full, Eq. 3 ), order-preserving 1.0/0.5/0.25/0.15/0.05 (Rescaled), 1.0/0.6/0/0/0.1 (Removed, zeroing the two walk tiers for incorrect trajectories). Accuracy is unavailable once the policy stops answering.
Figure 4: CNY improves accuracy across base models. Zero-shot base (hollow) vs. CNY best checkpoint (filled) for five backbones on WikiCS (maroon) and Cora (blue). Accuracy is on the evaluation subset tracked during training, so values differ slightly from Table 1 .
Per-step phase (s)
GRPO ( β=0 )
CNY+OPSD
Rollout
8.8
20.0
Log probabilities
14.1
17.6
Actor train (fwd/bwd)
48.3
55.3
Total step wall
87.7
108.9
Compute (PFLOP/step)
12.0
14.8
Table 7: Training-time cost. Median per-step wall time and compute for a matched 7B pair on identical data and hardware, with and without OPSD.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Nodes
Edges
Classes
Train
Val
Test
CiteSeer
3,186
8,450
6
1,911
637
638
PubMed
19,717
88,648
3
11,830
3,944
3,943
Photo
48,362
873,782
12
29,016
9,674
9,672
Computer
87,229
1,256,548
10
52,336
17,446
17,447
History
41,551
503,180
12
24,930
8,310
8,311
Sportsfit
173,055
3,020,134
13
103,834
34,610
34,611
Appendix
Table 8: Dataset statistics.
Figure 5: CNY rollout prompt template. Curly-brace fields are substituted per node.
Figure 6: Destination recap prompt used by OPSD (§ 4.4 ). The recap is produced by the LLM itself and constrained to a single topic-only sentence of at most 50 tokens, with node IDs, walk recommendations and any guess at the target’s class explicitly forbidden, so the recap supplies destination context without leaking the gold label or a navigation hint.
Figure 7: CNY node-classification prompt. A Cora test instance; node and label IDs are substituted per instance.
Figure 8: CNY edge-classification prompt. An FB15K237 test instance. Two anchors (head, tail) replace the single target, and the label slot is a 10 -way shortlist over the FB15K237 relation vocabulary; entity and relation IDs are substituted per edge.
Figure 9: CNY graph-reasoning prompt. An Expla-Graph test instance (gold stance: support). The (belief, argument) pair is the target and the explanation-graph concepts are the walkable neighbourhood; concept IDs and stance indices are substituted per instance.
Setting
Value
Backbone
Qwen2.5-14B-Instruct
GRPO group size N (rollouts per prompt)
8
Prompt batch size
32
Global batch size
256
Learning rate
1×10−6 (constant)
Optimiser
Adam ( β1=0.9 , β2=0.98 )
Appendix
Table 9: Hyperparameters of the CNY-14B reference run (Qwen2.5-14B-Instruct, GRPO with OPSD), as read from the released training configuration.
Backbone
GPUs
Parallelism
Qwen2.5-14B, Qwen3-14B
4× H100
TP =4
Qwen2.5-7B
2× H100
TP =2
Llama-3.2-3B, Qwen3-4B
1× H100 / L40
TP =1
Appendix
Table 10: Compute allocation per backbone. The smallest backbones also fit a single L40; the headline CNY-14B run uses four H100 80GB GPUs under Megatron tensor parallelism.