The Unbalanced Gromov Wasserstein Distance: Conic Formulation and\n Relaxation

Abstract

Comparing metric measure spaces (i.e. a metric space endowed with\naprobability distribution) is at the heart of many machine learning problems.\nThe most popular distance between such metric measure spaces is\ntheGromov-Wasserstein (GW) distance, which is the solution of a quadratic\nassignment problem. The GW distance is however limited to the comparison of\nmetric measure spaces endowed with a probability distribution. To alleviate\nthis issue, we introduce two Unbalanced Gromov-Wasserstein formulations: a\ndistance and a more tractable upper-bounding relaxation.They both allow the\ncomparison of metric spaces equipped with arbitrary positive measures up to\nisometries. The first formulation is a positive and definite divergence based\non a relaxation of the mass conservation constraint using a novel type of\nquadratically-homogeneous divergence. This divergence works hand in hand with\nthe entropic regularization approach which is popular to solve large scale\noptimal transport problems. We show that the underlying non-convex optimization\nproblem can be efficiently tackled using a highly parallelizable and\nGPU-friendly iterative scheme. The second formulation is a distance between\nmm-spaces up to isometries based on a conic lifting. Lastly, we provide\nnumerical experiments onsynthetic examples and domain adaptation data with a\nPositive-Unlabeled learning task to highlight the salient features of the\nunbalanced divergence and its potential applications in ML.\n