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

Ying Zhang; Hang Yu; Haipeng Zhang; Peng Di

cs.LGMar 16, 2026

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

Authors: Ying Zhang, Hang Yu, Haipeng Zhang, Peng Di

Organizations: Ant Group · ShanghaiTech University

Abstract

Text-rich graphs, which integrate complex structural dependencies with abundant textual information, are ubiquitous yet remain challenging for existing learning paradigms. Conventional methods and even LLM-hybrids compress rich text into static embeddings or summaries before structural reasoning, creating an information bottleneck and detaching updates from the raw content. We argue that in text-rich graphs, the text is not merely a node attribute but the primary medium through which structural relationships are manifested. We introduce RAMP, a Raw-text Anchored Message Passing approach that moves beyond using LLMs as mere feature extractors and instead recasts the LLM itself as a graph-native aggregation operator. RAMP exploits the text-rich nature of the graph via a novel dual-representation scheme: it anchors inference on each node's raw text during each iteration while propagating dynamically optimized messages from neighbors. It further handles both discriminative and generative tasks under a single unified generative formulation. Extensive experiments show that RAMP effectively bridges the gap between graph propagation and deep text reasoning, achieving competitive performance and offering new insights into the role of LLMs as graph kernels for general-purpose graph learning.

Figures & tables

Figure 1: Illustration of message passing paradigms on text-rich graphs. Given a text-rich graph (left) where each node is associated with long textual content, (i) traditional GNNs compress node texts into a compact representation during aggregation, whereas (ii) explicit aggregation paradigm retains original text for LLM reasoning.

Figure 2: Architecture of RAMP. Given a text-rich graph and a query, we wrap node contents into a token sequence and perform parallel decoding on all nodes to obtain their summaries. Hidden states of summary tokens are stored in a memory table to initialize the next layer, realizing (a) layer-wise message-passing; the final decoder aggregates graph information for (b) the answer generation.

GNN operation	RAMP counterpart
Node representation $\mathbf{h}_{i}^{(\ell)}$	Summary token sequence $\mathbf{S}_{i}^{(\ell)}=[s_{i,1}^{(\ell)},\dots,s_{i,n}^{(\ell)}]$
Neighbor message $\{\mathbf{h}_{j}^{(\ell)}:j\in\mathcal{N}(i)\}$	Concatenation of neighbor tokens $\mathbf{S}_{j}^{(\ell)}$ for $j\in\mathcal{N}(i)$
Aggregation function $\text{GNN}(\mathbf{h}_{i}^{(\ell)},\{\mathbf{h}_{j}^{(\ell)}\})$	LLM reasons over $[\mathbf{S}_{j_{1}}^{(\ell)}\\|\cdots\\|\mathbf{S}_{j_{m}}^{(\ell)}\\|\mathbf{X}_{i}\\|\mathbf{S}_{i}^{(\ell)}]$
Layer-wise propagation	Passing semantic messages via summary tokens $\mathbf{S}_{i}^{*}$

Table 1: Connection between classical GNN message passing and the proposed RAMP.

	Perplexity ${}_{\textit{self}}$ $\downarrow$	Perplexity ${}_{\textit{nbr}}$ $\downarrow$
Qwen-2.5-7B-Instruct	21.72*	-
RAMP mp=1,ρ=0.05	11.36	20.68
RAMP mp=1,ρ=0.1	9.17	20.87
RAMP mp=2,ρ=0.1	8.93	22.97
RAMP mp=2,compact	25.57	25.61

Table 2: Evaluation for pre-trained RAMP. Qwen-2.5-7B-Instruct (21.72 ∗ ) is the backbone reference; its value is the raw language modeling perplexity obtained by directly continuing node text.

Method	Cora	Citeseer	PubMed	History	Photo	Arxiv
MLP	69.00	59.35	75.55	77.71	47.56	57.23
GCN ( Zhang et al., 2019 )	82.29	70.16	81.92	80.55	70.14	66.52
GAT ( Veličković et al., 2017 )	83.03	71.29	80.78	78.93	66.18	67.76
GraphSAGE ( Hamilton et al., 2017 )	83.21	70.81	82.94	80.72	73.82	67.97
BERT ( Devlin et al., 2019 )	80.99	71.93	91.75	80.94	58.34	65.64
RoBERTa ( Liu et al., 2019 )	76.93	70.48	91.37	79.42	57.27	66.72

