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 的新型谱图神经网络，该网络能在不使用非线性函数的情况下超越所有对比算法。

谱图神经网络的强大程度

How Powerful are Spectral Graph Neural Networks

From the perspective of expressive power, this work compares multi-layer
Graph Neural Networks (GNNs) with a simplified alternative that we call
Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node
features with certain multi-hop operators on the graph and then applies an MLP
in a node-wise fashion. From the perspective of graph isomorphism testing, we
show both theoretically and numerically that GA-MLPs with suitable operators
can distinguish almost all non-isomorphic graphs, just like the
Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions
and examining the equivalence classes they induce on rooted graphs, we prove a
separation in expressive power between GA-MLPs and GNNs that grows
exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count
the number of attributed walks. We also demonstrate via community detection
experiments that GA-MLPs can be limited by their choice of operator family, as
compared to GNNs with higher flexibility in learning.

本文比较了多层图神经网络和一种被称为图增强多层感知器的简化替代品之间的表现，其中后者首先通过图上的某些多跳算子增强节点特征，然后以节点方式应用 MLP；并证明了 GA-MLP 具备适当算子的情况下，能像 Weifeiler-Lehman（WL）测试一样，理论和数值上能够区分几乎所有非同构图，但是 GA-MLP 与 GNN 之间在表达能力方面的差距随着深度呈指数增长，并且 GA-MLP 不能计算属性步行的数量，表明 GA-MLP 受其操作符族的选择限制比拥有更高学习灵活性的 GNN 更为受限，这在社区检测实验中也得到了证明。