Source-linked AI summary
Call Neighbours Yourself: Graph Walks with Destination-Conditioned On-Policy Self-Distillation
Yilun Liu, Boyu Luo, Yanran Tang, Ruihong Qiu, Zi Huang
TL;DR
Fixed pre-generation neighbour selection limits TAG reasoning when decisive evidence lies elsewhere in a graph neighbourhood. CNY lets LLMs acquire evidence through topology-constrained graph walks and uses destination-conditioned self-distillation for action-level credit. Across TAG benchmarks, CNY consistently improves over fixed-context baselines and transfers to unseen graphs and a held-out graph-level task.
Problem
Existing TAG methods fix accessible neighbours before generation, preventing adaptive evidence acquisition when decisive evidence lies elsewhere.
Method
CNY selects and expands neighbours during generation through graph-walk actions, while OPSD converts revealed-destination preference shifts into action-level training signals.
Results
CNY consistently outperforms fixed-context baselines across TAG benchmarks and transfers to unseen graphs and a graph-level task not used during training.
Takeaways & Limitations
Effective graph reasoning depends on both interpreting evidence and acquiring it adaptively during reasoning.
Takeaways & Limitations
CNY cannot inject domain facts absent from the backbone, and evaluation covers neither large-scale, heterogeneous, or temporal graphs nor broad task families.
Abstract
from arXiv · showhide
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.
1 Introduction
TAG reasoning requires evidence from graph neighbourhoods, but fixed pre-generation neighbour selection prevents models from adapting evidence acquisition during reasoning. CNY makes neighbour exploration an action and trains it with destination-conditioned self-distillation, outperforming fixed-context baselines.
- TAG reasoning combines each target node’s text with evidence distributed across text-bearing graph neighbours.
- Existing methods select neighbouring texts before generation, preventing the LLM from adapting evidence gathering to discoveries made during reasoning.
- 40.3% of 2,340 WikiCS test targets have one-hop neighbourhoods exceeding a 32K-token window, making fixed subset selection consequential.
- CNY exposes lightweight neighbour previews and lets the LLM select and expand neighbours during generation through graph-walk actions.
- Destination-conditioned on-policy self-distillation converts post-revelation changes in action preference into per-action credit without step labels.
- CNY surpasses fixed-context baselines across citation, hyperlink, co-purchase and knowledge-graph benchmarks.
2 Related Work
Prior TAG methods generally reason over fixed neighbourhood contexts, while agentic retrieval interleaves reasoning with free-form semantic search. CNY instead makes topology-constrained neighbour selection a learnable graph walk with destination-conditioned action supervision.
- Existing TAG methods commonly encode graph information while using neighbourhood contexts selected before generation by non-learned heuristics.
- Agentic retrieval systems interleave reasoning with external search by issuing free-form queries to semantic retrievers over unstructured sources.
- CNY formulates neighbour selection as a learnable graph walk and derives action-level supervision from revealed destinations without labelled intermediate trajectories.
3 Problem Definition
A text-attributed graph pairs adjacency structure, node descriptions, and a finite label set. The task is to predict a target node’s label from neighbourhood evidence under a limited reading budget.
- A TAG is represented as G = {A, X, Y}, with adjacency matrix A, textual node descriptions X, and label set Y.
- Given target node v0, the model predicts label ˆy from evidence distributed across its graph neighbourhood.
- Figure 2 depicts graph-walk trajectories in which successful walk node-ID tokens receive OPSD credit after destination text is revealed.
- 40.3% of WikiCS evaluation nodes have one-hop text exceeding 32K tokens, so prediction requires selecting a subset of neighbourhood evidence.
4 Method: Call Neighbours Yourself
CNY treats graph reasoning as interactive evidence acquisition: the LLM selects neighbours during generation, receives their full text, and learns local credit for walk decisions from destination-conditioned self-distillation.
- Interactive graph environment: CNY models neighbourhood evidence acquisition as a sequential decision process in which the LLM walks the graph instead of using a fixed neighbour set.Training uses reinforcement learning, trajectory-level rewards, and OPSD refinement.
- Interactive graph environment: The initial context contains the ego-node text, label descriptions, and short neighbour previews, while full neighbour text remains hidden until selected.This lets the model decide which candidate neighbours warrant deeper inspection.
- Interactive graph environment: Executing <walk> on node X reveals its full text and expands the frontier with unseen neighbours, restricting evidence acquisition to graph-connected nodes.Newly available nodes must be adjacent to previously inspected nodes.
- Reinforcement learning optimisation: The reward prioritises correct prediction, valid formatting, successful evidence acquisition, and answer completion through an ordered non-calibrated reward scheme.The ordering is 1.0 > 0.6 > 0.3 > 0.2 > 0.1 > 0, and the reward is unchanged in the β=0 ablation.
- Destination-conditioned self-distillation: OPSD uses the destination revealed by a realised walk to convert hindsight changes in action preference into local credit for neighbour-selection tokens.The same policy scores the walk under the original context and under a context containing a destination recap; δ_t is added only to successful walk node-ID tokens.
- Training: Reasoning tokens retain trajectory-level supervision, while GRPO advantages are refined only at walk-destination tokens within the PPO-style clipped optimisation.The destination signal is detached from θ, and β controls its strength.
5 Experiments
Across held-out graphs and task families, CNY’s learned graph walks outperform fixed-context reasoning and transfer beyond the training setting. Controlled experiments attribute gains to selective, topology-aware evidence acquisition and OPSD’s action-level credit.
- Main results: CNY attains the highest accuracy on every Table 1 setting, leading Graph-R1 across task families and transfer axes.The evaluation covers unseen graphs within trained task families and a task family absent from training.
- Cross-dataset transfer: 76.8 at 10 ways and 85.5 at 5 ways on WikiCS exceed the second-best 73.6 and 80.9, while Cora’s narrower margin reflects its sparser neighbourhoods.The reported comparison links the larger WikiCS gain to greater dependence on selecting informative neighbours.
- Cross-task transfer: 92.60 stance accuracy on Expla-Graph exceeds Graph-R1’s 89.71 and TRN-R1-Zero’s 85.92 despite no graph-level training and less input information.CNY receives only seed concepts and walks to reveal the remaining explanation graph, whereas reasoning baselines receive the full graph.
- Effectiveness of walking: Walking raises accuracy on every dataset at a matched text budget, indicating that selective reading—not simply more context—drives the improvement.The comparison uses direct reading of one full 1-hop neighbour versus walking to selected neighbours at 1.1–1.3 neighbours per node.
- Inference controls: 77.0 at 2,341 tokens per node beats self-consistency’s 74.5 and best-of-4 reranking’s 74.4 at 2,899 tokens on WikiCS.Showing every preview without permitting walks improves the direct baseline only modestly.
- Topology analysis: Degree-preserving rewiring drops WikiCS walk accuracy from 76.6 to 73.0, while same-class selections exceed homophily rates, supporting topology-sensitive exploration.Walks rarely select the most embedding-similar preview, indicating that the policy is not merely semantic retrieval.
- Multi-hop transfer: On WebQSP, zero-shot walking reaches 58.4 Hits@1 versus 38.5 from identical previews, a +19.9 gain without question-answering training.The frozen CNY-14B checkpoint walks Freebase subgraphs, while question-only and full 1-hop alternatives perform worse.
- OPSD effectiveness: OPSD improves cross-domain accuracy beyond the β=0 GRPO ablation even when both models reach the same training reward.The separated held-out accuracy places the observed contribution in generalisation rather than closer fitting of the training mixture.
6 Conclusion
CNY treats neighbour acquisition as graph-walk actions and supervises those actions with destination-conditioned OPSD. Across TAG benchmarks, it improves reasoning performance and transfers to unseen domains.
- CNY formulates neighbour acquisition as graph-walk actions supervised by destination-conditioned on-policy self-distillation.OPSD derives action-level credit from revealed destinations without annotated trajectories, external judges, or additional rollouts.
- CNY consistently improves reasoning performance across multiple text-attributed graph benchmarks.The framework replaces fixed neighbour contexts with adaptive evidence acquisition during reasoning.
- The learned exploration policy transfers to unseen domains.The reported conclusion links this transfer to adaptive evidence acquisition during graph reasoning.
Limitations
CNY’s scope is bounded by the base model’s encoded knowledge and by the benchmark coverage. The evidence for generalisation also spans limited task and model-family ranges.
- CNY cannot inject domain facts absent from the base model, so final accuracy is bounded by its encoded knowledge.Tasks requiring missing knowledge may need a stronger or further pre-trained backbone.
- The evaluation omits large-scale, heterogeneous, and temporal graphs.The benchmark is inherited from the GOFA-aligned zero-shot evaluation suite for direct comparison with prior work.
- Cross-task generalisation is supported by one graph-level task and one open-ended question-answering task.Broader graph families and task types remain untested.
- The backbone study covers the Llama and Qwen families up to 14B, leaving other model families uncharacterised.
- Prior TAG reasoning methods and agentic retrieval systems provide comparison context but do not remove these scope boundaries.Existing TAG methods use fixed neighbourhood contexts, while agentic retrieval typically operates through external semantic retrievers over unstructured corpora.
B OPSD Credit Derivation
The OPSD derivation connects destination-conditioned self-distillation to dense, action-level credit for graph walks. Its per-token update uses the teacher–student log-ratio on realised walk tokens.
- OPSD compares student and destination-conditioned teacher token distributions at positions belonging to a walk action.The teacher receives a recap attached to the selected walk, while the student uses the original autoregressive prefix.
- At each walk-action token, OPSD minimises the per-token reverse KL divergence between the student and recap-informed teacher.
- The teacher is held fixed with stop-gradient, and the student samples tokens on policy before being pulled toward the recap-informed distribution.
- The resulting REINFORCE-style per-token weight is the teacher-to-student log-ratio, making δ_t a per-token advantage.Credit assignment by the log-ratio and distillation toward the teacher produce the same update.
- Evaluated on the realised token, δ_t is a biased estimator of the reverse-KL gradient used directly as dense credit.The derivation therefore identifies a specific estimator caveat for the walk-action signal.
- Algorithm 1 generates CNY rollouts, while Algorithm 2 combines GRPO trajectory advantages with OPSD credit during training.
D Datasets and Prompt Templates
The appendix specifies reproducible datasets, rollout algorithms, and prompt constructions for node, edge, and graph-level tasks. Prompts expose walkable previews and reveal node information through constrained graph exploration.
- D Datasets and Prompt Templates: CNY uses fixed-random-state data construction so splits, neighbourhoods, and rollouts can be reproduced exactly.The evaluation reuses a GOFA-aligned suite with defined training and held-out datasets.
- D Datasets and Prompt Templates: A rollout samples actions from the policy, reveals a walked node’s information, updates the frontier, and returns an answer or failure.Walks are accepted only for frontier nodes, while malformed actions continue the loop.
- D Datasets and Prompt Templates: Training samples parallel rollouts, computes trajectory rewards and GRPO advantages, then adds OPSD credit to walk-action tokens before PPO optimisation.
- D.1 Baselines and Evaluation Details: The benchmark includes node-, edge-, and graph-level evaluations, with Expla-Graph as the sole graph-level task and no molecular regression or link prediction subset.
- D.3 Node-Classification Prompt: Node prompts use a shared multi-step template with illustrative turns and a strict format reward; edge prompts allow walks from either head or tail anchor.Edge labels use a ten-way candidate set consisting of the gold relation and nine deterministic distractors.
- D.5 Expla-Graph Stance-Walk Construction: Expla-Graph maps belief–argument stance classification onto the node walk template while keeping each instance’s concept graph isolated.The stance rule distinguishes agreement with the belief from general positivity toward the topic.
- D.5 Expla-Graph Stance-Walk Construction: Expla-Graph begins with connected seed concepts shown as name-only previews, then reveals remaining concept text and relations through the information channel.The gold explanation graph is withheld to prevent stance leakage.
- D.6 Destination Recap Prompt: Destination recaps are topic-only, single-sentence summaries generated by the LLM without node IDs, walk recommendations, or class guesses.They provide destination context for OPSD without leaking the gold label or navigation hint.
E Implementation
The implementation uses a configured CNY-14B reference run, with documented hyperparameters, compute allocation, frozen-model evaluation, and fixed preview budgets.
- The headline CNY-14B run uses four H100 80GB GPUs with Megatron tensor parallelism.The allocation is specified as TP=4; the run has a 1,000-step wall limit and fits within 80 GB per H100.
- Table 9 records the optimisation and rollout hyperparameters for the CNY-14B reference run.The configuration is identified as Qwen2.5-14B-Instruct trained with GRPO and OPSD.
- Evaluation measurements use the frozen CNY-14B model unless a training run is explicitly stated.
- Inference-only preview budgets yield WikiCS accuracies of 77.1 at 5 tokens, 77.9 at 10, 76.8 at 30, and 77.5 at 60.The 5-token setting is title-only, while 30 tokens is the published configuration.
F.2 Matched Preview Exposure
The matched control exposes all neighbour previews without allowing walking, while the destination recap is constrained to provide topic context without label or navigation leakage.
- Destination Recap: The destination recap is one topic-only sentence of at most 50 tokens produced by the LLM itself.
- Destination Recap: The recap forbids node IDs, walk recommendations, and guesses about the target class, preventing label or navigation leakage.
- Matched Preview Exposure: The direct-control baseline shows previews of every neighbour but forbids walking, matched to each dataset’s preview length and frontier size.
- Matched Preview Exposure: All-preview exposure improves direct accuracy modestly: Cora 65.0 →66.3, WikiCS 71.0 →73.4, and Products 83.0 →83.5.
F.3 Failure Modes of Walking
Walking errors are analysed as flips, with adjacent-class interference identified as the most common failure pattern among the described modes.
- Failure-mode definition: A flip is a node classified correctly from target text alone but misclassified after walking.Flips are pooled over three walk-evaluation seeds and assigned failure modes by manual inspection.
- Failure modes: The first failure mode concentrates on adjacent class pairs, most often Computer Architecture to Operating Systems.The second mode concerns multi-facet targets whose destination text foregrounds the wrong facet.
- Walk interaction: Each CNY turn uses a structured thinking-and-walk format, including a walk action that fetches a node’s full text and its 1-hop neighbours.