Transformer 能否替代图神经网络？深度解析与对比
当 Transformer 模型发布时，它彻底革新了机器翻译领域。虽然最初是为特定任务设计的，但这种革命性的架构显示出它可以轻松适应不同的任务。随后成为了 Transformer 的一个标准，甚至用于它最初设计之外的数据（如图像和其他序列数据）。
随着研究的深入，人们开始优化和寻找替代方案，主要是为了减少计算成本（自注意力机制的二次方成本）。关于哪种架构在计算成本方面更优的讨论一直在进行，但是对于 Transformer 来说，它的成功之处在于模型能够展示出强大的推理能力。
如何分析神经网络的推理能力？
最常用的方法之一是研究利用架构内部表示能执行哪些算法。有一个完整的领域致力于这项任务：Neural Algorithmic Reasoning（神经算法推理）。Transformer 是否能进行泛化，或者通过扩展是否能解决一些问题，这些问题仍然悬而未决，并且这方面的研究也十分活跃。
有些人认为 Transformer 具有普适推理能力，而其他人认为它是引领我们走向人工通用智能的架构（假设我们能够足够扩展它）。但是目前看 Transformer 能够在不同的领域，NLP、时间序列，甚至 CV 中取得良好的成绩，测试其极限也非常重要。我们不仅需要测试它的极限，还需要与其他架构进行比较，并在未来建立基准。
在最近的一项研究中，研究人员决定深入研究一个特定的领域：图神经网络（GNN）。
今天介绍的这篇论文叫'Understanding Transformer Reasoning Capabilities via Graph Algorithms'。
这可能听起来有些奇怪，但近来 Transformer（以及大型语言模型）与图（Graphs）之间的关系越来越密切。首先，自注意力可以被视为一种图的形式。其次，图（尤其是知识图谱）可以用来扩展 Transformer。第三，图是复杂推理的理想抽象。思维链条（Chain of Thought）和其他技术也可以被视为图的一种抽象。另外许多图问题可以通过简单的架构解决，而其他问题则需要复杂的推理和先进的图神经网络（GNNs）。
图计算已经成为过去几十年计算和人工智能中几个成功设计的基础之一，例如用于蛋白质预测的 AlphaFold。许多推理任务可以表达为关于图的推理（这就是为什么像 Tree of Thoughts 或 Graph of Thoughts 这样的技术显示出成功）。所以这似乎是测试 Transformer 能力的最佳选择。
尽管有不同的理论前提，但是进行严格分析并不容易：
图推理任务可以被归类到已知的计算类别中。但是当我们想要评估一个神经网络解决这些任务的能力时，情况就不同了。在 Transformer 的情况下，我们也感兴趣的不仅仅是固定深度的情况，还有通过改变层数从而学习更简单或更复杂的表征时的变化。并且 Transformer 也可以在宽度上增长，这在考虑到对上下文长度的重新关注时尤其相关。
作者总结了三类任务，它们的难度逐步增加，只能通过越来越复杂的模型来解决：
- 检索任务。节点计数、边计数、边存在检查和节点度数是只需要一次查找的任务，因此只需要一个 Transformer 层和一个小型嵌入。
- 可并行化任务。连通性、连接节点和循环检查（以及更复杂的任务如二分性和平面性）可以用对数深度的 Transformer 解决。
- 搜索任务。最短路径和其他需要更多推理的任务需要模型的扩展。
论文中进行了几项理论分析，展示了 Transformer 如何解决这些任务以及解决这些任务所需的维度要求。另一个有趣的点是，作者还分析了'pause tokens'的影响，这有助于模型在推理过程中暂停并处理中间状态。
