Search papers, labs, and topics across Lattice.
This paper rethinks the traditional message-passing paradigm in graph neural networks (GNNs) by introducing a retrieval-augmented approach, where each layer utilizes a node representation combined with a summary of retrieved graph context. The authors propose the RTA framework, which substitutes structural message passing with label-aware retrieval, demonstrating that this method not only matches but can surpass existing GNN and graph LLM baselines in performance. Theoretical insights reveal connections between retrieval-based aggregation and softmax-attention, highlighting the robustness of this approach against mis-retrieved outliers.
RTA shows that replacing traditional message passing with retrieval can enhance GNN performance while improving computational efficiency and robustness.
Graph neural networks (GNNs) are typically conceptualized as message-passing neural networks, yet it remains unclear why neighborhood aggregation reliably outperforms node-wise multilayer perceptrons (MLPs). Despite its empirical success, this paradigm can be computationally expensive and sensitive to imperfect graph structures. In this work, we present a retrieval-augmented view of GNNs: each layer makes predictions by applying an MLP to a node representation together with a permutation-invariant summary of retrieved graph context. Motivated by this perspective, we propose RTA, a simple MLP-based framework that replaces structural message passing with label-aware retrieval and propagation. We provide theoretical insights that (i) connect retrieval-based aggregation to softmax-attention message passing, and (ii) establish the robustness of retrieved-context supervision to mis-retrieved outliers. Experiments on multiple text-attributed graph benchmarks show that RTA matches or even outperforms strong GNN and graph LLM baselines while improving efficiency and robustness across diverse scenarios.
