Tree-Structured Optimal Transport

87 concepts56 papers1 proposal

Optimal Transport (OT) and the Wasserstein distance provide a geometrically meaningful way to compare probability distributions. By calculating the minimum cost required to transform one distribution into another, OT captures the underlying geometry of the data space. However, computing the exact Wasserstein distance traditionally requires solving a linear program with a cubic computational complexity of $O(N^3)$, where $N$ is the size of the distribution's support. Even regularized variants like the Sinkhorn algorithm scale quadratically ($O(N^2)$), introducing entropic bias and approximation noise that can degrade performance in downstream tasks.

To bypass this computational bottleneck, a powerful paradigm has emerged: tree-structured optimal transport. By embedding or projecting probability distributions onto a tree metric space, the global optimization problem collapses into a simple, exact, closed-form summation that scales linearly ($O(N)$) with the number of nodes.


The Core Intuition: Unique Paths and Mass Balance

To understand why trees fundamentally simplify optimal transport, imagine moving mass between nodes on a standard graph versus a tree. On a general graph or a Euclidean grid, mass can take infinitely many paths to reach its destination. Finding the optimal configuration requires a global optimization solver to evaluate and balance these competing routes.

On a tree, however, the geometry changes dramatically. Because a tree contains no loops, there is one and only one unique path between any two nodes.

       [ Root ]
       /      \
   [Node A]  [Node B]
     /
 [Subtree]

Because paths are unique, the optimal transport plan is entirely predetermined by the tree's topology. Consider any single edge in the tree. If we cut this edge, the tree splits into two disconnected components. Any probability mass that needs to travel from one component to the other must cross this specific edge. Therefore, the amount of mass that flows across an edge is exactly equal to the net difference between the total mass allocated to the subtree on one side of the edge and the total mass allocated to the rest of the tree.

As established by Le et al. in their seminal work on Tree-Sliced Variants of Wasserstein Distances, this structural property transforms the 1-Wasserstein distance into a weighted sum of absolute mass differences across all subtrees. Instead of optimizing a transport plan, the distance is computed via a single pass over the tree:

$$W_1(\alpha, \beta) = \sum_{e \in E} w_e |\alpha(T_e) - \beta(T_e)|$$

where $w_e$ is the weight of edge $e$, and $\alpha(T_e)$ and $\beta(T_e)$ represent the total probability mass contained within the subtree $T_e$ rooted below edge $e$ for distributions $\alpha$ and $\beta$.

This formulation reduces the computational complexity from cubic scaling to a linear-time operation relative to the number of tree nodes. As shown by Toyokuni et al. in Computationally Efficient Wasserstein Loss for Structured Labels, organizing data labels into a tree structure allows for the calculation of Wasserstein distances in linear time relative to the number of labels, making it highly scalable for large-scale classification tasks. Furthermore, Sando et al. demonstrate in Tree Structure for the Categorical Wasserstein Weisfeiler-Lehman Graph Kernel that exploiting this exact closed-form summation avoids the approximation noise and entropic bias inherent in iterative solvers like the Sinkhorn algorithm, preserving high classification accuracy while eliminating computational overhead.

This structural determinism also simplifies matching strategies. Houry et al. prove in Fast 1-Wasserstein distance approximations using greedy strategies that for distributions embedded in tree metrics or ultrametrics, a simple greedy matching strategy yields the exact optimal transport solution. This theoretical equivalence allows complex optimization to be replaced by an iterative matching process or even reduced to one-dimensional matching tasks, making the computational cost independent of the tree's depth.


Tree-Slicing: Extending to High Dimensions

While tree metrics offer massive computational advantages, real-world data rarely arrives neatly organized as a tree. To apply these benefits to high-dimensional continuous spaces, researchers use a technique called tree-slicing, inspired by the classic Sliced Wasserstein distance. While traditional slicing projects high-dimensional data onto simple one-dimensional lines, tree-slicing projects data onto complex, interconnected "tree systems."

Tran et al. demonstrate in Tree-Sliced Wasserstein Distance: A Geometric Perspective that tree metrics provide a tunable middle ground between the speed of linear slicing and the geometric accuracy of full-dimensional optimal transport. By capturing more complex topological information than 1D lines, tree-slicing preserves high-dimensional geometric structures while maintaining a closed-form solution.

This geometric flexibility has enabled rapid acceleration across several core machine learning tasks:

  • Barycenter Computation: Calculating the "average" of multiple probability distributions (the Wasserstein barycenter) is notoriously slow. Sato et al. introduce the Fixed Support Tree-Sliced Wasserstein Barycenter (FS-TSWB), leveraging the linear-time properties of tree-based distances to compute these averages up to 100x faster than standard methods while maintaining high approximation quality.
  • Non-Euclidean Spaces: Real-world data often exhibits hierarchical or non-Euclidean geometry. Pham et al. extend this paradigm to non-flat geometries in Mixed-Curvature Tree-Sliced Wasserstein Distance, projecting high-dimensional distributions onto tree metric systems to capture complex geometric features across mixed-curvature spaces with low computational complexity.
  • Smoother Optimization Landscapes: First-order transport metrics can suffer from optimization challenges like vanishing gradients. To address this, Tran et al. propose the Tree-sliced Sobolev IPM. By utilizing regularized Sobolev integral probability metrics on tree structures, they achieve the smoother optimization landscapes of higher-order metrics without incurring additional processing overhead.

