cs.LGMar 13, 2026

Sobolev--Ricci Curvature

Authors: Kyoichi Iwasaki, Tam Le, Hideitsu Hino

Organizations: The Graduate University for Advanced Studies, SOKENDAI · The Institute of Statistical Mathematics

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Ricci curvature is a fundamental concept in differential geometry for encoding local geometric structure, and its graph-based analogues have recently gained prominence as practical tools for reweighting, pruning, and reshaping network geometry. We propose Sobolev-Ricci Curvature (SRC), a graph Ricci curvature canonically induced by Sobolev transport geometry, which admits efficient evaluation via a tree-metric Sobolev structure on neighborhood measures. We establish two consistency behaviors that anchor SRC to classical transport curvature: (i) on trees endowed with the length measure, SRC recovers Ollivier-Ricci curvature (ORC) in the canonical W1 setting, and (ii) SRC vanishes in the Dirac limit, matching the flat case of measure-theoretic Ricci curvature. We demonstrate SRC as a reusable curvature primitive in two representative pipelines. We define Sobolev-Ricci Flow by replacing ORC with SRC in a Ricci-flow-style reweighting rule, and we use SRC for curvature-guided edge pruning aimed at preserving manifold structure. Overall, SRC provides a transport-based foundation for scalable curvature-driven graph transformation and manifold-oriented pruning.

Figures & tables

Figure 1: Community detection performance (ARI) and computational cost under Ricci flow.
Figure 2: The bars show the percentage of shortcut edges correctly removed (red) and the percentage of good edges incorrectly removed (light blue). Representative results on two datasets.
Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Empirical root sensitivity of SRC(SPT) on SBM and LFR. For each dataset, we estimate Er,r′[∥Δκ∥1/∣Δ∣]\mathbb{E}_{r,r^{\prime}}[\|\Delta\kappa\|_{1}/|\Delta|] by sampling multiple root pairs (r,r′)(r,r^{\prime}) and averaging over repeated graph instances, where ∥Δκ∥1\|\Delta\kappa\|_{1} is the L1L^{1} difference of edge curvatures and ∣Δ∣=∣E(Tr)△E(Tr′)∣|\Delta|=|E(T_{r})\triangle E(T_{r^{\prime}})| is the number of tree edges that change. This quantity corresponds to the left-hand side of ( A.13 ) and measures the average curvature perturbation per changed tree edge.
Continuous geometry (Riemann/Finsler)Discrete Sobolev geometry (this paper)
Point x∈Mx\in MMeasure μ∈P(V)\mu\in\mathcal{P}(V)
Tangent space TxMT_{x}MTμP(V)={ξ∈RV  ;  ∑v∈Vξ(v)=0}(independent of μ).T_{\mu}\mathcal{P}(V)=\left\{\xi\in\mathbb{R}^{V}\;;\;\sum_{v\in V}\xi(v)=0\right\}\hskip 9.24994pt(\text{independent of }\mu).
Chart φ:U→Rd\varphi:U\to\mathbb{R}^{d}Cut-coordinate map Φz0:μ↦(μ(γe))e∈E\Phi_{z_{0}}:\mu\mapsto(\mu(\gamma_{e}))_{e\in E}
Riemannian metric ggp=2p=2 : weighted inner product ⟨a,b⟩λ=∑eλ(e)aebe\langle a,b\rangle_{\lambda}=\sum_{e}\lambda(e)a_{e}b_{e}
Finsler norm F(ξ)F(\xi)General pp : F(ξ)=∥dΦz0(ξ)∥ℓλpF(\xi)=\|d\Phi_{z_{0}}(\xi)\|_{\ell^{p}_{\lambda}}
Geodesic distanceSp(μ,ν)=∥Φz0(μ)−Φz0(ν)∥ℓλpS_{p}(\mu,\nu)=\|\Phi_{z_{0}}(\mu)-\Phi_{z_{0}}(\nu)\|_{\ell^{p}_{\lambda}}
Appendix
Table 1: Interpretative correspondence between continuous geometry and the discrete Sobolev geometry induced by an extracted tree.
ItemValue
Flow iterations TflowT_{\mathrm{flow}}2020 , early stop if Δκ(t)<ε\Delta\kappa^{(t)}<\varepsilon
Lazy RW parameter α\alpha0.50.5
ST exponent pp (SRC)11
Tree constructionMST / SPT
Root selection (SPT)00
Length-to-affinity β\beta1.01.0
Appendix
Table 2: Common hyperparameters used across community detection experiments for SRF.
Table 6
Figure 4: SRC(SPT) ablation on LFR: effect of the SRC exponent pp and downstream clustering. We evaluate p∈{1,1.5,2}p\in\{1,1.5,2\} using two downstream procedures: Louvain on similarity weights (left) and threshold-based length-cut clustering (right). Top panels show standard deviation of ARI across trials, and bottom panels show the mean ARI. Louvain yields stable performance with little dependence on pp , whereas length-cut is unstable and substantially degrades ARI.
Figure 5: Ablation on the lazy random walk parameter α\alpha on LFR ( 500500 nodes). We sweep α\alpha and plot the standard deviation (top row) and the mean (bottom row) of ARI over multiple random seeds as a function of the mixing parameter μ\mu . Left: SRC(SPT). Right: SRC(MST).
Figure 6: Sensitivity to α\alpha on real-world networks. Error bars indicate std over runs.
Figure 7: LFR benchmark: sensitivity to the length-to-weight temperature β\beta in w~xy=exp⁡(−βwxy)\tilde{w}_{xy}=\exp(-\beta w_{xy}) . Left: ARI (mean ±\pm std) of SRC(SPT)+Louvain after the SRF. Right: best Louvain resolution selected by grid search (mean ±\pm std). Performance is stable for moderate β\beta (0.01–2), while overly large β\beta (5,10) collapses weights and degrades modularity-based clustering.
Figure 8: Ricci curvature distributions for different mixing parameters μ\mu .
Figure 9: Robustness to tree construction. SRC distributions on the same LFR graphs computed using different extracted trees (SPT, MST, Random spanning tree). Across μ\mu , the global distributional shapes are similar, suggesting SRC mainly reflects coarse graph geometry rather than a specific tree optimality criterion.
Figure 10: Two-dimensional synthetic datasets employed in the edge pruning experiments. Each dataset consists of 4,000 data points. Red lines indicate shortcut edges, i.e., edges that do not follow the underlying manifold structure.
Figure 11: Three-dimensional synthetic datasets employed in the edge pruning experiments. Each dataset contains 4,000 data points. Red lines indicate shortcut edges, i.e., edges that deviate from the underlying manifold structure.
Figure 12: Bars indicate the percentage of shortcut edges correctly removed (red) and good edges incorrectly removed (light blue). While Distance-only and ORC pruning often fail, “SRC only” achieves reliable shortcut detection with fewer mistakes. With MANL, ORC and SRC(SPT) consistently succeed.
Figure 13: Illustrative example on the 3D_swiss_roll dataset, where we see in Fig. 10 . Distribution of curvature values, showing that SRC(SPT) tends to assign larger curvature values than ORC. This leads to more effective identification of shortcut edges in the first-stage filtering.
More in this topic