Table 3: Performance comparison of different methods on node classification tasks (Accuracy %

\uparrow

). All baselines are evaluated under our unified setting with identical data splits. We highlight the best results in bold and the second best with underline .

Method	ExplaGraphs
Qwen-2.5-7B-Instruct	93.50
GNP ( Tian et al., 2024 )	87.04
G-Retriever ( He et al., 2024 )	87.05
GRAG ( Hu et al., 2024 )	88.05
Align-GRAG Xu et al. (2025)	89.92
RAMP-7B	93.86

Table 4: Evaluation of RAMP on GraphQA tasks.

Setting	Cora	Citeseer
RAMP (No Shuffle)	84.87	74.83
Neighbor-Order Shuffle	84.81 $\pm$ 0.08	74.73 $\pm$ 0.01
Cross-Node Shuffle	84.32 $\pm$ 0.14	74.41 $\pm$ 0.01

Table 5: Impact of Shuffling (Accuracy %

\uparrow

). We report the mean and standard deviation over three shuffling runs.

Figure 3: Scalability on Cora. (a) Accuracy and absolute inference time for RAMP. (b) Inference time scaling for each method, independently normalized to its performance in the smallest bucket (i.e., bucket

<25

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	#Nodes	#Edges	#Classes	Avg. D	Domain	Node Text
Cora	2,708	10,858	7	4.01	Computer Science	Paper titles and abstracts
Citeseer	3,327	9,464	6	2.84	Computer Science	Paper titles and abstracts
PubMed	19,717	88,648	3	4.49	Biomedical	Paper titles and abstracts
History	41,551	503,180	12	12.11	E-commerce	Item titles and descriptions
Photo	48,362	873,782	12	18.07	E-commerce	Item titles and reviews
Arxiv	169,343	1,166,243	40	6.89	Computer Science	Paper titles and abstracts

Appendix

Table 6: Dataset Statistics. “Avg. D” means the average node degree. We additionally provide the domain and the composition of node text.

Figure 4: Illustration of the graph transformation process for RAMP in GraphQA task. (a) An example of two arguments with a “Support” relation from the ExplaGraphs dataset. (b) The original graph structure where relations are represented as labeled edges. (c) Our transformed graph, where each original edge is reified into a dedicated node (orange), creating a bipartite-like structure that allows RAMP to process textual relational information more effectively.

$\rho$	Perplexity ${}_{\textit{self}}$ $\downarrow$	Perplexity ${}_{\textit{nbr}}$ $\downarrow$
0.01	16.39	21.19
0.02	13.66	21.14
0.05	11.36	20.68
0.10	9.18	20.88

Appendix

Table 7: Impact of compression ratio

\rho

on reconstruction perplexity (Cora,

mp\!=\!1

Method	Cora	PubMed
Qwen-2.5-7B-Instruct	82.65	90.79
RAMP mp=1,ρ=0.1	83.21	92.11
RAMP mp=2,ρ=0.1	84.87	93.68

Appendix

Table 8: Impact of message-passing rounds (Accuracy %

\uparrow

Method	Cora	Citeseer	PubMed
RAMP mp=2,compact	55.71	68.22	93.43
RAMP mp=2,ρ=0.1	84.87	74.83	93.68

Appendix

Table 9: Downstream ablation of raw-text anchoring on node classification (Accuracy %

\uparrow

). RAMP mp=2,compact denotes the variant where raw text is used only at initialization, and subsequent message passing is performed solely through propagated summary tokens.

Setting	Citeseer Acc.
RAMP (Correct Topology)	74.83
RAMP (Within-Subgraph Shuffle)	74.41 $\pm$ 0.01
Fine-tuned Backbone (No Topology)	74.35
RAMP (Cross-Subgraph Shuffle)	73.11 $\pm$ 0.06

Appendix

Table 10: Impact of radical topology perturbation on Citeseer (Accuracy %). The Within-Subgraph Shuffle here is equivalent to Cross-Node Shuffle in Tab. 5 of the main text.

Figure 5: Scalability on PubMed. (a) Accuracy and absolute inference time for RAMP. (b) Inference time scaling for each method, independently normalized to its performance in the smallest bucket (i.e., bucket

<10

Paper Title	Intermediate Output (penultimate round KV)	Final Output (last round KV)	Ground Truth
Unsupervised Learning Using MML	This paper should be classified into: Theory methods	This paper should be classified into: Probabilistic_Methods	This paper should be classified into: Probabilistic_Methods
First Order Regression	This paper should be classified into: Theory	This paper should be classified into: Rule_Learning	This paper should be classified into: Rule_Learning
First Order Regression: Applications in Real-World Domains	This paper should be in the rule-based category as it deals with rule based machine learning	This paper should be classified into: Rule_Learning	This paper should be classified into: Rule_Learning
Probably Approximately Optimal Derivation Strategies	This paper should be classified into: Theorys category: theory abstract: an paper describes a pao algorithm that first uses mu set of training examples to approximate these probability values and then uses these estimates to produce mu “probably approximately optimal” strategy that is given any ; ffi > 0, pao produces mu strategy whose cost is within of mu cost of mu optimal strategy with probability greater …	This paper should be classified into: Theory	This paper should be classified into: Theory
A Decision Tree System for Finding Genes in DNA	This paper should be in theory category, it describes a decision tree system for finding genes in vertebrate dna sequences, and uses new methods for identifying start codons, donor sites, and acceptor sites, and brings them together in a frame sensitive dynamic programming algorithm that findss the minimum segmentation of a dna sequence into coding and …	This paper should be classified into: Neural_Networks	This paper should be classified into: Neural_Networks
Space-Frequency Localized Basis Function Networks for Nonlinear System Estimation and Control	This paper should be classified into: Neural This paper deals with the on-line generation of nonparametric models for nonlinear systems using tools from multiresolution analysis and wavelet theory. It extendss earlier results on adaptive control and identification of nonparametric systems using wavelet basis functions to on-line generation of nonparametric models for nonparametric systems with wavelet basis functions …	This paper should be classified into: Neural_Networks	This paper should be classified into: Neural_Networks

Appendix

Table 11: Examples showing generations from different message-passing rounds in RAMP. While only the final round is supervised during training, we observe that the penultimate round KV also produces meaningful outputs. Comparisons across rounds reveal intermediate reasoning behaviors, occasional error correction, and in some cases error propagation. Italic text indicates predictions that do not match the ground truth.

Explore similar work

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning
May 11, 2026Dario VajdaLLM Reasoning with Graphs Text-Attributed Graph Learning
Faculty of Computer and Information Science University of Ljubljana
GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL
Aug 27, 2026Zike Yuan, Han Zhang, Jianzhi Yan +10LLM Reasoning with Graphs Language Model Robustness
Harbin Institute of Technology, Shenzhen, China · Peng Cheng Laboratory, Shenzhen, China · Xidian University, Xi’an, China
Position: How can Graphs Help Large Language Models?
May 4, 2026Xiyuan Wang, Yi Hu, Yanbo Wang +2LLM Grounding Knowledge Augmentation for Language Models
Institute for Artificial Intelligence, Peking University, Beijing 100871, China · School of Computer Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China

May 11, 2026J/K move · Enter open · S save

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning

Dario Vajda

Faculty of Computer and Information Science University of Ljubljana

LLM Reasoning with Graphs Text-Attributed Graph Learning Graph Transformer LLM Reasoning LLMs for Graph Learning

Open paper AskPDF arXiv

Using Large Language Models (LLMs) to process graph-structured data is an active research area, yet current state-of-the-art approaches typically rely on multi-step pipelines with Graph Neural Network (GNN) encoders that compress rich textual attributes into solitary tokens, creating a significant semantic bottleneck. In this paper, we introduce the Graph Transformer Language Model (GTLM), a novel architecture that enables pretrained LLMs to natively process graph topologies while entirely eliminating this compressive bottleneck. GTLM is exceptionally parameter-efficient: by injecting graph-aware attention biases directly into the LLM's attention modules, it introduces only 0.015% additional parameters relative to the base model. We theoretically prove that our bidirectional attention prefix preserves node permutation equivariance while maintaining exact backward compatibility with the pretrained base model. Extensive evaluations demonstrate that a 1B-parameter GTLM matches or exceeds the performance of 7B-parameter state-of-the-art models on standard Text-Attributed Graph benchmarks, while significantly surpassing baselines on GraphQA. Finally, we demonstrate that GTLM attention heads implicitly learn to simulate message passing, explaining its superior performance on algorithmic tasks. This paradigm shift enables true algorithmic reasoning within LLMs and provides a scalable foundation for next-generation GraphRAG and relational deep learning.

Abstract

Explore similar work

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning

GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL

Position: How can Graphs Help Large Language Models?