摘要

我们提出了一种构建具有线性复杂度和在多种基准测试中取得最先进结果的通用、强大、可扩展（GPS）图Transformer的方法。图Transformer（GTs）在图表示学习领域受到了广泛关注，近期有许多相关研究发表，但它们缺乏关于什么是良好的位置编码或结构编码以及这些编码之间有何区别的共同基础。在本文中，我们对不同类型的编码进行了更清晰的定义，并将其分类为$\textit{局部}$、$\textit{全局}$或$\textit{相对}$编码。以往的图Transformer受限于节点数仅为几百的小规模图，而我们在此提出了首个复杂度与节点数和边数呈线性关系$O(N+E)$的架构，通过将局部真实边聚合与全连接Transformer解耦实现这一目标。我们认为这种解耦不会影响表达能力，我们的架构可以作为图上的通用函数逼近器。我们的GPS方法包括选择三个主要成分：(i) 位置/结构编码，(ii) 局部消息传递机制，以及 (iii) 全局注意力机制。我们提供了一个模块化的框架$\textit{GraphGPS}$，支持多种类型的编码，并且在小规模和大规模图中均能保证效率和可扩展性。我们在16个基准测试上对我们的架构进行了测试，并展示了在所有测试中的高度竞争力，证明了模块化和不同策略组合带来的实证优势。