mlsanityData to 7 Oct 2026

FoSR: First-order spectral rewiring for addressing oversquashing in GNNs

arXiv 2210.11790 ↗First posted 21 Oct 2022cs.LG stat.MLcited by 104

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. While this allows GNNs to learn features depending on the graph structure, for certain graph topologies it leads to inefficient information propagation and a problem known as oversquashing. This has recently been linked with the curvature and spectral gap of the graph. On the other hand, adding edges to the message-passing graph can lead to increasingly similar node representations and a problem known as oversmoothing. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges to the graph based on spectral expansion. We combine this with a relational architecture, which lets the GNN preserve the original graph structure and provably prevents oversmoothing. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.

Key facts. Cited by 104 papers in the map (data through 7 Oct 2026). Builds on 30 of its 48 references that are in the map. First posted on arXiv 21 Oct 2022.

Builds on

30 of 48 references.

References · 30

  1. 2017Attention Is All You Needcited by 59,932
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2017Inductive Representation Learning on Large Graphscited by 6,284
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  10. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  11. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  12. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
18 more
  1. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  2. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  3. 2015Gated Graph Sequence Neural Networkscited by 792
  4. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  5. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  6. 2020A Generalization of Transformer Networks to Graphscited by 653
  7. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  8. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  9. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  10. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  11. 2019Diffusion Improves Graph Learningcited by 414
  12. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  13. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
  14. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  15. 2019GNN-FiLM: Graph Neural Networks with Feature-wise Linear Modulationcited by 75
  16. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  17. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 35
  18. 2022Rewiring Networks for Graph Neural Network Training Using Discrete Geometrycited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 16; 2024: 23; 2025: 37; 2026: 26.

104 papers.

Sort:

  1. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  2. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 96
  3. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  4. 2022On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networkscited by 63
  5. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  6. 2023How does over-squashing affect the power of GNNs?cited by 53
  7. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  8. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  9. 2023Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvaturecited by 39
  10. 2023Cooperative Graph Neural Networkscited by 35
  11. 2024VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connectionscited by 34
  12. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
38 more
  1. 2024On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systemscited by 26
  2. 2024How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashingcited by 24
  3. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  4. 2023Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreachingcited by 23
  5. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 23
  6. 2023Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challengescited by 22
  7. 2024Cayley Graph Propagationcited by 21
  8. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  9. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  10. 2023Effective Structural Encodings via Local Curvature Profilescited by 13
  11. 2025GNNs Getting ComFy: Community and Feature Similarity Guided Rewiringcited by 13
  12. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  13. 2024The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisitedcited by 11
  14. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 11
  15. 2024Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awarenesscited by 10
  16. 2024PANDA: Expanded Width-Aware Message Passing Beyond Rewiringcited by 10
  17. 2025Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modelingcited by 9
  18. 2025On Measuring Long-Range Interactions in Graph Neural Networkscited by 9
  19. 2024Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 8
  20. 2025Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvaturecited by 8
  21. 2024Layer-diverse Negative Sampling for Graph Neural Networkscited by 7
  22. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 7
  23. 2023The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structurecited by 6
  24. 2024Design Your Own Universe: A Physics-Informed Agnostic Method for Enhancing Graph Neural Networkscited by 6
  25. 2025Over-squashing in Spatiotemporal Graph Neural Networkscited by 6
  26. 2025Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Modelscited by 6
  27. 2024Graph Unitary Message Passingcited by 5
  28. 2024A Cosmic-Scale Benchmark for Symmetry-Preserving Data Processingcited by 5
  29. 2025PIORF: Physics-Informed Ollivier-Ricci Flow for Long-Range Interactions in Mesh Graph Neural Networkscited by 5
  30. 2023Higher-Order Expander Graph Propagationcited by 4
  31. 2024Deep Equilibrium Algorithmic Reasoningcited by 4
  32. 2025Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networkscited by 4
  33. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  34. 2025Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNscited by 3
  35. 2024Differentiable Cluster Graph Neural Networkcited by 2
  36. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  37. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2
  38. 2025Influence Functions for Edge Edits in Non-Convex Graph Neural Networkscited by 2

50 most cited of 104 All 104 (JSON)