Scalable Graph Curvature: Bounding Ollivier-Ricci via Local Combinatorics for Geometric Deep Learning
Giorgio Micaletto and Tebe Nigrelli
In NeurIPS 2026 Workshop on Graph Distributional Deep Learning. The extended version is on arXiv as Edgewise Envelopes Between Balanced Forman and Ollivier-Ricci Curvature , 2026
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 the OR curvature of each edge, parameterized by 2-hop local graph combinatorics, reducing the edgewise evaluation complexity from an optimal transport linear program to a worst-case time of order the maximum degree to the power 2.5, 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.
@inproceedings{micaletto2026scalable,title={Scalable Graph Curvature: Bounding Ollivier-Ricci via Local Combinatorics for Geometric Deep Learning},author={Micaletto, Giorgio and Nigrelli, Tebe},booktitle={NeurIPS 2026 Workshop on Graph Distributional Deep Learning},year={2026},}
In Bayesian statistics, the marginal likelihood is used for model selection and averaging, yet it is often challenging to compute accurately for complex models. Approaches such as bridge sampling, while effective, suffer from high variance when the proposal distribution overlaps poorly with the target posterior. To quantify this variance, we present a closed-form Monte Carlo standard error (MCSE) estimator for bridge sampling, extending classical variance approximations with a multi-chain effective-sample-size correction for autocorrelated MCMC draws and an exact log-scale variance. We show that the MCSE estimate itself is structurally capped at about 1.05, so values near this cap signal saturation rather than precision, and our calibration experiments show that the MCSE can be trusted when it is below 0.3. Furthermore, we introduce a hybrid score-matching proposal that regularizes the sample covariance using the local posterior geometry, significantly improving the stability of the estimator, and we demonstrate the efficacy of these methods using increasingly difficult simulated posteriors and real posteriors from the posteriordb database.
@article{micaletto2025bridge,title={Bridge Sampling Diagnostics},author={Micaletto, Giorgio and Vehtari, Aki},journal={arXiv preprint arXiv:2508.14487},year={2025},}
