Search papers, labs, and topics across Lattice.
This paper analyzes spectral graph neural networks (GNNs) in the graph Fourier domain, treating each layer as an element-wise frequency update to explicitly model depth and polynomial order. By proving the invariance of Gaussian complexity under the Graph Fourier Transform, the authors derive data-dependent generalization bounds that account for depth and polynomial order, along with stability estimates. Empirically, the data-dependent term in the linear case correlates with the generalization gap, suggesting practical choices for avoiding frequency amplification.
Spectral GNNs' generalization ability hinges on avoiding frequency amplification, and this paper provides a Fourier-domain lens to see it clearly.
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.
