摘要
图变换器（Graph Transformers, GTs）作为一种理论表达能力优于消息传递图神经网络（GNNs）的架构，近年来受到广泛关注。然而，典型的GT模型至少具有二次时间复杂度，难以扩展至大规模图结构。尽管近年来已提出若干线性复杂度的GT模型，但它们在多个主流图数据集上的表现仍落后于GNN基线模型，这引发了对其实际表达能力的严重担忧。为在GT的表达能力与可扩展性之间取得平衡，本文提出Polynormer——一种具有线性复杂度且具备多项式表达能力的图变换器模型。Polynormer基于一个新颖的基础模型构建，该模型能够学习输入特征上的高阶多项式。为确保基础模型具备置换等变性（permutation equivariance），我们分别将该模型与图拓扑结构和节点特征相结合，从而分别构建出局部与全局等变注意力机制。由此，Polynormer采用线性复杂度的局部到全局注意力机制，用于学习高阶等变多项式，其多项式系数由注意力得分动态调控。我们在包含百万级节点的大规模图在内的13个同质性（homophilic）与异质性（heterophilic）图数据集上对Polynormer进行了全面评估。实验结果表明，Polynormer在绝大多数数据集上均显著优于当前最先进的GNN与GT基线模型，甚至在未使用非线性激活函数的情况下仍保持优越性能，充分验证了其在表达能力与效率之间的良好平衡。