💻 computer science

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

本文通过确立谱表示、随机游走表示和邻接表示之间诸如信息损失与病态性等不同理论权衡，证明了图标记化的选择从根本上决定了 Transformer 的表达能力和深度需求，同时证明了对于有限深度的模型而言，在这些不相容的视图之间进行转换往往是不可能的。

原作者： Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

发布于 2026-05-22

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Maya Bechler-Speicher, Gilad Yehudai, Gil Harari, Clayton Sanford, Amir Globerson, Joan Bruna

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在教一个超级聪明的机器人（一个Transformer）如何理解一座城市。这座城市是一个图：一张连接着建筑物（节点）的街道（边）地图。

机器人无法直接查看地图；它需要将地图翻译成它能理解的语言：一个标记（tokens）列表（就像句子中的单词）。这个翻译过程被称为标记化（Tokenization）。

本文认为，你如何翻译地图，与机器人本身的“大脑”同样重要。取决于你选择哪种翻译方法，机器人可能瞬间解决问题，也可能需要思考很长时间（增加许多层深度）才能弄明白。在某些情况下，无论机器人多么聪明或层数多深，它都无法解决问题，因为翻译过程丢弃了关键信息。

作者测试了三种具体的城市地图翻译方法：

1. “逐条街道”列表（邻接标记化）

类比：想象你给机器人一份列表，对于每一座建筑物，你精确写下哪些其他建筑物与它直接相连。“建筑物 A 与 B、C 和 D 相连。”
好消息：这对局部任务非常棒。如果你问：“建筑物 A 是否与建筑物 B 相连？”机器人能立即看到答案。这就像站在街角；你确切知道你的邻居是谁。
坏消息：如果你问：“整个城市是连通的吗？”（你能否在不迷路的情况下从城市北侧走到南侧？），机器人必须进行大量的心算。它必须从一个邻居跳到另一个邻居，一步步地，才能追踪出横跨整个城市的路径。本文证明，对于大型城市，这种方法迫使机器人必须非常“深”（思考许多层）才能解决全局问题。

2. “城市蓝图”（谱标记化）

类比：与其列出邻居，不如给机器人一份描述城市整体形状的数学“蓝图”。这份蓝图描述了城市的整体几何结构，比如它的振动或频率。它捕捉了城市构建方式的“大局”。
好消息：机器人可以立即看到整个城市是否连通，或者理解其整体形状。这就像看卫星照片；你一眼就能看清整体布局。
坏消息：这种方法对局部细节来说糟糕透顶。如果你问：“建筑物 A 和 B 之间是否有某条特定的街道？”机器人会感到吃力。当试图放大查看微小细节时，数学计算会变得混乱且不稳定（病态）。这就像试图通过眯眼看模糊的卫星照片来阅读单个单词。此外，如果你为了节省空间而截断蓝图的一部分，你可能会意外抹去计数特定形状（如街道三角形）的能力。

3. “游客漫步”（随机游走标记化）

类比：想象一名游客从一座建筑物出发并随机漫步。你给机器人一份报告，说明游客在 1 步、2 步、3 步等之后返回起始建筑物的可能性有多大。
好消息：这对发现环路非常神奇。如果你问：“你能走一个圆圈并回到起点吗？”机器人能立即看到答案，因为报告字面上列出了返回概率。
坏消息：这种方法是有损的。它丢弃了信息。本文证明，两种完全不同的城市布局（一种可以在平面地图上绘制，另一种则不能）可能产生完全相同的游客报告。无论机器人多么聪明，它都无法区分这两座城市，因为翻译抹去了关键细节。这就像仅通过鞋码来识别一个人；许多不同的人拥有相同的鞋码。

主要结论

1. 你无法仅仅“修复”糟糕的翻译
你可能会想：“如果我给机器人‘逐条街道’列表，它难道不能学会在‘大脑’内部将其转换为‘城市蓝图’吗？”
本文说不行。如果机器人的规模（深度）受限，它就无法将一种翻译风格转换为另一种。如果你从“游客漫步”报告开始，无论机器人思考多久，它永远无法恢复完整地图。信息永远消失了。

