# Fast Unbalanced Optimal Transport on a Tree

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2020.

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

- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Unbalanced Optimal Transport through Non-negative Penalized Linear Regression](https://mlsanity.com/paper/2106.04145/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Diffusion Earth Mover's Distance and Distribution Embeddings](https://mlsanity.com/paper/2102.12833/) (2021)
- [Entropy Partial Transport with Tree Metrics: Theory and Practice](https://mlsanity.com/paper/2101.09756/) (2021)
- [Supervised Tree-Wasserstein Distance](https://mlsanity.com/paper/2101.11520/) (2021)
- [Re-evaluating Word Mover's Distance](https://mlsanity.com/paper/2105.14403/) (2021)
- [Fixed Support Tree-Sliced Wasserstein Barycenter](https://mlsanity.com/paper/2109.03431/) (2021)
- [Scalable Unbalanced Sobolev Transport for Measures on a Graph](https://mlsanity.com/paper/2302.12498/) (2023)
- [Approximating 1-Wasserstein Distance with Trees](https://mlsanity.com/paper/2206.12116/) (2022)
- [Optimal Transport for Measures with Noisy Tree Metric](https://mlsanity.com/paper/2310.13653/) (2023)
- [Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy](https://mlsanity.com/paper/2410.21107/) (2024)
- [Computationally Efficient Wasserstein Loss for Structured Labels](https://mlsanity.com/paper/2103.00899/) (2021)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [An Empirical Study of Self-supervised Learning with Wasserstein Distance](https://mlsanity.com/paper/2310.10143/) (2023)
- [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025)

## Abstract (arXiv)

This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We reveal which problems in unbalanced optimal transport can/cannot be solved efficiently. Specifically, we prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time under the strong exponential time hypothesis. Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric. The proposed algorithm processes a tree with one million nodes in less than one second. Our analysis forms a foundation for the theoretical study of unbalanced optimal transport algorithms and opens the door to the applications of unbalanced optimal transport to million-scale datasets.