🧬 biology

EntroPath: Maximum Entropy Path Ensemble Embedding for Manifold Learning

EntroPath 是一种流形学习方法，它利用最大熵随机游走来聚合扩散路径系综，从而比现有的最短路径或局部归一化方法更稳健地恢复测地几何结构，尤其是在具有非均匀采样和复杂分支结构的的数据集中。

原作者： Przemysław Rola

发布于 2026-07-08

📖 1 分钟阅读☕ 轻松阅读

原作者： Przemysław Rola

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ⚕️ 这是一篇未经同行评审的预印本的AI生成解释。这不是医疗建议。请勿根据此内容做出健康决定。阅读完整免责声明

想象你有一个巨大的、缠绕在一起的毛线球，它代表了一个复杂的数据集（比如数百万个细胞内的遗传指令）。你的目标是将这个毛线球平铺在桌面上，以便清晰地观察它的形状，同时又不撕裂线头或使其过度拉伸变形。这就是**流形学习（Manifold Learning）**所面临的挑战。

这篇论文介绍了一种名为 EntroPath 的新工具来解决这个问题。以下是通过简单的类比对它的工作原理进行的解释。

问题：两种有缺陷的世界绘图方式

要理解 EntroPath，我们首先要看看旧方法为什么会遇到困难。想象你正在绘制一张城市地图，但你只能看到连接邻居的街道。

“拥挤街道”问题（标准随机游走）：
想象一名游客在城市中随机行走。如果他们在街道密集的繁华市中心，他们很可能会留在那里。如果他们在只有一两条路的安静、稀疏的郊区，他们可能会不小心迷失方向或在地图之外徘徊。
- 用数据术语来说： 旧方法会“卡”在数据密集的区域（稠密区域），而忽略了那些稀疏但重要的区域（如罕见细胞类型或不同群体之间的细微桥梁）。它们压缩了地图中安静的部分。
“捷径”问题（最短路径）：
想象你试图通过只寻找单一最快路线来计算两点之间的距离。如果存在一个偶然的“捷径”（一条本不该存在的桥梁，或者一个将两个遥远地方连接在一起的噪声数据点），你的地图会显示这两个地方就在彼此旁边，即使它们实际上相隔万里。
- 用数据术语来说： 一个坏的连接就会毁掉整张地图，使原本遥远的事物看起来很近。

解决方案：EntroPath（“集体远足”法）

EntroPath 改变了规则。它不再只派出一名游客或寻找一条最短路径，而是同时派出数千名远足者，并要求他们探索所有可能的路径（且长度相同）。

这里有一个神奇的秘诀：最大熵（Maximum Entropy）。
EntroPath 不会让远足者被拥挤的街道分心，而是强制这群人尽可能均匀地展开。它将每条可能的路线都视为潜在路径，并将它们全部加权计算。

“桥梁”类比： 想象两座岛屿之间由一座非常细窄、脆弱的桥连接。
- 旧方法： 一名远足者可能会轻易穿过这座桥，认为两座岛屿离得很近。
- EntroPath： 它派出了一大群人。大多数远足者会卡在岛屿上，因为这座桥太窄，无法让“人群”轻松流动。系统会意识到：“嘿，从岛屿 A 到岛屿 B 其实很难。”它能正确地将它们标记为相距甚远，从而保留了世界的真实形状。

它是如何衡量距离的：“自由能”

EntroPath 如何决定两个点之间的距离？它使用了一个概念叫做自由能（Free Energy）（借用自物理学）。

这可以想象成一种 log-sum-exp（一种高级说法，意为“综合考虑所有最佳路径，但不要忽略其他路径”）。

如果只有一条超短路径，距离就很短。
如果有许多条良好的路径，距离也会很短（因为“交通”流动顺畅）。
如果没有好的路径，或者路径又长又曲折，距离就会很大。

这与仅仅寻找最短路径不同。它观察的是整个路径集合。如果一条路径被阻断或很长，但还有许多其他途径可以到达，那么距离仍然是合理的。这使得地图对“噪声”（坏数据点）具有极强的鲁棒性。

“短时间”的神奇之处

论文证明了一个有趣的数学事实：如果你观察这些远足者仅走几步（“短时间”）的情况，它们计算出的距离几乎完全等于数据在弯曲表面上的真实物理距离（测地线距离）。

这就像你在弯曲的海滩上迈出一小步；地面感觉是平坦且笔直的。EntroPath 利用这种“小小一步”的逻辑，构建出一张尊重数据真实曲线的地图，即使数据是杂乱或采样不均的。

为什么这对真实数据（如细胞）很重要

