CS Paper Radar

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.LG cs.AI ·submitted 2026-08-27 07:25 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Message Passing Does More with Less for In-Context Learning on Graphs

cs.LG cs.SI ·2026-09-29 ·Dooho Lee, Jinmo Lee, Minho Jeong, Kijung Shin, Jaemin Yoo
code/data similarity 0.72
Abstract

Achieving strong performance with graph neural networks (GNNs) typically requires training and hyperparameter tuning for each dataset, incurring repeated costs and effort. Graph in-context learning (ICL) avoids this by using a single pretrained model to predict unknown node labels directly from labeled context nodes. Existing approaches, however, rely on dense attention across nodes, making inference increasingly expensive as graphs grow. In this work, we present Ephris, a new graph in-context learner built on sparse message passing, scaling linearly with the number of node-feature entries and graph edges. Ephris is pretrained entirely on synthetic graphs generated from structural causal models with diverse graph structures and relational dynamics, exposing the model to varied dependencies among topology, features, and labels. We evaluate Ephris on 51 node-classification datasets against 15 extensively tuned GNNs and existing graph ICL methods under both high- and low-label train/validation/test splits. Across both settings, Ephris ranks first on all four aggregate measures: Elo, improvability, average rank, and accuracy. Its inference cost remains comparable to training a single GNN once, while being over 10 times faster than previous graph ICL models. Together, these results advance the performance-runtime Pareto frontier, demonstrating that strong graph ICL does not require dense attention. Code and model weights are available at https://github.com/nums-ai/ephris.

0.25

Bridging Semantics and Structure: A Theoretically Grounded Framework for Link Prediction on TAGs

cs.AI ·2026-10-29 ·Chen Shao, Ruirui Wang, Tobias Kafer, Danai Koutra
publishedbenchmark similarity 0.72
Abstract · 33 pages. Accepted for publication in ACM Transactions on Knowledge Discovery from Data (TKDD)

Link prediction on text-attributed graphs (TAGs) is a fundamental problem with applications in knowledge discovery, recommendation and beyond. Recent progress has highlighted the promise of combining Graph Neural Networks (GNNs) with Language Models (LMs) in order to leverage the complementary structural and semantic signals. However, due to the distinct inductive biases of GNNs and LMs, the design of an optimal fusion strategy remains an open research question. In this work, we present Bridge-LP, an intuitive, simple, efficient and theoretically grounded framework that unifies graph and language representations. It is built around three theoretically-justified design components: (D1) jumping connection of textual proximity, which enables robust LM training; (D2) compressed embedding, which encodes neighborhood information long exploited by classical link prediction heuristics, thereby enriching structural signals in a learnable way; and (D3) cache embedding training strategy, which reduces computational complexity. Together, these mechanisms establish an end-to-end cross-modal framework that scales to large graphs while capturing richer graph-text interactions. We conduct an extensive empirical evaluation, comparing against 40 existing models across 9 diverse datasets. Experiments show that Bridge-LP consistently outperforms state-of-the-art approaches, delivering up to a 43.06% improvement in Mean Reciprocal Rank (MRR) and setting a new benchmark for language-graph integration.

0.32

Complementary Supervised and Self-Supervised Representations for Out-of-Distribution Graph Learning

cs.LG ·2026-10-06 ·Qingying Hao, Zikang Chen, Chuxuan Hu, Jinyuan Jia, Bo Li +2 more
similarity 0.69
Abstract

