🤖 machine learning

EmbedOR: Provable Cluster-Preserving Visualizations with Curvature-Based Stochastic Neighbor Embeddings

该论文介绍了 EmbedOR，一种结合了离散图曲率的可证明随机邻域嵌入算法，旨在保留潜在的聚类结构，并防止像 UMAP 和 t-SNE 等方法中常见的连续高密度区域发生伪碎片化现象。

原作者： Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

发布于 2026-07-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Tristan Luca Saidi, Abigail Hickok, Bastian Rieck, Andrew J. Blumberg

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你拥有一个巨大的、缠绕在一起的毛线球，它代表着一个庞大的数据集。毛线的某些部分紧密地结成色彩鲜艳的簇（就像一群朋友），而另一些部分则延伸成长而连续的线段。你的目标是将这个三维的毛线球展平到一张二维的纸上，这样你就能看到其中的模式，而不会让毛线变得混乱不堪或被撕裂。

多年来，用于这项工作的流行工具——被称为 tSNE 和 UMAP ——就像一群热衷于此但笨手笨脚的孩子，试图展平这些毛线。它们通常在分离彩色簇方面做得很好，但它们有一个坏习惯：会折断那些长而连续的线段。它们可能会把一条单一且平滑的路径拆解成三个或四个互不相连的孤岛，使数据看起来像是破碎成了碎片，而实际上它们原本是连通的。它们有时甚至无法识别出最初的簇，如果数据不是完美圆润且整齐的话。

于是有了 EmbedOR，这是一个由研究员 Tristan Luca Saidi、Abigail Hickok、Bastian Rieck 和 Andrew J. Blumberg 设计的新工具。你可以把 EmbedOR 想象成一把“感知曲率”的剪刀。在它切割或展平毛线之前，它会测量每一处连接的“弯曲度”。

“弯曲度”（曲率）的奥秘

EmbedOR 的核心秘诀在于一种被称为 Ollivier-Ricci 曲率 的东西。想象你在参加一个拥挤的派对：

如果你身处一个朋友们彼此都认识的紧密群体中，这种“曲率”是正的。这感觉像是一个温馨、连通的社区。
如果你站在连接两个不同房间的狭窄桥梁上，这种“曲率”是负的。这感觉像是一个瓶颈；如果你走下这座桥，就会掉入另一个世界。

旧工具（tSNE 和 UMAP）主要只是观察人们在房间里站得有多近。然而，EmbedOR 观察的是人群的“形状”。它知道一个“负向弯曲”（瓶颈）是一个危险的地方。它将这些瓶颈视为高能垒，有效地表达了：“不要折断这根线！”

EmbedOR 能做什么（以及不能做什么）

研究人员通过数学证明，利用这种曲率图，EmbedOR 可以处理让旧工具栽跟头的杂乱、多噪的数据。他们证明了：

它能保持连通性： 如果两点在原始数据中属于同一条连续的线，EmbedOR 极有可能在扁平化的可视化中保持它们的连通。
它能分离不同的组： 如果两点属于不同的、分离的簇，该工具会确保它们保持距离。

至关重要的是，论文排除了仅仅通过微调现有工具就能让它们表现得更好的想法。作者认为，仅仅修剪“捷径”边（这是他们在前一篇论文中尝试过的方法，称为 ORC-ManL）是不够的，因为该方法使用的是一种僵硬的“开/关”开关。如果一条捷径恰好处于阈值的边缘，它就可能被漏掉。EmbedOR 则不同，因为它使用基于曲率的平滑、连续的“能量”标尺，这使得它更加稳健。

事实胜于雄辩（以及数据证明）

团队并不仅仅是靠猜测；他们在既有复杂数据（如“瑞士卷”形状）的模拟数据和包括手写数字图像（MNIST）以及单细胞 RNA 测序数据（用于追踪细胞发育过程）在内的真实世界数据上进行了测试。

