aiqbench analysis
This research addresses a critical computational bottleneck in geometric deep learning by establishing efficient transfer moduli between Ollivier-Ricci and Balanced Forman curvature metrics. By replacing expensive global optimal transport solvers with local combinatorial bounds, the method enables scalable statistical network analysis on large-scale graphs without sacrificing theoretical rigor. This advancement directly facilitates the practical application of spectral graph theory in training deep learning models on massive datasets.
Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature
arXiv:2603.13535v5 Announce Type: cross 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.
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.
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
Computation (stat.CO); Discrete Mathematics (cs.DM); Machine Learning (cs.LG); Combinatorics (math.CO); Differential Geometry (math.DG)
arXiv:2603.13535 [stat.CO]
(or arXiv:2603.13535v5 [stat.CO] for this version)
Full text under the publisher's open licence · 205 words
Related coverage
Discrete Ricci Curvature on Protein Contact Graphs for Lightweight Fold Classification
arXiv · Jul 21, 2026
Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature
arXiv · Jul 27, 2026
Ollivier-Ricci Curvature of Riemannian Manifolds and Directed Graphs with Applications to Graph Neural Networks
arXiv · Aug 27, 2026
Geometric Flow enhanced Graph Coarsening
arXiv · Sep 16, 2026