摘要

本文提出将一种低秩全局注意力（Low-Rank Global Attention, LRGA）模块引入图神经网络（Graph Neural Networks, GNNs），以提升其泛化能力。LRGA是点积注意力机制（Vaswani et al., 2017）的一种计算与内存高效的变体。为从理论上量化在GNN中引入LRGA模块所带来的泛化性能提升，本文聚焦于一类具有强表达能力的GNN家族，证明在该模型中引入LRGA可实现与一种强大图同构性检验算法——即2-Folklore Weisfeiler-Lehman（2-FWL）算法的算法对齐。具体而言，本文工作包括以下三个方面：（i）考虑近期提出的随机图神经网络（Random Graph Neural Network, RGNN）框架（Sato et al., 2020），并证明其在概率意义上具有通用性；（ii）证明在RGNN中引入LRGA后，其更新过程可通过多项式核函数实现与2-FWL算法更新步骤的对齐；（iii）在使用随机初始化的两层多层感知机（MLP）学习该核函数的特征映射时，给出了该映射的样本复杂度上界。从实际应用角度看，将LRGA模块集成到现有GNN层中，可在当前主流GNN基准测试中取得当前最优（state-of-the-art）性能。此外，我们观察到，将LRGA模块应用于多种不同的GNN架构时，通常能够显著缩小不同模型之间的性能差距。