Tree Metrics for Scalable Optimal Transport

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 269 papers102 conceptsfrozen 2026-10-04

Optimal Transport (OT), specifically the Wasserstein distance, is a powerful tool for comparing probability distributions because it accounts for the underlying geometry of the data. However, calculating the exact Wasserstein distance is computationally expensive, typically scaling cubically ($O(N^3)$) with the number of data points. This "computational tax" has long restricted OT to small-scale problems.

A growing body of research has found a way to bypass this bottleneck: by restricting the ground metric to a tree structure, the complex optimization problem of OT collapses into a simple, linear-time summation.

The Intuition: Unique Paths and Mass Differences

In a general metric space, moving mass from point A to point B involves finding the shortest path among infinitely many possibilities. On a tree, however, there is exactly one unique path between any two nodes. This structural constraint simplifies the transport problem fundamentally.

As Steven N. Evans demonstrated in The phylogenetic Kantorovich-Rubinstein metric for environmental sequence samples, the distance between two distributions on a tree is equivalent to the weighted sum of mass differences across all edges. To move mass from one side of the tree to the other, it must pass through the edges connecting the subtrees. Therefore, the total "work" required is simply the absolute difference in mass between the two distributions for every subtree, multiplied by the length of the edge connecting that subtree to the rest of the tree.

This transformation turns an optimization problem into a single pass over the tree. Researchers like Ayato Toyokuni and Makoto Yamada have leveraged this to create Computationally Efficient Wasserstein Loss for Structured Labels, reducing the complexity of comparing large-scale label hierarchies from quadratic to linear.

Tree-Slicing: Beyond One Dimension

Standard Sliced Wasserstein (SW) distances work by projecting high-dimensional data onto random one-dimensional lines. While fast, 1D projections often fail to capture complex topological structures.

Tam Le and Marco Cuturi introduced Tree-Sliced Variants of Wasserstein Distances to bridge this gap. Instead of lines, they project data onto tree structures. This "Tree-Sliced" approach maintains the closed-form efficiency of 1D slicing but offers a much richer geometric representation. Recent extensions by Hoang V. Tran and colleagues have even adapted this to Spherical Tree-Sliced Wasserstein Distance, allowing for efficient comparison of distributions on hyperspheres.

Learning the Tree Structure

The effectiveness of Tree-Wasserstein Distance (TWD) depends heavily on how well the tree represents the data's actual geometry. While some fields have natural trees (like phylogenetics in biology or financial hierarchies in An Earth Mover’s Distance Based Graph Distance Metric For Financial Statements), others require learning the tree from scratch.

Samantha Chen and Yusu Wang proposed Learning Ultrametric Trees for Optimal Transport Regression, which optimizes tree topology and edge weights to approximate the true Wasserstein distance. Similarly, Ya-Wei Eileen Lin and Ronen Talmon developed methods to learn Latent Feature Hierarchies, treating the tree as a fundamental model of the feature space rather than just a computational shortcut.

Scaling to Millions

The practical impact of this research is most visible in large-scale search and retrieval. By mapping distributions to tree-based embeddings, the Wasserstein distance can be approximated as a simple $L_1$ distance between vectors.

Cléa Laouar and Makoto Yamada demonstrated in Large-scale similarity search with Optimal Transport that this approach is three orders of magnitude faster than traditional methods, making semantic document search viable for millions of records. In the domain of graph matching, Nils M. Kriege and Franka Bause showed that Computing Optimal Assignments in Linear Time is possible if costs follow a tree metric, enabling graph similarity searches that were previously computationally prohibitive.

By trading the flexibility of general metric spaces for the structured efficiency of trees, this research direction has transformed Optimal Transport from a theoretical luxury into a scalable tool for high-dimensional data analysis.

Papers in this version

Showing 60 of 69 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 57 papers
  2. Version 1 · 2026-10-04 · 69 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_tree_based_optimal_transport_approximati_8ed3fc67,
  title = {tree-based optimal transport approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tree-based-optimal-transport-approximation/rdr_8ed3fc679f09492dbe316b647886bf6a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tree_metrics_for_scalable_optimal_transp_8ed3fc67_v1,
  title = {Tree Metrics for Scalable Optimal Transport},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tree-metrics-for-scalable-optimal-transport/rdr_8ed3fc679f09492dbe316b647886bf6a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}