Graph Tokenization for Bridging Graphs and Transformers
Authors: Zeyuan Guo
Enmao Diao
Cheng Yang
Chuan Shi
Venue: ICLR 2026 Poster (2026)
Keywords: Graph
BPE
Tokenizer
Primary area: learning on graphs and other geometries & topologies
TL;DR: Graphs can be tokenized for direct use by standard Transformers without any model architectural modifications and performs well.

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 \href{ https://github.com/BUPT-GAMMA/Graph-Tokenization-for-Bridging-Graphs-and-Transformers }{\color{blue}here}.

Published as a conference paper at ICLR 2026
GRAPH TOKENIZATION FOR BRIDGING GRAPHS AND TRANSFORMERS
Zeyuan Guo
Enmao Diao
Beijing University of Posts and Telecom., Beijing 100876, China
DreamSoul enmao. www.dddeeddddddddooooooooo com
guozeyuan@hupt.eddu www.bbuutt.uuu....
Cheng Yang
Chuan Shi
Beijing University of Posts and Telecom., Beijing 100876, China
Beijing University of Posts and Telecom., Beijing 100876, China sh thiichann@bupt.ede www.:bbppp..uuucommmmom
yangcheng@@uupt.com edd.pptteed.... on
ABSTRACT
The success of large pretrained Transformers is closely tied to tokenizers, which convert raw imput into discrete symbols. Extending these models graph- structured data remains 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 large language models (LLMs). To better capture structural information, the graph serialization process is guided by global statistics of graph substructures, ensuring that frequently occur- ring 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, results 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 avail- able at here.
INTRODUCTION
Large pretrained Transformer models (Vaswani et al., 2017: Minace al., 2024), exemplified by LLMs, have achieved sfate-of-the-art results across diverse domains (Dosovitskiy et al., 2020; Gong et al., 2021). A key component of this success is the tokenizer, which converts quences of discrete symbols. By structuring information into learnable units, the tokenizer provides the interface between complex data and Transformer architectures, supporting the scalability and performance of these models.
input into
Research extending Transformers graph-structured data has explored main strategies, each with inherent limitations (Yu et al., 2025; Guo et al., 2024). One strategy modifies the architecture by incorporating attention mechanisms into Graph Neural Networks (GNNs) to create specialized Graph Transformers (Yun et al., 2019). These approaches require graph-specific designs that diverge from standard sequence models and their ecosystem. The other strategy converts graphs into con- tinuous embeddings for use with Transformers (Tang et al., 2024), but this often causes information loss or unstable representations, which can degrade model performance (Chen et al., 2024).
Developing principled graph tokenizer requires reexamining the notion of tokenization in the con- text of graph-structured data. Specifically, text can be modeled as path graph, where the linear sequence of tokens provides both fixed neighborhood structure and canonical ordering, making tokenization relatively straightforward. In contrast, general graphs pose additional challenges, as
"Equal Contribution
"ooresponniig author

---

Published as a conference paper at ICLR 2026
their neighborhoods branch in multiple directions rather than follow simple linear sequence. They also lack permutation invariance, where graphs under node permutations are considered equiv- alent. Furthermore, co-occurrence statistics widely used in text, such as n- grgram frequencies based on contiguous tokens, are not directly applicable to graphs.
We propose framework that addresses these challenges by integrating graph serialization with Byte Pair Encoding (BPE), a data-driven compression algorithm widely applied in text tokenization (Shi- bata et al., 1999). To ensure that graph structure and labels are preserved, we adopt reversible se- rialization methods such as extended Euler circuits and ninimal-weight graph traversals. Ordering ambiguity resolved by using global statistics deterministically guide the serialization process, which translates common substructures into frequent and adjacent symbol patterns that BPE is well suited to merge. Specifically, BPE iteratively merges the most frequent pairs of symbols into new tokens, therehy reducing sequence length while preserving common substructures. As result, applying BPE to serialized graphs enables the construction of a vocabulary of frequent graph neigh- borhoods, producing discrete tokens that are both informative and well aligned with Transformer architectures.
In this work, our contributions can be summarized follows:
General Framework for Graph Tokenization. We introduce tokenization framework that combines reversible graph serialization with BPE. By decoupling the encoding of graph structure from the model architecture. this framework provides an effective inter- face that enables standard off-the-shelf Transformer models to be applied directly to graph- structured data without requiring any architectural modifications.
Strieture-Guided Serialization for BPE. We propose deterministic serialization pro- cess guided by global statistics of graph substructures. The process addresses ordering ambiguities in graphs and aligns frequently occurring substructures into adjacent sequence patterns. Structure Strueture-Guiedd Serialization provides an effective basis for BPE to learn a meaningful and interpretable vocabulary structural graph tokens.
-tate-of-the-Are Performance on Downstream Tasks. Our tokenizer enables standard Transformer backbones to achieve of results across diverse suite of 14 bench- marks for graph classification and regression. The proposed approach frequently out- performs both established Graph Neural Networks and specialized Graph Transformers, demonstrating its effectiveness and generalization.
2 RELATED WORKS
Graph Neural Networks. Graph Neural Networks (Kipf, 2016; Luo et al., 2025) are the prevail- ing framework for learning on graph-structured data. They rely on message passing, where node representations are updated by iteratively aggregating information from local neighbors. enabling effective modeling of local graph structure (Chen et al., 2019). To capture dependencies beyond lo- cal neighborhoods, subsequent work introduced self-attention, leading to Graph Transformers (Yun et al., 2019; Wu et al., 2023) and hybrid global-local models (He et al., 2023; Zhang et al., 2023). More recently, graph representation learning has been combined with Graph Foundation Models, often by mapping graph structure and features into the embedding space of pretrained foundation models (Tang et al., 2024; Chen et al., 2024; Zhang al., 2025; Yan al., 2025; Liu et al., 2026). These approaches depend on cross-modal alignment, with performance influenced by the semantic compatibility between graph features and natural language. Our objective is to design an interface that enables graphs to be processed directly by standard, off-the-shelf Transformers.
Graph Serialization. Serialization of a graph into a sequence was one of the earliest strategies for applying sequence-based models. Early methods such as DeepWalk generated node sequences through random walks and processed them with shallow neural networks (Perozzi et al.. 2014; Zhang et al., 2020). This direction was later surpassed by the message passing paradigm of GNNs (Gilmer et al., 2017), which became the dominant approach to learning graph representations. More re- cently, the success of sequence-native architectures such as the Transformer has renewed interest in serialization- methods (Wang et al., 2024). Many existing graph-to-sequence pipelines are not reversible. Specifically, walk- based serializations break the graph into local fragments. Each sequence reflects only part of the graph, and even combining many walks cannot reconstruct the original structure or capture global connectivity (Xia et al., 2019). In another case, traversal- based serializations sensitive to node ordering and starting choices, so even isomorphic graphs may
2

---

Published as a conference paper at ICLR 2026
produce different graph traversal circuits (Gao al., 2025). In contrast, method is reversible and almost invariant to graph permutation.
Tokenization The Transformer architecture has become the standard paradigm for sequence mod- eling (Vaswani et al., 2017). Its success is closely tied to the use of effective tokenization (Floridi & Chiriatti, 2020; Guo et al., 2025), which especially critical in LLMs. A tokenizer converts raw input (e.g., text) into sequence of discrete symbols, with BPE being widely adopted data-driven approach that builds a vocabulary by iteratively merging frequent symbol pairs (Shibata ct al., 1999). In prior work on graph data, the term graph tokenization has been used with different meanings. It has referred to neural encoders that produce continuous embeddings (Tang et al., 2024), pooling or coarsening modules that compress subgraphs into super-nodes (Shen & Póczos, 2024), and vector quantization components that discretize node features or latent representations (Yang et al., 2023). In this paper, we adopt the standard definition in natural language processing, where tokenizer is a deterministic procedure that maps a labeled graph to a sequence of discrete symbols for direct use by sequence models, in contrast to neural approaches (c.g.. PS-VAE (Kong et al., 2022)) that project substructures into continuous latent spaces via learnable encoders (see Appendix B.1 for detailed comparison).
METHOD
3.1 PRELIMINARIES
Graph. A graph is a tuple G = (V,E), composed of a finite set of nodes and a set of edges E. Our work focuses on labeled graphs, which we define tuple G (G, L, 2)), where E is finite alphabet of symbols and L : V U + E is a labeling function. Two labeled graphs 91 (G1, L1, Σ) and G2 (G2, L2, Σ) are isomorphic, denoted G1 = G2, if there exists graph isomorphism o: V1 + V/2 between G1 and G2 that also preserves all labels.
Graph Serialization. In general, graph serialization function f maps graph to a finite sequence of symbols. Let A denote the universe of possible sequence elements. The mapping is defined as
................................ sk) s.t. $ A for sisk. f: G + ($1, .......
The choice of A depends on the serialization method. It may consist of node identifiers (A V). continuous embeddings (A = Fdd, or discrete labels (AA = 2). For the purpose of building a discrete tokenizer, we focus on serializations where the output sequence is composed of symbols from the graph's 's alphabet, i.c., A = Σ. To serve as a reliable interface, such a serialization should satisfy two key properties:
Reversibility. A serialization f is reversible if the original labeled graph G can be recovered from its sequence S = f(g) up to isomorphism. Formally, let f-((S) denote the set of all graphs that could produce sequence S. The serialization is reversible if for any G in the domain of f. there exists a reversed graph g' E (f()( such that G' = G.
Determinism. A serialization function f is deterministic if, for any labeled graph g, it consistently produces the same sequence S. This property is essential for addressing the permutation-invaaiiance of graphs. deterministic serialization generates a stable sequence for all graphs within an isomorphism class.
Graph Tokenization. A graph tokenizer & maps a labeled graph G to a finite sequence of discrete symbols, referred to tokens.
:: S- (t,......, bm), t Vr.
In this work, we construct the graph tokenizer & by composing graph serialization function ff with a sequence tokenizer T inspired by the text tokenizers used in LLMs. The sequence tokenizer T maps a sequence over the initial alphabet Σ to a new sequence over a target vocabulary Vr, where the vocabulary is typically learned from data using BPE. The overall mapping is given by
$ = o
When decoding procedure available, the original graph can be reconstructed up isomorphism (i.c.. preserving complete topology and all labels; strict mode-index identity requires an additional index mapping) by applying the inverse operations - followed by f Specifically, the term graph tokenizer refers to methods that produce a discrete sequence. Methods that only discretize embeddings (Yang al., 2023) or apply pooling or coarsening (Shen & Póczos, 2024) are not considered tokenizers in this sense.
3

---

Published as a conference paper at ICLR 2026
3.2 GRAPH TOKENIZER
We construct our graph tokenizer & by composing a reversible and structure structure-guided serialization function with a tokenization step T based on BPE. To ensure graph structural information is preserved, is designed to be reversible, and to produce stable sequences, we enforce deterministic guiding policy for J. We propose a data-driven graph tokenizer & that is learned from training corpus of graphs rather than relying hand-crafted heuristics. Specifically, Algorithm I details the training, encoding, and decoding procedures GraphTokenizer, and Figure I illustrates the overall framework.
B. Seriolize
Byte Encoding
C:0:C-O-C-- d =0 O G Br C-O-C
G. CGCCO00CCOCCCCCCGCGCC
START
G.O.T O.T.O.TT. C-O. C.
Graph Tokenizer
Count
Free
Tafy
sequence models
Figure 1: Framework of the proposed graph tokenizer. (A) Substructure frequencies are collected from the training graphs. (B) Structure-guice guided and reversible serialization is performed using a frequency-guided Eulerian circuit, where the next edge is selected according a priority rule (e.g.. red C: encoded into discrete tokens for use in downstream sequence models.
(C) A BPE vocabulary is trained on the serialized corpus, and graphs are
Local Structural Pattern Statistics. The training procedure begins with the computation of dataset-level statistics of local patterns, which provide a data-driven basis for ensuring determinism in graph serialization. As illustrated in Fig. 1A, count how often small labeled patterns appear in the training graphs, using molecular graphs and edge patterns as an example. These counts are then normalized into relative frequencies.
For a labeled graph g = L, E), we define a basic local pattern as a labeled edge p (Lu, (v) E 33 which captures the labels of the source node, the edge, and the target node. Intuitively, this is the smallest substructure that still reflects a typed relation between two labeled entities. Compared with larger subgraphs, it is computationally inexpensive, over node indices, and stable under isomorphisms, which makes it practical choice for tie-breaking during graph serialization. The count p in G is given by
coomutation-invartii
Count(G,p) p) = { e = (u, v) E & (L(u), L(e), L(t)) = -p}/-
(4)
Aggregating over the training set DD we obtain raw counts and their normalized relative frequencies
C(p)
C(p) Σ Count(G,p) F(p) Eyers C(p)
GED
F(p) denotes the normalized relative frequency, while raw counts C(p) are introduced here as an intermediate definition.
GiructureGuided Reversible Serialization. We proceed to the next step of our framework,
where each graph is converted into sequence of symbols (Algorithm 1, line 5). In this proce- dure, line 4 corresponds to estimating from data, and the resulting frequency map guides the diuuttur-awant serialization function f- F). The function fg addresses traversal ambiguities by prioritizing edges whose incident labeled pattern has higher F (p) from itself and neighbors, with fixed lexical rules applied break any remaining ties.
Fig. 1B illustrates this serialization process on a molecular graph. Specifically, at the red node C, the next step is chosen by the F-guided priority rather than arbitrarily (e.g., choose the green node be-
4

---

Published as a conference paper at ICLR 2026
Table 1: Properties of graph serialization methods. For Random Walk, walk length and the
number of walks. Implementation details are in Appendix B.
Method
Reversibility
Determinism
Time Complexity
Random Walk
No
No
Q(RL)
Node-list BFS/DFS
No
No
0(1 + El
Topological Sort
No
No
0( + (8])
Eulerian circuit
Yes
No
O((E))
SMILES (non-canonical)
Yes
No
O(V +1)
Canonical SMILES
Yes
Yes
0(V)+18)
Chinese Postman Problem
Yes
No
0(VP)
Frequency-Guided Fulerian circuit
Yes
Yes
O(EE) O(V13)
Freiuency-Giided CPP
Yes
Yes
cause "C-C" pair has the highest frequency). To ensure that graph serialization yields faithful graph representations, we require it to satisfy the properties of reversibility and determinism discussed in Section 3.1. Ensuring that these two properties hold simultaneously for general graphs signif- icant challenge. To motivate our approach, we first review classical serialization methods against these criteria. To provide a clear overview, Table 1 summarizes the properties of existing serial- ization methods. A key limitation is that no classical method is simultancously broadly applicable, fully reversible, and inherently deterministic.
Early approaches such as Random Walks (Perozzi et al., 2014) are inherently stochastic and typi- cally explore only local portion of the graph per sample. Even when many walks are aggregated, substructures are split across sequences without markers, so reconstruction is not guaranteed, and the procedure remains non-deterministic. Standard traversal algorithms like Breadth-First Search (BFS) (Moore, 1959) and Depth-First Search (DFS) (Even & Even, 2011) also fail to meet these re- quirements. Their non-determinism arises from arbitrary neighbor selection when multiple choices available, and their node-list output omits edge connectivity, which prevents reconstruction of the original graph. Topological Sort (Kahn, 1962), which produces linear orderings for Directed Acyelic Graphs (DAGs), is limited to DAGs and admits multiple valid orderings, making it non- deterministic. Moreover, like other node-list traversals, it is not reversible because the precise edge connectivity information necessary for reconstruction is discarded.
In contrast to node-based traversals, methods that cover every edge of the graph are naturally re- versible. representative example is the Eulerian circuit (Biggs et al., 1986), which visits each edge exactly once. By treating each undirected edge as two opposing directed edges, the method can extend to any connected graph (Gao et al., 2025). During traversal, emitting an alternating node-edge-node sequence ensures that adjacent symbols share an endpoint, which preserves the information needed by f-1 to reconstruct the edges. Despite this reversibility, the method remains non-deterministic because the classical Hierholzer's algorithm (Hierholzer & Wiener, 1873) must make arbitrary choices whenever a node has multiple unvisited edges. A related approach is the Chinese Postman Problem (CPP) (Kwan, 1960), which seeks minimum weight traversal that ers all edges and thereby also preserves the complete graph structure. Non-determinism in CPP, although more constrained, is intrinsic its solution process, typically solved using Edmonds' blossom algorithm (Edmonds & Johnson, 1973). The standard procedure first identifies all odd- degree nodes and constructs auxiliary complete graph on them, with edge weights representing shortest path distances in the original graph. A minimum-weipe determine which paths should be duplicated. If multiple minimum weight matchings exist, the selection between them is arbitrary, which dictates the different possible traversals.
perfect matching is then computed
comain-specifee serialization methods for molecular graphs, such as SMILES (Weininger, 1988), represent a widely adopted approach in cheminformatics. Non-canonical SMILES is reversible but not deterministic, whereas canonical SMILES achieves determinism by applying an explicit canon- icalization procedure under a fixed scheme. These procedures rely on chemistry-specific perception rules (e.g., aromaticity, implicit hydrogens, and structural notations) and therefore do not generalize to arbitrary labeled graphs. Furthermore, the determinism of canonical SMILES is defined rela- tive to the chosen canonicalization algorithm and perception rules, and implementations may differ slightly across toolkits.
5

---

Published as a conference paper at ICLR 2026
Algorithm The GraphTokeni zer Framework
1: Procedure TRAIN(D, K)
2: Input: A training graph dataset D; number of BPE merges K.
3: Output: frequency map F; BPE codebook C (Vr, R).
4: F(p) <- "geD (o.nt((.p); Vp E
5: Ds t [5g (6(9.F).
6: Vr + Σ; RR'
7: for k k= =110 to K do
8: (5a 56) arg (a..6) ESED, Count(S, (8as 8b))
9: Snow t 54 sr
Dr + U
11: R+ R (s), st) - new
for each S Dg
13: replace all disjoint adjacent pairs (5% 8t) in S with Snew
14: return (F,C)
15:
16: Procedure ENCODE(G, F,C)
17: Input: graph 9; frequency map F; the codebook C = (Vr, R).
18: Output: A token sequence ST.
19: S [G, F)
20: for each (Sa, (0,)))))))))))) - Snew in R do replace all disjoint adjacent pairs (8a. sb) in S with Snew
22: ST + S
return ST
24:
25: Procedure DECODE(ST, C, 1-1
26: Input: token sequence Sr: codebook C = (Vr, R); inverse serialization function f-1
Output: A reconstructed graph G.
28: S 5 ST
for each (Sa, sb) - Snew reversed R) do
30: replace every Snew in S with the pair (Sa: st)
31: 9 f-((S
return
Building on the preceding analysis, our strategy is to impose determinism on traversal methods that are inherently reversible. This accomplished by introducing guiding mechanism that leverages the global frequency map F' to resolve traversal ambiguities. In this way, we obtain a structure- guided graph serialization function fy that simultaneously satisfies reversibility and determinism for general graphs.
Frequency-Guide Guided Eulerian circuit adapts Hierholzer's 's algorithm by introducing a priority rule. At any node u with unvisited outgoing edges E,,, the next edge e* is selected deterministically
E" arg max (e;; F),
(6)
e.EE.
where T(e,, F) assigns scalar priority. for example Tee,, F) = F(p:) for the pattern (L(u), L(e,), L(v)). Although traversal may begin from any node, the resulting circuit differs only by cyclic shift.
For example, in Fig. 1B, when the traversal reaches the red C, there are four candidate neighbors (including the incoming one). According to the dataset-level statistics F, the C-C labeled-edge pattern has the highest F(p), so fg takes that step (step 3). When later returns to the same red C, it selects among the remaining three neighbors: the edge to CI has the next-highest F(p) (step 5), followed by steps and 9.
Frequency-Guided CPP incorporates frequency statistics into the edge weights used by the solver. For an edge e with associated pattern Pe, the weight is defined as
w(e) + a) g( (F(p:)),

---

Published as a conference paper at ICLR 2026
where 9 is decreasing function of frequency (e.g.. 1/F(pe)) and [0,, 1] is a tunable hyperpa- rameter. Ties that arise during matching or tour construction are resolved using the priority policy specified in Eq. 6. For disconnected graphs, each component is serialized independently and the results are concatenated in a fixed order.
Vocabulary Learning via BPE. After converting the graph dataset D into corpus of symbol sequences Ds. the final stage of training is to learn a vocabulary from this corpus. We employ Byte Pair Encoding (BPE), inspired by the text tokenizers used in LLMs, corresponding to the main loop in Algorithm (lines 6-14). BPE iteratively identifies the most frequently occurring adjacent pair of symbols in the corpus and merges it into a new symbol added the vocabulary. Fig. IC illustrates the vocabulary learning procedure on a serialized molecular sequence. In this example, pair denotes an adjacent atom-bond symbol, e.g. (C,-). At each iteration the most frequent pair is replaced at all disjoint occurrences by a new token T,, and the corresponding merge rule (Sa, +6) T, added to the codebook C. The updated sequence is then passed back the counting step, forming an iterative training loop.
The key insight of our framework lies in the interplay between structure- gructure-guided serialization and the BPE algorithm. The serialization function fg is not merely a format conversion tool but leverages the global frequency map F to ensure that statistically common local graph structures are systematically encoded as frequently adjacent symbol pairs in the sequence corpus Ds. This structured corpus forms an ideal input for BPE's greedy merging strategy. When BPE merges the most frequent pair ($2, st) (line 8), the operation is not arbitrary compression but the discovery of statistically salient tokens derived from graph data. Each merged token represents a larger subgraph fragment that can be recovered from the serialization. The resulting vocabulary Vr provides data-driven, structurally informed representation of the graph for the downstream Transformer.
Encoding and Decoding. After training. the procedure produces two components for inference: the frequency map F' and the BPE codebook C. To encode a new graph, the ENCODE procedure in Algorithm| is applied. The graph is first serialized into symbol sequence by the function f, we apply the merge rules R. from C in the learned order to obtain the final token sequence ST- The DECODE procedure in Algorithm reverses this process. The tokens in Sr are first expanded back into the original symbol sequence by applying the inverse of R. and the inverse serialization function f-1 then reconstructs the graph. These procedures ensure that the mapping between graphs and sequences is both reversible and deterministic, providing a bidirectional interface between the two domains.
The primary output of our framework is a discrete sequence of tokens Sr that faith- fully encodes the original graph. This sequential representation provides interface through which the Transformer ecosystem can be directly applied to graph-structured data (Vaswani et al., 2017). For graph-level prediction tasks such as classification or regression, the token sequence can be pro- cessed by an encoder-only model (c.g., BERT). A special [CLS] ] token may be prepended, or the final hidden states pooled, to derive a vector representation for the entire graph (Perozzi et al., 2014). For generative tasks, a decoder-only model (e.g., GPT) can be trained to generate graphs auto- regressively by predicting the next token in the sequence, supporting applications such as molecular or material discovery (Radford et al., 2019). Multimodal models can also support tasks such as graph summarization, where we use pretrained graph representations from the proposed tokenizer with a large language model to generate concise descriptions of input graphs (Yamagata et al., 2023).
Applications.
In summary, the proposed graph tokenizer reframes graph representation learning as a sequence modeling problem. Our method decouples the structural complexity of graphs from the architectural design of the model and enables direct use of advances in sequence modeling, such as longer context windows (Ding al., 2022) and more efficient attention mechanisms (Dao et al., 2022) for wide range of graph learning tasks.
EXPERIMENTS
In this section, we evaluate our proposed graph tokenizer, GraphTokeni zer (GT), We aim to answer the following questions: (1) How effectively does BPE compress the serialized graph repre- sentations, and what is the efficiency of our approach in terms of sequence length, processing speed, and training throughput? (2) How does our framework, when paired with standard Transformer models, perform against state-of-the-
graph representation learning methods? (3) How do differ- ent design choices, such as the serialization method and BPE usage, affect performance? (4) Can the learned vocabulary and model attention provide interpretable insights into graph structures?
7