作者在单细胞数据上测试了这一点（想象一张描述干细胞如何转化为血细胞、神经细胞或皮肤细胞的地图）。

挑战： 在这些数据集中，某些细胞类型非常常见（稠密），而另一些（如细胞正在发生变化的过渡点）则非常罕见（稀疏）。
结果： 旧方法经常会将稀有细胞压缩到常见细胞中，使之看起来像是细胞直接跳跃到了另一种状态。EntroPath 则让稀有细胞保持在各自的空间内，正确展示了发育的“分支”路径。它不会被拥挤的区域所迷惑。

“可扩展性”的小技巧

计算数百万个数据点的这种过程听起来是不可能的（会耗费极长时间）。EntroPath 有一个聪明的技巧：

地标（Landmarks）： 它不是要求每一个点都去与每一个点进行通信，而是挑选了几个“地标”（就像地图上的主要城市）。它先计算这些地标的复杂数学运算。
投影： 然后，它只需询问其他点：“你离哪个地标最近？”并将它们放置在那里。这使得它处理大规模数据集（如 100,000+ 个细胞）的速度快到可以在几秒钟内完成。

总结

EntroPath 是一种将高维复杂数据扁平化为简单 2D 图片的新方法。

它通过观察所有可能的路径而非仅仅是最短路径，避免了在拥挤区域卡住。
它通过权衡整个路径组，忽略了“捷径”带来的错误。
它在数学上被证明能够找到数据的真实形状。
它在处理杂乱、采样不均的数据（如生物细胞）时表现出色，并且足以快速处理大规模数据集。

简而言之：它是一个拒绝被人群或捷径所欺骗的绘图师，确保最终的图像能够展现出你数据中真实的、蜿蜒起伏的道路。

技术摘要：EntroPath —— 用于流形学习的最大熵路径系综嵌入

1. 问题陈述

现代高维数据集（如单细胞转录组学和分子动力学轨迹）通常集中在低维黎曼流形附近。流形学习的一个核心目标是在低维表示中恢复这些流形的内在几何结构，特别是其测地距离（geodesic distances）。

现有方法面临显著局限性：

最短路径法（如 Isomap）： 通过邻域图上的单个最短路径来估计测地线。这些方法非常脆弱；一个位于测地距离较远区域之间的“捷径”边可能会破坏全局距离。此外，其理论恢复保证在非凸或分支流形上往往会失效。
局部邻域法（如 t-SNE, UMAP）： 侧重于通过概率目标来保持局部关系。虽然在可视化方面非常有效，但它们并未显式地编码全局测地结构。
标准扩散方法（如 Diffusion Maps, PHATE）： 通过路径系综（ensembles of paths）聚合信息，从而提高对图误差的鲁棒性。然而，这些方法通常依赖于通过局部节点度进行归一化的标准随机游走（SRW）。这会导致扩散向高密度区域漂移，从而压缩稀疏的分支和瓶颈，并使轨迹数据中的表示向高密度终端状态偏移。

2. 方法论：EntroPath

EntroPath 通过构建基于**最大熵随机游走（MERW）和源自路径系综的自由能差异（free-energy dissimilarity）**的差异度来解决上述问题。

2.1 最大熵随机游走 (MERW)

与 SRW 不同，MERW 通过全局最大化轨迹的熵来定义转移矩阵。其转移矩阵定义为：
$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$
其中 $A$ 是亲和矩阵， $\lambda_{\max}$ 是最大特征值， $\psi$ 是对应的 Perron-Frobenius 特征向量。

全局重加权： MERW 通过 $\psi$ 整合了全局图结构。它将概率均匀分布在路径系综上，极少在低度数（low-degree）的瓶颈处留下质量。
薛定谔算子结构： MERW 拉普拉斯算子（ $I-T$ ）类似于离散薛定谔算子 $H = \lambda_{\max}I - A = -\Delta + V$ ，其中 $V$ 是由度异质性诱导的势能（ $V_i = \lambda_{\max} - d_i$ ）。这种结构是该方法理论保证的核心。

2.2 自由能差异

EntroPath 定义节点 $i$ 与 $j$ 之间的差异度并非为单个最短路径，而是为所有 $k$ 步路径权重之和的负对数（即配分函数）。

路径代价： 边的代价定义为负对数亲和力， $E(u,v) = -\log A_{uv}$ 。
Log-Sum-Exp 公式： 差异度为：
$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$
其中 $\tilde{A} = A/\lambda_{\max}$ 。这代表了最短路径距离的一种 soft-min 松弛，聚合了整个 $k$ 步系综。
熵项： 差异度包含一个熵项（ $-\sum p(\gamma) \log p(\gamma)$ ），它奖励那些由许多可比路径连接的节点对，从而区别于最短路径度量。
对称化： 对于一般的亲和力，通过前向和后向转移概率的几何平均值进行对称化： $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$ 。在对称情况下（对于高斯亲和力是标准的），这简化为 $-\log (\tilde{A}^k)_{ij}$ 。

