Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914898979586048 |
|---|---|
| author | Yang, Guangrui Li, Jianfei Li, Ming Feng, Han Zhou, Ding-Xuan |
| author_facet | Yang, Guangrui Li, Jianfei Li, Ming Feng, Han Zhou, Ding-Xuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01281 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks Yang, Guangrui Li, Jianfei Li, Ming Feng, Han Zhou, Ding-Xuan Machine Learning Artificial Intelligence Functional Analysis 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. |
| title | Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks |
| topic | Machine Learning Artificial Intelligence Functional Analysis |
| url | https://arxiv.org/abs/2407.01281 |