Research map / Graph learning / Graph algorithms and clustering
Recovering Manifold Structure Using Ollivier Ricci Curvature
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ORC-ManL, a training-free pruning algorithm that removes shortcut edges from k-NN graphs using unweighted Ollivier-Ricci curvature candidates filtered by thresholded graph distances, with theory on curvature of shortcut edges.
Problem
Nearest neighbor graphs built from noisy manifold samples contain shortcut edges that bridge distant manifold neighborhoods, distorting distances and harming downstream geometric data analysis tasks.
Approach
Use unweighted Ollivier-Ricci curvature to flag extremely negative-curvature edges as candidate shortcuts, then remove only those candidates whose endpoint distance in the thresholded graph is large relative to epsilon, with theory showing shortcut edges have ORC at most -1 in the vanishing-noise limit.
Key results
- On synthetic manifolds, ORC-ManL removes 100% of shortcut edges on most manifolds while removing 0.0% of good edges, versus ORC Only removing about 11-18% of good edges.
- Spectral clustering with ORC-ManL pruning attains perfect ARI on the two-component noisy manifold examples, while unpruned graphs yield trivial clusterings.
- On MNIST, ORC-ManL removes 14.92% of inter-class edges and 7.90% of intra-class edges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the metric-distortion validation step after ORC candidate selection (ablation) | ORC-ManL vs. ORC Only · Synthetic manifolds: 1D and 2D pruning benchmarks | good-edge removal (%): ORC-ManL: 0.0\pm0.0; ORC Only: 10.9\pm0.1 to 18.1\pm0.3 | Helped |
| Add ORC-ManL graph pruning before manifold learning | Isomap, LLE, UMAP, and t-SNE · Noisy Swiss Roll and Swiss Hole | embedding quality | Helped |
| Add ORC-ManL graph pruning before t-SNE | t-SNE · Noisy Swiss Roll and Swiss Hole | embedding quality | No clear effect |
| Add ORC-ManL graph pruning before persistent homology | Vietoris-Rips persistent homology · Concentric Circles and Chained Tori | Wasserstein distance to noiseless persistence diagram | Helped |
| Add ORC-ManL graph pruning before spectral clustering | Spectral clustering · Synthetic manifolds with two connected components | adjusted Rand index | Helped |
| Add ORC-ManL graph pruning before intrinsic-dimension estimation | Pointwise intrinsic-dimension estimation · Swiss Roll and adjacent spheres | point-wise accuracy | Mixed |
| Add ORC-ManL graph pruning before scalar-curvature estimation | Scalar-curvature estimation · Swiss Roll and adjacent spheres | estimation accuracy | Helped |
| Prune the nearest-neighbor graph with ORC-ManL | Isomap · ALM brain-cell scRNAseq | neuronal community separation | Helped |
| Prune the nearest-neighbor graph with ORC-ManL | UMAP and spectral embedding · PBMC scRNAseq | cluster alignment with annotations | Helped |
| Prune the nearest-neighbor graph with ORC-ManL | UMAP · MNIST | inter-class edge removal (%): 14.92% inter-class edges; 7.90% intra-class edges | Mixed |
| Prune the nearest-neighbor graph with ORC-ManL | UMAP · KMNIST | inter-class edge removal (%): 14.70% inter-class edges; 5.39% intra-class edges | Mixed |
Surprising findings
- Shortcut edges in the vanishing-noise limit concentrate at ORC at or below -1, with ORC asymptoting to -2 as noise falls.
- Density and distance baselines are erratic across manifolds and require per-manifold manual threshold tuning, while ORC-ManL uses fixed parameters across all manifolds.
Limitations
- Theoretical guarantees assume epsilon-radius connectivity and vanishing noise, while experiments use k-NN graphs.
- Some good edges are removed in certain settings; the distance check is not fully justified for beta < 1 and beta is experimentally set to 1.
- Baselines require manual threshold tuning, and results on real data are largely qualitative.
Experimental setup
Datasets: MNIST KMNIST PBMC scRNAseq (10XGenomics) ALM mouse brain scRNAseq (Allen Institute) synthetic manifolds
Benchmarks: MNIST KMNIST
Metrics: percent good edges removed percent shortcut edges removed classification accuracy of edges adjusted Rand index Wasserstein distance between persistence diagrams mean-squared error of intrinsic dimension scalar curvature estimation error
Baselines: ORC Only Bisection MST Density Distance Isomap LLE UMAP t-SNE
Builds on: Ollivier-Ricci curvature Isomap UMAP t-SNE
Closest papers by meaning
- Curvature Regularization to Prevent Distortion in Graph Embedding (NeurIPS 2020 · similarity 0.87)
- Geometric Analysis of Nonlinear Manifold Clustering (NeurIPS 2024 · similarity 0.86)
- Graph Geometry-Preserving Autoencoders (ICML 2024 · similarity 0.85)
- Toward a Unified Geometry Understanding : Riemannian Diffusion Framework for Graph Generation and Prediction (NeurIPS 2025 · similarity 0.85)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.85)
- Finsler Multi-Dimensional Scaling: Manifold Learning for Asymmetric Dimensionality Reduction and Embedding (CVPR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.