Graph Tokenization for Bridging Graphs and Transformers

Zeyuan Guo; Enmao Diao; Cheng Yang; Chuan Shi

cs.LGMar 11, 2026

Graph Tokenization for Bridging Graphs and Transformers

Authors: Zeyuan Guo, Enmao Diao, Cheng Yang, Chuan Shi

Organizations: Beijing University of Posts and Telecom., Beijing 100876, China · DreamSoul

Abstract

The success of large pretrained Transformers is closely tied to tokenizers, which convert raw input into discrete symbols. Extending these models to graph-structured data remains a significant challenge. In this work, we introduce a graph tokenization framework that generates sequential representations of graphs by combining reversible graph serialization, which preserves graph information, with Byte Pair Encoding (BPE), a widely adopted tokenizer in large language models (LLMs). To better capture structural information, the graph serialization process is guided by global statistics of graph substructures, ensuring that frequently occurring substructures appear more often in the sequence and can be merged by BPE into meaningful tokens. Empirical results demonstrate that the proposed tokenizer enables Transformers such as BERT to be directly applied to graph benchmarks without architectural modifications. The proposed approach achieves state-of-the-art results on 14 benchmark datasets and frequently outperforms both graph neural networks and specialized graph transformers. This work bridges the gap between graph-structured data and the ecosystem of sequence models. Our code is available at bluehere.

Figures & tables

Figure 1: Framework of the proposed graph tokenizer. (A) Substructure frequencies are collected from the training graphs. (B) Structure-guided and reversible serialization is performed using a frequency-guided Eulerian circuit, where the next edge is selected according to a priority rule (e.g., red C: 7 $\to$ 13 $\to$ 15 $\to$ 17). (C) A BPE vocabulary is trained on the serialized corpus, and graphs are encoded into discrete tokens for use in downstream sequence models.

Method	Reversibility	Determinism	Time Complexity
Random Walk	No	No	$O(RL)$
Node-list BFS/DFS	No	No	$O(\|\mathcal{V}\|+\|\mathcal{E}\|)$
Topological Sort	No	No	$O(\|\mathcal{V}\|+\|\mathcal{E}\|)$
Eulerian circuit	Yes	No	$O(\|\mathcal{E}\|)$
SMILES (non-canonical)	Yes	No	$O(\|\mathcal{V}\|+\|\mathcal{E}\|)$
Canonical SMILES	Yes	Yes	$O(\|\mathcal{V}\|+\|\mathcal{E}\|)$

Table 1: Properties of graph serialization methods. For Random Walk,

L

is walk length and

R

the number of walks. Implementation details are in Appendix B .

Panel of Figure 2 — Figure 2: Efficiency analysis on the ZINC dataset. (a) BPE greatly reduces token sequence length from serialization. (b) Graph tokenization leads to substantial training speedup by enabling efficient processing with standard Transformers.

Model	molhiv auc $\uparrow$	p-func ap $\uparrow$	mutag acc $\uparrow$	coildel acc $\uparrow$	dblp acc $\uparrow$	qm9 mae $\downarrow$	zinc mae $\downarrow$	aqsol mae $\downarrow$	p-struct avg mae $\downarrow$
GCN	74.0 (0.9)	53.2 (1.4)	79.7 (1.7)	74.6 (0.4)	76.6 (0.8)	0.134 (0.004)	0.399 (0.006)	1.345 (0.013)	0.342 (0.003)
GIN	76.1 (1.1)	61.4 (0.7)	80.4 (1.2)	72.0 (0.8)	73.8 (0.9)	0.176 (0.006)	0.379 (0.007)	2.053 (0.058)	0.338 (0.002)
GAT	72.1 (0.8)	51.2 (1.1)	80.1 (0.9)	74.4 (1.1)	76.3 (0.7)	0.114 (0.015)	0.445 (0.015)	1.388 (0.008)	0.316 (0.003)
GatedGCN	80.6 (0.6)	51.2 (1.0)	83.6 (0.8)	83.7 (0.4)	86.0 (0.4)	0.096 (0.007)	0.370 (0.011)	0.940 (0.016)	0.312 (0.004)
GraphGPS	78.5 (1.5)	53.5 (0.7)	84.3 (0.9)	80.5 (0.8)	71.6 (0.8)	0.084 (0.004)	0.310 (0.005)	1.587 (0.011)	0.251 (0.001)
Exphormer	82.3 (0.7)	64.5 (0.9)	82.7 (1.1)	91.5 (0.2)	84.9 (0.8)	0.080 (0.005)	0.281 (0.006)	0.749 (0.006)	0.251 (0.002)

