Rethinking the Gold Standard: Why Discrete Curvature Fails to Fully Capture Over-squashing in GNNs?

As a topological invariant for discrete structures, discrete curvature has been widely adopted in the study of complex networks and graph neural networks. A prevailing viewpoint posits that edges with highly negative curvature will induce graph bottlenecks and the over-squashing phenomenon. In this paper, we critically re-examine this view and put forward our central claim: high negative curvature is a sufficient but not a necessary condition for over-squashing. We first construct a family of counterexamples demonstrating the failure of discrete curvature, where some edges are severely squashed, but the curvature still appears positive. Furthermore, extensive experiments demonstrate that the most commonly used discrete curvature measure --- Ollivier–Ricci curvature --- fails to detect as many as 30% 40% of over-squashed edges. To alleviate this limitation, we propose Weighted Augmented Forman-3 Curvature ($\mathsf{WAF3}$), which significantly improves the detection of over-squashed edges. Additionally, we develop a highly efficient approximation algorithm for $\mathsf{WAF3}$, enabling curvature computation on graphs with five million edges in only 23.6 seconds, which is 133.7 times faster than the existing algorithm with the lowest complexity for curvatures.