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

Qin Jiang, Chengjia Wang, Michael Lones, Dongdong Chen, Wei Pang · 2026

Read Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification by Qin Jiang, Chengjia Wang, Michael Lones, Dongdong Chen, Wei Pang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19091.txt.

Introduction

Jiang and co-authors argue that spectral graph networks for node labeling are neither spectral nor better. Such networks claim to filter graph signals in a frequency-like domain. The team names two flaws in that claim. Graph bases lack key traits of a true Fourier basis. High-degree polynomials can fit any response exactly, which voids the usual story. They prove that pass behavior in a common model stems from message passing, not spectral steps. Two directed models owe their scores to slips that turn them into message passers.

Catalog record

CREATORQin Jiang, Chengjia Wang, Michael Lones, Dongdong Chen, Wei Pang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44650
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19091

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification Qin Jiang, Chengjia Wang, Michael Lones, Dongdong Chen, Wei Pang 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 ) (n-1) -degree polynomials ( n 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. 1 Introduction Graph Neural Networks (GNNs) for node classification encompass several active research branches, such as Message Passing Neural Networks (MPNNs) ( 7 ; 27 ) and Spectral Graph Neural Networks (Spectral GNNs) ( 38 ; 14 ) . Spectral GNNs form a niche branch rooted in spectral graph theory ( 3 ) and polynomial approximation techniques ( 12 ) . However, their polynomial filters are problematic in that performance does not reliably improve as filter order K increases ( 14 ) . A recent position paper ( 9 ) further argues that graph Laplacian eigenvectors should not be treated as a canonical Fourier basis in the classical sense, thereby challenging the usual “spectral” interpretation. We agree with this conclusion. However, this limitation should not be attributed to a continuous-versus-discrete mismatch claimed by 9 : Fourier representations extend naturally to discrete settings via the DFT ( 25 ; 8 ) . Instead, the gap stems from structural differences between Euclidean domains and general graphs—most notably the absence of a global shift/translation operator—so the Laplacian eigenbasis lacks some of the canonical properties that underpin Fourier analysis in regular domains. We take a stronger stance: Spectral GNNs are theoretically flawed with several pitfalls, and their seemingly strong empirical performance stems primarily from equivalences to simpler MPNNs, rather than from any genuinely spectral mechanism. 1.1 Structure of this Position Paper Section 2 : We prove that Graph Fourier Basis \neq Fourier Basis of Graph, exposing our first theoretical concern. Section 3 : Even granting that graph Fourier bases qualify as true Fourier bases, polynomial approximations fail on their own terms. Following Spectral GNN reasoning, we show that on an n -node graph, an (n\!-\!1) th-order polynomial exactly interpolates any ideal spectral filter via a Vandermonde system, yielding a determined interpolation rather than a genuine approximation. Moreover, we point out that a k th-order polynomial exactly recovers k -hop message passing, explaining the effectiveness of Spectral GNNs as an equivalence to simpler MPNNs. Section 4 : We show that the commonly cited low-/high-pass behavior of GNN spectral filters can be justified via message passing; in contrast, a Graph Fourier Transform-based argument by itself cannot establish this filtering claim. Section 5 : We analyze two prominent Spectral GNNs for directed graphs—MagNet ( 38 ) and HoloNet ( 20 ) . Their strong empirical results stem not from spectral mechanisms, but from implementation bugs that reduce them to much simpler MPNNs. Scope and Terminology We focus on node classification, primarily on general graphs (with directed and undirected graphs as the special case where each edge is accompanied by its reverse). Let {\mathcal{G}}=({\mathbb{V}},\mathcal{E}) be a graph with n=\lvert{\mathbb{V}}\rvert nodes. Node features are stored in {\bm{X}}\in\mathbb{R}^{n\times f} , and node labels are y_{i}\in\{1,\ldots,c\} . The adjacency matrix is {\bm{A}}\in\{0,1\}^{n\times n} with {\bm{A}}_{ij}=1 indicating an edge i\to j . Let {\bm{D}} denote a degree matrix (specified as in-/out-degree when needed). For undirected graphs, the Laplacian is {\bm{L}}={\bm{D}}-{\bm{A}} , and the normalized Laplacian is \hat{{\bm{L}}}={\bm{I}}-{\bm{D}}^{-1/2}{\bm{A}}{\bm{D}}^{-1/2} . We use \hat{{\bm{A}}} to denote a normalized adjacency (defined in context). 2 Graph Fourier Basis 2.1 Background Spectral graph learning builds upon (i) Graph Fourier Basis as the conceptual foundation and (ii) polynomial approximations (e.g., Chebyshev, Bernstein) as a practical surrogate to avoid eigen-decomposition ( 9 ) . A Graph Fourier Transform (GFT) is typically defined through the eigen-decomposition of the normalized graph Laplacian \hat{\bm{L}}={\bm{I}}-\hat{{\bm{A}}} : \hat{\bm{L}}={\bm{U}}\bm{\Lambda}{\bm{U}}^{\top}, (1) where {\bm{U}} contains orthonormal eigenvectors and \bm{\Lambda} is diagonal. \hat{{\bm{A}}} is normalised adjacency matrix. 2.2 Graph Fourier Basis \neq Fourier Basis of Graph While {\bm{U}} indeed forms an orthonormal basis and defines a valid transform for the operator {\bm{L}} , identifying it as the graph’s own Fourier basis is conceptually misguided. The Fourier transform was originally developed for one-dimensional signals (e.g., vibrating strings and time sequences) ( 29 ) . Within Euclidean domains, the notion extends naturally to higher dimensions. For example, for images on \mathbb{Z}^{2} , the 2D Fourier transform represents an image as a superposition of sinusoidal patterns that vary along the horizontal and vertical directions of the grid ( 28 ; 8 ) . More fundamentally, Fourier modes in Euclidean settings arise as eigenfunctions (characters) of the translation group; consequently, “frequency” is tied to translation invariance and to sinusoidal patterns that are globally meaningful across the domain. On discrete domains the same principle holds: the discrete Fourier transform diagonalizes the action of cyclic shifts on \mathbb{Z}_{n} , and its modes are characters that represent globally meaningful oscillations on a regular grid ( 25 ) . For general graphs, however, there is no canonical notion of translation and no globally consistent set of orthogonal directions; thus, the classical semantics of frequency do not directly carry over ( 26 ) . Recent discussions further stress that the semantic properties that make Fourier analysis powerful in Euclidean settings may not be preserved when this terminology is transferred to arbitrary graphs ( 9 ) . Using Laplacian eigenvectors as the graph’s “Fourier basis” is analogous to the following construction in the image domain: rather than applying the standard 2D Fourier transform—whose modes are global sinusoids aligned with the horizontal and vertical directions—one instead diagonalizes a pixel-connectivity Laplacian and treats its eigenvectors as “spectral components.” This procedure indeed produces an orthonormal basis and defines a valid transform for that Laplacian. However, it is conceptually distinct from the classical Fourier basis, whose modes correspond to oscillations along the grid’s translation directions. Consequently, the resulting coefficients do not, in general, admit the classical interpretation of a “spectrum” tied to translation-invariant oscillations. This is a pitfall: Graph Fourier Basis \neq Fourier basis of graph. Recent work ( 9 ) reaches a similar conclusion but misattributes the issue to continuous-vs-discrete mismatch, overlooking the well-established Discrete Fourier Transform ( 25 ) . The real issue is that graphs generally

Read the complete text