Spectral Graph Learning: Origins and Theoretical Limitations

Recent work has questioned both the theoretical foundations and empirical effectiveness of spectral graph neural networks (Spectral GNNs). This paper examines two aspects of the spectral graph learning paradigm. First, we review the scope and limitations of classical spectral graph theory, highlighting its emphasis on graph structure, extremal spectral quantities, and a narrow set of special graph families. Second, we trace the historical development of the Graph Fourier Transform (GFT), a key concept underlying Spectral GNNs. We identify three successive conceptual generalisations and show how concepts from Fourier and harmonic analysis were transferred to settings that lack the mathematical structures from which they originally derive their meaning. This perspective clarifies both the limitations inherited from spectral graph theory and the conceptual foundations on which Spectral GNNs were later built.