Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning

1 INTRODUCTION

• GNNs aggregate neighborhood messages effectively but face scalability, graph-sensitivity, and deep-propagation challenges.These challenges motivate examining alternatives to fixed-edge message passing.Source: §1 · p. 1
• GNN layers can be interpreted as MLPs operating on a node and a retrieved context set.Different GNN variants correspond to different retrievers and permutation-invariant set functions.Source: §1 · p. 1
• RTA replaces recursive message passing with label-aware retrieval, contextual encoding, retrieval-graph construction, and label-enhanced aggregation.The framework is designed as a scalable retrieval-centric alternative for text-attributed graph representation learning.Source: §1 · pp. 1–2
• Top-k retrieval with aggregation sparsely approximates softmax-attention message passing, with error controlled by retrieval margins and score distributions.This provides a theoretical connection between retrieval-based aggregation and message passing.Source: §1 · p. 2
• Label-aware retrieved-context supervision reduces gradient influence from mis-retrieved outliers, supporting robustness under noisy contexts.The result provides theoretical support for label-guided retrieval and aggregation.Source: §1 · p. 2
• Experiments on multiple text-attributed graph benchmarks show that RTA matches or outperforms strong GNN baselines while improving efficiency and robustness.The paper frames this as retrieval-defined computation rather than fixed-edge diffusion.Source: §1 · p. 2

2 RELATED WORK

• The paper addresses an underexplored connection among message passing, text-attributed graph learning, and RAG by interpreting graph representation learning as retrieval-augmented prediction.This distinguishes the work from treating the three research areas independently.Source: §2 · p. 2
• Prior work studies message-passing GNNs for learning representations over graph-structured data and modeling complex relationships.Graph Transformers are also presented as an alternative for capturing long-range dependencies.Source: §2.1 · p. 2
• Research on text-attributed graphs examines how LLMs can act as predictors, aligners, or enhancers alongside graph models.Textual attributes provide a setting for applying LLMs to graph data.Source: §2.2 · p. 2
• RAG enhances LLM generation by retrieving external knowledge and conditioning the model on that evidence without additional fine-tuning.Related efforts improve RAG through correction, verification, critique, and graph-based context.Source: §2.3 · p. 2
• GraphRAG methods use knowledge graphs as structured sources of contextual and factual grounding for relation-aware reasoning.They supply entity-centric textual descriptions as organized evidence.Source: §2.3 · p. 3

3.1 Notations

• Text-attributed graphs provide textual features for nodes, encoded as a node feature matrix X over textual corpora.The graph is represented as G = (V, E), with textual features T = {t1, t2, . . . , tN}.Source: §3.1 · p. 3

3.2 Message-passing graph neural networks

• Message-passing GNNs use permutation-invariant aggregation over adjacent nodes followed by an update function that combines the node representation with aggregated context.The update function ϕ is typically an MLP, while aggregation may use mean or sum.Source: §3.2 · p. 3
• GNN variants extend this basic framework with components such as attention mechanisms, advanced aggregation functions, and residual connections.Source: §3.2 · p. 3

3.3 Retrieval-augmented generation

• RAG retrieves a top-k set of relevant contexts from a corpus and conditions a language model on the query and retrieved contexts to generate an answer.The classical formulation contains a retriever and a generator; advanced systems may additionally use chunking and reranking.Source: §3.3 · p. 3

4.1.2 Label propagation as label-centric RAG

• Label propagation is a label-centric retrieval process in which nodes collect neighboring label signals and combine them through propagation before inference.Labeled nodes provide one-hot label embeddings, while unlabeled nodes contribute padding messages; labels can therefore guide retrieval and aggregation without leakage.Source: §4.1.2 · p. 4

4.2.1 Label-aware retrieval-augmented node embedding

• RTA encodes each node by augmenting its text with sampled structural-neighbor contexts and available label signals.A permutation-invariant combination produces contextual embeddings intended to reflect semantic and structural correlations.Source: §4.2.1 · p. 4

4.2 Present framework

• The framework aggregates retrieved features and label embeddings, then applies an MLP-style update for task-specific node prediction.Unlike conventional GNNs relying on static edges, RTA adaptively redefines connectivity according to semantic relevance and structural proximity.Source: §4.2 · p. 4, Figure 3 · p. 5, §4.2.1 · p. 5