Breaking the Curse of Dimensionality in Complex Transport Problems

The linear-time properties of tree metrics become even more vital when moving beyond standard balanced optimal transport. When dealing with noisy datasets, outliers, or multi-distribution coordination, standard optimal transport scales poorly. Tree structures offer a mathematical escape hatch.

Unbalanced and Partial Transport

Standard OT requires both distributions to have the exact same total mass. When comparing datasets of different sizes or ignoring outliers, we turn to Unbalanced Optimal Transport (UOT) or Partial Optimal Transport.

Sato et al. show in Fast Unbalanced Optimal Transport on a Tree that utilizing tree metrics for UOT allows for quasi-linear time complexity, enabling the processing of million-scale datasets in under one second. To handle mass imbalances analytically, Tran et al. demonstrate in Tree-Sliced Entropy Partial Transport that partial transport problems on tree-metric spaces can be mathematically reduced to standard balanced optimal transport by introducing a virtual auxiliary node to collect discarded mass, allowing for efficient closed-form calculations.

Similarly, Le et al. prove in Entropy Partial Transport with Tree Metrics: Theory and Practice that applying specific entropic regularization to partial transport on tree structures enables a closed-form solution calculated via simple summation over edges, bypassing iterative solvers like Sinkhorn and reaching speedups up to 81 times faster.

Multi-Marginal Optimal Transport

Multi-marginal Optimal Transport (MOT) extends transport theory to coordinate many distributions simultaneously, but it is traditionally plagued by an exponential "curse of dimensionality" relative to the number of marginals.

Fan breaks this bottleneck in On the complexity of the optimal transport problem with graph-structured cost, proving that constraining the cost functions to a tree structure reduces the computational complexity from exponential to strictly linear relative to the number of marginals.

This structural acceleration is highly practical for tracking populations over time. As shown by Singh et al. in Inference With Aggregate Data in Probabilistic Graphical Models: An Optimal Transport Approach, exploiting the tree structure of graphical models within multi-marginal optimal transport reduces the projection complexity from exponential to linear with respect to the number of nodes, making aggregate tracking entirely independent of the total population size. This framework is mirrored by Zha et al. in Estimating Latent Population Flows from Aggregated Data via Inversing Multi-Marginal Optimal Transport, where constraining the cost tensor to a tree-structured graphical model allows for the efficient computation of latent population flows across consecutive time steps.


Designing and Learning the Underlying Trees

The performance and accuracy of tree-structured OT depend heavily on the quality of the tree itself. If the tree structure distorts the true underlying distances between data points, the resulting transport calculations will be inaccurate. Researchers have developed several strategies to build, learn, and optimize these trees.

Supervised and Unsupervised Metric Learning

Instead of relying on rigid, hand-crafted hierarchies, trees can be learned directly from data. Sato et al. introduce a supervised approach in Supervised Tree-Wasserstein Distance, making the tree-building process fully differentiable and optimizing it via a contrastive loss. Formulating these tree-based approximations as matrix multiplications makes them highly amenable to GPU acceleration and batch processing.

For scenarios where labeled data is unavailable, Düsterwald et al. develop Fast unsupervised ground metric learning with tree-Wasserstein distance. By embedding features as leaves on a tree structure where the distance between points is defined by the sum of edge weights along their unique path, they reduce the computational complexity of ground metric learning from quadratic to linear scales, enabling unsupervised metric learning on massive biological datasets like single-cell genomics.

Hierarchical Representation Learning

Trees can also be co-designed alongside the data representations themselves. Lin et al. propose an unsupervised framework in Joint Hierarchical Representation Learning of Samples and Features via Informed Tree-Wasserstein Distance that uses Tree-Wasserstein Distance combined with adaptive Haar wavelet filtering to jointly learn hierarchical structures for both samples and features. This approach incorporates hierarchical priors directly into distance measurements, capturing the nested relationships within high-dimensional datasets. This builds on the foundational concepts of Mishne et al. in Data-Driven Tree Transforms and Metrics, which calculate high-dimensional distance by comparing how data values are distributed across the nodes of an iteratively constructed hierarchical partition tree.

Decoupling Flow from Cost

A major challenge in tree embeddings is that forcing a high-dimensional space into a tree structure inevitably introduces geometric distortion. To combat this, Backurs et al. introduce a clever algorithmic decoupling in Scalable Nearest Neighbor Search for Optimal Transport through their algorithm, Flowtree.

[Step 1: Tree Structure] ----> Proposes an Optimal Transport Plan (Linear Time)
                                      |
                                      v
[Step 2: Original Metric] ---> Evaluates the Plan's Cost (Preserves Geometry)

Instead of using the tree to calculate the final cost, Flowtree uses a hierarchical tree structure solely to suggest a candidate transport plan (an optimal flow). Once the plan is found in linear time, the algorithm evaluates the actual cost of that plan using the original ground metric. By separating the determination of the flow from the calculation of its cost, Flowtree reclaims the geometric information lost during tree construction, achieving the speed of linear-time tree methods with the precision of quadratic-time algorithms.

Key Foundational Work

The Phylogenetic Kantorovich–Rubinstein Metric for Environmental Sequence Samples (2012) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_tree_based_optimal_transport_approximati_8ed3fc67_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake