Generalization Bounds for Spectral GNNs via Fourier Domain Analysis

Vahan A. Martirosyan; Daniele Malitesta; Hugues Talbot; Jhony H. Giraldo; Fragkiskos D. Malliaros

cs.LGApr 1, 2026

Generalization Bounds for Spectral GNNs via Fourier Domain Analysis

Authors: Vahan A. Martirosyan, Daniele Malitesta, Hugues Talbot, Jhony H. Giraldo, Fragkiskos D. Malliaros

Organizations: Université Paris-Saclay, CentraleSupélec, Inria, France · LTCI, Télécom Paris, Institut Polytechnique de Paris, France

Abstract

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.

Figures & tables

Figure 1: Basis stability across the spectrum (

K=10

	Chameleon			Squirrel			Cora			Citeseer
Basis	Base	+Reg	$\Delta$	Base	+Reg	$\Delta$	Base	+Reg	$\Delta$	Base	+Reg	$\Delta$
Monomial	$43.68\pm 2.0$	$44.28\pm 1.2$	$+0.60\uparrow$	$27.87\pm 1.2$	$26.76\pm 0.8$	$-1.11^{*}\downarrow$	$78.33\pm 1.4$	$75.34\pm 1.5$	$-2.99^{***}\downarrow$	$66.15\pm 1.9$	$64.30\pm 2.5$	$-1.85\downarrow$
Legendre	$41.22\pm 1.8$	$42.74\pm 1.9$	$+1.52\uparrow$	$26.32\pm 1.7$	$29.15\pm 1.0$	$+2.83^{***}\uparrow$	$79.53\pm 1.4$	$79.36\pm 1.4$	$-0.17\downarrow$	$65.35\pm 1.7$	$66.77\pm 2.0$	$+1.42\uparrow$
Bernstein	$40.58\pm 1.8$	$42.23\pm 1.9$	$+1.65^{*}\uparrow$	$26.44\pm 0.6$	$31.23\pm 0.9$	$+4.79^{***}\uparrow$	$78.45\pm 2.0$	$79.08\pm 1.7$	$+0.63\uparrow$	$65.47\pm 2.0$	$65.30\pm 2.0$	$-0.17\downarrow$
Chebyshev	$41.76\pm 1.7$	$43.29\pm 1.9$	$+1.53\uparrow$	$27.89\pm 0.8$	$31.20\pm 0.7$	$+3.31^{***}\uparrow$	$77.64\pm 2.0$	$78.23\pm 2.1$	$+0.59\uparrow$	$65.57\pm 1.6$	$65.88\pm 1.6$	$+0.31\uparrow$

Table 1: Test accuracy improvement depends on basis stability. The column

\Delta

uses empirically calculated

\rho

for paired significance (

{}^{*}p<0.05,^{**}p<0.01,^{***}p<0.001

). While other bases occasionally degrade performance (negative

\Delta

), a consistent positive improvement is observed across all datasets only for the Chebyshev basis.

	Chameleon			Squirrel			Cora			Citeseer
Basis	Base	+Reg	$\Delta$	Base	+Reg	$\Delta$	Base	+Reg	$\Delta$	Base	+Reg	$\Delta$
Monomial	$4.93\pm 0.97$	$1.99\pm 0.17$	$-2.94^{***}\downarrow$	$4.21\pm 1.43$	$0.89\pm 0.3$	$-3.32^{***}\downarrow$	$0.75\pm 0.06$	$0.63\pm 0.04$	$-0.12^{***}\downarrow$	$1.02\pm 0.04$	$1.02\pm 0.05$	$+0.00$
Legendre	$4.72\pm 1.1$	$2.23\pm 0.35$	$-2.49^{***}\downarrow$	$2.04\pm 0.66$	$1.79\pm 0.07$	$-0.25\downarrow$	$0.65\pm 0.06$	$0.49\pm 0.04$	$-0.16^{***}\downarrow$	$0.83\pm 0.06$	$0.90\pm 0.03$	$+0.07^{**}\uparrow$
Bernstein	$2.14\pm 0.3$	$3.46\pm 1.38$	$+1.32^{*}\uparrow$	$2.44\pm 0.55$	$0.29\pm 0.18$	$-2.15^{***}\downarrow$	$0.64\pm 0.06$	$0.54\pm 0.04$	$-0.10^{***}\downarrow$	$1.00\pm 0.05$	$0.99\pm 0.03$	$-0.01\downarrow$
Chebyshev	$3.06\pm 1.0$	$2.20\pm 0.17$	$-0.86\downarrow$	$2.77\pm 0.31$	$0.09\pm 0.09$	$-2.68^{***}\downarrow$	$0.79\pm 0.07$	$0.69\pm 0.06$	$-0.10^{**}\downarrow$	$0.99\pm 0.02$	$0.92\pm 0.06$	$-0.07^{*}\downarrow$

Table 2: The regularizer’s effect on the generalization gap. Column

\Delta

shows the change, where a negative value indicates a reduction in the gap (

{}^{*}p<0.05,^{**}p<0.01,^{***}p<0.001

). The gap reduction is most consistent and significant on the Chebyshev basis.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Jacobian bound tightness.

Panel of Figure 8 — Figure 8: Comparison of generalization bounds.

Generalization Bounds

Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.

See all 154 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.
Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification
Mar 19, 2026Qin Jiang, Chengjia Wang, Michael Lones +2Spectral Graph Convolution Node Classification
Department of Computer Science, University of Heriot-Watt, Edinburgh, UK
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.

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

Generalization Bounds

Explore similar work

Full-Spectrum Graph Neural Networks: Expressive and Scalable

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

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