The Ultrametric Gromov-Wasserstein Distance

We investigate compact ultrametric measure spaces which form a subset U(w )of the collection of all metric measure spaces M-w. In analogy with the notion of the ultrametric Gromov-Hausdorff distance on the collection of ultrametric spaces , we define ultrametric versions of two metrics on U-w, namely of Sturm's Gromov-Wasserstein distance of order p and of the Gromov-Wasserstein distance of order p. We study the basic topological and geometric properties of these distances as well as their relation and derive for p = infinity a polynomial time algorithm for their calculation. Further, several lower bounds for both distances are derived and some of our results are generalized to the case of finite ultra-dissimilarity spaces. Finally, we study the relation between the Gromov-Wasserstein distance and its ultrametric version (as well as the relation between the corresponding lower bounds) in simulations and apply our findings for phylogenetic tree shape comparisons.