🧬 biology

EntroPath: Maximum Entropy Path Ensemble Embedding for Manifold Learning

EntroPath is a manifold learning method that utilizes maximum entropy random walks to aggregate ensembles of diffusion paths, thereby recovering geodesic geometry more robustly than existing shortest-path or local-normalized approaches, particularly in datasets with non-uniform sampling and complex branching structures.

Original authors: Przemysław Rola

Published 2026-07-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Przemysław Rola

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

Imagine you have a giant, tangled ball of yarn representing a complex dataset (like the genetic instructions inside millions of cells). Your goal is to flatten this ball onto a table to see its shape clearly without tearing the threads or stretching them out of proportion. This is the challenge of Manifold Learning.

The paper introduces a new tool called EntroPath to solve this. Here is how it works, explained through simple analogies.

The Problem: Two Flawed Ways to Map the World

To understand EntroPath, we first need to see why the old methods struggle. Imagine you are trying to map a city, but you can only see the streets connecting your neighbors.

The "Crowded Street" Problem (Standard Random Walks):
Imagine a tourist walking randomly through the city. If they are in a crowded downtown area with many streets, they are likely to stay there. If they are in a quiet, sparse suburb with only one or two roads, they might accidentally wander off the map or get lost.
- In data terms: Old methods get "stuck" in areas where there is a lot of data (dense regions) and ignore the sparse, important areas (like rare cell types or thin bridges between groups). They compress the quiet parts of the map.
The "Shortcut" Problem (Shortest Paths):
Imagine trying to find the distance between two points by only looking for the single fastest route. If there is one accidental "shortcut" (a bridge that shouldn't be there, or a noisy data point connecting two faraway places), your map will say the two places are right next to each other, even if they are actually worlds apart.
- In data terms: A single bad connection in the data can ruin the entire map, making distant things look close.

The Solution: EntroPath (The "Group Hike" Approach)

EntroPath changes the rules. Instead of sending one tourist or looking for one shortcut, it sends out thousands of hikers at once and asks them to explore every possible path of a certain length.

Here is the magic sauce: Maximum Entropy.
Instead of letting the hikers get distracted by crowded streets, EntroPath forces the group to spread out as evenly as possible. It treats every possible route as a potential path and weighs them all together.

The "Bridge" Analogy: Imagine two islands connected by a very thin, fragile bridge.
- Old Method: A single hiker might easily cross the bridge, thinking the islands are close.
- EntroPath: It sends a massive group. Most hikers get stuck on the islands because the bridge is too narrow for the "crowd" to flow through easily. The system realizes, "Hey, it's really hard to get from Island A to Island B." It correctly marks them as far apart, preserving the true shape of the world.

How It Measures Distance: The "Free Energy"

How does EntroPath decide how far apart two points are? It uses a concept called Free Energy (borrowed from physics).

Think of it like a log-sum-exp (a fancy way of saying "average the best paths, but don't ignore the others").

If there is one super-short path, the distance is short.
If there are many good paths, the distance is also short (because the "traffic" flows easily).
If there are no good paths, or the paths are long and winding, the distance is large.

This is different from just finding the shortest path. It looks at the whole ensemble of paths. If a path is blocked or long, but there are many other ways to get there, the distance is still reasonable. This makes the map very robust against "noise" (bad data points).

The "Short-Time" Magic

The paper proves a cool mathematical fact: If you look at these hikers taking just a few steps (a "short time"), the distance they calculate is almost exactly the true physical distance along the curved surface of the data (the geodesic).

It's like if you take a tiny step on a curved beach; the ground feels flat and straight. EntroPath uses this "tiny step" logic to build a map that respects the true curves of the data, even if the data is messy or unevenly sampled.

Why It Matters for Real Data (Like Cells)

The authors tested this on single-cell data (imagine a map of how a stem cell turns into a blood cell, a nerve cell, or a skin cell).

The Challenge: In these datasets, some cell types are very common (dense), while others (like the transition points where a cell is changing) are rare (sparse).
The Result: Old methods often squashed the rare cells into the common ones, making it look like the cell just jumped from one state to another. EntroPath kept the rare cells in their own space, correctly showing the "branching" paths of development. It didn't get tricked by the crowded areas.

The "Scalable" Trick

Calculating this for millions of data points sounds impossible (it would take forever). EntroPath has a clever trick:

Landmarks: Instead of asking every single point to talk to every other point, it picks a few "landmarks" (like major cities on a map). It calculates the complex math for these landmarks first.
Projection: Then, it simply asks the other points, "Which landmark are you closest to?" and places them there. This makes it fast enough to handle huge datasets (like 100,000+ cells) in seconds.

Summary

EntroPath is a new way to flatten complex, high-dimensional data into a simple 2D picture.

It avoids getting stuck in crowded areas by looking at all possible paths, not just the shortest one.
It ignores "shortcut" errors by weighing the entire group of paths.
It is mathematically proven to find the true shape of the data.
It works great on messy, uneven data (like biological cells) and is fast enough for massive datasets.

In short: It's a mapmaker that refuses to be tricked by crowds or shortcuts, ensuring the final picture shows the true, winding roads of your data.

Technical Summary: EntroPath – Maximum Entropy Path Ensemble Embedding for Manifold Learning

1. Problem Statement

Modern high-dimensional datasets, such as single-cell transcriptomics and molecular dynamics trajectories, often concentrate near low-dimensional Riemannian manifolds. A central goal of manifold learning is to recover the intrinsic geometry of these manifolds, specifically their geodesic distances, in a low-dimensional representation.

Existing approaches face significant limitations:

Shortest-Path Methods (e.g., Isomap): Estimate geodesics via single shortest paths on a neighborhood graph. These are fragile; a single "shortcut" edge between geodesically distant regions can corrupt global distances. Furthermore, theoretical recovery guarantees often fail on non-convex or branching manifolds.
Local Neighbourhood Methods (e.g., t-SNE, UMAP): Focus on preserving local relationships via probabilistic objectives. While effective for visualization, they do not explicitly encode global geodesic structures.
Standard Diffusion Methods (e.g., Diffusion Maps, PHATE): Aggregate information over ensembles of paths, offering robustness to graph errors. However, they typically rely on Standard Random Walks (SRW) normalized by local node degree. This causes diffusion to drift toward densely sampled regions, compressing sparse branches and bottlenecks, and biasing representations toward high-density terminal states in trajectory data.

2. Methodology: EntroPath

EntroPath addresses these issues by constructing dissimilarities based on the Maximum Entropy Random Walk (MERW) and a free-energy dissimilarity derived from path ensembles.

2.1 Maximum Entropy Random Walk (MERW)

Unlike SRW, which normalizes transition probabilities locally by node degree ( $T_{ij} = A_{ij}/d_i$ ), MERW maximizes the entropy of trajectories globally. The transition matrix is defined as:
$T_{ij} = \frac{A_{ij}}{\lambda_{\max}} \frac{\psi_j}{\psi_i}$
where $A$ is the affinity matrix, $\lambda_{\max}$ is the largest eigenvalue, and $\psi$ is the corresponding Perron-Frobenius eigenvector.

Global Reweighting: MERW incorporates global graph structure via $\psi$ . It distributes probability uniformly over the ensemble of paths, leaving little mass on low-degree bottlenecks.
Schrödinger Operator Structure: The MERW Laplacian ( $I-T$ ) is similar to a discrete Schrödinger operator $H = \lambda_{\max}I - A = -\Delta + V$ , where $V$ is a potential induced by degree heterogeneity ( $V_i = \lambda_{\max} - d_i$ ). This structure is central to the method's theoretical guarantees.

2.2 Free-Energy Dissimilarity

EntroPath defines the dissimilarity between nodes $i$ and $j$ not as a single shortest path, but as the negative log of the sum of weights over all $k$ -step paths (a partition function).

Path Costs: Edge costs are defined as negative log-affinities, $E(u,v) = -\log A_{uv}$ .
Log-Sum-Exp Formulation: The dissimilarity is:
$D_{ij} = -\log \left( \tilde{A}^k \right)_{ij}$
where $\tilde{A} = A/\lambda_{\max}$ . This represents a soft-min relaxation of the shortest-path distance, aggregating the entire $k$ -step ensemble.
Entropy Term: The dissimilarity includes an entropy term ( $-\sum p(\gamma) \log p(\gamma)$ ) that rewards pairs connected by many comparable paths, distinguishing it from shortest-path metrics.
Symmetrization: For general affinities, the dissimilarity is symmetrized via the geometric mean of forward and backward transition probabilities: $D_{ij} = -\log \sqrt{T^k_{ij} T^k_{ji}}$ . In the symmetric case (standard for Gaussian affinities), this simplifies to $-\log (\tilde{A}^k)_{ij}$ .

2.3 Geometric Regimes and Scaling

The diffusion depth $k$ interpolates between two regimes:

Geodesic Regime (Small $k$ ): The dissimilarity approximates the graph geodesic (shortest path) via Varadhan's short-time heat-kernel formula.
Mixing Regime (Large $k$ ): The dissimilarity converges to a stationary distribution dependent only on the Perron vector, losing fine geometric details.
The method selects $k$ automatically using the "knee" of the von Neumann entropy of the MERW operator, ensuring the diffusion time is sufficient to connect points but not so long as to over-mix.

2.4 Scalability

For large datasets, EntroPath employs:

Landmark Projection: A Nyström-type extension where new points are projected into the embedding of a subset of landmarks via kernel interpolation, avoiding recomputation of the global operator.
Adaptive Kernels: Uses adaptive bandwidths (based on local $k$ -NN distances) to handle non-uniform sampling densities effectively.

3. Key Contributions

Algorithmic Innovation: Introduction of EntroPath, a manifold learning method based on MERW and a free-energy dissimilarity derived from path ensembles.
Theoretical Formulation: A proof that the symmetrized free-energy dissimilarity converges to the squared geodesic distance on the underlying manifold in the short-time limit (Theorem 5.3). This relies on the discrete Schrödinger-operator structure of the MERW Laplacian and Varadhan's formula.
Kernel Connection: Demonstration that the symmetrized MERW kernel admits an exact Gram factorization (Proposition 4.1), connecting EntroPath directly to kernel methods and diffusion maps, unlike many profile-based diffusion methods.
Scalable Extensions: Development of landmark-based out-of-sample embedding and a diffusion-potential pseudotime method for trajectory inference.
Evaluation Protocol: A two-stage evaluation separating distance-level (kernel quality) from embedding-level (layout quality) performance, highlighting a bias in standard geodesic evaluation that favors methods tied to the specific $k$ -NN graph used for ground truth.

4. Experimental Results

EntroPath was evaluated on synthetic manifolds (Swiss roll, sparse trees) and six biological single-cell datasets (e.g., Paul15, Nestorowa, Root Atlas).

Synthetic Manifolds:
- On non-uniformly sampled manifolds and sparse branching trees, EntroPath consistently outperformed diffusion-based baselines (PHATE, HeatGeo, DTNE) and shortest-path methods (Isomap) in recovering geodesic geometry.
- It achieved the highest Spearman and Pearson correlations with ground-truth geodesics in distance-level evaluations.
- In embedding-level evaluations, EntroPath preserved global structure better than local methods (UMAP, t-SNE) and showed superior trustworthiness and continuity compared to other diffusion methods, particularly in sparse regions where SRW-based methods "leak" across bottlenecks.
Single-Cell Data:
- EntroPath matched or exceeded the performance of PHATE, HeatGeo, and DTNE on metrics like DEMaP (manifold preservation) and trustworthiness.
- It demonstrated particular robustness on datasets with non-uniform sampling and well-separated branching trajectories, where it maintained clear separation between cell states without smoothing them into dense clusters.
- On the large-scale Arabidopsis root atlas ( $1.1 \times 10^5$ cells), EntroPath achieved comparable geometric fidelity to DTNE in approximately 15 seconds, leveraging its landmark and adaptive kernel strategies to avoid the computational cost of dense graph powers required by hard- $k$ NN methods.

5. Significance and Claims

The paper claims that EntroPath offers a principled solution to the tension between local degree normalization (which biases diffusion in SRW) and global geodesic recovery (which is fragile in shortest-path methods).

Robustness to Sampling Density: By utilizing MERW, EntroPath treats low-degree bottlenecks as high-energy barriers rather than easy passages. This preserves the separation of sparsely sampled branches and prevents the "collapse" of global geometry often seen in SRW-based embeddings.
Theoretical Guarantee: The convergence to squared geodesic distance provides a rigorous geometric foundation, distinguishing it from heuristic diffusion distances.
Practical Utility: The method provides a scalable, parameter-light approach (using automatic depth selection) that performs competitively across diverse data regimes, from synthetic benchmarks to complex biological trajectories.

The authors note limitations, specifically that entropy-based depth selection can become noisy on very short branches, and suggest future work in continuous-time formulations and handling directed affinities (e.g., for RNA velocity).