---

Published as a conference paper at ICLR 2026
4.1 EXPERIMENTAL SETUP
Datasets. We evaluate our method on 14 diverse public datasets for graph classification and re- gression. The benchmarks span multiple domains, including molecular graphs such as Mutagenicity (Muta) and Proteins (Riesen & Bunke, 2008), OGBG-molhiv (Hu et al., 2020), ZINC (Irwin et al., 2012), AQSOL (Sorkun et al., 2019), and QM9 (Wu et al., 2018); computer vision graphs like COIL-DEL (Rossi & Ahmed, 2015); graph theory like Colors-3 (Knyazev et al., 2019) and Syn- thetic (Feragen et al., 2013); biomedical graphs like DD (Dobson & Doig, 2003) (Bechler-S Speechrr al., 2024) and Peptides (Freitas al., 2020); social networks (Twitter (Pan al.. 2015)); and academic networks (DBLP (Pan et al., 2013)). A summary of dataset statistics is provided in Ap- pendix C.I.
Baselines. Our approach is benchmarked against a comprehensive set of baselines, ranging from classic GNNs (GCN (Kipf, 2016), GIN (Chen et al., 2019)) to sfate-of-the-art models, including the powerful GCN+ (Luo et al., 2025), Graph Transformers like GraphGPS (Rampášek et al., 2022), and the erializatioon-asee GraphMamba (Wang et al., 2024). To ensure a fair comparison, all baseline results are from official implementations run on our unified data splits and preprocessing pipeline (Dwivedi et al., 2023; Luo et al., 2025; 2023; Bechler-Speicher et al., 2024). Results on key benchmarks are in the main text; the rest are Appendix D.
Implementation Details. Our proposed method, GraphToken zer (GT), encodes graphs into token sequences that are subsequently processed by a standard Transformer model for downstream tasks. We report results with two Transformer backbones: (1) GT+BERT, which adopts the BERT- small architecture (Devlin et al.. 2019), and (2) GT+GTE, which uses the more recent GTE model with parameter count comparable to BERT-base (Zhang et al., 2024). By default, the tokenizer ap- plies the Frequency-Guue Guided Eulerian circuit (F (Feuler) serialization method followed by Byte Pair Encoding (BPE) on the resulting sequences. In the main results table, we report the best perffrrnfonming serialization for each dataset; a comprehensive comparison across all serialization methods is pro- vided in the ablation study (Table 3) and Appendix D.3. Further details on model architectures, dataset splits, and hyperparameter settings are provided in Appendix C.3.
4.2 PERFORMANCE RESULTS
We present the main performance comparison on representative subset of classification and regres- sion benchmarks in Tables For each dataset, we report the mean and standard deviation of the primary evaluation metric on five independent runs.
Sequence length and efficiency. Figure 2 illustrates the impact of our tokenizer efficiency. As shown in Figure 2a, BPE achieves a high compression ratio, reducing sequence lengths from reversible methods to approximately 10% of their original size. Notably, the frequency-guide Eulerian method (Feuler) produces more compact sequences post-BPE than its unguided coun- terpart, confirming that our structure-guided serialization is particularly well-suited for BPE. This compression translates directly to improved training efficiency. Figure 2b shows that with BPE, our approach using a standard Transformer backbone becomes significantly more efficient than spe- cialized Graph Transformers like GraphGPS and even surpasses classic GNNs such as GatedGCN. While the speedup (e.g., 225x on z ne for a 10x compression) not linear due to model over- head, the gains are substantial. This demonstrates that our graph tokenization framework not only enables standard sequence models to process graphs but also makes them a highly efficient and performant option for graph learning tasks.
Classification and Regression. Table 2 presents the performance classification and regression benchmarks, reporting the mean and standard deviation over five independent runs. Our approach, particularly with the GTE backbone (GT+GTE), achieves state-of-the-art results on a majority of the 14 benchmarks. On the ogbg mo 1 hiv benchmark, for instance, GT+GTE attains an ROC-AUC of 0.876 on our test split (val 0.903), significantly exceeding reported leaderboard results (test 0.8475, val 0.8275). This strong performance is achieved using an off-the-shelf sequence model without any graph-speciff architectural modifications. Furthermore, the framework's 's effectiveness is evident even with the compact GT+BERT model, which already outperforms strong baselines on several datasets. Critically, scaling up to the larger GT+GTE backbone yields consistent performance gains across the board, demonstrating clear advantage over many GNN architectures that can suffer from performance degradation with increased model capacity due to issues like over-smoothing. We further validate these findings through expanded evaluation in Appendix D.2. which includes comparisons against additional ofate-of-the-ans art architectures (e.g.. Graphormer, FragNet) and LLM- based Graph Foundation Models (e.g., GraphGPT, ILAGA)..
8

---

Published as a conference paper at ICLR 2026
21.04
wi BPE
w/ BPE
Sequencoe (K)
13.00
Compression Ratio
1044X
19.34
11,15x
11,14x
GNN
Comprass Ratio
Epoch (s)
8.40c
15
7.24x
6.08x
10
8.8b
1.5
5.x
2.5g
2.7
DFS
BF5
TOPO
SMILESEuleitan Feuler
CPP
FGPP
DFs
Euloian
GPP
GatedGGN GraphGPS
GMamba
Method
Method
(a) BPE achieves high compression ratios.
(b) Training time per epoch.
Figure 2: Efficiency analysis on the ZINC dataset. (a) BPE greatly reduces token sequence length from serialization. (b) Graph tokenization leads substantial training speedup by enabling efficient processing with standard Transformers.
Table 2: Results of classification (left block) and regression (right block). The best scores shown in bold, the second-best are underlined, and standard deviations are given in parentheses. Results for the remaining datasets presented in Appendix D.
molhiv
F-Eune apt
mutag ace?
co1.ddel accf
dblp
gm9
2inc mael
agsol mac]
p-struct ruct
Model
auct
ace
mac.
avg mace
GCN
74.0 (.
$3.2 (14:
79.7 (17)
74.6 m.)
76.6 (0.)
0.134 (0004)
0.399 (0.00)
1.345 (0.01))
0.342 (0000))
GIN
76.1
61.4
80.4
72.0
73.8
0.176
0.379
2,053
0.338
GAT
72. (0
51.2
80.1 (19)
74.4 ILD
76.3 (07)
0.1 (0015)
0.445 (0.015)
1,388 (0.000)
0,316 (0.06)
GatedGCN
80.6 (0.)
51.2 (1:)
83.6 (0:)
(0.4)
86.0
0.096 (0.00))
0.370
0,940 (0.00)
0.312 (0/044)
GraphGPS
78.5 (1.5)
53.5 (.7)
84.3
80.5
71.6 (0u))
0.084 (0.04)
0.310 (0.00)
1.587 (0.001)
0.251 (0.001)
Exphormer
82.3 m07)
64.5 m::
82.7 (1.1)
91.5 m.3)
84,9 (04)
0.080 (poee))
0.281 (0:000)
0,749 (0.006)
0.251 (0.00))
GraphMamba
81.2
67.7 (0:)
85.0 (1.)
74.5
87.6
0.083 (0.05)
0.209 (0.00))
1.133 (0:04))
0.248
GCN+
80.1 (04))
72.6 (U:)
88.2 (0:6)
88.9 (..))
89.6 (04)
0.072 (0.00)
0.116 (0.00))
0.712 (0.000)
0.244
(0.001)
GT+BERT
82.6 (0:4)
68.5 (15)
87.5 (0.)
74.1 (a.)
93.2 (01)
0.122 (0.00)
0.241 (0.01))
0.648 (0.000)
0.247
(0.000)
GT+GTE
87.4
73.1
90.1
89.6
93.6
0.071 (0004)
0.131
0.609
0.242
4.3 ABLATION STUDIES
We conduct ablation studies evaluate the impact of different serialization methods and the BPE tokenization step while keeping the GT+GTE backbone fixed. Table 3 shows that the choice of serialization has a significant impact on performance. Reversible methods that traverse every edge (e.g., Eulerian and CPP variants) significantly outperform non-reversible node-list traversals, with only few exceptions detailed Appendix Within the reversible category, the frequency-guides Eulerian circuit (Feuler) demonstrates a clear advantage over its unguided counterpart, not only mean performance but also in reduced variance, indicating greater stability. In contrast, the per- formance gap between CPP and its frequency -uidded version (FCPP) remains minimal. A plausible explanation that CPP's objective of finding minimum-weight traversal already yields highly structured sequence, leaving limited room for further improvement from frequency-basee guidance. Although FCPP performs comparably to Feuler, Feuler provides substantial benefits algo- rithmic complexity (Appendix B.5) and scalability, making it more practical choice for larger graphs.
A second key finding is that applying BPE to serialized sequences substantially improves model performance. Across nearly all configurations, BPE yields higher scores with a clear performance margin. This improvement is accompanied by reduced standard deviation, indicating and reliable training. Moreover, these performance gains come in addition to the substantial effi- ciency improvements discussed previously in Figure 2. Therefore, BPE is critical component of our framework, enhancing both accuracy and computational efficiency.
stable
Additional ablation studies in Appendix D.3 further investigate the sensitivity to the BPE vocabulary size K, the choice of statistical guidance unit for frequency collection, and the impact of serialization strategies on graph counting tasks (e.g., the COLORS-3 dataset).
Visualizing the Learned Vocabulary. To examine the structural semantics captured by tok- enizer, we visualize the vocabulary constructed by BPE on the ZINC dataset. As shown in Figure 3, BPE iteratively merges simple, frequent substructures into progressively complex and chem-

