Efficient Trajectory Inference in Wasserstein Space Using Consecutive Averaging

Amartya Banerjee, Harlin Lee, Nir Sharon, Caroline MoosmüllerAISTATS 2025

Introduction

In fields such as computational biology, researchers frequently encounter "cross-sectional" data—snapshots of a population, such as cells, captured at discrete time points. Because measurement processes like single-cell sequencing are often destructive, tracking individual trajectories over time is impossible. The challenge of trajectory inference is to reconstruct the continuous evolution of the population from these disjoint point clouds. Existing methods often struggle with two primary issues: mass splitting (e.g., cell division or lineage branching) and geometric consistency, where extrinsic Euclidean calculations fail to respect the data's inherent manifold structure.

Methodology: Wasserstein Lane-Riesenfeld (WLR)

The authors introduce the Wasserstein Lane-Riesenfeld (WLR) algorithm, which brings classical subdivision schemes—commonly used in computer graphics for curve smoothing—into the Wasserstein space of probability measures.

The core innovation lies in the "averaging" step. Instead of standard arithmetic averaging, which blurs discrete points, WLR employs Optimal Transport (OT) based geodesic averaging. To find the midpoint between two point clouds, the algorithm solves an OT problem to determine the most efficient mass transfer path; the "average" is then defined as the halfway point along this geodesic.

WLR performance on diverse synthetic datasets: Diverging Gaussian, Petal, Dyngen Tree, and Dyngen Cycle.

This approach ensures that the resulting trajectories are intrinsically tied to the geometry of the probability distributions. Furthermore, WLR handles trajectory splitting automatically. If the OT matching indicates that mass from a single source point distributes to multiple targets, the algorithm naturally branches the path, a feature often lacking in fixed-trajectory neural models.

Key Results and Comparison

The WLR algorithm was evaluated against a suite of synthetic and real-world biological datasets, including Diverging/Converging Gaussians, complex geometric "Petal" structures, and CITE-seq human stem cell data.

Comparison of WLR (Ours) against baseline methods on a branching dataset. WLR effectively captures branching structures that other methods struggle to resolve.

A key finding is WLR's superior handling of varying populations and non-uniform mass distributions. In the Converging Gaussian and CITE-seq supercell tests, WLR outperformed or matched state-of-the-art methods like Conditional Flow Matching (CFM) and MIOFlow. Qualitatively, WLR produces trajectories that are visually smoother and more biologically plausible, avoiding the jagged paths or unnatural crossings seen in extrinsic methods.

Beyond empirical performance, the authors provide theoretical rigor by proving linear convergence rates. As the number of refinement steps increases, the algorithm's output is guaranteed to converge to a continuous limit curve in the infinite-dimensional Wasserstein space.

Discussion and Limitations

While WLR offers high stability and predictability compared to "stiff" deep learning optimizations (like Neural ODEs), it faces computational challenges. The primary bottleneck is the requirement to solve multiple OT problems iteratively. Currently, the implementation is sequential, though its structure makes it a strong candidate for future parallelization. Additionally, scaling to extremely high-dimensional data or massive point clouds remains an ongoing area of research for all OT-based methodologies.

Summary updated

BibTeX
@inproceedings{banerjee2025efficient,
  author = {Amartya Banerjee and Harlin Lee and Nir Sharon and Caroline Moosmüller},
  title = {{Efficient Trajectory Inference in Wasserstein Space Using Consecutive Averaging}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}
Figure