Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning

Jintang Li; Yuhong Chen; Ruofan Wu; Binli Luo; Jiayi Ji; Hui Li; Rongrong Ji

cs.LGAug 27, 2026

Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning

Authors: Jintang Li, Yuhong Chen, Ruofan Wu, Binli Luo, Jiayi Ji, Hui Li, Rongrong Ji

Organizations: School of Computer Science and Engineering of Central South University, Changsha 410000, China

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.

Figures & tables

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

Fig. 2: Illustrative example on how GNNs are decomposed into RAG-like architectures.

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 $v_{0}$ , we augment its text with a small set of structural neighbors (size $k_{1}$ ) and corresponding labels as the resulting prompt to obtain the contextual node embedding $\mathbf{x}_{v_{0}}$ . 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.

Dataset	#Nodes	#Edges	#Classes	Type
Children	76,875	1,554,578	24	Homophilic
History	41,551	358,574	12	Homophilic
Computers	87,229	721,081	10	Homophilic
Photo	48,362	500,928	12	Homophilic
Fitness	173,055	1,773,500	13	Homophilic
Arxiv	169,343	1,166,243	40	Homophilic

TABLE I: Datasets statistics. Both homophilic and heterophilic graphs are included in our experiments.

	Children	History	Photo	Computers	Fitness	Arxiv	Cornell	Texas	Wisc.	Wash.
MLP	51.2 ±0.2	82.0 ±0.9	60.7 ±0.9	65.3 ±0.4	87.2 ±0.3	46.5 ±0.8	49.5 ±0.7	62.0 ±1.8	46.5 ±1.5	66.0 ±0.9
GCN	56.3 ±0.3	84.4 ±0.3	84.0 ±0.9	87.6 ±0.4	92.1 ±0.7	72.5 ±0.6	52.6 ±0.4	64.8 ±1.5	49.0 ±0.7	69.5 ±0.5
GAT	56.4 ±0.8	84.0 ±0.6	85.3 ±0.5	88.6 ±0.2	92.5 ±0.5	72.7 ±0.8	53.2 ±0.6	65.9 ±1.4	52.3 ±0.4	73.1 ±0.7
GraphSAGE	58.5 ±0.1	86.1 ±0.8	82.9 ±0.7	87.9 ±0.8	92.8 ±0.5	72.9 ±0.8	54.8 ±0.5	64.2 ±1.3	50.1 ±1.0	71.4 ±0.6
DGT	57.4 ±0.7	86.2 ±0.3	85.1 ±0.5	87.3 ±0.3	92.0 ±0.5	74.6 ±0.4	54.5 ±0.3	67.3 ±1.0	51.4 ±1.2	71.5 ±0.5
DGI	54.9 ±0.5	84.9 ±0.3	82.7 ±0.6	86.9 ±0.4	92.9 ±0.7	72.1 ±0.5	14.7 ±0.9	11.2 ±1.4	12.1 ±0.7	21.0 ±1.2

TABLE III: Node classification results (%) on text-attributed graphs. The best and second-best performances are highlighted as boldfaced and underlined , respectively.

Fig. 4: Performance comparison against graph adversarial attack SGA [ 61 ] .

Panel of Figure 7 — Fig. 5: Node classification performance with different network depth. Here we compare only with representative GNNs.

Panel of Figure 8 — Fig. 6: Comparison of training and inference time on Fitness dataset across different GNNs.

Panel of Figure 9 — Fig. 7: Ablation results on the number of retrieved samples in text embedding ( $k_{1}$ ) and message aggregation ( $k_{2}$ ).

	Children	History	Photo	Computers	Cornell	Texas	Wisc.	Wash.
RTA $\backslash$ (L-I)	56.6 ±0.3	85.4 ±0.9	86.2 ±0.8	86.9 ±0.6	85.4 ±0.4	95.1 ±0.7	90.2 ±0.6	80.7 ±0.9
RTA $\backslash$ (L-II)	58.3 ±0.6	86.6 ±0.7	85.4 ±0.5	88.8 ±0.3	79.4 ±1.1	86.1 ±1.5	83.3 ±1.6	74.6 ±1.4
RTA $\backslash$ (L-I&II)	55.9 ±0.7	84.7 ±0.4	83.2 ±0.3	85.4 ±0.4	76.6 ±1.4	68.6 ±0.9	80.6 ±0.8	69.6 ±1.2
RTA $\backslash$ (semantic retrieval)	57.8 ±0.7	84.9 ±0.8	84.6 ±0.7	87.1 ±0.6	78.8 ±1.3	84.7 ±1.6	82.1 ±1.5	73.8 ±1.4
RTA $\backslash$ (structural retrieval)	59.9 ±0.6	85.9 ±0.6	87.1 ±0.6	89.8 ±0.5	85.6 ±0.9	93.2 ±1.0	91.5 ±1.1	79.8 ±1.0
RTA	61.9 ±0.7	87.0 ±0.5	88.7 ±0.4	91.2 ±0.3	89.9 ±0.2	97.4 ±0.4	96.3 ±0.3	82.6 ±0.2