Out-of-distribution (OOD) generalization remains challenging for graph neural networks (GNNs), as graph distributions can vary substantially across time and domains. Supervised and self-supervised graph representation learning are guided by distinct objectives and offer different perspectives on graph representations. In this work, we study whether self-supervised representations (SSL) can provide complementary signals to improve supervised OOD node classification. We develop two backbone-agnostic frameworks that exploit such information at different stages of learning and prediction. Co-Train jointly learns supervised and SSL representations and adaptively integrates them during training, while Dual-Space Retrieval performs non-parametric prediction in the two representation spaces and combines their predictions through confidence-aware fusion at inference time. The supervised and SSL encoders are separately parameterized and need not share the same GNN architecture. We evaluate multiple GNN backbones and two distinct SSL objectives, DGI and GRACE, on four graph benchmarks spanning temporal and cross-domain distribution shifts. Extensive experiments show that Co-Train consistently outperforms strong supervised OOD baselines, while Dual-Space Retrieval achieves competitive performance as a flexible non-parametric alternative. Results across different backbones and SSL objectives, together with representation analyses and ablations, demonstrate that SSL representations provide complementary information to supervised representations and can improve OOD node classification across diverse settings.

0.19

Measuring the Influence of Modality-Specific Node Representations on Graphs

cs.SI cs.LGcs.MM ·2026-08-17 ·Xu Wang, Xunkai Li, Yinlin Zhu, Rong-Hua Li
benchmark similarity 0.68
Abstract

Multimodal attributed graphs combine graph structure with node text and image representations in recommendation and multimedia analysis. Graph predictors propagate these representations across connected nodes, so one input can change predictions at its own and nearby nodes. Measuring this distributed response reveals which modality-specific inputs a trained model relies on and how predictor design changes that reliance. We study influence measurement for modality-specific node representations. Given an encoded graph, a trained predictor, a training split, and fixed candidate representations, the task outputs one influence score per candidate and separate text and image rankings. We score a candidate by replacing it with its modality's training-node mean and comparing the original and changed predictions. Existing feature attribution and data valuation generally target one output, training examples, whole nodes, or graph elements rather than prediction changes across graph nodes. Our empirical study shows that nearby-node responses contain information missed by source-only scores and simple proxies, while response magnitude alone does not identify which class changes support the task. Guided by these observations, we propose MoGI (Modality-specific Graph Influence). It propagates training labels to define task direction, reads the same replacement response for the favored class and full class distribution, and averages the resulting ranks. MoGI requires no predictor retraining or learned scoring parameters. Under a shared five-dataset, eight-predictor benchmark, it achieves the largest aggregate held-out loss increase against all five external methods at every tested ranking cutoff.

0.09

DeKoR: Decomposed Knowledge Routing for Efficient GNN--LLM Fusion

cs.LG ·2026-10-10 ·Peiyuan Li, Yongqi Huang, Jitao Zhao, Di Jin, Dongxiao He
similarity 0.68
Abstract · 19 pages

Large Language Models (LLMs) have shown strong potential for text-attributed graph learning by leveraging rich pre-trained knowledge and language understanding capabilities. Combining LLMs with Graph Neural Networks (GNNs) offers a promising paradigm for expanding the modeling capabilities of graph learning. However, LLMs and GNNs follow distinct learning paradigms, leading to a pronounced mismatch between their knowledge spaces. Such discrepancies make effective knowledge fusion nontrivial. Moreover, existing methods often incur substantial additional computation for only limited performance gains. To address these challenges, we propose DeKoR, an efficient framework for GNN and LLM knowledge fusion. To enable efficient knowledge transfer, DeKoR decomposes LLM knowledge into complementary local and global views and uses the LLM as an offline teacher to distill them into lightweight experts. To enable selective knowledge fusion, an adaptive router learns how much each node should rely on each expert. Extensive experiments on multiple benchmarks demonstrate that DeKoR outperforms existing baselines on both node and subgraph classification, achieving superior effectiveness and efficiency.

0.29

QUARTET: Quad-branch cross-Attention and Random-walk Traces for Enhancing Transformers on Relational Graphs

cs.LG cs.AI ·2026-09-22 ·Kyaw Hpone Myint, Nan Jiang, Xiang Li, Zhe Wu, Alexandre G. R. Day +2 more
published similarity 0.68
Abstract · This work has been accepted for main conference track at Learning on Graphs (LoG) 2026

