Optimal transport is an increasingly popular tool to compare distributions or compute assignments for machine learning and statistical inference.
It takes advantage of the data's geometry, but suffers three limitations: (i) It is expensive to compute; (ii) it only compares probabilities; (iii) the distributions must be defined on the same space. Those restrictions are problematic to scale in applications, to discard geometric outliers, or to compare graphs with different structures. To alleviate each difficulty, it has been proposed to use entropic regularization, unbalanced optimal transport (UOT) and the Gromov-Wasserstein distance (GW). The goal of this presentation is to combine the above three ideas to define a new formulation called unbalanced Gromov-Wasserstein (UGW).

I first introduce the UOT formulation, and its entropically regularized version. I detail the Sinkhorn algorithm which solves the UOT problem on GPUs with a linear convergence. I then introduce the GW distance which is a non-convex quadratic assignment problem. It compares spaces equipped with a metric and a distribution, such as a graph with its geodesic distance and positive weights on nodes. I present two unbalanced extensions of this GW formulation. I show that the first one is a distance. The second one is computable on GPUs using entropic regularization by solving a sequence of regularized UOT problems. I end with ML experiments highlighting the applicability of UGW. If time permits, I will detail a new variant of Sinkhorn algorithm which accelerates the approximation of UOT and UGW.