Table 2: Results of classification (left block) and regression (right block). The best scores are shown in bold, the second-best are underlined, and standard deviations are given in parentheses. Results for the remaining datasets are presented in Appendix D .

Method	molhiv auc $\uparrow$		coildel acc $\uparrow$		p-func ap $\uparrow$		zinc mae $\downarrow$		qm9 mae $\downarrow$
Method	w	w/o	w	w/o	w	w/o	w	w/o	w	w/o
BFS	72.3 (0.6)	81.2 (0.9)	81.2 (0.9)	80.1 (1.3)	68.5 (0.6)	67.2 (0.2)	0.453 (0.011)	0.696 (0.013)	0.311 (0.009)	0.292 (0.011)
DFS	76.0 (0.4)	79.1 (0.5)	80.5 (0.4)	79.8 (0.8)	71.0 (1.1)	68.4 (0.3)	0.446 (0.009)	0.705 (0.008)	0.291 (0.007)	0.277 (0.010)
TOPO	73.2 (0.6)	75.6 (0.8)	82.6 (0.8)	81.4 (1.2)	67.9 (0.3)	64.5 (0.5)	0.416 (0.010)	0.634 (0.011)	0.293 (0.010)	0.275 (0.013)
Eulerian	84.5 (0.7)	81.0 (1.0)	84.1 (1.5)	84.0 (1.5)	69.1 (0.6)	66.8 (1.1)	0.164 (0.009)	0.160 (0.016)	0.083 (0.004)	0.104 (0.008)
Feuler	87.4 (0.4)	81.3 (0.5)	88.0 (0.7)	85.6 (0.6)	73.1 (0.3)	68.1 (0.9)	0.131 (0.007)	0.171 (0.013)	0.071 (0.005)	0.088 (0.007)

Table 3: Ablation of serialization method orderings with and without BPE. The best scores are shown in bold, the second-best are underlined, and standard deviations are given in parentheses. A dash (“—”) under the SMILES method indicates that the dataset either lacks SMILES representations or does not correspond to a molecular graph.

Figure 3: Illustration of the BPE merging process on ZINC. Each row shows how simple substructures (left) are iteratively merged to form larger, chemically meaningful tokens (middle and right).

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	# Graphs	Task	# Targets	Nodes (Mean $\pm$ Std)	Edges (Mean $\pm$ Std)	Node Raw Dim	Edge Raw Dim
aqsol	9,823	Regression	1	$33.7\pm 24.5$	$67.9\pm 50.0$	65	5
coildel	3,900	Classification	100	$21.5\pm 13.2$	$108.5\pm 77.0$	2	1
colors3	10,500	Classification	11	$61.3\pm 60.5$	$182.1\pm 187.3$	4	—
dblp	19,456	Classification	2	$10.5\pm 8.5$	$39.3\pm 39.3$	1	1
dd	1,178	Classification	2	$284.3\pm 272.1$	$1431.3\pm 1388.4$	1	—
molhiv	41,127	Classification	2	$25.5\pm 12.1$	$54.9\pm 26.4$	9	3

Appendix

Table 4: Comprehensive statistics and feature dimensions for all benchmark datasets. Node and edge counts are presented as mean

\pm

standard deviation. ”Raw Dim” refers to the dimensionality of the original features before they are mapped to discrete integer symbols.

Parameter	GT+BERT	GT+GTE
Model Configuration	BERT-Small	GTE-Base
Number of Hidden Layers ( $N$ )	4	12
Hidden Size ( $d_{\text{model}}$ )	512	768
Number of Attention Heads ( $h$ )	4	12
FFN Intermediate Size ( $d_{\text{ff}}$ )	2048	3072
Activation Function	GELU	GELU

Appendix

Table 5: Architectural parameters of the Transformer backbones used in our experiments.

Parameter	Default Value	Exceptions & Conditions
General Settings
Optimizer	AdamW	—
Epochs	200	—
Weight Decay	0.1	—
Random Seed	42	—
Batch Size	32	16 on ( DBLP , Peptides_* , and COIL-DEL )

Appendix

Table 6: Unified hyperparameter specification. This table details the default values used for training and the specific conditions under which they were overridden.

