用路径集合最大化熵,更准还原数据流形几何结构。
EntroPath: Maximum Entropy Path Ensemble Embedding for Manifold Learning

- 基于多步扩散路径的全集构建相似性,避免单一路径偏差。
- 短时间下相似性收敛到平方测地距离,理论保证强。
- 适合非均匀采样和分支结构数据,对单细胞分析尤佳。
我们提出EntroPath,一种基于图的流形学习方法,通过扩散路径集合恢复数据图中的测地几何。现有方法或依赖局部归一化随机游走,或使用最短路径距离,前者易集中在高密度区域,后者对图中虚假捷径敏感。EntroPath采用最大熵随机游走(MERW),聚合两点间所有k步路径的统计特性,而非依赖单一轨迹。结果表明,其自由能相似性在短时间极限下,通过Varadhan热核公式收敛于平方测地距离。扩散深度k平滑地介于局部邻域结构与全局流形几何之间,对称核可实现精确格拉姆分解,与核方法直接关联。我们还提出了基于地标投影和扩散势伪时间的可扩展方案。在合成流形与单细胞基准上,EntroPath始终优于或等同于基于扩散和最短路径的方法,且在局部结构指标上与UMAP、t-SNE等邻域保持嵌入方法相当。在非均匀采样和明显分叉结构的数据上优势尤为显著,路径集合扩散更忠实还原真实测地几何。
原文摘要 · Abstract (English)
We introduce EntroPath, a manifold learning method that recovers geodesic geometry from data graphs through ensembles of diffusion paths. Many existing graph-based embeddings rely either on locally normalised random walks or on shortest-path distances. The former can concentrate diffusion in densely sampled regions, while the latter are sensitive to spurious shortcut edges in the graph. EntroPath instead builds its dissimilarities from the maximum entropy random walk (MERW), which aggregates the full ensemble of k-step paths between points rather than relying on any single trajectory. We show that the resulting free-energy dissimilarity converges to squared geodesic distance in the short-time limit, via Varadhan's heat-kernel formula. The diffusion depth k interpolates smoothly between local neighbourhood structure and global manifold geometry, and the symmetrised kernel admits an exact Gram factorisation connecting EntroPath to kernel methods. We further provide scalable extensions via landmark projection and diffusion-potential pseudotime. Across synthetic manifolds and single-cell benchmarks, EntroPath consistently matches or outperforms diffusion- and shortest-path-based methods, while remaining competitive with neighbourhood-preserving embeddings (UMAP, t-SNE) on local-structure metrics. Its gains are most pronounced on manifolds with non-uniform sampling density and well-separated branching trajectories, where path-ensemble diffusion more faithfully preserves the underlying geodesic geometry.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。