A Scalable and Effective Alternative to Graph Transformers

图神经网络（GNN）在图表示学习方面表现出了惊人的性能，但由于其表达能力有限，它们面临着捕捉长距离依赖关系的挑战。为了解决这个问题，引入了图变换器（GT），利用自注意机制有效地建模节点之间的成对关系。尽管GT具有优势，但它们在图中的节点数量方面具有二次复杂度，限制了它们在大型图形中的适用性。在这项工作中，我们提出了图增强上下文算子（GECO），它是GT的一种可扩展且有效的替代方案，利用邻域传播和全局卷积，在准线性时间内有效地捕获局部和全局依赖关系。我们在合成数据集上的研究表明，相对于优化的注意力，GECO在具有2M节点的图中实现了169倍的加速。在各种基准测试中的进一步评估显示，GECO可扩展到传统GT经常面临内存和时间限制的大型图形。值得注意的是，GECO始终实现了与基线相当或更高的质量，将SOTA提高了4.5％，为大规模图形学习提供了可扩展且有效的解决方案。

本文旨在解决GNN在捕捉长距离依赖方面的限制，以及GT在处理大规模图时的复杂度问题。

本文提出了一种新的图神经网络GECO，利用邻域传播和全局卷积实现了对局部和全局依赖的有效捕捉。相比GT，GECO具有更高的可扩展性和更快的计算速度。

本文的实验结果表明，GECO在处理大规模图时比GT更具有可扩展性和计算效率，并且在多个基准测试中实现了与或优于当前最先进方法的结果。

与本文相关的研究包括Graph Transformers（GTs）和其他一些图神经网络模型，如GCN、GAT等。