VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections

图形转换器以其采用注意机制的能力，能够从图形的复杂拓扑和特征信息中捕获表达性表示，已被证明是一种有效的图形学习方法。传统上，图形转换器对每对节点执行密集的注意力（或全局注意力）以学习节点表示向量，导致二次计算成本，这对于大规模图形数据来说是无法承受的。因此，图形转换器的小批量训练是一个有前途的方向，但每个小批量中的有限样本无法支持有效的密集注意力以编码信息丰富的表示。面对这个瓶颈，我们（1）首先通过为每个节点分配一个由个性化PageRank（PPR）采样的令牌列表来开始，然后仅在这个列表上应用标准的多头自注意力来计算其节点表示。这种PPR标记化方法将模型训练与复杂的图形拓扑信息分离，使得重量级特征工程离线和独立，从而可以通过批量加载每个节点的令牌列表来进行图形转换器的小批量训练。我们进一步证明了这种PPR标记化方法可以作为一个具有固定多项式滤波器和跳跃知识的图形卷积网络。然而，仅使用个性化PageRank可能会限制由令牌列表携带的信息，这可能无法支持模型训练的不同图形归纳偏差。为此，我们（2）通过引入基于结构和内容的超级节点的多种虚拟连接类型来重构图形，使PPR标记化能够将局部和全局上下文、长程交互和异质信息编码到每个节点的令牌列表中，然后正式化我们的基于虚拟连接排名的图形转换器（VCR-Graphormer）。

解决问题：该论文试图解决大规模图数据中图转换器计算成本高的问题，提出了一种基于个性化PageRank的tokenization方法，使得mini-batch训练成为可能。

关键思路：论文提出了一种基于个性化PageRank的tokenization方法，将每个节点分配一个token列表，然后只对该列表应用标准的多头自注意力机制来计算节点表示向量，从而降低了计算成本，使得mini-batch训练成为可能。

其他亮点：该论文进一步证明了个性化PageRank可行作为具有固定多项式滤波器和跳跃知识的图卷积网络。此外，该论文通过引入多种类型的虚拟连接，通过结构和内容的超级节点，实现了对图的重连，使得PPR tokenization可以将本地和全局上下文，长程交互和异质信息编码到每个节点的token列表中。该论文使用了开源代码，并在多个数据集上进行了实验，证明了该方法的有效性和可行性。

相关研究：最近的相关研究包括《Graph Attention Networks》、《Semi-Supervised Classification with Graph Convolutional Networks》等。