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

  • 2023-05-31 08:50:48
  • Khang Nguyen, Hieu Nong, Vinh Nguyen, Nhat Ho, Stanley Osher, Tan Nguyen
  • 0


Graph Neural Networks (GNNs) had been demonstrated to be inherentlysusceptible to the problems of over-smoothing and over-squashing. These issuesprohibit the ability of GNNs to model complex graph interactions by limitingtheir effectiveness in taking into account distant information. Our studyreveals the key connection between the local graph geometry and the occurrenceof both of these issues, thereby providing a unified framework for studyingthem at a local scale using the Ollivier-Ricci curvature. Specifically, wedemonstrate that over-smoothing is linked to positive graph curvature whileover-squashing is linked to negative graph curvature. Based on our theory, wepropose the Batch Ollivier-Ricci Flow, a novel rewiring algorithm capable ofsimultaneously addressing both over-smoothing and over-squashing.


Quick Read (beta)

loading the full paper ...