Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks
This provides theoretical insights into a known bottleneck in graph neural networks, which is incremental but clarifies the approximation limits and over-smoothing behavior for researchers in graph machine learning.
The paper tackles the over-smoothing problem in Graph Convolutional Networks (GCNs) by establishing a theoretical framework using the K-functional and modulus of smoothness, showing that the approximation lower bound for target functions is governed by this smoothness and observing exponential decay in high-frequency energy in numerical experiments.
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.