Toward Graph-Tokenizing Large Language Models with Reconstructive Graph Instruction Tuning
Problem Statement
Building graph foundation models requires LLMs to genuinely comprehend graph structure, not just mimic textual answers, but current Graph-Tokenizing LLMs are trained solely with text-based instruction losses, so graph context is underutilized despite being encoded into tokens. This limits the generality and reliability of LLMs as universal graph predictors across diverse graph tasks and domains.
Key Novelty
- Information-theoretic diagnosis showing existing GTokenLLMs achieve only implicit graph-text alignment due to text-only supervision, causing a text-dominant bias
- Theoretical proof that the alignment objective is upper-bounded by the mutual information between input graphs and their hidden LLM representations, giving a principled optimization target
- RGLM: a reconstructive graph instruction tuning pipeline that adds explicit graph supervision by reconstructing graph information from the LLM's graph token outputs
- Three complementary variants (RGLM-Decoder in input space; RGLM-Similarizer and RGLM-Denoiser in latent space) each with theoretical analysis of alignment effectiveness
Evaluation Highlights
- Extensive experiments across multiple graph benchmarks and task scenarios demonstrate consistent effectiveness of RGLM over existing GTokenLLM baselines
- Theoretical analysis complements empirical results by characterizing the alignment tightness achieved by each of the three RGLM variants
Signal Assessment
Methodology
- Formulate graph-text alignment in GTokenLLMs information-theoretically and prove it is upper-bounded by mutual information between input graphs and LLM hidden representations
- Diagnose that existing methods rely only on implicit text supervision, leaving this mutual information bound loose and causing text-dominant bias
- Design RGLM to explicitly reconstruct graph information from the LLM's graph token outputs, tightening the bound with direct graph supervision
- Instantiate three variants: RGLM-Decoder reconstructs in the input (graph) space, while RGLM-Similarizer and RGLM-Denoiser reconstruct in the latent representation space
- Theoretically analyze and empirically validate the alignment effectiveness of each variant across benchmarks
System Components
Input-space variant that reconstructs the original graph structure/attributes directly from the LLM's graph token outputs, providing explicit input-level graph supervision
Latent-space variant that enforces similarity constraints between reconstructed and original graph latent representations to improve alignment
Latent-space variant using a denoising objective to recover clean graph latent representations from corrupted graph token outputs, injecting robust graph supervision
Theoretical foundation proving alignment quality is bounded by graph-representation mutual information, motivating the reconstruction-based supervision approach
Results
| Aspect | Existing GTokenLLMs | RGLM (This Paper) | Improvement |
|---|---|---|---|
| Graph-text alignment mechanism | Implicit, text-supervision only | Explicit graph reconstruction supervision | Tighter mutual information bound |
| Benchmark performance | Baseline GTokenLLM results | Consistently improved across variants | Reported as effective across benchmarks/tasks (no exact numbers in abstract) |
Key Takeaways
- Pure text-supervised instruction tuning is insufficient for genuine graph comprehension in LLMs; adding explicit graph reconstruction objectives measurably improves alignment
- Reconstruction-based supervision can be applied flexibly at either the input space (decoding graph structure) or latent space (similarity/denoising), offering practitioners multiple implementation options depending on compute and data constraints
- Information-theoretic mutual information bounds provide a useful lens for diagnosing and designing auxiliary losses in multi-modal (graph-text) alignment beyond graph-LLM settings
- When building graph foundation models, evaluate whether current alignment losses actually leverage graph structure versus merely fitting textual instruction outputs
Abstract
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.