Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks
Not on the map. Why?
Abstract (arXiv)
In this paper, we explore the approximation theory of functions defined on graphs. Our study builds upon the approximation results derived from the K-functional. We establish a theoretical framework to assess the lower bounds of approximation for target functions using Graph Convolutional Networks (GCNs) and examine the over-smoothing phenomenon commonly observed in these networks. Initially, we introduce the concept of a K-functional on graphs, establishing its equivalence to the modulus of smoothness. We then analyze a typical type of GCN to demonstrate how the high-frequency energy of the output decays, an indicator of over-smoothing. This analysis provides theoretical insights into the nature of over-smoothing within GCNs. Furthermore, we establish a lower bound for the approximation of target functions by GCNs, which is governed by the modulus of smoothness of these functions. This finding offers a new perspective on the approximation capabilities of GCNs. In our numerical experiments, we analyze several widely applied GCNs and observe the phenomenon of energy decay. These observations corroborate our theoretical results on exponential decay order.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 18 of its 32 references that are in the map. First posted on arXiv 1 Jul 2024.
Builds on
18 of 32 references.
References · 18
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
- 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
- 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
- 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
- 2018Deep Learning on Graphs: A Surveycited by 393
- 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
- 2020A Note on Over-Smoothing for Graph Neural Networkscited by 245
- 2022Graph-Coupled Oscillator Networkscited by 123
- 2020Towards Deeper Graph Neural Networks with Differentiable Group Normalizationcited by 113
- 2019A Gentle Introduction to Deep Learning for Graphscited by 107
- 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
6 more
- 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
- 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
- 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
- 2023Demystifying Oversmoothing in Attention-Based Graph Neural Networkscited by 47
- 2024How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashingcited by 24
- 2022Theoretical guarantees for the advantage of GNNs over NNs in generalizing bandlimited functions on Euclidean cubescited by 4
Built on by
Citing papers per year: 2024: 1.
1 paper.