Abstract
Optimal transport (OT) theory provides powerful tools to compare probability measures. However, OT is limited to nonnegative measures having the same mass, and suffers serious drawbacks about its computation and statistics. This leads to several proposals of regularized variants of OT in the recent literature. In this work, we consider an entropy partial transport (EPT) problem for nonnegative measures on a tree having different masses. The EPT is shown to be equivalent to a standard complete OT problem on a one-node extended tree. We derive its dual formulation, then leverage this to propose a novel regularization for EPT which admits fast computation and negative definiteness. To our knowledge, the proposed regularized EPT is the first approach that yields a closed-form solution among available variants of unbalanced OT. For practical applications without prior knowledge about the tree structure for measures, we propose tree-sliced variants of the regularized EPT, computed by averaging the regularized EPT between these measures using random tree metrics, built adaptively from support data points. Exploiting the negative definiteness of our regularized EPT, we introduce a positive definite kernel, and evaluate it against other baselines on benchmark tasks such as document classification with word embedding and topological data analysis. In addition, we empirically demonstrate that our regularization also provides effective approximations.
Introduction: The Challenge of Unbalanced Data
Optimal Transport (OT) is a cornerstone of modern data science, providing a robust mathematical framework for measuring distances between probability distributions. However, standard OT comes with a significant constraint: it requires the distributions being compared to have the exact same total mass. In real-world scenarios, such as comparing documents of varying lengths or persistence diagrams in topological data analysis, this assumption rarely holds.
To address this, researchers have developed "Unbalanced Optimal Transport" (UOT) or "Partial Optimal Transport" (POT), which allows for mass to be created or destroyed at a specific cost. While theoretically sound, these methods are often computationally prohibitive—requiring quadratic complexity—or rely on simplistic 1D projections that fail to capture the intricate geometry of high-dimensional data. This research introduces a middle ground: a method that is both computationally efficient and structurally rich by leveraging tree metrics.
Methodology: Leveraging Tree Structures
The core innovation of this work lies in the use of Tree Metrics. By assuming data points reside on a tree structure rather than a flat Euclidean space, the geometry of the problem is significantly simplified. The authors introduce three key technical contributions:
- The Extended Tree Trick: They prove that the EPT problem on a tree is mathematically equivalent to a standard OT problem on a tree extended by a single "virtual" reservoir node to handle excess mass.
- Closed-Form Regularization: Unlike traditional "Sinkhorn" regularizations that require iterative optimization, the authors propose a novel regularization that yields a closed-form solution. This allows distances to be calculated directly via a single formula involving simple absolute differences across tree branches.
- Tree-Slicing: To handle data where the underlying tree structure is unknown, the authors employ "tree-slicing." They sample multiple random tree metrics from the data and average the results, capturing complex structures more effectively than 1D projections.
Key Results: Speed and Accuracy
The proposed regularized EPT was evaluated across several domains, including Natural Language Processing (NLP) for document classification and Topological Data Analysis (TDA) for persistence diagrams.
Computational Efficiency
The most striking result is the speedup achieved. By moving from iterative optimization to a closed-form summation, the method is significantly faster than standard EPT (Kantorovich-Hellinger distance). In document classification tasks, the method was approximately 11x faster, while in TDA tasks, it achieved up to an 81x speedup.
Accuracy and Kernel Performance
Despite the massive gains in speed, the method maintains or exceeds the accuracy of state-of-the-art baselines like Sinkhorn-UOT and Sliced Partial Optimal Transport (SPOT). Furthermore, the authors proved that their proposed distance is "negative definite." This property is crucial for machine learning as it allows the distance to be used in standard Exponential Kernels to create Positive Definite Kernels. These kernels can be plugged directly into Support Vector Machines (SVMs) without the numerical "hacks" often required by other unbalanced OT methods.
Conclusion
By combining the structural flexibility of tree metrics with a novel closed-form regularization, this work provides a highly efficient path for comparing measures of different sizes. The resulting method is not only orders of magnitude faster than existing iterative approaches but also theoretically grounded, offering a positive definite kernel that performs robustly across diverse machine learning tasks. Future work may further refine tree sampling techniques to better capture data geometry while minimizing quantization effects.
Summary updated