Distinguished In Uniform: Self Attention Vs. Virtual Nodes

Graph Transformers（GTs），例如SAN和GPS，是将消息传递GNN（MPGNN）与全局自注意力相结合的图处理模型。它们被证明是通用函数逼近器，但有两个限制：1. 初始节点特征必须使用某些位置编码进行增强。2. 近似是非均匀的：不同大小的图可能需要不同的逼近网络。 我们首先澄清这种普遍性形式不是GTs所特有的：使用相同的位置编码，纯MPGNN甚至2层MLP也是非均匀通用逼近器。然后，我们考虑均匀表达能力：目标函数需要由一个网络逼近所有大小的图。在这里，我们将GTs与更高效的MPGNN +虚拟节点架构进行比较。两个模型定义之间的本质区别在于它们的全局计算方法——自我注意力与虚拟节点。我们证明这两个模型都不是均匀通用逼近器，然后证明我们的主要结果：两个模型的均匀表达能力并不相互包含。我们通过对合成数据的实验来证明这个理论。我们进一步增强了我们的研究，使用真实世界的数据集进行观察，发现实践中没有明确的排名。

比较Graph Transformers（GTs）和MPGNN + Virtual Node架构的统一表达能力，以及它们在实践中的效果

论文比较了GTs和MPGNN + Virtual Node架构的全局计算方法，证明了它们都不是统一通用逼近器，且两者的统一表达能力不相互包含

论文证明了使用相同的位置编码，纯MPGNNs和2层MLPs也是非均匀通用逼近器；实验使用了合成数据和真实数据集，并观察到了不同的结果；论文提供了开源代码

相关研究包括：《Graph Attention Networks》、《Simplifying Graph Convolutional Networks》、《How Powerful are Graph Neural Networks?》等