Ollivier-Ricci曲率（ORC）通过Wasserstein距离定义，捕捉了丰富的几何信息，近年来在理论和应用方面受到越来越多的关注。然而，Wasserstein距离计算的高成本显著限制了ORC的广泛实际应用。为了缓解这一问题，之前的工作引入了一种基于1步随机游走的计算效率较高的下界作为ORC的代理，但该方法在经验上与精确ORC存在较大差距。
在本文中，我们建立了一个比现有下界更为紧凑的ORC下界，同时保持了远低于精确ORC计算的计算成本，实际加速效果可达数十倍。此外，我们的下界不仅限于1步随机游走，还适用于k步随机游走（k ≥ 1）。在多个基本图结构上的实验表明，我们的下界在近似准确性和计算效率方面均表现出色。
博主点评： 这项研究针对Ollivier-Ricci曲率的计算瓶颈提出了有效解决方案，其引入的下界不仅提高了计算效率，还扩展了适用范围，显示出在图论应用中的巨大潜力，值得关注！