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 general nonnegative measures. 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
Optimal Transport (OT) is a powerful framework for measuring distances between distributions, but it faces significant hurdles in real-world applications. Specifically, standard OT requires distributions to have equal total mass—a constraint often violated in practice (e.g., comparing documents of different lengths). Furthermore, the computational complexity of OT makes it difficult to scale to large datasets. While variants like Sliced Wasserstein (SW) offer speed improvements, they often sacrifice structural information by projecting data onto one-dimensional lines.
This paper introduces Entropy Partial Transport (EPT) on tree metrics to overcome these limitations. By utilizing the hierarchical structure of trees, the authors develop a method that is both computationally efficient and capable of handling measures with unequal mass.
Methodology
The Extended Tree Trick
The authors demonstrate that the EPT problem, which allows for mass variation, is mathematically equivalent to a standard OT problem on an "extended tree." By adding a dummy node to the tree structure, the model can effectively "soak up" or provide the necessary mass to balance the distributions, simplifying the optimization landscape.
Closed-Form Regularization
A major contribution of this work is the introduction of a novel regularization ($\widetilde{ET}_\lambda^\alpha$) for EPT. Unlike traditional unbalanced OT methods that rely on iterative algorithms like Sinkhorn, this regularized version yields a closed-form solution. This allows the distance to be calculated directly through simple arithmetic over the tree edges, leading to massive speedups—up to 81x in topological data analysis tasks.
Tree-Slicing and Kernels
To apply this to data without an inherent tree structure, the authors use "tree-slicing." They sample multiple random tree metrics from the data points and average the EPT results. This approach captures more structural nuance than 1D projections. Additionally, the authors prove that their regularized EPT is "negative definite," allowing it to be used directly in positive definite kernels for machine learning models like Support Vector Machines (SVMs).
Experimental Results
The proposed method was evaluated across various domains, including document classification (TWITTER, AMAZON) and Topological Data Analysis (TDA).
Approximation Quality and Robustness
Beyond computational efficiency, the regularized EPT provides high-fidelity approximations of the exact transport cost.
As shown in Figure 1, the approximation error (relative difference) decreases as the Lipschitz parameter increases, indicating that the regularized version can be tuned to closely match the exact EPT.
Furthermore, Figure 2 demonstrates that the approximation remains highly stable across different values of the mass penalty parameter $\lambda$. In these experiments, the relative difference remains near zero, suggesting that the closed-form solution is robust to the choice of $\lambda$.
Performance Highlights
- Speed: The method achieved an 11x speedup on the TWITTER dataset and an 81x speedup on the MPEG7 dataset compared to standard EPT.
- Accuracy: In TDA tasks, the tree-based approach significantly outperformed Sliced Partial Optimal Transport (SPOT), confirming that tree structures better preserve topological features than 1D lines.
Conclusion
By leveraging tree metrics and a novel closed-form regularization, this work provides a scalable and mathematically robust framework for unbalanced optimal transport. The ability to handle unequal mass while maintaining high computational efficiency and compatibility with kernel methods makes EPT a promising tool for large-scale machine learning applications.
Summary updated