TL;DR
Call Neighbours Yourself (CNY) is a novel reinforcement learning framework that enables Large Language Models (LLMs) to actively explore text-attributed graphs via step-by-step, topology-constrained "walk" actions mid-generation. By introducing destination-conditioned on-policy self-distillation (OPSD), CNY provides precise token-level credit to these exploration choices in hindsight, significantly improving reasoning accuracy while using up to 6.3× fewer tokens than traditional retrieval-augmented generation (RAG) pipelines.
What Problem Does This Paper Address?
Reasoning over text-attributed graphs (TAGs)—such as citation networks, hyperlink webs, or product co-purchase graphs—requires an LLM to synthesize information from a target node alongside evidence scattered across its neighborhood.
Current state-of-the-art approaches treat this as a static prompt-construction problem: they use heuristics or external embedding retrievers to select a fixed subset of neighbor texts before the LLM starts generating its answer. This paradigm suffers from two major flaws:
- Context Overflow: On dense graphs, a node's full neighborhood can easily exceed practical context windows (e.g., over 40% of neighborhoods in the WikiCS dataset exceed 32K tokens), forcing aggressive and potentially destructive truncation.
- Decoupled Retrieval: Because neighbor selection happens before generation, the LLM cannot dynamically adapt its search based on clues or partial evidence it uncovers while it is actively reasoning.
Methods
The authors propose Call Neighbours Yourself (CNY), a framework that transforms neighbor selection into an interactive, sequential decision process. Instead of digesting a massive, pre-selected block of text, the LLM is initially shown only lightweight neighbor previews (like titles or short text prefixes). As the model generates its reasoning trace, it can proactively emit an explicit action—<walk>X</walk>—to fetch the full text of node X and expand its visible frontier to X's neighbors.
To train the LLM to walk effectively without relying on expensive, human-annotated step-by-step trajectories, the authors introduce Destination-Conditioned On-Policy Self-Distillation (OPSD):
- The Hindsight Signal: When the LLM executes a walk, the environment reveals the destination text, which is then compressed into a short, topic-level "recap" (excluding explicit labels or node IDs).
- Dual Scoring: The base LLM scores its own walk action twice: once blind to the destination (the "student" view) and once conditioned on the destination recap (the "teacher" view).
- Action-Level Credit: The difference in log probabilities (reverse KL divergence) between the teacher and student views serves as an immediate, local credit signal ($\delta_t$). If knowing the destination makes the original choice look better, that specific walk action is reinforced.
Datasets
- Training Mixture: CNY is trained on a multi-task mixture of 8 text-attributed graphs spanning node classification (CiteSeer, PubMed, Photo, Computer, History, Sportsfit, Instagram) and relation classification (WN18RR).
- Zero-Shot Evaluation: The trained model is evaluated without any fine-tuning on 5 held-out graphs: Cora, WikiCS, and ogbn-products (node-level); FB15K237 (edge-level); and Expla-Graph (a graph-level commonsense explanation dataset entirely absent from the training task family).
- Multi-Hop KGQA: The model is also evaluated on the WebQSP benchmark to test its ability to handle deeper, multi-step graph exploration.
Key Insights and Ideas
- Interleaved Reasoning and Retrieval is Highly Efficient: Letting the LLM decide what to read while it thinks is fundamentally more efficient than pre-filtering. Active walking allows the model to achieve superior accuracy with a fraction of the context length compared to standard RAG pipelines.
- Hindsight Eliminates the Need for Gold Labels: OPSD elegantly bypasses the need for separate process reward models (PRMs) or gold-standard step annotations. By simply asking the model "Knowing what you found at the destination, was that a smart move?", it generates its own dense, token-level training signal.
- Graph Topology is a Crucial Constraint: CNY forces the LLM to follow actual graph edges rather than jumping arbitrarily across an open query space. When the authors ran a control experiment with randomized edge-swapping (preserving node degrees but destroying topology), the model's performance collapsed, proving that it genuinely learns to navigate graph structures rather than just performing flat semantic retrieval.
Key Results
- Outperforming Fixed-Context Baselines: CNY consistently outperformed state-of-the-art post-training baselines like Graph-R1 and TRN-R1-Zero. For example, on the dense WikiCS dataset (10-way classification), CNY (14B) achieved 76.75% accuracy compared to Graph-R1's 73.25%.
- Token Reductions: On WikiCS targets where the full neighborhood could fit in a 32K context, CNY achieved higher accuracy than a standard RAG pipeline while consuming 6.3× fewer tokens (as illustrated in Figure 1a).
- Cross-Task Generalization: The learned exploration policy successfully transferred to entirely unseen task types. On Expla-Graph (graph-level stance detection), CNY achieved a top accuracy of 92.60% (vs. Graph-R1's 89.71%), despite never encountering graph-level reasoning during training.
- Deeper Exploration: On the multi-hop KGQA benchmark (WebQSP), CNY improved the Hits@1 score to 58.4 (compared to 49.0 for a full 1-hop context baseline), with the policy naturally scaling up its exploration depth to an average of 2.31 walks per question.
Limitations and Future Work
- Bounded by Base Model Knowledge: CNY optimizes the exploration policy, not the underlying world knowledge of the LLM. If the base model lacks the domain facts required to understand the text it uncovers, walking cannot fix it.
- Graph Scale and Diversity: The evaluation suite, while standard, does not cover massive-scale industrial graphs, highly heterogeneous networks, or temporal graphs where neighborhood structures shift over time.
- Model Families: The study was restricted to the Llama and Qwen model families up to 14B parameters; performance on other architectures remains uncharacterized.
Summary updated