Full-Spectrum Graph Neural Network: Expressive and Scalable

• URL: http://arxiv.org/abs/2605.05759v1
• Date: Thu, 07 May 2026 06:53:49 GMT
• Title: Full-Spectrum Graph Neural Network: Expressive and Scalable
• Abstract summary: spectral graph neural networks (GNNs) can universally approximate node signals.<n>We propose the Full-Spectrum GNN (FSpecGNN), a second-order generalization of classical spectral GNNs.<n> Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.
• Score: 47.228678765460735
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is well established that spectral graph neural networks (GNNs) can universally approximate node signals; however, their expressive power remains bounded by the 1-dimensional Weisfeiler-Lehman test, which is mirrored in their lack of universality for higher-order signals. To go beyond this bound, we propose the Full-Spectrum GNN (FSpecGNN), a second-order generalization of classical spectral GNNs. FSpecGNN advances spectral filtering in two perspectives: (1) it lifts the signal from the node domain to the node-pair domain; and (2) it extends the univariate spectral filter over eigenvalues to a bivariate filter over eigenvalue pairs. We show that classical spectral GNNs arise as a diagonal special case of FSpecGNN, and prove that FSpecGNN can be at most as expressive as Local 2-GNN while universally approximating node-pair signals, the latter being particularly beneficial for heterophilic graph learning. Moreover, FSpecGNN admits scalable implementations that avoid explicit node-pair-level computations; combined with a low-rank approximation that reduces full-spectrum convolution to a combination of polynomial spectral filters, it enables learning on large graphs. Empirically, FSpecGNN validates the predicted expressivity and delivers strong performance on heterophilic benchmarks.

Related papers

• L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations [31.210700220124192]
  We propose a new class of spectral graph neural networks (GNNs) based on a factorization of the graph Fourier transform (GFT)<n>We show that L2G-Net outperforms existing spectral techniques and is competitive with the state-of-the-art with orders of magnitude fewer learnable parameters.
  arXiv  Detail & Related papers  (2026-02-21T13:53:36Z)
• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum [17.27380476408333]
  Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power.<n>We propose a method to provably improve SGNNs' expressivity on simple spectrum graphs.
  arXiv  Detail & Related papers  (2025-06-05T19:26:29Z)
• 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 Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain.<n>We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• 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)
• 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)
• Node-oriented Spectral Filtering for Graph Neural Networks [38.0315325181726]
  Graph neural networks (GNNs) have shown remarkable performance on homophilic graph data. In general, learning a universal spectral filter on the graph from the global perspective may still suffer from great difficulty in adapting to the variation of local patterns. We propose the node-oriented spectral filtering for graph neural network (namely NFGNN)
  arXiv  Detail & Related papers  (2022-12-07T14:15:28Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  Spectral Graph Neural Network is a kind of Graph Neural Network based on graph signal filters. We first prove that even spectral GNNs without nonlinearity can produce arbitrary graph signals. We also establish a connection between the expressive power of spectral GNNs and Graph Isomorphism (GI) testing.
  arXiv  Detail & Related papers  (2022-05-23T10:22:12Z)

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.