# Optimal Transport for Measures with Noisy Tree Metric arXiv: https://arxiv.org/abs/2310.13653 ยท HTML: https://mlsanity.com/paper/2310.13653/ ## Key facts - Cited by 7 papers in the map (data through 14 Oct 2026). - Builds on 47 of its 82 references that are in the map. - First posted on arXiv 20 Oct 2023. ## Builds on (most cited first, 30 of 47) - [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018) - [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017) - [Persistence Images: A Stable Vector Representation of Persistent Homology](https://mlsanity.com/paper/1507.06217/) (2015) - [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018) - [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021) - [Max-Sliced Wasserstein Distance and its use for GANs](https://mlsanity.com/paper/1904.05877/) (2019) - [Missing Data Imputation using Optimal Transport](https://mlsanity.com/paper/2002.03860/) (2020) - [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022) - [Proximal Optimal Transport Modeling of Population Dynamics](https://mlsanity.com/paper/2106.06345/) (2021) - [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019) - [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020) - [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019) - [Sliced Wasserstein Kernel for Persistence Diagrams](https://mlsanity.com/paper/1706.03358/) (2017) - [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021) - [Sliced Wasserstein Kernels for Probability Distributions](https://mlsanity.com/paper/1511.03198/) (2015) - [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019) - [Learning Generative Models across Incomparable Spaces](https://mlsanity.com/paper/1905.05461/) (2019) - [Point-set Distances for Learning Representations of 3D Point Clouds](https://mlsanity.com/paper/2102.04014/) (2021) - [Projection Robust Wasserstein Distance and Riemannian Optimization](https://mlsanity.com/paper/2006.07458/) (2020) - [Outlier-Robust Optimal Transport](https://mlsanity.com/paper/2012.07363/) (2020) - [Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance](https://mlsanity.com/paper/1906.04516/) (2019) - [Energy-Based Sliced Wasserstein Distance](https://mlsanity.com/paper/2304.13586/) (2023) - [Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams](https://mlsanity.com/paper/1802.03569/) (2018) - [Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent](https://mlsanity.com/paper/2106.08502/) (2021) - [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017) - [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020) - [On Robust Optimal Transport: Computational Complexity and Barycenter Computation](https://mlsanity.com/paper/2102.06857/) (2021) - [Statistical Analysis of Wasserstein Distributionally Robust Estimators](https://mlsanity.com/paper/2108.02120/) (2021) - [Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Analysis](https://mlsanity.com/paper/2111.01361/) (2021) - [Bending Graphs: Hierarchical Shape Matching using Gated Optimal Transport](https://mlsanity.com/paper/2202.01537/) (2022) ## Built on by (most cited first, 7 of 7) - [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024) - [Tree-Sliced Wasserstein Distance: A Geometric Perspective](https://mlsanity.com/paper/2406.13725/) (2024) - [Scalable Counterfactual Distribution Estimation in Multivariate Causal Models](https://mlsanity.com/paper/2311.00927/) (2023) - [Tree-Sliced Wasserstein Distance with Nonlinear Projection](https://mlsanity.com/paper/2505.00968/) (2025) - [SAVA: Scalable Learning-Agnostic Data Valuation](https://mlsanity.com/paper/2406.01130/) (2024) - [An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph](https://mlsanity.com/paper/2502.00739/) (2025) - [From Cone Geometry to Monge Structure: Local Defects and Global Regret in High-Dimensional Optimal Transport](https://mlsanity.com/paper/2606.04695/) (2026) ## Abstract (arXiv) We study optimal transport (OT) problem for probability measures supported on a tree metric space. It is known that such OT problem (i.e., tree-Wasserstein (TW)) admits a closed-form expression, but depends fundamentally on the underlying tree structure over supports of input measures. In practice, the given tree structure may be, however, perturbed due to noisy or adversarial measurements. To mitigate this issue, we follow the max-min robust OT approach which considers the maximal possible distances between two input measures over an uncertainty set of tree metrics. In general, this approach is hard to compute, even for measures supported in one-dimensional space, due to its non-convexity and non-smoothness which hinders its practical applications, especially for large-scale settings. In this work, we propose novel uncertainty sets of tree metrics from the lens of edge deletion/addition which covers a diversity of tree structures in an elegant framework. Consequently, by building upon the proposed uncertainty sets, and leveraging the tree structure over supports, we show that the robust OT also admits a closed-form expression for a fast computation as its counterpart standard OT (i.e., TW). Furthermore, we demonstrate that the robust OT satisfies the metric property and is negative definite. We then exploit its negative definiteness to propose positive definite kernels and test them in several simulations on various real-world datasets on document classification and topological data analysis.