Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance, captures rich geometric information and has garnered increasing attention in both theory and applications. However, the high computational cost of evaluating Wasserstein distance has significantly limited the broader practical use of ORC. To address this issue, previous work introduced a computationally efficient lower bound based on 1-hop random walks as a proxy for ORC, yet this approach has empirically shown large gaps from the exact ORC.
In this paper, we establish a substantially tighter lower bound for ORC than the existing one, while maintaining a much lower computational cost than exact ORC computation, achieving practical speedups of tens of times. Furthermore, our bound is not restricted to 1-hop random walks but also applies to k-hop random walks (k ≥ 1). Experiments on several fundamental graph structures demonstrate the effectiveness of our bound in terms of approximation accuracy and computational efficiency.
Blogger's Review: This research addresses the computational bottleneck of Ollivier-Ricci curvature with an effective solution, introducing a lower bound that not only enhances computational efficiency but also broadens applicability, showcasing significant potential in graph theory applications worth noting!