4.2.2 Retrieval-augmented aggregation

• RTA constructs a retrieval-defined graph by combining semantic similarity from contextual embeddings with structural proximity derived from graph diffusion.Semantic retrieval can use approximate nearest-neighbor search such as FAISS, while structural retrieval uses personalized PageRank.Source: §4.2.2 · p. 5

Approximation

• A RAG-style top-k construction approximates a softmax-attention message-passing oracle with ℓ∞ error O(exp(−γu/τ)).The bound depends on the retrieval margin γu and attention temperature τ under regularity conditions.Source: §5 · p. 6

Connection to GNN aggregators

• When attention scores are constant, softmax attention becomes uniform averaging, matching mean aggregation in GCN and GraphSAGE.Sum aggregation differs only through degree-dependent scaling, so the message-level conclusion applies broadly to these GNN aggregators.Source: §5 · p. 6

Robustness

• Retrieved-context supervision imposes a smaller gradient penalty than individual outlier supervision when the outlier’s confident class conflicts with the ground-truth label.The theorem treats the query label as fixed during differentiation and compares the retrieved-context objective with the outlier’s individual cross-entropy.Source: §5 · p. 6

Datasets

• The evaluation covers six homophilic CSTAG datasets and four heterophilic university web-page graphs for text-attributed node classification.The datasets include Books, Electronics, Sports, Arxiv, Cornell, Texas, Wisconsin, and Washington graphs.Source: §6.1.1 · pp. 6–7

Baselines

• RTA is compared with standard GNNs, graph contrastive methods, vanilla LLMs, graph LLMs, and robust GNNs.The comparison includes models such as GCN, GAT, GraphSAGE, GraphMAE, GPT-4O, GLEM, LlaGA, RGCN, MedianGCN, SimPGCN, and ProGNN.Source: §6.1.2 · pp. 7–8

LLM-based Embedding Generation

• RTA uses a robustness-aware prompt that distinguishes consistent neighbor evidence from potentially misleading or adversarial information.The prompt aims to preserve target-node semantics while downweighting inconsistent neighbor signals.Source: §6.1.3 · p. 8

• RTA consistently outperforms traditional GNNs and graph contrastive learning methods by a large margin on homophilic and heterophilic datasets.Source: §6.2 · p. 9
• RTA’s simple MLP augmented with RAG mechanisms is more parameter-efficient than graph LLMs such as TAPE and LLaGA.Source: §6.2 · p. 9
• RTA achieves particularly strong improvements over graph LLMs on datasets with richer textual features and in heterophilic settings.Source: §6.2 · p. 9
• Vanilla LLMs perform poorly without fine-tuning, highlighting the need for graph-aware adaptation on text-attributed graphs.Source: §6.2 · p. 9

• The evaluation measures node-classification accuracy under test-time edge perturbations on Children, History, Photo, and Computers.Source: §6.3 · p. 9
• 56.7/79.3/80.3/84.5 accuracy: RTA achieves the best SGA-attack performance on Children/History/Photo/Computers.These results outperform the strongest baseline by clear margins.Source: §6.3 · p. 9
• Standard GNNs such as GCN and GAT collapse under SGA, while MedianGCN improves stability but remains substantially below RTA.Source: §6.3 · p. 9
• RTA’s robustness is attributed to retrieving task-relevant, redundant evidence that is less coupled to any specific adjacency.Source: §6.3 · p. 9

• The depth experiment directly tests whether RTA mitigates the performance degradation associated with deeper GNN architectures.Source: §6.4 · p. 10
• Standard GNN representations collapse as depth increases, causing significantly degraded performance beyond four layers.Source: §6.4 · p. 10
• RTA remains robust against oversmoothing and scales to deeper architectures without substantial performance loss.Source: §6.4 · p. 10
• RTA achieves state-of-the-art performance across all evaluated depths and increasingly larger margins as layers increase.Experiments use L ∈ {2, 4, 8, 16, 32} on the Children and History datasets.Source: §6.4 · p. 10