---

Published as a conference paper at ICLR 2026
Table Ablation of serialization method orderings with and without BPE. The best scores 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 molecular graph.
molhiv auct
coildel acef
Func apt
sinc
gm9
Method
mac)
mae,
BES
72.3 (1.)
81.2 (1.9)
81.2 (0.)
80.1 (1:3)
68.5 (M.)
67.2 (0.)
0.453 omm:1
0.696 0.013)
0.311 (000;
0.292 (0.01)
76.0
79.1 0.5)
79.8 m:0
(1:))
68.4
m000))
0.705 0100))
0.291 m100)
(uone)
TOPO
73.2
75.6 00.0
82.6 m3))
81.4 0.2)
67.9
64.5 (0.)
0,416 oumo)
0.634 (0011)
0.293 oume:
0,275 (1013)
Eulerian
84.5 00.7
81.0
84.1 (.5)
84.0 0.5)
69.1 (AS)
66.8 (1.3)
0.164 (u009)
0,160 (.me)
0.083 (L00)
0.104 (0u0s)
Feuler
87.4
81.3
88.0
85.6
73.1
68.1
0.131
0.171
0.071
0.088
CPP
86.9 (0.31
81.2 (.5)
89.6 (0.1)
86.7 (0.)
69.2 (X2)
67.0 (..))
0.141 (unos)
0.145 (0.09)
0.073 (0004)
0.093 (00s)
FCPP
86.4
81.0
89.4
86.8
69.2
66.3
0.140
0.151
0.079
0.095
SMILES
0.201 01007)
0.339 (1.08)
0.092 (1008)
0.081 (1044)
ically meaningful tokens. For example, a basic sulfonyl group is first established as a token, and then combined with adjacent atoms to form larger functional groups. This confirms that BPE can automatically discover and compose semantically relevant substructures, yielding an interpretable, hierarchical vocabulary.
Token ID: 731
Token ID: 921 Sequence: C[s
Token ID: 2908 Sequence: CC[5
Sequence: O=S=0
Token ID: 1201
Token ID: 2132
Token ID: 2163
Sequence: clccoccl
Sequence: Cclccccc1
Sequence: CCclcccec1
Figure 3: Illustration of the BPE merging process ZINC. Each shows how simple substruc-
tures (left) are iteratively merged to form larger, chemically meaningful tokens (middle and right).
statistical analysis of the vocabulary (K=2000) on ZINC further supports these observations: token size distribution peaks in the 4-6 node range (41.5%), which corresponds to typical func- tional groups, while atomic tokens (0-1 nodes) comprise only 7.1%. Over 60% of the vocabulary represents multi-node substructures, confirming that BPE discovers optimal level of abstraction. Further analysis is provided in Appendix D.1.
5 CONCLUSION
In this paper, introduce general framework for graph tokenization that bridges graph-structured data with the Transformer ecosystem. Our approach combines reversible, structure structure-guided graph serialization with BPE to construct faithful and efficient interface that encodes graphs into discrete token sequences. Fundamentally, the framework decouples the design of graph representations from the underlying model architecture, thereby reframing graph learning as a sequence modeling prob- lem. This perspective enables graph data to be directly integrated into general- pprpose Transform- ers, allowing the graph learning field to leverage rapid advancements in model architectures, training strategies, and scaling capabilities. Empirically, we demonstrate that this approach enables standard off-the-shelf Transformers to process graph data effectively and achieve state-of-the-an results on diverse set of benchmarks, outperforming established GNNs and specialized Graph Transformers. Limitations this work and directions for future research are discussed in Appendix A.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work is supported in part by the National Natural Science Foundation of China (No. 62550138, 62192784, 62572064, 62472329), and Young Elite Scientists Sponsorship Program (No.2033ONR001) by CAST.
ETHICS STATEMENT
The authors this work have read and commit to adhering to the Code Ethics. Our research proposes foundational framework for graph tokenization and, to the best of our knowledge, does not present any direct ethical concerns. The work does not involve the use of personally identifi- able information, sensitive human-subjer data, or applications with immediate potential for societal harm.
REPRODUCIBILITY STATEMENT
To ensure full reproducibility, our complete source code is provided the supplementary materials. This source code contains training configuration files for all experiments, and the necessary scripts to preprocess datasets from their original sources. For convenience, ready-to-use versions of the datasets also provided. Comprehensive details the experimental setup documented in the Appendix, including the datasets (Appendix C.I). I), model architectures (Appendix C.2), hyperparam- eter configuration (Appendix C.3), and runtime environment (Appendix C.4).
REFERENCES
Maya Bechler-Speicher, Amir Globerson, and Ran Gilad-Bachrach. The intelligible and effective graph neural additive network. Advances in Neural Information Processing Systems, 37:90552- 90578, 2024.
N. Biggs, E.K. Lloyd, and R.J. Wilson. Graph Theory, 1736-1936. Clarendon Press, 1986. ISBN 9780198539162. URL https: /books.o.....o gwwgle e pn. http///oos...xxxxxxkkxppppoo
Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.081 2024.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in neural information processing systems, 35:16344-16333 2022.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pp. 4171-4186 2019.
Lei Ding, Dong Lin, Shaofu Lin, Jing Zhang, Xiaojie Cui, Yuebin Wang, Hao Tang, and Lorenzo Bruzzone. Looking outside the window: Wide-context transformer for the semantic segmentation of high-resolution remote sensing images. IEEE Transactions on Geoscience and Remote Sensing, 60:1-13, 2022.
Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1929, 2020.
11

---

Published as a conference paper at ICLR 2026
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Jack Edmonds and Ellis L. Johnson. Matching, euler tours and the chinese postman. Mathe- matical Programming, 5:88-124, 1973. URL /ttp://appi. sepat.eennttccchoo...r.
:
Even and G. Even. Graph Algorithms Cambridge University Press, 2011. ISBN 9781135041557. URL htwps: /tts:s////oooooo/e/ googee wwtpooggle.cooooooooooooooooeooo http:/oooksiiimm001e..
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen De Bruijne, and Karsten Borgwardt. Scal- able kernels for graphs with continuous attributes. Advances neural information processing systems, 26, 2013.
Luciano Floridi and Massimo Chiriatti. Gpt-3: Its nature, scope, limits, and consequences. Minds and machines, 30(4):681-694 2020.
Scott Freitas. Yuxiao Dong, Joshua Neil, and Duen Horng Chau. A large-scale database for graph representation learning. arXiv preprint arXiv:2011.00 wew.2001100782. 2020.
Jian Gao, Weidong Cao, Junyi Yang, and Xuan Zhang. Analoggenie: A generative engine for automatic discovery of analog circuit topologies. The Thirleenth International Conference Learning Reprexentations, 2025.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. Pmlr, 2017.
Yuan Gong, Yu-An Chung, and James Glass, Ast: Audio spectrogram transformer. arXiv preprint 0110022 2021.
Daya Guo, Dejian Yang, Haowei Zhang. Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in lims via reinforcement learning. arXiv preprint arXiv:2501.12945 2025.
Yuxin Guo, Deyu Bo, Cheng Yang, Zhiyuam Lu, Zhongjian Zhang, Jixi Liu, Yufei Peng, and Chuan Shi. Data-centric graph learning: A survey. IEEE Transactions Big Data, 1 11(1):1-20, 2024.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-nixer to graphs. In International conference on machine learning, pp-
12724-12745. PMLR. 2023.
Carl Hierholzer and Chr Wiener. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathemaatschh Annalen, 6(1):30-33) 32, March 1873. ISSN 1432- 1807. doi: 10. 10.000///000442866 URL https: /ooi. . org/ 11.. 1 200000//FBT 442866.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 1122118-221 22133,223322 2020.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7):1777-1768, 2012.
A. B. Kahn. Topological sorting of large networks. Commun. ACM, 5(11):558-562, November 1962. ISSN 0001-0782. doi: 00.114453689966366005, URL //t//////.. /oi. httpl//.gr/00111////// 368996. 369025.
TN Kipf. Semi-supervised classification with graph convolutional networks. 1rXiv:160. 2016.
arXiv preprint
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks, Advances in neural information processing systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2026
Xiangzhe Kong, Wenbing Huang, Zhixing Tan, and Yang Liu. Molecule generation by subgraph mining and assembling. Advances in Neural Information Processing Systems, 35:2550- 2563, 2022.
Mei-ko Kwan. Graphic programming using odd or even points. Acta Mathematica Sinica, 10:263- 266, 1960. Also translated in Chinese Mathematies American Mathematical Society, 1962, pp- 273-277.
Yunhui Liu, Tieke He, Yongchao Liu, Can Yi, Hong Jin, and Chuntao Hong. Tabular foundation models are strong graph anomaly detectors. arXiv preprint arXiv:2601. 17301, 2026.
Xiao Luo, Yusheng Zhao, Zhengyang Mao, Yifang Qin, Wei Ju, Ming Zhang, and Yizhou Sun. Rignn: rationale perspective for semi-supervised open-world graph classification. Transactions Machine Learning Research, 2023.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Can classic gnns be strong baselines for graph-level tasks? simple architectures meet excellence. arXiv preprint wxXi:22502.09263, 2025.
Shervin Minaee, Tomas Mikolov, Narjes Nikzad, Meysam Chenaghlu, Richard Socher, Xavier Am- atriain, and Jianfeng Gao. Large language models: A survey. arXiv preprint arXiv:2402.06196, 2024.
E. F. Moore. The shortest path through maze. In Proc. International Symposium on the Theory of Switching, Part II. harvard, 1959.
Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Philip Yu. Graph stream classification using labeled and unlabeled graphs. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 398-409. IEEE, 2013.
Shirui Pan, Jia Wu, and Xingquan Zhu. Cogboost: Boosting for fast cost-sensitive graph classifica- tion. IEEE Transactions on Knowledge and Data Engineering. 27(11):293332 2946, 2015.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9, 2019.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 15511-1114555 2022.
Kaspar Riesen and Horst Bunke. Iam graph database repository for graph based pattern recogni- tion and machine learning. In Joint IAPR international workshops on statistical techniques in paltern recognition (SPR) and structural and syntactic pattern recognition (SSPR), pp. 287-297. Springer, 2008
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL tetttp:://networkrrppsss
com.
Yuchen Shen and Barnabás Póczos. Graphbpe: Molecular graphs meet byte-pair encoding, arXiv preprint arXiv:2407. 19039, 2024.
Yusuxke Shibata, Takuya Kida, Shuichi Fukamachi, Masayuki Takeda, Ayumi Shinohara, Takeshi Shinohara, and Setsuo Arikawa. Byte pair encoding: text compression scheme that accelerates pattern matching. Technical Report DOI-TR-166 Department Informatics, Kyushu University, 1999.
Murat Cihan Sorkun, Abhishek Khetan, and Süleyman Er. Aqsoldb, a curated reference set of aqueous solubility and 2d descriptors for a diverse set of compounds. Scientific data, 6(1):143, 2019.
13

