Generalization Bounds for Spectral GNNs via Fourier Domain Analysis

• URL: http://arxiv.org/abs/2604.00918v1
• Date: Wed, 01 Apr 2026 13:58:50 GMT
• Title: Generalization Bounds for Spectral GNNs via Fourier Domain Analysis
• Abstract summary: Spectral graph networks learn graph filters, but their behavior with increasing depth and neural order is not well understood.<n>We analyze these models in the graph domain, where each layer becomes an element-wise frequency update.
• Score: 13.038956023769996
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
  arXiv  Detail & Related papers  (2026-06-25T18:25:57Z)
• Data-Driven Graph Filters via Adaptive Spectral Shaping [10.449640808601199]
  We introduce Adaptive Spectral Shaping, a data-driven framework for graph filtering.<n>The framework provides compact spectral modules that plug into graph signal processing pipelines and graph neural networks.
  arXiv  Detail & Related papers  (2026-02-03T16:20:49Z)
• Piecewise Constant Spectral Graph Neural Network [5.048196692772085]
  Graph Neural Networks (GNNs) have achieved significant success across various domains by leveraging graph structures in data.<n>Existing spectral GNNs, which use low-degree filters to capture spectral properties, may not fully identify the graph's spectral characteristics because of small degree.<n>We introduce the Constant Piecewise Spectral Graph Neural Network(PieCoN) to address these challenges.
  arXiv  Detail & Related papers  (2025-05-07T21:17:06Z)
• GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
  Graph State Space Network (GrassNet) is a novel graph neural network with theoretical support that provides a simple yet effective scheme for designing arbitrary graph spectral filters. To the best of our knowledge, our work is the first to employ SSMs for the design of graph GNN spectral filters. Extensive experiments on nine public benchmarks reveal that GrassNet achieves superior performance in real-world graph modeling tasks.
  arXiv  Detail & Related papers  (2024-08-16T07:33:58Z)
• A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition [41.41593198072709]
  We present a novel wavelet-based graph convolution network, namely WaveGC, which integrates multi-resolution spectral bases and a matrix-valued filter kernel.<n>Theoretically, we establish that WaveGC can effectively capture and decouple short-range and long-range information, providing superior filtering flexibility.<n>Our numerical experiments showcase the consistent improvements in both short-range and long-range tasks.
  arXiv  Detail & Related papers  (2024-05-22T16:32:27Z)
• Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
  This paper proposes Advective Diffusion Transformer (AdvDIFFormer), a physics-inspired graph Transformer model designed to address this challenge.<n>We show that AdvDIFFormer has provable capability for controlling generalization error with topological shifts.<n> Empirically, the model demonstrates superiority in various predictive tasks across information networks, molecular screening and protein interactions.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  Conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs. Here we show this traditional reliance on the graph Fourier transform to be superfluous. We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based.
  arXiv  Detail & Related papers  (2023-10-03T17:42:09Z)
• Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs [122.06927400759021]
  We study the relationship between a graph neural network (GNN) and a manifold neural network (MNN) when the graph is constructed from a set of points sampled from the manifold. We prove non-asymptotic error bounds showing that convolutional filters and neural networks on these graphs converge to convolutional filters and neural networks on the continuous manifold.
  arXiv  Detail & Related papers  (2023-05-29T08:27:17Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  Spectral graph neural networks (GNNs) learn graph representations via spectral-domain graph convolutions. We introduce Specformer, which effectively encodes the set of all eigenvalues and performs self-attention in the spectral domain. By stacking multiple Specformer layers, one can build a powerful spectral GNN.
  arXiv  Detail & Related papers  (2023-03-02T07:36:23Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Fourier-based and Rational Graph Filters for Spectral Processing [0.0]
  Our overall goal is the definition of novel Fourier-based filters for graph processing. For efficient evaluation of discrete spectral-based and wavelet operators, we introduce a spectrum-free approach. Approximating arbitrary graph filters with rationals provides a more accurate and numerically stable alternative with respect to sparses.
  arXiv  Detail & Related papers  (2020-11-08T19:02:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.