• RTA achieves significantly higher computational efficiency than GCN, GAT, GraphSAGE, and DGT on the Fitness dataset.Fitness is described as the largest dataset used in the experiments.Source: §6.5 · p. 10, Figure 6 · p. 10
• RTA reduces redundant computation by avoiding costly graph convolutions and iterative neighbor aggregation, supporting faster convergence and lower training time.Source: §6.5 · p. 10
• Both the number of retrieved text samples k1 and aggregation neighbors k2 affect downstream RTA performance.Setting k1 = 0 or k2 = 0 reduces RTA to simpler baselines without retrieved context or neighborhood aggregation.Source: §6.6.1 · p. 10
• Relatively small k1 and k2 values already provide strong performance, while larger values can reduce accuracy by adding irrelevant or redundant context.Source: §6.6.1 · p. 11
• Excess retrieval harms heterophilic datasets more strongly, where indiscriminate neighbors are more likely to introduce noise.Source: §6.6.1 · p. 11
• Removing either label-aware contextual embedding L-I or label-aware aggregation L-II consistently degrades performance.Source: §6.6.2 · p. 11
• Removing L-II causes more pronounced degradation on heterophilic graphs, while removing both label-aware components produces the largest overall drop.Source: §6.6.2 · p. 11
• The bge-en-icl retriever achieves the best performance across all eight evaluated benchmarks.Source: Table 5 · p. 11, §6.6.3 · p. 12

7 CONCLUSION

• RTA queries and aggregates task-relevant context from text-attributed nodes, reducing reliance on explicit message passing.The framework uses label-aware retrieval and propagation within an MLP-based architecture.Source: §7 · p. 12
• The paper formalizes the relationship between retrieval-based aggregation and standard message-passing GNNs.Its theory connects RAG-based aggregation to conventional message passing and provides robustness guarantees for label-aware retrieval.Source: §7 · p. 12
• RTA achieves state-of-the-art results across text-attributed graph benchmarks against strong GNN, LLM, and graph-LLM baselines.The reported evaluations cover multiple benchmark settings rather than a single dataset or model family.Source: §7 · p. 12
• RTA demonstrates improved scalability and robustness under adversarial perturbations while mitigating oversmoothing.These benefits are reported alongside its benchmark performance.Source: §7 · p. 12

Theoretical framework

• Message passing is analyzed as prediction over a retrieved context set followed by a permutation-invariant summarization.For a query node, the retrieved set is constructed by score-based Top-k retrieval.Source: APPENDIX · p. 13

Label-aware retrieval

• Label-aware retrieval uses labeled nodes as supervised evidence, while unlabeled nodes contribute fixed padding embeddings under the stated setup.Retrieved node features are augmented with label embeddings subject to boundedness assumptions.Source: APPENDIX · pp. 13–14

Attention approximation

• Top-k mean aggregation provides a sparse approximation to softmax-attention message passing under a retrieval-margin condition.The approximation error separates into attention leakage outside the retrieved set and non-uniform weighting within it.Source: APPENDIX · pp. 14–15

Retrieval assumptions

• RTA uses a generalized retrieval score combining semantic and structural relevance to construct the Top-k neighborhood.The retrieval margin is defined from nodes ordered by this score.Source: APPENDIX · p. 14

Connections to GNN layers

• Uniform softmax attention recovers mean aggregation, and sum aggregation differs only through degree-dependent scaling.Thus the message-level conclusion applies to GCN, GraphSAGE, and a broader class of message-passing GNNs.Source: APPENDIX · pp. 14–15

Attention approximation

• A larger retrieval margin suppresses leakage, while a smaller within-set score spread makes attention closer to uniform mean aggregation.These conditions correspond respectively to stable retrieval and a coherent retrieved set.Source: APPENDIX · p. 15

Robustness to outliers

• Retrieved-context supervision attenuates the optimization impact of mis-retrieved outliers whose confident class conflicts with the query label.When the outlier condition holds, the retrieved-context objective imposes a smaller gradient penalty than individual outlier supervision.Source: APPENDIX · p. 15
• The appendix concludes that label information can improve semantic coherence and retrieval precision while retrieved-context objectives remain robust to residual retrieval noise.This combines label-guided retrieval with attenuation of conflicting outlier influence.Source: APPENDIX · pp. 14–15