---

Published as a conference paper at ICLR 2026
Jiabin Tang. Yuhao Yang. Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th In- ternational ACM SIGIR Conference Research and Development in Information Retrieval, pp- 491-500, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Chloe Wang, Oleksii Tsepa, Jun Ma, and Bo Wang. Graph-mamba: Towards long-range graph sequence modeling with selective state spaces. arXiv preprint arXi:22402.00889 2024.
David Weininger. Smiles, chemical language and information system. introduction method- ology and encoding rules. Journal of chemical information and computer sciences, 28(1):31-36 1988.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and
Junchi Yan. Sgformer: Simplifying and empowering transformers for large-graph representations. Advances in Neural Information Processing Systems, 36:64753-64773, 2023.
Zhengin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513-530, 2018.
Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. Random walks: A review of algorithms and applications. IEEE Transactions on Emerging Topics in Com- putational Intelligence, 4(2):95-107, 2019.
Taku Yamagata, Ahmed Khalil, and Raul RodrigeR Q-learning decision transformer: Leveraging dynamic programming for conditional sequence modelling in offline rl. In Inter- national Conference on Machine Learning, pp. 38989-399999 39007. PMLR, 2023.
Bo Yan, Cheng Yang, Chuan Shi, Jiawei Liu, and Xiaochen Wang. Abnormal event detection via hypergraph contrastive learning. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), pp. 712-720. SIAM, 2023.
Bo Yan, Yang Cao. Haoyu Wang, Wenchuan Yang. Junping Du, and Chuan Shi. Federated heteroge- neous graph neural network for Web Conference 2024, pp.
recommendation. In Proceedings of the ACM 2024.
Bo Yan, Zhongjian Zhang, Huabin Sun, Mengmei Zhang, Yang Cao, and Chuan Shi. Data-centric federated graph learning with large language models. arXiv preprint arXiv:2503. 19455, 2025.
Ling Yang, Ye Tian, Minkai Xu, Zhongyi Liu, Shenda Hong, Wei Qu, Wentao Zhang, Bin Cui, Muhan Zhang, and Jure Leskovec. Vggraph: Rethinking graph representation space for bridging gnns and mips. arXiv preprint arXiv:2308.08 02 2023.
Shuo Yu, Yingbo Wang, Ruolin Li, Guchun Liu, Yanming Shen, Shaoxiong Ji, Bowen Li, Fengling Han, Xiuzhen Zhang. and Feng Xia. Graph2text or graph2token: A perspective of large language models for graph learning. arXiv preprint arXiv:2501.01124 2025.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph trans- former networks. Advances neural information processing systems, 32, 2019.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
Shuaicheng Zhang, Haohui Wang, Si Zhang, and Dawei Zhou. Gpatcher: A simple and adaptive mlp model for alleviating graph heterophily. arXiv preprint arXiv:2306.1433 2023.
Xin Zhang, Yanzhao Zhang, Dingkun Long, Wen Xie, Ziqi Dai, Jialong Tang, Huan Lin, Baosong Yang, Pengjun Xie, Fei Huang, et al. mgte: Generalized cong-context text representation and reranking models for multilingual text retrieval. Proceedings of the 2024 Conference on Em- pirical Methods in Natural Language Processing: Industry Track, pp. 1393-1412, 2024.
14

---

Published as a conference paper at ICLR 2026
Zhongjian Zhang, Xiao Wang, Huichi Zhou, Yue Yu, Mengmei Zhang, Cheng Yang. and Chuan Shi. Can large language models improve the adversarial robustness of graph neural networks? In Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining V. I, pp. 2008-2019, 2025.
15

---

Published as a conference paper at ICLR 2026
Appendix
A DISCUSSION
This section provides candid discussion of our framework's limitations and outlines promising avenues for future research.
A.I LIMITATIONS
Graphs with Continuous Features. Our framework operates by first converting a labeled graph into sequence of discrete symbols, which subsequently forms the input for Byte Pair Encoding (BPE). This process implicitly assumes that the features associated with nodes and edges are discrete and can be directly mapped to an initial symbol alphabet. Consequently, graphs where attributes are primarily continuous (e.g., real-valued vectors) cannot be handled natively. The required conver- sion of continuous attributes into a finite set of discrete symbols always needs a quantization step, which is inherently lossy. This directly conflicts with our framework's 's core principle of creating a faithful and reversible representation. Integrating continuous features principled manner along- side our discrete tokenization process therefore remains key limitation. However, as elaborated in Appendix A.2, this is not a fundamental blockage. We propose that continuous features can be effectively integrated via Vector Quantization (VQ) interfaces or by treating continuous attributes as a parallel modality fused with token embeddings.
Node and Edge Level Tasks. The current framework is primarily evaluated on graph-level pre- diction tasks. Adapting for fine-grained objectives, such as node classification or link prediction, raises general consideration for graph tokenization: the Byte Pair Encoding (BPE) process, which essential for building an efficient vocabulary, may merge the specific target node or edge into a larger, composite token. As a result, the discrete identity of the target entity can be obscured, making difficult to formulate a direct prediction objective. To mitigate this, future iterations can introduce special "pointer tokens" to distinguish original nodes in composite token modify the BPE merge rules to prevent target nodes from being merged into composite tokens, thereby preserving their dis- tinct addressability.
Computational Complexity and Scalability. A key scalability limitation in our framework arises from the trade-off between different serialization methods. The Chinese Postman Problem (CPP) based approach, for instance, introduces a significant bottleneck: its O(V))) complexity renders impractical for datasets with large graphs. Consequently, we primarily adopt the highly efficient, linear-time Feuler method. With this choice, the main computational workload shifts to the BPE vocabulary training. However, this is far more manageable constraint, as BPE training is a one- time, offline cost, and its practical runtime impact is a constant-factor consideration rather than a prohibitive asymptotic scaling issue (as detailed in Appendix B.5). A separate, downstream con- straint is the Transformer's fixed context window, which limits the maximum size of a single graph. While this is an inherent limitation of the model architecture, our BPE compression significantly alleviates the issue, and adopting long-context models provides clear path for future scaling.
A.2 FUTURE WORKS
Our work opens several promising avenues for future research. Below, we outline these potential directions, ordered based on our perspective of their potential impact and research scope.
Graphs with Continuous Features. To extend our framework to graphs with continuous features, a straightforward approach would be to first discretize them using methods like vector quantization (Yang et al., 2023) and then apply our pipeline. However, we argue this direction is suboptimal, as such quantization is inherently lossy and conflicts with creating a faithful, reversible representation.
our framework's core principle promising direction is to treat discrete and continuous information in parallel channels. For instance, features learned via message passing could be incorporated as a continuous bias added to the discrete token embeddings, analogous how positional encodings supplement token information in standard Transformers. Alternatively, spectral graph theory offers a principled way to derive global information; the eigenvectors of the graph Laplacian could
more
16

---

