Partial Gromov-Wasserstein Metric
Authors: Yikun Bai
Rocio Diaz Martin
Abihith Kothapalli
Hengrong Du
Xinran Liu
Soheil Kolouri
Venue: ICLR 2025 Poster (2025)
Keywords: Optimal transport
Gromov-Wasserstein problem
Unbalanced optimal transport
Primary area: optimization

Abstract: The Gromov-Wasserstein (GW) distance has gained increasing interest in the machine learning community in recent years, as it allows for the comparison of measures in different metric spaces. To overcome the limitations imposed by the equal mass requirements of the classical GW problem, researchers have begun exploring its application in unbalanced settings. However, Unbalanced GW (UGW) can only be regarded as a discrepancy rather than a rigorous metric/distance between two metric measure spaces (mm-spaces). In this paper, we propose a particular case of the UGW problem, termed Partial Gromov-Wasserstein (PGW). We establish that PGW is a well-defined metric between mm-spaces and discuss its theoretical properties, including the existence of a minimizer for the PGW problem and the relationship between PGW and GW, among others. We then propose two variants of the Frank-Wolfe algorithm for solving the PGW problem and show that they are mathematically and computationally equivalent. Moreover, based on our PGW metric, we introduce the analogous concept of barycenters for mm-spaces. Finally, we validate the effectiveness of our PGW metric and related solvers in applications such as shape matching, shape retrieval, and shape interpolation, comparing them against existing baselines. Our code is available at https://github.com/mint-vu/PGW_Metric.

Published as a conference paper at ICLR 2025
PARTIAL GROMOV- SAABOV-WWSSERSTEIN METRIC
Yikun Bai", Rocio Diaz Martin 22 Abihith Kothapalli",, Hengrong Duu, Xinran Liu', and Soheil Kolouri'
Department of Computer Science, Vanderbilt University 2 *Department of Mathematics, Tufts University
3 Department of Mathematics, University of California, Irvine yikun. rii, abi.kothapalli xinran.liu, haloiilkooorriiaddeebbii 2 Prcciodiaz martin@tufls.eddu hennronnduuiiedu
ABSTRACT
The Cromov-Wassorstenn (GW) distance has gained increasing interest the machine learning community in recent years, as it allows for the com- parison of measures in different metric spaces. To overcome the limita- tions imposed by the equal mass requirements of the classical GW prob- lem, researchers have begun exploring its application in unbalanced set- tings. However, Unbalanced GW (UGW) crepancy rather than a rigorous metric/distance between two metric mea- sure spaces (mm--spaces). In this paper, we propose particular case of the UGW problem, termed Partial Gromov-Wassersten (PGW). We es- tablish that PGW is well-defined metric between mm-spaces and dis- cuss its theoretical properties, including the existence of a minimizer for the PGW problem and the relationship between PGW and GW, among others. We then propose two variants of the Frank- algorithm for solving the PGW problem and show that they are mathematically and computationally equivalent. Moreover, based on our PGW metric, we in- troduce the analogous concept of barycenters for mm-spaces. Finally, we validate the effectiveness of our PGW metric and related solvers in ap- plications such as shape matching, shape retrieval, and shape interpola- tion, comparing them against existing basclines. Our code is available at https: // httgggtthuuu.ttc com wwtp://ttttttt/////.o...
only be regarded as dis-
INTRODUCTION
The classical optimal transport (OT) problem (Villani, 2009) seeks match two probability measures while minimizing the expected transportation cost. At the heart of classical OT thcory lies the principle of mass conservation, which aims to optimize the transfer between two probability measures, assuming they have the same total mass and strictly preserv- ing it. Statistical distances that arise from OT, such as Wasserstein distances, have been widely applied across various machine learning domains, ranging from generative modeling (Arjovsky et al., 2017; Gulrajani et al., 2017) to domain adaptation (Courty et al., 2017) and representation learning (Kolouri et al., 2020). Recent advancements have extended the OT problem to address certain limitations within machine learning applications. These ad- vancements include: 1) facilitating the comparison of non-negative measures that possess different total masses via unbalanced (Chizat et al., 2018c) and partial OT (Figalli, 2010), and 2) enabling the comparison of probability measures across distinct metric spaces through Gromov- Wasserstein distances (Mémoli, 2011), with applications spanning from quantum chemistry (Gilmer al., 2017) to natural language processing (Alvarez-Melis & Jaakkola, 2018).
Regarding the first aspect, many applications machine learning involve comparing non- negative measures (often empirical measures) with varying total amounts of mass, e.g.,
"These authors contributed equally this work.

---

Published as a conference paper at ICLR 2025
domain adaptation (Fatras et al., 2021). Moreover, OT distances (or dissimilarity measures)
are often not robust against outliers and noise, resulting in potentially high transportation costs for outliers. Many recent publications have focused variants of the OT problem that allow for comparing non-negative measures with unequal mass. For instance, the optimal partial transport problem (Figalli, 2010; Caffarelli & McCann, 2010; Figalli & Gigli, 2010; Nguyen et al., 2024; Georgiou et al., 2008; Piccoli & Rossi, 2014), Kantorovich Rubinstein norm (Guittet, 2002; Heinemann et al., 2023; Lellmann et al., 2014), and the Hellinger Kantorovich distance (Chizat et al., 2018a; Licro et al., 2018). Recent works formulating the metric propertics of partial OT with total variation constraints include (Raghvendra et al., 2024; Nietert et al., 2023). These methods fall under the broad calegory of "unbalanced optimal transport." In this regard, we also highlight (Balaji et al., 2020; Nguyen el al., 2023; Le et al., 2021), which enhance OT's robustness in the presence of outliers.
Regarding the second aspect, comparing probability measures across different metric spaces is essential in many machine learning applications, ranging from computer graphics, where shapes and surfaces are compared (Broustein et al., 2006; Mémoli, 2009), to graph parti- tioning and matching problems (Xu et al., 2019a). Source and target distributions often arise from varied conditions, such as different times, contexts, or measurement techniques, creating substantial differences in intrinsic distances among data points. The conventional OT framework necessitates a meaningful distance across diverse domains, a requirement that is not always achievable. To circumvent this issue, the Wassees-ssse (GW) distances were proposed in (Mémoli, 2011; 2009) as an adaptation of the Gromov-Hausdorff Hausdorff distance, which measures the discrepancy between two metric spaces (Edwards, 1975; Gro- mov, 19; Burago ct al., 2001). The GW distance (Mémoli, 2011; Sturm, 2023) extends OT-based distances to metric mcasure spaces (mm-spaccs) up to isometrics. Its invariance across isomorphic nim-spaces makes the GW distance particularly valuable for applications like shape comparison and matching, where invariance to rigid motion transformations is crucial.
The main computational challenge of the GW metric is the non-convexity of its formulation (Mémoli, 2011). The conventional computational approach relies on the Frank- Wolfe (FW) algorithm (Frank ct al., 1956; Lacoste-Julien, 2016). Optimal transport (OT) computational methods (Guittet, 2002; Cuturi, 2013; Papadakis et al., 2014; Benamou et al., 2014; 2015; Poyré et al., 2019; Chizat et al., 2018b; Bonneel & Cocurjolly, 2019; Bai et al., 2023), such as the Sinkhorn algorithm, can be incorporated into FW iterations, which yields the classical GW solvers (Peyré et al., 2016; Xu et al., 2019b; Titouan et al., 2019a).
Given that the GW distance is limited to the comparison of probability mm-spaces, recent works have introduced unbalanced and partial variations (Séjouréé et al., 2021; Chapel et al., 2020; De Ponti & Mondino, 2022). These variations have been applied in diverse contexts, including partial graph matching for social network analysis (Liu et al., 2020) and the alignment variants of the GW problem yields notions of discrepanccess between mi-spaces, their metric properties remain unclear in the literature.
brain images (Thual et al., 2022). Although solving these unbalanced
Motivated by the emerging applications of the GW problem in unbalanced settings, this paper focuses on developing a metric between general (not necessarily probability) mm- spaces and providing efficient solvers for its computation. Our proposed metric arises from formulating a variant of the GW problem for unbalanced contexts, rooted in the frame- work provided by (Séjourné et al., 2021), which we named the Partial Gromov- Wasserstein (PGW) problem. In contrast to (Séjourné et al., 2021), which introduces a KL-divergence penalty and a Sinkhorn solver, we employ total variation penalty, demonstrate the result- ing metric properties, and provide novel, efficient solvers for this problem. To the best of our knowledge, this paper presents the first metric for non- coo-rbbabyllty mm-spaces based on the GW distance.
Contributions. Our specific contributions to this paper are:
GW metric in unbalanced settings. We propose the Partial Gromov- Wasserstein (PGW) problem and prove that it gives rise to a metric between arbi- trary mm-spaces.
2

---

