Optimal Transport for Measures with Noisy Tree Metric

We study optimal transport (OT) problem for probability measures supported on a tree metric space. It is known that such OT problem admits a closed-form expression, but depends fundamentally on the underlying tree structure of supports of input measures. In practice, the given tree structure may be, however, perturbed due to noisy or adversarial measurements. In order to mitigate this issue, we follow the max-min robust OT approach which considers the maximal possible distances between two input probability measures over an uncertainty set of tree metrics. In general, this robust OT approach is notoriously hard to compute due to its non-convexity and non-smoothness which hinders its practical applications, especially for large-scale settings. In this work, we propose \emph{novel uncertainty sets of tree metrics} from the lens of edge deletion/addition which covers a diversity of tree structures. Consequently, by building upon the proposed uncertainty sets, and leveraging the tree structure over supports, we show that the max-min robust OT also admits a closed-form expression which is scalable for large-scale applications. Furthermore, we demonstrate that the max-min robust OT satisfies the metric property and is negative definite. We then exploit its negative definiteness to propose positive definite \emph{kernels} and test them in several simulations on document classification and topological data analysis for measures on a tree.