# Diffusion Earth Mover's Distance and Distribution Embeddings

arXiv: https://arxiv.org/abs/2102.12833 · HTML: https://mlsanity.com/paper/2102.12833/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 54 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [TrajectoryNet: A Dynamic Optimal Transport Network for Modeling Cellular Dynamics](https://mlsanity.com/paper/2002.04461/) (2020)
- [Sliced Wasserstein Kernels for Probability Distributions](https://mlsanity.com/paper/1511.03198/) (2015)
- [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019)
- [Scalable Unbalanced Optimal Transport using Generative Adversarial Networks](https://mlsanity.com/paper/1810.11447/) (2018)
- [Scalable Nearest Neighbor Search for Optimal Transport](https://mlsanity.com/paper/1910.04126/) (2019)
- [Convolutional Networks for Spherical Signals](https://mlsanity.com/paper/1709.04893/) (2017)
- [Fast Unbalanced Optimal Transport on a Tree](https://mlsanity.com/paper/2006.02703/) (2020)
- [Network Density of States](https://mlsanity.com/paper/1905.09758/) (2019)
- [Learning transport cost from subset correspondence](https://mlsanity.com/paper/1909.13203/) (2019)

## Built on by (most cited first, 18 of 18)

- [Manifold Interpolating Optimal-Transport Flows for Trajectory Inference](https://mlsanity.com/paper/2206.14928/) (2022)
- [Digger: Detecting Copyright Content Mis-usage in Large Language Model Training](https://mlsanity.com/paper/2401.00676/) (2024)
- [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022)
- [Hyperbolic Diffusion Embedding and Distance for Hierarchical Representation Learning](https://mlsanity.com/paper/2305.18962/) (2023)
- [Wasserstein Wormhole: Scalable Optimal Transport Distance with Transformers](https://mlsanity.com/paper/2404.09411/) (2024)
- [Fixed Support Tree-Sliced Wasserstein Barycenter](https://mlsanity.com/paper/2109.03431/) (2021)
- [Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds](https://mlsanity.com/paper/2211.00805/) (2022)
- [The Manifold Scattering Transform for High-Dimensional Point Cloud Data](https://mlsanity.com/paper/2206.10078/) (2022)
- [The Impact of Off-Policy Training Data on Probe Generalisation](https://mlsanity.com/paper/2511.17408/) (2025)
- [Topology-aware Robust Optimization for Out-of-distribution Generalization](https://mlsanity.com/paper/2307.13943/) (2023)
- [Multimodal Unlearning Across Vision, Language, Video, and Audio: Survey of Methods, Datasets, and Benchmarks](https://mlsanity.com/paper/2607.07907/) (2026)
- [Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy](https://mlsanity.com/paper/2410.21107/) (2024)
- [Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance](https://mlsanity.com/paper/2107.12334/) (2021)
- [Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search](https://mlsanity.com/paper/2401.07378/) (2024)
- [From Missing Pieces to Masterpieces: Image Completion with Context-Adaptive Diffusion](https://mlsanity.com/paper/2504.14294/) (2025)
- [Graph Fourier MMD for Signals on Graphs](https://mlsanity.com/paper/2306.02508/) (2023)
- [An Empirical Study of Self-supervised Learning with Wasserstein Distance](https://mlsanity.com/paper/2310.10143/) (2023)
- [Pheno-GS: Phenoscape-scale Geodesic Sinkhorn](https://mlsanity.com/paper/2609.27633/) (2026)

## Abstract (arXiv)

We propose a new fast method of measuring distances between large numbers of related high dimensional datasets called the Diffusion Earth Mover's Distance (EMD). We model the datasets as distributions supported on common data graph that is derived from the affinity matrix computed on the combined data. In such cases where the graph is a discretization of an underlying Riemannian closed manifold, we prove that Diffusion EMD is topologically equivalent to the standard EMD with a geodesic ground distance. Diffusion EMD can be computed in tildeO(n) time and is more accurate than similarly fast algorithms such as tree-based EMDs. We also show Diffusion EMD is fully differentiable, making it amenable to future uses in gradient-descent frameworks such as deep neural networks. Finally, we demonstrate an application of Diffusion EMD to single cell data collected from 210 COVID-19 patient samples at Yale New Haven Hospital. Here, Diffusion EMD can derive distances between patients on the manifold of cells at least two orders of magnitude faster than equally accurate methods. This distance matrix between patients can be embedded into a higher level patient manifold which uncovers structure and heterogeneity in patients. More generally, Diffusion EMD is applicable to all datasets that are massively collected in parallel in many medical and biological systems.