mlsanityData to 14 Oct 2026

Solving Oversmoothing in GNNs via Nonlocal Message Passing: Algebraic Smoothing and Depth Scalability

arXiv 2512.08475 ↗First posted 9 Dec 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

The relationship between Layer Normalization (LN) placement and the oversmoothing phenomenon remains underexplored. We identify a critical dilemma: Pre-LN architectures avoid oversmoothing but suffer from the curse of depth, while Post-LN architectures bypass the curse of depth but experience oversmoothing. To resolve this, we propose a new method based on Post-LN that induces algebraic smoothing, preventing oversmoothing without the curse of depth. Empirical results across five benchmarks demonstrate that our approach supports deeper networks (up to 256 layers) and improves performance, requiring no additional parameters. Key contributions: Theoretical Characterization: Analysis of LN dynamics and their impact on oversmoothing and the curse of depth. A Principled Solution: A parameter-efficient method that induces algebraic smoothing and avoids oversmoothing and the curse of depth. Empirical Validation: Extensive experiments showing the effectiveness of the method in deeper GNNs.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 29 of its 31 references that are in the map. First posted on arXiv 9 Dec 2025.

Builds on

29 of 31 references.

References · 29

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2019Simplifying Graph Convolutional Networkscited by 1,477
  5. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  6. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  7. 2020Simple and Deep Graph Convolutional Networkscited by 860
  8. 2019Graph Neural Networks for Social Recommendationcited by 714
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  11. 2021GRAND: Graph Neural Diffusioncited by 258
  12. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 249
17 more
  1. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
  2. 2023NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classificationcited by 210
  3. 2023Exphormer: Sparse Transformers for Graphscited by 170
  4. 2023A mathematical perspective on Transformerscited by 164
  5. 2022Graph-Coupled Oscillator Networkscited by 124
  6. 2024Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classificationcited by 85
  7. 2022Revisiting Over-smoothing in BERT from the Perspective of Graphcited by 72
  8. 2025The Curse of Depth in Large Language Modelscited by 62
  9. 2021Dissecting the Diffusion Process in Linear Graph Convolutional Networkscited by 58
  10. 2025Do Language Models Use Their Depth Efficiently?cited by 50
  11. 2022Gradient Gating for Deep Multi-Rate Learning on Graphscited by 49
  12. 2023Demystifying Oversmoothing in Attention-Based Graph Neural Networkscited by 49
  13. 2024Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNscited by 34
  14. 2025Transformers are Graph Neural Networkscited by 29
  15. 2021Motif Prediction with Graph Neural Networkscited by 18
  16. 2024Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FRONDcited by 17
  17. 2025Measuring Over-smoothing beyond Dirichlet energycited by 1

Built on by

Not cited yet.