PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning

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

arXiv:2608.26732v1cs.LGcs.AI

TL;DR

The paper asks why neighborhood aggregation helps beyond node-wise MLPs despite message passing’s computational and structural vulnerabilities. It recasts GNN layers as retrieval-augmented prediction, proposes label-aware RTA, and reports competitive or stronger benchmark performance with improved efficiency and robustness.

  • Problem

    It remains unclear why neighborhood aggregation reliably outperforms node-wise MLPs, while message passing can be computationally expensive and sensitive to imperfect graph structures.

  • Method

    RTA replaces explicit recursive message passing with an MLP-based pipeline using label-aware contextual encoding, embedding and structural retrieval, and label-enhanced aggregation.

  • Results

    RTA matches or outperforms strong GNN and graph-learning baselines on multiple text-attributed graph benchmarks while improving efficiency and robustness.

  • Takeaways & Limitations

    The work supports retrieval-defined computation graphs as a practical alternative to fixed-edge diffusion for graph representation learning.

  • Takeaways & Limitations

    RTA uses only training labels for label-aware guidance, replacing labels with padding for validation, test, and unlabeled nodes to avoid leakage.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper unifies GNN message passing and retrieval-augmented prediction by viewing neighborhood context as retrieved evidence. It then proposes RTA, a label-aware retrieval framework supported by theoretical guarantees and benchmark results.

  • 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.

2 RELATED WORK

The related work connects message-passing GNNs, language-model learning over text-attributed graphs, and retrieval-augmented generation. It positions the paper as studying their shared computational structure rather than treating them as isolated areas.

  • 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.
  • 2 RELATED WORK: 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.
  • 2 RELATED WORK: 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.
  • 2 RELATED WORK: 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.
  • 2 RELATED WORK: 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.

3 PRELIMINARY

This section introduces the shared computational patterns underlying message-passing GNNs and retrieval-augmented generation, along with the notation for text-attributed graphs. It describes how GNNs aggregate neighboring node information and how RAG retrieves contexts before generating outputs.

  • 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}.
  • 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.
  • 3.2 Message-passing graph neural networks: GNN variants extend this basic framework with components such as attention mechanisms, advanced aggregation functions, and residual connections.
  • 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.

4 PRESENT WORK: RTA

RTA reframes graph learning as retrieval-augmented prediction, combining contextual text encoding, adaptive semantic-structural retrieval, and label-aware aggregation in an MLP framework. It replaces fixed-edge multi-hop message passing with retrieval-defined computation graphs.

  • 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.
  • 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.
  • 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.
  • 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.

5 THEORETICAL ANALYSIS

The theoretical analysis links top-k retrieval to softmax-attention message passing and explains why retrieved-context supervision can be tolerant of mis-retrieved outliers. These results extend to common mean and sum aggregation schemes under stated conditions.

  • 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.
  • 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.
  • 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.

6 EXPERIMENTS

RTA is evaluated for node classification across homophilic and heterophilic text-attributed graphs against GNN, self-supervised, LLM, graph-LLM, and robust-GNN baselines. The reported results emphasize competitive performance, efficiency, and robustness-aware embedding design.

  • 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.
  • 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.
  • 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.

6.2 Main results

Across homophilic and heterophilic benchmarks, RTA consistently outperforms conventional GNNs, graph contrastive methods, and graph LLM baselines. Its retrieval-augmented MLP also achieves these gains with a parameter-efficient design.

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

6.3 Robustness against adversarial attacks

RTA remains robust under the SGA structure-perturbation attack, outperforming both standard GNNs and robust defenses across four benchmark graphs. Its retrieved context is less tied to any single potentially poisoned neighborhood.

  • The evaluation measures node-classification accuracy under test-time edge perturbations on Children, History, Photo, and Computers.
  • 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.
  • Standard GNNs such as GCN and GAT collapse under SGA, while MedianGCN improves stability but remains substantially below RTA.
  • RTA’s robustness is attributed to retrieving task-relevant, redundant evidence that is less coupled to any specific adjacency.

6.4 Robustness against oversmoothing

As network depth increases, standard GNNs suffer severe oversmoothing and degraded performance, whereas RTA remains effective across deeper architectures. RTA achieves state-of-the-art performance at every evaluated depth.

  • The depth experiment directly tests whether RTA mitigates the performance degradation associated with deeper GNN architectures.
  • Standard GNN representations collapse as depth increases, causing significantly degraded performance beyond four layers.
  • RTA remains robust against oversmoothing and scales to deeper architectures without substantial performance loss.
  • 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.

6.5 Efficiency comparison

RTA is presented as a more computationally efficient alternative to standard GNNs, avoiding repeated graph convolutions and neighbor aggregation. Its retrieval and aggregation settings also show that modest, relevant context is preferable to excessive retrieval.

  • 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.
  • RTA reduces redundant computation by avoiding costly graph convolutions and iterative neighbor aggregation, supporting faster convergence and lower training time.
  • 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.
  • Relatively small k1 and k2 values already provide strong performance, while larger values can reduce accuracy by adding irrelevant or redundant context.
  • Excess retrieval harms heterophilic datasets more strongly, where indiscriminate neighbors are more likely to introduce noise.
  • Removing either label-aware contextual embedding L-I or label-aware aggregation L-II consistently degrades performance.
  • Removing L-II causes more pronounced degradation on heterophilic graphs, while removing both label-aware components produces the largest overall drop.
  • The bge-en-icl retriever achieves the best performance across all eight evaluated benchmarks.

7 CONCLUSION

The paper presents RTA as a retrieval-augmented alternative to message passing for text-attributed graphs, combining label-aware retrieval with MLP-based prediction. It provides theoretical and empirical evidence for effectiveness, scalability, and robustness.

  • 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.
  • 7 CONCLUSION: 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.
  • 7 CONCLUSION: 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.
  • 7 CONCLUSION: RTA demonstrates improved scalability and robustness under adversarial perturbations while mitigating oversmoothing.These benefits are reported alongside its benchmark performance.

APPENDIX

The appendix establishes when Top-k retrieval with mean aggregation approximates softmax-attention message passing and why label-aware retrieved-context supervision is tolerant of mis-retrieved outliers. The analysis connects these guarantees to retrieval margin, score coherence, and classical GNN aggregators.

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Robustness to outliers: 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.
Loading 2608.26732v1…