2. 不同的工作需要不同的地图

需要找到特定的邻居？使用逐条街道列表。
需要理解整个城市的形状？使用城市蓝图。
需要发现环路？使用游客漫步。
试图用一张地图解决所有问题，会使机器人效率低下或无法解决问题。

3. “最佳”解决方案是混合使用
在实验中，作者发现，当他们同时给机器人所有三种翻译时，它的表现最好。它可以利用“街道”列表处理局部细节，利用“蓝图”处理整体形状，结合每种视角的优势。

总结

本文得出结论：标记化不仅仅是一个枯燥的初步步骤；它是机器人智能的根本组成部分。选择错误的翻译方法会创建一个“瓶颈”，无论增加多少额外的计算能力，都难以轻易修复。要构建最好的图学习人工智能，你必须选择与你所提出的具体问题相匹配的翻译方法。

技术摘要：迷失在分词中：图分词用于 Transformer 的根本权衡

问题陈述

Transformer 已成为图学习中强大的架构，然而将其应用于图结构数据需要一个初步步骤：分词（tokenization）。与序列或网格不同，图缺乏规范化的连续输入格式。因此，必须选择一个从图到分词的映射，以决定在输入层向模型暴露哪些结构信息。

尽管存在各种分词策略（例如谱分词、随机游走分词、邻接分词），它们通常被视为经验性的设计选择或预处理细节。本文提出，分词的选择是Transformer 表达能力的一个根本组成部分。本文解决的核心问题是：不同的分词是否可互换，或者它们是否会导致截然不同的计算机制，特别是在解决图任务所需的深度以及恢复结构信息的能力方面。

方法论

作者将图分词形式化为计算模型的一个组成部分，分析了在有限深度（ $L$ ）、宽度（ $m$ ）和精度（ $p$ ）下，基于三种主要分词族（families）的 Transformer 的表达能力：

邻接分词（Adjacency Tokenization）： 通过每个节点的邻接行编码其局部连通性。它是无损的，但仅暴露局部结构。
谱（拉普拉斯）分词（Spectral (Laplacian) Tokenization）： 从图拉普拉斯矩阵（ $L = D - A$ ）的特征分解中导出分词。它捕捉全局拓扑属性，但具有置换等变性（permutation-equivariant）。
随机游走分词（Random-Walk Tokenization）： 编码长度为 $1 $到$ t(n)$ 的随机游走的返回概率。它捕捉扩散模式，但本质上是有损的（lossy）。

该方法论结合了复杂性理论分析与受控实验。

理论分析： 作者通过将图任务映射到复杂性类（例如 $TC^0$ 、 $NC^1$ 、 $L$ ）来建立下界和不可能性结果。他们分析了特定任务（例如 $k$ -闭游走检测、连通性、三角形计数、平面性）在不同分词下的表现，同时考虑有限深度的约束以及分词表示的数学属性（例如条件数、信息损失）。
实证验证： 实验在合成任务（验证深度分离性）和真实世界基准测试（GraphBench、Open Graph Benchmark、ZINC）上进行。该研究评估了使用每种分词的完整版本和截断版本的 Transformer，以及组合分词，并将其性能与 DeepSet 和 GIN 基线进行比较。

主要贡献

1. 将分词形式化为计算约束

本文形式化了输入表示如何在有限深度下约束 Transformer 的表达能力。它证明分词不仅仅是一个特征工程步骤，而是决定了模型可访问哪些结构依赖关系。

2. 分词之间的深度分离

作者证明，相同的图计算可能因分词的不同而需要截然不同的深度：

随机游走 vs. 邻接： 检测 $k$ -闭游走在随机游走分词下可在 $O(1)$ 深度内解决（因为统计量是显式的），但在邻接分词下需要 $\Omega(\log k)$ 的深度。这是通过将置换群 $S_5$ 上的字问题（一个 $NC^1$ -完全问题）归约到图拓扑来证明的，表明常数深度的 Transformer（ $TC^0$ ）无法模拟邻接分词所需的顺序路径遍历。
邻接 vs. 谱： 解决全局图连通性在邻接分词下需要 $\Omega(\log n)$ 的深度，而谱分词可在 $O(1)$ 深度内解决。

