The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
Authors: Thibault Sejourne
François-Xavier Vialard
Gabriel Peyré
Venue: NeurIPS 2021 Poster (2021)
Keywords: Optimal transport
Quadratic assignment problem
Gromov-Wasserstein

Abstract: Comparing metric measure spaces (i.e. a metric space endowed with a probability distribution) is at the heart of many machine learning problems. The most popular distance between such metric measure spaces is the Gromov-Wasserstein (GW) distance, which is the solution of a quadratic assignment problem. The GW distance is however limited to the comparison of metric measure spaces endowed with a \emph{probability} distribution. To alleviate this issue, we introduce two Unbalanced Gromov-Wasserstein formulations: a distance and a more tractable upper-bounding relaxation.  They both allow the comparison of metric spaces equipped with arbitrary positive measures up to isometries. The first formulation is a positive and definite divergence based on a relaxation of the mass conservation constraint using a novel type of quadratically-homogeneous divergence. This divergence works hand in hand with the entropic regularization approach which is popular to solve large scale optimal transport problems. We show that the underlying non-convex optimization problem can be efficiently tackled using a highly parallelizable and GPU-friendly iterative scheme. The second formulation is a distance between mm-spaces up to isometries based on a conic lifting.  Lastly, we provide numerical experiments on synthetic and domain adaptation data with a Positive-Unlabeled learning task to highlight the salient features of the unbalanced divergence and its potential applications in ML.

The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation
Thibault Séjourné
Françuis-Xaviee Vialard
Ecole Normale Supérieure, DMA, PSL thibault. sejourne@ens.
Université Gustave Eiffel
francois-xave vialardeu-pen.tr
Gabriel Peyré
Ecole Normale Supérieure, DMA, CNRS, PSL gabriel. peyreeens..eeeeeeeee.
Abstract
Comparing metric measure spaces (i.e. a metric space endowed with a probability distribution) is at the heart of many machine learning problems. The most popular distance between such metric measure spaces is the Maanov-Wssssetteinn (GW) distance, which the solution of a quadratic assignment problem. The GW dis- tance is however limited to the comparison of metric measure spaces endowed with probability distribution. To alleviate this issue, introduce Unbalanced in formulations: a distance and more tractable upper- bouud-bonndig relaxation. They both allow the comparison of metric spaces equipped with bitrary positive measures to isometries. The first formulation is positive and definite divergence based on a relaxation of the mass conservation constraint using a novel type of works hand hand with the entropic regularization approach which is popular to solve large scale optimal transport problems. We show that the underlying non-convex optimization problem can be efficiently tackled using a highly paral- lelizable and GPU-friendly iterative scheme. The second formulation is a distance between mm-spaces up to isometries based on conic lifting. Lastly, we provide numerical experiments synthetic examples and domain adaptation data with a Positive-Unie Unlabeled learning task to highlight the salient features the unbalanced divergence and its potential applications in ML.
sooatiicllly-omooneeeouu divergence. This divergence
1 Introduction
Comparing data distributions on different metric spaces is basic problem in machine learning. This class of problems is for instance at the heart of surfaces [Bronstein et al. 2006) or graph matching (Xu al. 2019 (equipping the surface graph with its associated geodesic distance), regression problems in quantum chemistry [Gilmer et al. 20177) (viewing the molccules as distributions points R3)
and natural language processing [Grave et al. 2019 Alvarez-Melis and Jaakkola 2018 (where texts in different languages are embedded as points distributions in different vector spaces).
Metric measure spaces. The mathematical way to formalize these problems is to model the data as metric measure spaces (mm-spaces). A mm-space is denoted as X' = (X, xdd,, n1) where X is complete separable set endowed with a distance and positive Borel measure μ E M+ For instance, if X (xt); is finite set of points, then J Σ; m,dz; (here òz; is the Dirac mass 2;) is simply set positive weights m, = (((x,}) 2 associated to each point I,, which accounts for its mass importance. For instance, setting some m; to 0 is equivalent to removing the point 2;. We
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

refer to Sturm 2012 for mathematical account on the theory of mmm-mmmmaee spaces. In all the applications highlighted above, makes sense to perform the comparisons up to isometric transformations of the data. Two mm-spaces X' = (X, dx. 11) and y = (Y, dy, v) are considered to be equal (denoted X' 3/) if they are isometric, meaning that there a bijection to : spt( - spt(()) (where spt((u) is the support of (t) such that dx(x2, y) dy (1)(2) (v()) and 2///1 = v. Here 1/ is the push-forward operator, so that Wyf v/ is equivalent to imposing (AA = (A)) for any set A C Y. For discrete spaces where μ = E; m.dz,,, then one should have V/ dap E, m.dy(a,)) As highlighted by M (201T), considering mm mm-spaces up to isometry is a powerful way to formalize and analyze a wide variety of problems such as matching, regression and classification of distributions of points belonging to different spaces. Most often, the objects of interest come with a natural distance such as an intrinsic or extrinsic distance and the uniform measure is the usual choice to make mm-spaces widely applicable. The key to unlock all these problems is the computation of a distance between mm-spaces up to isometry. So far, existing distances (reviewed below) assume that μ is a probability distribution, i.c. (xX) 1. This constraint is not natural and sometimes problematic for most of the practical applications to machine learning. The goal of this paper is to alleviate this restriction. We define for the first time class of distances between unbalanced metric measure spaces, these distances being upper-bounder by divergences which can be approximated by an efficient numerical scheme.
Csiszár divergences The simplest case is when X = Y and one simply ignores the underlying metric. One can then use Csiszár divergences (or g-divergences), which perform pointwise comparison (in contrast with optimal transport distances, which perform a displacement comparison). It is defined using an entropy function ş : R + [0, +oo], which is a convex, lower semi-continu- ous, positive function with (11) = 0. The Csiszár p-divergence reads (u(p)) -
fx p d dv + du y + 1 is called the Sadon-Nikodye or the Lebesgue decomposition
&o fx du++, where of ja with respect to V/ and 4/ = lim,- =(r)/r E TR J [+oc] is called the recession constant. This divergence D. is convex, positive, 1-homogeneous and weak lower-semicontinuous, see Liero et al. 2015) for details. Particular instances of p--divergences are Kullback-Leibler (KL) for (r(r)
du
log T + 1 (note that 4 = oo) and Total Variation (TV) for (p(r) = -Ir- 1/.
Balanced and unbalanced optimal transport. If the common embedding space X is equipped with distance d(xr, y). one can use more elaborated methods such optimal transport (OT) distances, which are computed by solving convex optimization problems. This type of methods has proven useful for ML problems as diverse as domain adaptation [Courty et al.! 2014), supervised learning over histograms [Frogner et al. 2013] and unsupervised learning of generative models Arrovssy et al. 2017]. In this case, the extension from probability distributions to arbitrary positive measures (/u, v) e M x)2 is now well understood and corresponds to the theory of unbalanced OT. Following Liero ct al. 2015), Chizat et al. [2018a]. a family of unbalanced Wasserstein distances is defined by solving
/ Md(zz y))dd(Z v) - D (m( + (T2ll)))
p),
inf x xxM(xxx)
(I)
Here (M1, R2) are the two marginals of the joint distribution n, defined by m (A) a(A x Y) for A C X. The mapping À : IR+ + IR and exponent q 2 1 should be chosen wisely to ensure for instance that UW defines a distance (see Section 2.2.1) p. is frequent to take pD. instead of D. (i.e. take //- = pT) to adjust the strength of the marginals penalization. Balanced OT is retrieved with the convex indicator 3 4t (i.e. ((1) 0 and (<x)) +oo otherwise) or by taking the limit + +00, which enforces T1 = au and T2 v. When 0 p < +00, unbalanced OT operates a trade-off between transportation and creation of mass, which is crucial to be robust to outliers in the data and to cope with mass variations in the modes of the distributions. For supervised tasks, the value of p should be cross-validated obtain the best performances. Its use gaining popularity in applications, such as medical imaging registration [Feydy et al.) 2019a]. videos [Lee et al., 2019]. generative learning [Balaji et al. 2020) and gradient flow to train neural networks [Chizat and Bach 2018 Rotskoff et al. 2019]. Furthermore, existing efficient algorithms for balanced OT extend to this unbalanced problem. In particular Sinkhorn's 's iterations, introduced ML for balanced OT by Cuturi
2013), extend to unbalanced OT [Chizat et al. 201 8b) Séjourné et al. 2019), as detailed in Section 3
The Gromoy- Wasserstens distance and its applications. The Gromov- Wasserseen (GW) dis-
tance [Mémoli 2011 1 Sturm 2012) generalizes the notion of OT to the setting of mm-spaces up to