Relational Deep Learning (RDL) models multi-table databases as heterogeneous temporal graphs, and graph transformers currently achieve state-of-the-art performance on benchmarks like RelBench. However, the current leading model, RelGT, suffers from two key limitations: its random local sampler yields loosely connected subgraphs that hinder message passing, and its global attention module relies on a single, seed-feature-based memory that ignores broader macro-level dynamics. To overcome these limitations, we introduce QUARTET, an expressive graph transformer architecture that applies full self-attention on local subgraphs while enriching global context through cross-attention branches. Specifically, QUARTET employs a Causal Random Walk (CRW) sampler based on recency-truncated Personalized PageRank (PPR) to extract compact, hub-robust, and densely connected local subgraphs without temporal leakage. Concurrently, a quad-branch cross-attention module integrates global context from four complementary perspectives: seed feature, seed topology, temporal dynamics, and collaborative dynamics. Across the RelBench v1 classification tasks, QUARTET consistently matches or outperforms the current state-of-the-art graph transformer baselines (HGT and RelGT). Ablation studies confirm that the CRW sampler significantly enriches local neighborhood quality, while the global branches provide essential, task-specific predictive gains.

0.21

Contrastive Adversarial Training for Robust Graph Neural Networks under Label Poisoning

cs.LG cs.AI ·2026-10-17 ·Manshika Charvi Bissessur, Melis Ilayda Bal, Michael Muehlebach
top venue similarity 0.68
Abstract

Graph Neural Networks (GNNs) are effective for modeling relational data but are vulnerable to label poisoning, where a small number of corrupted training labels can propagate errors across the graph via message passing. Despite this risk, defenses against label poisoning remain underexplored: existing methods are primarily designed for label noise and often rely on robust losses or heuristic data cleaning that fail to distinguish adversarial poisoning from naturally hard examples. In this paper, we propose CoLAT (Contrastive Label-flipping for Adversarial Training), a novel contrastive adversarial training framework tailored for robust node classification on graphs. The core of our approach is a structure-aware detection model that uses contrastive learning to identify label-structure inconsistencies. Unlike prior contrastive methods that focus on representation learning, CoLAT leverages contrastive embeddings to select high-risk nodes that guide adversarial label-flipping during training. This alternating optimization not only performs structure-aware adversarial training but also implicitly sanitizes some corrupted labels, improving robustness against diverse attacks from the literature. Extensive experiments on multiple benchmarks show that CoLAT consistently outperforms existing defenses under various poisoning intensities while scaling efficiently to large graphs.

0.32

PreGress: Ranking-Native Pre-training and Prompting for Graph Node Ranking

cs.IR cs.LG ·2026-08-10 ·Lujie Ban, Jiasheng shi, Yingli Zhou, Kaiwen Xue, Daiyin Wang +3 more
similarity 0.68
Abstract

Node ranking is a fundamental problem in graph information retrieval, measuring the relative importance of nodes and supporting a wide range of applications such as influence analysis, recommendation, and graph-based retrieval augmented generation. However, exact computation of graph-based ranking measures is often computationally prohibitive at scale. Existing GNN-based ranking methods provide scalable approximations, but they are typically tailored to individual ranking criteria and require retraining for each downstream task, which limits their transferability and efficiency. Recent graph pre-training approaches aim to enable knowledge transfer across tasks, yet their learning objectives are largely misaligned with node ranking, resulting in suboptimal adaptability to ranking-oriented applications. To address these limitations, we propose PreGress, the first ranking-native pre-training and prompting framework for supporting a wide range of node ranking tasks. PreGress performs multi-task pre-training using our carefully designed objectives, including degree centrality prediction and attribute reconstruction, to jointly capture structural and attribute information. To support heterogeneous ranking criteria, we design lightweight, task-specific prompt modules that adapt a frozen ranking backbone to downstream tasks without full retraining. Experiments on six public graphs and two real-world query-to-item benchmarks---Yelp2018 and MovieLens-100K---together with a controlled five-criterion graph-access study demonstrate strong ranking quality with low task-specific state overhead.

0.04