Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning

Jintang Li, Yuhong Chen, Ruofan Wu, Binli Luo, Jiayi Ji, Hui Li, Rongrong JiarXiv 2026 · arXiv

TL;DR

This paper reframes Graph Neural Networks (GNNs) through the lens of Retrieval-Augmented Generation (RAG), showing that message passing is essentially an MLP operating on a node and its retrieved graph context. Leveraging this insight, the authors introduce RTA (Retrieve-Then-Aggregate), a simple, highly efficient framework that replaces fixed-edge message passing with label-aware semantic and structural retrieval, significantly boosting robustness against noise and oversmoothing.

What Problem Does This Paper Address?

The dominant paradigm in graph representation learning is message passing, where nodes iteratively aggregate features from their immediate neighbors. While empirically successful, this approach suffers from several fundamental flaws:

  1. Structural Sensitivity: It assumes the input graph topology is perfect, making it highly vulnerable to noise or adversarial attacks.
  2. Oversmoothing and Oversquashing: As networks grow deeper, node representations tend to collapse and become indistinguishable.
  3. Heterophily Issues: Traditional message passing struggles on heterophilous graphs, where connected nodes belong to different classes.

The authors ask a fundamental question: Does the effectiveness of GNNs stem from graph-based propagation itself, or more generally, from conditioning node predictions on informative contexts? By drawing a parallel to RAG in natural language processing, they aim to decouple context selection from fixed, potentially noisy graph edges.

Fig. 1. Technical comparison between GNN and RAG. Both leverage contextual information beyond the raw input.

Methods

The authors propose RTA (Retrieve-Then-Aggregate), a pure retrieval-centric framework for text-attributed graphs (TAGs) that completely bypasses explicit multi-hop graph convolutions. RTA operates in three distinct stages:

  1. Label-Aware Contextual Node Embedding: Instead of embedding text nodes in isolation, RTA augments each node's text with a small set of structural neighbor texts and their corresponding training labels. This combined context forms a prompt fed into a text-embedding LLM (like bge-en-icl) to generate context-aware initial node embeddings.
  2. Semantic-Structural Context Retrieval: RTA dynamically rebuilds the graph topology by constructing a retrieval-defined context graph. For each node, it computes a unified retrieval score combining semantic similarity (via approximate nearest neighbor search like FAISS) and structural proximity (via Personalized PageRank). It then selects the top-$k_2$ most relevant nodes as the new context set.
  3. Label-Enhanced Retrieval Aggregation: Finally, a simple Multilayer Perceptron (MLP) updates the node representations by aggregating the features and available label embeddings from the dynamically retrieved context set.
Fig. 3. Overall framework of RTA. RTA recasts graph representation learning as a retrieval-augmented pipeline that avoids explicit multi-hop message passing over the original graph. Specifically, (a) for a query node v0, we augment its text with a small set of structural neighbors (size k1) and corresponding labels as the resulting prompt to obtain the contextual node embedding xv0. Then, (b) based on the learned embeddings and the original graph structure, we construct a retrieval-defined context graph by jointly considering semantic similarity and structural proximity. Specifically, semantic retrieval is performed in the embedding space (e.g., via FAISS), while structural retrieval exploits graph diffusion information. Finally, (c) we aggregate features and available label embeddings from retrieved contexts and apply an MLP-style update to produce task-specific node representations for prediction.

Datasets

The framework was evaluated on ten text-attributed graph benchmarks, categorized by their structural properties:

  • Homophilic Datasets: Children (Books-Children), History (Books-History), Computers (Ele-Computers), Photo (Ele-Photo), Fitness (Sports-Fitness), and Ogbn-Arxiv-TA.
  • Heterophilic Datasets: University web-page graphs including Cornell, Texas, Wisconsin, and Washington.
Dataset statistics

Key Insights and Ideas

  • The GNN-RAG Duality: The paper mathematically demonstrates that a standard message-passing layer can be viewed as a sparse approximation of softmax-attention message passing over a retrieved context set.
  • Inherent Robustness to Outliers: Through formal optimization analysis (Theorem 2), the authors prove that retrieved-context supervision naturally reduces the gradient influence of mis-retrieved or adversarial outlier nodes. This explains why RTA maintains high accuracy even when the retrieval step introduces noisy neighbors.
  • Breaking the Depth Barrier: Because RTA replaces recursive neighborhood diffusion with localized, retrieval-driven interactions, it completely mitigates the oversmoothing problem, allowing the model to scale to deep architectures (up to 32 layers) without performance degradation.

Key Results

  • Superior Accuracy: RTA consistently outperformed standard GNNs (GCN, GAT, GraphSAGE), Graph Contrastive Learning methods (DGI, MaskGAE), and specialized Graph LLMs (GLEM, TAPE, LlaGA) across all ten datasets. For instance, on the heterophilic Texas dataset, RTA achieved 97.4% accuracy compared to GraphSAGE's 64.2%.
  • Adversarial Resilience: Under structural-perturbation attacks (SGA), standard GNNs collapsed, while RTA maintained stable, state-of-the-art performance due to its redundant, multi-support retrieval mechanism.
  • Efficiency Gains: RTA demonstrated significantly higher computational efficiency, achieving faster training and inference times on large datasets (like Fitness) by avoiding costly iterative graph convolutions.

Limitations and Future Work

While RTA offers a powerful alternative to traditional GNNs, the paper notes or implies a few limitations:

  • Dependence on Embedding Quality: The framework relies heavily on the performance of the underlying text-embedding model. As shown in the ablation studies, switching from a strong embedder (bge-en-icl) to a weaker one (bert-base-uncased) leads to noticeable performance drops, especially in heterophilic settings.
  • Hyperparameter Sensitivity: Performance is bounded by a clear trade-off when choosing the number of retrieved samples ($k_1$ and $k_2$). Retrieving too many samples introduces irrelevant noise and redundancy, which can hurt accuracy.

Future work could explore adaptive methods for automatically tuning retrieval sizes and dynamically balancing semantic versus structural weights based on local graph density.

Summary updated

Abstract

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.
BibTeX
@misc{li2026rethinking,
  author = {Jintang Li and Yuhong Chen and Ruofan Wu and Binli Luo and Jiayi Ji and Hui Li and Rongrong Ji},
  title = {{Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning}},
  year = {2026},
  eprint = {2608.26732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.26732},
}
Figure