Graph Tokenization for Bridging Graphs and Transformers¶

会议: ICLR 2026
arXiv: 2603.11099
代码: 有（补充材料中提供）
领域: 自监督学习 / 图表示学习
关键词: graph tokenization, BPE, graph serialization, Transformer, graph classification

一句话总结¶

提出 GraphTokenizer 框架，将图通过可逆的频率引导序列化转换为符号序列，再用 BPE 学习图子结构词汇表，使标准 Transformer（如 BERT/GTE）无需任何架构修改即可直接处理图数据，在 14 个 benchmark 上达到 SOTA。

研究背景与动机¶

领域现状：图结构数据的学习主要依赖 GNN（通过消息传递聚合邻居信息）或专门设计的 Graph Transformer（引入注意力机制处理图）。另一条路线是将图转换为连续嵌入供 Transformer 使用。
现有痛点：(a) Graph Transformer 需要图特定的架构设计，无法直接复用 LLM 生态的预训练模型和训练技巧；(b) 将图映射到连续嵌入往往存在信息损失或表征不稳定问题；(c) 已有的图序列化方法（Random Walk, BFS/DFS）要么不可逆（丢失边连接信息），要么不确定性（同构图产生不同序列）。
核心矛盾：文本天然是路径图，有固定的邻域结构和顺序——tokenization 很简单。但通用图的邻域可以向多个方向分支、没有唯一的节点排序、n-gram 等共现统计无法直接应用。
本文要解决什么？ 设计一个通用的图 tokenizer，将任意带标签的图忠实地转换为离散 token 序列，使标准序列模型可以直接处理图数据。
切入角度：将图 tokenization 分解为两步——(1) 可逆且确定性的图序列化，(2) 用 BPE 从序列化语料中学习子结构词汇表。关键洞察是：通过全局频率统计引导序列化，使常见子结构在序列中相邻出现，正好适合 BPE 的贪心合并策略。
核心idea一句话：频率引导的可逆图序列化 + BPE = 图的 tokenizer，将图学习重构为序列建模问题。

方法详解¶

整体框架¶

GraphTokenizer \(\Phi = T \circ f\)：输入带标签图 \(\mathcal{G}\) → 频率引导的可逆序列化 \(f_g(\mathcal{G}, F)\) 产生符号序列 → BPE tokenizer \(T\) 将符号序列压缩为 token 序列 \(S_T\) → 送入标准 Transformer（BERT/GTE）进行下游任务。解码时反向操作 \(f^{-1} \circ T^{-1}\) 可完全重建原图。

关键设计¶

局部结构模式统计:
做什么：从训练集统计所有局部边模式 \(p = (l_u, l_e, l_v)\) 的频率 \(F(p)\)
核心思路：边模式是最小的保留两个实体间类型关系的子结构，计算高效且在节点排列下不变。频率图 \(F\) 作为全局统计信息引导后续序列化
设计动机：为序列化提供确定性的优先级，同时确保高频子结构在序列中相邻——为 BPE 创造理想输入
频率引导的可逆序列化（Frequency-Guided Eulerian Circuit）:
做什么：沿欧拉回路遍历图的每条边恰好一次，按频率优先级选择下一条边
核心思路：将无向边拆为两条有向边使任意连通图可做欧拉回路。在每个节点 \(u\)，对未访问的出边 \(\mathcal{E}_u\)，选择 \(e^* = \arg\max_{e_i \in \mathcal{E}_u} \pi(e_i, F)\)，优先级 \(\pi(e_i, F) = F(p_i)\)。遍历时输出 node-edge-node 交替序列，保证可逆性
设计动机：(a) 欧拉回路天然可逆（每条边都被访问）；(b) 频率引导解决了经典 Hierholzer 算法的不确定性问题，使同构图产生相同序列；(c) 时间复杂度仅 \(O(|\mathcal{E}|)\)
与之前方法的区别：Random Walk 不可逆、BFS/DFS 丢失边信息、SMILES 仅适用于分子图
BPE 词汇学习:
做什么：在序列化语料上训练 BPE，迭代合并最高频的相邻符号对为新 token
核心思路：由于序列化已将高频子结构排列为相邻符号，BPE 的贪心合并策略恰好发现有意义的图子结构 token。每个合并 token 对应一个可解码的子图片段
设计动机：(a) 压缩序列长度（约 10× 压缩比），降低 Transformer 的计算开销；(b) 学到的词汇是层次化的、有语义的（如分子中的官能团）；(c) 完全数据驱动，无需领域知识
频率引导的 CPP（Chinese Postman Problem）:
做什么：替代方案——用最小权重遍历覆盖所有边
核心思路：将频率信息编码到边权 \(w(e) = \alpha \cdot 1 + (1-\alpha) \cdot g(F(p_e))\)，使高频边更容易被连续访问
设计动机：CPP 本身已产出高度结构化序列，频率引导的进一步提升有限。但 CPP 复杂度 \(O(|\mathcal{V}|^3)\) 远高于 Feuler 的 \(O(|\mathcal{E}|)\)