2.3 几何机制与缩放

扩散深度 $k$ 在以下两个机制之间进行插值：

测地机制（较小的 $k$ ）： 差异度通过 Varadhan 的短时热核公式近似图测地线（最短路径）。
混合机制（较大的 $k$ ）： 差异度收敛到仅取决于 Perron 向量的平稳分布，从而丢失精细的几何细节。
该方法使用 von Neumann 熵的“拐点”（knee）自动选择 $k$ ，以确保扩散时间足以连接各点，又不至于过度混合。

2.4 可扩展性

对于大规模数据集，EntroPath 采用了：

地标投影（Landmark Projection）： 一种 Nyström 型扩展，通过核插值将新点投影到由一组地标构成的嵌入空间中，避免了重新计算全局算子的开销。
自适应核（Adaptive Kernels）： 使用基于局部 $k$ -NN 距离的自适应带宽，以有效地处理非均匀采样密度。

3. 核心贡献

算法创新： 引入了 EntroPath，一种基于 MERW 和源自路径系综的自由能差异的流形学习方法。
理论公式化： 证明了对称化的自由能差异在短时极限下收敛于底层流形的平方测地距离（定理 5.3）。这依赖于 MERW 拉普拉斯算子的离散薛定谔算子结构以及 Varadhan 公式。
核连接： 证明了对称化的 MERW 核具有精确的 Gram 分解（命题 4.1），这使得 EntroPath 直接与核方法和扩散映射相联系，不同于许多基于剖面的扩散方法。
可扩展扩展： 开发了基于地标的出样本嵌入（out-of-sample embedding）和用于轨迹推断的扩散-势能伪时间方法。
评估协议： 建立了一个两阶段评估体系，将距离级（核质量）与嵌入级（布局质量）性能分离，突出了标准测地评估中存在的偏见，即倾向于与用于真值的特定 $k$ -NN 图紧密结合的方法。

4. 实验结果

EntroPath 在合成流形（瑞士卷、稀疏树）和六个生物单细胞数据集（例如 Paul15, Nestorowa, Root Atlas）上进行了评估。

合成流形：
- 在非均匀采样流形和稀疏分支树上，EntroPath 在恢复测地几何方面始终优于基于扩散的基准方法（PHATE, HeatGeo, DTNE）和最短路径方法（Isomap）。
- 在距离级评估中，它实现了最高的 Spearman 和 Pearson 与真值测地线的相关性。
- 在嵌入级评估中，EntroPath 比局部方法（UMAP, t-SNE）更好地保持了全局结构，并且与其它扩散方法相比，表现出更高的可信度和连续性，特别是在 SRW 方法容易发生“泄漏”的稀疏区域。
单细胞数据：
- EntroPath 在 DEMaP（流形保持）和可信度等指标上达到或超过了 PHATE, HeatGeo 和 DTNE 的性能。
- 它在具有非均匀采样和清晰分离的分支轨迹的数据集上表现出特别的鲁棒性，能够维持细胞状态之间的清晰分离，而不会将其平滑进稠密簇中。
- 在大规模拟南芥根谱图（ $1.1 \times 10^5$ 个细胞）上，利用其地标和自适应核策略，EntroPath 以约 15 秒的时间达到了与 DTNE 相当的几何保真度，避免了硬 $k$ -NN 方法所需的密集图幂运算的计算成本。

5. 意义与主张

论文声称 EntroPath 为局部度数归一化（这会导致 SRW 中的扩散偏差）与全局测地恢复（这在最短路径法中很脆弱）之间的张力提供了一个原则性的解决方案。

对采样密度的鲁棒性： 通过利用 MERW，EntroPath 将低度数瓶颈视为高能垒而非易通过路径。这保留了稀疏采样分支的分离度，并防止了 SRW 类嵌入中常见的全局几何“坍塌”。
理论保证： 向平方测地距离的收敛性提供了严谨的几何基础，使其区别于启发式的扩散距离。
实际效用： 该方法提供了一种可扩展且参数轻量化的方法（使用自动深度选择），在从合成基准到复杂生物轨迹的多种数据机制下均表现出竞争力。

作者指出了一些局限性，特别是基于熵的深度选择在极短分支上可能会变得不稳定，并建议未来在连续时间公式化和处理有向亲和力（例如 RNA 速率）方面开展工作。