Published as a conference paper at ICLR 2026
be used to generate unique continuous encoding for each token's position within the global structure, complementing the discrete sequence.
Node and Edge Level Tasks. For adapting the framework to node or edge-level tasks, an intuitive strategy might be to predict the entire composite token that contains the target entity. However, this approach is problematic as it makes the learning signal less direct and can amplify prediction errors. A more targeted and principled approach would be to modify the BPE procedure itself. Specifically, we propose fixing the target entities so they are excluded from merging during tokenization. This would preserve the target's granularity for direct prediction, introducing an interesting trade-off between task-specific fidelity and overall vocabulary efficiency that warrants further investigation.
Generative Pre-training and Cross-Domain Generalization. A key advantage of our sequence-basee basence-based representation its potential for large-scale pre-training A natural next step is to explore pre-training on large corpora of graphs from within the same domain to enhance transferability. More ambitiously, our framework offers a new perspective on the grand challenge of cross-domain generalization. Since our method transforms any graph into a standard sequential format, we hypothesize that graphs from disparate domains can be treated as different 'languages' in NLP. This analogy extends to generative modeling: just as LLMs generate text, our framework enables autoregressive graph generation. We provide preliminary verification of this capability in Appendix D.1, demonstrat- ing that a standard decoder-only Transformer can generate valid graph structures. Consequently, training single, large-scale Transformer on diverse, multi-domain corpus of tokenized graphs could facilitate unprecedented knowledge transfer, potentially giving true Graph
rise to the scaling laws and unified representations that are foundational Foundation Models. Finally, such pre-training may also serve as a novel tool for analyzing datasets. Our preliminary results suggest that a dataset's s size does not always correlate with its 'information density,' and monitoring a model's 's overfitting on masked prediction task could provide a new way to quantify a graph dataset's quality and diversity.
Further Extensions and Applications. Our framework also opens several avenues for di- rect applications and algorithmic refinements. By reframing graph learning as a sequence modeling problem, it immediately enables the use of powerful autoregressive models, such as GPT-style architectures, for graph generation tasks like controllable molecular design. Furthermore, the sequential representation allows our method to seamlessly integrate with emerging long-context architectures to enhance scalability for massive graphs. Extend- ing the serialization to richer graph structures, such as heterogeneous information net- works (Yan et al., 2024) and hypergraphs (Yan et al., 2023), is another promising direc- tion. Finally, a more fundamental extension could involve making the serialization process itself learnable, where traversal decisions optimized end-to-end for specific down- stream task. While this could create a highly specialized graph-to-ser -o--eqeencee interface, also introduces significant challenges regarding generalization and stability.
A.3 USE OF LARGE LANGUAGE MODELS
In this work, we used large language models (LLMs) to assist with two substatttat aspects of the research workflow. No part of the scientific contributions-sut such as algorithm design, model architecture, theoretical formulation, or experimental evaluation- generated by or delegated to an L.M..
Manuscript Editing. LLMs were used to help polish the language of the manuscript. This includes surface-level edits such improving clarity, grammar, and conciseness of English expressions. All technical content, algorithmic designs, and empirical results were authored and validated by the authors.
* Code Documentation and Cleanup. At the time of open-sourcing our implementation, LLMs were used to assist in non-algorithmic tasks including: adding docstrings and in- line comments, generating basic usage documentation, removing deprecated or redundant code, and improving logging output for better reproducibility. All code functionality and correctness were manually verified by the authors.
17

---

Published as a conference paper at ICLR 2026
B FURTHER METHODOLOGICAL DETAILS
This section provides a formal and detailed supplement to the methodological discussions in Sec- tion We aim to precisely define how classical graph traversal algorithms are adapted for the task of graph serialization, and to rigorously analyze their resulting properties of reversibility and deter- minism, pinpointing the exact sources of their respective strengths and weaknesses for our frame- work. All notations, unless specified otherwise, follow the definitions established in Section 3.1.
B. DISTINCTION FROM NEURAL GRAPH TOKENIZATION METHODS
It is crucial to clarify that BPE differs fundamentally from neural-based continuous encoders such as VAE-based subgraph tokenizers (e.g., PS- (Kong et al., 2022)), linear projectors, or ViT- style patchified embeddings. These methods utilize learnable parameters project discrete inputs into continuous embedding spaces. While such continuous approximation is native for process- ing continuous signals (e.g., pixel intensities in CV), it introduces inevitable information loss and reconstruction ambiguity when applied to discrete structures like graphs. In contrast, our BPE ap- proach is a deterministic, statistics-based algorithm operating entirely within the discrete symbolic domain. It does not require neural network training and merges symbols based on frequency, avoid- ing the pradient-basee optimization complexity inherent in forcing discrete topology into continuous representations.
This distinction yields decisive practical advantages: (1) Reversibility: Our framework inher- ently lossless and deterministic. Since graph serialization preserves topology and BPE merging reversible via the vocabulary, we can reconstruct the exact graph structure up isomorphism, whereas VAEs rely on probabilistic decoders that only approximate the input. (2) Efficiency: BPE achieves significant sequence compression (over 10x) without the computational overhead of train- ing separate neural encoders, effectively reducing the quadratic complexity of the Transformer's at- tention mechanism. (3) Decoupling: By converting graphs into standard discrete symbol sequences, completely decouple graph representation from model architecture. Neural encoding strategies typically require specific graph encoders (e.g., GNNs) or specialized projection layers to bridge the modality gap. Once tokenized by our framework, graph is formally identical to natural language sequence and can be processed by any unmodified, off-the-shelf Transformer without specialized graph encoders or projection layers.
B.2 FORMAL ANALYSIS OF NODE-LIST SERIALIZATION METHODS
We first consider the class of methods that generate a sequence composed solely of node identifiers.
Formal Definition. When applied to graph serialization, a node- list traversal method a function
fuode 9 + S that maps labeled graph g = E), L, Σ) to a sequence of node labels S = (31, . Spy)). This sequence is generated by a traversal that visits every node in V exactly once. Let the sequence of visited nodes be (v), U2,.U..... ......, Upy)) where (Di...., U|1 V. The output sequence is then 5 (I(v1), L(12)...,,
(((p)))..,,((pp))) (()p))))
...
For Breadth- First Search (BFS) and Topological Sort, the order of nodes in the sequence reflects the layer-by-layee or dependency- traversal order. It is crucial to note that for E [|, 1), an edge (1, 66+1) ) is not guaranteed to exist in E.
For Depth-First Search (DFS), the standard algorithm produces a sequence where each node 1/+1 is an unvisited neighbor of (or node reached after backtracking). The quence of *first discovery* implics a tree structure (the DFS tree), but the output sequence itself does not encode this structure explicitly.
Reversibility. These methods are fundamentally irreversible. A serialization function f is re- versible if, for its output S = f()), the set of pre-images (aa contains a graph g' such that G' 1x G. For node-list methods, this condition fails. The output sequence S discards all ex- plicit edge connectivity information. Consequently, a vast number non-isomorphic graphs can produce the exact same node-label sequence. For example, consider two graphs three nodes (A, C) with identical labels: a path graph 9, with edges {(A, B), (B, C)} and star graph G2 with edges [(A, B), (A, C)}. A valid BFS starting from node A in 91 could produce the sequence
18

---

Published as a conference paper at ICLR 2026
(L(A), L(), and BFS starting from A in G2 could also produce the same sequence. From the sequence alone, it is impossible to distinguish G1 from G2, thus violating reversibility.
These methods are inherently non-deterministic. The source of non-determinism lies in the arbitrary selection of the next node visit from set of valid candidates. Formally, any step of the traversal from a node v. let Nuaia(u) be the set of unvisited neighbors (for BFS/DES) nodes with remaining incoming edges (for Topological Sort). Since Nuaii(u) an unordered set, any choice of v E (u) is permissible by the standard algorithm's definition. The final sequence is thus contingent on implementationnspeeiiii details, such the memory layout of the graph's 's adjacency list, which are not canonical properties of the graph itself. This leads to different sequences for the same graph, violating determinism.
Determinism.
B.3 FORMAL ANALYSIS OF EDGE-COVERING SERIALIZATION METHOSS
This class of methods generates sequences by performing walk that traverses every edge in the graph at least once.
Formal Definition. A walk W in a graph is a finite sequence of alternating nodes and edges,
"e....,,,. ck; Uk), where v; V, e &, and for all i E [1, k), edge e; (vi- 1, 0y) E. An edge-covering serialization function Sedge G + S maps 9 to the label sequence correspond- ing such walk, S (L(v)), [(e)), [(1),.... L(vw)): under the constraint that the multiset of edges in the walk, fei...., e covers the entire edge set of the graph, i.c., & C fei....., ex}.
W (vo, et, v1, .2,...,
For an Eulerian circuit, the algorithm is applied to graph where every undirected edge {u, u)
treated as pair of directed edges, (u, v) and u), forming an edge set E (Gao et al., 2025). The resulting walk traverses every edge in El exactly once.
For the Chinese Postman Problem (CPP), the algorithm finds walk W that covers & while minimizing the total weight of the walk, E w(e:), where w(e) is the weight of edge e (typically for unweighted graphs). This means some edges & may be traversed multiple times.
Reversibility. By definition, these methods are reversible. The output sequence S is composed of series of labeled triplets L(e)) ((v)). From this sequence, one can reconstruct the complete multiset of labeled edge traversals. Since this multiset is guaranteed to contain every edge from the original graph at least once, the full topology of can be losslessly recovered up to isomorphism. The mapping from the graph's structure to the information contained in the sequence injective.
Determinism.
In their classical forms, these methods are non-deterministic
For an Eulerian Path, the non-determinism stems from Hierholzer's algorithm. At any node u during the tour construction, let Junvisited be the set of untraversed edges incident to u. The algorithm proceeds by selecting an arbitrary edge from this set. As Eunvisited is an unordered set, this choice introduces ambiguity, leading to different valid Eulcrian circuits and thus different output sequences.
For the CPP, the primary source of non-determinism arises during the solution process. The algorithm first identifies the set of odd-degree nodes, Voda- It then computes minimum-weight weight perfect matching on a complete auxiliary graph constructed on Voaa- multiple distinct perfect matchings exist that share the same minimum total weight, the choice between them is arbitrary. This choice dictates which paths in the original graph are duplicated to form an Eulerian supergraph, ultimately resulting in different minimum-cost tours and thus different sequences.
Our proposed frequency-guiee mechanism (Section 3.2) addresses these specific sources of non- determinism by providing canonical, data-driven rule for making these choices.
B.4 DISCONNECTED GRAPHS
For completeness, we specify our procedure for handling graphs that are not connected. To ensure the overall serialization remains deterministic, input graph G is first decomposed into its set of
19

---

Published as a conference paper at ICLR 2026
connected components, {91, 02:...,Ge), Ge). Each component G3 is independently serialized into sequence S; using the chosen method. The resulting set of sequences {Si,..., Sc} is then sorted to produce canonical ordering. The sorting criterion is primarily the length of the sequence in descending order, any ties are resolved using standard lexicographical comparison. The final output is the concatenation of these sorted sequences. This guarantees that any given graph, regardless of its connectivity, maps to a single, unique sequence.
B.5 COMPLEXITY ANALYSIS
CPP Complexity. For CPP-based serialization, the end-to-end cost is O + (8]): O(D1) from the minimum-weight perfect matching on odd-degree vertices, and O(EE) from finding the Euler circuit after augmentation. Since Σ) S | (even |&| = ([V))) for a complete graph), we have O(VI3 [ O so throughout we denote the CPP family as O(V))).
Pipeline Complexity. We analyze the computational complexity of the GraphTokenizer train- ing procedure. Let DD = (Gi..... Gv be the training dataset, where G; = (Vi, &.). We define
Vs > [V:] and Lös Σ Bi=1 [&i] as the total number of nodes and edges in the dataset, respec- tively. Let K be the number of BPE merge operations and L be the average initial sequence length, where L Eg/N.
This stage requires single pass over all edges in the dataset to count local patterns. The complexity is therefore (EE))
Statistics Collection.
Graph Serialization. As summarized in Table 1, the complexity depends on the chosen method. Traversal-ban baaed methods such as Eulerian an (and its guided variant Feuler) are linear in graph size, with total cost for the dataset of O(Vs + Es). In contrast, CPP (and its guided variant FCPP) is dominated by solving a minimum-wert weight perfect matching for each graph, yielding a total complexity of O [V) Assuming relatively homogeneous distribution of graph sizes, this can be expressed as O(N )3) = 0 Ve
BPE Training. The complexity of the BPE training phase (Lines 6-14) is dominated by the se- quence merge operation. For a standard implementation using dynamic arrays, the cost of a merge is proportional to sequence length. We analyze the total complexity under two bounding scenarios.
First, consider the case where small number of pairs are merged per iteration. The work is domi- nated by rewriting all N sequences for each of the K iterations, leading to total complexity of:
C O(K N
Second, consider the case where a maximal number of pairs are merged, halving the total corpus length n =
NL in each step. The work performed can be described by the recurrence relation:
T(n) = = + (())
where (n) is the cost of a single merge pass. For naive array- merge, f(n) = (+)
0( n² ). By the Master Theorem, with = 1.6 = 2, d = 2, we have d > log, a, so the total
N
complexity is dominated by the root node's work:
C2 =0 22 N ) O(NI2)
(10)
If the merge operation were optimized to be ((1) per merged pair (e.g., using linked list represen- tation or mark new token only at range endpoint to be replaced), then f(n) = O(n). In this case, = 1 > log, 1, so the complexity would be:
C2.opt 0n))= O(NL)
(11)
The final complexity depends on the termination criterion. We employ fixed number of iterations, K, to allow for flexible control over the final vocabulary size and compression ratio across experi- ments. In typical settings, K (e.g., 103 - 104) is much larger than the average sequence length L (e.g.. 102). making the C₁ term the dominant factor. Alternatively, if one were to terminate based on minimum frequency threshold, the process would resemble the recursive scenario, making C2
20

