英文标题：Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature
作者：Giorgio Micaletto, Tebe Nigrelli
arXiv ID：2603.13535 | 分类：stat.CO | 发表：2026-09-13
许可：CC-BY
摘要 在大规模图上评估Ollivier-Ricci（OR）曲率在计算上是不可行的，因为需要对每条边求解一个最优传输问题。我们通过推导基于传输的OR曲率与组合式平衡Forman（BF）曲率之间显式的、双侧的、分段仿射的传递模量，绕过了这一瓶颈。我们建立了由2跳局部图组合结构参数化的{{PT_MATH_1}}的确定性界，{{NL}}将逐边评估复杂度从最优传输线性规划降低到最坏情况下的{{PT_MATH_2}}时间，完全消除了对全局求解器的依赖。{{NL}}经验可扩展性基准验证了这些理论保证，表明所提出的传递模量相对于精确OR评估的陡峭多项式缩放，产生了显著的渐近和常数因子加速。{{NL}}此外，这
Evaluating Ollivier-Ricci (OR) curvature on large-scale graphs is computationally prohibitive due to the necessity of solving an optimal transport problem for every edge. We bypass this bottleneck by deriving explicit, two-sided, piecewise-affine transfer moduli between the transport-based OR curvature and the combinatorial Balanced Forman (BF) curvature. We establish deterministic bounds for $\mathfrak{c}_{\rm OR}(i,j)$ parameterized by 2-hop local graph combinatorics, reducing the edgewise evaluation complexity from an optimal transport linear program to a worst-case $\mathcal{O}\left(\max_{v \in V} \operatorname{deg}(v)^{2.5}\right)$ time, entirely eliminating the reliance on global solvers. Empirical scalability benchmarks confirm these theoretical guarantees, demonstrating that the proposed transfer moduli yield significant asymptotic and constant-factor speedups over the steep polynomial scaling of exact OR evaluation. Furthermore, the tightness of these bounds is validated via distributional analyses on canonical random graphs and empirical networks, with the derived analytical bands enclosing the empirical distributions independent of degree heterogeneity, geometry, or clustering, providing a scalable, computationally efficient framework for rigorous statistical network analysis.
查看完整双语翻译 →
正在跳转到翻译阅读页… 如果没有自动跳转，请点击这里。