在模拟数据上： EmbedOR 成功地展开了“瑞士卷”而没有将其撕裂，而 tSNE 未能展开它，UMAP 则将其切碎成了碎片。
在真实的细胞数据上： 在观察细胞随时间发育的过程时，UMAP 和 tSNE 经常会在时间轴上制造出“间隙”，使细胞看起来像是从一个阶段跳跃到了另一个阶段。EmbedOR 则保持了时间轴的平滑与连续。

在实验中，研究人员发现，根据 EmbedOR 的新地图，最短的连接与标准地图相比，跨越两个不同簇的可能性降低了10 倍以上。在单细胞数据中，这一降幅接近 7 倍。这表明 EmbedOR 的地图在识别哪些点真正属于彼此方面要出色得多。

审视旧地图的新方式

最酷的部分在于：你甚至不需要使用 EmbedOR 来生成图像就能获得其益处。作者展示了你可以使用任何可视化结果（甚至是使用 UMAP 生成的混乱图像），并在其上叠加“EmbedOR 距离”。如果你看到 EmbedOR 地图中的一条短线在图像中显得拉长或断裂，你就知道这张图像已经使数据发生了“碎片化”。这就像拥有一个说真话的指南针，能指出地图在何处欺骗了你。

我们有多确定？

作者对背后的数学原理非常有信心。他们提供了理论证明，表明对于特定类型的噪声数据，EmbedOR 的距离度量为“保持簇特征”的可视化创造了完美条件。他们证明了，如果你选择正确的设置（特别是控制工具排斥负曲率边的参数 $p$ ），该算法能够以极高的概率找到正确的结构。

然而，他们也诚实地说明了局限性。他们的数学证明依赖于一个关于如何向数据添加噪声的具体模型。虽然他们在许多现实世界的数据集上进行了测试并发现效果极佳，但“完美的”数学保证适用于他们构建的理论模型。在现实世界中，结果在经验上得到了证明是更优越的，但论文并未声称它解决了世界上所有可能的数据问题。

简而言之，EmbedOR 是一种更聪明的方式来展平世界的各种数据。它倾听连接的形状，避免折断那些维持整体性的线索，并为我们呈现出隐藏在数据中的几何结构的更清晰、更诚实的图像。

EmbedOR 技术摘要：基于曲率的随机邻域嵌入及其可证明的聚类保持可视化

问题陈述

随机邻域嵌入（SNE）算法，特别是 t-SNE 和 UMAP，被广泛用于高维数据的可视化。然而，这些方法在几何保持方面存在显著的理论和实践局限性。具体而言，这些方法在处理具有噪声的高维数据时，往往无法恢复其潜在几何结构，表现为：

无法识别聚类：对于本身具有良好聚类特性的数据，无法识别出其中的簇。
引入碎片化（Fragmentation）：将底层数据流形中原本相连的连通分量在可视化中错误地分离开来。

现有的 t-SNE 理论保证仅限于对数据极其严苛的假设（例如，球形且高度分离的聚类），而对于 UMAP 则缺乏显著的理论成果。此外，实证研究表明，标准实现往往违反了这些假设，导致可视化效果不佳。

方法论

作者提出了 EmbedOR，一种通过集成 Ollivier-Ricci 曲率（ORC） 来构建增强聚类距离度量的创新 SNE 算法。该方法分为两个阶段：

基于曲率的度量学习 ( $\Delta_E$ )：
- 算法首先构建数据的最近邻图。
- 计算图中每条边的 ORC。ORC 量化了局部连通性：正曲率表示位于高度连通社区内的边；负曲率则表示“瓶颈”或连接不同聚类的桥接边。
- 基于曲率 $\kappa$ 定义一个能量函数 $E(\kappa; p)$ 。该函数对具有负曲率的边分配高“能量”（惩罚），对正曲率的边分配低能量。
- 计算一种新的成对距离度量 $\Delta_E$ ，它是加权图中的最短路径距离，其中边权重是欧几里得距离与基于曲率的能量函数的乘积。这种度量鼓励路径经过正曲率边（簇内），并避开负曲率边（簇间）。
定制化随机邻域嵌入：
- EmbedOR 使用了一个融合了 t-SNE 和 UMAP 元素的定制 SNE 框架。
- 高维亲和力 ( $p_{ij}$ )：与使用欧几里得距离的标准 t-SNE 不同，EmbedOR 使用 $\Delta_E$ 度量来计算亲和力。
- 优化：算法最小化高维亲和力与低维亲和力（由 Student t-分布建模）之间的“模糊交叉熵”损失。优化过程使用随机梯度下降（SGD），借鉴了 UMAP 的计算效率（避免重新归一化低维亲和力），同时保留了 t-SNE 基于困惑度（perplexity）的相似性计算。

