On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformers

图转换器近来在图学习领域受到了极大的关注，部分原因是它们通过自注意力能够更好地捕捉全局交互。然而，尽管高阶图神经网络已经得到了相当充分的研究，但将图转换器扩展到更高阶的变体的探索才刚刚开始。理论理解和实证结果都十分有限。在本文中，我们系统地研究了阶数为$k$的图转换器和稀疏变体的理论表达能力。我们首先证明，没有额外结构信息的$k$阶图转换器比$k$-Weisfeiler Lehman($k$-WL)测试的表达能力要低，尽管它的计算成本很高。然后，我们探索了两种策略来稀疏化和增强高阶图转换器，旨在提高它们的效率和表达能力。事实上，基于邻域信息的稀疏化可以增强表达能力，因为它提供了关于输入图结构的额外信息。特别地，我们展示了一种自然的基于邻域的稀疏$k$阶转换器模型不仅计算效率高，而且表达能力强——和$k$-WL测试一样强。我们进一步研究了几种计算效率高且提供了表达能力分析的稀疏图注意力模型。最后，我们提供实验结果来展示不同稀疏化策略的有效性。

本文旨在系统研究高阶图变换器的理论表达能力，并探索优化这些变换器的策略，以提高它们的效率和表达能力。此外，论文还试图验证高阶图变换器对于解决图学习问题的有效性。

论文提出了一种基于邻域信息的稀疏高阶图变换器模型，该模型不仅计算效率高，而且表达能力与$k$-Weisfeiler Lehman ($k$-WL)测试相当，进一步探索了其他稀疏图注意力模型的表达能力。

论文的实验表明，基于邻域信息的稀疏高阶图变换器模型在效率和表达能力方面都具有优势。此外，论文还提供了其他稀疏图注意力模型的表达能力分析。论文使用了多个数据集，并开源了代码。

在最近的研究中，已经探索了高阶图神经网络的表达能力，但是对于高阶图变换器的研究还比较有限。此外，也有一些研究关注了图注意力模型的稀疏化问题。