Call Neighbours Yourself: Graph Walks with Destination-Conditioned On-Policy Self-Distillation
AuthorsYilun Liu, Boyu Luo, Yanran Tang, Ruihong Qiu, Zi Huang
CNY teaches language models to choose which graph neighbours to inspect while reasoning, rather than forcing them to rely on a fixed context.
Key results
Zero-shot graph-level accuracy on the unseen Expla-Graph task.
Comparison score for the DeepSeek-R1-distilled Qwen2.5-14B Graph-R1 baseline.
Share of test targets whose full one-hop neighbourhood exceeds 32K tokens.
Zero-shot multi-hop question-answering score without question-answering training.
Score when answering from identical neighbour previews without walking.
Aggregate compute increase over GRPO in matched 7B training experiments.
What the paper found
Call Neighbours Yourself, or CNY, reframes text-attributed-graph reasoning as active evidence acquisition: instead of fixing a neighbourhood before generation, a language model emits topology-constrained <walk> actions, reveals a selected neighbour’s full text, and expands the frontier. Its key training method, destination-conditioned on-policy self-distillation, re-scores each chosen walk after generating a short recap of the revealed destination, then uses the probability shift as token-level credit without step annotations, external judges, or extra rollouts. Using Qwen2.5-14B-Instruct, matched to the DeepSeek-R1-distilled Qwen2.5-14B Graph-R1 baseline, CNY improves zero-shot accuracy across citation, product, relation, and graph-level tasks; on the unseen Expla-Graph task it reaches 92.60 versus Graph-R1’s 89.71. The need for adaptive exploration is clearest on WikiCS, where 40.3% of test targets exceed a 32K-token one-hop context, and CNY’s learned walking outperforms retrieval while using 6.3× fewer tokens in the motivating comparison. On WebQSP, without question-answering training, CNY achieves 58.4 Hits@1 versus 38.5 from identical previews. The method also transfers across Llama and Qwen backbones, although its training overhead rises by 24% in matched 7B experiments, and its gains shrink as the underlying model becomes stronger.
Original abstract
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.
Read the original paperMore in Graph Learning
Browse all 32 papers →CodeGraph: Open-Taxonomy Knowledge Graph for Source Code with Wikidata Grounding
Federico Pennino, Andrea Gurioli, Stefano Zacchiroli, Maurizio Gabbrielli, Paolo Ferragina
CodeGraph turns 167 million source files into a Wikidata-grounded knowledge graph of algorithms, paradigms, patterns, and software domains.
GraphWrit3R: End-to-End 3D Scene Graph Writing
Luka Milivojevic, Nikola Popovic, Sayan Deb Sarkar, Sebastian Koch, Iro Armeni, Luc Van Gool, Danda Pani Paudel
GraphWrit3R turns 3D spatial data into open-vocabulary scene graphs using multimodal encoders and an LLM, without requiring ground-truth object annotations at inference.
Statistical Inference for Causal Discovery under Selection and Latent Variables via Single-Target Interventions
Xiaotian Hou, Kwangmoon Park, Hongzhe Li
This work shows how a small, carefully designed set of single-variable interventions can recover causal structure even when hidden confounders and selection bias complicate the data.