摘要

空间消息传递图神经网络（MPGNNs）在图结构数据的学习中得到了广泛应用。然而，l步MPGNNs的关键局限在于它们的“感受野”通常仅限于节点的l跳邻域，并且远距离节点间的信息交换受到过度压缩（over-squashing）的限制。为了解决这些局限，我们提出了一种新的图神经网络（GNNs）建模范式——时空谱图神经网络（S$^2$GNNs），该方法协同结合了空间参数化和频谱参数化的图滤波器。部分在频域中参数化的滤波器能够实现全局而高效的信息传播。我们证明了S$^2$GNNs克服了过度压缩问题，并且其逼近理论误差界比MPGNNs更严格。此外，从基础层面重新思考图卷积打开了新的设计空间。例如，S$^2$GNNs允许自由的位置编码，这使得它们比1-维斯费勒-莱曼（Weisfeiler-Lehman, WL）测试更具表达能力。为了获得通用的S$^2$GNNs，我们提出了适用于有向图的频谱参数化滤波器。实验结果表明，S$^2$GNNs在肽长程基准任务等任务上优于空间MPGNNs、图变换器和图重连方法，并且与最先进的序列建模方法具有竞争力。在40 GB的GPU上，S$^2$GNNs可以扩展到数百万个节点。