3. 内在局限性与有损性

随机游走被证明是有损的： 无论游走长度如何，随机游走分词都无法确定图的平面性。作者利用 Godsil-McKay (GM) 切换构造了具有相同随机游走分布的平面和非平面图，证明没有任何 Transformer 的深度或宽度能够恢复这种拓扑区别。
谱截断是脆弱的： 截断拉普拉斯谱（即使仅截断一个特征值）也可能使三角形计数变得不可能。作者表明，在对称节点之间添加一条边只会改变一个特征值；如果该特征值被截断，Transformer 就无法区分这些图。
邻接截断： 截断邻接分词的维度（通过随机投影）会破坏解决三角形计数等任务的能力，这是通过通信复杂性下界（集合不相交问题 Set Disjointness）证明的。

4. 谱分词对局部任务的条件数恶化

虽然谱分词捕捉全局拓扑，但它在边缘预测等局部任务上在数学上是病态的（ill-conditioned）。本文推导出了一个下界，表明从全局谱中解码局部边缘所需的参数范数随最大度（ $d_{max}$ ）缩放。这迫使进行权衡：要么模型遭受 Softmax 饱和（梯度消失），要么需要爆炸性的权重，使得优化变得困难。

5. 有限深度下转换的不可能性

本文确立，在有限深度下，在不同分词族之间进行转换通常是不可行的。

Transformer 无法高效地将邻接分词转换为随机游走统计量（需要 $\Omega(\log k)$ 的深度）。
Transformer 无法从随机游走分词中恢复完整的邻接或拉普拉斯表示（由于信息损失）。
在全局（谱）和局部（邻接）视图之间转换会产生严重的计算瓶颈或优化不稳定性。

结果

理论发现：

深度分离： 实证验证确认，谱分词在所有图大小下均能以 $L=1$ 解决连通性任务，而邻接分词在较大图（ $n \ge 128$ ）上退化为随机猜测性能。
恢复限制： 当训练 Transformer 从邻接分词预测随机游走返回概率时，误差随游走长度 $k$ 增长，这与 $\Omega(\log k)$ 的深度要求一致。
平面性： 使用随机游走分词的模型无法区分平面和非平面图，即使增加深度也是如此，这证实了理论上的不可能性结果。

实证发现：

任务依赖性： 没有一种分词占主导地位。
- 局部任务： 邻接分词在受显式局部约束支配的任务（例如最大团、拓扑排序）上表现最佳。
- 全局任务： 谱（拉普拉斯）分词在依赖全局几何的任务（例如 Tox21 分子属性预测）上表现最佳。
- 组合方法： 组合互补的分词（邻接 + 谱 + 随机游走）通常能产生最佳性能，使模型能够利用不同的结构信号。
截断效应： 截断的分词通常会降低性能，特别是对于需要精确结构恢复的任务（例如三角形计数），这验证了截断的理论“脆弱性”。

意义与主张

本文主张，图分词是一个根本性的权衡，而非预处理细节。分词的选择决定了 Transformer 接收到的图的“视图”，从而限制了模型在有限深度下可表达的结构依赖关系的类别。

作者强调的关键要点包括：

不可互换性： 邻接、谱和随机游走分词是不可互换的；它们会导致截然不同的深度机制和表达能力限制。
内在局限性： 特定的分词具有可证明的盲点（例如，随机游走无法看到平面性；谱分词对局部边缘是病态的）。
转换障碍： 如果初始分词不利，Transformer 无法简单地“学习”高效地转换这些表示；弥合这些差距所需的深度可能是不可行的。
实际意义： 最佳分词取决于下游任务的结构性质。组合互补视图是克服任何单一表示局限性的稳健策略。

作者总结道，虽然他们的分析侧重于节点级分词，但研究结果表明了一个更广泛的原则：输入表示是图学习中复杂性的关键维度，未来的工作应探索优化挑战以及边级分词。