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.
Figures & tables
Figure 1: Graph Fourier transform and its inverse, showing spectral modulation by a diagonal filter in the Fourier domain.
MagNet ( α=2πq )
Edges
As
As
As
ℜ(As)
ℑ(As)
m→n
0.5
d0.5
d0.5ejα
d0.5cosα
d0.5sinα
n→m
0.5
d0.5
d0.5e−jα
d0.5cosα
−d0.5sinα
m↔n
1
d−1
d−1
d−1
0
m↔n
0
0
0
0
0
Table 1: Case enumeration of the elements with entry mn in adjacency matrices for different edge types between node m and node n . Here, As is the symmetrized adjacency matrix, As is its GCN-normalized adjacency matrix, and As is the complex-valued adjacency matrix used in MagNet with parameter α=2πq . The variable d denotes the node degree.
Telegram
MLP
None
Row
Sym
Dir
Origin
38.0±7.2
95.6±2.8
74.2±5.5
93.0±4.1
92.8±4.7
No Feature
38.0±0.0
95.4±4.0
38.0±0.0
93.0±4.7
93.0±3.0
In-degree
64.0±5.7
95.8±3.8
80.8±4.1
92.6±3.3
94.4±2.1
Out-degree
63.0±5.7
96.4±2.5
78.4±5.9
90.6±7.4
93.6±4.5
Both degrees
89.4±5.8
95.0±3.4
80.0±4.3
93.4±2.1
94.4±4.3
Table 2: Classification accuracy (%) of Dir-GNN ( Rossi et al., 2024 ) and MLP with different feature configurations and normalization schemes on Telegram datasets. Feature configurations include: original node features from datasets (Origin Feature), constant features (No Feature, all set to 1), and node degree variants (in-degree, out-degree, or both). Bold value indicates learning failure with row normalization and no features. Underline value indicates that predictions can be made accurately using only node degrees by MLP without message passing.
Figure 2: Accuracy change with different coefficients of Dir-GNN ( Rossi et al., 2024 ) on Chameleon and Squirrel datasets. Hyperparameter choices are corresponding to the best parameters in Dir-GNN ( Rossi et al., 2024 ) .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Accuracy change with different coefficients of Dir-GNN ( Rossi et al., 2024 ) on Chameleon and Squirrel datasets. Hyperparameter choices are corresponding to the best parameters in Dir-GNN, except that without L2 normalisation.
Spectral graph convolution applies learned filters in the graph Laplacian or Fourier domain to model graph structure, signal frequencies, and long-range dependencies.
It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNNs (FSpecGNNs), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering from two perspectives: (1) it lifts signals from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNNs, and prove that FSpecGNNs can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.
Xiaohan Wang, Deyu Bo, Longlong Li +1
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.
Despite their theoretical advantages, spectral methods based on the graph Fourier transform (GFT) are seldom used in graph neural networks (GNNs) due to the cost of computing the eigenbasis and the lack of vertex-domain locality in the resulting representations. As a result, most GNNs rely on local approximations such as polynomial Laplacian filters or message passing, which limit their ability to model long-range dependencies. In this paper, we introduce an exact factorization of the GFT into operators acting on subgraphs, which are then combined via a sequence of Cauchy matrices. Building on this factorization, we propose a new class of spectral GNNs, termed L2G-Net (Local to Global Net). Unlike existing spectral methods, which are either fully global (when using the GFT) or local (when using polynomial filters), L2G-Net operates by processing the spectral representations of subgraphs and then combining them via structured matrices. Our algorithm avoids full eigendecompositions, exploiting graph topology to construct the factorization with quadratic complexity in the number of nodes, scaled by the maximum cut size between subgraphs. Experiments stressing long-range dependencies on large graphs show that L2G-Net scales to regimes out of reach for the standard GFT, and is competitive with state-of-the-art methods with orders of magnitude fewer learnable parameters.
Samuel Fernández-Menduiña, Eduardo Pavez, Antonio Ortega
Spectral graph neural networks learn graph filters, but their behavior with increasing depth and polynomial order is not well understood. We analyze these models in the graph Fourier domain, where each layer becomes an element-wise frequency update, separating the fixed spectrum from trainable parameters and making depth and order explicit. In this setting, we show that Gaussian complexity is invariant under the Graph Fourier Transform, which allows us to derive data-dependent, depth, and order-aware generalization bounds together with stability estimates. In the linear case, our bounds are tighter, and on real graphs, the data-dependent term correlates with the generalization gap across polynomial bases, highlighting practical choices that avoid frequency amplification across layers.
Vahan A. Martirosyan, Daniele Malitesta, Hugues Talbot +2
Université Paris-Saclay, CentraleSupélec, Inria, France · LTCI, Télécom Paris, Institut Polytechnique de Paris, France