Source-linked AI summary
Let Your Graph Do the Talking: Encoding Structured Data for LLMs
Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, Jonathan Halcrow
TL;DR
LLMs take sequential text as input, while structured data has relational structure that is difficult to represent optimally for them. GraphToken learns parameter-efficient graph prompt tokens and improves graph reasoning across tasks, with up to a 73% improvement on the GraphQA benchmark.
Problem
How to represent structured data optimally for LLMs remains an open question, as text serialization requires models to decode structure and has proved insufficient for graph reasoning.
Source: §1 · p. 1Method
Results
Across nine graph reasoning tasks, GraphToken greatly improves LLM graph reasoning, with up to a 73% improvement on the GraphQA benchmark.
Source: §6 · p. 8Takeaways & Limitations
Explicitly representing structure significantly improves performance on the comprehensive GraphQA benchmark for general structured-data reasoning tasks.
Source: §1 · p. 2The method requires an LLM that accepts token embeddings and permits gradients with respect to part of its input sequence.
Source: §3.1 · p. 4
Abstract
from arXiv · showhide
How can we best encode structured data into sequential form for use in large language models (LLMs)? In this work, we introduce a parameter-efficient method to explicitly represent structured data for LLMs. Our method, GraphToken, learns an encoding function to extend prompts with explicit structured information. Unlike other work which focuses on limited domains (e.g. knowledge graph representation), our work is the first effort focused on the general encoding of structured data to be used for various reasoning tasks. We show that explicitly representing the graph structure allows significant improvements to graph reasoning tasks. Specifically, we see across the board improvements - up to 73% points - on node, edge and, graph-level tasks from the GraphQA benchmark.
1. Introduction
LLMs can use fresh factual context, but representing structured data for them remains a challenge because their inputs are sequential. GraphToken learns parameter-efficient prompts that explicitly encode structure, and the paper reports improvements on graph reasoning tasks.
1. Introduction
- RAG can enrich LLM prompts with factual, fresh information, including relational data from sources such as private databases and social networks.Structured data contains complex dependencies between discrete parts.Source: §1 · p. 1
- Hand-crafted text serialization makes LLMs decode and understand structure before using it, and pure text representations have proved insufficient for graph reasoning.The paper frames finding an optimal structured-data representation for LLMs as a crucial research question.Source: §1 · pp. 1–2
- GraphToken learns a parameter-efficient encoding function that extends textual prompts with explicit structural information using a small number of trainable parameters.Unlike pre-training or fine-tuning, the method trains the encoder that generates soft-token prompts.Source: §1 · p. 2
- The authors report significant improvements from explicitly representing structure on the comprehensive GraphQA benchmark.They describe GraphToken as the first parameter-efficient encoder aimed at general structured-data reasoning tasks.Source: §1 · p. 2
- GraphToken improves LLM capabilities on graph reasoning tasks and generalizes to unseen tasks and graphs.The contributions include experiments across graph, node, and edge-level tasks.Source: §1 · p. 2
2. Background
The background reviews language-model adaptation and graph representation learning, then situates GraphToken among approaches that connect graphs with LLM reasoning. It highlights the mismatch between non-sequential structured data and sequential language-model inputs.
2.1. Large Language Models
- LLMs are pretrained on large text corpora and adapted to downstream tasks; parameter-efficient methods reduce adaptation costs by updating only a small number of parameters.Soft-prompt methods prepend learnable tokens while keeping the LLM parameters frozen, and GraphToken extends this approach with a GNN-based structured-data encoder.Source: §2.1 · p. 2
2.2. Graph Encoding with Neural Networks
- Graph representation learning maps discrete structured data into continuous representations for downstream machine-learning tasks, including node and whole-graph embeddings.The passage traces a shift from node embeddings such as DeepWalk to GNN methods that learn graph representations.Source: §2.2 · p. 3
2.3. Graphs and LLMs
- Prior work combines graphs and LLMs through knowledge-graph retrieval, node classification, graph learning with text attributes, and graph-reasoning evaluation.GraphQA found graph reasoning difficult and reported that scaling laws did not appear to apply; GNN-only approaches lack the textual understanding central to LLM integration.Source: §2.3 · p. 3
3. GraphToken
GraphToken maps graph structure into learned continuous prompt tokens and pairs them with task text for a frozen LLM. Its encoder produces task-dependent graph representations, which are trained through answer likelihood without updating LLM parameters.
3. GraphToken
- GraphToken replaces lexical graph serialization with learned continuous graph tokens produced by a GNN encoder for the LLM input.The method aims to provide a rich, concise, expressive representation without requiring a chosen sequential ordering of the graph.Source: §3 · p. 3
3.1. Architecture
- The graph encoder produces a fixed number of token embeddings that are prepended to prompt embeddings, and the LLM decodes the combined sequence into an answer.It uses graph positional encodings and a GNN; readout varies by task, using pooled node representations for graph-level tasks, node representations for node-level tasks, and global or paired node representations for edge-level tasks. A final dense layer projects representations into LLM token space. The framework requires an LLM that accepts token embeddings and permits gradients with respect to part of the input sequence.Source: §3.1 · pp. 3–4, Figure 2 · p. 4
3.2. Training procedure
- Training uses graph, task-text, and answer triples, minimizing the expected answer’s LLM log-likelihood while backpropagating gradients to the graph encoder and keeping LLM parameters frozen.The augmented query concatenates the graph encoding with the task-text embedding.Source: §3.2 · p. 4
4. Experiments
Across GraphQA tasks, GraphToken outperforms existing methods, while encoder architecture and node features affect task performance. The experiments also examine the parameter cost of the graph encoders.
4.1. Experiment 1: GraphToken Performance
- GraphToken significantly outperforms existing methods on graph-, node-, and edge-level GraphQA tasks.Table 1 compares it with prompt-engineering and soft-prompting baselines using simple accuracy.Source: Table 1 · p. 5, §4.1 · p. 5
4.2.1. CHOICE: GRAPH CONVOLUTION
- No examined graph encoder dominates across all tasks, although linear NodeSet and EdgeSet models perform strongly on their respective counting tasks.Nonlinear models also perform well on some counting tasks, including MHA on node count and MPNN on edge count.Source: §4.2.1 · p. 6, Table 2 · p. 6
4.2.2. CHOICE: GNN FEATURES
- Learned positional features generally outperform Laplacian features, and combining learned and spectral features greatly improves some encoder-task combinations.Learned features lift counting tasks for many encoders; spectral features also benefit NodeSet, which does not use graph edges.Source: §4.2.2 · p. 6, Figure 3 · p. 7
4.2.3. PARAMETER USAGE IN GRAPHTOKEN
- GraphToken’s graph encoder models use 17k–199k parameters, while the projection layer to token space contains roughly 11 million.The reported total is dominated by the projection layer; attention-based MHA and HGT add the most encoder parameters among nonlinear architectures.Source: §4.2.3 · p. 7
5. Discussion
The discussion examines what GraphToken’s encoders learn and whether they generalize to unseen graphs and tasks. It reports cross-task transfer and identifies future directions for adapting graph encoders to LLMs.
5.1. Graph Encoder Analysis
- Attention-based encoders trained on cycle-check and triangle-counting tasks generalize well to bipartiteness detection on 8-node graphs.The authors identify this as an example of graph encoders generalizing to a new task.Source: §5.1 · p. 8, Table 4 · p. 8
- MPNN and attention-based encoders are generally strongest, and performance on edge-count prediction correlates with training on edge count or node count.The authors suggest these patterns indicate that encoders learn features useful across downstream tasks.Source: §5.1 · p. 8
5.2. Future Work
- Future work includes designing LLM-suited graph convolutions, testing factual grounding, studying broken equivariance, and using LLMs to interrogate GNNs.The paper also asks whether graph representations can support novel questions about knowledge graphs or molecules.Source: §5.2 · p. 8
6. Conclusions
The conclusion presents GraphToken as a parameter-efficient way to encode graphs for LLMs without updating LLM parameters. Across nine graph reasoning tasks, it reports improvements of up to 73% on GraphQA.
6. Conclusions
- GraphToken learns a graph-embedding function using gradients from a frozen LLM, training only the graph encoder to project structured data into latent prompt space.The method does not update LLM parameters.Source: §6 · p. 8
- Across nine graph reasoning tasks, GraphToken improves LLM graph reasoning by up to 73% on the GraphQA benchmark.The conclusion describes the experimental analysis as extensive.Source: §6 · p. 8
- The authors see GraphToken as a potential approach for adapting new structured data sources to LLMs and addressing hallucinations, factuality, and freshness.These are presented as potential applications and problems, not demonstrated outcomes in this conclusion.Source: §6 · p. 8
A.1. Graph Encoders
The appendix describes GNNs through neighborhood-informed state updates and message pooling. Different implementations of these operations yield different graph encoders, including the illustrated NodeSet and EdgeSet architectures.
A.1. Graph Encoders
- A GNN updates node or edge hidden states using information from neighboring states and aggregates neighborhood messages into fixed-size representations.The two operations are named NEXTSTATE and EDGEPOOL.Source: §A.1 · p. 13
- Different NEXTSTATE and EDGEPOOL implementations support varied GNN operations, including Transformer-style attention in place of graph edges.The cited example is attributed to Dwivedi & Bresson (2021).Source: §A.1 · p. 13
- Figure 5 illustrates NodeSet and EdgeSet architectures, while other GNN models apply graph convolutions before reading out node or edge states.The figure is described as a figurative illustration of set-based GNN architectures.Source: §A.1 · p. 13, Figure 5 · p. 13
A.2. Additional experiments
The additional experiments report stronger performance for complete graph populations than for trees, which the authors attribute to trees being somewhat out of distribution. Across the considered cases, the best overall encoder outperforms naïve set encodings.
A.2. Additional experiments
- The best overall encoder outperforms naïve set encodings across the considered cases, while complete graph populations perform significantly better than trees.The authors attribute the tree results to trees being somewhat out of distribution after training on diverse data.Source: §A.2 · p. 13
- Tables report MSE for clustering coefficient and triangle count, and accuracy for degree, diameter, k-core, and edge count on connected 8-node graphs.The captions identify these metrics and graph populations but do not provide numerical results in the supplied passages.Source: Table 5 · p. 14, Table 6 · p. 14, Table 7 · p. 14
- Additional tables report planarity AUC and shortest-path MSE on connected 8-node graphs, plus degree and diameter accuracy and shortest-path MSE on 15-node trees.The captions identify the evaluations and metrics, not their results.Source: Table 10 · p. 15, Table 11 · p. 15, Table 13 · p. 15