引言

Graph Transformer已成为ML的重要架构，它将基于序列的Transformer应用于图结构数据。然而当面对大型图数据集时，使用Graph Transformer会存在扩展性限制。为此，「Google提出了一个稀疏注意力框架Exphormer，它使用扩展图来提高图Transformer的可扩展性，并在长期依赖关系表现出了强大的性能」。

论文：https://arxiv.org/pdf/2303.06147.pdf

背景介绍

图在计算和机器学习 (ML) 中无处不在，其中对象及其关系可以用图中的节点和节点之间的边来表示。社交网络、道路网络以及分子结构之间的相互作用都都具有类似图结构。通过机器学习可学习图的节点、边亦或者整个图的属性。

图学习的一种常见方法是图神经网络（GNN），它通过对节点、边和全局属性信息进行相应的转换来实现对图数据的操作。典型的图神经网络（GNN）是通过消息传递框架进行数据操作，其中每一层都将节点的表示与其直接相邻的表示聚合在一起。

最近，图Transformer已成为了消息传递架构的替代方案。这些模型建立在Transformer成功的基础之上，使其可以适应图结构数据。图Transformer中的注意力机制可以通过交互图来建模，其中边代表相互关联的节点对。与消息传递架构不同，图Transformer具有与输入图分离的交互图。

典型的交互图是一个完整的图，它表示一个完整的注意力机制，可以对所有节点对之间的交互进行建模。然而，这会产生二次计算和内存瓶颈，限制了图Transformer在具有数千个节点的小图上的适用性。使图Transformer具备可扩展性，已被认为是该领域最重要的研究方向之一。

面对二次计算和内存瓶颈，一种方法是使用边数较少的稀疏交互图。当前已经提出了许多稀疏且高效的Transformer来消除序列的二次瓶颈，但是，它们通常不会将其扩展应用到图神经网络。

基于以上背景，在ICML2023上，Google提出了“Exphormer: Sparse Transformers for Graphs”中，通过引入专为图数据设计的Transformers 的稀疏注意力框架来解决可扩展性问题，Exphormer框架在各种数据集上获得优异的结果。

Exphormer

「Exphormer核心思想是使用扩展图」，它们是稀疏但连接良好的图，如下图所示。

并且具有以下属性：

• 1）图的矩阵表示具有与完整图类似的线性代数属性；

• 2 ）它们表现出快速混合的随机游走，即从任何起始节点开始的随机游总走中的少量步骤足以确保收敛至图节点上的“稳定”分布。

当前 Exphormer 已应用于不同领域，例如算法、伪随机性、复杂理论和代码纠错。

一类常见的扩展图是扩展图，其中每个节点都有d条边（即每个节点的度数为d）。扩展图的好坏通过谱间隙来衡量的，谱间隙是其相邻矩阵的代数属性。那些最大化谱间隙的图被称为Ramanujan图——它们实现了的间隙，这本质上是正则图中最好的。多年来，针对不同的  值，提出了一系列的Ramanujan图构造。本文使用Friedman随机扩展结构，它可以近似产生Ramanujan图。

构建稀疏交互图

Exphormer 将扩输入图的扩展器边缘和虚拟节点结合起来。具体来说，Exphormer 的稀疏注意力机制构建了一个由三种类型的边组成的交互图，如下图所示：

• 输入图的边（局部注意力）

• constant-degree扩展图的边（扩展注意力）

• 从每个节点到一小组虚拟节点的边（全局注意力）

其中，每个组件都有特定的用途：输入图的边保留输入图结构的归纳偏差；扩展边允许良好的全局连接性和随机游走混合特性；虚拟节点充当全局“内存接收器”，可以直接与每个节点通信。虽然这会导致每个虚拟节点的附加边等于输入图中的节点数，但生成的图仍然是稀疏的。扩展图的degree和虚拟节点的数量是用于调整以提高质量指标的超参数。

此外，由于使用constant-degree扩展图和少量恒定数量的虚拟节点来进行全局注意力，因此所得的稀疏注意力机制与原始输入图的大小呈线性关系，即它模拟了许多直接交互节点和边总数的顺序。

此外，Exphormer 与密集Transformer一样具有表现力，并且遵循常用的近似属性。特别是，当 Exphormer 的稀疏注意力图通过自环（将节点连接到自身的边）进行增强时，它可以普遍逼近连续函数。

与稀疏Transformer的关系

将 Exphormer 与稀疏注意力方法进行比较是很有趣的。也许在概念上与我们的方法最相似的架构是 BigBird，它通过组合不同的组件来构建交互图。BigBird 也使用虚拟节点，但与 Exphormer 不同的是，它对其余组件使用来自 Erdős-Rényi 随机图模型的窗口注意力和随机注意力。

BigBird 中的窗口注意力着眼于序列中标记周围的标记，而Exphormer 中的局部邻域注意力可以被视为窗口注意力对图的概括。

n 个节点的 Erdős-Rényi 图 G(n, p) ，以概率 p 连接每对节点，也可用作高度为p的扩展图。然而，需要超线性边数来确保 Erdős-Rényi 图是连通的，更不用说良好的扩展器了。另一方面，Exphormer 中使用的扩展器仅具有线性数量的边。

实验结果

为了评估 Exphormer 的性能，本文以GraphGPS 框架为基础，该框架结合了消息传递和图Transformer，并在许多数据集上实现了最先进的性能。实验结果如下图所示：

可以发现，用 Exphormer替代GraphGPS 框架中的密集注意力可以实现具有可比或更好性能，并且具有更少的训练参数。

此外，Exphormer 能够让图Transformer架构的扩展超出常规大小限制。Exphormer 可以扩展到包含 10,000 多个节点图的数据集，例如 Coauthor 数据集，甚至可以扩展到更大的图，如下图所示。