Spatio-Spectral Graph Neural Networks

空间消息传递图神经网络（MPGNNs）被广泛用于学习图结构化数据。然而，l步MPGNNs的主要限制在于它们的“接受域”通常仅限于节点的l跳邻域，并且远距离节点之间的信息交换受到过度压缩的限制。受到这些限制的启发，我们提出了空间-频谱图神经网络（S$^2$GNNs）——一种新的图神经网络（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可以扩展到数百万个节点，并且在状态-of-the-art序列建模方面具有竞争力。

论文旨在解决l-step MPGNNs的局限性，即接收范围通常仅限于节点的l-hop邻域，并且远程节点之间的信息交换受到过度压缩的限制。同时，论文还试图提高图神经网络的表达能力。

论文提出了S$^2$GNNs，一种新的图神经网络建模范式，将空间和频域参数化的图滤波器相结合，部分在频域中参数化的滤波器使得全局信息传播变得更加高效。

论文展示了S$^2$GNNs比空间MPGNNs、图变换器和图重连等方法更加优越，例如在肽长程基准任务上，S$^2$GNNs表现出色，并且在序列建模方面也有竞争力。此外，论文还提出了适用于有向图的频域参数化滤波器，并且S$^2$GNNs允许自由位置编码，使其比1-Weisfeiler-Lehman (WL)测试更具表现力。

最近在这个领域中，还有一些相关的研究，例如《Graph Convolutional Networks》、《Semi-Supervised Classification with Graph Convolutional Networks》、《Gated Graph Sequence Neural Networks》等。