Spectral Graph Neural Networks (GNNs) have achieved tremendous success in
graph learning. As an essential part of spectral GNNs, spectral graph
convolution extracts crucial frequency information in graph data, leading to
superior performance of spectral GNNs in downstream tasks. However, in this
paper, we show that existing spectral GNNs remain critical drawbacks in
performing the spectral graph convolution. Specifically, considering the
spectral graph convolution as a construction operation towards target output,
we prove that existing popular convolution paradigms cannot construct the
target output with mild conditions on input graph signals, causing spectral
GNNs to fall into suboptimal solutions. To address the issues, we rethink the
spectral graph convolution from a more general two-dimensional (2-D) signal
convolution perspective and propose a new convolution paradigm, named 2-D graph
convolution. We prove that 2-D graph convolution unifies existing graph
convolution paradigms, and is capable to construct arbitrary target output.
Based on the proposed 2-D graph convolution, we further propose ChebNet2D, an
efficient and effective GNN implementation of 2-D graph convolution through
applying Chebyshev interpolation. Extensive experiments on benchmark datasets
demonstrate both effectiveness and efficiency of the ChebNet2D.

提出了一种名为 2-D graph convolution 的新卷积范式，通过应用 Chebyshev 插值在 ChebNet2D 上实现，以解决现有光谱图神经网络在执行光谱图卷积时存在的关键问题。