《Recipe for a General, Powerful, Scalable Graph Transformer》NIPS2022
摘要
论文提出了一种构建通用、强大、可扩展（GPS）图变换器（Graph Transformer, GT）的方法，该方法具有线性复杂度，并在多个基准测试上取得了最先进的结果。图变换器在图表示学习领域越来越受欢迎，但目前缺乏关于什么是好的定位或结构编码的共同基础。论文总结了不同类型的编码，并将其更清晰地定义并分类为局部、全局或相对编码。此外，提出了首个架构，通过将局部真实边聚合与全连接变换器解耦，实现了与节点和边数线性相关的复杂度 O(N+E)O(N+E)。作者认为这种解耦不会负面影响表达性，并声称他们的架构是图的通用函数逼近器。GPS 配方包括选择三个主要成分：（i）定位/结构编码，（ii）局部消息传递机制，和（iii）全局注意力机制。作者构建并开源了一个模块化框架，支持多种类型的编码，并在小型和大型图上都提供了效率和可扩展性。在11个基准测试上测试了他们的架构，并在所有基准测试上展示了非常有竞争力的结果。
概述
拟解决的问题： 图变换器（GTs）在处理小规模图时受到限制，并且缺乏一个共同的基础来定义什么是好的定位或结构编码。此外，标准的全局注意力由于其二次方的计算成本 O(N2)O(N2)，限制了 GTs 只能应用于具有数百个节点的小图。
创新之处：
- 提出了一个清晰的定位编码（PE）和结构编码（SE）的定义，并将其分类为局部、全局和相对编码。
- 提出了首个线性复杂度的架构，通过解耦局部真实边聚合和全连接变换器，使得模型可以扩展到具有数千个节点的图。
- 构建了一个模块化框架，支持多种类型的编码，并在小型和大型图上都提供了效率和可扩展性。
- 在多个基准测试上展示了有竞争力的结果，证明了模块化和不同策略组合的经验优势。
方法论
提出了一种名为通用、强大、可扩展（GPS）的图Transformer架构，通过精心设计的定位和结构编码，结合局部消息传递机制和全局注意力机制，实现了对图数据的高效处理，具有线性时间复杂度，能够在保持强大表达力的同时扩展到大型图结构，并通过模块化设计灵活适应不同的图表示学习任务。它包括三个主要组成部分：
- 定位/结构编码：整合了多种 PE 和 SE 方案，作为节点特征的附加信息。
- 局部消息传递机制：使用局部消息传递和全局注意力层的组合。
- 全局注意力机制：采用线性注意力模型，如 Performer 或 BigBird，以实现对大型图的扩展。
3.1 模块化位置和结构编码
提出了对PE和SE的分类方法，将它们分为局部（Local）、全局（Global）和相对（Relative）三类，以促进这些编码在图变换器中的集成，并为未来的研究方向提供指导。
PE 给出了距离的概念，而 SE 给出了结构相似性的概念。
局部编码使得节点能够了解其在局部簇中的位置和角色。如果两个节点在同一个局部簇中且彼此接近，则它们的局部编码也应该相近。局部编码的例子包括：
- 随机游走矩阵非对角线元素的列求和。
- 节点到其所在簇质心的距离。
全局编码允许节点了解其在整个图中的全局位置。在全局视角下，如果两个节点在图中彼此接近，则它们的全局编码也应该相近。全局编码的例子包括：
- 邻接矩阵、拉普拉斯矩阵或距离矩阵的特征向量。
- 图的质心距离。
- 图中每个连通分量的唯一标识符。
相对编码允许两个节点理解它们之间的距离或方向关系。相对编码的例子包括：
- 基于热核、随机游走、格林函数、图测地线或任何局部/全局编码的节点距离对之间的边缘嵌入。
- 特征向量的梯度或任何局部/全局编码的梯度。
- 指示两个节点是否在同一簇中的布尔值。
3.2 为什么我们需要MPNN中的PE和SE
这一节探讨了为什么需要在图神经网络（GNNs）中使用位置编码（PE）和结构编码（SE），尤其是针对消息传递神经网络（MPNNs）。
MPNNs在处理图数据时，尽管能够有效地进行消息传递和聚合，但它们在理论上受到Weisfeiler-Lehman（WL）测试的限制。WL测试是一种图同构测试，它基于节点的标签和邻居标签的组合来区分节点。MPNNs的表达能力被证明与1-WL测试等价，这意味着它们在没有额外信息（如PE和SE）的情况下，难以区分某些非同构图。
1-WL测试是一种简单的WL测试，它只考虑节点的1-hop邻居信息。尽管MPNNs在图结构上操作，但它们在没有PE和SE的情况下，对于某些图结构的信息是“盲”的。例如，对于某些特定的图结构，如Circular Skip Link (CSL) 图和Decalin分子图，MPNNs无法区分这些图中的节点，因为这些节点在结构上是同构的，但全局或局部的PE和SE可以提供区分它们的信息。
具体来说，PE和SE可以提供以下帮助：
- 全局PE：通过使用图的全局属性（如图的拉普拉斯矩阵的特征向量），可以帮助节点了解其在图中的全局位置。
- 局部SE：通过使用局部图结构的信息（如m-step随机游走矩阵的对角元素），可以帮助节点理解其在局部子结构中的角色。
3.3 GPS层:MPNN+Transformer混合
尽管MPNNs能够有效地处理图数据，但它们受限于过度平滑和过度压缩的问题，这限制了它们对图结构的表达能力。为了克服这些限制，作者提出了GPS层，该层通过结合局部消息传递和全局自注意力机制，旨在提高模型对图结构的捕捉能力。
GPS层的设计基于以下几个关键组件：
-
局部消息传递机制（MPNN层）：这一部分负责处理图中每个节点的局部邻域信息。通过聚合邻居节点的信息，MPNN层更新每个节点的特征表示。
-
全局注意力机制（Global Attention层）：这一部分允许模型在全局范围内捕捉节点之间的关系。通过自注意力机制，每个节点可以关注图中的所有其他节点，从而捕捉长距离依赖。
-
特征融合：通过多层感知器（MLP）将局部消息传递和全局注意力的结果结合起来，生成新的特征表示。
原文地址：https://blog.csdn.net/qq_46981910/article/details/142336640
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！