Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature
This work addresses fundamental limitations in GNNs for modeling complex graph interactions, providing a unified theoretical framework and practical solution.
The study tackled the problems of over-smoothing and over-squashing in Graph Neural Networks by linking them to local graph geometry using Ollivier-Ricci curvature, and proposed a novel rewiring algorithm to address both issues.
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.