Organizations: Beijing University of Posts and Telecommunications, Beijing, China · Beihang University, Beijing, China · China Telecom Bestpay, Beijing, China
The remarkable success of large language models (LLMs) has motivated researchers to adapt them as universal predictors for various graph-related tasks, with the ultimate goal of developing a graph foundation model that generalizes diverse scenarios. The key challenge is to align graph data with language spaces so that LLMs can better comprehend graphs. As a popular paradigm, Graph-Tokenizing LLMs (GTokenLLMs) encode complex structures and lengthy texts into a graph token sequence, and then align them with text tokens via language instructions tuning. Despite their initial success, our information-theoretic analysis reveals that existing GTokenLLMs rely solely on text supervision from language instructions, which achieve only implicit graph-text alignment, resulting in a text-dominant bias that underutilizes graph context. To overcome this limitation, we first prove that the alignment objective is upper-bounded by the mutual information between the input graphs and their hidden representations in the LLM, which motivates us to improve this upper bound to achieve better alignment. To this end, we further propose a reconstructive graph instruction tuning pipeline, RGLM. Our key idea is to reconstruct the graph information from the LLM's graph token outputs, explicitly incorporating graph supervision to constrain the alignment process. Technically, we embody RGLM by exploring three distinct variants from two complementary perspectives: RGLM-Decoder from the input space; RGLM-Similarizer and RGLM-Denoiser from the latent space. Additionally, we theoretically analyze the alignment effectiveness of each variant. Extensive experiments on various benchmarks and task scenarios validate the effectiveness of the proposed RGLM, paving the way for new directions in GTokenLLMs' alignment research.
Figures & tables
Figure 1. (a) Typical graph instruction tuning methods follow an LLM-centric design that solely leverages text supervision. (b) RGLM designs extra reconstructive graph tasks to explicitly incorporate graph supervision into the tuning process.
Figure 2. Neighbor detail template for graph serialization ( Chen et al., 2024b ) .
Figure 3. (a) Overview of RGLM. Given an input TAG, RGLM aims to reconstruct the graph information from the LLM’s graph token outputs, explicitly incorporating graph supervision to constrain the alignment process. (b) Decoder variant directly reconstructs the raw node features and topology in the input space. (c) Similarizer and (d) Denoiser variants reconstruct latent node representations of pre-trained GNNs via the cosine-similarity and denoising strategy, respectively.
Method
Dataset
Cora
Pubmed
OGBN-Arxiv
Reddit
Rank
Metric
Acc
F1
Acc
F1
Acc
F1
Acc
F1
Acc
F1
GNNs
GCN
89.30
87.95
89.48
89.04
73.83
54.97
63.19
62.49
5
6
GraphSAGE
87.82
86.77
90.54
90.51
74.47
56.41
58.51
58.41
10
8
GAT
87.08
86.32
88.11
87.60
74.39
57.71
61.78
65.38
9
5
DIFFormer
85.60
84.31
81.60
81.94
58.80
42.44
55.30
55.09
15
14
UniMP
87.82
86.32
90.34
90.17
70.96
53.24
59.55
59.53
11
10
Table 1. Node classification results under supervised settings. Best are bolded, and runner-up are underlined. “OOM” indicates out-of-memory, exceeding the A800’s 80 GB limit. “Rank” represents the overall ranking on all datasets.
Figure 4. Ablation study on the node classification task across different datasets, where accuracy is reported for each variant.
Figure 5. Ablation study on the link prediction task across different datasets, where accuracy is reported for each variant.
Method
Dataset
Cora
Pubmed
Reddit
Metric
Acc
F1
Acc
F1
Acc
F1
Baselines
GCN
84.26
83.91
90.00
89.98
74.38
73.85
UniMP
71.62
70.92
80.76
80.54
73.09
72.53
GRACE
70.44
69.19
81.74
81.56
61.68
60.88
GraphGPT
59.85
59.85
73.60
73.39
56.69
27.19
LLaGA
82.21
79.66
91.78
91.88
79.73
76.60
Table 2. Link prediction results under supervised settings. Best are bolded, and runner-up are underlined.
Method
Training set
Cora+Pubmed
Test set
Cora
Pubmed
Metric
Acc
F1
Acc
F1
Baselines
GCN
85.61
84.16
85.07
84.29
GraphSAGE
86.35
86.21
89.27
89.12
GAT
83.03
82.29
86.51
85.99
UniMP
86.35
85.21
89.20
89.14
Table 3. Node classification results under multi-dataset training. Best are bolded, and runner-up are underlined.
Figure 6. Zero-shot accuracy on node classification and link prediction tasks, where models are trained on the OGBN-Arxiv and evaluated on unseen Cora and Pubmed.
Figure 7. Attention distribution over graph tokens for different methods, where the attention scores are log-scaled.
Figure 8. Time complexity (left) and resource cost (right) analysis of different RGLM variants.
Figure 9. Compatibility analysis of different RGLM variants on base LLMs, where accuracy is reported for each variant.
Figure 10. Analysis of the hyper-parameter λs and λf in the RGLM-Decoder variant.
Figure 11. Analysis of the hyper-parameter λl in the RGLM-Similarizer and RGLM-Denoiser variants.
The remarkable success of large language models (LLMs) has motivated researchers to adapt them as universal predictors for various graph tasks. As a widely recognized paradigm, Graph-Tokenizing LLMs (GTokenLLMs) compress complex graph data into graph tokens and treat them as prefix tokens for querying LLMs, leading many to believe that LLMs can understand graphs more effectively and efficiently. In this paper, we challenge this belief: Do GTokenLLMs fully understand graph tokens in the natural-language embedding space? Motivated by this question, we formalize a unified framework for GTokenLLMs and propose an evaluation pipeline, GTEval, to assess graph-token understanding via instruction transformations at the format and content levels. We conduct extensive experiments on 6 representative GTokenLLMs with GTEval. The primary findings are as follows: (1) Existing GTokenLLMs do not fully understand graph tokens. They exhibit over-sensitivity or over-insensitivity to instruction changes, and rely heavily on text for reasoning; (2) Although graph tokens preserve task-relevant graph information and receive attention across LLM layers, their utilization varies across models and instruction variants; (3) Additional instruction tuning can improve performance on the original and seen instructions, but it does not fully address the challenge of graph-token understanding, calling for further improvement.
Zhongjian Zhang, Yue Yu, Mengmei Zhang +3
Beijing University of Posts and Telecommunications · China Telecom Bestpay · Beihang University
Leveraging Graph Neural Networks (GNNs) as graph encoders and aligning the resulting representations with Large Language Models (LLMs) through alignment instruction tuning has become a mainstream paradigm for constructing Graph Language Models (GLMs), combining the generalization ability of LLMs with the structural modeling capacity of GNNs. However, existing GLMs that adopt GNNs as graph encoders largely overlook the problem of aligning GNN-encoded representations across domains and tasks with the LLM token space to obtain unified graph tokens, thereby limiting their ability to generalize across diverse graph data. To bridge this gap, we aim to incorporate a multi-domain, multi-task GNN encoder into GLMs and align its representations with LLMs to enable multi-domain, multi-task graph alignment instruction tuning. This alignment problem remains underexplored and poses two key challenges: 1) learning GNN-encoded representations that are simultaneously generalizable across domains and tasks and well aligned with textual semantics is difficult, due to substantial variations in graph structures, feature distributions, and supervision signals, together with the lack of textual-semantic alignment guidance in task-specific GNN training; 2) diverse graph data and task-specific instructions can exhibit different degrees of compatibility with the LLM token space during instruction tuning, leading to varying alignment difficulty and rendering a fixed alignment strategy suboptimal. To tackle these challenges, we propose UniGraphLM, a Unified Graph Language Model that incorporates a multi-domain, multi-task GNN encoder to learn generalizable graph representations aligned with textual semantics, and then adaptively aligns these representations with the LLM.
Graph Language Models (GLMs) have become a promising direction for adapting Large Language Models (LLMs) to graph learning tasks. By transforming graph topology and node information into graph tokens, GLMs allow LLMs to jointly process structured graph inputs and textual instructions. Yet, it remains unclear how LLMs internally interpret these graph tokens and whether graph tokens act as meaningful carriers of graph structure. In this work, we analyze how LLMs process graph information through graph-token behavior in representative GLM architectures. Findings. We find that the internal saliency of graph tokens in GLMs is not equivalent to graph information utilization. Graph sink tokens consistently emerge as activation-level outliers: they can be identified by massive activation values along a small set of hidden-state dimensions and are biased toward early graph-token positions. However, this activation-level saliency does not imply that these tokens are the main carriers of graph information. Unlike classical attention sinks in language and vision-language models, graph sink tokens do not necessarily attract the largest attention weights from query tokens. Through pruning, repositioning, and swapping interventions, we show that graph sink tokens are not the most important semantic or structural tokens for downstream prediction. Implications. Together, these results suggest that after current GLMs map graph structure into the LLM token space, the resulting graph-token representations do not naturally form a fully usable topology-aware internal representation; instead, they exhibit a decoupling between activation-level saliency and graph-semantic utility. This decoupling points to limitations in existing graph-token construction, placement, and alignment mechanisms.