Generalization Bounds for Spectral GNNs via Fourier Domain Analysis
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Manifold Perspective on the Statistical Generalization of Graph Neural Networks
Graph Neural Networks (GNNs) extend convolutional neural networks to operate on graphs. Despite their impressive performances in various graph learning tasks, the theoretical understanding of their generalization capabil…
Generalization BoundsGraph LearningPosition: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification
Spectral Graph Neural Networks (Spectral GNNs) for node classification promise frequency-domain filtering on graphs, yet rest on flawed foundations. Recent work shows that graph Laplacian eigenvectors do not in general h…
Node ClassificationPAC-Bayesian Adversarially Robust Generalization Bounds for Graph Neural Network
Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversaria…
Generalization BoundsGraph Neural NetworkA PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
In this paper, we derive generalization bounds for the two primary classes of graph neural networks (GNNs), namely graph convolutional networks (GCNs) and message passing GNNs (MPGNNs), via a PAC-Bayesian approach. Our r…
Generalization BoundsTopology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks
Graph neural networks have demonstrated excellent applicability to a wide range of domains, including social networks, biological systems, recommendation systems, and wireless communications. Yet a principled theoretical…
Stochastic OptimizationRecommendation SystemsGraph Classification