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 已应用于不同领域,例如算法、伪随机性、复杂理论和代码纠错。
一类常见的扩展图是
扩展图,其中每个节点都有d条边(即每个节点的度数为d)。扩展图的好坏通过谱间隙来衡量的,谱间隙是其相邻矩阵的代数属性。那些最大化谱间隙的图被称为Ramanujan图——它们实现了
的间隙,这本质上是
正则图中最好的。多年来,针对不同的
值,提出了一系列的Ramanujan图构造。本文使用Friedman随机扩展结构,它可以近似产生Ramanujan图。
Exphormer 将扩输入图的扩展器边缘和虚拟节点结合起来。具体来说,Exphormer 的稀疏注意力机制构建了一个由三种类型的边组成的交互图,如下图所示:
其中,每个组件都有特定的用途:输入图的边保留输入图结构的归纳偏差;扩展边允许良好的全局连接性和随机游走混合特性;虚拟节点充当全局“内存接收器”,可以直接与每个节点通信。虽然这会导致每个虚拟节点的附加边等于输入图中的节点数,但生成的图仍然是稀疏的。扩展图的degree和虚拟节点的数量是用于调整以提高质量指标的超参数。
此外,由于使用constant-degree扩展图和少量恒定数量的虚拟节点来进行全局注意力,因此所得的稀疏注意力机制与原始输入图的大小呈线性关系,即它模拟了许多直接交互节点和边总数的顺序。
此外,Exphormer 与密集Transformer一样具有表现力,并且遵循常用的近似属性。特别是,当 Exphormer 的稀疏注意力图通过自环(将节点连接到自身的边)进行增强时,它可以普遍逼近连续函数。
将 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 数据集,甚至可以扩展到更大的图,如下图所示。