Spectral Graph Neural Network is a kind of Graph Neural Network (GNN) based
on graph signal filters. Some models able to learn arbitrary spectral filters
have emerged recently. However, few works analyze the expressive power of
spectral GNNs. This paper studies spectral GNNs' expressive power
theoretically. We first prove that even spectral GNNs without nonlinearity can
produce arbitrary graph signals and give two conditions for reaching
universality. They are: 1) no multiple eigenvalues of graph Laplacian, and 2)
no missing frequency components in node features. We also establish a
connection between the expressive power of spectral GNNs and Graph Isomorphism
(GI) testing, the latter of which is often used to characterize spatial GNNs'
expressive power. Moreover, we study the difference in empirical performance
among different spectral GNNs with the same expressive power from an
optimization perspective, and motivate the use of an orthogonal basis whose
weight function corresponds to the graph signal density in the spectrum.
Inspired by the analysis, we propose JacobiConv, which uses Jacobi basis due to
its orthogonality and flexibility to adapt to a wide range of weight functions.
JacobiConv deserts nonlinearity while outperforming all baselines on both
synthetic and real-world datasets.

本文研究了基于图信号滤波器的谱图神经网络的表达能力，证明了无需非线性函数就可产生任意图信号，并建立了表达能力与图同构测试之间的联系。提出了一种名为 JacobiConv 的新型谱图神经网络，该网络能在不使用非线性函数的情况下超越所有对比算法。