arXiv：cs.LG· Giorgio Micaletto, Tebe Nigrelli·· 5 小时前
在 Balanced Forman 与 Ollivier-Ricci 曲率之间建立边缘包络
Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature
AI 导读
该论文推导出 Ollivier-Ricci（OR）曲率与组合式 Balanced Forman（BF）曲率之间的显式双侧分段仿射传递模量，将逐边曲率评估复杂度从最优传输线性规划降至最坏情况 O(max 度数的 2.5 次方)，完全摆脱对全局求解器的依赖。
正文
Abstract: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.
| Comments: | 38 pages, 4 figures. Accepted under the title 'Scalable Graph Curvature: Bounding Ollivier-Ricci via Local Combinatorics for Geometric Deep Learning' at the NeurIPS 2026 GDDL Workshop |
| Subjects: | Computation (stat.CO); Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Combinatorics (math.CO); Differential Geometry (math.DG) |
| MSC classes: | 05C82 (Primary) 05C12, 49Q22, 68R10 (Secondary) |
| ACM classes: | G.2.2; F.2.2 |
| Cite as: | arXiv:2603.13535 [stat.CO] |
| (or arXiv:2603.13535v5 [stat.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2603.13535 arXiv-issued DOI via DataCite |
Submission history
From: Giorgio Micaletto [view email]
[v1]
Fri, 13 Mar 2026 19:16:17 UTC (2,698 KB)
[v2]
Mon, 13 Apr 2026 22:27:39 UTC (2,696 KB)
[v3]
Tue, 25 Aug 2026 23:15:56 UTC (2,713 KB)
[v4]
Sun, 13 Sep 2026 21:55:22 UTC (2,240 KB)
[v5]
Wed, 30 Sep 2026 13:48:45 UTC (2,240 KB)
来源：arXiv：cs.LG · arxiv.org