图在计算和机器学习 (ML) 中无处不在，其中对象及其关系表示为节点（或顶点）以及节点对之间的边（或链接）。例如，社交网络、道路网络以及分子结构和相互作用都是底层数据集具有自然图结构的领域。ML 可用于学习节点、边或整个图的属性。
图学习的一种常见方法是图神经网络(GNN)，它通过对节点、边和全局属性应用可优化的转换来对图数据进行操作。最典型的 GNN 类通过消息传递框架运行，其中每一层将一个节点的表示与其直接邻居的表示聚合在一起。
最近，图变换器模型已成为消息传递 GNN 的流行替代方案。这些模型建立在Transformer 架构在自然语言处理 (NLP) 中的成功基础之上，使其适用于图结构化数据。图变换器中的注意力机制可以通过交互图建模，其中边表示相互关注的节点对。与消息传递架构不同，图变换器具有与输入图分开的交互图。典型的交互图是完整图，这表示一种完整的注意力机制，可以建模 所有节点对之间的直接交互。然而，这会产生二次计算和内存瓶颈，从而限制图变换器对最多只有几千个节点的小图数据集的适用性。使图变换器可扩展一直被认为是该领域最重要的研究方向之一（请参阅此处的第一个未解决的问题）。
一种自然的补救措施是使用具有较少边的稀疏交互图。已经提出了许多稀疏且高效的转换器来消除序列的二次瓶颈，但它们通常不会以原则性的方式扩展到图。
在ICML 2023上发表的 “ Exphormer：用于图的稀疏变换器”中，我们通过引入专为图数据设计的变换器稀疏注意力框架来解决可扩展性挑战。Exphormer 框架利用了扩展图，这是谱图理论中的一种强大工具，能够在各种数据集上获得强大的实证结果。我们对 Exphormer 的实现现已在GitHub上提供。
扩展图
Exphormer 的核心思想是使用扩展图，它是稀疏但连通性良好的图，具有一些有用的属性 - 1) 图的矩阵表示具有与完全图类似的线性代数属性，2) 它们表现出随机游走的快速混合，即从任何起始节点开始的随机游走中的少量步骤足以确保收敛到图节点上的“稳定”分布。扩展器已应用于各种领域，例如算法、伪随机性、复杂性理论和纠错码。
一种常见的扩展图类别是d正则扩展图，其中每个节点都有d条边（即每个节点的度为d）。扩展图的质量通过其谱间隙衡量，谱间隙是其邻接矩阵（图的矩阵表示，其中行和列由节点索引，并且条目指示节点对是否通过边连接）的代数属性。那些最大化谱间隙的图称为拉马努金图- 它们的间隙为d - 2*√( d -1 )，这基本上是d正则图中最好的。多年来，针对各种d值提出了许多确定性和随机性的拉马努金图构造。我们使用Friedman 的随机扩展器构造，它能生成近拉马努金图。
扩展器图是 Exphormer 的核心。好的扩展器是稀疏的，但表现出随机游动的快速混合，使其全局连通性适合于图变换器模型中的交互图。
Exphormer 将标准 Transformer 的密集全连接交互图替换为稀疏d正则扩展图的边。直观地讲，扩展图的谱近似和混合特性允许远距离节点在图形转换器架构中堆叠多个注意层后相互通信，即使节点之间可能不直接相互关注。此外，通过确保d为常数（与节点数量的大小无关），我们在生成的交互图中获得线性数量的边。
Exphormer：构建稀疏交互图
Exphormer 将扩展器边与输入图和虚拟节点相结合。更具体地说，Exphormer 的稀疏注意力机制构建了一个由三种类型的边组成的交互图：
来自输入图的边（局部注意力）
来自常数度扩展图的边（扩展器注意力）
从每个节点到一小组虚拟节点的边（全局注意力）
Exphormer 通过组合三种类型的边来构建交互图。生成的图具有良好的连通性，并保留了输入数据集图的归纳偏差，同时仍保持稀疏性。
每个组件都有特定的用途：输入图中的边保留了输入图结构的归纳偏差（这通常会在完全连接的注意力模块中丢失）。同时，扩展器边允许良好的全局连接和随机游走混合属性（以更少的边在光谱上近似完整图）。最后，虚拟节点充当全局“内存接收器”，可以直接与每个节点通信。虽然这会导致每个虚拟节点的额外边等于输入图中的节点数，但生成的图仍然很稀疏。扩展器图的度数和虚拟节点的数量是需要调整的超参数，用于改进质量指标。
此外，由于我们对全局注意力采用常数度的扩展图和常数个虚拟节点，因此得到的稀疏注意力机制与原始输入图的大小呈线性关系，即，它对直接交互的数量建模，其数量级与节点和边的总数成正比。
我们还表明，Exphormer 的表现力与密集变压器一样强，并且遵循通用近似特性。具体而言，当 Exphormer 的稀疏注意力图增加自循环（将节点连接到自身的边）时，它可以通用地近似连续函数 [ 1 , 2 ]。
与序列稀疏 Transformer 的关系
将 Exphormer 与序列稀疏注意力方法进行比较是很有趣的。在概念上与我们的方法最相似的架构可能是BigBird，它通过组合不同的组件来构建交互图。BigBird 也使用虚拟节点，但与 Exphormer 不同的是，它对其余组件 使用窗口注意力和来自Erdős-Rényi随机图模型的随机注意力。
BigBird 中的窗口注意力机制会按序列查看围绕某个标记的标记，而 Exphormer 中的局部邻域注意力机制则可以看作是窗口注意力机制对图的概括。
n 个节点 上的 Erdős-Rényi 图G(n, p)以概率p独立连接每对节点，当p足够高时，它也可用作扩展器图。但是，需要超线性数量的边 (Ω( n log n )) 才能确保 Erdős-Rényi 图是连通的，更不用说好的扩展器了。另一方面，Exphormer 中使用的扩展器只有线性数量的边。
实验结果
早期研究已经展示了在包含多达 5,000 个节点的图数据集上使用基于全图 Transformer 的模型。为了评估 Exphormer 的性能，我们以著名的GraphGPS 框架[ 3 ] 为基础，该框架结合了消息传递和图转换器，并在多个数据集上实现了最先进的性能。我们表明，用 Exphormer 替换 GraphGPS 框架中的图注意力组件的密集注意力，可以实现具有相当或更好性能的模型，通常需要更少的可训练参数。
此外，Exphormer 还特别允许图转换器架构远远超出上述通常的图大小限制。Exphormer 可以扩展到包含 10,000 多个节点图的数据集，例如Coauthor 数据集，甚至可以扩展到更大的图，例如著名的ogbn-arxiv 数据集，这是一个引文网络，由 170K 个节点和 110 万条边组成。
在五个长距离图形基准数据集上将 Exphormer 与标准 GraphGPS 进行比较的结果。我们注意到，在本文发表时，Exphormer 在五个数据集中的四个数据集（PascalVOC-SP、COCO-SP、Peptides-Struct、PCQM-Contact）上取得了最先进的结果。
最后，我们观察到 Exphormer 通过扩展器创建小直径的叠加图，表现出有效学习长距离依赖关系的能力。长距离图基准 是一套由五个图学习数据集组成的套件，旨在衡量模型捕获长距离交互的能力。结果表明，基于 Exphormer 的模型优于标准 GraphGPS 模型（在发布时，该模型在五个数据集中的四个上都处于领先地位）。
结论
图转换器已成为 ML 的重要架构，可将 NLP 中使用的非常成功的基于序列的转换器应用于图结构数据。然而，可扩展性已被证明是实现在具有大型图的数据集上使用图转换器的主要挑战。在这篇文章中，我们介绍了 Exphormer，这是一个稀疏注意力框架，它使用扩展图来提高图转换器的可扩展性。Exphormer 被证明具有重要的理论特性并表现出强大的经验性能，特别是在需要学习长距离依赖关系的数据集上。有关更多信息，我们向读者介绍了 ICML 2023 的简短演示视频。
致谢
我们感谢我们的研究合作伙伴——不列颠哥伦比亚大学的 Hamed Shirzad 和 Danica J. Sutherland 以及谷歌研究部的 Ali Kemal Sinop。特别感谢 Tom Small 制作了本文中使用的动画。
评论