---

isometries. It replaces the linear cost f X(d)dT of OT by a quadratic function. It reads
GW(X - min
{ X(dxx(x, x/) dy (lld v))
Ti p
(2)
(XX)(Xx))
22
It is proved in Mémoli (2011]. Sturm [2012] that GW defines with X(t) = to distance up to isometries on balanced spanssaces (1.e. the measures are probability distributions). The GW distance is applied successfully in natural language processing for unsupervised translation learning (rrave al. 2019 Alvarez- Melis and Jaakkola, 2018], in generative learning for objects lying spaces of different dimensions [Bunne et al. [019] and to build VAE for graphs (Xu et al. [020]. It has been adapted for domain adaptation over different spaces [Redko et al.) 2020) It is also relevant distance to compute barycenters between graphs shapes [Vayer al. 2018 Chowdhury and Needham 2020]. When (X' 3) are Euclidean spaces, this distance compares distributions up to rigid isometry, and is closely related (but not equal) to metrics defined by procrustes analysis [Grave et al. 2019 Alvarez- et al., 2019]. The problem (2 is non convex because the quadratic form X( M[dx- dy |d @ π is not positive in general. It is in fact closely related to quadratic assignment problems Burkard et al., 1998), which are used for graph matching problems, and are known to be NP-hard in general. Nevertheless, non-convex optimization methods have been shown to be successful in practice to use GW distances for MI. problems. This includes for instance alternating
minimization [Mémoli 2011 Redko al. 2020 and entropic regularization [Peyré et al. 2016 Gold
and Rangarajan 1996..
Related works and contributions. The concomitant work of De Ponti and Mondino [2020) extends the L transportation distance defined in Sturm et al. [2006] to unbalanced mm mm-spaces and studies its geometric properties. This distortion distance is not equivalent the GW distance, and is more difficult to estimate numerically because it explicitly imposes a triangle inequality constraint in the optimization problem. The work of Chapel et al. (2020) relaxes the GW distance to the unbalanced setting by hybridizing GW with partial OT [[igall]] 2010) for unsupervised labeling. It ressembles one partieular setting of our formulation, but with some important differences, detailed in Section 2 Our construction is also connected to partial matching methods, which find numerous applications in graphics and vision [Cosmo et al. 2016). In particular, Rodola et al. (012) introduces a mass conservation relaxation of the GW problem.
The two main contributions of this paper the definition of two formulations relaxing the GW distance. The first one is called the Unbalanced computed efficiently on GPUs. The second one is called the Conic Gromov-Wassersse Wasserstenn distance (CGW). It is proved to be a distance between mm-spaces endowed with positive measures up to isometries, stated in Theorem [ which is the main theoretical result of this paper. We also prove in Theorem that UGW can be used as a surrogate upper-bounding CGW. We present those concepts and their properties in Section We also detail in Section 3 an efficient computational scheme for a particular setting of UGW. This method computes an approximate stationary point of a biconvex relaxation of our formulations. Even though it is lower bound of the original problem, we provide in Theorem 3 conditions ensuring the tightness of this relaxation in many cases of interest. The algorithm leverages the strength of entropic regularization and the Sinkhorn algorithm, namely that it is GPU-friendly and defines smooth loss functions amenable to back pook-propggttion for ML applications. Section Section|Arrovicee provides some numerical experiments to highlight the qualitative behavior of this algorithm and its ability to cope with outliers and mass variations in the modes of the distributions. We illustrate numerically the tightness of the relation between UGW and CGW, showing that UGW is a reasonnable proxy of a distance, at least locally. We provide an application of our divergence in the positive unlabeled learning setting, using domain adaptation data, and display results which are at par or outperform the computable competitor Chapel et al. [2020].
in (UGW) divergence and can be
2 Unbalanced
Wassoy-Wssserttein formulations
We present in this section our two new formulations and their properties. The first one, called UGW, is exploited in Sections 3 and derive an efficient algorithm used in numerical experiments. The second one, called CGW, defines a distance between mm-spaces up to isometries. Those results build upon the work of Liero et al. [2015), and a summary of the construction of UOT is detailed in Appendix A In all what follows, we consider complete separable mm-spaces endowed with a metric and positive measure.
3

---

2.1 The unbalanced Gromov- Wasseestten divergence
This new formulation makes use of quadratic g-divergences, defined as D. (plu) - (0 pl where p @ p E (X2) is the tensor product measure defined by d(p p). y) dp(z)dply). Note that D is not a convex function in general.
Definition 1 (Unbalanced GW). The Unbalanced Saanoov-asssesteein divergence is defined as UGW(X inf (Xxx) (TT) ((x)) + D (MIlP) + D ( (T2lP).
This definition be understood as hybridation between ① and (2) but with twist: one needs to use the quadratic divergence D in place of D.. To the best of our knowledge, it is the first time such quadratic divergences are being used and studied. In the TV case, this the most important distinction between UGW and partial-GW [Chapel et al. 2020]. Note also that the balanced GW distance
2 is recovered as a particular case when using & 41 or by letting p - +00 for entropy p.p.
Using quadratic divergences results in UGW being 2- h-homogencous: for 0 2 O, writing (R', )%) equiped with (0u, 0v), one has U 3o V/) = UGW(X.)), When using non tensorized -p-divergences, the resulting unbalanced Gromov-Wasse Wassertein functional between Xs and Vo have y different and inconsistent behaviors when + O and + +oc. Indeed, once normalized by and 8-1, obtains respectively balanced GW and Hellinger-type distance. Using tensorized divergences ensures that the behavior does not depends on It is also fundamental to connect UGW with our distance CGW, Theorem I and Appendix B
We first prove the existence of optimal plans a minimizing L, which holds for the three key settings of Section 2.2.1 namely for KL, TV,, and for compact metric spaces (such finite pointclouds and graphs). All proofs are deferred in Appendix B
Proposition 1 (Existence of minimizers), We assume that (X, Y) are compact and that either (i) sp superlinear, i.e d DC, or (ii) X has compact sublevel sets in R., and 24/ + inf > O. Then there exists E .M (X x Y) such that UGW 3 = ((T).
The following proposition ensures that the functional UGW can be used to compare mm-spaces.
Proposition 2 (Definiteness of UGW). Assume that y ((0)) (1) and X ((()) {0). Then UGW(X') y) 2 0 and is 0 if and only if ~ y.
We end this section with a reformulation of UGW which is important to make the connection with the second formulation CGW of the following section. It splits UGW into two parts: the term (() (1) 1 (v v) accounts for the pure creation/destruction of mass and a new transport cost Le accounts for the remaining part (partial/pure transport and partial creation/destruction of mass).
Lemma 1. Defining Lo(a, b) A c + a:((1/a) + bup(1/b), and writing (f
2 du A du the
dey dus
Lebesgue densities of (H, v) w.E.. (T1, R2) such that μ fm n² and v 9Th + vi, one has
((T)= - (f @ J.g @ g)drdr + (0) @
(3)
Proof. Write f dej and g dw. The Lebesgue decompositions read μ 2 lr = (f < f) m Ø
dv
Ti + (y & p) and & = (g @ g) @ πo + (v @ v) thanks to the tensorized structure of the decomposed plans. To prove Equation 2215)) such that (alj)) = (ula), where (x) e ( !) also an entropy function satisfying
we need to define the reverse entropy [iero al.
v00). One then has
/ Xxxx2 X(D)drd ( (N) (T2)I))
((x)
/ Xxxxy A(T)ddd - ( (x

---

[(T) /
|xaxya x(T)drdr / vf @ f) - f 10 @ g)dradmz
x2
(00)(( @ +) ((v
x²xy² Lf @ f.g 2 g) +00l
Using the definition of 1a in Le ends the proof.
2.2
The conic Gromov- Wasserstenn distance
We introduce second "conic" formulation of unbalanced GW, which is connected to UGW, and whose construction is inspired by the conic formulation of UOT (see Appendix A for an overview).
2.2.1
Background on cone sets and distances
The conic formulation lifts a point E X to couple (I,r) E X x R+ where r encodes some (power of a) mass. Then we seek optimal transport plans defined over c|x] & X x R x {0}), where coordinates (z, r = 0) with no mass are merged into a single point ox called the apex of the cone. In the sequel, points of X R+ are noted (z, while [z, r] are quotiented points of c[X].
While transport plans depend on variables ([x,, r., [y. s)) and ([x',r) r'), (y',s)) in e[X] x the trans- portation cost involved in our conic formulation only makes use of the 2-D cone C(R+] over R, en- dowed with the distance Iu 2 (note that any other distance on could be used well). More specif- ically, we consider coordinates of the form ([u, al, (u, bj) = ([dx x (I, x'),,r") [dy (v,,")) "s),,s')) ss')) E [[R+] x [] Thus we now describe conic discrepancies D on e[R.], which are defined for (p. 9) 2 as D([u, a], [u. 61) & HA((u-ul)
w. 6P). where He(a", 6*) & infe2o ( #) is the perspective transform of L. introduced in Lemmal [ The intuition underpinning the definition of this cost is that the perspective transform accounts for the possibility to rescale a transport plan π by a scalar but the scaling is performed pointwise instead of globally. In general D is not distance, but it is always definite as stated by this result proved in Appendix
((00)= = {1} and is coercive. Then D is definite C[IR+] i.e. D([u, a], [v. b]) = 0 if and only if (a = = 0) or (a = b and u v).
Proposition 3. Assume A x-1((0) ((0}) [0}, ;
Of particular interest are those y where D is a distance, which necessitates a careful choice of X, p and q. We now detail three examples where this is the case.
Gaussian Hellinger distance (GH). When D2 KL, A(L) (2 and g p then one has D([u, a), [v. 6]) a² + 6² 2abe lla-1/2 This cone distance [Burago et al. (200]] is further gen- eralized by De Ponti 2019 who shows that D is distance for power entropies (p() p--p(s-10 1)-1 corresponding to D,2 = KT.).
1(p-1)
if p 2 1 (the case
Hellinger-Kantorovich (HK) / Waassesstein-Fisher-BBee
distance (WFR). When D
KL.
A(t) = log cos? 3) and q = p = 2, then one has D[,u, a). [v, 6))2 a² + 2ab cos( //z A ul). This construction, which might seem peculiar, corresponds to the one used to make unbalanced OT geodesic distance, as detailed in [Liero al. 2015 Chizat et al. 2018a]
Partial optimal transport distance (PT). When D. TV. A(t) = t", q and = 1. then
D[[u, a), [v. 6))5 + b (a A 6) Iu v/9)+ defines a cone distance [Chizat al. 2018a
2.2.2 Definitions and properties
The conic formulation consists in solving a GW problem on the cone, with the addition of two linear constraints. Informally speaking, La from Lemma becomes D. the term (I(, n4)+1 + [v @ +D taken into account by the constraints (5) below, and the variables (f, g) are replaced by (r", sP).
reads CGW(X, A inf infaeu,(a.)) H(a) where
H(aa) A f [p(ldx(1, x'), rr'), (dy 1') (o " do([2, r), (v. s))da(((' ( Mr,,,, (V))))))
(4)
and Up(p,)) v) is defined as the set v, & {a M=(x x(x)), / r'dai(.r) u. / S/, sPdaz(; =v (5)
5

---

It is similar to the conic formulation of UW, see Appendix A formulation ( and in sharp contrast with the conic formulation of UW here the transport plans are defined on the cone e[x] x e[Y] but the cost D is distance on +
Note that similarly to the GW
We present now the main contributions of this paper, proved in Appendix C We state that CGW defines a distance under conditions that hold for the settings of Section (2.2ion[2.2.] and that it is upper- bounded by UGW. The divergence UGW can be approximated with efficient numerical schemes as detailed in Section 3
Theorem 1. (i) The divergence CGW is symmetric, positive and definite up to isometries. (ūi) If is distance on C[R+], then CGW is distance the set of mm-spaces up to isometries. (iii) For any (D2, X, q) with associated cost 'D on the cone, one has UGW 2 CGW.
3 Algorithms
We focus in this section on the numerical computation of the upper bound UGW using a bi-convex relaxation and derive an alternate minimization scheme coupled with entropic regularization. We also propose to approximate CGW by doing a similar alternate minimization, as detailed in Appendix E We provide guarantees of tightness on the bi-convex relaxation for CGW (see Theorem 33. The computation of the distance CGW is heavy in practice because it requires an optimization over a lifted conic space, which needs to be discretized. Thus does not scale to large problem for CGW, but allows to explore numerically how tight is the upper bound UGW > CGW, see Section 4 The algorithm for UGW is presented on arbitrary measures, the special case of discrete measures being a particular case. The discretized formulas and algorithms are detailed in Appendix [ see also Chizat et al. [2018b), Peyré et al. [2016). All implementations are available at https //github. com/ command pip install unbalancedgw.
and installable in Python with the
3.1 Bi-convex relaxation and tightness
In order derive a simple numerical approximation scheme, following Mémoli [201]] we introduce a lower bound obtained by introducing two transportation plans. To further accelerate the method and enable GPU-friendly iterations, similarly to Gold al. [1996], [Solomon al. (2166]. we consider an entropic regularization. It reads, for any 2 O.
UGW:(X,)) A inf ((T) EKL (T O
inf F(T, 7) (T
(6)
J,7
and F( & / /xxx= M(Ixx - dyl)dt @ + ( @ ml Do 8
where (71, 72) denote the marginals of the plan 7. In the sequel we write F, = = Note that in contrast to the entropic regularization of GW Peyré al. [2166). here we use tensorized entropy to maintain the overall homogeneity of the energy. A simple method to approximate this lower bound is to perform an alternate minimization on π and 7, which is known to converge for smooth &o to stationary point since the coupling term in the functional is smooth [Tseng] 2001). Note that if π & optimal then so is (ST) @ (27) with 2 Thus without loss of generality we can optimize under the constraint m([) = m(>) by setting s = /m(1)/m(TT).
We now discuss the tightness of the bi-convex relaxation by generalizing result of Konno. We first present a result which applies to general quadratic assignment problems, then state its application to setting.
Theorem (Tight relaxation). Let B a Banach space, let f: B B L: C c + I the function defined on the corvex set C' C B L(T) { k(x)) +2((T) where I is a symmetric bilinear map which is negative (not necessarily definite) on AC & Span( (TT
be a function and let
7; (T), E C}),, that is, for any E AC,, (2, kz) < O. Assume that there exists To C such that L((T)) < 400, and define F(R,,) A 2 (m k(T)) + S(T) f(7). Then, for any (m.. E
arg min F F(xz, 7), we have F F(m,, n.) T.),, = (.).. Moreover, if one assumes either
that k is definite kernel or f strictly convex, one gets T %.

---

The above Theorem is proved in Appendix D As an application, we now state our tightness result for GW and CGW. In those settings the optimizers of the bi-convex relaxation are also optimal for the original problem.
Theorem 3. For GW₂ with E 2 0 or for CGW, assume that X(t) f2 and that (dx,dy) are both conditionnally negative (or conditionally positive) kernels. Then the bi-convex relaxation of both problems is light.
Proof. The proof for CGW is detailed in Appendix
E we prove the tightness for GW When X(t)
2 the kernel k = A(dx dy |) is conditionally negative on the set { 7), Ti = "1 and R2 = )
Le. we have (( 7), k( (() < 0 (see|Maron Maron and Lipman (0188). For GWe
e one has т = 71 /
and T2 = 7/2 = V/ thanks to the constraints on marginals. Thus the kernel is negative semi-definite
and the proof of Theorem 2 applies, hence the tightness of the relaxation.
Konno's result Konno| [976] applies for unregularized (s = 0), Balanced-GWi The novelty of Theorem 3 is its extension to both GW: and CGW. So far it an open question whether the relaxation is tight or not for UGW,, because the above proof no longer holds. Note that in all our numerical simulations, our solvers always found solutions of UGW, 5 such that
y when Idx dy I is conditonally negative. The property that the kernel dd - dy 1a is negative does not hold in general (e.g. for graph geodesic distances) and the tightness of the relaxation remains open in this setting. We know from [Maron and Lipman 2018 Theorem 1] that it is conditionally negative semi-definite when both (dx.dy) d are conditionally negative kernels. Examples of distances which are negative kernels are tree metrics in the case of graphs, as well as Euclidean, spherical and hyperbolic distances over their respective manifolds Feragen al. (2015). In practice, when is small, observed in the indefinite setting that the relaxation outputs more frequently spurious minima than in the negative semi-definite setting.
3.2 Alternate Sinkhorn minimization
Minimizing the lower bound (6) with respect to either æ or y is non-trivial for an arbitrary yp We restrict our attention to the Kullback-Leible case D., = pKT. with p >> 0, which can be addressed by solving regularized and convex unbalanced problem as studied in Chizat et al. 2018b). Séeourné et al. 2019). It is explained in the following proposition.
Proposition 4. For a fixed y, the optimal x E argmin F(T,7) + eKT @ 71(μ @ e))2) solves
min / cfto, y)dT(I, v) + (m()) + (L(())L((TlV) + =m(()) v),
where ml>) 2 7(X Y) is the mass of and where we define the cost associated to y as
<(0,0)) / [((dx((,))) dy(v: (1)-))) of log( dr )dn log( dha )a + log( d7 ddy dudv
du
du
Computing the cost 65 for spaces X and Y of n points has in general a cost O(n²) in time and memory. How- ever, as explained for instance in Peyré et al. (0166). for the special case X(t) = t2 this cost is reduced to O(n²) in time and On)2) in memory. This is the setting we consider in the numerical simulations. This makes the method applicable for scales of the order of 1 points. For larger datasets one should use approximation schemes such as hierarchical ap- proaches (Xu et al. 2019 Nyström compression of the kernel [Altschuler et al. 2018).
Algorithm 1 UGW(X, p,
Input: mm-spaces (X',)), relax. p. regul. E Output: ग, solving (6)
Init, === = l @ v/ mt///m(((m)))))./m g = 0.
while (TT, 7) has not converged do
Update ι t-7,
then e <- c.. p x- m(T)p, E m (T)E
while (f,g) has not converged do
f +-- 52 log I - c(ol)))dt-w))/ de(y)
g co log s c( du(==)
end while
The resulting alternate minimization method is de- tailed in Algorithm []] see Appendix a discretized version. It uses the unbalanced Sinkhorn algorithm Chizat et al. [201 (2018b). Séjourné et al. [2019] as sub-
Upd. 7(x, ()t,y)+e" Reld ((x)v(y)
Rescale 7 <- /m(T)//(77)
end while Return (TT, 7).
iterations and takes æ = 1a 69 v/ /mljm) (V)) to ini- tialize the updates. This Sinkhorn algorithm operates over a pair of continuous functions (so-called
7

---

Kantorovitch potentials) f() and g(y). For discrete spaces X and Y of size n. these functions are stored in vectors of size n, and that integral involved in the updates becomes a sum. Each iteration of Sinkhorn thus has cost n², and all the involved operation can be efficiently mapped to parallelizable GPU routines as detailed in Chizat et al. [20 Séjourné et al. (2019). Another advantage of using an unbalanced Sinkhorn algorithm is its complexity Onn [E) to compute an e-approximation,
as stated in Pham et al. 2020). which should be compared to O(n² /=²) operations for balanced Sinkhorn.
Note also that balanced GW is recovered as a special case when setting p - +00, so that ğ/ + i) + 1 should be used in the iterations. In order to speed up Sinkhorn inner-loops, especially for small values of one can use linear extrapolation (Thibault et al. [017] or non-linear Anderson acceleration [Anderson] 1965 Scieur et al., 2016).
There is extra scaling step after computing y involving the mass m(*). It corresponds to the scaling 8 of π (8 y such that m(()) = m()), and we observe that this scaling is key not only to impose this mass equality but also to stabilize the algorithm. Otherwise we observed that m(7) m(x) and underflows whenever m(7) - 0 and m(T) + 00.
4 Numerical experiments
This section presents simulations on synthetic examples to highlight the qualitative behavior of UGW and the tightness of the bound UGW 2 CGW. Other illustrations on UGW are available in Appendix E We end the section with learning application of UGW in positive-unlabeled setting, using domain adaptation data so as to compare with PGW Chapel al. [2020). In the synthetic experiments, and v are probability distributions, which allows us compare GW with UGW.
Robustness to imbalanced classes. In this first example, we take X = R Y = R² and consider Eg, &3. C and S to be uniform distributions on 2D and 3D ellipse, square and sphere. We consider mm-spaces of different dimensions to emphasize the ability of (U)GW to compare different spaces. contrasss the transportation plan obtained by GW and UGW for a fixed μ 0.58, + 0.5S and // obtained using two different mixtures of & and C. The black segments show the largest entries of the transportation matrix æ, for sub-sampled set of points (to ease visibility), thus effectively displaying the matching induced by the plan. Furthermore, the width of the dots are scaled according the mass of the marginals π1 μ and n2 R v, i.e. the smaller the point, the smaller is the amount of transported mass. This figure shows that the exact conservation of mass imposed by GW leads to a poor geometrical matching of the shapes which have different global mass. As this should be expected, UGW recovers coherent matchings. We suspect the alternate minimization algorithm is able to find the global minimum in these cases.
Figure[ccomine contrasts
GW
UGW
GW
UGW
Figure 1: GW vs. UGW transportation plan, using v = 0.38, - 0.7C on the left, and v -..32+ on the right. The 2D mm-spaces is lifted into 3R3 by padding the third coordinate
Tightness of the bound CGW We propose to approximate CGW by doing a similar alternate minimization as for UGW, as detailed in Appendix E This numerical scheme does not scale to large problems, but allows us to explore numerically how tight is the upper bound UGW > CGW. Figure 2 highlights the fact that in Euclidean space X Y Rd this bound seems to be tight when the two measures are sufficiently close. We consider discrete measures
1 " E 8z, in X Y _d and 14 1 E. &y: where y, 2, + tA; where A, are random perturbations and
8

---

denote (X², (/) the two mm-spaces associated to the Euclidean distance. As - O, μ and i4 get closer, we observe numerically that UGW CGW. Figure considers random points (æ;); and (ui); and displays the histograms of the ratio CGW (GW/UGW for = 3. This shows that while the bound CGW S UGW seems not tight, the ratio appears to bounded even for points not being close. This numerical experiment suggests that UGW and CGW are locally equivalent and that UGW is in practice an acceptable proxy of the distance CGW. We leave for future works a tighter analysis of the gap between UGW and CGW.
Positive unlabeled learning experiments Positive Unla- beled (PU) learning is a semi-supervised classification problem, where instead of learning from positive and negative samples (x,, L4); with labels & E [-1,1] we only learn from one class labeled with positives, i.e. only those X (x; : 14=1, 1). The task is leverage X to predict the classes & Ely)
p-11
pM20
DON 2-10
Co0 2-10
+-1++1 of unlabelled y Y belong to separate space. We consider here that X, Y are embedded in Euclidean space, and denote Y the associated labelled and unlabelled mm-spaces, equipped with the uniform distribution. Our experiments are adapted from Partial-GW (PGW) (CaWee et al. [2020), which used partial GW to solve PU-learning. The rationale of using unbalanced OT methods for PU learning stems from the fact that positive samples should be matched with positive due to their similar features, while negative samples would be ignored due to dissimilar features that induce a laziness to transport mass and match them.
02
04
12
1181
Figure 2: Comparison of UGW(X, (4) and CGW(X,
as the support gets shifted by a perturbation.
We consider PU learning over the Caltech office dataset used for domain adaptation tasks (with domains Caltech (C) Griffin et al. [2007]. Amazon (A), Webcam (W) and DSLR (D) [aannoo et al. (2010). The Caltech datasets are represented with two embeddings based on Surf and Decaf features Saenko et al.] [2010). Donahue al. [014]. On the latter datasets, we perform PU learning over similar features (e.g. surf-C - surf- or decaf-C - decaf-*) and from one feature format to the other (e.g. surf-C - decaf-* or surf-C - decaf-*). Those features are projected via PCA to subspaces of dimension 10 for surf features and 40 for decaf features. In the last task, one cannot use standard PU-method, and to the best of our knowledge, Unbalanced-GGW methods are the only approaches for PU learning across different domains/features.
The procedure the following. We solve the PU learning problem by computing the optimal plan π for UGW(X', y). We compute its first marginal T2 on V, and predict the labels of some y e Y as f(y) - sign( 22 (v) - q) where q the quantile of corresponding to the proportion of positives samples in Y. Following Chapel et al. [2020) which adapted from Kato et al. (218 Hsich et al. 2219)) this proportion r is assumed to be known. We report the accuracy of the prediction over the same 20 folds of the datasets, and use 20 other folds to validate the parameters of UGW. We consider 100 random samples for each fold of (X, Y), a ratio of positive samples r = 0.1 for domains W.D. and ratio = 0.2 for domains (C.
ni2
0.9
Figure 3: Histograms of the ratio CGW /UG/ for random spaces with n E (2, 3, 5) samples. Ratios over 1 are due to local minima.
Since the GW objective is non-convex, the initialization of the minimization algorithms is key to obtain good perfor- mances. In Chapel et al. 2020 and our experiments, for tasks where Y and Y belong to the same Euclidean space, (e.g. surf-C surf-*) we initialize æ with the Partial-Wassesster (PW) solution with squared Euclidean cost. For cross-domain prediction (e.g. surf-C - decaf-*), following Chapell et al.] 2220). PGW is initialized with a list of plans built using a coarsened representation of the data with N-NN. While Chapel et al. (2020) makes use in an oracle manner of the plan providing the best accuracy, we modified their protocol and keep the plan which has the lowest PGW cost, which seems fairer, hence the difference in performance with Chapel et al. 2020). To initialize UGW when X and Y do not belong to the same Euclidean space, we use a UOT solution of matching between distance

---

Dataset
prior
Init (PW)
PGW
UGW
Dataset
prior
Init (FL
PGW
LGW
surf-C + surt-C
0.1
89,9
84.9
83.9
surt-C - docat-C
0.1
85.0
85.1
85.6
surf-C + surf-A
0.1
81.8
82.2
83.5
surf-C + dccaf-A
0.1
84.2
87.1
83.6
surf-C + surf
0.1
81.9
81.3
80.3
surf-C decaf-W
86.2
88.6
86.8
surf-C surf-D
0.1
80.0
81.4
83.2
surf-C decal-D
0.1
84.7
91.1
90.7
surf-C + surf-C
0.2
79.7
75.7
75.4
surt-C decaf-C
0.2
74.8
75.6
75.9
surf-C - surf-A
0.2
65.6
66.0
76.4
surf-C - decaf-A
0.2
76.2
87.9
82.4
surf-C + surf- W
0.2
65.1
64.3
67.3
surf + decaf-
0.2
81.5
88.4
89.9
docaf-C + dccaf-C
0.1
93.9
83.0
86.8
dccaf-C - surf-C
0.1
81.7
81.0
81.1
decaf-C decaf-A
0.1
81.4
85.6
decaf-C surf-A
80.9
81.2
82.4
decaf-C + decaf W
0.1
80.1
82.7
86.1
decaf-C surf- W
0.1
82.0
81.3
83.5
decaf-C + decaf-D
0.1
80.6
83.8
83.4
decaf-C - surf-D
0.1
80.0
80.8
81.5
dccaf-C + decaf-C.
0.2
90.6
76.7
80.5
decat-C - surf-C
0.2
66.6
63.7
65.2
decaf-C docaf-A
0.2
62.5
68.7
74.7
decaf-C surf-A
0.2
62.9
62.4
69.3
decaf-C + decaf-W
0.2
65.7
75.9
79.2
decaf-C - surf-W
65.1
61.4
83.3
Table 1: Accuracy for all tasks. The left block are domain adaptation experiments with similar
features, where both PGW and UGW are initialised with PW. The right block are domain adaptation experiments with different features, and the reported init is FLB (see Appendix E used for UGW.
histograms called FLB Mémoli
2011]. We define FLB in our UGW setting as
FL)(X))) & min { XXY
1 dx
U* dxdy p + pKL((zl)) +e <KI(T (7)
xx where n* dx (x) - fx (ar, of d()(())))) is the eccentricity, i.e. histogram of aggregated distances,
and j = n/m(()) Contrary to GW Mémoli (2011). there a priori no link between FLB and UGW.
In the experiments we slightly generalize UGW and use two different marginal penalties pi ( + P2KL & (TT)lW) with two parameters (pt, pa) to take into account shifts between domains/features. Note that PGW has single parameter (which plays a role similar to (PI, P2)) which controls the cost mass creation/destruction. We set e = 2-9, which avoids introducing an extra parameter in the method. The value P2) E {2-* k [5, 10]]² are cross validated for each task on the validation folds, and we report the average accuracy on the testing folds. We discuss in Appendix E the impact of reducing the number of parameters
the performance. Comparison with other methods PU and PUSB Kato et al. 2018 Du Plessis et al. 2014) are provided in Chapel et al. 2020) and we focus here the comparison with PGW only.
The results are reported Table T. We display the performance of PGW, UGW and the initialization used for UGW to guarantee that using UGW does improve the performance. We observe that when the source and target dataset is the same (C-C tasks), the PW initialization performs better and PGW/UGW degrade the performance,
that in this setting Optimal Transport should be preferred over GW, which is to be expected. However when the domains are different, applying UGW improves the performance over the initialization (which is FLB) in almost all tasks. Note that in that case the methods PU, PUSB or PW cannot be used. Overall, this shows that GW methods are able to solve to some extent the PU learning problem across different spaces, and that using "softer" KI. penalties in UGW is at least at par with Partial GW, and performs better in some settings.
Conclusion and perspectives
This paper defines two Unbalanced Wesso--Wasserstein formulations: CGW and UGW. We prove that they are both positive and definite. We provide scalable, GPU-friendly algorithm to compute UGW illustrate its applicability in learning tasks, and show that CGW is distance between mm- spaces up isometry. These divergences and distances allow for the first time to blend in seamless way the transportation geometry of GW with creation and destruction of mass. This hybridization the key to unlock both theoretical and practical issues. This work opens new questions for future works, for instance removing the bias introduced by the use of entropic regularization, which is important for applications to ML. Note that such a debiasing was successfully applied for Balanced- GW in Bunne et al. [2019) and is shown to lead to a valid divergence for balanced OT in Feydy et al. [2019) and UW in Séjourné et al. [2019]. The design of efficient numerical solvers for CGW also an interesting avenue for future works, well as the study of its induced topology.
10

---

Acknowledgements
The works of Thibault Séjourné and Gabriel Peyré supported by the ERC grant NORIA. The work of G. Peyré was supported in part by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' d'avenir" program, reference ANR19-P31A-0001 (PRAIRIE 3IA Institute).
The authors thank Rémi Flamary for his remarks and advices, as well as Laetitia Chapel for her help to reproduce her experiments.
References
Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel. Generalized multidimensional scaling: framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences, 103(5): 1172, 2006.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserstein learning for graph partitioning and matching. In Advances in neural information processing systems, pages 3046- 3056, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Shanning-Volume Volume 70, pages 1263-1272. JMLR. org, 2017.
Edouard Grave, Armand Joulin, and Quentin Berthet. Unsupervised alignment of embeddings with wasserstein procrustes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1880-1890, 2019.
David Alvarez-Melis and Tommi S Jaakkola. Gromov-wasserstein aligmment of word embedding spaces. arXiv preprint
2018.
Karl-Theodor Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv: 0434, 2012.
Facundo Mémoli. Gromov-waseertein distances and the metric approach to object matching.
Foundations of computational mathematics, 11(4):417-487,200 2011.
Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transpont problems and new nellinger-kantorvvic distance between positive measures. Inventiones mathematicae, pages 1-149, 2015.
Nicolas Courty, Rémi Flamary, and Devis Tuia. Domain adaptation with regularized optimal transport. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 274-289. Springer, 2014.
Charlie Frogner, Chiyuan Zhang. Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learning with Wasserstein loss. In Advances in Neural Information Processing Systems, pages 2053-2061, 2015.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. arXiv: 17X1v: 077775 2017.
Wasserstein GAN. arXiv preprint
Lénaïc Chizat, Gabriel Peyré, Bernhard Schmitzer, and Laançois-Xavice Vialard. Unbalanced optimal transport: Dynamic and kantorovich formulations. Journal of Functional Analysis, 274(1 I): 3090-3123, 2018a.
Jean Feydy, Pierre Roussillon, Alain Trouvé, and Pietro Gori. Fast and scalable optimal transport for brain tractograms. In International Conference on Medical Image Computing and Computer- Assisted Intervention, pages 636-644. Springer, 2019a.
John Lee, Nicholas P Bertrand, and Christopher J Rozell. Parallel unbalanced optimal transport regularization for large scale imaging problems. arXiv preprint (wX.::1119.00014.0 2019.

---

Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances Neural Information Processing Systems, 33, 2020.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for weer-parameterized models using optimal transport. Advances in neural information processing systems, pages 3036-3046, 2018.
Grant Rotskoff, Samy Jelassi, Joan Bruna, and Eric Vanden-Eijnden. Global convergence of neuron birth-death dynamics, arXiv preprint arXiv: 0tti:/90220 1902.01443 2019.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Adv. in Neural Information Processing Systems, pages 2292-2300, 2013.
Lenaic Chizat, Gabriel Peyré. Bernhard Schmitzer, and François- -avier Vialard. Scaling algorithms for unbalanced transport problems. to appear in Mathematics of Computation, 2018b.
Thibault Séjourné, Jean Feydy, François-Xavier Vialard, Alain Trouvé, and Gabriel Peyré. Sinkhorn divergences for unbalanced optimal transport. arXiv preprint arXiv: 12958, 2019.
Charlotte Bunne, David Alvarez-Melis, Andreas Krause, and Stefanie Jegelka. Learning generative models across incomparable spaces. arXiv preprint arXiv:1905.054:00 2019.
Hongteng Xu, Dixin Luo, Ricardo Henao, Svati Shah, and Lawrence Carin. Learning autoencoders with relational regularization. arXiv preprint arXiv:2002.02913. 2020.
Ivegen Redko, Titouan Vayer, Rémi Flamary, and Nicolas Courty. Co-optimal transport. arXiv preprint arXiv:2002.0373// 2020.
Titouan Vayer, Laetita Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov- wasserstein distance for structured objects: theoretical foundations and mathematical properties. arXiv preprint arXiv: 1 1.02834, 2018.
Samir Chowdhury and Tom Needham. Gromov-wasserstinn averaging in riemannian framework. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition Workshops, pages 842-842 843, 2020.
David Alvarez-Melis, Stefanic Jegelka, and Tommi S Jaakkola. Towards optimal transport with global invariances. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1870-1879. PMLR, 2019.
Rainer E Burkard, Eranda Cela, Panos M Pardalos, and Leonidas S Pitsoulis. The quadratic as- signment problem. In Handbook of combinatorial optimization, pages 1713-1809. Springer, 1998.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-waaserstein averaging of kernel and distance matrices. In International Conference on Machine Learning, pages 2664-2672, 2016.
Steven Gold and Anand Rangarajan. A graduated assigmment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence, 18(4)3377-388 1996.
Nicoló De Ponti and Andrea Mondino. Entropy-trannsprt distances between unbalanced metric measure spaces. arXiv preprint arXiv:2009. 106366 2020.
Thel-Th Sturm et al. On the geometry of metric measure spaces. Acta mathematica, 196(1): 65-131, 2006.
Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial gromov-wasserster with applications on uosibile-unlabeled learning, arXiv preprint arXiv:2002.08826, 2020.
Alessio Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-566) 2010.
Luca Cosmo, Emanuele Rodolà, Michael M Bronstein, Andrea Torsello, Daniel Cremers, and
Y Sahillioglu. Shree' 16: Partial matching of deformable shapes. Proc. 3DOR, 129): 2016.
12

---

Emanuele Rodola, Alex M Bronstein, Andrea Albarelli, Filippo Bergamasco, and Andrea Torsello. A game-theoretic approach deformable shape matching. In 2012 IEEE Conference on Computer Vision and Puttern Recognition, pages 182-189. IEFE, 2012.
Dmitri Burago, Iu D Burago, Yuri Burago, Sergei A Ivanov, and Sergei Ivanov. A course in metric geometry, volume 33. American Mathematical Soc., 2001.
Nicolò De Ponti. Metric properties of homogeneous and spatially inhomogeneous f-dieerggnees
IEEE Transactions on Information Theory, 66(3):2872-2890 2019.
Steven Gold, Anand Rangarajan, et al. Softmax to softassign: Neural network algorithms for combinatorial optimization. Journal of Artificial Neural Networks, 2(4):381-399, 1996.
J. Solomon, G. Peyré, V. Kim, and S. Sra. Entropic metric alignment for correspondence problems.
ACM Transactions on Graphics (TOG), 35(4), 2016.
Paul Tseng. Convergence of a block coordinate descent method for nondiffcrentiable minimization. Journal of optimization theory and applications, 109(3):475-499)) 2001.
Haggai Maron and Yaron Lipman. (probably) concave graph matching.
arXiv preprint
arXiv:1807.09972. 2018.
Hiroshi Konno. Maximization of a convex quadratic function under linear constraints. Mathematical programming, 1 11()):117-27,, 1976.
Aasa Feragen, Francois Lauze, and Soren Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3032-3042, 2015.
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Weed. Massively scalable Sinkhorn distances via the nystr\" om method. arXiv preprini 18X2::0 2018.
Khiem Pham, Khang Le, Nhat Ho, Tung Pham, and Hung Bui. On unbalanced optimal transport: An analysis of sinkhorn algorithm. arXiv preprint arXiv:2002.0329. 2020.
Alexis Thibault, Lénaïc Chizat, Charles Dossal, and Nicolas Papadakis. Overrelaxed Sinkhorn- Knopp algorithm for regularized optimal transport. arXiv preprint arXiv: 1.00851 2017.
Donald G Anderson. Iterative procedures for nonlinear integral equations. Journal of the ACM (JACM), 12(4):547-560, 1965.
Damien Scieur, Alexandre d' Aspremont, and Francis Bach. Regularized nonlinear acceleration. In Advances In Neural Information Processing Systems, pages 712-720, 2016.
Gregory Griffin, Alex Holub, and Pietro Perona. Caltech-256 object category dataset. 2007.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European conference on computer vision, pages 213-226. Springer, 2010.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In International conference on machine learning, pages 647-655. PMLR, 2014.
Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from positive and unlabeled data with a selection bias. In International Conference on Learning Representations, 2018.
Yu-Guan Hsieh, Gang Niu, and Masashi Sugiyama. Classification from positive, unlabeled and biased negative data. In International Conference Machine Learning, pages 2019.
PMLR,
Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. Advances in neural information processing systems, 27:703-711, 2014.
Jean Feydy, Thibault Séjourné, François-Xaviss Xavier Vialard, Shun-ichi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. The 22nd International Conference Artificial Intelligence and Statistics, pages 2681-2690, 2019b.
13

---

Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal transport in competition with reaction: The hellinger- hellinger- kantorovich distance and geodesic curves. SIAM Journal on Mathematical Analysis, (8(4):2869-29) 2016.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François- Xavier Vialard. An interpolat- ing distance between optimal transport and fisher-rao metrics. Foundations of Computational Mathematics, 18(1):1-44 2018c.
Cedric Villani. Topics in C. Transportation. Graduate studies in Math. AMS, 2003.
Rémi Flamary and Nicolas Courty. Pot python optimal transport library. com//flamary/POT, 2017.
GitHub: https:/ggithub
Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic analysis on semigroups: theory of positive definite and related functions, volume 100. Springer, 1984.
14


Reviews:
[{"review_id": "l3xMihZUt_v", "reviewer": "Reviewer_mUoT", "summary": "The paper deals with unbalanced Gromov-Wasserstein (UGW)  to compare un-registered metric measure spaces not necessarily endowed with a probability distribution. It proposes the relaxation of the  usual marginal constraints using quadratic  divergences leading to  a new  divergence that can be used to compare metric measure spaces.  By  adding an adapted entropic regularization to  the UGW formulation, an alternate optimization scheme based on Sinkhorn iterations  is designed. The  paper also  introduces another conic  formulation for Unbalanced GW (CGW) that  defines a distance invariant to isometries. The former is shown  to upper-bound CGW which optimization procedure is computationally  heavy. Both CGW and UGW  are illustrated on simulated. Furthermore application of  UGW to PU  learning shows  the effectiveness  of the  proposed UGW divergence. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Overall, the paper is well written and well  organized. The rationale behind the proposed method is justified and the  novelty brought  by  the approach is stated clearly. Theoretical  analysis of the proposed unbalanced  GW formulations is  provided  along  with the strengths and  limitations of UGW and CGW. Optimization approach to compute both GW-based divergences is also given. Empirical evaluations support the  effectiveness of the  proposed methods. Hence,  the paper brings a significant and interesting contribution to the field of unbalanced Gromov-Wasserstein distance.\n- The main novelty  of the paper is  the definition of Unbalanced GW based $\\varphi$-quadratic divergences that allow to express a 2-homogeneous relaxation of  the  marginal constraints of balanced GW. The paper  should deserve a few lines to provide better intuition on the quadratic divergences.\n- GW  discrepancy is  known to   isometry-invariant. Is it the  case for UGW? As a general comment, the theoretical properties (beyond existence and definiteness) of UGW discrepancy measure should be more discussed and  made clearer. \n-  Lemma 1  plays  a central role in connecting UGW to the conic formulation of GW. Such as presented, that Lemma is hard to handle with several dense  notations. The paper should improve the introduction and the comments of that Lemma for a better readability.\n- Interestingly the conic formulation  (CGW) defines a distance up  to isometries, a desirable property for some practical applications.  Also a strong result  of the paper is that the CGW distance is upper-bounded by the UGW discrepancy measure. The latter being computationally more favorable, it offers a theoretically justified  way to approximate CGW. The paper investigates empirically  the tightness of the relation CGW $\\leq$ UGW. Nevertheless the empirical analysis has to be extended to isometry-invariance framework.\n- The  weak points  of the paper are related to the optimization  procedure. Indeed,  the more general setting of UGW is narrowed to some specific divergences (KL in fact) or map function $\\lambda$  limiting the applicability scope of UGW. I guess such assumptions are unavoidable to allow competitive optimization schemes. The second remark is the use  of entropic regularization in order to elaborate an efficient  bi-convex relaxation  to solve UGW. Depending on the choice of the regularization parameter, the upper-bound on CGW  may be less tight as expected. Can the authors discuss that  ? Also, is there any result on the convergence of regularized UGW towards UGW when $\\epsilon  \\rightarrow  0$?\n- The paper informs that CGW has a high computation burden. Can  the paper provide  some insights on the computational complexity or memory requirement to compute CGW?\n- The empirical evaluations show the good behavior and  the benefits of the proposed unbalanced GW divergences. Especially the obtained results are impressive for some experimental setups (see Table 1) and  they illustrate the benefit of the proposed marginal constraint relaxation using quadratic-divergences. Compare to PGW  how  one can explain the effect of applying such quadratic-divergences in-lieu of  the  classical ones?\n- In the robustness to imbalanced classes, it  might be interesting to  plot the matching suggested by PGW. \n\nAfter feedback\n-------------------\nI thank the authors for providing detailed responses to the raised points. I highly appreciate their endeavour to clarify most concerns, especially the  isometry-invariance property of UGW, the computational burden of UGW in the general setting or the convergence convergence of regularized UGW towards UGW when $\\epsilon  \\rightarrow  0$.  I expect the revision will improve on these points and on the dense notations. Hence, I still have a positive view of the paper and I keep my rating.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Unless I was mistaken, the paper does not discuss the broader impact of the proposed approaches. On my view the work does not raise specific issues except the computation burdent inheritent to  GW.", "review_text": "", "extra_scores": {"ethical_concerns": "The  paper does not raise  any ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "TtKJILz0IC0", "reviewer": "Reviewer_XuXr", "summary": "The paper extends the Gromov-Wasserstein (GW) distance framework to two novel relaxations, the unbalanced GW (UGW) and the conic GW (CGW), which both address the question of comparing arbitrary positive measures on different metric spaces. The paper also proves that CGW is upper bounded by UGW, and introduces an algorithm to compute UGW based on Sinkhorn iterations. Numerical experiments are presented to illustrate the performance of the new algorithm. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents new results of theoretical and practical importance for the two proposed GW formulations. The text is well-written and streamline. Technical writing is also to a high standard, with clean notation and coherent proofs.\n\nThe results are quite strong, combining ideas from unbalanced optimal transport (UOT), conic optimal transport (COT) and GW. By choosing a specific divergence in the new formulations, the paper partly retrieves the well-known equality connecting UOT and COT. The tightness result based on maximization of convex functional furthers the theoretical understanding of GW and elucidates how to extend the Sinkhorn algorithm to the GW setting.\n\nSome specific comments/concerns I have are as follows:\n1. After Theorem 2 it is claimed that the kernel $|d_X-d_Y|^2$ is negative semi-definite. According to the proof of Theorem 2 it is supposed to be negative semi-definite on the set of all signed measures due to the unbalanced setting. (Vayer, Titouan, et al. \"Sliced Gromov-Wasserstein”) show that it is negative semi-definite on the set of all couplings, thus accounting for the balanced GW distance. Do the authors have a reference/proof for this general claim? This is crucial for the usefulness of Theorem 2 and to applications of the proposed methods.\n\n2. The paper would benefit from more account of theoretical aspects of CGW. The reviewer understands that this may exceed the scope of the current submission, but more results on, e.g., induced topology on mm-spaces and its relation to GW, would be a nice addition. The authors should at least consider mentioning such research trajectories as future directions.\n\n3. The entropic regularization is standard, but in UGW setting it remains unclear whether all the nice properties (convergence, global optimality, stopping criterion, etc.) still hold. For completeness, these should be checked, in addition to just showing the computational cost of each step. The dependence of the entropic relaxation on $\\epsilon$ should also be examined, e.g., if it converges to the UGW as $\\epsilon\\to 0$. In general the 'doubly entropic' GW is worth studying even for the balanced case.\n\n4. The paper repeatedly claims that the regular GW is recovered as $\\rho\\to\\infty$, which should also be verified rigorously as it is unclear whether it’s the distance or the optimal coupling that’s recovered, and 'recovered' in what sense.\n\n5. The main theorem claims UGW $\\geq$ CGW, and the paper only illustrates numerically how tight this inequality can be. Is it possible to bound the gap and to give criterions when they are equal?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2cotUu08yoi", "reviewer": "Reviewer_abgG", "summary": "This paper proposes two unbalanced Gromov-Wasserstein formulations, namely Unbalanced Gromov-Wasserstein (UGW) divergence and Conic Gromov-Wasserstein (CGW) distance. Both of them are positive and definite. UGW has a scalable and GPU-friendly algorithm, which is applicable to large learning problems. CGW is a distance between mm-spaces up to isometry. It is theoretically and empirically shown that UGW can be used as a surrogate upper-bounding CGW. The authors then apply UGW to positive unlabeled learning with Caltech office dataset and achieve comparable or better performance than Chapel et al., 2020. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper flows well. That being said, I would strongly recommend the authors to simplify the notations and terminologies in the main paper, especially in the introduction section. This can make the work more accessible for general readers. Besides, notations like $\\iota$ and $\\bot$ lack proper definition.\n\nIt is an interesting idea to use a scalable divergence to surrogate a real distance. \n\nAlthough according to the algorithm the computation of UHW should be efficient and scalable, it would be better if the computation time is also reported.\n\nI am curious that whether the plots for $\\rho=1, 10$ will have the same trend as $\\rho=0.1$ is the shift is larger.\n\nLine 228 the code at https://github.com/anonymous-conference-submission does not exist (by July 16. This is just a minor point because there is code in the supplement material).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper considers the formulation of unbalanced Gromov-Wasserstein distance, and does not contain any specific applications that may have negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A standard approach for defining distances between metric measure spaces is to use the Gromov-Wasserstein distance. However this formalism is limited to settings where the metric measure space has an underlying probability distribution. The main contributions of this paper are in formulating unbalanced analogues of the Gromov-Wasserstein distance that work with general positive measures. The specific formulations adapt ideas from unbalanced and conic optimal transport. Furthermore they use entropic regularization to design a Sinkhorn-style iterative algorithm and give experimental results on synthetic data and for problems in domain adaptation. The paper is well-written and has a nice mix of contributions. The only weakness is that they specialize to KL divergences which seems to limit the scope and applicability. Furthermore, in their setup working with more general divergences appears to be much more computationally challenging. 
Decision: Accept (Poster)