Geometry-Aware Graph Coarsening via Ollivier-Ricci Curvature

We introduce Ollivier-Ricci Graph Coarsening (\method), a geometry-aware graph coarsening framework that formulates node contraction through Ricci-curvature optimization.Existing methods commonly use adjacency rules or Laplacian preservation, which do not model metric-measure geometry explicitly.Gromov-Wasserstein coarsening makes this geometry explicit, but its global distance and assignment computations make efficient implementation difficult.ORGC instead adopts Ollivier-Ricci curvature as an efficient geometric primitive for comparing Markov neighborhoods.We define Ricci Geometric Coherence (RGC) over non-singleton coarse clusters, which measures all-pairs curvature agreement among nodes that are actually contracted together.ORGC derives a contraction-forest lower bound ${\mathcal{L}}_h$ for this objective and exactly maximizes this bound through a Kruskal-style greedy algorithm.We further establish a boundary-preservation guarantee for ORGC under a forest-rank separation condition.Experiments on structural fidelity, graph classification, molecular regression, and runtime scaling show that ORGC preserves graph structure and downstream utility while remaining efficient.