# Approximating 1-Wasserstein Distance with Trees

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 45 references that are in the map.
- First posted on arXiv 24 Jun 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [MoverScore: Text Generation Evaluating with Contextualized Embeddings and Earth Mover Distance](https://mlsanity.com/paper/1909.02622/) (2019)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Max-Sliced Wasserstein Distance and its use for GANs](https://mlsanity.com/paper/1904.05877/) (2019)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Proximal Optimal Transport Modeling of Population Dynamics](https://mlsanity.com/paper/2106.06345/) (2021)
- [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019)
- [Sliced Wasserstein Kernels for Probability Distributions](https://mlsanity.com/paper/1511.03198/) (2015)
- [Projection Robust Wasserstein Distance and Riemannian Optimization](https://mlsanity.com/paper/2006.07458/) (2020)
- [Improving Mini-batch Optimal Transport via Partial Transportation](https://mlsanity.com/paper/2108.09645/) (2021)
- [Word Rotator's Distance](https://mlsanity.com/paper/2004.15003/) (2020)
- [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020)
- [Scalable Nearest Neighbor Search for Optimal Transport](https://mlsanity.com/paper/1910.04126/) (2019)
- [Learning to Match via Inverse Optimal Transport](https://mlsanity.com/paper/1802.03644/) (2018)
- [Fast Unbalanced Optimal Transport on a Tree](https://mlsanity.com/paper/2006.02703/) (2020)
- [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)
- [Principal Differences Analysis: Interpretable Characterization of Differences between Distributions](https://mlsanity.com/paper/1510.08956/) (2015)
- [Approximating 1-Wasserstein Distance between Persistence Diagrams by Graph Sparsification](https://mlsanity.com/paper/2110.14734/) (2021)

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

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [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)
- [Learning Ultrametric Trees for Optimal Transport Regression](https://mlsanity.com/paper/2210.12288/) (2022)
- [Learning Structured Representations by Embedding Class Hierarchy with Fast Optimal Transport](https://mlsanity.com/paper/2410.03052/) (2024)
- [Tree-Sliced Wasserstein Distance with Nonlinear Projection](https://mlsanity.com/paper/2505.00968/) (2025)
- [Fast unsupervised ground metric learning with tree-Wasserstein distance](https://mlsanity.com/paper/2411.07432/) (2024)
- [An Empirical Study of Self-supervised Learning with Wasserstein Distance](https://mlsanity.com/paper/2310.10143/) (2023)
- [Barycentric Fused Gromov-Wasserstein Balancing for Causal Inference under Multiple Treatments](https://mlsanity.com/paper/2608.22024/) (2026)

## Abstract (arXiv)

Wasserstein distance, which measures the discrepancy between distributions, shows efficacy in various types of natural language processing (NLP) and computer vision (CV) applications. One of the challenges in estimating Wasserstein distance is that it is computationally expensive and does not scale well for many distribution comparison tasks. In this paper, we aim to approximate the 1-Wasserstein distance by the tree-Wasserstein distance (TWD), where TWD is a 1-Wasserstein distance with tree-based embedding and can be computed in linear time with respect to the number of nodes on a tree. More specifically, we propose a simple yet efficient L1-regularized approach to learning the weights of the edges in a tree. To this end, we first show that the 1-Wasserstein approximation problem can be formulated as a distance approximation problem using the shortest path distance on a tree. We then show that the shortest path distance can be represented by a linear model and can be formulated as a Lasso-based regression problem. Owing to the convex formulation, we can obtain a globally optimal solution efficiently. Moreover, we propose a tree-sliced variant of these methods. Through experiments, we demonstrated that the weighted TWD can accurately approximate the original 1-Wasserstein distance.