---

Published as a conference paper at ICLR 2026
the more relevant complexity model. Given our fixed-iteration approach, the overall BPE training complexity is:
CEPE O(K N L) (OKOOKKO00 Es))
(12)
Overall Training Complexity. For serialization with Feuler and other methods with linear time complexity, the total complexity dominated by the BPE training, resulting in O(K Es). If minimum-frequency stopping criterion were used, the complexity would instead be dominated by
the n, term, becoming O - NN = O(NL3) = 0 F ). For serialization with FCPP, the total complexity dominated by the most expensive component, yielding 0
V N
+ K Es) =
0 Vea N
which in practice for large graphs, implies that the serialization becomes the bottleneck.
C
EXPERIMENTAL SETUP
This section provides the comprehensive configuration details required fully reproduce all exper- iments presented in this paper.
C.I DATASETS
Our evaluation is conducted on diverse suite of benchmark datasets. The aqsol and zinc datasets sourced from the benchmark collection proposed by (Dwivedi et al., 2023), while the remaining datasets are standard benchmarks obtained from libraries such as PyTTrrch Geometric (PyG) and DGL. Table 4 below offers comprehensive summary of their statistical properties and raw feature dimensions.
Table 4: Comprehensive statistics and feature dimensions for all benchmark datasets. Node and edge counts are presented as mean standard deviation. "Raw Dim" refers to the dimensionality of the original features before they are mapped discrete integer symbols.
Dataset
Graphs
Tusk Regression Classifiatiin
# Nodes (Mean Std)
Edges (Mean
Std)
Node Row Dim
Edge Row Dim
ageol
9,833
33.7
21.5
67.9 50.0
65
coildel
3,900
100
21.5 =: 13.2
108.5 77.0
2
colore3
10,500
Classification
80.5
182.1 187.3
4
dblp
19,456
Classifiation
10.5
39.3 39.3
1
dd
1,178
Classifiatiinn
284.3 272.1
1431 1388.4
1
Classification
muta
4,337
Clasification
30.3 20.1
61.5 33.6
]
p- funu
15,335
MT-CClasoficatioo
10
150.9 + 84.2
307 3 172.2
9
p-struct
MT-Rognesion
proteins
1,113
Classiication
39.1 45.8
145.6 6 169.3
2
qma
130,311
Regression
16
18.0 + 2.9
37.3 + 6.3
16
synthetic
300
Clasification
0.0
twitter
144,033
Classficatio
4.0 1.7
10.0 1:
1
zine
12,000
Regression
43.8 4: 8.5
91.1 4 18.1
28
C.2 MODEL ARCHITECTURES
We employed two Transformer backbones in our experiments. The first, which we denote as GT+BERT, is based on BERT-Small architecture. The second, GT+GTE, utilizes cent and powerful GTE-Base model. The precise architectural parameters for each are detailed side-by-side in Table 5. This format facilitates direct comparison and is designed accommodate additional model configurations in future scaling law studies. Note that the vocabulary size is de- termined dynamically based on the dataset and tokenization strategy, causing the total parameter count to vary slightly across experiments, the results reported here include the embedding layer size corresponding to the vocabulary encoded using BPE on the ZINC dataset.
C.3 HYPERPARAMETERS
Our hyperparameter tuning strategy was designed for systematic evaluation and reproducibility rather than exhaustive per-dataset optimization. We established a robust base configuration, de- tailed in our publicly available configuration files, which was applied to all experiments by default. For certain datasets, particularly those with very large or very small graphs, targeted adjustments made key parameters like batch size and learning rate ensure stable training.
21

---

Published as a conference paper at ICLR 2026
Table 5: Architectural parameters of the Transformer backbones used in our experiments.
Parameter
GT+BERT GT+GTE
Model Configuration
BERT-Small GTE-Base
Number of Hidden Layers (N)
12
Hidden Size (dmodde)
512
768
Number of Attention Heads (h)
12
FFN Intermediate Size (dn)
2048
3072
Activation Function
GELU
GELU
Dropout Rate (Attention & Hidden)
0.1
0.1
Position Embedding
Learned Abs
RoPE
Max Sequence Length
768
8192
Layer Normalization e
le-12
le-12
Total Parameters (Approx.)
~ 15M
115M
Table provides comprehensive overview of these settings. The "Default Configuration" column represents the base values applied to all datasets unless otherwise specified. The subsequent columns detail the specific overrides for datasets or groups of datasets that required adjustments. This unified view clearly illustrates both our general training strategy and the specific exceptions made.
Table Unified hyperparameter specification. This table details the default values used for training and the specific conditions under which they were overridden.
Parameter
Default Value
Exceptions & Conditions
General Settings
Optimizer
AdamW
Epochs
200
Weight Decay
0.1
Random Seed
42
Batch Size
32
16 (DBLP, and COIL-DEL)
Serialization & Tokenizer Settings
Default Method
Feuler
BPE Enabled
True
BPE Merges (K)
2000
Finetuning Settings
Learning Rate
le-5
5e-5 on (DBLP, moliiv, twitter)
LR Warmup Ratio
0.025
Max Gradient Norm
0.5
Early Stopping
20 epochs
Pre-training (MLM) Settings
Learning Rate
le-4
5e-5 on (muta, molhiv, qm9, twitter, dblp) For GTE, prevent training instability.
LR Warmup Ratio
0.12
Max Gradient Norm
2.0
Mask Probability
0.09
C.4 COMPUTATIONAL ENVIRONMENT
Software. Our implementation relies shared software stack to ensure consistency. The key packages and their versions are listed below. For a complete and exhaustive list of dependencies, please refer the environment files in public code repository.
22

---

Published as a conference paper at ICLR 2026
Py Torch: 2.1.2
CUDA Toolkit: 12.1
DGL: 2 2.4.0
PyTorch Geometric (PyG): 2.4.0 (with corresponding
libraries
pyg-lib,
etc.
Hardware. All experiments conducted on heterogeneous cluster of NVIDIA GPUs, in- cluding consumer grade (GeForce RTX 2080, 3090, 4090) and data center grade (A800, H800) hardware. We verified that results stable and consistent across these different architectures.
C.5 HYPERPARAMETER SETTINGS FOR ADDITIONAL BASELINES
To ensure a fair comparison in the extended benchmarks (Appendix D.2), we adopted the official configurations for all baseline models whenever available:
Graph Transformers (GraphGT, Graphormer): We utilized the standard hyperparam- eters provided in their official implementations (e.g., 6-12 layers, hidden dimension of 80-768 depending on dataset size) match the parameter budget of our models.
Graph Foundation Models (GraphGPT, LLAGA): For the adaptation experiments, used the open-sourced checkpoints (e.g.. LLaMA-2-7b backbone) and fine-tuned the pro- jection layers LoRA adapters following the protocols specified in their original papers.
Specialized Architectures (FragNet, Seoph--VTT-LLMMM sults using the optimal settings reported in their respective publications.
We reproduced these re-
D EXPERIMENTAL RESULTS
In this section, we present comprehensive suite of additional experiments further validate the robustness, interpretability, and comparative performance of our proposed framework. The content organized as follows:
Qualitative Analysis (Appendix D.1): We offer detailed interpretation of the learned BPE vocabulary to elucidate the structural semantics captured by our tokenizer, and provide proof-of-concept for autoregressive graph generation.
Performance Benchmarks (Appendix D.2): We report complete results for all datasets and expand our comparative evaluation to include recent statc-of-the-ar Graph Trans- formers (e.g., GraphGT, Graphormer) and LLM-based Graph Foundation Models (e.g., GraphGPT, LLAGA).
Ablation Studies (Appendix D.3): We conduct systematic investigations into core design choices, ranging from architectural components (e.g., Transformer backbones, serialization methods) to specific hyperparameters (e.g., vocabulary size, statistical guidance units), and empirically validate the impact of serialization strategies counting tasks.
Scalability Analysis (Appendix D.4): We report runtime measurements on large-scale OGB datasets to empirically validate the scalability our pipeline.
D.I QUALITATIVE ANALYSIS AND INTERPRETABILITY
Visualizing the Learned Vocabulary. To understand the structural patterns captured by our kenizer, we visualize the vocabulary constructed by BPE's merging process the ZINC dataset. Figure illustrates how BPE iteratively merges simple, frequent substructures into progressively more complex and chemically meaningful tokens.
Each row in the figure demonstrates such a merging sequence. For instance, the top row shows that a basic structure representing a sulfonyl group (O=S=0 the 1t merge iteration) is established as a token. In subsequent merge steps, BPE combines this token with adjacent atoms to form a more complex token (C [SH] (=0) =0) and then
larger one (CC [SH] (=0) =0). This progression directly reflects BPE's mechanism: greedily merging the most frequent adjacent symbol pairs to build vocabulary. Similarly, the bottom row shows the process starting from classic benzene
23

---

Published as a conference paper at ICLR 2026
ring, which is then merged with neighboring carbon chains to form tokens corresponding to toluene and ethylbenzene.
Interpretation of Learned Vocabulary. To understand the structural semantics captured by tokenizer, we analyzed the size distribution of the learned vocabulary on the ZINC dataset with a merge count of K 2000. As detailed in Table 7, the vocabulary not dominated by small atomic tokens. Instead, it exhibits a distinct preference for medium-scale substructures. Specifically, atomic tokens (0-1 nodes) comprise only 7.1% of the vocabulary, while the distribution peaks in the 4-6 node range (41.5%). In the context of molecular graphs. this size range corresponds to typical func- tional groups and ring structures. Combined with the 7-9 node range. over 60% of the vocabulary represents complex, multi-node substructures. This confirms that the BPE merge process, guided by our frequency statisties, successfully identifies an optimal level of abstraction produccing tokens large enough capture meaningful local topology (e.g., cycles, branches) yet frequent enough to ensure generalization across the dataset.
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 preference for sunctional-group--izee substructures.
Token Size
Atomic (0 ~ 1) Small (2~33
Medium (4~6) Large (7 ~ 9) Huge (10-)
Proportion 7.1%
28.5%
41.5 %
20.4%
2.5%
Auto-regressive Graph Generation. A core advantage of framework is that it converts graph data into a format formally identical to natural language, thereby theoretically enabling the use of standard autoregressive (decoder-only) models for graph generation. To empiri- cally validate this capability, we conducted proof-of- of-ncept experiment using the MNIST dataset, treating images as readily visualizable grid graphs
Proof-of-Coneee
Setup. We converted each 28 x 28 MNIST image into a regular grid graph, where pixels correspond to nodes and are connected to their immediate spatial neighbors (up, down, left, right). These grid graphs were then tokenized using our proposed framework Frrquency-Guuiee Serialization + BPE) to produce discrete token sequences. We trained a standard, unmodified decoder-only Transformer (GPT-style architecture) on these sequences using the conventional next-token prediction objective (CCL)).
Results. As illustrated in Figure 4, the model successfully learns to generate coherent graph struc- tures token-by-token. The reconstructed graphs clearly depict recognizable digits, demonstrating that the model effectively captures the global topology and local connectivity patterns solely from the serialized token sequence. This result confirms that our framework effectively bridges the gap between graph generation and standard sequence modeling, opening the door for applying large- scale generative pre-training (e.g., GPT) to graph domains such as molecular design and material discovery.
D.2 PERFORMANCE RESULTS
Classification and Regression Benchmarks. We present the complete results for all datasets eval- uated in our main experiments. The experimental setup and reporting format are identical to those described in the main text. The results for the remaining datasets (which were not included in the main text due to space constraints) are detailed in Table 8.
Comparison with State-of-the-Art Architectures. To strictly validate the effectiveness of our tokenizer, we sigmificantly expanded our comparative evaluation to include a broader range of state- of-the-art architectures. We conducted a comprehensive evaluation against recent Graph Trans- formers (GraphGT, Graphormer), serialization-basse or hybrid methods (FragNet, Graph-ViT- MLPMixer)) and classic baselines (HAN, ChebNet). As detailed in Table 9, our method con- sistently outperforms strong baselines graph classification (MOLHIV, COIL-DEL) and long- range modeling tasks (Peptide-func). Notably, we surpass specialized architectures like FragNet and Graph- Sinh-viT-MM MLPMixrr without requiring their domain-specit regression task, our performance is comparable to standard Graph Transformers (c.g.. Graphormer), while classic architectures (ChebNet, HAN) lag significantly behind. This confirms that general- purpose tokenizer can unlock state-of-the-as performance across diverse graph learning benchmarks using a standard Transformer architecture.
inductive biases. On the ZINC
24