Optimal Transport

Optimal transport compares and transforms probability distributions by finding low-cost ways to move mass between them.

See all 289 papers

Explore similar work

CardsList
Apr 6, 2026

Ollivier-Ricci Curvature of Riemannian Manifolds and Directed Graphs with Applications to Graph Neural Networks

This thesis is an exposition of Ollivier-Ricci Curvature of metric spaces as introduced by Yann Ollivier, which is based upon the 1-Wasserstein Distance and optimal transport theory. We present some of the major results and proofs that connect Ollivier-Ricci curvature with classical Ricci curvature of Riemannian manifolds, including extensions of various theoretical bounds and theorems such as Bonnet-Myers and Levy-Gromov. Then we shift to results introduced by Lin-Lu-Yau on an extension of Ollivier-Ricci curvature on graphs, as well as the work of Jost-Liu on proving various combinatorial bounds for graph Ollivier-Ricci curvature. At the end of this thesis we present novel ideas and proofs regarding extensions of these results to directed graphs, and finally applications of graph-based Ollivier-Ricci curvature to various algorithms in network science and graph machine learning.

Eleanor P Wiesler

The Department of Mathematics Harvard University Cambridge, Massachusetts

Ollivier-Ricci CurvatureRiemannian Geometry
AskPDF
Jul 24, 2026

Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature

Curvature notions on graphs, particularly Ollivier-Ricci and Forman, have emerged as powerful tools for addressing fundamental issues in Graph Neural Networks (GNNs) such as oversmoothing and oversquashing, but rely almost exclusively on local edge-level comparisons and therefore fail to certify how information actually propagates over long distances. We introduce Entropic Curvature, a global, transport-based curvature obtained by extending the Lott-Sturm-Villani framework to graphs through the displacement convexity of entropy along Wasserstein geodesics. We define a tractable Weak Entropic Curvature proxy that lower-bounds the global entropic curvature, and from it derive (i) a Poincare-type inequality controlling oversmoothing, (ii) a transport-entropy generalization bound, and (iii) an expansion paradox proving that sparsity, strong spectral expansion, and positive entropic curvature cannot coexist in large graphs, unifying oversmoothing and oversquashing as opposite ends of a single curvature spectrum. We translate the theory into three practical mechanisms, the E-Gate aggregator, the ENT structural encoding, and Midpoint-Completion Rewiring (MCR), and benchmark them against SDRF, FoSR, BORF, LCP, and Graph Ricci Flow on six node-classification benchmarks, and graph-classification.

Rachid Caich, Yassine Abbahaddou

LIX, École Polytechnique IP Paris Palaiseau, France

OversmoothingGraph RewiringOver-SquashingGraph Neural NetworksOver-Squashing in GNNsGNN Oversmoothing+1
AskPDF
Apr 14, 2026

A Residual-Shell-Based Lower Bound for Ollivier-Ricci Curvature

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.

Xiang Gu, Huichun Zhang, Jian Sun

School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, 710049, Shaanxi, China · School of Mathematics, Sun Yat-sen University, Guangzhou, 510275, Guangdong, China

Ollivier-Ricci CurvatureApproximation Algorithms
AskPDF