Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature

Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, Tan Minh Nguyen
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:25956-25979, 2023.

Abstract

Graph Neural Networks (GNNs) had been demonstrated to be inherently susceptible to the problems of over-smoothing and over-squashing. These issues prohibit the ability of GNNs to model complex graph interactions by limiting their effectiveness in taking into account distant information. Our study reveals the key connection between the local graph geometry and the occurrence of both of these issues, thereby providing a unified framework for studying them at a local scale using the Ollivier-Ricci curvature. Specifically, we demonstrate that over-smoothing is linked to positive graph curvature while over-squashing is linked to negative graph curvature. Based on our theory, we propose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable of simultaneously addressing both over-smoothing and over-squashing.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-nguyen23c, title = {Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature}, author = {Nguyen, Khang and Hieu, Nong Minh and Nguyen, Vinh Duc and Ho, Nhat and Osher, Stanley and Nguyen, Tan Minh}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {25956--25979}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/nguyen23c/nguyen23c.pdf}, url = {https://proceedings.mlr.press/v202/nguyen23c.html}, abstract = {Graph Neural Networks (GNNs) had been demonstrated to be inherently susceptible to the problems of over-smoothing and over-squashing. These issues prohibit the ability of GNNs to model complex graph interactions by limiting their effectiveness in taking into account distant information. Our study reveals the key connection between the local graph geometry and the occurrence of both of these issues, thereby providing a unified framework for studying them at a local scale using the Ollivier-Ricci curvature. Specifically, we demonstrate that over-smoothing is linked to positive graph curvature while over-squashing is linked to negative graph curvature. Based on our theory, we propose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable of simultaneously addressing both over-smoothing and over-squashing.} }
Endnote
%0 Conference Paper %T Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature %A Khang Nguyen %A Nong Minh Hieu %A Vinh Duc Nguyen %A Nhat Ho %A Stanley Osher %A Tan Minh Nguyen %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-nguyen23c %I PMLR %P 25956--25979 %U https://proceedings.mlr.press/v202/nguyen23c.html %V 202 %X Graph Neural Networks (GNNs) had been demonstrated to be inherently susceptible to the problems of over-smoothing and over-squashing. These issues prohibit the ability of GNNs to model complex graph interactions by limiting their effectiveness in taking into account distant information. Our study reveals the key connection between the local graph geometry and the occurrence of both of these issues, thereby providing a unified framework for studying them at a local scale using the Ollivier-Ricci curvature. Specifically, we demonstrate that over-smoothing is linked to positive graph curvature while over-squashing is linked to negative graph curvature. Based on our theory, we propose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable of simultaneously addressing both over-smoothing and over-squashing.
APA
Nguyen, K., Hieu, N.M., Nguyen, V.D., Ho, N., Osher, S. & Nguyen, T.M.. (2023). Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:25956-25979 Available from https://proceedings.mlr.press/v202/nguyen23c.html.

Related Material