Search papers, labs, and topics across Lattice.
This paper introduces EntroPath, a novel manifold learning method that utilizes maximum entropy random walks to recover geodesic geometry from data graphs by aggregating ensembles of diffusion paths. Unlike traditional methods that rely on either locally normalized random walks or shortest-path distances, EntroPath effectively mitigates issues related to sampling density and spurious edges by constructing dissimilarities from a comprehensive set of k-step paths. The results demonstrate that EntroPath consistently matches or surpasses existing methods in preserving manifold geometry, particularly in scenarios with non-uniform sampling and distinct branching trajectories.
Path-ensemble diffusion in EntroPath reveals the true geodesic structure of complex manifolds, outperforming traditional methods in challenging sampling scenarios.
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.
