【ICML2024】论谱不变图神经网络的表达能力

将谱信息融入图神经网络（GNNs）以提升其性能已显示出良好的效果，但由于特征向量的固有模糊性，这带来了一个基本挑战。为了解决这一模糊性，各种架构被提出，这些架构被称为谱不变架构。值得注意的例子包括使用谱距离、谱投影矩阵或其他不变谱特征的GNNs和图Transformers。然而，这些谱不变架构的潜在表达能力仍然很不明确。本研究的目标是深入理解使用谱特征时可获得的表达能力。

我们首先引入了一个设计谱不变GNNs的统一消息传递框架，称为特征空间投影GNN（EPNN）。综合分析显示，EPNN本质上统一了所有之前的谱不变架构，因为它们要么严格地不如EPNN表达能力强，要么与EPNN等效。还建立了不同架构之间的细粒度表达能力层次。另一方面，我们证明了EPNN本身被最近提出的一类子图GNNs所限制，这意味着所有这些谱不变架构的表达能力都严格低于3-WL。

最后，我们讨论了在结合更具表达能力的GNNs时，使用谱特征是否可以获得额外的表达能力。