Search papers, labs, and topics across Lattice.
This paper critiques the theoretical foundations and empirical justification for Spectral Graph Neural Networks (GNNs) in node classification. It demonstrates that "graph Fourier bases" lack properties of true Fourier bases, and that polynomial approximations used in spectral GNNs are theoretically unsound due to exact interpolation capabilities. Through theoretical analysis and controlled experiments on MagNet and HoloNet, the authors show that the performance of Spectral GNNs stems from their effective reduction to Message Passing Neural Networks (MPNNs), rather than spectral filtering.
Spectral GNNs' purported spectral advantages for node classification are illusory; their performance actually hinges on their underlying MPNN structure, debunking the "graph Fourier transform" narrative.
Spectral Graph Neural Networks (Spectral GNNs) for node classification promise frequency-domain filtering on graphs, yet rest on flawed foundations. Recent work shows that graph Laplacian eigenvectors do not in general have the key properties of a true Fourier basis, but leaves the empirical success of Spectral GNNs unexplained. We identify two theoretical glitches: (1) commonly used"graph Fourier bases"are not classical Fourier bases for graph signals; (2) (n-1)-degree polynomials (n = number of nodes) can exactly interpolate any spectral response via a Vandermonde system, so the usual"polynomial approximation"narrative is not theoretically justified. The effectiveness of GCN is commonly attributed to spectral low-pass filtering, yet we prove that low- and high-pass behaviors arise solely from message-passing dynamics rather than Graph Fourier Transform-based spectral formulations. We then analyze two representative directed spectral models, MagNet and HoloNet. Their reported effectiveness is not spectral: it arises from implementation issues that reduce them to powerful MPNNs. When implemented consistently with the claimed spectral algorithms, performance becomes weak. This position paper argues that: for node classification, Spectral GNNs neither meaningfully capture the graph spectrum nor reliably improve performance; competitive results are better explained by their equivalence to MPNNs, sometimes aided by implementations inconsistent with their intended design.