Token Size	Atomic ( $0\sim 1$ )	Small ( $2\sim 3$ )	Medium ( $4\sim 6$ )	Large ( $7\sim 9$ )	Huge ( $10+$ )
Proportion	7.1%	28.5%	41.5%	20.4%	2.5%

Appendix

Table 7: Fine-grained distribution of token sizes (node counts) in the learned BPE vocabulary on ZINC (

K=2000

). The distribution peaks at the 4-6 node range, indicating a preference for functional-group-sized substructures.

Figure 4: Visualization of autoregressive graph generation on MNIST. The model generates the graph structure token-by-token (left to right). The resulting sequences are decoded back into grid graphs, forming coherent digit images. This demonstrates the framework’s capability to support generative tasks using standard decoder-only Transformers.

Model	colors3 acc $\uparrow$	twitter acc $\uparrow$	proteins acc $\uparrow$	dd acc $\uparrow$
GCN	66.0 (2.1)	52.7 (0.3)	73.2 (1.6)	62.7 (1.1)
GIN	69.3 (1.6)	55.6 (0.2)	64.3 (4.0)	65.2 (0.9)
GAT	76.6 (1.4)	53.6 (0.3)	70.5 (0.9)	58.5 (1.0)
GatedGCN	77.1 (1.2)	59.8 (0.4)	71.1 (1.2)	77.2 (0.7)
GraphGPS	77.4 (1.8)	53.0 (0.5)	67.9 (0.6)	76.3 (0.5)
Exphormer	73.9 (1.9)	55.1 (0.3)	74.1 (0.9)	74.6 (0.6)

Appendix

Table 8: Additional classification results on datasets not shown in the main table. Best scores are in bold , second-best are underlined . Std in parentheses.

Model	ZINC (MAE $\downarrow$ )	MOLHIV (AUC $\uparrow$ )	Peptide-func (AP $\uparrow$ )	COIL-DEL (ACC $\uparrow$ )*
GraphGT	0.226 (0.014)	–	63.26 (1.26)	86.1 (0.8)
Graphormer	0.132 (0.006)	80.51 (0.53)	–	88.4 (0.3)
FragNet	0.078 (0.005)	81.32 (0.86)	66.8 (0.5)	83.4 (0.6)
Graph-ViT-MLPMixer	0.073 (0.001)	79.97 (1.02)	69.7 (0.8)	89.1 (0.4)
HAN*	0.348 (0.042)	72.3 (0.6)	52.2 (1.1)	74.5 (0.6)
ChebNet*	0.423 (0.013)	70.1 (0.7)	51.3 (0.8)	71.4 (0.8)

Appendix

Table 9: Comparison with additional baselines. ‘*’ indicates results reproduced using official implementations; ‘–’ denotes results not reported in the original papers. Our method remains competitive against specialized architectures.

Model	ZINC (MAE $\downarrow$ )	COIL-DEL (ACC $\uparrow$ )
GraphGPT	0.373 (0.021)	5.6 (0.9)
LLAGA	0.317 (0.016)	12.5 (1.1)
Our Method	0.131 (0.007)	89.6 (0.2)

Appendix

Table 10: Performance comparison with LLM-based models via textualized graph adaptation. These models exhibit significant performance degradation on pure structural tasks compared to our native tokenization.

Panel of Figure 5 — Figure 5: Efficiency analysis on the QM9 dataset.

Panel of Figure 6 — Figure 6: Efficiency analysis on the MolHIV dataset.

Panel of Figure 7 — Figure 7: Efficiency analysis on the DD dataset.

Panel of Figure 8 — Figure 8: Efficiency analysis on the COLORS-3 dataset.

Panel of Figure 9 — Figure 9: Efficiency analysis on the COIL-DEL dataset.

Panel of Figure 10 — Figure 10: Efficiency analysis on the AQSOL dataset.