Published as a conference paper at ICLR 2025
PGW solver. Analogous to the technique presented in (Caffarelli & McCann, 2010), we show that the PGW problem can be turned into a variant of the GW problem. Based on this relation, distinct in numerical implementation, problem. Inspired by the results of (Lacoste-Julien, 2016), prove that similar to the Frank- Wolfe solver presented in (Chapel et al., 2020), our proposed solvers for the PGW problem converge linearly to a stationary point.
propose two mathematically equivalent, but
Trank-Wolfe solvers for the discrete PGW
Numerical experiments. We demonstrate the performance of our proposed al- gorithms in terms of computation time and efficacy on a series of tasks: shape- matching with outliers between 2D and 3D objects, shape retrieval between 2D shapes, and shape interpolation using the concept of PGW barycenters. We com- pare the performance of our proposed algorithms against existing baselines for each task.
BACKGROUND
In this section, we review the basics of OT theory, one of its variants in unbalanced contexts called Partial OT (POT), and their connection as established in (Caffarelli & McCann, 2010). We then introduce the GW distance.
2.1 OPTIMAL TRANSPORT AND PARTIAL OPTIMAL TRANSPORT
Let Ω Rd be, for simplicity, compact subset of Rd and P(2)) be the space of probability measures defined on the Borel o-algebra of ft
The Optimal Transport (OT) problem for n, E P(.), with transportation cost cxx, v) 9 x Ω - R2, being a lower-semi continuous function is defined as:
where r(c)= = J c(æ, y) d7(2,))
OT(Hp)) = min 7(c), gel(ar))
(1)
and where T(u, v) denotes the set of all joint probability measures on Ω2 = Ω Q with marginals H, i.e., 71 FI# μ4, 72 = 72#7 v, where TI, Ω2 + Ω are the canonical projections (1 y) == 2, (2(2,)) y) := y. A minimizer for (1) always exists (Villani,
2009; 2021) and when c(x,8) = | ylp", for p 2 1, it defines metric P(l2), which is referred to as the "p- Wasserstein distance":
W v) min [ || d/ v)-
(ET Joe
(2)
The Partial Optimal Transport (POT) problem (Chizal et al., 2018c; Figalli & Gigli, 2010; Piccoli & Rossi, 2014) exlends the OT problem to the set of Radon measures (S), ie., negative and finite measures. For X > 0 and u, MM2)),, the POT problem is defined as:
inf >()) A(Ix n1 +n|+|o 122)) PO;(H, (0M,
(3)
where, in general, |a| denotes the total variation norm of a measure i.c., lo|:= == (?). The constraint 7 .M (522) in (3) can be further restricted to 7 E (H,
Is (H, := E M_(()) n 14, 14,22 Sv}.
denoting 71 < pu if for any Borel set B C Ω, (B) < ((B) (respectively, for 72 v) (Figalli, 2010). Roughly speaking, the linear penalization indicates that if the classical transportation cost exceeds 2X, it is better to create/ destroy" mass (see (Bai al., 2023) for further details).
The relationship between POT and OT. By using the techniques in (Caffarelli & McCann, 2010). the POT problem can be transferred into an OT problem, and thus, OT solvers (e.g., network simplex) can be employed to solve the POT problem.
'iiooruusyy speaking, due to the non-convexity of the GW problem and its variants, current methods achieve only local minima rather than global minima. We use the term "solver" following the convention of previous related works (Séjourné et al., 2021; Chapel et al., 2020). However, it should be emphasized that the proposed methods aim to find local minima rather than global minima, similar to related and classical computational GW works.
3

---

Published as a conference paper at ICLR 2025
Proposition 2.1. (Caffarelli 8 McConn, 2010; Bai et al., 2023) Given p.v E M+(2)) construct the following measures on f2 QU { for an auriliary point do:
j = u 10 and i ύ= v + |
(4)
Consider the following OT problem
OT min 7(0), where c(x.y) [c(x,)) 22 ger(a.))
iz,, elsewhere.
(5)
Then, there exists a bijection F T v) - I(j,, i) given by
F(r) : 7 (p - 11) @ 8% 8,z (v 72) + 1718
(6)
such that is optimal for the POT problem (3) if and only if F(?) is optimal for the OT problem (5).
It is worth noting that instead considering the same underlying space for both measures j and v, the OT and POT problems can be formulated in the scenario where μ and v are defined on different metric spaces X and Y, respectively. In this sotting, one needs a cost function c: X Y + R, to formulate the OT and POT problems. However, in practice, it is usually difficult to define reasonable 'distance' or ground cost c(.--) between the two spaces X and Y. In particular, the p- Wassersteii distance cannot be adopted if μa, v are defined on different spaces. To relax this requirement, in the next section, we will review the fundamentals of the Gromov- Wasserstein problem (Mémoli, 2011).
2.2 THE GROMOV- WASSERSTEIN (GW) PROBLEM
A metric mcasure space (mm-space) consists of a set X endowed with metric structure, that is, a notion of distance dx between its clements, and equippod with a Borel mcasure μ. As in Mémoli (2011, Ch. 5), we will assume that X is compact and that suрр(u) = X. Given two probability mm-spaces X = (X, xx,xx,,,, Y = (Y, dY, v), with μ E P(X) and v E P(Y), and non-ne negative lower semi-contimuous cost function L R - R. (e.g., the Euclidean distance or the KL-loss), the Gromov- Wasserstein (GW) matching problem is defined as:
GWL(X, = inf 7 32 (L(dx(;:), gET(M.))
where, for brevity, we employ the notation 702 for the product measure dy32 y), (x','')) dr(x. y)dn(() (1'((((')))) ,y)). If M(a = la DP, for S < oc, we de- note GW"(s)) simply by GWP(:.). In this case, the expression (7) defines equivalence relation ~ among probability mm-spaces, ie.. X ~ Y if and only if GWP(X, Y) = 0². A minimizer of the GW problem (7) always exists, and thus, we can replace inf by min. More- over, similar to OT, the above GW problem defines distance for probability mm-spaces after taking the quotient under ~. For details, we refer to Mémoli (2011, Ch. and 10).
3 THE PARTIAL CROMOV-WASSERSE
(PGW) PROBLEM
The Unbalanced Gromov-Wassersters (UGW) problem for general (compact) mm-spaces X = (X, (X,dx.P) (), Y = (Y, dy, v), with (X), E MY))), studied in (Séjouréé et al., 2021; Kong et al., 2024) is defined as:
inf UGW Y): = (Xx)
(L + A(D 82 || 02) + Do || D2)), (8)
where À > 0 is a fixed linear penalization parameter, and D& is a Csiszár or d-divergence. The above formulation extends the classical GW problem (7) into the unbalanced setting (μ and v are no longer necessarily probability measures but general Radon measures).
We underline two points: First, discussed in (Séjourné et al., 2021), while the above quantity allows us to 'compare' the mm-spaces X and Y, its metric property is unclear.
2 Moreover, given two probability mm-spaces X and Y, GW Y) 0 if and only if there exists bijective isometry o X ++ Y such that 2g/l= = In particular, the GW distance is invariant under rigid transformations (translations and rotations) of given probability mm-space.
4

---

Published as a conference paper at ICLR 2025
Secondly, when Dø is the KL divergence, Sinkhorn solver has been proposed in (Séjourné et al., 2021). However, a solver for general o-divergences has not yet been proposed.
In this paper, we will analyze the case when D& is the total variation norm. Specifically, for 2 1, we consider the following problem, which we refer to as the Partial Gromov- Wasserstein (PGW) problem:
inf (X == "EM+(XXX)
02 (L(d). (x)) + M(11 02 71
2
02
72
1)
(9)
Remark 3.1. If y ETTS (H,V), the above cost functional can be rewritten as
(L Rz)) 2(In82 - 2 I + 1232 2) y 8/ (I(dz, dz) 22) + A A1m12 1112)
does not depend
Proposition 3.2. Given mm-spaces X = dx, u),Y Y= by,dy,1) the minimization prob- lem (9) can be restricted to the set {() = (7 E M+ x Y): n S p.72 u.. That is,
PGW X.g (X.Y)
inf TET
882 (L(d', d 2A) + 1213).
(10)
For the proof inspired by (Piccoli & Rossi, 2014), we direct the reader to Appendix B.
We notice that similar Partial Gromov-Warn Wasserstein problem (and its solver) has been studied (Chapel et al., 2020). Indcod, in (Chapel ot al., 2020), the X-penalization in the optimization problem (10) is avoided, but the constraint set is replaced by the subset of all Y E (1, v) such that by| p for a fixed p E [0, mil] [μ]]]. We will call this formulation the Mass- Constrained Partial Gromov- Wasserslein (MPGW) problem. In Appendix L, we explore the relations between PGW and MPGW, and in Section and A Appendices O, Q, analyze the performance of the different solvers through different experiments.
Proposition 3.3. If L(r1,r2) = |r - r2l2, for p [o), we use PGWA, to denote PGW x. In this case, (9) and (10) admit a minimizer.
The proof is given in Appendix C: Its idea extends results from (Mémoli, 2011) from prob- ability mm-spaces to arbitrary mm-spaces.
Next, we state one our main results: The PGW problem gives rise to a metric between mm-spaces. The rigorons statement, well its proof, is given in Appendix D: The formal statement is based on the definition of equivalence classes among mm-spaces (sce Remark D.1). The most difficult part of the proof is the triangle incquality, and the main technique used relies on the relation between PGW and GW (see Appendix D.3).
Proposition 3.4. Let > O, S P.P < oo and L(r1,22) = Iri - r2l?. Then (PGWT () (.
defines metric belween men-spaces.
Finally, for consistency, we provide the following result when the penalization tends to infinity. Its proof is given in Appendix E.
Proposition 3.5. Consider probability mam-spaces X= XX,xx,M 1), == = (Y,dy, v), that is, [p] = |o] 1. Assume that L is a continuous function. Then limx- PGW 2.g (X, Y) = GWL(X, (X, V).
4 COMPUTATION OF THE PARTIAL GW DISTANCE
In the discrete setting, consider mm-spaces X (X, (X,dx,E=I DN B2,), Y (Y,dy, E of )g,); where X [ InJ, Y "it...,,u,,, the weights p.x of are non-negative numbers, and the distances dx, dy are determined by the matrices ax RuXn CV E mmmm defined by
CX 1,p== (= Vi,i' E [1:n] and CY == d Vj.J" ml:
(11)
Let :=: = 1g ......,h,T T and q q: = 10 ,......... 2YT denote the weight vectors corresponding to the given discrete measures. We view the sets of transportation plans T(p, q) and (p,
5

---

Published as a conference paper at ICLR 2025
for the GW and PGW problems, respectively, the subsets of matrices
((p.g)= (7 R 7Im= = 1 = = lf Σ p =1 Σ 9
Ig
(12)
q= = f E R4 7Im S SP,y In S q).
(13)
for any pair of non-negative vectors p E 14,, q IR4, where 1p is the vector with all ones in R" (resp. Im), and 71m S p means that component-wise the S relation holds.
Given by a non-negative function L Rux= x Rmxm - R the transportation cost. M and the 'partial' transportation cost M are represented by the n x m X n X m tensors: and M := 2A == M 2 where m.m. is the lensor with ones in all its entries. For each X m and each n x m matrix ", we define tensor-matrix multiplication M o 7 E Raxm by
MaJ.s = L(C C
(14)
lensor M
(Mo = E(Mes
Then, the Partial GW problem in (10) can be written as (X, Y)= = min
Cx(()) + A(Ipl2 + |q/3),
where
(15)
(ELs(P-))
(xr(7)== :- My Σ Mas Σ 1 7M,,))
(16)
and (r stands for the Frobenius dot product. The constant term A(pl2 lq will be ignored in the rest of this paper since it does not depend 7.
4.1 FRANK-WOLL FOR THE PGW PROBLEM SOLVER
In this section, we discuss the Frank-Wolfe (FW) algorithm for the PGW problem (15). A second variant of the FW solver is provided in the Appendix G.
As a summary, in our proposed method, we address the discrete PGW problem (15), high- lighting that the dtrection-finding subproblem in the Frank-Wand Wolfe (FW) algorithm is POT problem for (15). Specifically, (15) treated as a discrete POT problem in our Solver 1, where we apply Proposition 2.1 to solve discrete OT problem.
For each itcration k, the procedure is summarized in three steps detailed below.
The convergence analysis, detailed in Appendix K, applies the results from (Lacoste-Julien, 2016) our context, showing that the FW algorithm achieves stationary point a rate of ((L/vk) for non-convex objectives with a Lipschitz continuous gradient in a convex and compact domain.
STEP COMPUTATION OF GRADIENT AND OPTIMAL DIRECTION.
is straightforward to verify that the gradient of the objective function (16) in (15) is given by
(17) The classical method to compute M o is the following: First, convert M into an (n X m) x (n X m) matrix, denoted as ((M) and convert 7 into an (n x m) vector v(7). Then, the computation of M o y is equívalent to the matrix multiplication e(M)v(7). The
(1) = 2M o.
computational cost and the required storage space are Onn In certain conditions, the above computation can be reduced to O(n² m²). We refer to Appendices F and H for details.
Next, we aim to solve the following problem:
(ky arg min () 7) (p-q)
JET's (P-a(
which is discrete POT problem since it is equivalent to
min (2M 78), ()))))))>)) + X/y (k) ((pl + |q| 2/7)).
(E"'(p-q)
The solver can be obtained by firstly converting the POT problem into an OT problem via Proposition 2.1 and then solving the proposed OT problem.

---

Published as a conference paper at ICLR 2025
Algorithm 1: Frank- Wolfe Algorithm for PGW, ver 1
Input: / Ei= Pj Se, 2==1 97 0y 7(1)
Output: ((Sinal)
Compute Cx ,.x
for k = 1, do
G t 2M o o // Compute gradient
711) + arg min (p.g) (G(k), 7)) ())) // Solve the POT problem.
Compute (*) [0. via (18) // Line Search
((++)) + (1 a (,()) + (8)) (k// Update 7
if convergence, break end for (ffnna)) 7()
STEP 2: LINE SEARCH METHOD.
In this step, at the k-th iteration, we need determine the optimal step size:
a (k) = arg min {Lrr ((1 - a)),(1)) + (a) )} aE/u,1]
The optimal a (8) takes the following values (sce Appendix for details):
{
0
a S 0, 0 b> 0, a S 0, + 6- 0, where
87 (8) 7,0 - -700)
Let (k)
a == (M 06,(1),8 67(1)))
clip(
=b 2a
[0, 1I)
if > 0,
b = 2(M o 1k), ,))(
(18)
and clip( -b [0, 1]) = m
2n 13
b
2n
STEP 3: UPDATE (1+11) + (1 - ((l))) (1)) + (1())
4.2 NUMERICAL IMPLEMENTATION DETAILS
The initial guess, 701) In the GW problem, if there is no prior knowledge, the initial guess is set to 71(1) pq
In PGW, however, as μ, v may not necessarily be probability measures (i.e., Σ E,r,,,, + 1 in general), we set y0))
It is straightforward to verify that (1) E T (p, as pl
pq
1m lqlp
lpl
max(pp). (q)) S.. (" max([p], I q.
Golumn/Row-Ren Rod-uttttiiooon According to the interpretation of the penalty weight param- eter in the Partial OT problem (e.g. see Lemma 3.2 in (Bai et al., 2023)), during the POT solving step, for each [1 n] (or j E [1 ml), if the 5th row (jth column) of M o (() contains a non-negative entry, all the mass of p (q) will destroyed (created). Thus, we can remove the corresponding row (column) to improve the computational efficiency.
EXPERIMENTS 5.1 Toy EXAMPLE: SHAPE MATCHING WITH OUTLIERS
We use the moon dataset and synthetic 2D/3D spherical data in this experiment. Let {z, Win {3, / denote the source and target point clouds. In addition, we add mm (where 7 20%) outlicrs to the target point cloud. See Figure 1 for visualization.
We visualize the transportation plans given by the GW (Mémoli, 2011), MPGW (Chapel et al., 2020), UGW (Séjourné et al, 2021), and our proposed PGW problems. For MPGW. UGW, and PGW, we set the mass to be for each point in the source and target point clouds. For GW, we normalize the mass of these points that the source and target have

---

Published as a conference paper at ICLR 2025
the same total mass. From Figure observe that PGW and MPGW induce one- by-one relation in both cases, and no outlier points are matched to the source point cloud. Meanwhile, GW matches all of the outliers. For UGW, as it applies the Sinkhorn algorithm, we observe mass-splitting transportation plans in both cases. Moreover, we observe that some mass from the outliers has been matched, which is not desired.
data ritce sie
GW
MPGW
UGW
PGW
SAR SARA aattrrreeeeeeee
SAR rerre
120
1966
Figure 1: The set of red points comprises the source point cloud. The union of the dark blue (outliers) and light blue points comprises the target point cloud. For UGW, MPGW, and PGW, set the mass for each point to be the same. For GW, normalize the mass for the balanced mass constraint setting.
5.2 SHAPE RETRIEVAL
Experiment setup. We now employ the PGW distance to distinguish between 2D shapes, as done in (Beier et al., 2022), and use GW, MPGW, and UGW baselines for comparison. Given a series of 2D shapes, we represent the shapes as mm-spaces X' = (TR2 11,, 1²), where n² = Σr' a a'622. For the GW method, we normalize the mass for the balanced mass constraint setting (i.e., = ) and for the remaining methods, we let a² for all the shapes, where a >> 0 is a fixed constant. In this manner, we compute the pairwise distances between the shapes.
We then use the computed distances for nearest neighbor classification. We do this by choosing representative at random from each class in the dataset and then classifying each shape according to its nearest representative. This is repeated over 10,000 iterations, and generate confusion matrix for each distance used. Finally, using the approach given by (Beier el al., 2022; Titouan et al., 2019b), we combine each distance with a support vector machine (SVM), applying stratified 10-fold coss-validation. In each iteration of cross-validation, we train an SVM using exp(-oD) as the kernel, where D is the matrix of pairwise distances (w.r.t. one of the considered distances) restricted folds, and compute the accuracy of the model on the remaining fold. We report the accuracy averaged over all 10 folds for each model.
Dataset setup. We test two datasets in this experiment, which we refer to as Dataset I and Dataset II. We construct Dataset by adapting the 2D shape dataset given (Beier al., 2022), consisting of 20 shapes in each of the classes: bone, goblet, star, and horseshoe. For each class, we augment. the dataset. with an additional class by selecting either a subset of points from each shape of that class (rectangle/ bone, trapezoid/ goblet, disk/ /staattarrraaa adding additional points to each shape of that class (amnulus/ hhoseshoe).. Hence, the final dataset. consists of 160 shapes across total classes. This dataset is visualized in Figure 9a.
For Dataset II, we generate 20 shapes for each of the classes: rectangle, house, arrow, double arrow, semicircle, and circle. These shapes were generated in pairs, such that each shape of class rectangle is a subset of the corresponding shape of class house, and similarly for arrow anrow/double arrow and semicircle/circle. This dataset. is visualized in Figure Db.

---

Published as a conference paper at ICLR 2025
DWV
USW
POW Tours)
In each row, the first figure visualizes an example shape from each class, and the second figure visualizes the resulting pairwise distance matrices. The first row corresponds to Dataset I, and the second corresponds to Dataset II.
Figure 2:
Distance
Dataset
Dataset II
Distance
Dataset
Dataset II
GW
0.9813
0.8083
GW
49.02s
137.122
MPGW
0.2375
0.2500
MPGW
49.
93.90s
UGW
0.89375
0,9000
UGW
1484.49s
519.91s
PGW (ours)
0.9625
1.0000
PGW (ours)
35.92s
79.27s
(a) Mean accuracy of SVM using each distance the kernel.
(b) Wall-clock time comparison.
Table 1: Accuracy and wall-clock time comparison for shape retrieval experiment.
Performance analysis. We refer to Appendix O for full numerical details, parameter settings, and the visualization of the resulting confusion matrices. We visualize the two considered datasets and the resulting pairwise distance matrices in Figure 2. For the SVM experiments, GW achieves the highest accuracy on Dataset I, 98.198.19 13%, while the second best method PGW, 96.25%. For Dataset II, PGW achieves the highest accuracy, correctly classifying 100% of the samples. The complete set of accuracies for all considered distances on each dataset reported in Table la.
In addition, report the wall-clock time required to compute all pairwise distances for cach distance in Table 1b. We observe that GW, MPGW, and PGW have similar wall-clock times across both experiments (30-50 seconds for Dataset I, 80-140 seconds for Dataset II), with PGW admitting a slightly faster runtime in both cases. Meanwhile, UGW requires almost 1500 seconds the experiment with Dataset I and over 500 seconds on the experiment with Dataset II.
5.3 PARTIAL GROMOV- WASSERSTEIN BARYCENTER AND SHAPE INTERPOLATION
By (Poyré ct al., 2016), Cromov-Wassersee can be applied to interpolate two shapes via the concept of Gromov- Wasserstein Barycenters. In this paper, we introduce Partial Gromov- Wasserslein Barycenters by exlending the GW Barycenter to the setting of PGW as follows.
Consider the discrete mm-spaces X!..... ,..., KK where X (X*,, || I| E 1 b24)) with X = { 1 C Rd We denote C = [||= a 12 and p* = p Given
positive constants A O, the PGW Barycenter defined by:
min Σ EM(M(C, * 212
(19)
C.ah
where each n* p*). We refer to Appendix M for the solver of (19) and details.
9

---

Published as a conference paper at ICLR 2025
Experiment setup. We apply the PGW barycenter to the following problem: Given two shapes X = {oi]i=1 C Rd and Y f C R modeled as mm-spaces X = (X, -l llss -i=1 6z,) and Y = (Y, 11z2, Ei= b we wish to find interpolations between them. In addition, we assume Y corrupted by noise, i.c., Y is redefined as (Y, || Ile >i= 6y, + >;=1 6%,) with Y YU ) where v E [0, 1] is the noise level and each ys is randomly selected from a particular region R Rd2
POW CW.
data
= D/7
t= 1/7
t 2/7
t 3/7
t 4/7
t 507
t 6/7
tw 777
Figure 3: In the first columm, the first and second figures are the source and larget point clouds in the first experiment (1) = 5%); the third and fourth figures are the source and target point clouds in the second experiment (7=10%)
Dataset sctup. We adapt the dataset given in (Peyré et al., 2016). See Appendix M.1 for further details the dataset. In this experiment, we test 1 5%, 10%. We visualize the barycenter interpolation from I = 0/7 to t= 7/7, where (1 - 1), / are the weight of the source X and the target Y, respectively, in the barycenter (19). The visualization given in Figure 3 is obtained by applying SMACOF MDS (multidimensiooal scaling) of the minimizer C.
Performance analysis. From Figure 3, we observe that in these two scenarios, the inter- polation derived from GW is clearly disturbed by the noise data points. For example, in rows 3, columns t 1/7,2/77, 3/7, we see that the point clouds reconstructed by MDS have significantly different width-height ratios from those of the source and target point clouds. In contrast, PGW siguificantly less disturbed, and the interpolation more natural. The width-height ratio of the point clouds generated by the PGW barycenter is consistent with that of the source cource/target point clouds.
SUMMARY
In this paper, we propose the Partial Gromov- Wasserstein (PGW) problem and introduce two Frank- Wolfe solvers for As byproduct, we provide pertinent theoretical results, including the relation between PGW and GW, the metric property of PGW, and the PGW barycenter formulation. Furthermore, we demonstrate the efficacy of the PGW solver in solving shape matching, shape retrieval, and shape interpolation tasks. For the shape trieval experiment, we observe that due to their metric property, PGW and GW have similar accuracy and outperform the other methods evaluated. In the shape matching and shape interpolation experiments, we demonstrate that PGW admits a more robust result when the data corrupted by outliers/noie data.
ACKNOWLEDGMENTS
This research was partially supported by the NSF CAREER Award No. 2339898.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
David Alvarez- Melis and Tommi Jaakkola. Gromov-wasserseen alignment of word embed- ding spaces. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1881-1890, 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp- 214-223. PMLR, 2017.
Yikun Bai, Bernhard Schmitzer, Matthew Thorpe, and Soheil Kolouri. Sliced optimal partial transport. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognation, pp. 13681-13690, 2023.
Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applica- tions in generative modeling and domain adaptation. Advances in Newral Information Processing Systems, 33:1293: 12944, 2020.
Florian Beier, Robert Beinert, and Gabriele Steidl. On a linear gromov wasserseenn distance. IEEE Transactions on Image Processing, 147292-7305,, 2022.
Jessa, Bekker and Jesse Davis. Learning from positive and unlabeled data: A survey. Machine Learning, 109:719 760, 2020.
Benamou, Brittany Froese, and Adam M Oberman. Numerical solution of the optimal transportation problem using the monge-ampère ampère equation. Journal of Computational Physics, 260:107-126, 2014.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iterative bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2):A1111 A1111-A1133 2015.
Nicolas Bonneel and David Coeurjolly. SPOT: sliced partial optimal transport. ACM Trunsactions on Graphics, 38(4):1-13, 2019. URL https://dl acm. wtw.mooo///oo/...11111
3306346. 3323021.
Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel. Generalized multidimen- sional scaling: a framework for isometry-invarian partial surface matching. Proceedings of the National Academy of Sciences,
2006.
Diitri Burago, Yuri Burago, Sergei Ivanov, et al. A course in metric geometry, volume 33. American Mathematical Society Providence, 2001.
Luis A Caffarelli and Robert J McCann. Free boundaries in optimal transport and monge- ampere obstacle problems. Annals of mathematics, pp. 673 773-730, 2010.
Cedric Cagniart, Edmond Boyer, and Slobodan Ilie. Free-form mesh tracking: a patch-based approach. In 2010 IEEE Computer Society Conference on Computer Vision and Pottern Recognétion, pp. 1339 1346. IEEE, 2010.
Zixuan Cang, Yaqi Wu, and Yanxiang Zhao. Supervised gromov- optimal trans- port. arXiv preprinl ar Xiv:2440 002260 2024.
Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applica- tions on 33:2903-200 2913, 2020.
unlabeled learning. Advances in Neural Information Processing Systems,
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavv Xavier Vialard. An in- terpolating distance between optimal transport and Fisher- Rao metrics. Foundations of Computational Mathematics, 18(1):1-44, 2018a.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavin Xavier Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87 (314):2563- 2609, 2018b.
11

---

Published as a conference paper at ICLR 2025
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. Unbal- anced optimal transport: Dynamic and Kantorovich formulations. Journal of Functional Analysis, 274(11) 2018c.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distri- bution optimal transportation for domain adaptation. Advances in newral information processing systems, 30, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in newral information processing systems, 26, 2013.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In Inter- national conference on machine learning, pp. 685-693. PMLR, 2014.
Nicolò De Ponti and Andrea Mondino. Entropy-transped distances between unbalanced metric measure spaces. Probability Theory and Related Fields, 184(1-2):159 208, 2022.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: deep convolutional activation feature for generic visual recogni- tion. In International conference machine learning, pp. 647-655. PMLR, 2014.
David A Edwards. The structure of superspace. Studies in topology, pp. 121-133. Elsevier, 1975.
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 223-220,220 2008
Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courly. Unbalanced minibatch optimal transport: applications to domain adaptation. In International Conference on Machine Learning, pp. 3186 3197. PMLR, 2021.
Alessio Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-500 560, 2010.
Alessio Figalli and Nicola Gigli. new transportation distance between non-negative mea- sures, with applications to gradients flows with dirichlet boundary conditions. Journal de mathématiques pures et appliquées, 94(2):107-183 130, 2010.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Tevgen Redko, Antoine Rolct, Antony Schutz, Vivien Seguy, Danica Sutherland, Romain Tave- nard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1 8, 2021. URL http: //mmr. org/ ptggpapprss/22. 20-451.html
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Noval research logistics quarterly, 3(1-2):95 110, 1956.
Tryphon Georgion, Johan Karlsson, and Mir Shahrouz Takyar. Metrics for power spectra: an axiomatic approach. IEEE Transactions on Signal Processing, 57(3):859 867, 2008.
Justin Gilmer, Samucl Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263 1272. PMLR, 2017.
M Gromov. Metric structures for riemannian and non-riemannian spaces. Bulletin of the American Mathemalical Sociely, 38:353 363, 2001.
Michael Gromov. Groups of polynomial growth and expanding maps (with appendix by jacques tits). Publications Mathémaliques de ITHÁS, 53:53 78, 1981a
12

---

Published as a conference paper at ICLR 2025
Mikhael Gromov. Structures métriques pour les variétés riemanniennes. Teates Math., 1, 1981b.
Kevin Guittet. Extended Kantoroeich norms: a tool for optimization. PhD thesis, INRIA, 2002.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information pro- cessing systems, 30, 2017.
Florian Heinemann, Marcel Klatt, and Axel Munk. sentorovvic--ubbinsteen distance and barycenter for finitely supported measures: Foundations and algorithms. Applied Mathe- maties Optimization, 87(1):4, 2023.
Yu-Guan Hsich, Gang Niu, and Masashi Sugiyama. Classification from positive, unla- beled and biased negative data. In International Conference on Machine Learning, pp- 2820-2829. PMTRR 2019.
Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from positive and unlabeled data with a selection bias. In International conference on learning represenlations, 2018.
Soheil Kolouri, Navid Naderializadeh, Gustavo K Rohde, and Heiko Hoffmann. Wasserstein embodding for graph learning. In International Conference on Learning Representations, 2020.
Lemin Kong, Jiajin Li, Jianheng Tang, and Anthony Man-Cho So. Outlier-robust gromov- wasserstein for graph data. Advances in Neural Information Processing Systems, 36, 2024.
Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives, arXiv preprint orXiv:1607.00330 2016.
Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and barycenter computation. Advances in Neural Information. Processing Systems, 34:21947-21958 2021.
Jan Lellmann, Dirk A Lorenz, Carola. Schonlieb, and Tuomo Valkonen. Imaging with kantorovich rubinstein discrepancy. SIAM Journal on Imaging Sciences, 7(4):2833 2859, 2014.
Matthias Liero, Alexander Mielke, and Giuseppe Savare. Optimal entropy-transport prob- lems and a new Helinger-Kantorviith tiones mathematicae, 211 2018. URL http: sttp://link.. springer.cooooo com/10. 1007//00222-017-0775--
Kantorovich distance between positive measures. Inven-
Weijie Liu, Chao Zhang, Jiahao Xie, Zebang Shen, Hui Qian, and Nenggan Zheng. Partial gromov-wasserster learning for partial graph matching, arXiv preprint ar SrXiv:2012.01253, 2020.
Xinran Liu, Yikun Bai, Huy Tran, Zhanqi Zhu, Matthew Thorpe, and Soheil Kolouri. Ptlp: Partial transport (2 distances. In NewrlPS 2023 Workshop Optimal Transport and Machine Learning, 2023.
Facundo Mémoli. Spectral wrsserewn distances for shape matching. In 2009 IEFE 1 12th International Conference on Computer Vision Workshops, ICCV Workshops, pp- 256 263. IEEE, 2009.
Facundo Mémoli. Gromov-wasserse distances and the metric approach to object match- ing. Foundations of computational mathematics, 11:417-488 2011.
Anh Duc Nguyen, Tuan Dung Nguyen, Quang Nguyen, Hoang Nguyen, Lam M. Nguyen, and Him-Chuan Toh. On partial optimal transport: Revised sinkhorn and efficient gradient methods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, 2024.
13

---

Published as a conference paper at ICLR 2025
Quang Minh Nguyen, Hoang H Nguyen, Yi Zhou, and Lam M Nguyen. On unbalanced optimal transport: Gradient methods, sparsity and approximation error. The Journal of Machine Learning Research, 2023.
Sloan Nictert, Rachel Cummings, and Ziv Goldfeld. Robust estimation under the wasscrstein distance. arXiv preprint wxXi:2302.01223 2023.
Nicolas Papadakis, Gabriel Peyré, and Edouard Oudet. Optimal transport with proximal splitting. SIAM Journal on Imaging Sciences, 7(1):212 238, 2014.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov- wasserstein averaging of kernel and distance matrices. In International conference on machine learning, pp. 2664-20000 2672. PMLR, 2016.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundalions and Trendsot in Machine Learning, 11(5-6):355 607, 2019.
Benedetto Piccoli and Francesco Rossi. Generalized wasserstein distance and its application to transport equations with source. Archive for Rational Mechanics and Analysis, 211: 335 358, 2014.
Sharath Raghvendra, Pouyan Shirzadian, and Kaiyi Zhang, A new robust partial p- wassorstein-basee metric for comparing distributions. arXiv preprint arXiv:2405. 036664,, 2024.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category mod- cls to new domains. In Computer Vision-ECCV 2010: 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Port IV 11, pp. 213 226. Springer, 2010.
Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55 (58463):94, 2015.
Thibault Séjouréé, François-Xavier Vialard, and Gabriel Peyré. The unbalanced gromov wasserstein distance: Conic formulation and relaxation. Advances in Neural Information Processing Systems, $4:8766-8777 2021.
Thibault Séjourné, Clément Bonet, Kilian Fatras, Kimia Nadjahi, and Nicolas Courty. Un- balanced optimal transport meets wasses-wwsss arXiv preprinl ar arXiv:2306.077 07176, 2023.
Karl-Thcodor Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces, volume 290. American Mathematical Society, 2023.
Alexis Thual, Quang Huy Tran, Tatiana Zemskova, Nicolas Courty, Rémi Flamary, Stanislas Dehaene, and Bertrand Thirion. Aligning individual brains with fused unbalanced gromov wasserstein. Advances in Neural Information Processing Systems, 35:21792 21804, 2022.
Vayer Titouan, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning, pp. 6275 6284. PMLR, 2019a.
Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Rémi Flamary, Optimal transport for structured data with application graphs. Tn Kamalika Chand- huri and Ruslan Salakhutdinov (eds.), Proceedings of the 96th International Confer- ence Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6275 6284, Long Beach, California, USA, 09 15 Jun 2019b. PMLR. URL http: //proceedings mlr. ppess/v97 http//////ttttttttttee htmm..
Cedric Villani. Topics in Optimal Transportation. American Mathematical Society, 2003.
URL hattp://wwr ams.org, .ewss.rggggsoee htt.sor/////./......
Cedric Villani. Optimal tronsport: old and new. Springer, 2009. URL https: //www cedricvillani.
14

---

Published as a conference paper at ICLR 2025
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable gromov-wasserseii learning for graph partitioning and matching. Advances in neural information processing systems, 32, 2019a.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wassorteinn learning for graph matching and node embedding. In International conference on machine learning, pp. 6932 6941. PMLR, 2019b.
15

---

Published as a conference paper at ICLR 2025
A
NOTATION AND ABBREVIATIONS
OT: Optimal Transport.
POT: Partial Optimal Transport.
GW: Cromov-Wassersteee
PGW: Partial Gromov-Wassorsten.
FW: Frank-Word
MPGW: Mass-Constrainel Partial Cromov-Wassersteddd
|| ||: Euclidean norm.
X² x X.
M+(X): set of all positive (non-negative) Randon (finite) measures defined on X.
P2(X): set of all probability measures defined on X, whose second moment is finite.
R4: set of all non-negative real numbers.
RTxm; set of all n x m matrices with real coefficients.
R4 (resp, R+): set of all n x m matrices (resp., n-vectors) with non-negative coofficients.
Baxxxиxи; set of all
tensors with real coefficients.
In Iaxms Ixxmxxxmi vector, matrix, and tensor of all ones.
1 gg characteristic function of measurable set E
1x(2) {o
= E, otherwise.
X, Y: metric measure spaces (mm-spaccs): X = (X,dx,u), Y (Y, v).
C given discrete mm-space X (X, dx, 14), where X far,... Enl, the symmetric matrix C E R2x" is defined as C2, = d% (x,,
s2 product measure j & J..
T④o: T: X + Y is measurable function and is measure X. Two is the push-forward measure a, i.e. its the measure on such that for all Borel set A Y, T+o aT (A)-
7:71, 72: 7 is joint measure defined in product space having 71, 72 as its first and second marginals, respectively. In the discrete setting, they are viewed as matrices and vectors, i.e., y E RR and 71 yI E TRT, 72 = 7 1, E Rm
X x Y + X, canonical projection mapping, with (x, + Similarly, 22 X x Y + is canonical projection mapping, with (z, y) + y.
ø1,2 : X Y Xx XxY, canonical projection mapping, with (8,ar (x. Similarly, N0.1 maps (s,2,)) y) to (s,x); N0,2 maps (s, v) to (s,y).
I(u,,), where E (2))), WEE P2(Y)) (where X, Y may not necessarily be the same sct): is the set of all the couplings (transportation plans) between p and v, i.c. T(H,v) = =f P2(X x Y):
H2 = v).
I'(p, q): set of all the couplings between the discrete probability measures
E x 8z, and Σ 43 ōy, with weight vectors
JT
and q=
m
(20)
That is, r(p. q) coincides with I'4, v), but it is viewed subset of matrices defined in (12).
p.g: q: real numbers 1 S P.q < oc.
P. q: vectors of weights as in (20).
p (P.....,Py Pm] p' Iy.... p/l if p3 p/, for all $ j n.
16

---

Published as a conference paper at ICLR 2025
pl Ei=1 P: for p [p1 ........ Pol-
cxz xxx + I2, denotes the cost function used for classical and partial optimal transport problems. lower-semi continuous function.
OT(,, p): it is the classical optimal transport (OT) problem between the probability measures p and v defined (1).
Wplu, v): it is the p- Wasserstein distance between the probability measures μ and v defined in (2), for 1 S < 00.
( v; A): the Partial Optimal Transport (OPT) problem defined in (3). |p]: total variation norm of the positive Randon (finite) measure j defined measurable space X, i.e., |r| = =x)))
μ S a: denotes that for all Borel set. B S X we have that the measures μ,a M+(X) satisfy (BB) I (B). Ig(u,)), where μ E (X), M+ set all "partial transportation plans" Ts(u,)) = Mx x Y): "1 14 S v).
[p, q): set of all the "partial transportation plans" between the discrete prob- Σ= 0/ 6g, with weight vectors 19 .......hhh -.d- That is, (p, coincides with (g)(u,) but it viewed as a subset of n x m matrices defined in (13).
ability measures μ Ei=1 P 8z, and
p ip....,, P and
À > 0: positive real number.
xo: auxiliary point.
= ((o).
n, D: given in (4).
a: given in (53).
9: given in (6).
é(t-)) & x x - R4: cost as in (5).
L:RxR + R: cost function for the GW problems.
D:Rx R + R: generic distance on R used for GW problems.
GWV(.,): ): GW optimization problem given in (7).
GWP())): GW optimization problem given in (7) when T(a, b) la BlP.
GW](.)) general GW optimization problem for g 2 1 given in (33).
GWP(.)): general GW optimization problem for 2 1 and I(a, b) = la blP given
in (34).
GWP, (s:): generalized GW problem given in (39).
GW: GW-variant problem given in (51) for the general case, and in (55) for the discrete setting.
i.: cost. given in (16) for the GW-variant problem.
d: X x (oo): "generalized" metric given in (50) for X.
X ~ W: equivalence relation in for mm-spaces, X W and only if they have the same total mass and GWP(X, Y) = O.
PGWXg(s)) (s:): partial GW optimization problem given in (9) or, equivalently, in (10).
PGWR,g6 partial GW optimization problem given in (10) when L(a, b) -la-bbe
PGWX(-e)) is is the PGW problem PGWP (.--) for the case when =
(()): given a measure and function Φ
u(Ø) / d(z)du(x).
17