---

Published as a conference paper at ICLR 2026
0
1
2
3
4
5
6
7
8
9
3
6
5
4
7
6
]
C
3
4
5
6
7
8
9
7
I
2
3
4
5
7
8
9
1
7
3
4
7
6
7
8
9
1
2
3
4
5
6
7
8
1
2
3
7
5
6
7
8
9
2
7
4
f
C
7
J
9
2
3
4
L
T
S
9
/
3
S
6
6
/
3
4
6
8
G
Acc: 0.905
BPP: 636
PPL: 1.6
Figure 4: Visualization of autoregressive graph generation on MNIST. The model generates the graph structure token-by-token (left right). The resulting sequences decoded back into grid graphs, forming coherent digit images. This demonstrates the framework's 's capability to support generative tasks using standard decoder-only Transformers.
Comparison with LLM-based Graph Models. We further benchmarked our method against re- cent "Graph Foundation Models" (GFMs) such as GraphGPT and LLAGA. Since these models are fundamentally designed for text-attributed graphs (TAGs), we evaluated them via adaptation (textualizing graph structures), treating discrete node labels as textual tokens satisfy their in- put constraints. The results in Table 10 reveal a critical limitation of the textualization paradigm. These models struggle significantly with pure structural tasks, performing near random guessing datasets like COIL-DEL. This highlights that while L.MSs excel when rich semantic text is avail- able, they lack the native capability reason about complex graph topology solely from linearized text strings. In contrast, our tokenizer specifically captures structural patterns, enabling superior performance on structure-centric tasks.
Sequence length and efficiency. To demonstrate the generalizability of our model's efficiency, present visualizations of token efficiency and training throughput for the remaining datasets, analogous to Figure 2 in the main paper. The results, shown in Figure 5-10, confirm that our approach consistently maintains superior efficiency across diverse range of datasets.
25

---

Published as a conference paper at ICLR 2026
Table Additional classification results on datasets shown in the main table. Best scores are in bold, second-best are underlined. Std in parentheses.
colors3 acef
twitter acct
proteins acef
dd ace?
Model
GCN
66.0 (2.1)
$2.7 (0.3)
73.2 (1.61
62.7 (1.1)
GIN
69.3 (1.)
(0.6
64.3 (4.0)
65.2 (0.9
GAT
76.6
53.6
70.5 (0.1
58.5 (1.0)
GatedGCN
77.1 (1.2)
59.8
71.1 (1.2)
77.2 (0.7)
GraphGPS
(18)
53.0 (0
67.9 (0.6)
76.3 (0.5)
Exphormer
73.9 (1.)
55.1 (0.3)
74.1 (0:91
74.6 (0.6)
GraphMamba
93.6 (09)
(0.7)
70.5 (1.3)
76.8 (0.4)
GCN+
85.8 (23)
61.3 (02)
77.1 (0.9)
79.1 (0.5)
GT+BERT
96.2 (1.)
62.3 (0.3)
75.0 (0.7)
72.0 (0.9)
GT+GTE
100.0 (0.0)
65.7 (0:2)
79.1 (0.6)
79.6 (0.6)
Table 9: Comparison with additional baselines. ** indicates results reproduced using official imple-
mentations; ' denotes results not reported in the original papers. Our method remains competitive against specialized architectures.
Model
ZINC (MAE MOLHIV (AUC
Peptide-func (AP1)
COIL-DEL (ACC ty*
GraphGT
0,226 (0.014)
63.26 (1.26)
(08)
Graphormer
0.132 (0006)
80.51 (0.5)
88.4 (03)
FragNet
0.078 (0:05)
81.32 (0.86
66.8 (0.5)
83.4 (06)
Graph-ViT-MLPPN VIT-MLPMixer
0.073 (0001)
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.01.)
70.1 (0.7)
51.3 (0.8)
71.4 (0.8)
Our Method
0.131 (0.07)
87.4 (0.2)
73.1 (0.2)
89.6 (0.2)
wio BPE
wio BPE
$9.0s
wi BPE
BPE GNN
CompressilfeRaatio
6.10x
6.82x
80
Length
4010
6.10x
Compresse Ratlo
13.18
4.30x
$1.41
3744
20
21.5s
bds
smiks culerian Method
Euterian
GPP
GatedOCN GraphoPS GMamba
Method
(a) Average sequence length comparison.
(b) Average training time per epoch.
Figure 5: Efficiency analysis the QM9 dataset.
D.3 ABLATION STUDIES
To further validate design choices, this section provides detailed ablation studies that comple- ment the analysis in the main paper. We first present the complete ablation results for the GT+GTE model in Table 11 and the GT+BERT model in Table 12 and Table 13. Beyond these general per- formance trends, we conducted systematic studies to validate our specific design choices regarding vocabulary size, frequency guidance units, and serialization strategies for counting tasks.
Impact of Vocabulary Size (K). Our experiments identify
2000 as the optimal saturation point, effectively balancing sequence compression with model learnability. As shown in Table 14, increasing K initially yields significant gains in compression (1.00x to 10.84x). However, this ben- efit plateaus around K 2000. Extending to K 5000 offers diminishing returns in compression (11.34x) but fails to improve MAE (0.132). This stagnation may be driven by the "long-tail" effect: tokens added beyond K 2000 appear too infrequently receive sufficient gradient updates (of-
26

---

Published as a conference paper at ICLR 2026
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.
Model
ZINC (MAE 4)
COIL-DEL (ACC 1)
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)
1880
wio BPE
wfo BPE
16.0
Compression Ratio
7.21x
GNN
80-
1.00x
Epoch Time (6)
5.47x
SAtx
Comp Pampross
1080
31.80
31.b
21.8s
20
67s
bis
togo
aulerian Method
Fauler
topp
DF5
Eulerian
CPP
GaladGCN GraphoPS GMamba
Mathod
(a) Average sequence length comparison.
(b) Average training time per epoch.
Figure 6: Efficiency analysis on the MoIHIV HIV dataset.
Wif
3M
BPE
BPE
1180
Compression
GNN
2.f9x
poohh Time (e)
186x
1.1
1..00
Comprsat
2.%
1.8t
1.66
1:1x
0.9g
0.8c
cpp
1opp
GraphoPS
Method
Methed
(a) Average sequence length comparison.
(b) Average training time epoch.
Figure 7: Efficiency analysis on the dataset.
w/o BPE
25
w/o BPE
34.5u
17280
wi BPE
wi BPE
3.52x
GNN
Length
10:00
3.15a
328x
3.17x
3:1x
Comprass Rallo
20
12200
16
Ats
5.8x
2.58
t0po
stllrian
cpp
fcpp
GeledGONN GraphGPS
(a) Average sequence length comparison.
(b) Average training time per epoch.
Figure Efficiency analysis on the COLORS-2 dataset.
ten appearing fewer than 10 times across the entire dataset), thereby increasing model complexity without contributing to generalization.
27

---

Published as a conference paper at ICLR 2026
10:00
BPE
20.0
18
w/ BIPE
w/ BPB
Sequencc Langtth (KC
Compression
Compresse Rallo
Time
12.5
1.24x
1.04x
1154x
1d4x
Edet
5.0
2,5
2.18
13
dis
Bts
1opo
culerian Method
Teuler
cgp
Popp
DF5
Eulerian
GPP
GaledGGN GraphöPS GMamba
Method
Average sequence length comparison.
(b) Average training time per epoch.
Figure Efficiency analysis on the COIL-DEL dataset.
w/
Wio BPE
29
wio BPE
25.06
Comp Ratio
7.56x
GNN
Langth
6.15x
Comp fos Ratio
4.87%
4.66
2.4
topo
opp
topp
(a) Average sequence length comparison.
(b) Average training time per epoch.
Figure 10: Efficiency analysis on the AQSOL dataset.
Choice of Frequency Guidance Unit. The ablation confirms that Node-Edge-Noot trigrams of- fer the superior trade-off, achieving the highest compression rate (10.84x) while maintaining linear complexity. The results in Table 15 show that simpler units like Node-Node bigrams perform sub- optimally (10.71x) because they discard critical edge label information. Conversely, more complex units (2-hop/3-hog paths) surprisingly reduce compression (10.37x) despite their high computational cost (O(E$ /N2)). This counter-intuitive result may be due to data sparsity. Specifically, as pat- terns grow longer, their exact recurrence becomes exponentially rarer, rendering the frequency map too sparse to provide robust global guidance.
Serialization Strategy and Counting Tasks. While most results are consistent with the main paper, the COLORS-3 dataset presents a notable exception due to its unique task of counting nodes with specific colors. On this dataset, node-based serialization methods like DFS perform best as they visit each node exactly once, making the counting task trivial. contrast, our default edge-traversll method (Eulerian) can visit a single node multiple times, creating ambiguity for direct counting.
To empirically validate this hypothesis, we conducted a controlled experiment on ZINC by simu- lating node counting task (counting carbon atoms). As shown in Table 16, the edge-based serial- ization struggles with this task (21.6% accuracy), whereas switching to node-based DFS traversal immediately resolves the failure (83.4% accuracy). This confirms that the limitation stems specif- ically from the mismatch between the edge-covering serialization strategy and the node-counting objective, rather than inherent deficiency in the tokenizer Transformer architecture. Despite this task-specific dynamic, a crucial finding remains: our guided serialization significantly outper- forms unguided versions general structural tasks, reinforcing the effectiveness of our guidance mechanism.
28

---

Published as a conference paper at ICLR 2026
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. dash ("-") under SMILES indicates that the dataset either lacks SMILES representations or is not a molecular graph.
mutag
colors3 ncet
dblp acc?
eqsol
F-strucc avg mae]
Method
mae]
winn
w/n
Win
Wh
win
BFS
79.2
78.8
73.4
74.4.0)
91.8
91.7
0.701
0.702
0.2495 coum)))
0,2494
DFS
81.9 (0.7)
79.4-1.5
(0.1
100.0 s./b
92.8 (0.09)
92.6 m.11)
0.684 (0003)
0.676 (001
0.2421 (2,025)
0.2468 (0 Doat)
TOPO
80.1
(.44
0.
98.3r13)
93.0 (a.))
92.5 10.35
0.814
0.737 (oom)
0.2626 (0/0th))
0.2556 o1 co0m
Gulerian
86.1
84.3
(1.b
44.7 (2:)
(100)
0,2514 (ouaz7))
0.2499 01,00e)
Feuler
90.1
86.7 (0)))
4.3
45.3 (0:0
93.6 (118)
88.9 o114)
0.621 (3307)
0.623 (5017)
0,2510
(20001)
0.2548 (0.000))
CPP
87.7
85.4
36.9
45.9
90.9
92.1
0.654
0.643
0.2535
0.2482
ECPP
37.7 (94)
86.0 (0.))
37.5 (1.))
45.6 00.0
92.4 (108)
92.3 0L38)
0.654 (2007)
0.633
(0000)
0.2537 (OUMER))
0,2481 01.000
SMILES
0,741
0,673
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 not a molecular graph.
mo molhiv auct
cot 1dl1 ncct
p- func apt
zinc mac
gm3
Method
mael
wio
W/
w/o
Wil
wilo
76.5
76.1 (0.9)
80.1 (1.3)
66.9
63.2 (05)
0.612 (0.09)
0,961 (0.01)
0.227 (0011)
0.324 (0.013)
DFS
74,6 (1.4)
79.5 (..))
80.5
79.8 (0.)
71.3 (03)
67.5 (1.))
0.537 (.ms)
0.976 0.99)
0.275 0.00;
0,281 (0.04)
TOPO
77.9 (0.)
81.4 (.2)
65.3
54.6
(.01))
1.034 (0.02)
0.277 00010
0.266 (0.01))
Eulerian
83.7 m.7)
83.9 (..)
72.1 (08)
69.9 (2.9
67.3 (09)
64.1 (18)
0.304 (.0s)
0.396 0.012)
0.104 o.00)
0.127 (0.07)
mm
81.8 m.5)
(())
76.1 m9)
(1.4
0.241 max))
(1011)
0.122 mo00:
CPP
85.0 (0.3)
82.8 (1.)
72.5
83,3 (.))
65.6
59,5 (1.5)
0.319 (005)
0.464 00.00)
0,115 01004
0,131 (006)
FCPP
83.2 (0.3
82.2 (0.)
68.9 (0.3)
78.3 (1.))
65.5 (1.)
61.0
0,316 (0005)
0,467 (0,00))
0.107 (1005)
0.132 (007)
SMILES
0,273 (104)
0.320 00.07)
0,117 01014)
0,120 mo06)
D.4 SCALABILITY ANALYSIS ON LARGE-SCALE OGB DATASETS
To understand the computational characteristics of our pipeline on large graphs we profile each stage on OGB datasets containing millions of edges (ogbn-arxiv, v, ogbg-code2, and oggb--roouuce s). All measurements use the rrqueeccy-Guided Eulerian circuit for serialization and are performed
single CPU thread, with results normalized to Time per I Million Nodes.
Table 17 reveals a clear separation between the two stages. BPE encoding introduces negligible overhead, completing in tens of milliseconds per million nodes and remaining stable across datasets regardless of graph density. The computational cost of the pipeline thus dominated by the seri- alization stage, whose runtime scales with edge density and serialization method. This decomposi- tion highlights a practical advantage of our modular design: since the tokenization stage (BPE) is lightweight, the overall efficiency can be improved by selecting a serialization method suited the scale and structure of the target graphs.
29