损失函数 / 训练策略¶

Tokenizer 本身无需梯度训练（BPE 是统计算法）。下游使用标准 Transformer 训练： - GT+BERT: BERT-small 架构，prepend [CLS] token - GT+GTE: 更大的 GTE 模型（约 BERT-base 参数量） - 标准分类/回归损失

实验关键数据¶

主实验¶

模型	molhiv (AUC↑)	p-func (AP↑)	mutag (Acc↑)	zinc (MAE↓)	qm9 (MAE↓)
GCN	74.0	53.2	79.7	0.399	0.134
GIN	76.1	61.4	80.4	0.379	0.176
GraphGPS	78.5	53.5	84.3	0.310	0.084
GraphMamba	81.2	67.7	85.0	0.209	0.083
GCN+	80.1	72.6	88.7	0.116	0.077
GT+BERT	82.6	68.5	87.5	0.241	0.122
GT+GTE	87.4	73.1	90.1	0.131	0.071

GT+GTE 在 14 个 benchmark 中多数达到 SOTA，且使用标准 off-the-shelf Transformer 无任何图特定架构修改。

消融实验¶

序列化方法	molhiv (w/ BPE)	molhiv (w/o BPE)	zinc (w/ BPE)	zinc (w/o BPE)
BFS	72.3	81.2	0.453	0.696
DFS	76.0	79.1	0.446	0.705
Eulerian	84.5	81.0	0.164	0.160
Feuler	87.4	81.3	0.131	0.171
CPP	86.9	81.2	0.141	0.145

关键发现¶

可逆序列化至关重要：边遍历方法（Eulerian/CPP）显著优于节点遍历方法（BFS/DFS/TOPO），因为保留了完整的边连接信息
频率引导有效：Feuler 稳定优于无引导的 Eulerian，且方差更小
BPE 是关键组件：几乎在所有配置下提升性能，同时带来约 10× 序列压缩和 2.5× 训练加速
模型可扩展：从 GT+BERT 扩展到 GT+GTE 带来一致性能提升，不像 GNN 容易因过平滑而退化
BPE 学到的词汇有化学语义：token 大小分布峰值在 4-6 节点（对应官能团），原子级 token 仅占 7.1%

亮点与洞察¶

图学习的范式转换：将图学习彻底重构为序列建模问题，解耦了数据表示和模型架构。这意味着图领域可以直接受益于 LLM 生态的所有进展（更长上下文、更高效注意力、预训练模型等）
频率引导序列化与 BPE 的协同设计：两者不是简单串联，而是精心设计的协同——序列化为 BPE 创造理想的压缩输入，BPE 反过来发现有意义的子结构。这种 co-design 思想可迁移到其他非序列数据的 tokenization
可逆性作为质量保证：序列化的可逆性不仅是理论优点，直接关联到更好的下游性能——信息无损是高质量 tokenization 的基础

局限性 / 可改进方向¶

仅验证了图级任务（分类/回归），未验证节点级和边级预测任务
序列化依赖连通图假设，非连通图需分别序列化后拼接
频率统计基于最简单的边模式 \((l_u, l_e, l_v)\)，未探索更大子结构模式的统计引导
BPE 是贪心算法，可能无法找到全局最优的子结构分解
未探索预训练+微调范式——如果在大规模图数据上预训练 tokenizer+Transformer，效果可能进一步提升

评分¶

新颖性: ⭐⭐⭐⭐⭐ 将 NLP tokenization 范式完整移植到图领域，理念新颖且执行完整
实验充分度: ⭐⭐⭐⭐⭐ 14 个 benchmark、全面的消融、效率分析、可视化
写作质量: ⭐⭐⭐⭐⭐ 问题定义清晰，理论框架严谨，图表设计精美
价值: ⭐⭐⭐⭐⭐ 可能改变图学习的研究范式，使标准 Transformer 直接可用于图数据