摘要

图Transformer作为一种新兴的架构，在多种图学习与表示任务中展现出巨大潜力。尽管取得了显著成功，但如何在保持与消息传递网络相当的准确率的前提下，将图Transformer扩展至大规模图，仍是当前面临的重大挑战。本文提出Exphormer，一种用于构建强大且可扩展图Transformer的框架。Exphormer采用基于两种机制的稀疏注意力机制：虚拟全局节点（virtual global nodes）与扩展图（expander graphs）。这两种机制所具备的数学特性——如谱扩张性（spectral expansion）、伪随机性（pseudorandomness）以及稀疏性——使得所构建的图Transformer在计算复杂度上仅与图的规模呈线性关系，同时能够证明所得到的Transformer模型具备理想的理论性质。实验结果表明，将Exphormer集成到近期提出的GraphGPS框架中，可在多种图数据集上取得具有竞争力的实证性能，其中在三个数据集上达到了当前最优（state-of-the-art）结果。此外，我们还验证了Exphormer在处理比以往图Transformer架构更大规模图数据时仍具备良好的可扩展性。相关代码已开源，地址为：\url{https://github.com/hamed1375/Exphormer}。