mlsanityData to 14 Oct 2026

Spatio-Spectral Graph Neural Networks

arXiv 2405.19121 ↗First posted 29 May 2024cs.LG cs.AIcited by 17

Not on the map. Why?

Abstract (arXiv)

Spatial Message Passing Graph Neural Networks (MPGNNs) are widely used for learning on graph-structured data. However, key limitations of l-step MPGNNs are that their "receptive field" is typically limited to the l-hop neighborhood of a node and that information exchange between distant nodes is limited by over-squashing. Motivated by these limitations, we propose Spatio-Spectral Graph Neural Networks (S2GNNs) -- a new modeling paradigm for Graph Neural Networks (GNNs) that synergistically combines spatially and spectrally parametrized graph filters. Parameterizing filters partially in the frequency domain enables global yet efficient information propagation. We show that S2GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs. Further, rethinking graph convolutions at a fundamental level unlocks new design spaces. For example, S2GNNs allow for free positional encodings that make them strictly more expressive than the 1-Weisfeiler-Lehman (WL) test. Moreover, to obtain general-purpose S2GNNs, we propose spectrally parametrized filters for directed graphs. S2GNNs outperform spatial MPGNNs, graph transformers, and graph rewirings, e.g., on the peptide long-range benchmark tasks, and are competitive with state-of-the-art sequence modeling. On a 40 GB GPU, S2GNNs scale to millions of nodes.

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 79 of its 103 references that are in the map. First posted on arXiv 29 May 2024.

Builds on

79 of 103 references.

References · 79

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  4. 2017Graph Attention Networkscited by 8,923
  5. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  6. 2023Mamba: Linear-Time Sequence Modeling with Selective State Spacescited by 4,718
  7. 2018How Powerful are Graph Neural Networks?cited by 4,393
  8. 2017MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applicationscited by 3,845
  9. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  10. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  11. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  12. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
38 more
  1. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  2. 2017Deep Setscited by 1,421
  3. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  4. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  5. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  6. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  8. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2020Benchmarking Graph Neural Networkscited by 680
  11. 2020A Generalization of Transformer Networks to Graphscited by 661
  12. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  13. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 629
  14. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  15. 2017SchNet: A continuous-filter convolutional neural network for modeling quantum interactionscited by 571
  16. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  17. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  18. 2019Self-Attention Graph Poolingcited by 421
  19. 2019Diffusion Improves Graph Learningcited by 414
  20. 2023Hyena Hierarchy: Towards Larger Convolutional Language Modelscited by 393
  21. 2017Residual Gated Graph ConvNetscited by 346
  22. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  23. 2022Long Range Graph Benchmarkcited by 263
  24. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  25. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  26. 2023Exphormer: Sparse Transformers for Graphscited by 170
  27. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  28. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  29. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  30. 2020Directional Graph Networkscited by 133
  31. 2019Stability Properties of Graph Neural Networkscited by 127
  32. 2021Global Self-Attention as a Replacement for Graph Convolutioncited by 114
  33. 2021MagNet: A Neural Network for Directed Graphscited by 107
  34. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 106
  35. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  36. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  37. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  38. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93

50 most cited of 79 All 79 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 10; 2026: 4.

17 papers.

Sort:

  1. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 43
  2. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 24
  3. 2024Benchmarking Positional Encodings for GNNs and Graph Transformerscited by 13
  4. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  5. 2025Can You Hear Me Now? A Benchmark for Long-Range Graph Propagationcited by 10
  6. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  7. 2025Recent Advances in Malware Detection: Graph Learning and Explainabilitycited by 7
  8. 2025Molecular Fingerprints Are Strong Models for Peptide Function Predictioncited by 5
  9. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  10. 2025Adaptive Canonicalization with Application to Invariant Anisotropic Geometric Networkscited by 3
  11. 2024Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariancecited by 2
  12. 2026Which Graph Shift Operator? A Spectral Answer to an Empirical Questioncited by 1
5 more
  1. 2025DRAN: A Distribution and Relation Adaptive Network for Spatio-temporal Forecastingcited by 0
  2. 2025Graph Neural Network-Based Multicast Routing for On-Demand Streaming Services in 6G Networkscited by 0
  3. 2026L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizationscited by 0
  4. 2026S3GNN: Efficient Global Mixing and Local Message Passing for Long-Range Graph Learningcited by 0
  5. 2026Learn When and Where to Connect: Adaptive Virtual Nodes for Dynamic Message Passing on Graphscited by 0