Generalization Bounds for Spectral GNNs via Fourier Domain Analysis

Vahan A. Martirosyan, Daniele Malitesta, Hugues Talbot, Jhony H. Giraldo, Fragkiskos D. Malliaros
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:5095-5103, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-martirosyan26a, title = { Generalization Bounds for Spectral GNNs via Fourier Domain Analysis }, author = {Martirosyan, Vahan A. and Malitesta, Daniele and Talbot, Hugues and Giraldo, Jhony H. and Malliaros, Fragkiskos D.}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {5095--5103}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/martirosyan26a/martirosyan26a.pdf}, url = {https://proceedings.mlr.press/v300/martirosyan26a.html}, 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. } }
Endnote
%0 Conference Paper %T Generalization Bounds for Spectral GNNs via Fourier Domain Analysis %A Vahan A. Martirosyan %A Daniele Malitesta %A Hugues Talbot %A Jhony H. Giraldo %A Fragkiskos D. Malliaros %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-martirosyan26a %I PMLR %P 5095--5103 %U https://proceedings.mlr.press/v300/martirosyan26a.html %V 300 %X 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.
APA
Martirosyan, V.A., Malitesta, D., Talbot, H., Giraldo, J.H. & Malliaros, F.D.. (2026). Generalization Bounds for Spectral GNNs via Fourier Domain Analysis . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:5095-5103 Available from https://proceedings.mlr.press/v300/martirosyan26a.html.

Related Material