提出更精确的曲率下界计算方法，大幅提速且适用更广
A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature
- 基于残差壳结构构建新下界，突破传统1跳随机游走限制
- 相比现有方法，近似精度显著提升，计算速度提升数十倍
- 适用于多跳随机游走，适合大规模图数据曲率分析
Ollivier-Ricci曲率（ORC）通过Wasserstein距离刻画丰富的几何信息，在理论与应用中日益受到关注。然而，Wasserstein距离的高计算成本严重限制了ORC的广泛应用。此前工作提出基于1跳随机游走的高效下界作为近似，但其与真实曲率存在较大差距。本文建立了一个比现有方法更紧的下界，计算代价远低于精确计算，实际速度提升数十倍。该方法不仅适用于1跳随机游走，还可推广至k跳随机游走（k > 1）。在多个基础图结构上的实验表明，该下界在近似精度和计算效率方面均表现出色。
原文摘要 · Abstract (English)
Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications. However, the high computational cost of Wasserstein distance evaluation has significantly limited the broader practical use of ORC. To alleviate this issue, previous work introduced a computationally efficient lower bound as a proxy for ORC based on 1-hop random walks, but this approach empirically exhibits large gaps from the exact ORC. In this paper, we establish a substantially tighter lower bound for ORC than the existing lower bound, while retaining much lower computational cost than exact ORC computation, with practical speedups of tens of times. Moreover, 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 both approximation accuracy and computational efficiency.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。