Comparing high-dimensional probability distributions is a fundamental challenge in modern machine learning. Whether evaluating the fidelity of a generative model or measuring the distance between two massive datasets, we often rely on the Wasserstein distance (or "Earth Mover's Distance"). While mathematically elegant, the Wasserstein distance is computationally punishing, scaling cubically with the number of data points.
To bypass this "curse of dimensionality," researchers often turn to Sliced Optimal Transport (SOT). As Khai Nguyen explains in An Introduction to Sliced Optimal Transport, SOT breaks a complex high-dimensional problem into a collection of simple one-dimensional tasks. By projecting data onto a 1D line, the optimal transport problem gains a closed-form solution that can be solved simply by sorting.
The Information Gap in Linear Projections
The speed of 1D slicing comes at a cost: topological blindness. When we project a complex manifold—like a dataset with holes, clusters, or entanglements—onto a single line, that structure often collapses. Tao Li and colleagues note in Hilbert Curve Projection Distance for Distribution Comparison that linear projections frequently fail to preserve local geometric structures, causing distinct neighborhoods to overlap and smear out.
This loss of information is more than a theoretical nuisance. In TopP&R: Robust Support Estimation Approach for Evaluating Fidelity and Diversity in Generative Models, Pum Jun Kim and Jaejun Yoo demonstrate that random linear projections can obscure the subtle geometric relationships needed to distinguish high-quality generative samples from "topological noise."
From Lines to Trees
To bridge the gap between the speed of 1D slicing and the structural richness of full Optimal Transport, a new family of metrics has emerged: Tree-Sliced Wasserstein (TSW) distances.
The intuition is straightforward: instead of projecting data onto a single, rigid line, we project it onto a "tree system"—an interconnected network of lines that can branch and bend to follow the data's natural shape. In Tree-Sliced Wasserstein Distance: A Geometric Perspective, Hoang V. Tran and Tam Le show that these tree structures capture complex high-dimensional topologies that 1D projections miss, all while maintaining the computational efficiency of a closed-form solution.
By using trees, the metric can account for the "branching" nuances of a manifold. This makes the distance calculation invariant to certain transformations and much more sensitive to the underlying geometry. Hoang V. Tran further refined this in Distance-Based Tree-Sliced Wasserstein Distance by introducing "splitting maps" that consider the actual distance between data points and projection lines, ensuring the metric remains robust under Euclidean rotations and translations.
Adapting to Non-Euclidean Geometry
Real-world data rarely lives in a flat, Euclidean world. It often clusters on spheres (like global weather data) or follows hyperbolic branching patterns (like hierarchical taxonomies). Standard slicing methods struggle here because a straight line is a poor fit for a curved space.
Recent work has extended the tree-slicing paradigm to these non-Euclidean domains:
- Spheres: In Spherical Tree-Sliced Wasserstein Distance, Hoang V. Tran and Thanh Chu project data onto "spherical trees," allowing for fast distribution comparison on hyperspheres without losing the circular continuity of the space.
- Mixed Curvatures: Duy-Tung Pham and Tan Minh Nguyen introduced the Mixed-Curvature Tree-Sliced Wasserstein Distance, which handles manifolds that combine different geometric properties, ensuring that the "slicing" respects the intrinsic curvature of the data.
Robustness and Scale
Beyond capturing shape, tree-based methods are proving highly effective at handling the "messiness" of real data. Tree-Sliced Entropy Partial Transport by Hoang V. Tran and Thanh Tran combines tree projections with "partial transport" logic. This allows the metric to ignore outliers and compare datasets of different sizes—a common requirement in transfer learning.
The ultimate goal of this research direction is "lightspeed" comparison. As Nhat Ho and Khai Nguyen demonstrate with s-OTDD, by choosing the right projection transforms, we can reduce the comparison of massive, high-dimensional datasets to near-linear time operations. By moving from simple lines to structured trees, we no longer have to choose between the speed of slicing and the accuracy of full geometric analysis.