Method	mutag acc $\uparrow$		colors3 acc $\uparrow$		dblp acc $\uparrow$		aqsol mae $\downarrow$		p-struct avg mae $\downarrow$
Method	w	w/o	w	w/o	w	w/o	w	w/o	w	w/o
BFS	79.2 (0.9)	78.8 (0.6)	73.4 (0.8)	74.4 (0.3)	91.8 (0.19)	91.7 (0.22)	0.701 (0.017)	0.702 (0.008)	0.2495 (0.0018)	0.2494 (0.0005)
DFS	81.9 (0.7)	79.4 (1.5)	99.9 (0.1)	100.0 (0.0)	92.8 (0.09)	92.6 (0.12)	0.684 (0.013)	0.676 (0.011)	0.2421 (0.0026)	0.2468 (0.0040)
TOPO	80.1 (0.8)	78.4 (1.4)	76.6 (1.1)	98.3 (1.3)	93.0 (0.09)	92.5 (0.13)	0.814 (0.004)	0.737 (0.003)	0.2626 (0.0022)	0.2556 (0.0002)
Eulerian	86.1 (0.9)	84.3 (1.3)	38.9 (1.0)	44.7 (2.2)	93.1 (0.09)	91.7 (0.17)	0.609 (0.001)	0.627 (0.016)	0.2514 (0.0027)	0.2499 (0.0035)
Feuler	90.1 (0.6)	86.7 (0.9)	41.0 (1.2)	45.3 (0.8)	93.6 (0.08)	88.9 (0.14)	0.621 (0.007)	0.623 (0.017)	0.2510 (0.0001)	0.2548 (0.0004)

Appendix

Table 11: Ablation with GT+GTE on additional datasets not covered in the main table. The best scores are shown in bold , the second-best are underlined , and standard deviations are in parentheses. A dash (“—”) under SMILES indicates that the dataset either lacks SMILES representations or is not a molecular graph.

Method	molhiv auc $\uparrow$		coildel acc $\uparrow$		p-func ap $\uparrow$		zinc mae $\downarrow$		qm9 mae $\downarrow$
Method	w	w/o	w	w/o	w	w/o	w	w/o	w	w/o
BFS	76.5 (0.6)	76.1 (0.9)	81.2 (0.9)	80.1 (1.3)	66.9 (0.9)	63.2 (0.9)	0.612 (0.009)	0.961 (0.012)	0.227 (0.011)	0.324 (0.013)
DFS	74.6 (0.4)	79.5 (0.5)	80.5 (0.4)	79.8 (0.8)	71.3 (0.3)	67.5 (1.0)	0.537 (0.008)	0.976 (0.009)	0.275 (0.009)	0.281 (0.014)
TOPO	72.2 (0.6)	77.9 (0.8)	82.6 (0.8)	81.4 (1.2)	65.3 (0.5)	54.6 (1.0)	0.711 (0.011)	1.034 (0.012)	0.277 (0.010)	0.266 (0.011)
Eulerian	83.7 (0.7)	83.9 (1.0)	72.1 (0.6)	69.9 (2.9)	67.3 (0.9)	64.1 (1.6)	0.304 (0.008)	0.396 (0.012)	0.104 (0.006)	0.127 (0.007)
Feuler	82.6 (0.4)	81.8 (0.5)	74.1 (0.3)	76.1 (0.9)	68.5 (1.0)	65.4 (1.1)	0.241 (0.006)	0.432 (0.011)	0.122 (0.004)	0.128 (0.005)

Appendix

Table 12: GT+BERT ablation of serialization orderings with and without BPE on main datasets. Best scores in bold , second-best underlined , std in parentheses. . A dash (“—”) under SMILES indicates the dataset lacks SMILES or is not a molecular graph.

Method	mutag acc $\uparrow$		colors3 acc $\uparrow$		dblp acc $\uparrow$		aqsol mae $\downarrow$		p-struct avg mae $\downarrow$
Method	w	w/o	w	w/o	w	w/o	w	w/o	w	w/o
BFS	76.1 (0.6)	76.4 (0.7)	72.7 (0.9)	67.3 (4.1)	91.9 (0.17)	91.3 (0.26)	0.851 (0.002)	0.844 (0.002)	0.2477 (0.0014)	0.2620 (0.0021)
DFS	79.6 (0.5)	77.3 (0.6)	98.3 (0.1)	87.5 (4.4)	92.6 (0.08)	92.4 (0.13)	0.831 (0.002)	0.852 (0.002)	0.2526 (0.0036)	0.2550 (0.0012)
TOPO	74.9 (0.5)	71.2 (0.7)	60.4 (2.3)	66.6 (2.2)	92.7 (0.08)	92.7 (0.11)	0.810 (0.002)	0.840 (0.002)	0.2578 (0.0011)	0.2648 (0.0026)
Eulerian	85.5 (0.8)	82.0 (1.1)	37.8 (1.4)	40.7 (0.6)	93.1 (0.04)	91.8 (0.14)	0.648 (0.002)	0.677 (0.003)	0.2522 (0.0012)	0.2700 (0.0049)
Feuler	87.5 (0.4)	84.1 (0.8)	38.5 (1.1)	40.3 (1.0)	93.2 (0.06)	88.5 (0.11)	0.648 (0.002)	0.685 (0.004)	0.2476 (0.0010)	0.2615 (0.0045)

