[2604.00918] Generalization Bounds for Spectral GNNs via Fourier Domain Analysis

Computer Science > Machine Learning arXiv:2604.00918 (cs) [Submitted on 1 Apr 2026] Title:Generalization Bounds for Spectral GNNs via Fourier Domain Analysis Authors:Vahan A. Martirosyan, Daniele Malitesta, Hugues Talbot, Jhony H. Giraldo, Fragkiskos D. Malliaros View a PDF of the paper titled Generalization Bounds for Spectral GNNs via Fourier Domain Analysis, by Vahan A. Martirosyan and 4 other authors View PDF HTML (experimental) 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. Comments: Subjects: Machine Learning (cs.LG) Cite as: arXiv:2604.00918 [cs.LG]   (or arXiv:2604.00918v1 [cs.LG] for this version)   https://doi.org/10.48550/arXiv.2604.00918 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submissi...