用曲率判断数据边真伪，提升邻近图质量
Recovering Manifold Structure Using Ollivier-Ricci Curvature
- 基于奥利维耶-里奇曲率与度量扭曲，识别并剪除虚假连接
- 在低维流形数据上，真实流形边的曲率更接近零
- 适用于单细胞测序等几何分析任务，可显著提效
我们提出ORC-ManL算法，利用奥利维耶-里奇曲率和估计的度量扭曲来剪除近邻图中的虚假边。动机源于流形学习：当数据为低维流形上的噪声采样时，穿越环境空间的短路边具有更负的奥利维耶-里奇曲率，而沿流形的边则曲率较接近零。实验表明，该方法优于其他剪枝方法，并显著提升多种下游几何数据分析任务的表现，包括流形学习、持久同调、维度估计等。此外，该方法可用于改善单细胞RNA测序数据的聚类与流形学习。我们还通过实证收敛实验验证了理论结果。
原文摘要 · Abstract (English)
We introduce ORC-ManL, a new algorithm to prune spurious edges from nearest neighbor graphs using a criterion based on Ollivier-Ricci curvature and estimated metric distortion. Our motivation comes from manifold learning: we show that when the data generating the nearest-neighbor graph consists of noisy samples from a low-dimensional manifold, edges that shortcut through the ambient space have more negative Ollivier-Ricci curvature than edges that lie along the data manifold. We demonstrate that our method outperforms alternative pruning methods and that it significantly improves performance on many downstream geometric data analysis tasks that use nearest neighbor graphs as input. Specifically, we evaluate on manifold learning, persistent homology, dimension estimation, and others. We also show that ORC-ManL can be used to improve clustering and manifold learning of single-cell RNA sequencing data. Finally, we provide empirical convergence experiments that support our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。