ICMLJun, 2024
谱不变图神经网络的表达能力研究
On the Expressive Power of Spectral Invariant Graph Neural Networks
Bohang Zhang, Lingxiao Zhao, Haggai Maron
TL;DR使用光谱特征的图神经网络（GNNs）已显示出有希望的结果，但由于特征向量的固有模棱两可性，这提出了一项基本挑战。已经提出了几种架构来解决这种模棱两可性，被称为光谱不变架构。其中几个著名的例子包括使用光谱距离、光谱投影矩阵或其他不变光谱特征的 GNNs 和图变换器。然而，这些光谱不变架构的潜在表达能力仍然不太清楚。本研究的目标是在使用光谱特征时获得深入的理论理解可获得的表达能力。我们首先介绍了一种用于设计光谱不变 GNNs 的统一传递信息框架，称为特征空间投影 GNN（EPNN）。全面的分析表明，EPNN 本质上统一了所有先前的光谱不变架构，因为它们要么严格不可表达，要么与 EPNN 等价。还建立了不同架构之间的细粒度表达层次结构。另一方面，我们证明了 EPNN 本身被一种最近提出的子图 GNNs 类所约束，这意味着所有这些光谱不变架构严格不可表达 3-WL。最后，我们讨论了结合更具表达能力的 GNNs 时是否可以通过使用光谱特征来获得额外的表达能力。