How Powerful are Spectral Graph Neural Networks
  Spectral Graph Neural Network is a kind of Graph Neural Network (GNN) based
on graph signal filters, and 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 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 polynomial basis due to
their 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.
