Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification

• URL: http://arxiv.org/abs/2603.19091v2
• Date: Thu, 26 Mar 2026 15:25:26 GMT
• Title: Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification
• Abstract summary: Spectral Graph Neural Networks (Spectral GNNs) for node classification promise frequency-domain filtering on graphs.<n>Recent work shows that graph Laplacian eigenvectors do not in general have the key properties of a true Fourier basis.<n>This paper argues that for node classification, Spectral GNNs neither meaningfully capture the graph spectrum nor reliably improve performance.
• Score: 10.36868472818283
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion [82.7007012514703]
  We show that under a denoising objective, linear attention is suboptimal and can only learn an average spectral denoising filter over the training distribution.<n>We introduce Spectral Attention, which directly utilizes the input graph spectrum and provably outperforms linear attention by a margin governed by the spectral diversity of the distribution.<n>For block models, GCA provably matches the idealized Spectral Attention mechanism.
  arXiv  Detail & Related papers  (2026-07-07T17:52:17Z)
• Full-Spectrum Graph Neural Network: Expressive and Scalable [47.228678765460735]
  spectral graph neural networks (GNNs) can universally approximate node signals.<n>We propose the Full-Spectrum GNN (FSpecGNN), a second-order generalization of classical spectral GNNs.<n> Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.
  arXiv  Detail & Related papers  (2026-05-07T06:53:49Z)
• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum [17.27380476408333]
  Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power.<n>We propose a method to provably improve SGNNs' expressivity on simple spectrum graphs.
  arXiv  Detail & Related papers  (2025-06-05T19:26:29Z)
• GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
  Graph State Space Network (GrassNet) is a novel graph neural network with theoretical support that provides a simple yet effective scheme for designing arbitrary graph spectral filters. To the best of our knowledge, our work is the first to employ SSMs for the design of graph GNN spectral filters. Extensive experiments on nine public benchmarks reveal that GrassNet achieves superior performance in real-world graph modeling tasks.
  arXiv  Detail & Related papers  (2024-08-16T07:33:58Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain.<n>We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  Spectral graph neural networks (GNNs) learn graph representations via spectral-domain graph convolutions. We introduce Specformer, which effectively encodes the set of all eigenvalues and performs self-attention in the spectral domain. By stacking multiple Specformer layers, one can build a powerful spectral GNN.
  arXiv  Detail & Related papers  (2023-03-02T07:36:23Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  Spectral Graph Neural Network is a kind of Graph Neural Network based on graph signal filters. We first prove that even spectral GNNs without nonlinearity can produce arbitrary graph signals. We also establish a connection between the expressive power of spectral GNNs and Graph Isomorphism (GI) testing.
  arXiv  Detail & Related papers  (2022-05-23T10:22:12Z)
• When Does A Spectral Graph Neural Network Fail in Node Classification? [10.177243505636692]
  We conduct a theoretical analysis of spectral GNNs performance by investigating their prediction error. We indicate that graph filters with low response efficiency on label difference are prone to fail.
  arXiv  Detail & Related papers  (2022-02-16T07:18:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.