Appendix

Table 13: GT+BERT ablation on additional datasets (Appendix). Best scores in bold , second-best underlined , std in parentheses. A dash (“—”) under SMILES indicates the dataset lacks SMILES or is not a molecular graph.

Merge Count ( $K$ )	Compression Ratio	Performance (MAE $\downarrow$ )
0 (Raw)	1.00x	0.171 (0.013)
100	2.86x	0.144 (0.012)
500	5.37x	0.137 (0.010)
1000	8.11x	0.131 (0.011)
2000	10.84x	0.131 (0.007)
5000	11.34x	0.132 (0.009)

Appendix

Table 14: Impact of BPE merge count (

K

) on compression ratio and model performance (ZINC).

K=2000

achieves the best balance; larger vocabularies yield diminishing compression returns and do not improve performance due to token rarity.

Unit	Collect Cost	Compression Ratio
W/O Guidance	0	10.46x
Node-Node Bigram	$O(E)$	10.71x
Node-Edge Bigram	$O(E)$	10.72x
Node-Edge-Node Trigram	$\mathbf{O(E)}$	10.84x
Multi-hop Path (2 hop)	$O(E^{2}/N)$	10.56x
Multi-hop Path (3 hop)	$O(E^{3}/N^{2})$	10.37x

Appendix

Table 15: Impact of different statistical units on BPE compression ratio (ZINC). ‘Collect Cost’ denotes the complexity of gathering statistics. Trigrams achieve the highest compression with linear overhead.

Serialization Method	Accuracy (w/ BPE)	Accuracy (w/o BPE)
Edge-based (Feuler)	21.6%	24.8%
Node-based (DFS)	83.4%	88.4%

Appendix

Table 16: Performance on simulated node counting tasks (ZINC). Switching from edge-based to node-based serialization resolves the counting failure, confirming our analysis regarding the COLORS-3 dataset.

Dataset	Serialization (ms)	BPE Encoding (ms)
ogbn-arxiv	14,948	57
ogbg-code2	4,108	74
ogbn-products	29,670	56

Appendix

Table 17: Efficiency of different components of our method on large-scale OGB datasets (Normalized to Time per 1 Million Nodes ).

Graph Representation Learning

Graph representation learning develops methods for encoding nodes, edges, and whole graphs for prediction, comparison, and transfer.

See all 296 papers

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
May 21, 2026Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3Transformer Expressivity Graph Representation Learning
Meta AI · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Google Research +2
Riemannian Graph Tokenizer for Structural Knowledge Transfer
Oct 11, 2026Qimin Zhou, Haibo Liu, Yujie Wang +2Graph Representation Learning Cross-Domain Transfer Learning
Beijing University of Posts and Telecommunications, Beijing, China
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

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

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford+2

Meta AI · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Google Research+2

Transformer Expressivity Graph Representation Learning Neural Network Expressivity Graph Transformer

Open paper AskPDF arXiv

Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines which structural information is exposed at the input. In this work, we show that this choice is a fundamental component of transformer expressivity. We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations. We prove that different tokenizations induce distinct depth regimes: the same graph computation may be realizable by a shallow transformer under one tokenization, while requiring substantially larger depth under another. For example, we prove that random-walk tokenization is lossy for any walk length, making it impossible in general to recover the graph from it, and that while spectral tokenization is lossless, it is ill-conditioned for local tasks. We further show that although both random-walk and spectral tokenizations are derived from adjacency information, it is impossible for a limited-depth transformer to convert between tokenization families in general. In particular, we establish lower bounds and impossibility results showing that unfavorable tokenizations may preclude the efficient recovery of more suitable structural representations. Finally, we complement our theory with controlled experiments on synthetic and real-world tasks, validating the predicted separations and showing that different tasks favor different structural views, and combining complementary tokenizations allows the transformer to leverage distinct signals from each representation.

Abstract

Graph Representation Learning

Explore similar work

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers

Riemannian Graph Tokenizer for Structural Knowledge Transfer

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning