Adaptive Recurrent Message Passing for Test Time Computing on Graphs

Traditional graph neural networks (GNNs) rely on a fixed number of layers, which imposes a rigid receptive field. This creates a mismatch when applying pre-trained models to diverse real-world graphs that require varying levels of local or global context. The authors investigate whether a recurrent graph model can overcome this by adjusting its receptive field dynamically during test time without requiring architectural changes or retraining.

The authors provide a theoretical analysis establishing that step dependence is a necessary and sufficient condition for a recurrent process to converge adaptively. Based on this, they propose AdaR (Adaptive Recurrent graph model). AdaR uses a single recurrent layer that is iteratively reused. To ensure the model remains stable and effective across different iteration budgets, the authors:

• Encode normalized step information using sinusoidal position embeddings, allowing the model to remain aware of its progress toward convergence.
• Implement a proxy-based relation computing strategy, where a fixed number of pseudo-nodes aggregate information from task-specific targets, enabling the model to handle varying target counts.
• Use gradient-based supervision during training to guide representation updates throughout the recurrence, ensuring the model learns to approximate a continuous-time dynamical system.

AdaR demonstrates that by explicitly incorporating step information and representation-target relations, a recurrent graph model can be trained with a small iteration budget and evaluated with significantly larger budgets. Empirical results show that AdaR consistently outperforms strong baselines across both inductive and transductive graph learning settings. The model effectively bridges the gap between pre-training and diverse downstream tasks by allowing the receptive field to adapt to the specific requirements of the input graph at inference time.