# Fast unsupervised ground metric learning with tree-Wasserstein distance

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 11 Nov 2024.

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

- [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)
- [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)
- [Inverse optimal transport](https://mlsanity.com/paper/1905.03950/) (2019)
- [Learning to Match via Inverse Optimal Transport](https://mlsanity.com/paper/1802.03644/) (2018)
- [Regularized Optimal Transport is Ground Cost Adversarial](https://mlsanity.com/paper/2002.03967/) (2020)
- [Fast Robust PCA on Graphs](https://mlsanity.com/paper/1507.08173/) (2015)
- [Supervised Tree-Wasserstein Distance](https://mlsanity.com/paper/2101.11520/) (2021)
- [Approximating 1-Wasserstein Distance with Trees](https://mlsanity.com/paper/2206.12116/) (2022)
- [The Gene Mover's Distance: Single-cell similarity via Optimal Transport](https://mlsanity.com/paper/2102.01218/) (2021)
- [Data-Driven Tree Transforms and Metrics](https://mlsanity.com/paper/1708.05768/) (2017)
- [Unsupervised Ground Metric Learning using Wasserstein Singular Vectors](https://mlsanity.com/paper/2102.06278/) (2021)
- [Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance](https://mlsanity.com/paper/2107.12334/) (2021)

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

- [Unsupervised Ground Metric Learning](https://mlsanity.com/paper/2507.13094/) (2025)

## Abstract (arXiv)

The performance of unsupervised methods such as clustering depends on the choice of distance metric between features, or ground metric. Commonly, ground metrics are decided with heuristics or learned via supervised algorithms. However, since many interesting datasets are unlabelled, unsupervised ground metric learning approaches have been introduced. One promising option employs Wasserstein singular vectors (WSVs), which emerge when computing optimal transport distances between features and samples simultaneously. WSVs are effective, but can be prohibitively computationally expensive in some applications: O(n2m2(n log(n) + m log(m)) for n samples and m features. In this work, we propose to augment the WSV method by embedding samples and features on trees, on which we compute the tree-Wasserstein distance (TWD). We demonstrate theoretically and empirically that the algorithm converges to a better approximation of the standard WSV approach than the best known alternatives, and does so with O(n3+m3+mn) complexity. In addition, we prove that the initial tree structure can be chosen flexibly, since tree geometry does not constrain the richness of the approximation up to the number of edge weights. This proof suggests a fast and recursive algorithm for computing the tree parameter basis set, which we find crucial to realising the efficiency gains at scale. Finally, we employ the tree-WSV algorithm to several single-cell RNA sequencing genomics datasets, demonstrating its scalability and utility for unsupervised cell-type clustering problems. These results poise unsupervised ground metric learning with TWD as a low-rank approximation of WSV with the potential for widespread application.