---

Published as a conference paper at ICLR 2025
C(y; A, p, v): the transportation cost induced by transportation plan y T (1(,, in the Partial GW problem 10,
C, p,, = 82 (L + A(M1 +u/2 1v22-11133
C: functional for the optimization problem PGWA(+;))
M, M, and M: see (14), and (54). Notice that, (M 21) Mi,'..'' - 22.
t:)ee Frobenius inner product for matrices, i.e,, (A,B), = traco(A = Lng
m Ar for all B, R=xm.
M o: product between the tensor M and the matrix ?
V: gradient.
n] (l)
step size based on the linc search method.
10); initialization of the algorithm.
(k), 7(0); previous and new transportation plans before and after step 1 in the k-th iteration of version 1 of our proposed FW algorithm.
((a) g(k)'; previous and new transportation plans before and after step 1 in the k k-th iteration of version 2 of our proposed FW algorithm.
G = 27, G = 2M of: Gradient of the objective function in version I and version 2, respectively, of our proposed FW algorithm for solving the discrete version of partial GW problem.
(07; a, b) and (09, a, b): given in (18) and (56) for versions and 2 of the algorithm, respectively.
Cl-functio:: continuous and with continuous derivatives.
MPGW,(,>> ConstConstra Partial
defined in (77). (2, v): set transportation plans defined in (78) for the Mass-Constrained Partial Sromov-Wasserster problem.
B PROOF OF PROPOSITION 3.2
The idea of the proof inspired by the proof of Proposition 1 in (Piccoli Rossi, 2014).
The goal is to verify that
PGW Ag (X,
= inf J
d2 - - 32 + 82
82
7/2
7EM=(X,Y)
mass penalty
transport GW cost
inf
L(d d' >El'slai) ( (XxY)²
+ (1102
12
02 - 22) (21)
Consider 7 M4 Y) such that 71 S μ does not hold. Then we can write the Lebesgue decomposition of 71 with respect to μt:
= f w+
where f 2 is the Radon-Nikodym derivative of m with respect to Jt, and μz are mutually singular, that is, there exist mcasurable sets A, B such that A B X AU B and (+(A) 0, ((B) = 0. Without loss of generality, we can assume that the support of f lies on A, since
mEE)= S du(c) + (En VE C X measurable.
BnA
18

---

Published as a conference paper at ICLR 2025
Define A₁ = fa E A f(z) > 1), e :: f(x) s 1} (both are measurable, since f is measurable), and define ç = f.. 1}.. Then,
M 1
and iS fu S fu 1 u== =1 71
There exists a y E M+ x Y) such that "1 = P. S 7, and f2 S 72- Indeed, we can construct y in the following way: First, let {nr) be the set of conditional measures (disintegration) such that for every measurable (test) function vb X x XxY- R we have
I (((,)) = -fx 0l v) dr dn))).
Then, define y as
7(U) = /x J 11 v) ( (V) dp(r) W Borel.
Then, 7 verifies that T1 = R. and since á S n. we also have that 7 S 7 which implies
72 S 72-
Since hn = h22 and |hl
15l. then we have hi² - 71 = =122 - -
We claim that
1
78 2 11 70
+ h1² --
02
(22)
Left-hand side of (22): Since {A, B} is a partition of X, we first split the left-hand side of (22) as
11:02 - 02 = 82 - 71
82) (A x A) + (11 -1 B) (110 - ( A)
(T)
+ 81
82 ( x B).
(III)
Then we have
(111) = -
B) - x)) 0 = 1,-1,
(11) = (1022 - ( B) + - (1 x A) 2212~1(p 1(--
Since 71 fu in A, then 71 = in A₂ and 31 u A,, so we have
(u->))(A) = (A1)))(A)) + (u (p--0:1 (A)=) (n1- (11) + (u 71)(A2)
= -mn1 (A) + -4- (A)).
Thus,
(IT) - 21 - (A)(A) + 11--5000 (A))
and we also get that
(T) 82 71 (A A)
(4102 02
(2 (A1 x A1) + 01102 (02 (12)- x A2) +2)
(102--200000 x A2)
+ (1102 02 - ) x A1)
(1 -0)) x A1) + -2000-2000 202 x A2)+
-
+ +151 - 71 (A1 A2)) +
+ / 71 71 @ 71 71 A1)
= - 02 ) A1) + 02 71 ( x A2) + +(m - -
= -2 - ( - 01
82 (A A) + 2(m - (A)(41)4-77111))
Right-hand side of (22): First notice that
- (B) (m - (B) S (B) 1a+t,,
19

---

Published as a conference paper at ICLR 2025
and since fn and pbB) = 0, we have
(u (B)
Then,
1n 719 + hi 82 1 =
=m102 11 ( +
(A x A) +
B)
+ +n1 ) B) +) 11 (A B) 0710 71 12 ) x B)
+ (n - 7/ ) (1) 1 )
A)
S (1 02 - 719) A) +(1 11 (4 x A) + + 1 - (A).
+ +2
S(D)
=(IIl)
=(II)
Thus, (22) holds. We finish the proof of the proposition by noting that
82
7 + S2
202
s 32 7/ h 82
8/ 72
+ 1222
= =1182 - 12
- - 1/2
82
+ 82
7/2
S 12 1/2 + 82 82
where the first. inequality follows from (22), and the second inequality holds from the fact the total variation norm |-| satisfies triangular inequality. Therefore, 7 induces a smaller transport GW cost than (since S 7), and also decreases the mass penalty in comparison that corresponding to y. Thus, 7 is a better GW transportation plan, which satisfics f S μ. Similarly, we can further construct 5 based & such that 5 μ4, 5/2 v. Therefore, can restrict the minimization in (9) from M+ (X x Y) to (g(,, Thus, the equality (21) is satisfied.
Proof of Remark 3.1. Given 7 E [')(u,)), since 71 S 44 72 S v, and (X) = 1mal = Inl h72l (Y),, we have
12
02 =x - 7/ (x + 2 - - 62 +
1 - 72
= |11l + |/|2 2/1²3
and so the transportation cost in partial GW problem (10) becomes
[ [Xxxx (x, a.), By (v. /..l)) d=(2, v)d v/) + X (1 - -/2 + 1+ 2)
Sowe [(dg(1, d')
v/) + > (1u12 + 22/11)
Sxxry
(1 1) v/)
(1112 + (112+1u1p)
(23)
does not depend on y
C PROOF OF PROPOSITION 3.3
In this soction, we discuss the minimizer of the Partial GW problem (9). Trivially, I (p, S M_ x Y) and by using Proposition 3.2 it is enough to show that min- imizer for problem (10) exists.
We refer the reader to Mémoli (2011, Chapters and 10) for similar ideas.
20

---

Published as a conference paper at ICLR 2025
C.1 FORMAL STATEMENT OF PROPOSITION 3.3
Suppose X,Y Y are compact sets, then erists compact set [0, 3] C R, such that
d(z,z'), d(v.y') E [0, Vr, E X, v, EY
Let A = 0. Let LAz denote the restriction of L on A?, t.e. L A R with Aa (11, T(r1,r2), Vri, E A. Suppose I, salisfies the following: there exists 0 < < oo such that for every 12, A,
(L12((1,22) (r r2)1 K|ri ríl, (Laa(1i,2)) LAr(r,, r2)1 S Kkr r' (24)
(i.e,, LAz is Lipschilz on each variable). Then (G admils a minimizer.
Note, the condition (24) contains the case L(r1, r2) = In r2l as special case: Lemma C.1. If L(11, Ir r2l", for S oc, then L satisfies the condition (24).
Proof. Assune that L is defined
interval of the form [0, M), for some M > 0. Consider 22,1,,2,11, r2 E [0, MJ. If p = 1, by triangle inequality, we have
(2)), - L(r), r2)1 = ||| r2 In r2ll S In - -11
and similarly,
(L(1, L(r (r), S 12-2221 r/gl
From Mémoli (2011, page 473), since for 1 < oe, the function + to, for t E [0, is Lipschitz with constant bounded by pM we have
-(ri,r2)- ((1,, S pMM-1111 rr--ii ríl-
and similarly,
(L(1, - L(r1, S 1pM--11r - -r'al-
Lemma C.2. Given 2 1, consider 8 > 0. Then [0, c ca E [0,89] is a Lipschitz function.
Proof. Given C2 E [0, we have
lef - c S 9399-1111 - -c2
(25)
Thus, + al is Lipschitz function.
C.2 CONVERGENCE AUXILIARY RESULT
If sequence { converges weakly to 7, we write 7" A 7. In this setting, if n "6 7, it does not imply that (7")02 V 7,8 Thus, the technique used in classical OT for proving the existence of minimizer for the optimal transport optimization problem as consequence of the Stone- Weierstrass theorem does not apply directly in the Gromov- Wasserstein context.
Inspired by (Mémoli, 2011), introduce the following lemma.
Lemma C.3. Given metric space (Z, d,, suppose Φ Z + is Lipschilz continuous function with respect to (Z2, dt), where
(z((21222) (2' 2/)) = (2 2/) dz(z2, 2/2,,
(2/, V(2 (2), 2/) Z
Given 7 E (Z), and a sequence
{r" E (M) such that converges weakly to 7
n" (n - 00).
Finally, consider the mapping
2 z 7(0(z,))) = ((2,z")d77(+) e ER.
Then we have the following results:
21

---

Published as a conference paper at ICLR 2025
(1) ("(0(2,))) - (()(2.)) uniformly (when - 00).
(2) (0() -g00 ( (when oe).
(3) IfM M C M+ is compact for the weak converyence, then inf 7 (o(())) admils a manimizer.
Proof. The main idea of the proof is similar to Mémoli (2011, Lemma 10.3): we extend it from (Z) to M+ (Z).
(1) Since y" 3 7, and Z is compact, we have 1y - l7]. Then, given > 0, for sufficiently large we have bll
h
Let us denote by lol the Lipschitz constant of ø. For any 22, Z, we have:
hn(((=),)) (0(22, )) / (0(2), (z22,
S max (0(2)) -(2 2)(ml)
=EZ
$ (h7l + +e)lol)l dz(z1. 22) (dz(21,
where K= (hyl + c)lllllaap is a finite positive value. Note that the above inequality also holds if we replace 7" with 7.
Since (Z,dz) is compact, Z z= = U e/K) for some 2 NN E Z, where Bzz,, e/3K) = {2 E Z dz(z, S </3K] is the closed ball centered at 25 with radius e/ K. By definition of weak convergence, when n is sufficiently large,
(n" -)) (0((z, ()) < <//3, for each i E [1:N]:
Given 2 E Z, then E (22)) for some z;. For sufficiently large n, we have: (o( - 7(,(2.))
$ (o" 7" (ó(2, ))) +11))))1++""" (o(z,, 1) (6(2), )) (=((2))) )) - (6((, ))] < Kd(2, 2)) + c + Kd(2, 2)) = c/3 + c/3 + c/3 = e. Thus, we prove the first statement.
(26)
(2) We recall that we do not have (17)62 "i 02
Consider an arbitrary > 0. We have,
0 < lim sup ((7 (7 (b) (+))
(27)
n=+00
lim sup
(1 8 8))) (7 2 (0) + lim limsup (( (1) A_
n
B.,
For the first term, when n is sufficiently large, by statement (1), we have:
A, / (7"()(2,))) (0)-))))))(()))))))0 -)) dyy
$ max mmxx(""(((2,))) 7(0(2,))
<<(h++ +c)
(28)
Thus, lim sup,, A = lim, A =
Similarly, for the second term, when n is sufficiently large, we have
Bn = (7 / -(0))) ()) ())2))))) s s/7l-
(29)
Thus, limsup, B, = lim,, B. = 0.
Therefore, from (27), (28) and (29), we obtain
lim sup (( (2)) (+))²(())) 2=000
lim 1(7))82(0) (1))82 = 0. (30)
n-000
22

---

Published as a conference paper at ICLR 2025
(3) Let 7n E M be a sequence such that (7)) (weakly) converges to E.M (o). Since M is compact, there exists sub-sequence 7"t " 7 for some 7 E M. Then, by statement (2), we have:
(0) (0m0)"")00(0)) inf (6), yEM
and we complete the proof.
C.3 PROOF OF THE FORMAL STATEMENT FOR PROPOSITION 3.3
The proof follows the ideas of Mémoli (2011, Corollary 10.1).
Define (Z, d2) as = X x Y, with (z((2, (x', = dx(2, + dy(v.8))
We claim that the following mapping
(X Y)² 0 R
((I, (2' v/) + axx (1' (f',)')) Lid d' 22
is Lipschitz function with respect to dzz where L satisfies (24). Indeed, given ((11,8)) (2), 1/),,, ((22,82) (12, v/2)) E Z², we have:
(0((21,11,, (1), @((02 v2), (2/z v/2)11
= () v/1) L(dx (x2: x22), dy (82. 1/2)l1
S 2(d v/)) - L(dx (z2 x222 dy (11. v())
+ (22 v()) - L(dx (12, 22) (y2, 1/2)
S -x) + A (11, - (v2, v2)1
S {'1dx((1, [")
S -xx(,,, ("1 dy (1222/2)
(31)
2b)) + (d + dr (V/
(32)
= K'
+ ((dx (2), an)) + dy dy v/2)
dz (1/2 vb2) K'd ((1))((11)))) (22. ((01, v1), (I2, 422))
K" [dz
where in (31), K" -.3--1 K; the incquality holds by lemma C.2; The incquality (32) follows from the triangle inequality:
dx x1) - dx (I2, x/2) - (x x2) + dx (Iz, 25) + dx (12, - (x((22,,)))) xzn ) + dx (2),22)
= =x
and similarly,
dx 2/)) dx
(0), x1) < dx (1i, x2) + dx (x),
Let M = (H, From Liu et al. (2023, Proposition B.1), we have that (u, is compact set with respect to the weak convergence topology.
By Lemma (C.3) part (3), we have the PGW problem, which can be written as inf )0) A(In|2 [|u/2+Iub) 11|3)
(erg(n,))
admits solution, i.e,, a minimizer TT (M, Therefore, we end the proof of Proposition 3.3.
D PROOF OF PROPOSITION 3.4: METRIC PROPERTY OF PARTIAL GW
Let L(r1, (r,, r2) for metric D on R, and since all the metrics in R are equivalent, for simplicity, consider D(r,, = |r r2l. (Notice that this satisfies the hypothesis of Proposition H.1 used in the experiments).
23

---

Published as a conference paper at ICLR 2025
Consider the GW problem, for 1,
inf (X, Y): == TEl(Hu)) (xxx1
(x, x²), d)
(33)
or, in particular,
GWT(X,Y) inf / re((u.) (Xxx2² 1d (x d4 (v.3') dy
(34)
For probability mm-spaces we have the equivalence relation X ~ Y and only GW7(X, Y) 0.
By Mémoli (2011, Chapter 5), X Y is equivalent to the following: there exists bijective
isometry mapping Φ : X + Y, such that
dx dx(x,x²) dy (o(z), = =0, 0 a.s.
04H= v.
Remark D.1. In the literature, the case where 9 = 1 is the most frequently considered problem. In porticular, in (Mémoli, 2011) it is stated the equivalence relation X ~ Y if and only if there erists & x-x+- K-Y such that 64t4 = v and dx (I,x') = dy (Ø(x). ((x')(())))))))))))())))))))(( 1 a.s. 0. Thus, X ~'
Y is also equivalent to have : X -Y such that oy = and dx (x, x²== dy(y.v)) 702 - a.s. where y is a minimizer for GWT(X, Y). So, in this situation we also have d' (z, x') = dd(... (u.3') 782 a.s. for any given q 2 1. Therefore, K ~ Y if and only if GW? (X, Y) =
if and only if GWP(X.
D.1 FORMAL STATEMENT OF PROPOSITION 3.4
We first rntuue the formal statement of Proposition 3.4. To do so, we exlend the equiv- alence relation to all mm-spaces (not only probability mm-spaces): Given arbitrary mm-spaces X = (X, dx n), Y = (Y,dy, v), where X, Y are compact and μ E (X),, write X Y if and only if they have the same total mass (i.e., |p| = (X)) = u(Y) = ID)) and G) O.
(Y),),
Formal statement of Proposition 3.4: Given x > (PGWX,(..-)) defines a metric among mm-spaces under taking quotient with respect to the equivalence relation ~.
0. S P.q 0o, then
Next, we discuss its proof.
D.2 NON-NEGATIVITY AND SYMMETRY PROPERTIES
is straightforward lo verify PGWP In what follows, we will concentrate on proving PGWP
X.q (X, Y) 2 0, and that PGWP X.q (X, Y) = (Y,
3.g (X, Y) = 0 and only if if V:
If x ~ Y, then |n| = |2], and we have
S PGWT, X.g (X, S
0,
where the inequality follows from the fact (4,, v) C (1,, v). Thus, PGWP b.g (X, Y) = 0. X.g (X, Y) 0. We claim that |p| |p| and that
For the other direction, suppose that PGW there exist an optimal plan y for PGWP, X.g (X, Y) such that [r| ly| = jr]. Let us prove
this by contradiction. Assume |/4| < [v]- For convenience, suppose 1n|2 < |u|2 e, for some e > O. Then, for each 7 E I I''(pt (p, v), we have | S In|2 < |u|2 - e, and so
PGWP
X.q (X, Y) 2 2( + |u|2 2///2) 2 1|p21-111 2 >
Thus, PGWP X.g (X, Y) > 0, which is a contradiction. So, ||| = |r/ In addition, if E ( is optimal for PGWP X.g (X, Y), have 1 |u| ju]. thus E T(,,v). Therefore, since PGWP X.g (X, Y) = 0, and for such optimal 7 we have |n/ = |p| = -p/, we obtain
Juway (d'( - dl P/
24

---

Published as a conference paper at ICLR 2025
As result, d' (2,)²) (v. 702 - a.s., which implies that GX Y) 0, and so <
D.3 TRIANGLE INEQUALITY STRATEGY: CONVERT THE PGW PROBLEM INTO A GW PROBLEM
Consider three arbitrary mm-spaces S (S, x (X,dx, 1!), Y (Y,dy, v). We define $ = ($, dg. X = dx, d.) Y (Y, dy. 1) in a similar way that of Proposition G.1 but now aiming to have new spaces with equal total mass:
First, introduce auxiliary points don, 501, 5i2 and set
S SU (dop, d01, d02).
X X foc0, 601, do2),
y YU (000; 201, 602)-
Define 8, ft, & as follows:
j μ 10 p
(35)
û v + lo 000 + 1110550
Note that is not supported on point dog, similarly, f is not supported on d01, & is not supported on do2. In addition, we have [ |o| = |ō| = |p4| |e| + lor. (For a similar idea
in classical unbalanced optimal transport, see, for example, (Heinemann al., 2023).)
Finally, define dg : 52 + RU {oo} as follows:
dg(o,5') 11 (ds(s,')) if (s,
100
(36)
elsewhere
Note, .)(,,)) is not a rigorous metric in $ since we allow dg co. Similarly, define dx dy- As a result, we have constructed new spaces
$ dg)
Y= (Xt
dg)
(37)
We define the following mapping DA (R ( (RU (oo) R,:
I r2l" if 11, < x,, if r 00, 12
(2(1)
X
vice versa,
(38)
if r r2 oc.
Note that Dx is not rigorous metric since it may sometimes violate triangle inequality. See the following lemma for detailed and precise explanation.
Lemma D.2. Let Dx(:,) denote the function defined in (98). For any 11,72 (oo)) we have the following:
Dx(r1, 2 0. D2(1).2)= = if and only if T2, where denotes that F = 12 E R or r r2 0C.
Except the case F1, T2 E RR ro = 0o, for all other cases, we have
Dx(11,72) & Dx(r1.ro) + D2(r2.ro).
Proof of Lemma D.2. It straightforward to verify Dx(, :) 2 0.
Now, consider To, Pi, P2 RUfoo. If r2 R or ri P2 co, have Dx(ri, 0. Otherwise, Dx(ri,r2) > O. So, D2)ri,r2) = if and only if ri Y2.
For the second item, have the following cases:
25

---

Published as a conference paper at ICLR 2025
Case 1: To,77 R.
Dx(ri,2) = In r2
S n r2l + |r2 - rol
= = 11) + (2(
Case 2: r1, 12 E ER, ro = 00. We do not need to verify the inequality in this case.
Case 3: 11 E P2 co, or 20, Ro co. In this case, have Dx(11, = Dx = VX, (x(12,7o) =0
and it is Euraightforward to verify the inequality.
Case 4: 11, 00, E RR. In this case, we have Dx(r1, = 00 Dx(ro.r) + Dx(ro.12). Case r2, ro = oo. In this case, we have
Dx(r1, Dx(ri,ro) m))
and it is straightforward to verify the inequality.
We construct the following generalized GW problem:
GWP ( 2) = inf /
DR x (2, (2, (u. dy02.
(39)
(ET((,,) (XxD)
O(9:).000)
Similarly, we define GWP, X.g (X, $), and GWT,g P).
The mapping (6) is modified as:
Is 1) 3 , 70 E l' ji), 70t : (a 11 2 8:00 dāe @ (n (1-1 01) + 171000,, | S20
(o) 9 02 + 02 l' D),
; (a - 11 2 8000
+ dācs 2 -22) + 1700 + 1
(v 3 32 + 12 E l( 212 = + (μ - @ 8e + dāc 2 (v - -2)) + h9 + 1n10s0.
(40)
Remark D.3. It is straightforward to verify the above mappings are dell-defined addition, we observe that, for each 701 (o, 70 (s(o, v) Ts(,,
In
(1602) x X) - (dbz)) O,
(41)
(120)) x Y) = "S x (o.1) = O,
(42)
(1200) x X) = 222 x (200)) = O. Proposition D.4. If 12 E (1, is optimal in PGW problem PGWP 212 defined in (40) is optimal in generalized GW problem GW b (%, 9). Purthermore, C(522 p,,) = C22 >, (.v)), v), and thus,
K.g (X,Y), then
GWP R (2, Y). (X, Y) PGWP (x,
Proof of Proposition D.4. For each y E I's v), define & by (40).
Note that if we merge the points 61, oo dig as 6o, i.e.
6o 60 602 dcs,
the value Öl;;; A, is, 0) will not change. Thus, we merge these three auxiliary points.
26

---

Published as a conference paper at ICLR 2025
We have:
C(;;,, - 1 (8xpp Di(d' (x, x'), , (1,2)))
= -Jaayy
(xxy) 1 (x)(x, (v. 1P
Ad9 +
1r82
([00)x})
(Xx160))
+
Adg +2
AdR
20
((0))X)x(XXX))
(Xx(23))x(XX)
[[)))((0)]]
+2
D0 +2
00)200
(())x))((xx(())
((0)x((())x(XX))
+2
00 +2
(xx()))x((1) 00(00,
((0))(())x(()'
1 [xxxy (2 - dz d2
+22(11) h1/1 A(kl hn)² + +1((ml hDhl A(1a hy)²
= - (x,)) dz (v, 8 112 d7 x2) A(12 + |A|2 - -2/1)) = C(:A,,
As we merged the points 5o,, 222, 503, by Bai et al. (2023, Proposition B.1.), the mapping Y + á defined in (40) is a bijection. Then, 7 (u, is optimal for the PGW problem PGW (X, Y) (defined in (10)), & E I(2, 8) is optimal for generalized GW problem GWT, (X, Y) (defined in (39)). Therefore, G,T,(X,
GW (X, = PGW N.g YX.
Proposition D.5 (Triangle incquality for GWP (.g((.))) (.-)). Consider the generalized GW prob- lem (39). Then, for ony p E [o), we have
GWP, x. ( f) S
GWP A.q (S, x) + GWP X.q (8, 1)
Proof of Proposition D.5. We prove the case p = 2. For general p 2 1, it can be proved similarly.
Choose an optimal 722 E (4( for PGW? X Y), an optimal 701 E I' (a, p) for A.g PGW2 Ag (S, X), and an optimal 02 (a, for PGW2 (40).
A.g (S, Y). Construct 312,301, 300 by
By Proposition D.4, we have that 912, 201, 702 are optimal for GW3 ( (,, GW2,, (Ś, Y), respectively.
Y), GW2 3.g ($,
Define canonical projection mapping
No.1 :{$ x X x 8) + -$$ x X) (8, (s)
Similarly, we define Ta,2; 41,2-
By gluing lemma (see Lemma 5.5 (Santambrogio, 2015)), there exists & E M5 X x 8), such that ( (To,2)) = 902 Thus, (T12) f is coupling between fl, We have
CX, (x, Y) / (xxxy DR (z, x') ). d2 v/ 1d)
$ / / Di (x,2)) du. (u.)
(43)
27

---

Published as a conference paper at ICLR 2025
The inequality holds since (f12) 9/2 I(p, D), and 912 is optimal. Next, we will show that
Lerkwer //o 1 (x, &) (x.1))
Let ((s,2, (8', E (5,8, and assume that
(2 &. (v. (x(dg(e, (x, + (')
(44)
By Lemma D.2, (44) implics dx(r, (v. E RR,gg(s,s') = oc. Thus, by definition
(36), it also implics
ex. ( s
(45)
Define the following sets:
A. = $ x X x Y,,
Ag (000) X Y,
A = [001) x X xY,
A2 (002) X.
Notice that, (44) = (45) is equivalent to
(44) - ((x :::::A-:AAA x u As).
(46)
Next, we will show (A) 0. Indeed,
9(A)) S {(100)) x X x 8) = (((00)))
by definition (35) of 6
1(Ai) S {(100)) x X x Y) (000( x Y3) = by (42),
1(A2) < (((002) x X x X)= = (1662 x X3) =0 by (41).
Thus, (A) = 0. By considering ($ x 8 x Y)² \ A, we obtain
= - x'
since (A) =0
< / (D. (v. 2 d2
by (46)
< [8xxxx ( (D.(dg(s,))) (z,,') + d7. 2 d2
(47)
28

---

Published as a conference paper at ICLR 2025
Following (43) and (47); have
& (Lowenr Di(d (x, d(
1/2
(X, 2) (X
1/2
Veentres d) + (o, d782
1/2
1/2
(48)
1/2
- (2(d)(s,'') d (x, (x,
1/2
+ Ri (s, 5) d (..
- + GW3 R )),
where in the third inequality (48) we used the Minkowski inequality in ((((xxxx)) )02).
Now, we can complete the proof of Proposition 3.4: By the Propositions D.4, we have
PGW (x, Y) GWP X (X, and similarly for PGWP, A.g and (8, X), PGW (S, (8,Y). Y). By the Proposition D.5, GWP A.gg (3.)
satisfies the triangle inequality, thus We complete the proof:
PGWP ( Y)
GWP, g (x,
I GWP, (, + GWP
Agg (S, ($, V)
PGWP A.g (S, X) + PGWP A (S, Y).
E PROOF OF PROPOSITION 3.5: PGW CONVERGES TO GW AS \
Co. 00.
In the main text, set À E R.. In this section, discuss the limit when X - Lemma E.1. Suppose |u| S [p], for each ( v), there exists 7 E T (u, v) such that y S and (m1)*7 n.
Proof. Lot 7 E (
If hl [u], then have (mI)#7 Fc.
hy < [p], let 4e" = p- (T1) 1"====11 = = (T2)
We have that μ", v" are non-negative
measures, with [n"] = |ml] 11hl O. If we define
7 - |p|
10" 2 v²,
171
we obtain S5% In addition, we have:
(m)) = (TI)#7 + 1²"
(TI) 7 + 11" = p4
| h
14"
12"
(m2) (T2) v
|0|
(me)
#7 10'
[ h
V.
Thus, n E (Tg(u,))) and (m))7/ n
29

---

Published as a conference paper at ICLR 2025
Lemma E.2. Given general mm-spaces X
(Y, dy,y where p.v supported on bounded sets (in general, is assumed that X and Y are compact, and that supp(μ) X, supp(y) ), consider the problem the problem PGW continuous functions. If X is sufficiently large, in particular:
(X, p4), Y =
x.g (X, Y) with L(r,,r))
AZ max 2, Ecupp(u) v.y Esupp(r)
L(dx (z, x' dr (),1))),
then there exists optimal y for PGW Y) such that by) min((u), Iv])
Purthermore, when
[(dx(x, xe dr (v.2')),
max z.z Esupp(e) v.y Esupp())
the for all optimal y E (Ts(,,)), v); we have h|= min(lal,
Proof. We prove it for q 1. For a general q 2 1, can be proved similarly.
Without loss of generality, suppose |u| < p//.
Since v,v are supported on bounded sets, there exists
[0, such that
dx (x(2xx') x'), dy vy.v) E A for all x, E supp(μ), v. v E supp(r).
Thus, the restriction of L A?, denoted as L continuous on A?, and thus bounded. So, consider
m = max (L(r),72)) 2 T1,
dy, Va, E supp(p), u.y. E supp(v).
Suppose 2A 2 m+1, and assume that there exists optimal y I's [' v) such that |r| < |m]. By Lemma E.1, there exists 7' such that y I Y, (TI)#7' m. Thus, have
C(yiA,, C(niA, (
Ix (dx((x,x),,e v') 22 22d((')22-(1793)
$/xxn) m 2) (7)
= =- - 1n13)
= (1u|2 - 111?) < 0,
which is contradiction since y is optimal, and so we have completed the proof.
Lemma E.3. Consider probability mm-spaces X = (X, d), Y = that is, with
[pl |p| 1. Then, for each X >> 0, we have
PGW x. (x, S GW Y).
Proof. In this setting, we have V' C (T' v), and thus
inf g(r'gla))) (XXY)2
((d7(2, (') + A(ln||2 + (1f222(13)
I
inf (ET((u) (XXx72 / TEI(aN) (xxx]
(ld'(a, d2 (y, +(|a 1112 2//12)2227 2)
= inf
-GW, (X.Y)
Based the above properties, we now prove Proposition 3.5:
30

---

Published as a conference paper at ICLR 2025
Proposition E.4 (Generalization of Proposition 3.5). Consider general probability mm- spaces X (X, H), = (Y, =Y, dy.yy/ .V), that is, with 1 = // = 1, where X,Y Y are bounded. Assume that L is continuous. Then
lim PGWX X.g (X, Y) GW (x, Y). A
Proof. When À is sufficiently large, by Lemma E.2, for each optimal Y E T' (2, of the minimization problem PGW A.g (X, Y), we have hyl min([a), [n]) = 1. That is, TA v), Plugging "/ into C(7xi A, (,V),, we obtain:
PGW X.g (X, S(xMMP [(dx(1, x'), (.. + +1(12 +1 -
22 12)
J -XxAn L(d (z, x²), ) (v. /)) 2 GW (W,
By Lemma E.3, we also have PGW A,g (x, Y) & GW (x, Y) and we complete the proof.
F TENSOR PRODUCT COMPUTATION
Lemma F.1. Given lensor M E I=xmxxx and 7.76 E Ruxm the lensor product
operator M o o salisfies the following:
(i) The mapping + M ao is linear with respect to 7.
(ii) If M is symmetric, in particular, Misss = Mr Vi, E [1: nl. E [11: m]] then
Proof.
(i) For the first part, consider 7,7/ E Ruxm and hs R. For each i,j E [1 n] [1 m)) we have we have
(M ( 72))i
Σ M Day
155"
= Σ Maa + MMsirsdy
255"
25
= -MM )))s + (M o oodyr
(M (k7)) = Σ (
= k Σ
Mijas
3',3'
K(M 7))g.
Thus, M (o(++n')= Moy Moy M and M (kr) = kM o7. Therefore, + Mor is linear.
(ii) For the second part, we have
Σ
Σ Maswnhoh
(49)
(M)i,)
where (49) follows from the fact that M is symmetric.
n
31

---

Published as a conference paper at ICLR 2025
G ANOTHER ALGORITHM FOR COMPUTING PCW DISTANCE SOLVER
2
Our Algorithm 2 for solving the proposed PGW problem is based on a theoretical result that relates GW and PGW. The details of our computational method, as well as the proof of Proposition G.1 stated below, are provided Appendix G.1. Based on such a proposition, we extend the PGW problem to discrete GW-earrant problem (55), leading to solution for the original PGW problem by truncating the GW-variant solution.
Proposition G.1. Let X (X, be a mm-spocc. Consider an auriliary point do and let x = (X, xx p),, where X = (doo,, f is constructed by (4), and considering oo as an auciliary point to IR such that S oc for every x E IR, we extend dx into dx Xx2 - [xc) and define LA : RRU. }oo} - R as follows:
(x, xx,
if Nx E _2((1112) ((r,, -2 2X otherwise
T R elsewhere
(50)
00
0
Consider the following G GW-variant problem:
GW Y) = inf 702 (La (g)))
(51)
GET(A.0)
Then, when considering the bijection y + defined in (6), have that y is optimal for PGW problem (10) if and only if ft is optimal for the GW-voriant problem (51).
Remark G.2. Intuitively, the above proposition states that, by introducing auziliary points do, we can build an equivalent relation between PGW and GW problem. This idea is firstly discussed in (Cagniart et al,, 2010) in a classical optimal partial transport setting. In this paper, we extend the technique to the partial GW setting. However, this technique canmot be extended to the MPGW setting; we refer to Chopel et al. (2020, Appendiz A.3) for details.
Proof. The mapping F defined by (6) well-defined bijection, as shown in(aai ct al., 2023; Caffarelli & McCann, 2010).
Given 7 E T<(u,,), v), we have & = F(7) E r(2, D). Let Ö(Fsu,v) denote the transportation cost in the GW-variant problem (51), that is,
d O(AA,)) = J Lald (2, 2'), d (2. (2.0)) d)())))())))))))))))))) ()) v/)
Then, have
C(1A,115)) = -Jxwny (L(d) 22) d7 +
X(11| + |n])
does not dopend om 7
SEXMY SCCAN (x)) 22) d7 + +A(lA| + |w|)
(since flxxy
- -(xuvp
IIAAN (L
22) d2 + A(1al + Ip]) (as dglxxx = dxs delrxx = dy)
- (A, d4 + >(1ml + InD) (since ((RKR(s))) = (I(s-))- - 22))
02 + A(kk + [M|
(since L assigns 0 to do)
does not depend on
"CW L2 (x, i) is not rigorous GW problem since dx co is possible, thus it is not metric.
Also, X, V are not necessarily probability mm-spaces
32

---

Published as a conference paper at ICLR 2025
Combining this with the fact that F P y is bijection, have that y is optimal for (10) and only if y is optimal for (51). Under the assumptions of Proposition 3.3, there exists an optimal (p, for the PGW problem exists, and so we have:
arg min C(Fip = arg min C(T; U, (ET(U,0)
(52)
yET's sEE)(
Remark G.3. Both algorillmss (Algorilhmm 1 and 2) are mathemalically and compulationalyy equivalent, owing to the equivalence between the POT problem in Solver and the OT problem in Solver 2.
G.1 FRANK-WOLFE FOR THE PGW PROBLEM SOLVER 2
Similarly to the discrete PGW problem (15), consider the discrete version of (4):
p= [p: E I=++1, q= 19:///pl E Rm+1,
(53)
and, in a similar fashion, we define M E ( as
[Msss if
E [1: m],
Maj.'' (0
(54)
elsewhere.
Then, the GW-variant problem (51) can be written
GW (X, 9) min (El((p.4)
(9)
(55)
Based on Proposition G.1 (which relates PGW with GW )), propose two versions of the Frank- Wolfe algorithm (Frank et al., 1956) that can solve the PGW problem (15).
Apart from Algorithm in (Chapel et al., 2020), which solves different formulation of partial GW, and A Algorithm 1 in (Séjourné et al., 2021), which applies the Sinkhorn algorithm to solve an entropic regularized version of (8), to the best of our knowledge, precise computational method for the discrete PGW problem (15) has not been studied.
Here, we discuss another version of the FW Algorithm for solving the PGW problem (15). The main idea relies on solving first the GW-variant problem (51), and, at the end of the iterations, by using Proposition G.1, convert the solution of the GW-varian problem to solution for the original partial GW problem (15).
First, construct p, á, M as described in Proposition G.1. Then, for each iteration k perform the following three steps.
Step 1: Computation of gradient and optimal direction. Solve the OT problem:
g0ky arg min (2(()), (Er(P.4)
The gradient (2 can be computed a similar way as described Lemma H.2. We refer to Section H for details.
Step 2: Line search method. Find optimal step size (t);
a (k) = arg min (Gxr ((1 - ()2(1) + agg )}
ag(o.1)
Similar to Solver 1, let
(k( = 7(0)' - 7(0)
(M 05((k) 85(1)))
(56)
b= = 2(M o (g( ((0))
Then the optimal (k) is given by formula (18). See Appendix J for detailed discussion. Step 3. Update (k+11) (1 (K)) (+))))))
33

---

Published as a conference paper at ICLR 2025
Algorithm 2: Frank- Wolfe Algorithm for partial GW, ver 2
Input: / Ei=1 Pi 8 2==1 93 8y, 7(1)
Output: ([Sinal)
Compute C. C. Pb, 4,4
for k = 2. do
G(k) - 2M o 9(1)) // Compute gradient
4/4)" < arg minger(p.a) (G(A)) f) // Solve the OT problem
Compute a (k) [0, via (56), (18) // Line Search
q(k+1) + (1 (3(0) + a0((k/ Update
if convergence, break
end for (fénnat) 4- (1 n, ml
H GRADIENT COMPUTATION IN ALGORITTMM AND
In this section, we discuss the computation of Gradient v (7) in Algorithm 1 and VL (f) Algorithm 2.
Proposition H.1 (Proposition 1 (Peyré et al,, 2016)). If the cost function con be wrillen
= ( (2(22) hy (ri)ha(()))
(57)
then
Moy= = u(c*, ,r, ((0
(58)
where u(C*, :0x,,",,):== fic + 1,72 f2(C").
Additionally, the following lemma builds the connection between M o and M o%,
Lemma H.2. For any 7 E Raxm we have:
Mor= =oy=Mor Moy
- 22/7|
(59)
Proof. For any y Raxm, have
M o
(M I Inn.m,m 22) 0 7
= (M - 221mmmm 0
M 7 2mm 07
. 7 mmm
.M o 22/7/Ln,.
where the second equality follows from Lemma F.1.
Next, in the setting of Algorithm 2, for any R8 (g I1(=1)x((++1, we have
vL 2M o
(60)
and M f can be computed by the following lemma.
Lemma H.3. For each & E ((+++))xx (m++1), we have Mog E (1(++)xx0 1)++))x(+++)) with the following:
(M o 4[1 n, m)) if ml E [ ml elsewhere
(M f)g
(61)
0
34

---

Published as a conference paper at ICLR 2025
Proof. Recall the definition of M is given by (54), choose i E [1 ::nnj [1 ml, we have
(M o M)ss =
M.ss P +
f +
Σ Mag.mi+
+ 11m+mmmm+11m11
Mij
M f
1'1
(M (7L1 n, 1: ml))
If n n+1, 1, we have
n+1 m++1
(M o f)+11
Motises
Similarly, (M o 00)mm+1 = 0. Thus, we complete the proof.
I LINE SEARCH IN ALGORITHM
In this section, we discuss the derivation of the line search algorithm.
We observe that in the partial GW setting, for each E T (H,v), the marginals of y are not fixed. Thus, we can not directly apply the classical algorithm (e.g., (Titouan al., 2019a)).
In iteration k, let 708) , 7k)" be the previous and new transportation plans from step of the algorithm. For convenience, we denote them as and y,, respectively.
The goal is to solve the following problem:
min C(M, (1 - atyy + +ay) cE|0.1]
(62)
where C(M,7) (M (M (..)). By denoting 8y = 7 7, have L(M, (1 a)r + ann) L(M, 7 + ad7).
Then,
(M o (r + ad7), (7 adt))
(M ) (IM on, 07)) (M o0,7)))) a² 6%)
Let
(M 87,88)
(M o0,o0881 87) (M 87,7) 2(M o 7, 87)
(63)
c (M 07, 77,)),
where the second identity in (63) follows from Lemin F.1 and the fact that M M Mln.n,mm 2AIn is symmetric.
Therefore, the above problem (62) becomes
min aa² ba + c. aE[0.1]
The solution is the following:
if S 0
a²
if <
(64)
-b clip(
(0. 1))
if > 0.
2a
35

---

Published as a conference paper at ICLR 2025
where
b
E 10, 2g if
if -
bb [0, 1]) min { 1 1, (0,
-b1 2a
clip(
24 < 0,
2a
if
2a
We further discuss the difference in computation of a and b in the PGW setting and the classical GW setting. the assumption Proposition H.1 holds, by (58) and (59), we have
a = oMo
((Mody - 2 22)
(Mody, 2210712
(65)
(u(C*, 08)) - 111 (67 -2167113
b 2(M ),M)) -2(M o 22/2 87) 2((M o 0,5%) 2218>11111)
(66)
Note that in the classical GW setting (Titouan et al., 2019a), the term u(C* (Y,,7) On xm and |ō>| O. Therefore, in such line search algorithm (Algorithm 2 in (Titouan et al., 2019a)), the terms u(C* ,7)) 2A 6 are not required. In addition, in equation (66), M y, 2X/r| have been computed in the gradient computation step. Thus, these two terms can be directly applied in this step.
LINE SEARCH IN ALGORITHM 2
Similar to the previous section, in iteration k let (((), 2(0) denote the previous transporta- tion plan and the updated transportation plan. For convenience, we denote them as 9, respectively.
Let 0%- = -
The goal is to find the following optimal a:
= arg min L(M, (1- (1)),,)))))))) = arg min L(M, ad9 + aE/0.1]
(67)
ac(0,1]
where M E p(++lxx((+))))xxxXxxxxxxxxx with M[1 n, m. n. ml = M M
2 x
Similar to the previous section, let.
a (M 89,
b (M 8%,4)) + (M o 0,,4%r = 2(M rr.
(68)
(M o
where (68) holds since M symmetric. Then, the optimal a given by (64).
It remains to discuss the computation. By Lemma F.1, we set = A[1 n, 1 m), 8y
[9[1 n, m]. Then,
((M 69) m),87) ((M 67, 8y)..
= (( o [1)[1 n, 1. m),7)F = ((M o 87, 7)
Thus, we can apply (65). (66) to compute a, b in this setting by plugging in y = A[1 3[1:00 [:11:11. m and 87 89(1 n, m.m.
36

---

Published as a conference paper at ICLR 2025
K CONVERGENCE
As in (Chapel et al., 2020), we will use the results from (Lacoste-Julien,, 2016) on the convergence of the Frank-Wolfe algorithm for non-convex objective functions.
Consider the minimization problems
min L (7) (p.q))
and
min L (f)
(69)
fel((..))
that corresponds to the discrete partial GW problem and the discrcte GW-variant problem (used in version 2), respectively.
Consider the objective functions 7 + (7) M 782 and + (F) M1 9/8, where M = M 2λ 1 n,m for a fixed matrix M E IRuxm with A > 0, and M is given by (54). Although M and M are symmetric for À >> 0, they are not positive semi-definite, these objective functions are generally non-convex.
However, the constraint sets (p( q) and r(p, i) are convex and compact in Raxm (see Proposition B.2 in (Liu et al., 2023)) and in (==+))x(==)) respectively.
From now on, we will concentrate on the first minimization problem in (69), and the con- vergence analysis for the second one will be analogous.
Consider the Frank- Wolfe gap of L at the approximation ((h) of the optimal plan y
g& = min (V 7,)) 7) <Ep's)).))
(70)
It provided good criterion to measure the distance to a stationary point at iteration k. Indeed, a plan ((8) is stationary transportation plan for the corresponding constrained optimization problem in (69) if and only if gb. 0. Morcover, 9k is always non-negative (gk 2 0).
From Theorem in (Tacoste-Julien, 2016), after K iterations, we have the following upper bound for the minimal Frank-Wolf gap:
max (2L, max Lip (Ciam(T<(ppq)))
9K
min 9k 1skSK
(71)
VK
where
: ()
min
(x)(7)
yET
is the initial global sub-optimal bound for the initialization (1) of the algorithm; Lip is the Lipschitz constant of function 7 + VLgi and
diam (T
17--11 TT
sup
the || || diameter of (p, in Raxm
The important thing to notice is that the constant max(2L, Dr} does not depend on the iteration step k. Thus, according Theorem in (Lacoste-Julien, 2016), the rate in ğK is (L) That is, the algorithm takes at most (11=²2) iterations to find an approximate stationary point with gap smaller than e.
Lemma K.1. In the discrete PGW problem, have
diam(I=(p)) q)) 2s min(pp). lg)
(72)
Proof. Choose 7,76 (p<(p.)) we apply the property
(a-b)² b)2 < 2a² 28 Va, IR
(73)
37

---

Published as a conference paper at ICLR 2025
and obtain
[i -
f
n,m
2/, 12 +21%/ss
2
Σ
nos) +
1 12
2(h1 + 1//1²)
(74)
s 2 min (lp). lal)² 2 min((p), la))
4 min min((pp (ppl.
and thus, we complete the proof.
Lemma K.2. For the Lip lerm in (71) can be bounded us following:
Lip S um max (2(C +2,
(75)
1333
Proof. Pick y, E [p, 9) we have,
(V (
=IIM o- .M 7/?1?
= II[M - -21 o (r (7-1')11
= Σ (I(M- - -21) -7--1)))
2
Σ
Σ
(Misss - (1.5)))
1
V
2
Mijaa's 22 -
2
2 m,m
1,
max [Migees -2A} tg o
Σ
ha - ke.
2.
For the first term, we have:
A < max + 2212
where
max (2 + 22 21] = max max 2(C + +(C)) 2,22
For the second term, we have:
2
her y Norrcl
mmm
1.j
n1.
11
38

---

Published as a conference paper at ICLR 2025
Thus obtain
max(2(C**) + +((C)) 22)mm/mmlll ~Ylle mm max + +2(
Lip &
| >-11=
and we complete the proof.
Combined the above two lemmas, we derive the convergence rate of the Frank-Woo gap (70):
Proposition K.3. When L2r1, -22 in the PGW problem, the Prank- Wolfe gap of algorithm I, defined in (70) at iteration k satisfies the following:
r2
2h,, 4 min((p), lq)2 (2(x)
max
S
(76)
Proof. The proof directly follows from the upper bounds (72),(75) and the incquality (71).
Remark K.4. Note, if the cost function PGW defined by Iri- r2l for some p + 2, it is straightforward to verify that the upper bound of gie is obtained by replacing the term max((C* + (Cx),, 22, should be replaced by
2 12 "(C''(+X+"+"" (CK)), 2),
E.J.
Remark K.5. It is struightforward to verify that the Frank- Wolf gop for algorithm 2 is also upper bounded by (76).
Remark K.6. From the proposition (K.3), achieve an c-accurate solution, the required number of iterations is
max 2L, 2 min( (. |ql) n² n2m max m2x(2(C2) )
2
In practice, by lemma E.2, when X is large, it is equivalent to set X = max((C and thus,, the value X will not affect the number of iterations.
Remark K.7. In this remark, compare the upper (40) and the upper bounds in previous works, including (Chapel et al., 2020) and 2usp202sssereseed We observe that:
If we ignore the term X (or equivalently, set À max (2(Cx)2 + 2(C))))), the upper bound (76) aligns with the upper bound for the Frank- Wolfe Gap in fass-comstraint PGW (see Chapel et al. (2020, Eq. (10))) and balanced GW (see Cong et al. (2024, p. 18).
However, there exist several differences in details between our result and the result in (Chapel el. al., 2020).
First, in (Chapel et al., 2020), the term nm omitted. We suspect this omission is lypo, as the nm term is contained in (Cang et al., 2024).
In (Chapel et al,, 2020), "s" plays the role of min([p], Iq]) in our result. The assumption in Chapel et al. (2020, Lemma 1) is
In| m-= -==11=1
If we normalize such that max(1p), (ql) < 1, we will obtain
minn(pp) 2 min(Ipl, /q]),
and our result will induce the upper bound in Chapel et al. (2020, Lemma 1).
39

---

Published as a conference paper at ICLR 2025
L RELATED WORK: MASS-CONSTRAINED PARTIAL GROMOV-WASERSTEN!
Partial Gromov-Wasserster is first introduced in (Chapel et al., 2020). To distinguish the PGW problem in (Chapel et al., 2020) and the PGW problem in this paper, we call the former one the Mass- Constrained Gromov Coomov-aassersteii problem (MPGW):
MPGW, (X, ==
inf ner per- (K.))
7 (L('x,
(77)
where p [0, min (1ul, [=]]], and
Te (p,1) == E : 22 12 In| p}.
(78)
Unlike the relationship between Partial OT and OT, it is not rigorous to claim that PGW and MPGW are equivalent. The objective function
Jawry I(dx (2), dz dy
(79)
non-convex, even the map (21,72) + L(,, itself is convex (Peyré et al., 2019). the problem were convex, then MPGW. viewed the 'Lagrangian formulation' of PGW (adding the partial constraint into the functional via Lagrange multipliers), would coincide with PGW. However, since these problems are not convex, we cannot assert their equivalence in principle.
We can still investigate their relationship by the following lemma, based on which we design the wall-clock time experiment in Section Q.
Proposition L.1. For each 2 O, there erists E [0, min([al, such that, for each Y E (g, with Iy| p, y is optimal in PGW, (X, Y) iff is optimal in M PGW (XX, Y). Purthermore,
PGWA(H, v) = MPGW,(0. + AQIm + ju|2 -2p²).
Proof. Pick o' (Tg( CTs(u,)) v). since y is optimal in PGWx(U, v), we have 0 s C(y; A, u.v) - -((')A.,,
= =/ [( x²), dr (v. (v.7))) -
Thus, is optimal in 1 (M,v) for MP Y) and we complete the proof.
Remark L.2. The above proposition clarifies a connection between PGW and MPGW. Specifically, it implies that optimal transportation. plan for PGW can be derived from MPGW by appropriately setting However, it is important to note that MPGW and PGW admit distinct transportation costs. MPGW does not define a metric, whereas PGW W does. Therefore, in experiments that require transportation costs, such as the shape retrieval experiment described in the main text, the results produced by the two methods will differ significantly.
Example L.3. Consider the following three mm-spaces
1000
800
400
X,
R3
1R.11.1.2 1=11
adz.. X,
R23
11,
_ adz,
X3 IR33 11,1111111 11,
ad
where O is the mass of each point. For numerical stability reasons, set 1/1000. On the one hand, is we compute MPGW, the mass is fixed to be a value E [0, 0.4), since the lotal mass in Xg is 0.4. For our eaperimenl,
p = 0.4, and we observe:
MPGW,
0.4) MPGW, (X2, Kzs; 0.4) MPGW (XG, 0.4) =
40

---

Published as a conference paper at ICLR 2025
On the other hand, if we compute our PGW, considering any À > 0 fin particular, set 10), we obtain
P X2; 10) 3.6
PGW (X2, X3; = 10) = 4.8
PGW (XL, X3: 10) 8.4
In particular, one con verify the triangular inequality-
As a conclusion, in this example, MPGW can not describe the dissimilarity of any two datasets taken from {%,, K2, K3). They are three distinct datasets, but MPGW returns for each pair. On the contrary, our PG W can mensure dissimilarily.
In addition, the discrepancy provided by our PGW sormalation is consistent with the fol- lowing intuitive observation: One expects the dissimilarily between X1 and X3 to be larger than the difference X1 and X2 and than the difference between X1 and X2. This is because we are considering discrete measures, with the same mass at each point concentrated on the sets (.1...., (Z1....,T400) datasets X3, X2, X1, respectively.
{æ1..... ;,00:...,
T800. (1000..,TT000-....
F1000) for the
Remark L.4. Moreover, there may, in fact, exist instances of the two problems for which the solution sets are not equal for any value of the hyperparameters X and pi we illustrate this in the following ezample:
Consider the mm- nan-spaces given by
X1
Rd:
Σ Sz,
and X2
Rda ||
11.
5uy
If we let À = 0, then PGWo(X,, K2) has )( solution for all (i,j), well the zero measure.
Now, we observe that for p 0, ((rry))) is not solution of MPGW (iWWW((x,, X2);; meanwhile, for any p O, the zero measure is not solution of MPGW,((1,, X2).
Hence, we see that the set of solutions between PGWo(X1, X2) and MPGW, (P (2)) are distinct for all p.
Remark L.5. The other direction of the "equivalence relation" between PGW and MPGW given by Proposilion L.1 may not hold. In porticular, there erisls a problem M PGW PP %2) for some p > 0,, such that for all X > O, each solution to M MPGW, (X1. %2) is not solution to PGWW(% Xx2), and each solution PGWx T22) not a solution M MPW 1,; x2)-
As an example, consider X, = (Red, 11- 11..111100 100 8x.) and X
(Rd I1 11. Σ
Ei=1
200
where
Fi, .... I200 distinct. Then for each p E (0, 100), any solution to MPGW (TPGW(X)) (x1, is not solution for PGWx (X1,%)) X2) and vice versa.
M PARTIAL
WAANNO--SSSRSSTEIN BARYCENTER
We first introduce the classical Gromov- Wasserstein problem (Peyré et al., 2016); Consider finite discrete probability measures μ ..... ...,,,. k where 1² Mm df and each af e gd for some dg E N. Let C = [|| - x 11 [[] and pt [pi...., I Given p E RT with [p| for some n N and ..,... problem is defined by:
.......e Ex 0 with ΣK Es 1, the GW barycenter
K EA (I
min
(80)
where the minimization is over all matrices C RRax A T(p.p'), Ak E :]
41

---

Published as a conference paper at ICLR 2025
Similarly, extend the above definition into the PGW setting. In particular, relax the assumptions |p] = 1 and Ip"1 = for each E [1 : K]. Given A1...., Ak > 0, the PGW barycenter is the follow problem:
min C
Σ C*M o , 21xl7*'
(81)
where each 7 E <p)
The problem (81) can be solved iterative by two steps: Minimization with respect to C: For each k we solve the PGW problem
min T((p((pp
(M(C,C*) o 21
via solver or 2.
Minimization with respect to ha:
min (M(C o ,
(82)
Note, we can ignore the - terms 7 is fixed in this case. It has closed form solution due to the following lemma and proposition: Lemma M.1. Given matrices A R. Rmm. ,C R let
L = (AB,C),
then dc = CBT AA
Proof. For any e [1 n].j E [1 m], we have
dC
Σ d
(AB)
dAij
2.8 dAg
d(Ex Av Ax,)
Σ Cv.
dAi
Σ Ciy C (CB
Proposition M.2. If L. satisfies (57), and fi/h', is invertible, then (82) can be solved by
E (C(h))
C=
(83)
Ex
where
A
Aij
0
with convention 0
0.
B
Bij ij
Special case: if [p| < 1p*), vk, when x is sufficiently large, (83) and Peyré et al. (2016,
Proposition 3) coincide.
Proof. From Proposition H.1, the objective in (82) becomes
L Σ EL L - (1(0)))
Σ CC Σ ( 7/ [
constaut
42

---

Published as a conference paper at ICLR 2025
We set dc dc
0. From Lemma M.1, we have:
0 dC
dc
h
= f(()) Φ Σ S (,1))))(()))))))))))))))) - -1/(C) @ Σ (nnhaa(C
= f((C) o Σ Entlltt -M(() o Σ (2))
(84)
We claim A well-defined, i.c., if Bij = O, then Aij = 0. B
For each i,j [1: [1: if Biy
have two cases:
Case 1: VA E [1 K], have [ O. Thus, [1, = TT So A[i, = (7 h2* (+)))) O
Case 2: vk E [1 K]. we have T} =0.
It implics (7 [:, On, thus A(:,5] (x+b2(C"))()))11> Oney Therefore, Ar 0. Thus A is well-defined.
In addition, in these two cases, if we change the value Cj., L will not change.
From (84), have:
fi M
(C)
ij
if By > 0. In addition, if Big = 0, there is no constraint for Cij.
Combining it with the fact that if Brg = o, then Ci, does not affect L. Thus, we have the following is a solution:
J h1
-1 Ex (EnSenth
C=
Extnn(T)))
In particular case: |p| S 1p*1, Vk, suppose X max(c² : E UR C+ UCJ, by lemma E.I, we have for each k, | min([p). (p|*) [pl, that is 7f =
Thus,
Ean(()) Eantht Σ Edpp
pp
Thus, C= (1 -1 (E
Remark M.3. In 12 loss case, iec L(ri,T2) = =|m - r21?, (83) becomes
C
C Ex (xnttt
(85)
Since in this case, we can set
fx(x) =² =
hu (x) = 2x. N2(y)) y-
Thus (x) = 2x x and
-1 (x) = r. Therefore, (83) becomes (85).
43

---

Published as a conference paper at ICLR 2025
Algorithm 3: Partial Gromov-Wassostcin Barycenter
Input: (Ck, p*, A
Output: C
Initialize C.
for i 1,2,... do
compute 7 +- arg g (F(C, 2),, [1 K]. Update C by (83).
if convergence, break
end for
Algorithm 4: Mass-Constrans Constrained Partial MaanovvWasssrstein Barycenter
Input: {Ck, .p. As A
Output: C
Initialize C.
for i 1,2,... do compute 7 + arg aug (,))) e K]. Update by (83).
if convergence, break end for
Similarly, we can also extend the above PGW Barycenter into the MPGW setting:
K
min C.a
Eu (L)
where, for each E []: Ps [0,min((pl: I)],,, and the optimization is over C e R" and The 1 (p.p*) for l [1: K].
It can be solved by the following algorithm 4.
M.1 DETAILS OF SHAPE INTERPOLATION EXPERIMENT
Dataset and data processing. We apply the dataset in (Peyré al., 2016) with download link. The original data are images, which convert into point cloud using the k-mean algorithm, where
1024 (see the second row of Figure 4).
Suppose D C I is region that contains these point clouds. Let. R C IR2 denote another region. In R, we we randomly select and add nn noise points to these point clouds. particular, consider noise corruption in the following three cases:
Case is a rectangle region which disjoint to D. See the third row in Figure
Case 2: R = R1 U R2, where R1, R2 are rectangles which are disjoint to D. See the fourth row in Figure 4.
Case 3: R contains D. See the fifth row in Figure 4.
GW Barycenter and PGW Barycenter methods. We select ti,..., tk with = f <
t2 ..... <tx = 1. For each t E (h...... tk), compute the GW Barycenter
arg min (1 (i-)tt(LCCCC C2 on +3 C. x
(86)
where 71 E P'p. E P2).p²). Apply Smacof-MDS to the minimizer C, the resulting embedding, denoted X, Rax2 (where 1024) the GW-based interpolation.
Replacing the GW Barycenter with the PGW Barycenter
arg min (1 ()(((((C,C on) 2h (((T(C, o +2/7?2), (87)
Cat
44

---

Published as a conference paper at ICLR 2025
Image
kmoo
RDST
Figure 4: We visualize the dataset in shape interpolation. The first row is the original images in Link. The second row the point clouds obtained by the k-mean method, where k = 1024.
where dι, A2 0,7 E (''(p."),, (s(p,p²). Then, obtain PGW-based interpola- tion.
Problem setup. We select one point cloud from the clean dataset denoted as X = {2;; 1 (source point cloud), n 1024.
Next, select noise-corrupted point cloud, described in Case 1, Case 2, and Case 3, respectively. In these three scenarios, we test y= = 0.5% and y= 10% where 7j is the noise level. Therefore, lest. * 2 = 6 different interpolation tasks for these two methods. The size of the target point cloud is then m = n + nn,. See Figure for details.
Numerical details. In the GW-barycenter method, because of the balanced mass setting, we set
p² In, .²
1m, P.
1 n
n
77
In PGW-barycenter, we set.
mm 1n In addition, we set d2 such that 2\1, 2h2 2 max(max(C:)3, max(()))) We compute GW/PGW barycenter for t
p
In,
p²
72
72
n
In both GW and PGW barycenter algorithms, we set the largest mumber of itcrations to 100. The threshold for convergence is set to be le-5.
Performance analysis. Each interpolation task is essentially unbalanced: the source point cloud contains clean data, while the target point cloud contains clean and noise points. We observe that in the first two scenarios, the interpolation derived from GW is clearly disturbed by the noise data points. For example, rows 1, 5, 7, columns = 1/7, 2/7, 3/7,, we see that the point clouds roconstructed by MDS have significantly different width-height ratios from those of the source and target point clouds.
In contrast, PGW is significantly less disturbed, and the interpolation is more natural. The widtth-eiggh ratio of the point clouds generated by the PGW barycenter is consistent with that of the marce/target point clouds.
45

---

Published as a conference paper at ICLR 2025
ONL 5
PGW
GW 10%
PGW 10%
GM 5%
PGW. 5%
CMM 10%
PGW
GIN 5%
POW, 5%
GIN
PCW 10%
077
577
Figure 5: We test interpolation tasks in 3 scenarios: source data is clean, target data is selected from three cases as described section dataset and data processing. scenario, we lest. 7) 5%, 10% respectively. In the first column, we present the source and target point cloud visualization in each task. In columns 2-9, we present GW, PGW barycenter for t 0/7, 1/7, 7/7.
each
46

---

Published as a conference paper at ICLR 2025
In the third scenario, the noise data is uniformly selected from large region that contains the domain of all clean point clouds. In this case, we observe that the GW and PGW barycenters perform similarly. However, at == 2/7,, GW-barycenters present more noise points than PGW-barycenters in the same truncated region.
Limitations and future work. The main issue of the above CW/PGW techniques arises from the MDS method:
Given minimizer C R= of GW/PGW barycenter problem (86) (or (87)), MDS studies the following problem:
Xx 2
min X
C |X,
(88)
1P==1
Let O(n) denote the of all n X orthonormal matrices. Suppose X is minimizer, then RX* is also a minimizer for the above problem for all R E O(n).
In practice, this means manually setting suitable rotation and flipping matrices for each method at each step, especially for the GW method.
However, we understand that this issue stems from the inherent properties of the GW GW/PGW method. GW can be seen as tool that describes the similarity between two graphs, which are rotation-invariant and flipping-nvvariat. Therefore, the GW/PGW barycenter essentially describes the interpolation between two graphs rather than two point clouds.
M.2 MULTI-SHAPE INTERPOLATION
In this section, we present the interpolation between 4 different shapes. In addition, let be the percentage of outliers; we test 7) = and 5%.
Experiment sctup. We select 4 shapes (bird, cat, human, and rooster) from the 2D clouds dataset. Two them, i.e,, cat and rooster, are embedded into 4D space and are randomly rotated. The goal is to find the interpolation between them.
Baselines. We select baselines, optimal transport barycenter (Cuturi Doucet, 2014), partial optimal transport barycenter (Bonneel & Cocurjolly, 2019), GW barycenter (Peyré et al., 2016) and our PGW barycenter.
Note that OT and partial OT barycenter can not be directly applied to this setting. We first embed the 2D shapes into 4D space via mapping
2 a + [x; 0; 0]:0 E R.
and then compute the OT/POT barycenter. Finally, we apply PCA to project the result back to 2D space for visualization.
Result analysis. We present the results in Figures 6 and 7. When r = 0, from Figure 6, observe that OT/POT admits good interpolation results between 2D shapes (bird and human). However, the OT interpolation between 2D and 4D is not as good as GW/PGW The main reason is that the OT /POT barycenter incorporates the absolute coordinates of these shapes for interpolation, which is affected by random rotation. However, GW /PGW is not affected by the absolute coordinates of the shapes.
In the second figure, we demonstrate the result for = 5%. Two shapes are corrupted by the noise points (cat and rooster). We obscrve that GW's interpolation is affected by the outlicrs (scc, c.g.,a from bird to human or from cat to rooster), while PGW is less affected by these outlier points and admits much better /smoother interpolation.
N DETAILS OF SHAPE MATCHING
Dataset setup. In the Moon dataset (see link), we apply n = 200 and set Gaussian variance to be 0.2. The outliers are sampled from region [[-2, -1.5] x [-3.5, -3]]-
47

---

Published as a conference paper at ICLR 2025
(a) OT barycenter
(b) Partial OT barycenter
(c) GW barycenter
(d) Partial GW barycenter
Figure 6: We visualize multi-shapes interpolation, where the proposition of noise v 0. "bird" and "human" shapes are distributed in 2D space, "cat" and "rooster" are distributed in 4D space.
In the second experiment, the circle data is uniformly sampled from a 2D circle
s {s R² || = 1}
and spherical data uniformly sampled from 3D sphere
2² = (s [0, 0, 4 E R2 || = 1};
where the shift [0,0,4] is applied for visualization.
We set sample size 200 for both 2D and 3D samples.
In both experiments, the number of outliers ryn 0.2n 40. Numerical details. In GW, we normalize the two-point clouds as
at ) Y (Y,
X (X,
n
ru
1=1
In PGW, MPGW, and UGW, we define the point clouds as
n X (X,
x+nn
Σ
)w:),
dr,
Σ
85g
n
n
48

---

Published as a conference paper at ICLR 2025
(a) OT barycenter
(b) Partial OT barycenter
(c) GW barycenter
(d) Partial GW barycenter
Figure We visulize of multi-shapes interporlation. "bird", hhmann" shapes are distributed in 2D space, "cat", "rooster" are distributed in 4D space. The noise level, n, is 5%.
In PGW, we choose À such that À 2 max(max(((*)) max(( in particular, = 10.0. In addition, we tested 0.01, 0.1, 1.0, 10.0.
In MPGW, we tested 0.3, 0.5, 0.8, 1.0 and selected 1.0
In UGW, tested [le 10, 1e 1, 1.0, 10) and selected #1 = p2 1.0, e 0.05.
We refer to Figure for the visualization of all tested parameters.
49

---

Published as a conference paper at ICLR 2025
3.23
Manct
32
(a) 2D and 2D matching
massub33
0-0.01
pgh. h-0.)
Uge,
maga, mass.
UgA, P-
FBA 1-10
MEDA masso1.0
USW 0010.
PRA A010.0
(b) 2D and 3D matching
Figure 8: We visualize the shape-matching result for all tested parameters.
50

---

Published as a conference paper at ICLR 2025
O
DETAILS OF SHAPE RETRIEVAL EXPERIMENT
bone
goblet
dar
Porzeshoe
rectargle
Bick
aniakk
T0.48
05:00 BFT04
dRde
(a) Dataset I
(b) Dataset
Figure 9: Visualization of representative shape from each class of the two datasets.
Dataset details. We test datasets in this experiment, which we refer to as Datasct I and Dataset II. We visualize Dataset in Figure 9a and Datasel II in Figure 9b. The complete datasets can be accessed from the supplementary materials.
Numerical details. We represent the shapes in each dataset mm-spaces X (R2. =l anced mass constraint setting. For the remaining distances, we set a = I where N is the median number of points across all shapes in the dataset. For the SVM experiments, use exp(-oD) as the kernel for the SVM model. Here, we normalize the matrix D and choose the best to facilitate a fair comparison of the resulting performances. We note that the resulting kernel matrix not necessarily positive semidcfinitc.
We use a' = 1 to compute the GW distances for the bal- n²
N.
{0.001, 0.01, 0.1, 1, 10, 100, 1000, 10000) for each method used order
In computing the pairwise distances, for the PGW method, set À such that À S Amar max; (IC* (2). In particular, we compute Amaz for each dataset and use X = 5 Ammaz for each experiment. For UGW, we use = 10-1 and P1 = P2 = for both experiments. Finally, for MPGW, we set the mass-constrained term to be min(læ*), (12)) when computing the similarity between shape X' and XT.
Performance analysis. The pairwise distance matrices visualized for each dataset in Figure 10, and the confusion matrices computed with each dataset are given in Figure 11. Finally, the classification accuracy with the SVM experiments is reported in Table la. The results indicate that the PGW distance is able to obtain high performance across both datasets consistently.
In addition, from Figure 10, we observe that PGW qualitatively admits a more reasonable similarity measure compared to other methods. For example, in Dataset I, class "bone" and "rectangle" should have relatively smaller distances than "bone" and "annulus". Ideally, reasonable distance should satisfy the following:
d(bone, rectangle) d(bone, anulus).
However, we do not observe this relation in GW and UGW4, and for the MPGW method, MPGW (bone, rectangle) As O, which is also undesirable. For PGW, however, we do observe this relation. Additionally, we report the wall-clock time comparison in Table 1b.
O.1 ADDITIONAL EXPERIMENT WITH OT UUT BASELINES
In this subsection, we incorporate optimal transport distance (Villani, 2003) and unbalanced optimal transport distance (Chizat et al., 2018c) into the shape retrieval experiment.
For UGW, this is due the Sinkhorn regularization term.
51

---

Published as a conference paper at ICLR 2025
MPCW
UGW
PGW (ours)
bone
iccarggc
torseshow
anulaa
bine
reszangle
gateer
trapeand
stre
horesstiee
dos
accesstion
boree
rectangaa
trapcood
Mat
horertose
hore
mezmoople
polsrt
adde
hometioee
ammiti
trapeandd
ster
homestise
dok
acmiti
(a)
Dataset
GW
MPGW
UGW
PGW (ours)
rertange
deable srow
restarggh
double snow
Mumiconc
ciecle
Hertanghe
aroo
dedble anower
cleck
rectangle
diuble arow
enoor
clicke
(b) Dataset IT
Figure 10: Pairwise distance matrices computed for each dataset.
MPGW
UGW
(ours)
bone
mectangle
torsedoow
antulu
boner
exchingle
gntbet
trasccne
star
dise
hestertooy
Lotte
intanggle
polfer
trawcnd
dlstt
emortad
techengoo
goller
trspacedd
stter
Ievendeen
di
acrosiee
Brote
gribet
trisscne
star dist
toe sectio acmsaaa
(a)
Dataset
GW
MPGW
UGW
PGW (eurs)
mectongle
House
double arro
armw
carple
mestongle
husse
dusbis arrize
demiciicte
conce
recsongle
hause
arrrer
doshii Arrowe
bemitt cide
dirde
messagle
Rozoee
arre
dosbll airoze
Aeriictice
circle
(b) Dataset
Figure 11: Confusion matrices computed from nearest neighbor classification experiments.
Dataset setup. We perform shape retrieval experiments in two scenarios: the original 2D dataset and a 4D dataset. For the 4D scenario, we embed the shapes into 4D space and then apply random rotation to each shape.
Basclines. We evaluate the performance of the following methods: Optimal Transport distance (OT) (Villani, 2003), Unbalanced Optimal Transport (UOT) distance (Chizat et al., 2018c), Gromov- Wasserstein distance (GW) (Gromov, 2001), Mass-constrained Gromov- Wasserstein discrepancy (MPGW) (Chapel et al., 2020), Unbalanced Gromov- Gromov-Wasserstein Wasserstein
52

---

Published as a conference paper at ICLR 2025
Method
Dataset
Dataset TT
OT (d= 2)
95.6%
55.8%
OT (d 4)
79.3%
50.8%
UOT (d =
73.5%
73.3%
UOT (d
56.9%
63.3%
GW (d -
98.1%
80.8%
MPGW (d 4)
23.7%
25.0%
UGW (d -d=22 2,4)
89.4%
90.0%
PGW (ours, d 2,4)
96.2%
100%
Table 2: Performance comparison across different methods and datasets.
discrepancy (UGW) (Séjourné et al., 2021), and our Partial Wannov-Wasserstein (PGW) distance.
The parameter settings for GW, MPGW, UGW, and PGW are described in the previous section. For the UOT method, we set the weight of Sinkhorn regularization to 0.1 and the weight of the marginal penalty to 0.2.
Result. In Dataset when data is in the 2D space, OT achieves an accuracy of 95.6%, while UOT achieves 73.5%. OT's accuracy is slightly lower than GW EW/PGW, but it remains strong classifier this sctting. In Datasct UOT outperforms OT with an accuracy of 73.3% compared to 55.8%.
When the shapes are embedded into 4D space, the accuracy of OT and UOT drops signif- icantly, ranging from 56.9% to 79.3%. far below the performance of GW and PGW. This decline highlights the reliance of OT/UOT on absolute coordinates, which becomes more problematic in higher dimensions. In contrast, GW-based methods (GW, MPGW, UGW, PGW) remain unaffected, as they are invariant to absolute locations. Overall, regardless of whether the data is in 2D or 4D space, OT and UOT consistently perform worse than GW and its variants. The gap in performance becomes even more pronounced in 4D space.
P OTHER NUMERICAL IMPLEMENTATIONS
P.1 INITIAL METHODS
In this experiment, we discuss several different. methods to define the initial guess in the Frank- Wolfe algorithm proposed in this paper. Note some of these methods have been applied in FW algorithms/ /erssiinnknn solvers in classical GW (Mémoli, 2011), Mass-constraint GW (Chapel et al., 2020) and Unbalanced GW (Séjourné et al., 2021)
Given two min-paaces X (X, 1)), X (Y,dy, v), we consider the two cases:
Case 1: Dimensions of X and Y are the same. Note, in this case, we can define classical OT/partial OT/unbalanced OT between l and u. Thus, (Chapel el al., 2020) proposed the following "POT initilization" method:
(1) c arg min (L(X,Y),))
(89)
(p.9)
where L(X,Y) Raxm (L(X, Y) = || w for some fixed p 2 1 and
T (p. = (r E R m (7 1, E (a) 0), ri S. hr = m).
(90)
The above problem can be solved by Lasso (L' norm) regularized OT solver.
Case 2: Dimensions of X and are different. The above technique can not be applied since the problem (89) (in particular L(X,Y) is not well-defined.
53

---

Published as a conference paper at ICLR 2025
In this case, (Séjourné et al., 2021) introduced the "FLB-UOT" method:
7(0) + arg min / (xx,(())=
(El'((p.) XXY
(91)
where sx,p(x) fx |x x (dd((x) and Sy.p is defined similarly. The problem (91) is called Hellinger Kanlorovich, which is a classical unbalanced optimal transport problem. The Sinkhorn solver can solve it (Chizat et al., 2018b).
Analog to the above method, we propose the third method, called "FLB-POT" (first lower bound-partial optimal transport)
/ (xx,p(1) - 70) arg min (E-g(p-)) XXY
+ A(IP 71 +14 - 721)-
(92)
The above problem is partial OT problem and can be solved by classical linear program- ming (Caffarelli & McCann, 2010).
P.2 PARAMETER SETTING FOR PGW
Setting parameter À in PGW important in the numerical implementation. There two scenarios to consider:
Both source and larget measures contain outliers:
The parameter À acts as an upper bound for the transported distance. Specifically, if
|xx (2, x²) (v.
2X,
then either y) or (z',y") will not be transported. When the distance between outliers and clean data is large, and the pairwise distances within the clean data are relatively small, should be set to lic between these two scales.
Only one measure contains outliers:
As stated in Lemma F.2, À can be set sufficiently large to satisfy:
2A Z
x z,r' (x, dy dy
max
In the interpolation and shape retrieval experiments, we fall under the second sce- nario, which does not require significant parameter tuning.
54

---

Published as a conference paper at ICLR 2025
Q WALL-CLOCK TIME COMPARISON FOR PARTIAL GW SOLVERS
In this section, we present the wall-clock time comparison between our method Algorithms 1, 2, the Frank-Wolf algorithm proposed in (Chapel et al., 2020), and its Sinkhorn version (Peyré et al., 2016; Chapel ct al., 2020). Note that these two basclines solve a mass constraint version of the PGW problem, which we refer to as the "MPGW" problem. The proposed PGW formulation in this paper can be regarded as a "Lagrangian formulation" of MPGW formulation to the PGW problem defined in (10). In this paper, we call these two baselines the "MPGW algorithm" and the "Sinkhorn PGW algorithm".
Numerical details. The data generated as follows: let μ Cnif([O, 2/²) and v [n ) we select i.i.d. samples {r; ~ | {Uj ~ 1) where is selected from 10000) and m A 0.2, 1.0, 10.0. The mass constraint parameter for the algorithm (Chapel et al., 2020), and Sinkhorn is computed by the mass of the transportation plan obtained by Algorithm or The runtime results are shown Figure 12.
[10, 50, 100,
+ 100, p 1, l,/m,q = 1m/m. For each n, we set
Regarding the acceleration technique, for the POT problem in step 1, algorithms and the MPGW algorithm apply the linear programming solver provided by Python OT package (Flamary et al., 2021), which is written in C++. The Sinkhorn algorithu from Python OT does not have an acceleration technique. Thus, we only test its wall-clock time for n S 2000. The data type is 64-bit float number.
From Figure 12, we can observe the Algorithms 1, 2, and MPGW algorithm have a simi- lar order of time complexity. However, using the POT computation discussed in previous sections and the fact the convergence behaviors of Algorithms 1 and 2 are similar to the MPGW algorithm, we observe that the proposed algorithms 1, 2 admits a slightly faster speed than MPGW solver.
technique for the
wall-clock time
10
=
10y
=1,A=1000
=
10-1
v2,A=
m,
mA=10.0
5,A
5,A 10.0
0
2000
4000
6000
5000
10000
n: size of p
Figure 12: We test the wall-clock time of our Algorithm and Algorithm 2, the MPGW solver (Algorithm in (Chapel et al,, 2020)) and the Sinkhorn algorithm (Peyré et al., 2016). We denote these methods as "v1", "v2", "m" and "s", respectively. The linear pro- gramming solver applied in the first three methods is from POT (Flamary et al., 2021), which is written C++. The maximum number iterations for all the methods is set to be 1000. The maximum iteration for OT/OPT solvers set be 300n. The maximum Sinkhorn iteration is set to be 1000. The convergence tolerance for the Frank-Wole algo- rithm and the Sinkhorn algorithm are set be le 5. To achieve the best performance, we set the number of dummy points to 1 for both MPGW and PGW.
Duee to the non-convexity of GW, we do not have a strong duality in some of the GW repre- sentations. Thus, the Tagrangian form is not rigorous description.
55

---

Published as a conference paper at ICLR 2025
R POSITIVE UNLABELED PROBLEM
R.T PROBLEM SETUP
Positive unlabeled (PU) learning (Bekker & Davis, 2020; Elkan & Noto, 2008; Kato et al., 2018) is a semi-supervised binary classification problem for which the training set only contains positive samples. In particular, suppose there exists fixed unknown overall dis- tribution over triples (x, o. I), where x is data, E 1) is the label of x; o E (0, 1} where 1, 0 denote that is observed tion is that only positive samples' labels can be observed, i.e., Prob(o = 1/,, / 0) = 0. Consider training labeled data X {(r D) C {a : = 1} and lesting data X {x) km 1 1==1 C f : o= = 0}, where x.p," E Rd, ,T) Rd4. In the classical PU learning setting, d2 d1- However, in (Séjourné et al., 2021), this assumption is relaxed. The goal to leverage X2 to design a classifier i: x - {0, 1} to predict 1(x") for all xx E X
not, respectivcly. In the PU task, the assump-
Following (Elkan & Noto, 2008; Chapel et al., 2020; Séjourné et al., 2021), in this experiment, we assume that the "select completely at random" (SCAR) assumption holds: Prob(o use Prob(l 1) E [0, to denote the
1 1) Prob(o = 1 = 1). In addition, ratio of positive samples in testing set?. Following the PU learning setting (Kato al., 2018; Hsieh et al., 2019; Chapel et al., 2020; Séjourné el al., 2021), we assume π is known. In all the PU learning experiments, we fix π = 0.2.
R.2 METHODOLOGY
Similar to (Chapel et al., 2020) our method is designed as follows: We set E R" R RD
RM
as p,a f, [1 : nli of - i [1 m). Let XP = (XP, Il Il Ex 1 dn, ),
(X", |l- ll.. ビド= of dg,). We solve the partial GW problem (XW, x") and suppose
a solution. Let 72 = r In. The classifier Í defined by the indicator function (xx" (a" (o where quantile is the quantile value of 72 according to 1 11-1
(93)
Regarding the initial guess 7(1), (Chapel et al., 2020) proposed a POT-based approach when X and Y are sampled from the same domain, i.e, dj = d2, which we refer to "POT initialization."
When X,Y are sampled from different spaces, that is, d1 # d2, the above technique (89) is not welledefined. Inspired by (Mémoli, 2011; Séjourné et al., 2021), we propose the following "first lower bound-partial OT" (FIB-POT) initialization:
(1)) = arg min / (sx,2(x) - sx.(2)) v) + A(IP - 71l + (2)))
(PT's XxY
where (x,((x) = |x- (x xdd(() and sy. is defined similarly. The above formula is analog to Eq. (7) in (Séjourné et al., 2021), which is designed for the unbalanced GW setting. To distinguish them, in this paper, we call Eq. (7) in (Séjouréé et al., 2021) as "FLB-UOT initialization".
R.3 DATASETS
The datascts include MNIST, EMNIST, and the following three domains of Caltoch Office: Amazon (A), Webcam (W), and DSLR (D) (Saenko et al., 2010). For each domain, we select. the SURF features (Saenko et al., 2010) and DECAF features (Donahue el al., 2014). For MNIST and EMNIST, we train auto-encoder, respectively, and the embedding space dimension is 4 and 6, respectively. See Figure 13 for the TSNE visualization of these datasets.
'In the classical setting, the goal is to learn classifier for all In this experiment, we follow the setting (Séjourné al,, 2021).
"In the classical setting, the prior distribution æ is the ratio of positive samples of the original dataset. For convenience, ignore the difference between this ratio in the original dataset and the test dataset.
56

---

Published as a conference paper at ICLR 2025
MNIST
(b) EMNIST
mo
pa
ba
mo
de
sp
(c) Sur((A)
(d) Decal(A)
mo
pa
de
le
Sur((D)
Decaf(D)
mo
ba
mo
de
sp
(g) Sur(WW)
(h) Decaf(w)
Figure 13: TSNE visulization for datasets EMIIST, Caltech Office.
57

---

Published as a conference paper at ICLR 2025
R.4 NUMERICAL DETAILS AND PERFORMANCE
Accuracy Comparison. In Table and Table 5, we present the accuracy results for the MPGW, UGW, and the proposed PGW methods when using three different initialization methods: POT, FLB-UOT, and FLB-POT.
Following (Chapel et al., 2020), in the MPGW and PGW methods, incorporate the prior knowiedge π into the definition of p and q. Thus, it is sufficient to set mass for MPGW and choose sufficiently large value for À in the PGW method. This configuration ensures that the mass matched in the target domain y is exactly equal to π. However, in the UGW method (Séjourné ct al., 2021), the sctting p In,, and m 1m
Overall, all methods show improved performance in MNIST and EMNIST datasets. One possible reason for this could be the better separability of the embeddings in MNIST and EMNIST, as illustrated in Figure 13. Additionally, since MPGW and PGW incorporate information from into their formulations, they exhibit slightly better accuracy in many experiments.
Numerical details. In this experiment, to prevent unexpected convergence to local minima in the Frank- Wolf algorithms,, we manually set during the line search step for both MPGW and PGW methods.
For the convergence criteria, set the tolerance term for Frank- Wolfe convergence and the main loop the UGW algorithm to be le 5. Additionally, the tolerance for Sinkhorn convergence in UGW was set to le 6. The maximum number of iterations for the POT solver in PGW and MPGW was set to 500n. In addition, for MPGW, we set mass = 0.2 and for PGW method, based lemma E.2, set À to be constant such that 2A 2 (max(IC*X]) 1)² max(1C*()3)
For UGW, as we directly apply the numerical method in (Séjourné et al., 2023), where the prior knowledge = 0.2 is not Incorporated in the setting of p and Thus, in each experiment, we test different parameters (p, P2, e) and select the ones that result in transported mass close to æ.
Regarding data types, we used 64-bit floating-poin numbers for MPGW and PGW and 32-bit floating- ppini numbers for UGW.
For the MNIST and EMNIST datasets, we set n 1000 and m = 5000. In the Surf(A) and Decaf(A) datasets, each class contained an average of 100 samples. To ensure the SCAR assumption, we set 1/2* 100 50 and m 250. Similarly, for the Surf(D) and Decaf(D) datasets, we set n 15 and m 75. Finally, for Surf(W) and Decaf(W), we used 20 and m = 100.
Wall-clock time Table 4, we provide a comparison of wall-clock times for the MNIST and EMNIST datasets.
DATASET
INIT METHOD
INIT ACCURACY
MPGW
UGW
PGW (OURS)
+
POT
100%
100%
95%
100%
M M
FLB-U
75%
96%
95%
96%
+
FLB-P
75%
99%
95%
99%
M FM
FLB-U
78%
94%
95%
94%
M + EM
FLB-P
78%
94%
95%
94%
EM M
FLB-U
75%
97%
96%
97%
EM + M
FLB-P
75%
97%
96%
97%
EM EM
POT
100%
100%
95%
100%
EM + EM
FLB-U
78%
94%
95%
94%
EM EM
FLB-P
78%
95%
95%
95%
Table 3: Accuracy comparison the MPGW, UGW, and the proposed PGW method on PU learning. Here, 'M' denotes MNIST, and 'EM denotes EMNIST.
58

---

Published as a conference paper at ICLR 2025
SOURCE
TARGET
INIT METHOD
INIT TIME
MPGW
UGW
PGW (OURS)
M(1000)
M(500))
POT
0.5
7.2
152.0
7.4
M(1000)
((5000)
FLB-U
0.02
30.5
152.6
27.8
M(1000)
M(5000)
FLB-P
0.5
27.8
144.9
26.9
EM(0000)
EM(5000)
POT
0.5
7.3
157.3
7.5
EM(1000)
EM(5000)
FLB-U
0.02
30.0
181.8
29.9
EM(1000)
EM(5000)
FLB-P
0.5
22.2
155.1
22.3
M(1000)
EM(5000)
FLB-U
0.02
34.0
157.9
34.4
1(00
EM(5000)
FLB-P
0.5
34.9
155.5
35.0
(1000)
M(5000)
FLB-U
0.02
24.3
139.3
22.2
EM (1000)
M(5000)
FLB-P
0.5
32.0
162.7
29.9
M (2000)
M(10000)
POT
1.7
31.1
1384.8
32.1
M ((2000)
M(10000)
FLB-U
0.1
209.0
1525.8
192.5
((200))
M(10000)
FLB-P
1.7
208.0
1418.4
192.1
M(2000)
EM EM00000)
FLB-U
0.1
165.1
1606.1
164.2
M(2000)
EM(10000
FLB-P
1.7
224.1
1420.7
223.7
EM (2000)
M(10000)
FLB-U
0.1
149.1
1426.5
138.1
EM (0000)
M(10000)
FLB-P
1.7
113.9
1407.6
103.9
EM (2000)
EM (10000)
POT
1.6
32.4
1445.9
33.4
EM (2000)
EM (10000)
FLB-U
0.1
233.0
1586.3
233.9
EM EM(0000)
EM(10000)
FLB-P
1.8
142.1
1620.6
142.1
Table 4: In this table, we present the wall-clock time for the MPGW, UGW, and the proposed PGW method, well three different initialization methods (POT, FLB-UOT, FLB-POT). In the "Source" (or "Target") column, M (or EM) denotes the MNIST (or EMNIST) datasct, and the value 1000 (or 5000) denotes the sample size of X (or Y). The units of all reported wall-clock times are seconds.
S COMPUTE RESOURCES
All experiments presented in this paper are conducted on computational machine with an
AMD EPYC 7713 64-Core Processor, 32GB DIMM DDR4, 3200 MHz, and an NVIDIA RTX A6000 GPU.
59

---

Published as a conference paper at ICLR 2025
DATASET
INIT МETHOО
INIT ACCURACY
MPGW
UGW
PGW (OURS)
SURF (A] 7 SURF(A)
POT
81.2%
74.7%
66.5%
74.7%
SURF A) SURF
FLB-U
64.9%
65.7%
66.5%
65.7%
SURF(A 7 SURF(A)
FLB-P
63.3%
66.5%
66.5%
66.5%
DECAF(A) 7 DECAF (A)
POT
95.1%
95.1%
60.8%
95.1%
(ECAF(A) 7 DECAF (A)
FLB-U
78.0%
67.4%
83.7%
67.4%
DECAF( + DECAF(A)
FLB-P
78.0%
74.7%
88.6%
74.7%
SURF 7 SURF (D)
POT
100%
100%
89.3%
100%
SURF(D) + SURF D
FLB-U
62.7%
73.3%
84.0%
73.3%
SURF(D) 7 SURF (D)
FLB-P
60.0%
60.0%
78.7%
60.0%
DECAF + DECAF(D)
POT
100%
100%
100%
100%
DECAF + DECAF(
FLB-U
76.0%
68.0%
70.7%
68.0%
DECAF D + DECAF(D)
FLB-P
73.3%
73.3%
86.7%
73.3%
SURF(W) W SURF(W)
SURF
POT
100.0%
100.0%
81.3%
100.0%
SURF W + SURF(W] W)
FLB-U
76.0%
70.7%
81.3%
70.7%
SURF W) SURF( W)
FLB-P
73.3%
68.0%
78.7%
68.0%
DECAF W) + DECAF W)
POT
100%
100%
100%
100%
DECAF W) > DECAF W)
FLB-U
73.3%
68.0%
62.7%
68.0%
DECAF(W) (W) + DECAF W)
FLB-P
70.7%
70.7%
73.3%
70.7%
SURF(AL A) DECAF(A A)
FLB-U
73.9%
83.7%
91.8%
83.7%
SURF (A) + (ECAF(A
FLB-P
73.9%
83.7%
87.8%
83.7%
(ECAF(A) - SURF A)
FLB-U
67.3%
67.3%
69.0%
67.3%
DECAF(A) A) + SURF( A
FLB-P
67.3%
68.2%
71.4%
68.2%
SURF(D)
DECAF
FLB-U
76.0%
76.0%
65.3%
76.0%
SURF(D) + DECAF
FLB-P
76.0%
76.0%
65.3%
76.0%
DECAF(D) + SURF
FLB-U
73.3%
62.7%
73.3%
62.7%
DECAF(D) + SURF (D)
FLB-P
73.3%
73.3%
73.3%
73.3%
SURF (W) + DECAF
FLB-U
70.7%
70.7%
76.0%
70.7%
SURF( (W) + DECAF W)
FLB-P
70.7%
70.7%
76.0%
70.7%
DECAF( (W) > SURF W
FLB-U
68.0%
68.0%
65.3%
68.0%
DECAF(W) (W) 7 SURF(W)
FLB-P
68.0%
68.0%
70.7%
68.0%
Table 5: In this table, present the accuracy comparison of the MPGW, UGW, and the proposed PGW method. We first describe the initialization method and report its accuracy, followed the accuracy of MPGW, UGW, and PGW. The prior distribution æ p(1 is set to be 0.2 in all experiments. To guarantee the SCAR assumption, for Surf(A) and Decaf(A), we set n 50, which is half of the total number of data in one single class. is set to be 250. Similarly, we set suitable n, m for Surf(D), Decaf(D), Surf(W), Decaf(W).
60

---

Published as a conference paper at ICLR 2025
DATASET
INIT МЕTHON
INIT TIME
MPGW
UGW
PGW (OURS)
SURF (A) (URF(A)
POT
1.4E-3
1.9E-2
3.8
2.0E-2
SURF A 7 SURF(A
FLB-U
2.2E-3
1.8E-2
3.6
1.9E-2
SURF (A) > SURF(A)
FLB-P
1.7E-3
1.8E-2
3.8
1.5E-2
DECAF(A) 7 DECAF
POT
1.7E-3
1.9E-2
7.3
1.9E-2
(ECAF(A) - DECAF
FLB-U
9.6E-3
1,8E-2
6.8
1.5E-2
DECAF(A) - DECAF(A)
FLB-P
2.0F-3
1.8E-2
6.7
1.6R-2
SURF(D) SURF
POT
2.9E-4
5.8E-4
3.1
3.8E-4
SURF ( 7 SURF (
FLB-U
1.4E-3
3.0E-3
5.4
2.2F-3
SURF SURF (D)
FLB-P
3.1E-4
2.9E-3
5.4
2.1E-3
DECAF(D) + DECAF(D)
POT
3.1E-4
6.0E-4
3.3
3.6E-4
DECAF + DECAF(
FLB-U
1.4E-3
2.9E-3
5.8
2.1E-3
DECAF ( + DECAF(D)
FLB-P
3.4E-4
2.8E-3
5.3
2.0E-3
SURF(W + SURF(W)
POT
3.0F-4
6.0R-4
5.2
3.6R-4
SURF W + SURF(W]
FLB-U
1.36-3
2.9R-3
5.1
2.1m-3
SURF W) + SURF( W)
FLB-P
3.3E-4
2.9E-3
5.1
2.1E-3
DECAF W) - DECAF W)
POT
3.3E-4
6.2E-4
3.3
3.4E-4
DECAF W 7 DECAF W)
FLB-U
1.2E-3
2.9E-3
5.8
2.1E-3
DECAF(W) - DECAF W)
FLB-P
3.3E-4
2.8E-3
5.4
2.0E-3
SURF A) DECAF(
FLB-U
1.1E-
2.8B-2
6.7
2.6F-
SURF(A) + DECAF A)
FLB-P
1.9E-3
2.2E-2
0.2
2.1E-2
DECAF(A) > SURF(A
FLB-U
0.1
5E-2
6.7
4E-2
DECAF(A) A)
+ SURF( A
FLB-P
2F-3
1.8
6.8
1.5
SURF(D) (D) + DECAF
FLB-U
1.8F-3
5.3R-3
6.0
2.3F-3
SURF(D) 7 DECAF
FLB-P
3.5E-4
3.9R-4
5.9
3.8E-4
DECAF(D) + SURF D
FLB-U
1.8E-3
0.296
5.6
0.165
DECAF(D) + SURF
FLB-P
3.3E-4
0.218
5.6
0.170
SURF + DECAF W)
FLB-U
1.8E-3
5.3E-3
5.0
2.3E-3
SURF( W) DECAF W
FLB-P
3.4E-4
4.1E-4
5.0
3.9E-4
DECAF( W) 7 SURF
FLB-U
1.86-3
5.1E-3
5.8
2.16-3
DECAF(W) (W) SURF W)
FLB-P
3.4E-4
2.9E-3
5.6
2.26-3
Table In this table, we present the wall-clock time comparison of the MPGW, UGW, and the proposed PGW method. We report the initialization method and its wall-clock time, followed by the wall-clock time each of the methods MPGW, UGW, and PGW. The units p(1
of all reported wall-clock times are seconds. The prior distribution 0.2 in all experiments. To guarantee the SCAR assumption, for Surf(A) and Decaf(A), we set 50, which is half of the total number of data in one single class. is set to be 250. Similarly, we set suitable n, m for Surf(D), Decaf(D), Surf(W), Dec.f(W).
is set to be
61


Reviews:
[{"review_id": "XWKv3PHRKh", "reviewer": "Reviewer_q52X", "summary": "This paper improves unbalanced approaches to the optimal transport (OT) problem. \nThe objective is to compare probability measures between different metric spaces (GW distances).\nTo overcome the non-convexity of the  formulation, which usually relies on the Frank-Wolfe (FW) \nalgorithm. \n\nThe authors propose a new metric rooted in the so called Partial Gromov-Wasserstein (PGW) problem, \nand the main novelty is to use a total variation penalty as well as to provide efficient solvers. \n\nThe paper commences by introducing OT and its partial extension POT.  Then, it comes out the regularization\nterm which in principle is the Kullback-Leibler divergence which is replaced by Total Variation (TV). \nThen, the FW algorithm is adopted. \n\nThe toy experiment: \n\"TOY EXAMPLE: SHAPE MATCHING WITH OUTLIERS\nWe use the moon dataset and synthetic 2D/3D spherical data in this experiment.\"\n\nshould be explained earlier in the paper to motivate the reader. Formal language should not be \nan enemy of intuition.\n\nPros: \n- Nice formal language. \n\nCons:\n- Not intuitive for general readers. \n- The contribution is relevant (avoid strong outliers) \n\nQuestions:\n- Is there any formalism for Bregman divergences?", "questions": "* Adequacy to Bregman divergences?\n* Put synthetic examples in the beigning as a motivation and smooth the formal language.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Nice formalization.", "weaknesses": "Very hard to read even for an experienced reviewer.", "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": "", "extra_scores": {}}, {"review_id": "UE138awhEL", "reviewer": "Reviewer_t4aR", "summary": "The Gromov-Wasserstein (GW) distance has drawn a lot of attention in recent years for the comparison of measures in different metric spaces. This paper focuses on the Unbalanced Gromov-Wasserstein (UGW) problem, which they called Partial Gromov-Wasserstein (PGW). They showed PGW is a well-defined metric between metric measuring spaces and discussed some theoretical properties. They designed a Frank-Wolfe algorithm-based method to solve PGW. Convergence analysis is provided. Numerically, they tested it on some datasets with existing baselines.", "questions": "Please address the question in the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Pros:\n\nThey propose PGW, a total variation version of the UGW problem with theoretical properties analysis.\n\nThe experiment is showing their good performance in PGW.", "weaknesses": "Cons:\n\n1. The main concern is the novelty and significance since the problem itself is not well-generalizable to other problems. Meanwhile, some techniques are adopted from existing works. For example:\n\na. What is the unique technique of your method design compared to the Frank-Wolfe solver presented in (Chapel et al., 2020) except their problem setting is UGW?\n\nb. How is the convergence analysis partially harder than the existing method?\n\nc. Since the algorithm only guarantees stationary points (this is fine, the reviewer does not require a global optimality), how can we convinced it works well in more real scenarios? Is there any more evidence?\n\n\n\n2. For the FW algorithm in the optimization problem in line 331, it’s the main subroutine in each iteration, how is the complexity of solving it? This is important in the analysis since FW usually could be dramatically slowed down by the subroutine.\n\n\n3. Minor issue. There are some citation errors in lines 165 and 177.", "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": "", "extra_scores": {}}, {"review_id": "MFJQRc0UuR", "reviewer": "Reviewer_pJHH", "summary": "This paper introduces the Partial Gromov-Wasserstein (PGW) metric, a novel adaptation of the Gromov-Wasserstein (GW) distance tailored for metric measure spaces. Unlike traditional GW, which requires equal mass in spaces for meaningful comparison, PGW accommodates unbalanced settings through the incorporation of a total variation penalty. The authors present theoretical results, including proof of PGW as a metric, and develop two Frank-Wolfe solvers for computational efficiency. Experiments on shape matching, retrieval, and interpolation demonstrate PGW's robustness to some extent.", "questions": "- The baseline selection of the experiment is too limited to demonstrate the effectiveness of your methods. Why don't you compare the methods [1,2,3] based on robust OT? Please add corresponding experiments.\n- - [1] Nietert S, Goldfeld Z, Cummings R. Outlier-robust optimal transport: Duality, structure, and statistical analysis[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2022: 11691-11719.\n- - [2] Wang X, Huang J, Yang Q, et al. On Robust Wasserstein Barycenter: The Model and Algorithm[C]//Proceedings of the 2024 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2024: 235-243.\n- - [3] Le K, Nguyen H, Nguyen Q M, et al. On robust optimal transport: Computational complexity and barycenter computation[J]. Advances in Neural Information Processing Systems, 2021, 34: 21947-21959.\n- In Wasserstein barycenter's experiment for robustness, why only show the interpolation between two shapes? Can you show me how the algorithm computes the average shape of several shapes?\n- It seems that all the experiments you provide can be replaced by the equivalent of robust OT, which cannot truly reflect the advantages of robust Gromov-Wasserstein barycenter.\n- Is the parameter $\\lambda$ easy to search? Different proportions of noise seem to require different $\\lambda$s. Does this hinder the practicality of this method? It seems that the specific $\\lambda$ search process and the influence of $\\lambda$ on the experimental effect are not given in the experiment.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper rigorously proves that PGW qualifies as a metric.\n- The two Frank-Wolfe solvers for PGW demonstrate effective performance, making the method feasible for practical applications.\n- Experimental results indicate that PGW outperforms traditional GW in handling unbalanced data with outliers, enhancing its utility in real-world tasks.", "weaknesses": "- Comparisons with alternative unbalanced OT metrics are somewhat limited, which leaves the practical performance of PGW against state-of-the-art methods less explored.\n- The robustness parameter $\\lambda$ requires careful tuning, which could pose a challenge for practical applications.\n- The computational efficiency of PGW may still be restrictive in high-dimensional settings or for very large datasets.", "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": "", "extra_scores": {}}, {"review_id": "hOXxJGfBHy", "reviewer": "Reviewer_htBd", "summary": "The Gromov-Wasserstein (GW) distance is a metric on probability measures supported on different metric spaces. This paper extends this notion to more general Radon measures, not necessarily probability measures, termed partial Gromov-Wasserstein (PGW) distance. The authors show that PGW is indeed a metric. Two Frank-Wolfe (FW) algorithms are proposed to compute PGW, and three examples are provided to illustrate the performance of PGW.", "questions": "1, Please read the paper thoroughly and correct any other typos.\n\n2, Is the proposed Algorithm 1 the same as Algorithm 1 in the paper \"Partial Optimal Transport with Applications on Positive-Unlabeled Learning\"? What are the novelties in the optimization algorithms?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1, The main contribution is to establish the metric property of partial GW. \n\n2, Simulations in subsection 6.2 clearly demonstrate improved performance of PGW compared to MPGW.\n\n2, The simulation examples are interesting and illustrative.", "weaknesses": "1, The current manuscript has many typos. For example, the citations on lines 165 and 177 are not displaying properly.", "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": "", "extra_scores": {}}, {"review_id": "HfAyK7SUT6", "reviewer": "Reviewer_2CuZ", "summary": "This paper introduces Partial Gromov-Wasserstein (PGW), a particular case of UGW, and prove that it is a metric between mm-spaces. The authors propose Frank-Wolfe-based algorithms with convergence guarantees for solving the PGW problem and extend the concept of barycenters to mm-spaces. PGW’s effectiveness is demonstrated through applications like shape matching, retrieval, and interpolation, showing improved performance over existing baselines.", "questions": "1. Could the authors incorporate other experiments, such as PU learning (positive-unlabeled learning), to provide a broader evaluation?\n  \n2. Could the authors report the results of varying hyperparameters in the baselines to examine their impact on performance?\n  \n3. While the KL divergence in UGW is not a rigorous metric, it has desirable properties such as robustness to outliers. Could the authors explain why the TV norm used in PGW results in better performance in the numerical experiments compared to UGW? Alternatively, is the improved performance due to the use of the Frank-Wolfe (FW) algorithm instead of Sinkhorn?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and easy to follow.\n  \n2. The paper rigorously proves that PGW, a specific case of UGW with the TV norm as the chosen $f$-divergence, defines a valid metric between mm-spaces, contributing to the theoretical understanding of these transport frameworks.\n  \n3. The authors propose using the Frank-Wolfe algorithm to solve the PGW problem and provide a convergence guarantee, enhancing the computational tractability of the method.", "weaknesses": "1. Limited Experimental Scope: The experimental evaluation in this paper could be expanded. It might be helpful to include experiments on PU learning (positive-unlabeled learning), similar to those conducted in the UGW paper, for a more comprehensive comparison.\n  \n2. Hyperparameter Tuning in Baselines: For the toy examples and point cloud matching experiments, the baselines' performance might improve with more thorough hyperparameter tuning since authors use fixed values mentioned in Appendix N. Given that UGW has been shown to be robust to outliers both theoretically and empirically (as demonstrated in the original UGW paper and also [A]), better-tuned baselines could potentially mitigate the impact of outliers more effectively in these experiments.\n\n3. Minor Issues: Several broken references and citations are present in the paper, such as those on lines 165-166, 894, and 1025. Addressing these would improve the paper's readability and professionalism.\n\n\n[A] Tran, Quang Huy, et al. \"Unbalanced co-optimal transport.\" *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 37. No. 8. 2023.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)