---

Published as a conference paper at ICLR 2026
Table 13: GT+BERT ablation on additional datasets (Appendix). Best scores in bold, second-best underlined, std in parentheses. dash ("-") under SMILES indicates the dataset lacks SMILES or is not molecular graph.
mutag ace
colora3
dblpp
agscl
p-struct
Method
mae.
avg mael.
wib
WM
whb
sile
wib
BFS
76.1
76.4 (0.7)
72.7
67.3
91.9
91.3 0126)
0.851
0.844
0.2477
0.2620
DFS
77.3 79.6
98.3 (3.3
87.5 (44)
92.6 m0:8
92.4 m.13)
0.831 (000))
0.852 (0002)
0.2526 (00036)
0.2550 0.0012)
TOPO
m4.9
71.2.077
60.4-2.5)
66.6 0.2)
92.7 mo::
92.7 mm11)
0.810
0.840 (a0m))
0.2578 (m0011)
0.26448 0.000
Eulerian
37.8
(M
93.1 moz
m:10)
(00m7)
0.2522 (uoo12)
o1z019
Feuler
87.5 m.4)
84.1 0000
38.5 a.0
40.3 mM
93.2 (00::
88.5 uL11)
0,648 (0022)
0.685 (03934)
0.2476 (woosd)
0.2615 0L0048)
83.6
36.5
(0:11)
0.651
0.2547
(000355)
0.2734
RCPP
85.7 m.5)
85.0 (.
37,1 (0/0
44.5 0.0
91.8 m.13)
91.9 0.20
0.670 (M005)
0.695 (9,03)
0.2541
(b:025))
0.2681
(.005))
SMILES
0.746
0.783
Table 14: Impact of BPE merge count (K) compression ratio and model performance (ZINC). K 2000 achieves the best balance; larger vocabularies yield diminishing compression returns and do not improve performance due token rarity.
Merge Count (K)
Compression Ratio
Performance (MAE 4)
(Raw)
1.00x
0.171 (0.01)
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)
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.
Unit
Collect Cost
Compression Ratio
W/O Guidance
0
10.46x
Node-Node Bigram
10.71x
Node-Edge Bigram
0(E)
10.72x
Node-Edge-Node Trigram
O
10.84x
Multi-hop Path (2 hop)
( (N)
10.56x
Multi-hop Path (3 hop)
0(E3/N2
10.37x
Table 16: Performance on simulated node counting tasks (ZINC). Switching from edge-based node-based serialization resolves the counting failure, confirming analysis regarding the COLORS-3 dataset.
Serialization Method
Accuracy (w/ BPE)
Accuracy (w/o BPE)
Edge-based (Feuler) Node-based (DFS)
21.6%
24.8%
83.4 %
88.4 %
Table 17: Efficiency of different components of method large-scale OGB datasets (Normal- ized to Time per Million Nodes).
Dataset
Serialization (ms)
BPE Encoding (ms)
ogbn-arxiv
14,948
57
ogbg-code2
4,108
74
ogbn-products
29,670
56
30


Reviews:
[{"review_id": "E8KWKoTmPY", "reviewer": "Reviewer_eXKx", "summary": "This paper proposed GraphTokenizer, which essentially just tokenizes the graphs s.t. they can be easily consumed by Transformer based models. The method contains two steps, where the authors first use a deterministic and reversible (in opposite to random walks) sterilization method to transfer the graph data into corpus of sequences, and then use BPE to tokenize them. Once the graphs are tokenized, the following becomes natural as in language modeling. The proposed method performed well across many evaluated benchmarks.", "questions": "n/a", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. While the high level idea is not new, the proposed work executed the graph tokenization fairly well, and showcased good performance in the tasks that it can handle.\n2. In the evaluations, the proposed method showed good performances as well as efficiency.", "weaknesses": "The limitations on page 14 are very on point. \n\n1. As limitations 1&2 mentioned, the focus on only graph-level tasks with discrete features significantly constrains the scope of this work. With such constrains, the proposed method almost only makes sense on protein and chemical graphs, where nodes are atoms, etc.\n2. All three limitations kinda showed a theme that this proposed work might not be very suitable for larger graphs such as social networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PEJeKB0VEf", "reviewer": "Reviewer_p82C", "summary": "The paper presents a novel graph tokenization scheme designed to provide graphs with discrete features as input to standard Transformers. The method involves two main steps: \n* First, it employs frequency-guided Eulerian Circuit and Chinese Postman Problem (CPP) approaches to achieve reversible and deterministic serialization of the input graph. \n* Second, it uses Byte Pair Encoding (BPE)—a standard in LLMs—to greedily combine frequently occurring token substrings. \n\nThe authors validate these results by combining their tokenizer with bidirectional BERT and GTE Transformers, comparing their performance against various GNNs and demonstrating the efficacy of BPE in terms of sequence compression.", "questions": "While the paper mentions generative tasks via GPT-style models as an application, it only evaluates on classification/regression using BERT/GTE. Would pairing the tokenization scheme with autoregressive transformers be able to solve similar supervised graph learning tasks as well (given their general-purpose successes in language modeling)?\n\nIt would be interesting to better understand the BPE patterns, lengths, and statistics. Does the learned vocabulary consist mostly of small node/edge tokens, or are there many longer sequence tokens?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The proposed approach is elegant and cleanly integrates graph inputs with established LLM best practices. The combination of BPE with graph walks is clever, well-motivated, and useful for inputting graphs directly into Transformers, effectively sidestepping the need for specialized GNN architectures.\n\nThe experiments appear strong and thorough. They demonstrate compelling compression rates from BPE and show that the method beats a variety of GNN models, although I note that I lack full context for this specific research area.\n\nThe authors are direct about the limitations of their work, specifically regarding continuous features and graph-level tasks, and they suggest reasonable future steps.", "weaknesses": "Regarding reversibility: Output sequences consist only of standard labels (Eq. 1), not unique node identifiers. In graphs with many identically labeled nodes (e.g., large carbon lattices), how does the decoder $f^{-1}$ explicitly distinguish between returning to a previously visited node versus arriving at a new node with the same label? Is reversibility guaranteed for all labeled graphs without positional markers? For one particular example, what structure can be accurately recovered from the molecular path in Figure 1?\n\nThe serialization example in Figure 1 is confusing. The numbering is difficult to follow (especially as it does not appear to start with 1 as the first edge), and it is unclear why the right-most 'C' appears after 'Br' and 'Cl' in the sequence, given the labeling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aRlRYGlPF4", "reviewer": "Reviewer_Qc9K", "summary": "This paper proposes a graph tokenization framework that converts graphs into discrete token sequences by combining reversible graph serialization (frequency-guided Eulerian circuits or Chinese Postman Problem) with Byte Pair Encoding (BPE). The tokenized sequences aim to enable standard off-the-shelf Transformers (BERT, GTE) to process graph-structured data.", "questions": "See weakness", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Approach: The idea of combining reversible graph serialization with BPE, with formal analysis showing why existing methods fail to satisfy both reversibility and determinism is interesting.\n\nEmpirical Performance: The method achieves state-of-the-art results on 12 out of 13 benchmarks and it also demonstrated that properly tokenized graphs enable standard Transformers to outperform specialized graph architectures without any modifications.\n\nEfficiency Gains: BPE compression achieves 6-10× reduction in sequence length with 2-3× training speedup on Figure 2.\n\nInterpretability: The learned vocabulary on Figure 3 shows that BPE discovers chemically meaningful substructures like benzene rings and functional groups, it seems it provides interpretable tokens aligned with domain knowledge.", "weaknesses": "Scope: The paper only evaluates graph-level classification and regression tasks. Despite claiming to \"bridge graphs and transformers,\" node-level and edge-level prediction tasks are entirely absent from evaluation. The authors acknowledge this limitation (Appendix A.1) but provide no experimental validation of their proposed solutions. This significantly undermines the claim of providing a general framework for graph learning. \n\nContinuous Feature Problem: The framework fundamentally requires discrete labels (mostly just on chemical domain), making it incompatible with graphs that have continuous node/edge features without lossy quantization. This is a critical limitation since many real-world graphs (social networks, knowledge graphs, citation networks) have rich continuous attributes. The authors acknowledge this conflicts with their \"faithful and reversible representation\" principle but offer only speculative solutions without validation.\n\nScalability: While the paper discusses O(|E|) complexity for Feuler serialization, there's no evaluation on truly large-scale graphs. The largest graphs tested have ~284 nodes on average (DD dataset). No experiments on OGB-scale datasets (millions of nodes/edges) or analysis of how the method scales. The Transformer's fixed context window limitation is mentioned but not empirically investigated.\n\nInsufficient Baselines: The baseline comparison omits several recent and relevant methods: (1) recent graph transformers like GraphGT, Graphormer, and NAGphormer are not compared; (2) other recent serialization-based methods beyond GraphMamba such as GPatcher; (3) graph LLM models like G-Retriever or InstructGLM that also aim to connect graphs with language models. The claimed state-of-the-art status is therefore difficult to fully verify.  The paper incorrectly positions GCN (Kipf, 2016) as the GNN foundation, overlooking earlier spectral GNN methods and the rich history of graph neural networks. Important categories like heterophilic GNNs are completely absent despite being highly relevant for understanding when message passing succeeds or fails, this is a critical consideration for evaluating serialization-based alternatives (not to mention some graph partition based methods like Graph-ViT-MLPMixer).\n\nLimited Ablation Studies: Several design choices lack thorough ablation: (1) the number of BPE merges K (fixed at 2000) has no sensitivity analysis; (2) the frequency guidance mechanism's individual components are not ablated; (3) why edge-level patterns (triplets) specifically, rather than larger motifs? (4) The comparison with G2T-FM methods (mentioned in related work) is absent from experiments despite being highly relevant.\n\nNo Analysis of Failure Cases: The method performs poorly on COLORS-3 (Table 8) where node-counting is required, this exposes fundamental limitations of edge-traversal approaches. However, there's no systematic analysis of when and why the method fails. The paper would benefit from characterizing graph properties (size, density, label distribution) that predict success or failure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "11atEuVnJO", "reviewer": "Reviewer_y33R", "summary": "This paper introduces a new graph tokenization framework that transforms graphs into discrete sequences through reversible traversal and BPE techniques. The proposed approach effectively preserves structural information, allowing standard Transformer models to process graph data and achieve competitive performance when compared to state-of-the-art graph-based models.", "questions": "1. Could the authors provide more details on how each token in the vocabulary is embedded in the model?\n2. In previous work, such as PS-VAE [5], a graph-structured tokenization method similar to BPE that merges subgraphs is used. Could the authors clarify how the proposed approach differs from PS-VAE?\n3. For graph-structured datasets, could the authors discuss the impact of subgraph vocabulary size on model training and experimental performance?\n\n[5]. Molecule Generation by Principal Subgraph Mining and Assembling, NeurIPS 2022.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a graph tokenization method that allows standard Transformers to process graph data without altering the model architecture.\n2. The proposed frequency-guided serialization strategy establishes a bidirectional mapping between graphs and sequences, ensuring the reversibility and determinism.\n3. The paper conducts the experiments on 12 benchmark datasets and mostly outperforms both graph neural networks and graph transformers.", "weaknesses": "1. A key strength of this approach is its proposed reversible graph tokenization method. However, the experiments predominantly emphasize the encoding aspect, with limited exploration of its reversibility.\n2. Lacking the discussion or comparison with strong baselines and relevant works. Several existing graph serialization studies, such as those based on chemical rules [1], ring/functional group approaches [2], and models towards the order of token-sequence [3-4]. A detailed comparison and discussion of the advantages of the proposed method would significantly strengthen the paper’s contribution.\n3. Inadequate justification and analysis of the subgraph frequency heuristic.\n\n[1]. Advancing Molecular Graph-Text Pre-training via Fine-grained Alignment, KDD 2025.\n[2]. Expressivity and Generalization: Fragment-Biases for Molecular GNNs, ICML 2024.\n[3]. A Graph is Worth K Words: Euclideanizing Graph using Pure Transformer, ICML 2024.\n[4]. GraphGPT: Graph Learning with generative Pre-trained Transformers, arXiv:2401.00529.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)