Efficient Solvers for Partial Gromov-Wasserstein
Yikun Bai Rocio Diaz Martin Hengrong Du Ashkan Shahbazi Soheil Kolouri
The partial Gromov-Wasserstein (PGW) problem facilitates the comparison of
measures with unequal masses residing in potentially distinct metric spaces,
thereby enabling unbalanced and partial matching across these spaces. In this
paper, we demonstrate that the PGW problem can be transformed into a variant of
the Gromov-Wasserstein problem, akin to the conversion of the partial optimal
transport problem into an optimal transport problem. This transformation leads
to two new solvers, mathematically and computationally equivalent, based on the
Frank-Wolfe algorithm, that provide efficient solutions to the PGW problem. We
further establish that the PGW problem constitutes a metric for metric measure
spaces. Finally, we validate the effectiveness of our proposed solvers in terms
of computation time and performance on shape-matching and positive-unlabeled
learning problems, comparing them against existing baselines.