Scalable Graph Curvature: Bounding Ollivier-Ricci via Local Combinatorics for Geometric Deep Learning

Evaluating Ollivier-Ricci (OR) curvature on large-scale graphs is bottlenecked by the need to solve an optimal transport problem per edge. This limits the scalability of geometry-aware Graph Neural Networks, where the sign of OR curvature is actively used to mitigate oversmoothing and over-squashing. We bypass this computational barrier by deriving explicit, two-sided, piecewise-affine transfer moduli between OR and Balanced Forman (BF) curvature. This reduces edgewise evaluation from a linear program to worst-case $\mathcal{O}(\max_{v \in V} \deg(v)^{1.5})$ time, eliminating reliance on global solvers. Scalability benchmarks and validations across synthetic and empirical networks show that our approach yields significant runtime speedups while ensuring these analytical bands enclose empirical distributions regardless of graph geometry or clustering, enabling highly scalable curvature-based rewiring.