Diffusion Earth Mover's Distance and Distribution Embeddings.

Area of Science:

• Computational Biology
• Data Science
• Topology

Background:

• High-dimensional datasets are prevalent in biological and medical research.
• Existing methods for measuring distances between such datasets can be computationally intensive.
• There is a need for fast, accurate, and scalable distance metrics.

Approach:

• Propose Diffusion Earth Mover's Distance (EMD), a novel algorithm for measuring distances between large, related high-dimensional datasets.
• Model datasets as distributions on a common data graph derived from an affinity matrix.
• Prove topological equivalence to standard EMD with geodesic distance on Riemannian manifolds.

Key Points:

• Diffusion EMD achieves $\tilde{O}(n)$ computation time, significantly faster than existing methods.
• Demonstrates higher accuracy compared to other fast algorithms like tree-based EMDs.
• Fully differentiable, enabling integration with deep learning frameworks.

Conclusions:

• Diffusion EMD offers a scalable and accurate solution for comparing high-dimensional biological data, such as single-cell samples from COVID-19 patients.
• Accelerates patient stratification and reveals underlying patient heterogeneity.
• Broadly applicable to massively parallel datasets in various scientific domains.