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

Qin Jiang; Chengjia Wang; Michael Lones; Dongdong Chen; Wei Pang

cs.LGMar 19, 2026

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

Authors: Qin Jiang, Chengjia Wang, Michael Lones, Dongdong Chen, Wei Pang

Organizations: Department of Computer Science, University of Heriot-Watt, Edinburgh, UK

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.

Figures & tables

Figure 1: Graph Fourier transform and its inverse, showing spectral modulation by a diagonal filter in the Fourier domain.

MagNet ( $\alpha=2\pi q$ )
Edges	${{\bm{A}}}_{s}$	$\widetilde{{{\bm{A}}}_{s}}$	$\widehat{{{\bm{A}}}_{s}}$	$\Re(\widehat{{{\bm{A}}}_{s}})$	$\Im(\widehat{{{\bm{A}}}_{s}})$
${\bm{m}}\rightarrow{\bm{n}}$	$0.5$	$\frac{0.5}{d}$	$\frac{0.5}{d}e^{j\alpha}$	$\frac{0.5}{d}\cos\alpha$	$\frac{0.5}{d}\sin\alpha$
${\bm{n}}\rightarrow{\bm{m}}$	$0.5$	$\frac{0.5}{d}$	$\frac{0.5}{d}e^{-j\alpha}$	$\frac{0.5}{d}\cos\alpha$	$-\frac{0.5}{d}\sin\alpha$
${\bm{m}}\leftrightarrow{\bm{n}}$	$1$	$d^{-1}$	$d^{-1}$	$d^{-1}$	$0$
${\bm{m}}\not\leftrightarrow{\bm{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

{\bm{m}}

and node

{\bm{n}}

. Here,

{\bm{A}}_{s}

is the symmetrized adjacency matrix,

\widetilde{{{\bm{A}}}_{s}}

is its GCN-normalized adjacency matrix, and

\widehat{{{\bm{A}}}_{s}}

is the complex-valued adjacency matrix used in MagNet with parameter

\alpha=2\pi 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

L_{2}

normalisation.

Spectral Graph Convolution

Spectral graph convolution applies learned filters in the graph Laplacian or Fourier domain to model graph structure, signal frequencies, and long-range dependencies.

See all 22 papers

Full-Spectrum Graph Neural Networks: Expressive and Scalable
May 7, 2026Xiaohan Wang, Deyu Bo, Longlong Li +1Graph Neural Networks GNN Expressivity
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.
L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations
Feb 21, 2026Samuel Fernández-Menduiña, Eduardo Pavez, Antonio OrtegaSpectral Graph Convolution Graph Signal Processing
University of Southern California.
Generalization Bounds for Spectral GNNs via Fourier Domain Analysis
Apr 1, 2026Vahan A. Martirosyan, Daniele Malitesta, Hugues Talbot +2Generalization Bounds Neural Network Generalization
Université Paris-Saclay, CentraleSupélec, Inria, France · LTCI, Télécom Paris, Institut Polytechnique de Paris, France

May 7, 2026J/K move · Enter open · S save

Full-Spectrum Graph Neural Networks: Expressive and Scalable

Xiaohan Wang, Deyu Bo, Longlong Li, Kelin Xia

Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore.

Graph Neural Networks GNN Expressivity Spectral Methods Higher-Order GNNs Spectral Graph Convolution

Open paper AskPDF arXiv

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.

Abstract

Spectral Graph Convolution

Explore similar work

Full-Spectrum Graph Neural Networks: Expressive and Scalable

L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations

Generalization Bounds for Spectral GNNs via Fourier Domain Analysis