TABLE IV: Comparisons between RTA and its variants. L-I: label-aware contextual embedding; L-II: label-aware aggregation.

Retriever backbone	Children	History	Photo	Computers	Cornell	Texas	Wisc.	Wash.
bert-base-uncased	60.1 ±0.4	85.7 ±0.8	87.6 ±0.6	90.3 ±0.2	81.4 ±1.6	80.4 ±0.6	77.8 ±2.0	68.6 ±1.6
all-mpnet-base-v2	60.6 ±0.3	86.2 ±0.3	88.2 ±0.3	90.8 ±0.3	82.6 ±1.2	84.9 ±0.8	79.1 ±1.4	69.6 ±1.5
bge-en-icl	61.9 ±0.7	87.0 ±0.5	88.7 ±0.4	91.2 ±0.3	89.9 ±0.2	97.4 ±0.4	96.3 ±0.3	82.6 ±0.2

TABLE V: Retriever backbone ablation for RTA on eight node classification benchmarks.

Explore similar work

PromptGNN-sim: Deep Fusion and Alignment of GNN and LLMs for Text-Attributed Graph Learning
Jun 29, 2026Zhifei Hu, Alexandra I. CristeaText-Attributed Graph Learning Multimodal Fusion
Durham University, Durham, United Kingdom
TAG-DLM: Diffusion Language Models for Text-Attributed Graph Learning
Jun 30, 2026Lingjie Chen, Yuanchen Bei, Haobo Xu +3Masked Diffusion Models Link Prediction
UIUC · VISA
LLM as Graph Kernel: Rethinking Message Passing on Text-Rich Graphs
Mar 16, 2026Ying Zhang, Hang Yu, Haipeng Zhang +1LLMs for Graph Learning Text-Attributed Graph Learning
Ant Group · ShanghaiTech University

Jun 29, 2026J/K move · Enter open · S save

PromptGNN-sim: Deep Fusion and Alignment of GNN and LLMs for Text-Attributed Graph Learning

Zhifei Hu, Alexandra I. Cristea

Durham University, Durham, United Kingdom

Text-Attributed Graph Learning Multimodal Fusion

Open paper AskPDF arXiv

Text-Attributed Graphs (TAGs) combine textual semantics with graph structure and are central to many graph learning tasks. However, existing fusion methods often treat text and structure as separate inputs in a shallow, one-way pipeline, which limits deep interaction between modalities and weakens performance under sparse connectivity or cross-graph generalisation. To address this issue, we propose PromptGNN-sim, a bi-directional structure-semantic fusion framework for collaborative GNN-LLM learning. PromptGNN-sim uses a Graph Attention Network (GAT) for semantically aware neighborhood selection by combining structural attention with textual similarity. The selected structural context is then used to generate structure-aware prompts for an LLM, including the target node summary, label categories, and representative keywords from similar neighbors. During training, bi-directional cross-modal contrastive learning and cross-attention are introduced to jointly optimize the GNN and LLM components. Experiments on six public datasets, including Cora, Pubmed, and WikiCS, evaluate accuracy, generalisation, and robustness under cross-task transfer, cross-dataset generalisation, and sparse perturbations. Results show that PromptGNN-sim outperforms classical GNNs, LLMs, and recent GNN-LLM fusion methods, demonstrating the effectiveness of interactive structure-semantic collaboration for text-attributed graph learning.

Abstract

Explore similar work

PromptGNN-sim: Deep Fusion and Alignment of GNN and LLMs for Text-Attributed Graph Learning

TAG-DLM: Diffusion Language Models for Text-Attributed Graph Learning

LLM as Graph Kernel: Rethinking Message Passing on Text-Rich Graphs