核心贡献

理论扩展：作者证明了 EmbedOR 距离度量将 t-SNE 的理论一致性结果（此前仅限于球形、高度分离的数据）扩展到了更广泛的数据类。具体而言，他们证明在噪声流形模型下：
- $\Delta_E$ 下的簇内距离收敛于流形测地线距离。
- 簇间距离由一个随排斥参数 $p$ 增加的值所下界约束。
- 因此，对于足够大的 $p$ ，数据满足了使 t-SNE 生成聚类保持可视化所需的条件。
算法创新：提出了 EmbedOR，该算法利用离散图曲率创建了一种能够强调潜在聚类结构且不会引入碎片化的距离度量。
诊断工具：展示了 EmbedOR 度量可以作为后验工具来标注现有的可视化结果。通过可视化 $\Delta_E$ 距离较短的边，用户可以识别碎片化现象（即在 $\Delta_E$ 中距离较近的点在嵌入空间中却很远），从而获得对底层几何结构的洞察。

实验结果

作者在合成数据集和真实世界数据集（包括 MNIST、Fashion-MNIST 以及各种单细胞 RNA 测序数据集）上将 EmbedOR 与基准方法（如 t-SNE、UMAP、PHATE、Isomap 和 Laplacian Eigenmaps）进行了对比评估。

合成数据：EmbedOR 在分离潜在连通分量同时避免碎片化连续路径方面，表现出持续优于或等同于最优的性能。虽然 UMAP 经常引入碎片化，且 t-SNE 无法展开类似“瑞士卷”（Swiss Roll）的结构，但 EmbedOR 保持了拓扑完整性。
真实数据 (scRNA-seq)：在发育轨迹和细胞类型数据集中，与 UMAP 和 t-SNE 相比，EmbedOR 更好地保留了轨迹的连续性和细胞类型的分离度。
碎片化分析：通过使用 Spearman 相关系数和 z-score 标准化的边长度进行的定量分析证实，EmbedOR 极小化地扩张了那些被 $\Delta_E$ 度量判定为接近的点之间的距离。相比之下，UMAP 和 t-SNE 被证明显著扩张了这些距离，表明存在碎片化。
度量效用：实验确认，相比于标准 k-NN 图， $\Delta_E$ 短边连接的点更有可能属于同一个地面真值（ground-truth）聚类（或细胞类型），这验证了该度量检测其他嵌入中碎片化能力。

意义与主张

本文声称 EmbedOR 在突出聚类结构与保持数据流形连续性之间实现了“微妙的平衡”，而这种特性在测试的基准方法中并未观察到。

理论意义：这项工作首次为使用基于曲率的度量来放宽 SNE 收敛所需的严格假设提供了理论依据，从而扩大了可证明聚类保持的适用范围。
实践意义：对于需要保持连通分量完整性的噪声高维数据可视化（例如在单细胞基因组学领域），EmbedOR 提供了一个鲁棒的替代方案。
诊断价值：作者强调，EmbedOR 度量具有双重用途：它既是算法的核心距离度量，也是识别和解释其他方法生成的可视化中碎片化的诊断工具。

作者对理论范围保持谦逊，指出其收敛结果依赖于 t-SNE 的特定实例化版本，且其定制算法融合了 UMAP 和 t-SNE 的元素。然而，他们认为关于度量 $\Delta_E$ 的理论见解为其实际有效性提供了强有力的动机。