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

Abstract: The Gromov–Wasserstein (GW) problem, a variant of the classical optimal transport (OT) problem, has attracted growing interest in the machine learning and data science communities due to its ability to quantify similarity between measures in different metric spaces. However, like the classical OT problem, GW imposes an equal mass constraint between measures, which restricts its application in many machine learning tasks. To address this limitation, the partial Gromov-Wasserstein (PGW) problem has been introduced.
 It relaxes the equal mass constraint, allowing the comparison of general positive Radon measures. Despite this, both GW and PGW face significant computational challenges due to their non-convex nature. To overcome these challenges, we propose the linear partial Gromov-Wasserstein (LPGW) embedding, a linearized embedding technique for the PGW problem. For $K$ different metric measure spaces, the pairwise computation of the PGW distance requires solving the PGW problem $\mathcal{O}(K^2)$ times.
In contrast, the proposed linearization technique reduces this to $\mathcal{O}(K)$ times. Similar to the linearization technique for the classical OT problem, we prove that LPGW defines a valid metric for metric measure spaces. Finally, we demonstrate the effectiveness of LPGW in practical applications such as shape retrieval and learning with transport-based embeddings, showing that LPGW preserves the advantages of PGW in partial matching while significantly enhancing computational efficiency. The code is available at https://github.com/mint-vu/Linearized_Partial_Gromov_Wasserstein.

Published as a conference paper at ICLR 2025
LINEAR PARTIAL GROMOV-WASSERSTE EMBEDDING
Yikun Bai', Abihith Kothapalli" Hengrong, Du 2 Rocio Diaz Martin" 33 and Soheil Kolouri'
Department of Computer Science, Vanderbilt University
2 mepartment of Mathematics, University of California, Irvine 3 Depparment of Mathematics, Tufts University 1 Lyikun.bal bai, abi hothaall,,, koheil. kolouri@vanderrblt..ed. hhengrond @wci..dddudiuuuuu 3 rocio. diaz martin@tufts..duu
ABSTRACT
The Gromov-Waan Wasserstein (GW) problem, a variant of the classical opti- mal transport (OT) problem, has attracted growing interest in the machine learning and data science communities due to its ability to quantify similar- ity between measures in different metric spaces. However, like the classical OT problem, GW imposes an equal mass constraint between mcasures, which restricts its application in many machine learning tasks. To address this limitation, the partial introduced. relaxes the equal mass constraint, allowing the comparison of general positive Radon measures. Despite this, both GW and PGW face sig- nificant computational challenges due to their non-convex nature. To over- come these challenges, we propose the linear partial Gromov-Wasserste Wasserstein (LPGW) embedding, a lincarized embedding technique for the PGW prob- lem. For K different metric mcasure spaces, the pairwise computation of the PGW distance requires solving the PGW problem O(K2) times. In contrast, the proposed linearization technique reduces this O(K) times. Similar to the linearization technique for the classical OT problem, we prove that LPGW defines a valid metric for metric measure spaces. Finally, we demonstrate the effectiveness of LPGW in practical applications such as shape retrieval and learning with transport-based embeddings, showing that LPGW preserves the advantages of PGW in partial matching while signifi- cantly enhancing computational efficiency. The code available at https: Parttarridd__aratalallaaaaaaaaal Partial, -romov Wasserstein.
(PGW) problem has been
//github.
INTRODUCTION
Optimal transport (OT), unbalanced and partial OT, and linearized OT. The core objective this work, and general challenge machine learning, to match objects and devise practical, computationally efficient notions of similarity between shapes. One of the most well-known techniques for this task arises from optimal transport (OT) theory, which has found extensive applications in generative modcling (Arjovsky et al., 2017: Genevay et al., 2016), domain adaptation (Courty et al., 2016; Balaji et al., 2020), represontation learning (Wu et al., 2023), and many other domains. The classical OT problem, as detailed by (Villani, 2009), involves matching two probability distributions to minimize the expected transportation cost, giving rise to the so-called Wasserstein distances. Although the classi- cal OT problem imposes a mass conservation requirement, recent advances have extended the utility of OT beyond probability measures, allowing for comparisons of non-negative measures with different total masses and partial matching of sets through the unbalanced and partial OT frameworks (Chizat et al., 201 2018;;;; Fatras et al., 2021; Séjourné et al., 2021). Additionally, in large-scale machine learning applications, since the OT approach computationally expensive, has motivated numerous approximations that lead to sig- nificant speedups, such as those in (Cuturi, 2013; Chizat et al., 2020; Scetbon & Cuturi,
These authors contributed equally to this work.

---

Published as a conference paper at ICLR 2025
2022), and the lincarization technique, termed linear optimal transportation (LOT), pro- posed by (Wang et al., 2013). There have also been advances in reducing the computational complexity of comparing unbalanced measures (Cai et al., 2022; Bai et al., 2023).
The Gromov- Wasserstein (GW) distance, unbalanced and partial GW, and lin- carized GW. Another line of research has focused on the comparison of probability mea- sures across different metric spaces using Gromov- Manoov-Wassorstein (GW) distances (Mémoli, 2011). These innovations have applications in areas ranging from quantum chemistry (Peyré et al., 2016) to natural language processing (Alvarez-Ni) Melis & Jaakkola, 2018), enhancing fundamental tasks such as clustering (Chowdhury & Needham, 2021), dimensionality re- duction (Van Assel et al., 2024), shape correspondence (Kong et al., 2024), shape analysis (Mémoli & Needham, 2022), and inference-based simulation (Hur et al., 2024). The GW distance is a valuable tool across a variety of domains, as it allows for comparisons between distributions while being independent of the ambient spaces. To extend GW to unbalanced settings, GW-like comparisons have been developed for metric measure spaces with differ- ing total masses (Liu et al., 2020; Chapel et al., 2020; Séjourné et al., 2021; Bai et al., 2024; Zhang et al., 2022). Furthermore, to address the computational expense of pairwise GW distance calculations in large-scale applications, a linearized version GW has been proposed in (Beier et al., 2022). Similar to the LOT framework (Wang et al., 2013), this approach is based on barycentric projection ion maps of transport plans.
Contributions.
We propose the linear Partial Gromov- Wasserstein embedding (LPGW) technique, which extends the classical LOT embedding technique to the partial GW setting.
Based on the embedding, we propose the so-called LPGW distance, which we prove be a metric under certain assumptions. Given K different metric measure spaces, computing their pairwise PGW distances requires solving the PGW problem O(K2) times. However, computing the LPGW distance pairwise requires only O(K) dis- tance computations.
Numerically, we test our proposed LPGW embedding and LPGW distance in two experiments: shape retrieval and learning with transform-based embeddings. In both experiments, we observe that the LPGW-based approach can preserve the partial matching property of PGW while significantly improving computational efficiency.
BACKGROUND
2.1 THE WASSERSTEIN DISTANCE
Let P(R.) be the space of probability measures on the Borel o-algebra Rd, and let P2(R4) == {u E P(R"): fae |x|2 < oo). Given a (measurable) mapping T Rdd + Rd.
the pushforward mcasure Tyj y is defined as TB)(B)= == (()) for all Borel sets B C Rd. where (B) = fx: T(x) E B} is the preimage of B under T.
Given u. E (RRR), the 2- Wassersteii distance is defined as
W (2, min TET(Ge) X
| - 2d
where T(H,, u) is set of joint probability measures on R RRd whose first and second marginals are μ and v, respectively. The classical OT theory (Villani, 2021; 2009) guarantees that a minimizer to (1) always exists, so such a formulation is well-defined. In fact, there might exist multiple minimizers, and we denote by (",,,)) v) the set of all optimal transportation plans for problem (1).
When an optimal transportation plan y is induced by a mapping T Rd > Idd, that is,
= (id x + E (u, with T+p== =
we say that the Monge mapping assumption holds, and the function T called a Monge mapping. In particular, by Brenier's theorem, when y is continuous measure (i.e.,
2

---

Published as a conference paper at ICLR 2025
absolutely continuous with respect to the Lebesgue measure on RR), Monge mapping T always exists and it is unique.
We refer to Appendix A for detailed introduction to the LOT formulation.
2.2 THE WASSSSV-ASNNNNTIIN DISTANCE
Consider two compact gauged measure spaces (gm-spaces) X (X, (x,9x, n)) and V (Y, gr, v), where X C _2= Y C Rd are non non-empty (compact) convex sets (with da, dy E N); 9x : X + R is a gauge function in ays (X ,,2)) i.c., the space of symmet- ric, real-valued functions on X == X x X that are square-integrabl
with respect to u := p @ u (similarly for gy E ( v and μ. V are probability measures de- fined on X,Y respectively. In addition, assume that X and Y are metric measure spaces (mm-spaces); that is, there exist distances dx and dy on X and Y, respectively. In gen- eral, we will assume that gx is a continuous function on X with respect to the metric dx ((x1, a1), (I2, = (x1, + dx (21, xh) on X (respectively, for gr). Thus, since X is compact, 9x (respectively, gy) is Lipschitz continuous function, Le., there exists K E Ry0 such that
(9x( - 9x (x 25)1 & (dx( + (x(x),, a2)), Vxn, 21. X2, x/2 E X.
(3)
For the reader's convenience, unless stated otherwise, we default to gx (x), (2
(z) 22)
(which is the classical setting for the Wasnov-asssesttein problem (Alvarez-Melis & Jaakkola, 2018; Vayer, 2020)), to the inner product gx (x1, x22 x 22 (which has been studied in (Vayer, 2020; Sturm, 2012)). The same applies to gy.
The Gromov-Wassersten (GW) problem between and Y defined as
GW? Y) = min (1gx gr P,7 7ET(Lu)
(4)
where
[ (xxx) lex(x, - gr v/) dr(xx, v)d ,'))-
(lex grl2, 82)
A minimizer for (4) always exists (Mémoli, 2011), and we use I (" Y) to denote the set of all optimal transportation plans y E T(u, v) for the GW problem defined in (4). In addition, when ex = d& and gr dy for s 2 1, (W.).) defines metric on the space of mm-spaces up to isomorphism'
Similar to classical OT theory, we say that the GW-Monge mapping assumption holds there exists a minimizer for (4) of the form 7 = (id x Tu, where id X + X is the identity map
X, and T X - Y is measurable function that pushes forward μa to v. In recent years, the existence of Monge mappings for the GW problem has been studied in works such as (Vayer, 2020; Maron & Lipman, 2018; Dumont et al., 2024).
Note that the GW minimization problem defined in (4) is quadratic but hon-convex. The computational cost of GW(:)) for discrete measures nt of size n is O(n L.) to obtain a solution that a local minimum, where n² is the computational cost of one iteration and L is the required number of iterations". Thus, when faced with the task of computing the pairwise GW distances between discrete gm-spaces Y'...., YK with n points each, the resulting complexity is O(K2 nn3 L). To reduce the complexity of computing the pairwise distances in this setting, (Beier ct al., 2022) introduces a lincar embedding technique called linear Gromov- Wasserstein (LGW), which we discuss in the following section.
2.3 THE LINEAR GROMOV-WASSERSTEE EMBEDDING AND DISTANCE
Consider a fixed gm-space X = (X,9x.H). which serves as a reference space. Given a target gm-space Y = (Y.gy, v), suppose that the GW-Monge mapping assumption holds, ie., there exists an optimal transportation plan 7 = (id x T) for the GW problem
"wwo mm-spaces X, Y are isomorphic is there exists an isometry v : X + Y, Le., dx(a,x²) = dy (1b(2), (<x"), which is surjective and such that v = th
We refer to Appendix D) for details.
3

---

Published as a conference paper at ICLR 2025
(4) between X and Y. Then, the linear Gromov-Wassersten (LGW) embedding is defined as the following mapping
Y + k4 == -r
(5)
which assigns each gm-space Y to gauge function by X X R defined by (5). This embedding can recover the GW distance GW(X, Y) by the following:
GW = Sx (
Given two gm-spaces VI (Y) ,9r,, ,y,, =2 (Y2, assume that there exist op- timal transportation plans 7= (id x T 4/1 (X, = (id x T E [* W²). Let k kyz denote the corresponding linear GW embeddings defined by (5). Then, the LGW distance conditioned on ,1,7? is defined as
LGW(Y", xt,,t,, || k kgall22(102)
(6)
When the GW-Monge mapping assumption does not hold, (Beier et al., 2022) extend the above distance conditioned on pair of arbitrary plans 7² E ( r' 1"xX, Y2):
LGW(Y', "''''',2:x77'..1 nerle (m) (1rr1 grel? 899)
inf
inf - (x3j4 I
lori (r- v "' o't ""''""""''"
where
= I(y', 13:) tye x Y x 2²): (Tx (== (xx))))))))))))))))))))))))))))) =2, (Tx)# p),
for Tx, v.,,,,,,))))) = (x,y') for = 1,2, and xx (x, = x. Finally, the LGW distance between y1 and 82 is defined as
LGW(Y' (Y Y2X)
inf 7'Er"(ww"") (M.2)
LGW(Y), ",,,,',)?
(8)
We refer to Appendix for further details.
To simplify the computation of the above formulation, (Beier et al., 2022) propose the barycentric projection method, which we will briefly review here.
Let E E I(,,v) be transportation plan between E P(X) and v E P(Y). By using [Definition 5.4.2, Ambrosio et al. (2005)], the barycentric projection map T, : X + is defined
Tx(x) S, y d (zlx).
where (yyx )= is the corresponding disintegration of with respect to its first marginal μ. That is, (xx))xx is family of measures satisfying
J o(z,)) d(,,)) Jel, ((a,))) ((xxx(()d)d) V C(E
n E (X. Y), define the measure T..- (Tx- P(Y) and the gm-space Vy- (Y,gr, M. We provide the following results as a complement to the work in (Beier et al., 2022).
Proposition 2.1. Let 7" E (X Y) and 70 (X, Then, have the following:
(1) The LGW embedding of Y can recover the GW distance, i.e.,
LGW -

---

Published as a conference paper at ICLR 2025
(2) I is Monge mapping for GW(X, Y) such that y- (id x #) then Tr. T, p-a.e. As consequence, V.-. = v and thus Vx- Y.
(3) If 9y(-1.2) = a(11, where 22) is an inner product restricted to and a E R, then the barycentric projection map Tx- defined by (9) is Monge mapping in the sense that 7 (id T is optimal for the GW problem GW (X, V.-).
We refer the reader to Appendix E for the proof.
Based on the above proposition, given Y = ,y', and Y = (Y2,,y2, 100y, let 7 E (X, Y! and 72 E (X, Y²). The following approximated LGW (aLGW) distance can be used as a proxy for the LGW and GW distances. Furthermore, in practice, we can fix a single pair (7', ?²) to compute the distance rather than compute the infimum:
aLGW(Y', x²:x)==
inf (x,)) (x,""
LG, 23:i
inf (x.1) (x,1)
llr1 (Tx(11))) (2)) (T
(10)
2 10 (T,) (1),, gr -T,6
(11)
2.4 THE PARTIAL WASIERSSESS DISTANCE
Partial Gromov-Ward Wasserstein (PGW), or more generally, unbalanced GW, relaxes the assumption that n, are normalized probability measures (Chapel et al., 2020; Séjourné et al., 2021; Bai et al., 2024). In particular, the PGW distance is defined as
(X, Y):= = inf (1ax 1rr + A(I - 7x + |202 022 I), rElg(u.))
(12)
where À 0 is parameter; 7x (xx) # 7, 7, (TY) # the corresponding marginals
y on X and Y, respectively; and I& (14, v) = f E M+ x XY) : 7x S s. ty S v), where (4 Y) denotes the set of finite non-negative measures on X x Y, and xx S a denotes that for any Borel set A, (A) S ((A) (similarly for > S v).
In the discrete setting, the PGW problem algorithm (see the algorithms in (Bai et al., 2024) for details). From a theoretical perspec- tive, there always exists a minimizer for the optimization problem in (12) (see [Proposition 3.3, (Bai et al., 2024)]). We use the notation 1 x (x, Y) to denote the set of all optimal transportation plans for PGWA(X, Y). For convenience, when À is fixed, we may omit the subscript and write (X, Y) instead.
be solved by variants of the Frank-Wolff
We say that the PGW-Monge mapping assumption holds if there exists optimal transportation plan for the optimization problem in (12) of the form 7 = (id x T) for some T: X +Y
3 LINEAR PARTIAL GROMOV WASSERSTEIN EMBEDDING AND DISTANCE
Inspired by the work in (Beier et al., 2022), we extend the LGW distance to the unbalanced setting. In particular, we present a linearization technique for the PGW problem proposed in (Bai al., 2024).
Given gmm-spaces X = (X, and Y = vV, let E 1% 1 Y). We first suppose that the PGW-Monge mapping assumption holds; that is, = (id x +x for some T X Y. We subsequently define the linear partial Gromov- Wasserstein (LPGW) embedding
V ト (1x, Nc),
(13)
where 7x = (Tx)#7, (,,-1.))) -x),1))) (T)(())))() and To == مو (rr) 62
for Ty = (Ty) Here, the first component of the embedding, 7x, encodes the mass transportation from the source domain X. The second component, ky, describes the trans- portation cost function. Finally, the third component, Ye, encodes the mass creation in the target domain Y.
5

---

Published as a conference paper at ICLR 2025
Similarly to the LGW embedding given by (5), we show in Proposition 3.1 that the above embedding can recover PGWA Y in the sense that
| Mxy-1122(77))) (0) M(H1 hxl + 112l) PGWA Y).
Given two gm spaces Y', Y2, let 7' E r 2 (X, Y' and 72 - x Y²). Suppose ?² are induced by Monge mappings T T and compute the corresponding LPGW embeddings via (13). We define the LPGW discrepancy conditioned on 71,7² by
LPGWA 82 = inf [|,, k,z (12 Alp2 + j0212 - - (14)
where (nx A (B) (7 + (E F)). Note that the above lormulation can be written entirely in terms the LPGW embeddings since |v-12 hal + lxxl', and similarly 10212 hal h2
When the PGW-Monge mapping assumption does not hold, we extend the above LPGW dis- crepancy conditioned on arbitrary transportation plans 7 E 1 2 ) E x Y?) as follows:
LPGWA ,
inf
1ly! gralle + A(e | |0912 2/x)3,, (15)
Ter (ang(rtntt))
where
Ts(1 = E (x xY)): (xxx)) S 7*, (Tx,Y= #7 S 7 Finally, to gain independence from the transportation plans 7 73, we formally define the LPGW discrepancy as
LPGW> (2;))
inf g. 2x
LPGW x
(16)
Proposition 3.1. Given compact gm-spaces X = (X.gx.1) and Y = (Y,gr, v), let 70 T 1 (X,X) and 7 x Y). We have the following:
(1) Problem (15) admits minimizer.
(2) Under the PG PGM-Me mapping assumplion, the problems (14) and (15) coincide.
(3) Under the PGW-Monge mapping ossumption, when
2A
max Eyr
(y .y - gr gr2 21
(17)
problem (14) achieves the value
LPGW (F, = 1k, k,a 111211332230000 + A(p211 2 +10pp -2/7x A x
(18)
(4) The LPGW embedding of Y recover PGW,,%, Y) in the sense that, under the PG PGW-Monge mapping assumplion, we have
||a (12=((17)02) - >(|a|2 hxll + h::1 = (X,)(X,
and in general, we have
LPGW (X,7: (X))(
(5) The LPGW discrepancies defined in (15) and (16) are pseudo-metrics. Indeed, under certain conditions, (16) is a rigorous metric. We refer to Appendiz F for delailed discussion.

---

Published as a conference paper at ICLR 2025
The proof of the above proposition is included in Appendix F.
Similar to LGW, to accelerate the computation of the above formulation, we propose the following barycentric projection method in the LPGW setting.
First, similar to Proposition 2.1, we present the following theorem, for which we provide the proof in Appendix H.
Theorem 3.2. Given gm--spaces X (x, and Y = (Y,gy, let 70 E T g' (X, and 7" E MM+(X X).. Further, let V = V. = (Tx') and y (Y, D). Then,
(1) 1f is induced by a mapping T, then T T, a.s.
(2) 1 E (X Y), and the conditions for gy (-1, 2) in statement (3) of Proposition 2.1 hold, then 7. = (id x T7 is optimal for PGW V,.).
(3) If 7 E (Xx and 72 E T (x, (x, Y2), and the PGW-Monge mapping assumplion holds, then
LPGWA CY X
LPGWA N,, + A(hal + +1 (19)
Based part (3) in the above theorem, we define the approximated LPGW (aLPGW) discrepancy by
aLPGW
inf x 2 g.
LPGWA R,2; A0h2++ hall-
(20)
Proposition 3.3. If X.XY Y are compact sets, when X is sufficienlly large, in particular, (17)
is satisfied, the above formulation becomes:
aLPGWX(Y)) ,Y:))
inf (,,,) (.
|ikt kG 1 + A(w' ( 1|21 2nx 1x2 (21)
In practice, similar to LGW, we only select one pair of optimal transportation plans ?
to compute the embedding and the above aLPGW discrepancy. In addition, we apply (21) to approximate the original formula (20). That is, in our experiments, we directly compute
||ky, kyy 1 yo + A(122 |0312 - 2/xx 17)
(22)
3.1 NUMERICAL IMPLEMENTATION OF LPGW IN DISCRETE SETTING
In practice, we consider discrete distributions (or, more generally, discrcte Radon measures). Suppose X {X, (1-Illd, 1 = Σ pr62, where X R is convex compact set containing (0d, 21,... 2.). We similarly let y (Y', Ila,, EØ g3 and y (Y?,
11,, 1² = 1122 k.))))
Suppose 71 E RT is an optimal transportation plan for PGWA(X, Y!). By convexity of Y, the barycentric projection given by (9) becomes
0: q br'l if where /= = = 7 1m
Txp
(23)
Od
if To
Thus, the corresponding projected measure becomes By. = E, 7. - In addition, we have hnl = ( p,) -Zi 7.) Let
K = ky. [ll.. 7711 - ||,, 2 (lveee E Rx*
(24)
Suppose ?2 E R m an optimal transportation plan for (GW Y2). We define all corresponding terms analogously.

---

Published as a conference paper at ICLR 2025
Let g¹.² - - -0.1011 by (20) and (21) becomes
E= q/. The aLPGW distance given
aL.PGW X2
(10)) -
9i 112-1
2/)
i=1
- [Ki K2) ( + a(ha + hha |
-22 42
(rV);
(25)
where (K₃ - K2)² denotes the element-wise squared matrix and -=== 92 3) The above quantity (25) can be used to approximate the original PGW distance between V and Y
= 91 (similarly for
In addition, the original LPGW embedding (13) of Y (in fact, of Y' is (K', 17,,,))). 1e). We reduce this embedding to (K), 7. Ie!l) which is sufficient to compute the above aLPGW discrepancy. Thus, (K) " hid can be regarded as numerical implementation of the LPGW embedding (13).
EXPERIMENTS
4.1 ELLIPTICAL DISKS
In this experiment, we apply the LPGW distance and the PGW distance to the 2D dataset presented in (Beier et al., 2022), consisting of 100 elliptical disks. We first compute the pairwise distances between the samples using the PGW distance and then compare them against the LPGW distance using nine different reference spaces. We present the resulting wall-clock time for each method and evaluate the quality of the approximation of PGW by LPGW using the mean relative error (MRE) and the Pearson correlation coefficient (PCC).
Experiment setup. We represent each 2D shape an mm-space X' (R22 || H²), where μ¹' Σi= n 16g, We normalize each shape so that the largest pairwise distance in each mm-space is 1. Based on [Lemma E.2, Bai et al. (2023)], the largest possible choice of X given by 2A = 1. We hence test À E (0.05, 0.08, 0.1, 0.3, 0.5), and for each reference space, we compute the pairwise LPGW distances and compute the wall-clock time, MRE, and PCC. We refer to Appendix K for full numerical details, MDS visualizations, and complete results.
Performance analysis. We present the results when = observe that LPGW is significantly faster than PGW it only requires N 100 transport plan computations, whereas the PGW methods require (2) transport plan computations. Second, we observe that when the reference space is one of S7, Ss. Sg, LPGW admits relatively smaller MRE and higher PCC, demonstrating the importance of the chosen reference space.
Table 1. First, we
PGW
8
Sy
points
441
545
317
time (min)
46.97
1.56
MRE
0,0114
PCC f
0.5781
0.5738
0.5881
0.8581
0.9871
0.9930
0.9952
0.9954
0.9949
Table 1: Experimental results when À 0.1. The first row shows the total wall-clock time for PGW and LPGW. The second and third rows display the MRE (mean relative error) and PCC (Pearson correlation coefficient), respectively.
4.2 SHAPE RETRIEVAL
Experiment setup. We now employ the PGW distance to distinguish between 2D and 3D shapes, similarly to as done in (Beier et al., 2022). We use GW, LGW, and PGW as baselines for comparison against the results of our proposed LPGW. Given a series of
shapes, represent. the shapes mm-spaces X (R4, || 112, u²), where j² Ex'r a a'
8

---

Published as a conference paper at ICLR 2025
For the GW and LGW methods, normalize the mass for the balanced mass constraint setting (i.e., a' = 3) and for the PGW and LPGW methods, we let a² = a for all the shapes, where > Ô is fixed constant. In this manner, we compute the pairwise distances between the shapes.
Next, using the approach given by (Beier al., 2022), we combine each distance matrix with a support vector machine (SVM), applying stratified 10-fold cross-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 to 9 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 one 2D shape dataset and one 3D shape dataset. We use the 2D datasct presented in (Bai et al., 2024), consisting of 8 classes, cach containing 20 shapes. The 3D datasct is given by (Pan al., 2021), which provides 100-200 complete shapes in each of 16 different classes, and for each complete shape, provides 26 corresponding "incomplete shapes." We choose four classes of shapes from this dataset, and for each, we sample 15 complete and 45 incomplete shapes, yielding total of 240 shapes. The datasels are visualized in Figure in the Appendix.
Performance analysis. We refer to Ap- pendix L for full numerical details, param- eler settings, and the visualization of the resulting confusion matrices. We visualize the resulting pairwise distance matrices in Figure 7. For the SVM experiments, on the 2D dataset, GW achieves the highest accu- racy, 98. 08.1% while the second best method LPGW, 97.5%. On the 3D dataset, PGW achieves the highest accuracy of 93.8%, and LPGW achieves the next. highest accuracy of 93.7%. We refer to Table for details.
LPGW (ours)
GW
PGW
LGW
Dataset
Accuracy
98.1% 43s
96.2%
93.7% 0.4s
97.5%
Time (6)
39s
0.8s
3D
Dataset
Accuracy
92.5%
93.8% %
92.5%
93.7%
Time (m))
203.0m
203.6m
1.3m
1.8m
Accuracy and wall-clock time com- parison in shape retrieval experiment.
Table 2:
In addition, we report the wall-clock time required to compute all pairwise distances for each distance in Table 2. In both datasets, observe that LGW /LPGW admit similar computational time and are much faster than GW/PGW, This difference is more obvious in the 3D dataset. We note that when À is sufficiently large, the performance between the LPGW method and the LGW method is the same (see Appendix L for details).
4.3 LEARNING WITH TRANSFORM-BASDA EMBEDDINGS
Data
Method
LOT
LGW
LPGW (ours)
Accuracy
89.0%
82.5%
82.5%
rotation
Time 4
+13s+16s
105s+777s
309s-+84s
Accuracy
51.2%
82.5%
82.5%
0
Time +
183s+15s
405s+777
309s-+84s
Accuracy
13.4%
17.0%
81.8%
1 = 0.1
Time
183s + 17s
405s--888 88s
309s+-914
Accuracy
12.5%
13.3%
75.8%
= 0.3
Time 4
183s4-234
405s 145s
309s + 123s
Accuracy 12.5%
12.5%
72.9%
0.5
Time 4
183s +-3s
405s+-2484
309s 168s
Table Accuracy and wall-clock time comparison for learning with transform-based em- beddings experiments. We report each time as t t2, where t is the time required to compute the training set embeddings and t2 is the time required to compute the testing set embeddings.
In this experiment, we perform machine learning tasks using transform-based embeddings. Specifically, given training and testing datasets, apply various transform-bast embed- ding methods to both. Additionally, we assume that the testing data randomly rotated and has been corrupted with random noise. The objective is to evaluate the robustness of
9

---

Published as a conference paper at ICLR 2025
machine learning models trained using the different embedding techniques. The full numer- ical details for this experiment can be found in Appendix M.
Baseline methods. In this experiment, we consider several classical embedding methods, namely the LOT embedding (Wang et al., 2013; Kolouri et al., 2020; Nenna & Pass, 2023), LGW embedding (Beier et al., 2022), and our proposed LPGW embedding.
Dataset setup. We adopt the MNIST 2D point cloud dataset for this experiment. Specifically, for each digit, we sample N1 = 500 point clouds per class from the training set and N₂ = 100 point clouds per class from the testing set. Each point cloud is represented
3
4
3
4
gm-space in R2 with the mcasure p= -==i= p:Oa,, where pt > 0, Ví E {l,..., n are the pixel intensities provided by the original dataset. We normalize pj such that Σ P. = 1 for all sampled point clouds.
(a) MNIST point cloud dataset.
For each shape in the training set, we randomly ro- tate or flip the shape horizontally and add the trans- formed shape to the training set. As a result, each class contains 500 x 2 = 1000 shapes in the training set. For each test shape, we first randomly rolate or flip the shape, and we then "corrupt" the shape by adding uniformly distributed noise. The mass of each added point is 1, where n is the number of points in the original shape, and the total mass of the added points is E (0,0.1 0.1, 0.3,
n
Dala
LoT
LGW
LPGW
(b) Reconstructed digits based on the D0T/LGW/LPGV) embeddings.
Performance analysis. For each method (LOT, LGW, and LPGW), we first compute the embed- dings of the training data and optimize a classifica- tion model (logistic regression) using these embeddings. Then, we compute the embeddings for the test dataset and evaluate the accuracy of the model on the test emboddings. The results are presented in Table 3. In this table, we observe that for the original test datasct, LOT achieves the highest accuracy at 89.0%. However, on the corrupted dataset, LOT's performance drops significantly, classifying only 51% correctly when 1/ = 0 (no noise but with random rotation/ fflip) and falling dropping to 12.5% (i.e., random guessing) when n > 0.1. LGW is more robust to the data with random rotations /flps, but its accuracy also reduces to random guessing as is increased. In contrast, LPGW embeddings exhibit substantially greater performance, with its accuracy ranging from 70-85% when 1) 2 0.1.
Figure 1: MNIST digits and its ro- construction.
For an intuitive comparison of the performance of these embeddings, we present the data reconstruction results in Figure 1b and the t-SNE visualization of the embeddings produced by each method in Figure 9. Further details can be found in Appendix N.
SUMMARY
In this paper, propose the linear partial Gromov- Wasserstein (LPGW) embedding, linearization technique for the PGW problem. Theoretically, we prove that LPGW admits a metric with certain assumptions, and numerically, we demonstrate the utility of our proposed LPGW method in shape retrieval and learning with transform-based embedding tasks. We demonstrate that the L.GWW-based method can preserve the partial matching property of PGW while significantly improving computational efficiency.
A ACKNOWLEDGMENTS
This research was partially supported by the NSF CAREER Award No. 2339898.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
David Aivarez-Melis and Tommi S Jaakkola. wrosor-wasserstein alignment word em- bedding spaces. arXiv preprint arXi::189.00000 00013, 2018.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Grodient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasscrstein generative adversarial networks. In International conference machine learning, pp. 214-223. PMLR, 2017.
Yikun Bai, Bernard Schmitzer, Mathew Thorpe, and Soheil Kolouri. Sliced optimal partial transport. arxiv preprint (tt::2212.080433 2022.
Yikun Bai, Ivan Vladimir Medri, Rocio Diaz Martin, Rana Shahroz, and Soheil Kolouri. Linear optimal partial transport embedding. In International Conference Machine Learning, pp. 1492-1520. 1520. PMLR, 2023.
Yikun Bai, Rocio Diaz Martin, Abihith Kothapalli, Hengrong Du Xinran Liu, and Soheil Kolouri. Partial gromov-wasserseiin metric. arXiv preprinl arXiv:2402. 03664, 2024.
Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applica- tions in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 33:12934 12944, 2020.
Florian Beier, Robert Beinert, and Gabriele Steidl. On linear gromov-wassersien distance. IEEE Transactions on Image Processing, 31:7292-7300 2022.
Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia conference, pp. 1-12, 2011.
Tianji Cai, Junyi Cheng, Bernhard Schmitzer, and Matthew Thorpe. The linearized hellinger hellinger-kantorone kaatorovict distance. SIAM Journal on Imaging Sciences, 15(1):45-83) 83, 2022.
Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applica- tions on positive-unlabeled learning. Advances in Neural Information Processing Systems, 33:2903-29133 2020.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François- Xavier Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87 (314):2563-266) 2609, 2018a.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François Xavier Vialard. Unbal- anced optimal transport: Dynamic and Kantorovich formulations. Journal of Functional Analysis, (7:(3)):0090-111) 3123, 2018b.
Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xaan Xavier Vialard, and Gabriel Peyré. Faster wasserstein distance estimation with the sinkhorn divergence. Advances in Neural Information Processing Systems, 33:2257 13:2257-2269, 2020.
Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov- wasserstein learning. In International Conference Artificial Intelligence and Statistics, pp. 712-720. PMLR, 2021.
Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy. Optimal transport for domain adaptation. IEEE transactions pattern analysis and machine intelligence, 3953):1833-1865, 2016.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Théo Dumont, Théo Lacombe, and Xavver Vialard. On the existence of monge maps for the gromov- wasserstein problem. Foundations of Computational Mathematics, pp. 1 1-48, 2024.
11

---

Published as a conference paper at ICLR 2025
Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courty. Unbalanced minibatch optimal transport: applications to domain adaptation. In International Conference on Machine Learning, pp. 3186-3197. PMLR, 2021.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Tevgen Redko, Antoine Rolet, 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 attp::/jmmt http:///mmooo//////////eee/////t wtgg/apprs//22/ 20- 20-451 451.htll.
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large-scale optimal transport. Advances in neural informalion processing systems, 29, 2016.
YoonHaeng Hur, Wenxuan Guo, and Tengyuan Liang. Reversible gromov for sinulation-based inference. SIAM Journal on Mathemalics of Dala Science, 6(2): 283-310, 2024.
gromov--mong" monge sampler
Soheil Kolouri, Navid Naderializadeh, Gustavo K Rohde, and Heiko Hoffmann. Wasserstein embedding for graph learning. arXiv preprint arXim:2006.094 2020.
Lemin Kong, Jiajin Li, Jianheng Tang, and Anthony Man-Cho So. Outlier-robust gromov- wasserstein for graph data. Aduances in Newral Information Processing Systems, 36, 2024.
Weijie Liu, Chao Zhang, Jiahao Xie, Zebang Shen, Hui Qian, and Nenggan Zheng, Partial gromov-wassrrttiin learning for partial graph matching. arXiv preprint 2112:2201..11222, pp. 115, 2020.
Xinran Liu, Yikun Bai, Huy Tran, Zhanqi Zhu, Matthow Thorpe, and Sohcil Kolouri. Ptlp: Partial transport Ip distances. In NeurIPS 2023 Workshop Optimal Transport and Machine Learning, 2023.
Haggai Maron and Yaron Lipman. (probably) concave graph matching. Advonces in Newral Information Processing Systems, 31, 2018.
Facundo Mémoli. Gromov wasserstein distances and the metrie approach object match- ing. Foundations of computational mathematics, 11:417-487, 2011.
Facundo Mémoli and Tom Needham. Distance distributions and inverse problems for metric measure spaces. Studies in Applied Mathematics, 149(4) (4))9)) 1000,,00,,---000000 2022.
Caroline Moosmüller and Alexander Cloninger. Linear optimal transport embedding: prov- able Wasserstein classification for certain rigid transformations and perturbations. Infor- mation and Inference: A Journal of the IMA, 12(1):363 389, 2023.
Luca Nenna and Brendan Pass. Transport type metrics on the space of probability measures involving singular base mcasures. Applied Mathematics & Optimization, 87(2):28, 2023.
Liang Pan, Tong Wu, Zhongang Cai, Ziwei Liu, Xumin Yu, Yongming Rao, Jiwen Lu, Jie Zhou, Mingye Xu, Xiaoyuan Luo, et al. Multi-view partial (mvp) point cloud challenge 2021 on completion and registration: Methods and results. arXiv preprint orXio:2112.1 12053, 2021.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. waasesssssn averaging of kernel and distance matrices. In International conference on machine learning, pp. 2664 2672. PMLR, 2016.
Filippo Santambrogio. Optimal transport for applied mathematicians. Binkāuser, NY, 55 (58-63):94, 2015.
12

---

Published as a conference paper at ICLR 2025
Meyer Scetbon and Marco Cuturi. Low-rank optimal transport: Approximation, statis- tics and debiasinng In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: //openreview. wtt.r//wwwwe.eeeetoorddddddadaaa het./forunidd<bblleeaA..
Thibault Séjourné, Prançois-Xavier Vialard, and Gabriel Peyré. The unbalanced gromov wasserstein distance: Conic formulation and relaxation. Advances in Neural Information Processing Systems, 34:8766-8779, 2021.
Karl-Theodor Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. ar preprint urXiv:108. 120..0434 2012.
Hugucs Van Assel, Cédric Vincent-Cuaz, Nicolas Courty, Rémi Flamary, Pascal Frossard, and Titouan Vayer. Distributional reduction: Unifying dimensionality reduction and clustering with gromov-wasserseiin projection. arXi preprint ar arXiv:2402.02233 2024.
Titouan Vayer. A contribution to optimal transport on incomparable spaces. ar preprint (xXi:2011.04444 2020.
Cedric Villani. Optimal transport: old and new. Springer, 2009. URL attps://wwr
cedricvillani.org. httpe///eee/iieeee...eiae///////
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Wei Wang, Dejan Slepčev, Saurav Basu, John A Ozolek, and Gustavo K Rohde. A linear optimal transportation framework for quantifying and visualizing variations in sets of images. International journal of computer vision, 101(2):254-20) 259-269, 2013.
Fang Wu, Nicolas Courty, Shuting Jin, and Stan Z Li. Improving molecular representation learning with metric learning-enhanced optimal transport. Patterns, 4(4), 2023.
Zhengxin Zhang, Youssef Mronch, Ziv Goldfeld, and Bharath Sriperumbudur. Cycle con- sistent probability divergences across different spaces. In International Conference Artificial Intelligence and Statistics, pp. 7257 7285. PMLR, 2022.
13

---

The space of measures (2((R can be endowed with the two- awo-Wasserstein metric W2, and the resulting space defines Riemannian manifold (see, e.g., (Villani, 2021)), which is referred to in the literature as the Wasserstein space. Under the Monge mapping assumption, consider μ P2(R)) and let (an denote the corresponding tangent space at μ. that Published as a conference paper at ICLR 2025
A BACKGROUND: LINEAR OPTIMAL TRANSPORTATION DISTANCE
Then, each tangent vector E Tan,(P2(R")) can be regarded as is, v Fd + R2d such that
1u0l22())) = |[(x))] dp(x)) < co.
Given u (2(R), suppose 7 = (id T) an optimal transportation plan for W2(n, v). Then, the logarithm mapping is defined by
P2(RR) PVE By (T- id)= Tan, (P)
(26)
and the resulting image Uy is the so-called Linear Optimal Transportation (LOT)
embedding (Wang et al., 2013).
The LOT embedding b, is "reproscntation" of the measure v and encodes the optimal displacement from the fixed mcasure μ to v. Indced,
( v) = ||e, - 01
In general, given two probability measures v v² E P2(R2), if 7²,, are optimal solutions for W2(u, v"), W2(u, v²) of the form (2), one can use the following so-called LOT distance to approximate the original OT distance W2(v², v²) (Moosmüller & Cloninger, 2023):
LOT (v), U
l|a, uyz ")2)
(27)
The above definition relies on the Monge mapping assumption. In (Wang et al., 2013; Moosmiller & Cloninger, 2023), the authors generalize the LOT distance without the Monge mapping assumption; however, in what follows, we will avoid such an assumption.
First, we discuss the notion of geodesic in the classical OT setting, Suppose y an optimal transportation plan for the OT problem wetn μ,, v E P2(R)). Then, the geodesic from ju to v defined by
t 72 = ((1 t)ıx + t
(
(28)
Remark A.1. In the particular case where y is of the form 7 = (idXT) #1, the above formula reduces to
t ((1 - t)id + :T) Remark A.2. In the discrete case, μ Σ p,o,, and Σソ gog By abuse of notation, let 7 (u, be interpreted matrix. Then, the above geodesic becomes
(0st$l)
8111)a.4t0 Ti
(0$15)).
Given curves {yy he] the beto. both originating from μt, claim they are equivalent if there exists O such that for all & [0,e], & = 7/. Let G₁ denote the set of all the equivalence classes. The generalized tangent space at μ. denoted by Tan (PR()))) is defined as the closure of G₁, (see (Beier et al., 2022) for details).
Now, given 2 v² E P2(RR), let 72,7² 2 be some optimal transportation plan in 1 (w, v²)) (",,,2), respectively. We define the following distance, defined on the space Tan (Rd), as the LOT distance conditioned on ? ,1,7
inf [ 11v2 (1, LOTT(UE, ;1 (,))) Jer("'
(29)
where T(r', (2::):ppp==)))))) = (n P(R3d) (mo1) = n², (TT2) 22}. where To Te n. .22) (t, maa (2, (1)) (2
14

---

Published as a conference paper at ICLR 2025
Remark A.3. When 7² (id T #1, 22 = (id x T3) # for some mappings T T there exists only one element in , : (4), which is (id x T x TT. Thus, the right-hand side of (29) becomes
|| (x) TT))-T())))
(30)
That is, (29) and (27) coincide.
Finally, to formulate distance that is independent of the optimal transportation plans rt, 72: we define the LOT distance between 2² u² with respect to μ by
LV v) == inf LOT3(v v (
(31)
(ae") (e
The above LOT distance is complicated to compute. To simplify the computation, (Wang al., 2013) roduues the "barycent.rie projection" method that will recall here.
Barycentric projection.
First, we review some basic concepts in measure theory. Given 7 E P(TR2d) with #1#7= = μs where सy R2dd Rd is given by x (z, y) = z, by the disintegration theorem (sce, for e.g., (Ambrosio et al., 2005, Thm 5.3.1) and (Dumont et al., 2024, Theorem 6)), there exists a p-a.ee uniquely defined family of probability measures (7(-1=)) C C(RR)) such that
J ((z,y)dy(E,
fed /e ola.))dd(wlz)dd()))
VΦ E (RR
(32)
In this paper, we call r(11z) the disintegration of with respect to its first marginal (p), given x (for each supp(u)).
The barycentric projection map Ty Rdd + Rdd of y is defined by
/ Ilv 1lv- v/12 d'(0'(x') [ d/
Tx(x) = arg min yEY
(33)
Note that the second equality holds since the distance between y, y/ is simply the quadratic Euclidean distance. In the third term, we have a vector integration.
Given optimal transportation plan ? I' (p,
define i. == (T7)#11
Proposition A.4 (Prop. II.4 (Beier al., 2022)). I ( then the transportation plan induced by the barycentric projection map Ty, denoted as 7 == (id x TT) is optimal for the OT problem W2(u, By))
In addition, i/ = (id #1 salisfies the Monge mapping assumption, then Ty- T p-a.e and is a Monge map.
Thus, if we replace v by Vy, the OT problem Wz(H, (4) can be solved by the map Ty. Based on this property, given vi, v2 E P(RR), consider optimal transportation plans 7 e I' v )² E T(u, v²,, then define the following approximated LOT distance (aLOT)
to estimate W2(u ,2)):
( ;12:1)====
inf er (r,'" "er (a.e2)
D,,3, 7,
inf
||T/1 - TT==>11
(34)
r'E (
er (M,
TTy Tap 2=1(22(m)
(35)
Note, in most of the literature, (35) is referred to as LOT,, and for simplicity, it approx- imated by any pair of optimal transportation plans ?7).
15

---

Published as a conference paper at ICLR 2025
B BACKGROUND: LINEAR GROMOV- WASSERSTEIN DISTANCE
Let X C. Id be a compact and convex subset, and consider a Borel measure j on X. A symmetric function 9x X - R with fx 9x (xr ddy < oc is called gauge function. In this poper, without specific description, we default set 9x to be continuous (thus, Lipschitz continuous) For erample 9x (z, = x²11 or 9x (x, ) =xxx' The space = (X, (x.P). P) is called gauged measure space (gi--ppace), which can be regarded as generalized version of an mm-space. The GW problem between two gm-spaces X, is:
The space of all gauge functions
denoted as L e (X02,
X.
//xxx) lax gy (v. //)
(x, = inf gEL(U.) (xxx)02
Lemma B.1. There exists a minimizer yy of GW Y) in T(H,))
The existence of minimizers of GW(X, Y) could be shown by standard compact-SNEss argument, see for instance, Lemma 10.3 in (Mémoli, 2011). Suppose is one optimal solution of the above generalized GW problem. The geodesic between X and is defined by
t + . = (X Y1 t)gx + +gy [0.
(36)
Note, even if gx. gy are metrics, "it is a gm-space (rather than mm-space), and this is the reason mm-space generalized to gm-spaces in (Beier et al., 2022) and in this paper.
Two gm-spaces X, Y are "equivalent" if GW3(X, Y) = 0. Let [X] denote the equivalence class of X. The tangent space at [X] defined by
L Eyym x m13)
Tang
(37)
(x)
X are reprosentatives of k L (x11)22 (22) E L2 ((x))82 (12)) we say that ki ~ k2 if there exists 7 E T(XI, x2) such that GW(X1, x2) = 0. (We refer to (Beier et al., 2022) for more details.)
where, if Ty (X., ,xx,,"))) The T
(X2 gx2,,,,
(X y dx. "x,7"), xx (X Y2, dx,?3 ?²) where 71,7² are optimal transportation plans for GW (X, Y GW Y2,, respectively, it is straightfor ward to verify
Given spaces X
GW(X, x') = GW xx) 0,
thus X X E [X].
In addition, choose kn L (X (4 ()2)) k2 ((X2)82 (72))2), then we have k1, K2 E Tang,
where I (T Tk2) is same to [" ,2) in (x!,x²) Their inner product distance is defined by
(21 =
inf
||k - K211200
gET- (Te,
Now, we set 1s = kG, = grl - gx 12 = kyp = gr² - gx. Thus, the linear GW distance between y1 and Y² given 9², defined by the above inner product distance. That is,
NGW(Y',Y,;, x4 == (Kk 1:2)
inf 7Er* (Th, Tkg)
l|k k2 122(
/
inf
ly ,. -rr((1 12 )
( ( (XxXXxyaje
(38)
16

---

Published as a conference paper at ICLR 2025
(mx,)1) ( 22}. The third line follows from Proposition III.1 in (Beier et al., 2022) (or equivalently from the identity (49) in the next section). Note, under Monge mapping assumptions, 7' = (id uu,
where I('', ;2: == { x X x xY9)
(id x 4M, I() ,2) { x T x + and the above distance (38) coincides with (7).
The original Linear Maanoov-asssesttein distance between Y and Y with respect to X is defined as
LGW(Y', Y2:)= (X:
inf LGW Y2 (2;
(39)
C LOT/LLGW/LPGW EMBEDDING WITHOUT MONGE MAPPING.
In this section, we bricfly discuss the linear transportation embedding under lincar optimal transport, linear Gromov Wasscrstein, and lincar partial Gromov Wasscrstein setting. In summary, the formulations of these embeddings do not rely on the Monge mapping assump- lion.
Linear OT embedding without Monge mapping. Given probability measures v2,2² P(2), and reference measure μ E P(2), where Q I& is non-empty set. Choose optimal transportation plans nt (T, E (H,,")), the linear OT embodding 26
can be generalized to
v' D' = 7
(40)
where the conditional distribution (+(x)) can be treated "random mapping". When
y²= = (id T 4W,,, it is straightforward to verify T T'). That is, the embedding (26)
coincide.
We define the "distance" between two such two random mappings T T via:
1 - 11 : = y inf llv =2 (orr('''))d dd(())
(41)
From (29), we have
(VT = [eercor 11 -²2 321,(1, v..""' 1²)
I inf
11 - -
| 12 [[
Linear GW embedding without Monge mapping. Similar to above formulation, = (Y+, gya, ""g,,v2) v²) and reference gm-space x 9x, p), where μt y/ v² are probability measures. Suppose y', ?²,72 are optimal trans- portation plans for GW Y GW Y2) respectively. Then the embedding (5) can be generalized to:
given two gin spaces YI (Y1 (Y",gr,,,"))
1 xx,x'' + (gyn (1, 2)) (n (110))
(42)
Note, similar to LOT, when y = (id x T #/, we have f' = T!. That is (5), coincide. Similarly, we define the "distance" between two embeddings h 82 via:
22 (((0)
= /
inf xx (l)) (1a))())))))
dd) (/x)d/ (=')d (x,2')
(43)
17

---

Published as a conference paper at ICLR 2025
From (8), we have
LGW(W, Y2; Y x)
inf 19r (v', ,y4) - (y² -rz 322 ,²²)²
inf
(or -r= , 22 (30)))00000"0000000000 ("",)"" 12')))
x2 Ser (1l),
|| - 122
That is, the distance between two embeddings coincides with the LGW distance between two gm spaces.
LPGW embedding without Monge mapping. Similar to above setting, given gm-spaces X. YI Y² and suppose ,1, are optimal transportation plans for PX Y!), PGW, W2), the LPGW embedding in general case is defined by
E² = (k2 Aho == (u")02 (7)1) Y E
(44)
Note, when the Monge mapping assumption holds, (13).(44) coincide.
The distance between two embeddings is defined as:
(²) = inf #S
||A2 k.- (l(aaaa + >(hi 17x12 - 2/12 2 hat h21)
(45)
We have
LPGWW X)
inf (eT'(o",u''0 (X2)*xx²)
1661 (v',8")) "2" v'r") """ v2,
A(12212 + 1
/Se. (4
inf A/?
inf per(y' (11)))))))))))) Er (11=)))))))
ba 1.(())882)
+ A(1x'
InX 2 +
112-1121 +h + 1nx1 - -2
1n
D(E F²)
That is, the distance between two embeddings coincides with the LPGW distance between the two gm-spaces.
D COMPUTATIONAL COMPLEXITY OF LPGW
Computational Complexity of GW and PGW. The classical solvers for the GW and PGW problems are variants of the Frank- Wolf algorithms (Chapel et al., 2020; Bai et al., 2024).
Consider metric mcasure spaces X and Y, with measures given by μ = E pròz. and = En uu respectively. To achieve an e-accuraee solution for the GW problem, the number required iterations of the FW algorithm is
max 2L, 2 n² mmm (2(
2
18

---

Published as a conference paper at ICLR 2025
and for PGW is
2
max 2h, 2min(p. [q]) n²m max
2²
Here, L1 is a value determined by the initial guess 70 used in the FW algorithm and Cx C are the corresponding cost matrices for X, V. Note, since the largest value for À is 2A = max(2(C** (2, P,2((")) the above two quantities coincide.
In each iteration of FW, we are required solve an OT/POT problem, whose complexity is On + m)) (Bonneel et al., 2011). Thus, the theoretical time complexity to solve GW/PGW is O nm(( + m)n?m²).
Given K mm-spaces, Bi....X,, then, computing their pairwise GW/ WWGPWW distances re- quires (5) O nm(n + m)n²m?). Meanwhile, computing the pairwise LPGW distances
between them roquires only
KO ( nmmn + m) + +m²m² + K
O(mB). )
(46)
where the term (nn)) represents the time complexity of computing the distance between two embeddings, and no denotes the size of the reference space. In general, we would like to set Vi to be the mheanmediann/ //e/iia/mmaximmm maximuum of the sizes of K mm-spaces, and thus, this term can be ignored compared to the first term.
Remark D.1. We generally impose a fixed limit the maximum number of iterations to be used in the FW algorithm (e.g., in PythonOT (Flamary et al., 2021), it is set to 1000 by default). In practice, this maximum number of iterations is generally not achieved. Hence, un-rigorously speaking, we can think of the complexity of GW/PGW as being (0mm(n+mm
E PROOF OF PROPOSITION 2.1
E.1 CLARIFICATION
Although statements (1) and (2) in this proposition are not explicitly introduced in (Beier et al., 2022), they are implicitly mentioned, for example, in Proposition III.1 of such article. Thus, we do not claim the proofs of statements (1) and (2) as contributions of this paper. Additionally, to the best of our knowledge, the statement (3) has not yet been studied. We present the related proof as a complement to the work in (Beier et al., 2022).
F.2 CONJECTURE AND UNDERSTANNDING
Regarding statement (3), conjecture that this conclusion can be extended to the case where 9x and gy are squared Euclidean distances. However, this statement may not hold for other gauge mappings. In our understanding, for general gauge mappings, achieving similar result to the statement (3) would require defining a generalized barycentric projection mapping that is dependent on the specific gauge mapping.
The formulation of a new barycentric projection mapping based on the chosen gauge map- ping, as well generalized version of statement (3), is left. for future work.
E.3 PROOF OF PROPOSITION 2.1: PART (1)
Proof in a particular case. We first show the result in a simplified case. In particular, suppose > satisfics the Monge mapping, i.c. 7 = (id T) where T X + Y. and
7d = (id x id) E (* X). Then k,p = 0 and thus
LGW (X, xxx,,",77 = bka 1,01|2 = |ky 12,0
(XXY)82 19x(2, gr
=GW(X, Y).
19

---

Published as a conference paper at ICLR 2025
Proof in the general case. Consider 70 E (X, and y E -(7,,
We claim the following lemma
Lemma E.1. Choose 70 (X, y" E M Y), for each y I(7", pp) we have the followsng identily:
[ Joxxaanee 1x(xx - gy (y, (g(10)))))))))))))000 ,))),, (x² 22 w'
= -xxunja - (v.1/))
(47)
Proof of Lemma (E.1). Since
1 [xxxX (ex(xt,2" -xx 0,
GW (X,
we have
gx (x x²1) 9x(xx 0, 70 a.s.
For convenience, let x1= = X2 = X be independent copies of X. We have:
(,² f [ 1ex(x - gr (v. 3/ d2 x 2²), (2² x (v.z/))
= 19x
,xxxxxx"") -x
+ 9x(x" xx')²"))== - or (2"", ((0" "2""""""""""" 22) (y,
-Jxwwayy Vin 1ex (02 ex(x* ,It1) gx(x* (x) , gr (0,0))²
de (xyixxxxa ")), (03 )²1) d(2")) 0z (at, x²))))
(48)
- -Jouxesjo U/ (xx(=",a")) gy (w, 2 (11 wn') (02 (02,021))
((1") (()" (x
[ - (Xixy)02 1ex(x' ,01) - gr (y. // d 82 ((a' vi),),, (a", x²,)
- 1xx(x, - pr (w.. | ((r, (2'.1))
(49)
where (48) (H the disintegration of y with respect to (xx 70.
Based on the identity (47) and the fact 7tt is optimal for problem GW(X, Y), we have:
LGW (X, Y; 7,7")
inf >er("",>*) ( inf GW(X, Y) >r"()",>")
|dx (xxx=,,="0 dr (v. 2/) 82 (( xx), (x "0), (v.1
-G Y),
and have completed the proof.
E.4 PROOF OF PROPOSITION 2.1: PART (2)
In this case, 7* = (id x 44, for each x E Supp(u), we have that the disintegration of y* with respect to its first marginal (xx)#7" = 7x,, given first component x,
(xx''))) = 5(-2 TTx)),
20

---

Published as a conference paper at ICLR 2025
where d is the Dirac measure. Thus, for all x E supp(u)), we have:
Ty- (x) ((())=]( / yd / y dō T(x)) = T(:).
where the last equality holds from the fact T(x) supp(v) C Y. Therefore, T-- = T a-a.s Since TH = U, we have Byg = (T 1 Tap = v.
E.5 PROOF OF PROPOSITION 2.1: PART (3)
E.5.1 PROOF IN THE DISCRETE CASE
We first demonstrate the proof in the following simplified discrete case: Suppose gx (z,x²) x' x' and (y = y y', and consider
Σ P5OKIT
Σ
g
with Σ p.
Σ 9k-
In addition, we suppose that X, Y are compact convex sets which contains 0 (besides containing (fI, and f, Mm respectively).
Let 7* (X, Y) be optimal transportation plan. Then, the corresponding barycentric projected measure is given by
1
D = Vy = Σ Pedge
where Ti ==
pi 5=1
By convexity, Vi...., Jn E EY Thus V = W,- = DX)
Then, it induces a transportation plan 7* = diag(pl, ... p%) E 1RTx" with first and second marginals p and D, respectively. We will show that for any transportation plan 7 E ((u, holds that
C S C,
where
11
C(xX,, Σ
(a) xy 23 yy reriess
=1
in other words, we will show that 7'' is optimal for GW(X, Y) First, we notice that (7+)-1 = (lag(1/pi.... 1/p.). Then, set
7 := 7(=) 117" E Raxm.
Secondly, we check that y v), In fact, let p (PI,.... PP.. 9 = (q1,..., qm) be the vectors of the weights of finite discrete measures and v, respectively, then, since 7 Im and 5"d In, = q, we have
7lm = 7 T = (r ",)
=
1,
1 = p.
Lastly, we compute the costs follows:
m7
C()";X,Y)=
Σ
(o) ) +
Σ 1 2 Σ Σ
(x] x (v) By Mi
=1
1,47
= J1 - 2
4 xv MN3 uy Yi5
21

---

Published as a conference paper at ICLR 2025
where J1 = Ei (2, (x, P.pp + Ei yy) Pagy is independent of y By the multi- linearity of the last term in the identity, can show
-)
X, = J2- -2
(a (e
We
1,²=1 8,0==
11
Té5Uy y
(50)
- Σ
TV
Pe
De
j5'=1 1,1=1 8,t'=1
J2 J1 +
where J2 Σx, -1 (x, xv P'pp' Ei.e= (ee We Prpp.. Similarly, we can compute
C(1; YY = J2 - J1 +1 C(:
(51)
The optimality of y" together with identities (50) and (51) implics that C(7: Y) z C))
E.5.2 PROOF IN THE GENERAL CASE
Similar to the discrete case, given 7"h (X, Y), the barycentric projection is given by
Ty- [ y d (y/xr)
We have that 70 = (id Typ H is a joint measure with first and second marginals μ and V. = By.. = (Tx-) HM, respectively. The goal is to show that 7 is optimal for GW(X, Y) where Y: := Vy = (Tz-)
Let 7 E ((,, be an arbitrary plan. Let 7(222) == (+)x(=21x) denote the disintegration o with respect to given that the first. component is x, for each x E Supp(u). Similarly, we adopt the notation 7 (=2/z) for each x Supp(u).
We define the joint measure
7 := 7
(52)
on X xY. In particular, the above notation means that for each test function & E Co xY), we have
Jr Xxy ((2,))d7(E.5) Jruvxxr 2(z.v)dr (yl2 (x" dd" (z. V)
= ((ole.o)aaral))) dF (=
d5 (x.0)
22

---

Published as a conference paper at ICLR 2025
For any test functions Øx Co(X), or Co(Y) we have
Sear (x()))((x,)) = / XXXXXXXX (x D)
Xxx (x(x))((z,))
x ox(x)dp(x)
Jswr (r(U)d7(1,0) XxxXxXX (v)) yd7 (x ( (1. 1)
JxxYXx or ()
JKw or(y) (ul=))dd
xxx
XxX (x
J (r(u)du())
Thus 7 v)
In addition, we observe that we have the following property that holds for the case of considering inner products:
Lemma E.2. Suppose X C Rdr.Y c Rd are finite-dimensional, conver compact sets. Let y E M4(X Y) and define Ty as (9). In addition, let gy (y(y)') aly. v'), where (v.1) + (y.3)) = ==
> y.yl is an inner product (the standard one, for ezample). Then for each x, x' E X, let y= TT (x)) = (x(x), we have:
gy (..7) YxY gy (v. V/ (d
(53)
Proof of Lemma E.2. For each [1 dyJ, we have:
J vlild((ul)) / ('1/)))(1)))
J s/ 31 f ulll 1
JxY M M
where the third oquality follows from Fubini's theorem.
Thus,
dy D
By (7.7)
ubl (1
XxY
= =Jr Eu(tv/iii
-Jry gx ox(1:11)
23

---

Published as a conference paper at ICLR 2025
Now, continue with the proof of Proposition 2.1, part (3). We have
C(""X,,)) = [ J(KANIE 1ox(x, gr (o0
(2d
-11 2') 2')l + (.. -
(xxx)o0 //xxxxex gx 20) (v. v)d (a', 3/
11 2g -
(54)
where J1 = =111xx1 1111xl12 + 11a [ir is independent to y- Similarly,
x
[ (xxy)02
(z, vd)
=11ax ([aa) + 11g (2:00)) - (xxx) (x(x,21) dor (7. V)) (2. (o'.8)
J2--2 f xx(xx (Ty: (x), Ty. (x' (2'))d((
(55)
J2 2 f
reo ex( 1 or gr (u (wlz)dr ( (1)) du(x))d(az))
(56)
J2 /
(xxx)a2
= J2 2 (7*)82)
(57)
where in (55), J2 = (1 2 2) + 11or (-1, 12) (2):2222))) (which is independent of 77"); and (56) follows from Lemma E.2. Combining (54) and (57), we have
x C(>"; Y) J1 + J2.
(58)
Similarly, we can show that
= = J1 J2.
(59)
Also, similarly to (54) and (57), we have
Cl1; X, Y) = J1 - 2
(60)
C(7; X, W)
-2 - 2((gx 7002
(61)
It remains to show
(gx = (gxxg,,79 702).
(62)
24

---

Published as a conference paper at ICLR 2025
Indeed,
10xgr,70% Juxames
I 0x(x,2²) /
(177
X
(63)
[XXXXx - (x( Tx-
of (1
- (x(2,0") 2')
(2" (77"")7777"" 1F
(64)
-I (x
9x (x, x'
1g (y. (1)
(XxY)02
where (63) holds since given V, theprobability measure (-101))) is only supported on {s" X: =T,- (x²)), similarly to measure 7-117);; (64) follows from Lemma E.2 (that is, from equality (53)).
Combining (59), (58), (62) and the fact C(r";X, Y) S C(; Y), we obtain that C(F;; X, Y) C(7; X, Y) which completes the proof.
F PROOF OF PROPOSITION 3.1
Consider gm-spaces X, Y1,
17,y7 Y2 and select 7 E
Y²). Inspired by
the LGW distance (38), propose the LPGW distance (conditioned on 22) (15) in the general case:
LPGW (2x,,,,
inf serg (29)) (Xxx) + A( 1
loni - 21)
(65)
where
(Tx.Y
Next, discuss the proof of Proposition 3.1.
F.1 PROOF OF PROPOSITION 3.1: PART (1)
In this section, we discuss the proof of statement (1) of Proposition 3.1; namely, we prove the existence of minimizer to the LPGW problem.
First, we introduce a series of lemmas.
), Lemma F.I. Given Radon measures μ, vt v², and nt E v"), x2 eTs(u, v2), then
is sequentially compact set.
25

---

Published as a conference paper at ICLR 2025
Proof. The main idea is similar to the proof in, e.g., Lemma B.2 (Liu et al., 2023). In It is straightforward to verify that this sequence is bounded above in total variation (since 7 and 72 are finite measures) and that it is also tight sequence. This verification is even simpler because X, Y and Y are compact. Thus, by Prokhorov's theorem for signed measures, the closure of ['s(>", (in the weak topology) is weakly sequentially compact in MMX Y x x²).
particular, consider a sequence (?²) C Txxxx(1xx
It remains to show "=(7",>2:P4 is closed.
Suppose y" "I MM x Y x Y2), for cach nonnegative test function & E C(X x Y!), we have
lim /
6(0, (orrv")(((xxx)))) (,,,"") lim XXViXY2 - (1r,y))d((z, .22)
6( Mx,y")d>"(un (x,
[d>"
xxx1
= S o(x, ((xx)))))))))))
That is, (TX,Y11 #7 "x (πx,Y=))7. By Lemma B.1 in (Liu al., 2023), we have (xx,1)#77 S 7t Similarly we have (Tx,Y*) 3.
Thus, Y (=(7,,22:/) and have completed the proof.
Lemma F.2. Suppose yx,9r are conlinuous functions (see assumption (3)), we cluim that the mapping
(X x 8)82 e ((x,1), (x', ./))) + 19x (2, (u,''')) IR
is a Lipschitz function with respect to metric
Dxxy((x, u), (z', v/)) = (x( x') + dr (v,
Proof of Lemma F.2. Let the mapping in the statement of the lemma be denoted by T. For 21,21, 22, 2/2 E X, vr, vi,vi U2, 1/2 Y we have
x ((11, 21) $((22, v2). (1/2 1/2)11
= (x x1) - gr (y,, 21)2 (xx(22, x/2) - gr
(V2, gy gr (vn, v1) (x x²2) gy (11, s/
11
< (2),
+ (12, - gr (un, s/1 - 1gx x/4 gr (u2, 19
< K (lgx (2), x1) - 9x (x2, + (or v1) - gr 322))
(66)
= K2 12) + dx (x + dy (v/, V2) + dy (0/ v221
(67)
where (66) follows from the fact that the function rı + |rj - r2| 2 is Lipschitz on a compact set (sce, e.g., Lemma C.1 in (Bai et al., 2024)), and K₁ 2 0 is its Lipschitz constant. Then, (67) follows from assumption (3) for gx and gr, with K₂ 2 0 being the maximum their Lipschitz constants.
Consider (7*) c , such that
(lgr) - grzl 2X, (7
inf (lrr - 2 - Terg(T (w))
-0,, 002).
By compactnoss of ( 1=:
72:14 (see Lomma F.1), we have that there exists y" E [s(>), 22:1) which is sub-sequence limit of 7" (in weak convergence).
By Lemma F.2 and Lemma C3) in (Bai et al., 2024), we have
(gy) |r2 - 2X, (2)) TET (
inf
(lgy) - grrl2 72)
Thus, 7"h is a minimizer, and we have completed the proof.
26

---

Published as a conference paper at ICLR 2025
F.2 PROOF OF PROPOSITION 3.1: PART (2)
Proof. Under the Monge mapping assumptions, we have
r { x T x )p v A
1
Thus, (65) becomes
LPGW Y2; x2
inf [ lgr (z), (r ||
+122 - x T T 4
M'StEAnX x82
inf /
(c), (r:
(T: +/00)++1021 212/13)
"'STXAA3 Xxo
= =(14).
and we have proven the statement.
F.3 PROOF OF PROPOSITION 3.1: PART (3)
Since x, Y are compact, by continuity (see (3)), we have that 1y1,, gyz are bounded functions.
By Lemma E.2 in (Bai et al., 2024), when 2A > max( ".''"") (r" ))))),,))))))))))))))))))))))) pick any optimal
7 TET
{(id T x T ) : 4l S 7 ^ )x
have hy| min(m''l. 1-2 min(m hx Thus y (id x T x T # A ^3
Plug in
this optimal into the LPGW problem (14) (or (15)), we obtain
LPGW 12,,, ,,;
[1grr gy> P. (7x 7 102 + A(p2
2 |/212 - 2hx A x213)
= <(Mii 1= (1x A 7x) 82 x(w2212 + |u212 2/12 A 12
and we complete the proof.
F.4 PROOF OF PROPOSITION 3.1: PART (4)
First, under the Monge mapping assumption, an optimal PGW plan of the form x" =
(id T) 7X for some 7X μr, have
|| 11 (12((11))0)) + A( - hx1 + hal)
=/ X
- gr (To)) A(I132 - (7 2822 -13)-()))82)
= (X,).
In the general case, we first introduce the following lemma.
Lemma F.3. IJ T E Tx (X, X), then (πx)*7 = us, ( = p.
Proof of Lemma F.3. Pick any 7 (X, X), suppose |y| < lpl. we have
C,y; X, x, = xx (xx(x, gx (x x (dy + X(2/u12 -2/113)
2 2 2
0.
(68)
However, (X, X)= 0. Thus,y is not optimal.
27

---

Published as a conference paper at ICLR 2025
By the above lemma, have 1/" I 17%]. For each E I ,=<>">>";p) from (Bai et al., 2024), there exists 7 E I ss y²) such that (Tx,Y) = =7" and 7 S 7. Thus we have M1=h"
Let
X(,:X,,,,Y))) = JIXXXXYYO (x(xxx)) gr (u, ((x,, ((x, (x,, (v.))) (1.)))
+ +|mp - -
and similarly we define C(r': x, X, A). Then
:(y;X,,,,,,) -(,;X,X,
- -xxxxxryo 119x(,, - gr (v. (y.88)12 22] -0) (x,)
0.
In addition,
C,,
gr = (v),:)))=-v(,))))))))))) (( ((x, (x. x'), (v. + A(1112 + +|012 2//113)
- - -(xxxy0
(v ( = PX,)
A0 + 1/12 -2/>"1
where the second equality holds by (49) and the fact |>| h- Thus, we have
LPGWA Y; 7,, >²) s Ch'; Y, A) (X,
Another direction is trivial since for each & E [g( 7'; (m2 = (πxx) (s( v). Thus
PG Yin) S C(;;, Y, S LX ,',,
and have completed the proof.
F.5 PROOF OF PROPOSITION 3.1: PART (5)
This section discusses the proof of statement (5) of Proposition 3.1. That is, discuss the metric properties of the proposed LPGW distance.
F.5.1 FORMAL STATEMENT
In this section, we set gY = di. Let
(== (Y,9y.u)
where y C Rdd for some d E N such that. Y is nonemply convex compact set; v E M+ with 2 (Igrl) < co.
Then VY1 Y² E G, define Y1 2² iff GW(Y1, Y²) - O. By (Mémoli, 2011), in this case, optimal transportation plan GW GW(Y1, Y²) is induced by the Monge mapping T. Furthermore, T is bijection v -a.s. and is called "isomorphism" since
dy (v), /n dy (T(x)) T(y")) aa.s.
Next, given G' C we introduce the following assumptions:
Assumption F.4. For each V E G', the problem PGWx(%, (X,V) Y) admits a unique solution.
28

---

Published as a conference paper at ICLR 2025
Assumption F.5. For subset G', define K1, K2 by
K supllu, V (V,gr, E g)), (y 8')1 Y= e))
K2 supl max v. Esupp(v)
We suppose K1, K2 < oo.
Assumption F.6. ,y,, are induced by metries. In particular, gx gx(:)))
(:
(y- = dyn().)))) (5)), (x-) = (ta(+.), where dx metric defined in X, 2 1, similar to dy1,dy2.
Remark F.7. The uniqueness of optimal transportation plan assumption (F.4) is also intro- duced by (Nenna & Pass, 2023) to prove the triangle inequality linear optimal transport. The assumption (F.5) discusses the bounded total mass and transportation cost.
Proposition F.8 (Metric property of LPGW). Fir X E 9 and for each Y we select Y' x Y
) E ( Y²). In addition, set gx dx.9r dy where s 2 1. Then we have:
(1) The LPGW distances (15),(16) are nonnegative:
LVG X2, LFG YY;X) 2
(69)
(2) The LPGW distances (15),(16) are symmetric:
LPGW YY;K ,,, LPGW Y 12,,,,,,7,.. (PGW(YY,Y''
LPGW XY:)).
(70)
(3) The LPGW distances (15) satisfy triangle inequality. In addition, under assumption (F.4), (16) satisfies the triangle inequality.
(4) Under assumption (F.6), if LPGW x2 = O, we have Y ~ 3/2
Similarly to LPGW X2XX).
K1, and 2A > K₂ + (5) Under assumption (F.5), suppose |p| Y?, where K1, K2 are defined in (F.5). sup (usppr/()upp(r) 19x (z, x2) and Y Then there crists 7 ,22 such that LPGW(W,, X ,,,)) = LPGWA(W) x2;)=
Therefore, under the assumptions (F-4), (F.5), and (F.6), have that (16) defines a metric in /¹l
Note, the above statement implics the metric property of LGW by sctting À oo. We refer to the next section for details.
F.5.2 PROOF OF PROPOSITION F.8: PARTS (1), (2), (4), (5)
Proof. Choose Yl, Y.,Y g.
(1), (2) It is straightforward to verify the nonnegativity (1) and symmetry (2).
(4) Tn this setting, have:
0 LPGW x2:
/
inf reTg(r (:) (xxxy I (v', ..''"" ) gr- "PP""""))) 12 2/1l)
Pick one corresponding minimizer 7, we obtain
J lgr .. gy> 2
29

---

Published as a conference paper at ICLR 2025
and
1 + |122 -2/y/² = 0.
2/7/1²
Thus 7 E I(v2, v²) and therefore
GW(Y', y²)= = O.
That is Y Y
By a similar process, if T.GGW (V), Y2:X) = 0, we have VI ~ W2
55) Since Y ~ Y2, from triangle inequality of PGWA(:))) :), we have PGW Y-) PGWA(X, Y²).
In addition, there exists bijection mapping supp(u*) - supp(u²) such that gyn gyn (x1, 5x, (())) ut such that Txu = v².
Pick 7 E 1 (x, Y. Let 7² = (id x T) that is, for each test function ó Co(X Y
(()) = / XXXYI o(a,T(o"))
We claim 7² optimal for PGW ,Y),
(R1)# = ( S 14
(#2)#7² T4 (( # > v²
since (πy)# Sv¹.
Thus, 72 e (T, In addition,
c()2; Y²)
= -fxxxije ((xxrjje (x((e,z)--0r((((( (o))===r((T")),))xx)/xxxx)))))") + Alaa +122p2-2171 -
-1xxxysee - -
")'d' (
+ + |1d - -117111)
(XxXIj8 19x(xx gyb (y' ("''""")(((t))"""(...." """"""""''''"000)) yn
+ -
(71)
= (X, PGWA(X,Y3)
and thus 72 is optimal in PXW
Since 2λ is sufficiently large, by lemma E.2 in (Bai et al., 2024), there exists optimal 73 such that:
hn min(1u), wo')) |/'1.
Thus we have h- = 1 |o'l = 112 Plug 7,, 7 into (15), we have:
(PG ,2,
= / or gva gr>
v
0.
(72)
F.5.3 PROOF OF PROPOSITION F.8: PART (3)
Notation Setup and Summary Choose n2 E (², E n (x,
(%, Y³) the goal is to show triangle inequality in this section:
IPGWA Y. LPGWA 19; LPGW, (,,,,,,,,,
(73)
30

---

Published as a conference paper at ICLR 2025
Related Lemmas
Lemma F.9 (Varient Gluing lemma). Suppose 7 E "(,,""), E((,, E ((2, probability measures. Pick 2212 E I''', -2:1), ;2; y E I( (ip)), ET(' 7
there erists 7 E P(X x X x y x yd) such that
(Tx,YI, #7=" (mx, #7== -22.3
(74)
Note, if we set X = {0) and == da, the above lemma becomes the classical Gluing lemma. (sec c.g. Lemma 5.5 (Santambrogio, 2015)). For this, we call the variant gluing lemma.
Proof of Lemma F.9. For convenience, let X y be independent copy of X, y3. By gluing lemma, there exists y E EP(((X x yI 22) x X') such that
(+) - y1.. (Tx,x)) #7 = (id x id)
(75)
Apply gluing lemma again between 7' and 71.3, , we can find 7" E x x V8) (X' 22 y²() such that
x
(#x))**x)))==) (Tx 7233
Applying 7 (4)) we complete the proof.
Alternatively, we can set
= y xr2 yra va x ((x)
and it is straightforward to verify y satisfies (74).
Lemma F.10 (Triangle inequality for LGW). Suppose X, V1, Y2, ys are under the balanced GW setting, choose 7² E T (T, ))?? E 1 (2, 72 E (p, we have
LGW(Y) Y M x2) < LGW(Y,, X (2) + LGW LGW(Y,, ,9;
(76)
Proof of lemma F.10. Pick the y from lemma F.9, we have
#7x,N1 (πx.Y1) =71, (mx,y) #7x,y= 2 7²2
Thus (Tx,,1,)=) 1 Then we have
= -lor - grvl" (n 1.2 12)622112 1/2
s (ler- - 3 ((xx.)t.2))77)89))
(77)
1/2
- gr= 1
(v "",, ",) (,"),(""11))) (
(lor (Frararay
gyr (0- + -yBl (3² gr 2 07.02)
1/2
( (1 - gr- (r> )²
1/2
(
dr
1/2
-Vrrrrra (10r2 2 gr ,31)² dr
(78)
LYW(Y!) NOWWYYYYY,,,,... LGW N.CWWe?,'',... (
31

---

Published as a conference paper at ICLR 2025
where (77) follows from the fact 71,2 is optimal in :(7',>2:1) (78) holds by the Minkowski inequality. In the uniqueness assumption (F.4), we have
LGW(Y',Y2:2) s LGW(Y' Y LGW(
Convert LPGW to LGW sition 3.3 in (Bai et al., 2024).
The main idea of this step is similar to the proof of Propo-
Notations Setup
We can redefine ,'
( MM y x X x X2) (m12) S (F3,)))) 5 (#13) = (id x id) # n S u}.
(79)
We define auxiliary points Sop 501, 502, dog and then define
X X U (obu):
ÿi y U (ob1, d02, do3):
82 = 22 U 1601, 602, 6os),
y y U f0b1, 602, doa).
and
81 72 + h So0 + 15010 E MM+(8 x 82),
52 = 7² + h 20. + 17 10 E MM x 82),
43 70 h 00 1 S0 EM+ v.)..
Define
(2r f Y
g4. (v,, ,
clsewhere
and 992-9re Iys are defined similarly.
Finally, define
Dx(11,2) = [ In - r2l
if rf E R clsewhere.
IVA
Let X = (600) to be copy of set X. Then,
set
,(01,92:1) = (+ x pl X (T12) = , ( =43
(80)
(T1,) 1x (id ( H sp).
(81)
Consider the mapping:
F: (r') 7::0 + i(7) .2:14)
+ (7) (m1,2) 7) 8 )( + )(0. @ 20² (Ta,4) + (7)6 (os))) 1 (600),
(82)
By the following lemma, we show that F defines an equivalent relation between the two sets.
Lemma F.11. The mapping F defined in (82) is well-defined. In addition, it is a bijection if set the identily 6on 2o1 602 dog.
32

---

Published as a conference paper at ICLR 2025
Proof of Lemma F.11. By (Bai et al., 2022, Proposition B.1) we have for each y I(y). p),,
(TL2) = 32 ( =
In addition,
(Mi.)) (m. ((T1)TT' (TT) 2 8 + dz @ (( (171 8
Thus,
( Ix (TT = (id x (T))
where (T I (#1)#7* $ ,4 and we have F is well-defined.
It remains to show F is bijection. For each 9 E f (+') 52) and we define mapping
F (2 + +' (,
(83)
+ 1xx1xxxX2
remains show F-1 is inverse of F. First, we claim F- is well-defined. Pick y E f(71, (2), by Lemma (Bai et al., 2022, Lemma B.1.), we have (mx,r1) S (ma,)) S 2p
In addition,
(MI (T1 # 1x (id x id) #
where 1l p. Thus, (f) (T 72: 1u).
In addition, it is straightforward to verify F (F(r)) 7, 47 E ( then complete the proof.
is straightforward to verify:
(Dilori.9-a By., )(2)) = (lgrr rr A(17'1 - hn/3)
Combine it with the above lemma, take the infimum over T($1,52: P)),), we obtain:
(equivalently, over
inf (D (22)) 5ET(31,925)
inf (e (3))
(lrr gyz 2 62 X01 +1221 1 1nl3) )
= LPGW(YY' Y;: 1 ,?2)
where the second equality holds from the fact | 1221 = | = = 1 1 Similar
identity holds for LPGW(Y) y3,x, 7²), LPGW ( Y3, Y 79)
Verifying Inequality Tt remains to show
inf (Da (2))))) < (E(()))599))
inf 5p)
(p;
inf 7 202))2/2 7Eñ(59599)
Pick 712 E 2 that is optimal for (D2 J52; 7 1/2 Similalry, pick optimal 113 Pe(7- 2 E Ts(?2,7²), construct the corresponding optimal g1.3 E T(G (,, E T ;3;
Thus, by Gluing lemma, there exists E (XXXXXXX)) (Xx Y2) x (X (X)) such that
(T(12),(5.0) 92.3
(T.)))))))))))444 = -2333 Now by the definition of i'6' (00 1), (1;,,",);;;)))) we have
(11,5) (id id) 4 (Ta.5) (id id) #/
(84)
(85)
33

---

Published as a conference paper at ICLR 2025
for some radon measures pl, p= μ. Thus, we have μí = n² S μ. Therefore, (mi3) (id id)
In addition,
(#1,2 (T1,2) 5 = 9/1
(Ta,4) ( =9 -72
So (7 :pp)) Therefore, we have
< $ (KK(ky,, 822 1/2 kys)),
where the second inequality holds from (Bai et al., 2024, (57)..
G RELATION BETWEEN LPGW AND LGW
Theorem G.1. Suppose |l| = | = 1 =1 and x,z is bounded, gyi,gy? gyz are continuous function.
Choose sequence An + co, i is sufficiently large, we have Xa, then
LPGW (Y Y2: LGW,, (Y-, Y2;)), aLPGW A., (V Y2 (Y' Y2;X).
Proof of theorem G.1. By the lemma F.1 in (Bai et al., 2024), when n is sufficiently large, in particular, when
An M
sup y ErY
1gri(y),u"))
8² y Er²
for each 71 E (X, v.), b-|
min( (1-1) =1 That is
F T (X, Y2) I (X, Y!).
Similarly, when n is sufficiently large, we have I n (x, Y2) = 1 (X, Y?).
Pick 7/ r (X,
Y (X, |ua| 1, the mass penalty term vanishes in (65), thus we have
(X, y²), E (X, I (X, Y2), since h = |1| = 1
LPGW (Y), Y2;
LGW(Y) ,
Take the infinum over all y 2² and the take limit for n xc, we prove
LPGW A. (Y), x2:x) LGW
Similarly, in this case, g0 = 0
LPGW Am (L,,, X 72) + A(hidl + h²) = LGW(Y, 7, & Take the infimum on both sides over 71 72 and take An J0, we obtain aLPGW x2:x) aLGW (x), x2x)).
34

---

Published as a conference paper at ICLR 2025
H PROOF OF THEOREM 3.2
H.1 PROOF OF THEOREM 3.2: PARTS (1), (3)
(1) Similar to proof in Theorem 2.1, in this case, we have Ty. -T, 7x a.s.
(3) Based on statement (2) of Theorem 3.2 (see the proof in next section), we have
7", 7 are optimal solutions for PGW W,,), PGWA(X, V,a) respectively.
By (1), we have 7 T2t T i A 78 -a.s.
a.s. Thus, we have:
LPGWA(Y 12;
[ bdy (T' (11,, ( *
inf MY X
122p - 21p2
[
inf wExxMm X
(1) + M1,.1111 + 10 - -2)
1(102122 1uge -
1/ X02
inf WSA
-
+ A(12,112 |0 211013))
+ Alvill + 11)l
(86)
-.PGWA W,
x, 7 72) + 1(1xal++ball
+ hal3)
where (86) holds since
D = T = -1 (अv) S Sv¹ Thus |2 1012 (vl)02
lndl: and similarly we have 1
h22--
H.2 PROOF OF THEOREM 3.2: PART (2)
H.2.1 PROOF IN THE DISCRETE CASE.
Notation sctup
We first demonstrate simplified proof in the discrete case. Next, will provide the proof of the statement in the general case.
Suppose
Σ /
== Σ bilj
PiTti
1=1
==1
Vr, E X, Vy.y' EY. Choose 72 E (X, (x,Y), Y), we obtain the corresponding barycentric projected measure:
9x xx = TT x', 9x y v..
i = Wy. =E 9.t with
Vi [1:n]]
(87)
j=1
if q 0, elsewhere.
0.
(88)
Then Y,,- = (Y,gr, D), 7t diag(@).... )a).
Our goal is to show 7' = diag(q,. .
④n) is
optimal in PGW V.
35

---

Published as a conference paper at ICLR 2025
Pick 7 E (p. == -T (H. 2), similar to section E.5, we set diagonal matrix (5*)-1
as
1 if O 7 0,
(
0
elsewhere.
Let 7:=7(")~~ E E Ruxm Let 7x = y and Ty == y 1n-
In addition, we set D = fi: q > 0}, and lD E R with 1nld - Vi e D and 1pli] 0 elsewhere. Then we have:
7 1-=))))11 =x S Po:
(89)
7 Ln (") 1, S (7))
= 1 S.
(90)
Therefore, 7x 7x S P. W S Nÿ S q. Thus, E <T'(p.))
Relation between PGWA(X,) Y) and PGW 9). Similar to (54),(57), we obtain
((,';X,,,A) ((x 2')2 82) + ((v y))² (75) + A(pp +1/ 1 -)
-2 1W=1 =1
C = ((x x') (7x) (2) + (1V '))², (++ 02) + +(pp=+++++ + - -17")
2
3:
where (a TT) = [< x4) [I..e( R (1x) 02 xT ((TTa'), (1))
(iv=r( x4) (1xx) e the element-wise dot product. All other notations are defined similarly.
Combined the above two equalities with the fact |r hyl and 7 = 7x, we obtain: x, X, X) + (07 77 )2)) - ((v T (7)) (75) + A(Ial2 - I7?).
= ;(
(91)
Similarly, from the fact 7x 7x (see (89)) we obtain
C(F A) = C(r; X, A) + (0 7) (fx) - {(y v'). (2)))2) + A(la|2 - -1@13). (92)
Thus
X(F"; Y, A) - Ci; (,
= =C(""; Y, A) X (07 ()77)),777)8 (fx)
Y,
1/)/1(((7))) - (2x)
< <(TTT) ( 82 (2) - T/) - (1r)
T De) (7)))()))))))))) (.8)) (rr) Σ (uJ u. - (93)
m
Σ
LEED
=1
The (ax) 2z) ((7))) (rr)
A'EDjf'=
w Uy 1 ((())))))))))))))))))))))))))))) - (xx))(())))
(94)
J-'=1
m
Vi - (o))))))))))) (()))))))))()))))))))))))))
Σ
V )2
((r)))))))))
SPEED
(95)
36

---

Published as a conference paper at ICLR 2025
where (93) holds since 7 is optimal in PGWA(X, Y); (94) follows from the facts Y S 78 (see (90)), and the fact
m
Yo
VV U/
0.
1/
Vi,
q:a.
j=1
and Jensen's i inequality:
7
Yo. W s (0) v)?
9:
j=1
11==1
The last equality (95) holds from the following: For each (j,j" E ml), we have
Mi Ty (GT))
q 4
Mij Rij (7))))5))) -67)))))
(fx (Tx) - -(x))(())
q q
iPED
LPED
where
=
Σ
क J/
4:9
IPED
Σ 1PEDD
Ri
Σ Mij
Σ Vei
=0
-
IED
FIED
Mi Vi.s
B
Nr. Fiv
Tk'
1PED
k,k==1
k,k==1
The Th.
7k
D k,
k =1
iED
SED
Ik. T/ 3 R Yo
Σ
9 9p
A.ED k,k==
and thus we complete the proof.
H.3 PROOF FOR THE GENERAL CASE
H.3.1 NOTATION SETUP AND RELATED LEMMA
Suppose
x') agx TaaTTa 2',9r ar Va, E e,Y, x.
Choose E (X, Y). The barycentric projection mapping is
(x) = / y/ (g/12'), Ve e supp(u))
We obtain: D:= Ty. (Ty- * 7"' (id x Ty- au and V,r = (X,9r,
37

---

Published as a conference paper at ICLR 2025
Our goal is to show 7/ is optimal in PGWx Y). Equivalently, pick 7 [g((, D), need to show
x, - X, A).
Set y from (52):
7 = 7 7
We have y satisfics the following two lemma:
Lemma H.1. Choose Y E &T((u,)) E (g((,, Set (Tx))H then y defined in (52)
satisfies the following:
(a) 7 TETT((Tx)))
( (T
furthermore:
(#x)#7 = (mx)#π (TY)#7 (
(96)
(97)
(b) =" then y =
(c) Regarding the second marginal of 7, we have for each test function Φx E Co(X):
J (r())drr))) -octwwWw--xxwxrrra - (v))) (vlx dd (0).
(98)
Proof.
(a) Note, in a discrete setting, this statement has been proved in (89), Pick test. functions ox E Co(XX)) dv E Co(Y) with øy 2 O, we have:
(ox.7)= /
XXY @x(x))d((,1)
J I
(2"0 v)
S
JxXY (x(x))7(a,))
[ (x(x)d(x(())
( f
XXXY (r(2)d7(I,1)
- I (r()))d")))))))
Jaw J. (r 10
-f XxY (y(w)dt""wl")ddds(
= J (r(())t(())
where the inequality holds from the fact Fy E 77.
38

---

Published as a conference paper at ICLR 2025
(b) If = y, pick Cu(X x X), we have:
XXY J / (1x,)) (0000) (0,7)
S Jow J J ola.
xxxY
Sx / ola - )x)
Jaw (v
Sxxx (x.1)dd7(x,1)
(c) It follows directly from the definition of y.
H.3.2 RELATION BETWEEN PGWA(X, Y) AND (XWA(X, V). From (60) and (62), we obtain:
Y, = C(>"; Y, + (5) )02) (op (18) + A((1)2 - (0)
(99)
C( C(::X Y. A) (0) (2) (op (mx) -(1p//- - -1713
(100)
From (99)-(100), obtain
C(F" A) ((,; =C(""; Y - C(T; X, Y, A)) + (07) -1)))))))00)8))))1111 (3,))))))))))))) (g), (Tt) 02 (ir) 02) - (0p, (7x) 82
78 82)
(101)
where (101) holds from the fact 7 is optimal in PGWA(X, Y). In addition, pick J. 77' E supp(Ht), then for each x E (1lp)) x' (splp("((>ll')) we have:
ÿ -= = (x-
Thus,
A = Socrnee / xee (Tx Tx. (z (2"))))((
(o.7))
From Lemma E.2 and Jensen's inequality
(Tx (I²), T (x
= ( gr (v. v ddy (w/2 ddy (V/1 " 1aro)))
(d)=")dr*
< / 2 (v. d'' (yl (d (y' (
Combined it with the fact 77 S ty (sce Lemma H.1 (a)). we obtain
A [ ((xxy)02 / xe2 of (u.v')d (v1 (ul=:))))))))))))))))) ydy" (v')=>
(1" (($)) (2 -2 ((.,)"),(v.1''))
= (ot, (77))99 1rix (7)) (172)002 (5x )02))
(102)
39

---

Published as a conference paper at ICLR 2025
Thus, continue bound (101):
(101) I (0): (7 ) (7 ((7)) -(xx) - ( (18) - 788
= (gy, (7 xix (7
82
(Tt) )02 (02)
XIy
B1
(gr, (gr,(())))) (,x)) (7 ) X (Ty) 002 (yx) )82)
(103)
P2
where B2 = 0 from lemma H.1 (c) and B = B2 from lemma H.1(b). Therefore w, we
complete the proof.
H.4 PROOF OF PROPOSITION 3.3
The proposition is directly implied by definition (20) and Proposition 3.1 (3).
I SPECIAL CASE: LINEAR MASS- CASSTRNNST PARTIAL WAAMOV-WSSSRSTEIN DISTANCE
In this section, we introduce the linearization technique for the "mass-constrain"" partial Gromov- Wasserstein distance, which can be regarded as a special case of the proposed LPGW distance.
Mass-constraint Partial Gromov- Wasserstein distance is defined as:
inf yEr (1.2) J 19x x') gr (u.
MPGW (X, (X, Y)
(104)
where [0, min((u), |v- is fixed number.
(u, = (y E M+ x x): (Tx)#7 S n. (TY)#7 S su111= nt.
We use (X, Y!) to denole the set of all optimal transportation plans.
Consider the following gm-spaces X = (X, 9x, (xx,4) 14), Y = (Y gr grrr v²), Y2 = (Y², (y2, v²), given 7) E [0, min([="), and we suppose |x| n). Choose 72 r (X, )²,, E r Y²).
Suppose the Monge mapping assumption holds and let T,,7" be the corresponding trans- portation plan. We define
kyg (1, + dx (11, 2) dy ((()
as linear MPGW embedding of y2 given 72. ky, is defined similalry.
Thus, similar to (15) and (7), the linear M-PGW distance between Y Y?, given 73, is defined as
LMPGW, (V), x2x = |ki. hyya 12
(105)
and similar to (7),(15) the general case without Monge mapping assumption is
I
(F
inf n (xxx) lax 02
(106)
where (2(7).?2:)) = (r M4 Y x Y (Tx,r S (Tx,)=)= S 21
7) And similar to (10), by applying barycentric projection Tai, Tx2, we define the approximated lincarMPPWW distance as follows:
aLMPGW,
WY (Y), Y2:X)=
inf MMP + (2,5)
(X,
inf (x,x)) x (x,
bd (z)) (a=))ddy=(TT((e) 11 (x)))))))) (107)
Similar to theorem 3.2, we have:
40

---

Published as a conference paper at ICLR 2025
Proposition 1.1. Choose 7' E (X, e r (x,) " Y²), have:
(1) linear MPGW embedding of Y can recover MPGW discrepancy between X and Y! i.e.
k 11 MPGW,(x).
In general, we have:
(X, = (X, 4y E _ X).
(2) If Monge mapping assumption hold for 7 ,², then [[06),(15)) coincide.
(3) 9"' (id Ta. #1 is optimal for MPGW, (X, Yy)) GW (X, )
(4) When X is sufficienlly large, we have:
LM PGW, CON,W,,Y" (Y,,)YY11))) (2; LPGW (Y) Y2 - A(122/2 + (1122-2177) aLMPGW, (Y", ,Y2;) = aLPGW> Y²:X) 2(1e112 + ||212 2n1²)
(5) If |u| = - |ua1 - = =1=1, LMPGW, v, LGW coincide and PLM aLGW coincide.
Proof.
(1) If Monge mapping assumption holds for y", i.c 7" = (id x #) we have:
MPGW,(X,Y) J(xrr xx((xxx)) - gr v/ d(7))0
||, 11,02.
Without Monge mapping assumption, pick 70th E (X,, since 17 = 17= = =14|, we have 70 IH,, Thus
= I (xxxxx 19x(x, - (x., (x(==,,")))/((()>>>>>"""""" ==)))(()9))0== (X) G)(X,X)
Therefore 70 (X,
Pick Y E 1 (7)))" ((("),"))((("">>"))) by (49), we have
Jxxxxsy/00 (xx gr
=/ (XxY]e2 (x, gr v') 02
MPGW, (X, W ,,,7)
It holds for all 7 E (>'""",""), thus
LMPGW, Y; 7 MPGW, Y*).
(2) Under Monge mapping assumption, we have 7 (id x T | 72 = (id x #1" for some mappings T T2, where μL, S μ. Since |4'| = ||0"| = 17 |pl, then we have μ1" = p² = J.. Thus,
T - ((id T x wp' p¹
u4, |4'| -
=((id x T x T T [1)
and we have (106),(105) coincide.
41

---

Published as a conference paper at ICLR 2025
(3) Since 17 lp|. we have |ااق| = |r2 17= |pl, thus
1 (1, By-1) = I(,, Byy))
Thus, MPW,, (x)) y. Since 7* is optimal in MPGW, Y) (X, Y), from Proposition 2.1, we have 371 is optimal for GW Y,1) MPGW, (x, 1,1 and we complete the proof.
(4) Since X, X,Y', are compact, by Lemma E.2 in (Bai et al., 2024) when À is suffi- ciently large, for each 7 E T (XX,, x² E - x (X, Y2), we have | = h
") |p]. By Proposition M.1. (Bai et al., 2024), we have 7²,7² are optimal for MPGW, W²), MPW,, (x, Y²). That is
r ( Y C T (X, ,
& X Y T (X,
For the other direction, pick 7 E r - Y), 7 E e S Y!). Thus |/| 17, and we have
= - (x((222)-99 gr " d()))) 02 + 71m1 + +12112- - -2n²²
(xx(2, -o)" + >111|2 + +1o212 -21²)
= -O(Y/X, ,)))
= PGWA V!)
Thus, 71 E 1. (X, Y)).
Therefore,
", (X, Y²).
Pick 7 E T (X, (') - (Z) Y2), we have ,;X,,'
MLPGW, ,2,,,, ;²) LPGWx =
- A(1='1+ 10 1 20²))
Take the infimum over all 9,,72 we obtain
MLPGW, (Y), Y2XX) = LPGW x2;x) A(12112 + +1221=- -202)) Similarly, we have aMLPGW, (Y), X² = aLPGW> x2;X) - 1(K22 + 1122122 2273) (108)
5 In this case, we have 1 [2 v² = I(u, (1, 2² I(u, 1²). Thus
Y (X, Y2) = r (X, Y2).
Thus LMPGW, LGW coincide, aLMPPW aLGW coincide.
NUMERICAL IMPLEMENTATION OF LOT, LGW, LPGW DISTANCE.
LOT distance In previous sections, introduce LOT distance (31), aLOT distance (34)
and its approximation formulation (35). Their relationship can be described as follows:
LOT distance (31) is proposed to approximate OT distance.
aLOT distance (34) is proposed to approxiamte LOT distance.
42

---

Published as a conference paper at ICLR 2025
(a) Shapes in ellipse dataset.
(b) Reference spaces.
Figure 2: In the first figure, visualize the ellipse dataset (Beier et al., 2022). For cach cllipse shape C Rax2 we normalize the scaling of the shape such that mex;,e ( - X :] 1. The sizes of these shapes range from 90 to 650. In the second figure, we visualize the reference spaces. In each shape, the color represents the value of the probability mass at the corresponding location.
43

---

Published as a conference paper at ICLR 2025
Formulation (35) is proposed to approximate aLOT distance.
However, in practice, it is not a multi-layer approximation. The distance LOT (31) and the distance LOT (34) are only proposed for theoretical completeness and are not computation-
ally feasible. In practice, formulation (35),
|T Taa ([[)))
is used to approximate OT distance between v² and 2² and in most of the reference which cite (Wang et al., 2013), (34) is refereed as LOT distance, the original formulation (31),(34) are not mentioned.
A similar convention adapted LGW and LPGW.
LGW distance The relation between LGW distance (39), aLGW distance (10) and its approximation formulation (11) can be described as follows:
LGW distance (39) is proposed approximate GW distance.
aLGW distance (10) is proposed to approximate LGW distance.
Formulation (11) is proposed to approximate aLGW distance.
Similarly, it not a multi-layer approximation. LGW distance (39) and aLGW distance (??) are only proposed for theoretical completeness and are not computationally feasible. In practice, formulation (11);
loy (7)
is used to approxinate GW distance.
LPGW distance The relation between LPGW distance (16), aLGW distance (20) and its approximation formulation (22) can be described follows:
LPGW distance (16) is proposed to approximate PGW distance.
aLGW distance (20) is proposed to approximate LPGW distance.
Formulation (22) is proposed approximate aLPGW distance.
Similarly, it is not multi-layer approximation. LPGW distance (16) and aLGGW distance (20) are only proposed for theoretical completeness and are not computationally feasible. In practice, formulation (22).
1gr (Tx) (1), Tx2())) (T==((x>1)).......> (1) + A(k2 + - -2hx 7 )2)
is used to approximate PGW distance.
K DETAILS OF ELLIPTICAL DISKS EXPERIMENT
In this section, we present the details the elliptical disks experiment.
Dataset and numerical setting details. The dataset we used is the ellipse dataset given by (Beier et al., 2022), which consists 100 distinct ellipses. Each cllipse is represented as x 2 matrix, where ranges from 90 600. For reference shapes, 2D shapes, including disks, squares, triangles, and others. See Figure 2 for a visualization of the dataset and the reference spaces. In this experiment, each shape is modeled with empirical measure Σ 1.2.
selected 9 different
Performance analysis
We present the results in Table 4. As mentioned in the main text, LPGW is significantly faster than PGW, as it requires only N 100 PGW computations, while PGW requires (>) computations. Furthermore, we observe that for some reference spaces (e.g., Ss, S7,
44

---

Published as a conference paper at ICLR 2025
PGW
8g
8g
84
Sg
S7
%
Sg
points
time (mins)
45.34
0.86
3.8
3.08
0.66
0.63
1.43
1.89
2.1
0.69
0.05
MRE
0.1982
0.6263
0.1428
0.6315
0.4732
0.1454
0.0394
0.0793
0.0245
PCC
0.5774
0.5741
0.5884
0.5584
0.6514
0.7698
0.9303
0.8711
0.9944
time (mins)
43.86
1.02
3.33
3.55
0.34
0.99
1.25
1.29
1.33
1.22
MREE
0.1941
0.0205
0.0198
0.0245
PCC
0.5781
0.5738
0.5881
0.8581
0.8741
0.993
0,9962
0.9954
0.9949
time (mins)
46.97
0.76
3.78
3.13
0.08
0.62
1,56
1.91
1.98
0.71
0.1
MRE
0.1941
0.1264
0.1431
0.25-12
0.0538
0.0411
0.0205
0.0198
0.0215
PCC
0.5781
0.5738
0.5881
0.8581
0.9871
0.993
0.9952
0.9954
0.9919
time (mins)
0.74
3.68
3.02
0.08
0.61
1.89
0.5
MRE
0.1932
0.1262
0.1428
0.2542
0.0538
0.0443
0.0205
0.0198
0.0246
PCC
0.5779
0.6737
0.5879
0.8683
0.9871
0.993
0.9952
0.9953
0.9949
Table In the first column, the values 0.05, 0.08, 0.1, 0.5, represent the selected À values. For each Å, the first row shows the wall-clock time for PGW and LPGW. The second and third rows display the MRE (mean relative error) and PCC (Pearson correlation coefficient), respectively.
8g), the MRE is relatively lower. Morcover, for most reference spaces, including S7, Ss, and Sg. LPGW admits PCC greater than 0.85. Finally, when À is larger, the PCC tends to be higher, and the MRE is lower across all reference spaces, discussed further in the next section. These results highlight the importance the choice reference space, as commonly the case for linear OT-based methods.
Relative error analysis Given vA, A,v2 v DK and reference measure μ4, the relative error is defined
PGW(VV,V)) LPGW PGW(v),))
MRE
(109)
K
Remark K.1. For numerical stability, when À is small (i.c., x 0.05, 0.08). remove the NGW/LPGY' distance whenever PGW < 10-10 since 10-10 is the tolerance in the PGW algorithm. In this case, PGW Rs 1 10-10 and LPGW 1 1-10-11 which renders the relative error uninformative.
We decompose this error into the following four aspects:
The transportation plan induced by LPGW may not necessarily be the optimal transportation plan for the PGW problem.
In practice, i. These two measures can be distinct, especially when the optimal transportation plan is not generated by the Monge mapping.
the barycentric projected measure & to approximate s for each
The solvers for both PGW and LPGW rely on the Frank- Wolfe algorithm. Due to the non-convexity of these problems, the Frank-Wolfe algorithm may yield a local mininizer instead of global one. Therefore, the computed PGW transportation plan might not be optimal.
practice, we approximate the original LPGW distance (16) (or (10)) using the approximation formulation (22). This introduces gap between the real LPGW distance and the approximation.
is important to note that the first issue arises from a theoretical perspective, while the remaining aspects are due to the numerical implementation. The first two errors are also present in other lincar OT-based methods (Wang et al., 2013; Cai et al., 2022: Bai et al,, 2023; Beier et al., 2022). The third issue stems from the non-convexity of GW/PGWV affecting both LGW and LPGW similarly. The final error is specific to LPGW due to the approximation formulation used.
45

---

Published as a conference paper at ICLR 2025
In practice, several methods can be employed to reduce these errors. For example, the dataset can be represented as empirical measures with equal mass at each point. This approach is effective for unbalanced linear OT techniques (e.g., (Bai et al,, 2023; Cai et al., 2022)), as these methods do not require mass normalization. With high probability, this will result in Monge mapping, reducing the second error. Additionally, to minimize the last error, as stated in Theorem 3.2, using a higher leads to lower error, and when À is sufficiently large, this error becomes zero.
MDS visualization and analysis. We visualize the multi-dimensional scaling (MDS) embeddings for both PGW and LPGW with respect each reference space in Figure 3. We observe that when À is large (i.e. À = 0.1, 0.5), LPGW with reference space S5, Se, S7, Sg. Sg admit similar patterns. When
0.05 or À 0.08, we observe LPGW with reference S7, Sg, Sg and PGW admit similar patterns. From this figure, observe that S7, Sg. Sg admit better performance than other reference spaces.
Summary. Although LPGW methods subject to potential errors, the high PCC ob- served between LPGW and PGW (when, e-g., the reference space is S7, Sg. suggests that LPGW can serve good proxy for PGW, rather than simply approximation.
46

---

Published as a conference paper at ICLR 2025
= 0.05
(b) 0.08
A= 0.1
(d) À
Figure 3: MDS visualization for À = 0.05, 0.08. 0.10, 0.50. Each subfigure shows the MDS visualization for PGW and LPGW based on different reference spaces, In each figure, the first subfigure in the first row is the MDS visualization of PGW.
47

---

Published as a conference paper at ICLR 2025
L DETAILS OF SHAPE RETRIEVAL EXPERIMENT
Dataset details. We test two datasets in this experiment: 2D dataset and a 3D dataset. The vi- sualization of the two datasets is presented in Figure 4.
bone
goblet
Star
horseshoe
In addition, for each shape X {#1.... J, we normalize the scal- ing such that m | For the 3D datasct, we apply the k-means clustering to reduce the size of each shape to 500, from its original size 2048.
rectangle
traczoid
1.
(a) 2D Dataset
Numerical
details. We represent the shapes in each datasct mm-spaces X
airplane
gutar
skateboard
Fdd Il 112, Ek= We use o² ni to compute the GW/LGW distances for the balanced mass constraint setting,
compg
incompleee
For the PGW/LPGW set N. where N is the median mumber of points across all shapes in the dataset.
distances,
(b) 3D Dataset
For the SVM experiments, we exp(-oD) the kernel for the SVM model. Here, we normalize the matrix D and choose the best a E (0.001, 0,1, 8, 10, 100} for each method used in order facilitate a fair comparison of the resulting performances. We note that the resulting kernel matrix is not necessarily positive semidetinite.
Figure 4: Datasets for shape retrieval experiment.
Parameter selection for PGW and LPGW. The paramcter À for PGW and LPGW is chosen as follows. For the 2D dataset, we set such that À S Amaz = max, ((Ci)2 = 0.5, since all shapes are normalized to a scale of 1. We perform a line search for À over the set (0.2, 0.3, 0.5] and select À = 0.2 for both PGW and LPGW.
randomly select 2-3 shapes and compute the PGW distance between these shapes and the reference space. We find that Amaz 0.15. Thus, we conduct line search for À over the range (0.02, 0.03, 0.05, 0.06, 0.070.08, 0.080.1, 0.15) and choose 0.06 for both PGW and LPGW.
For the 3D dataset,
Reference space setting for LGW and LPGW. Similar the classical OT method (Wang et al., 2013), the ideal reference space should represent the "center" of the tested measures. In practice, we typically use the GW barycenter (Peyré et al., 2016) the PGW barycenter (Bai et al., 2024).
For each dataset, we randomly select one point cloud from each class. Specifically, for the 2D dataset, we select 8 shapes, and for the 3D dataset, we select 4 shapes. We then compute the GW/PGW barycenter between these selected shapes. The wall-clock time for this computation on the 2D dataset is about 10 seconds, and for the 3D dataset, it is about minutes. For fairness comparison, we apply the same reference space for both the LGW and LPCW methods in all experiments.
Nearest neighbor classification. Once the pairwise distance matrices have been com- puted between the shapes using each method, the computed distances for nearest-
48

---

Published as a conference paper at ICLR 2025
PGW
LPGW (ours)
bone
rectangle
trsperoid
horseshoe
annulus
boste
restangle
goaber
trapeteed
elar
herstoteed
diat
anmuii
bont
rectangle
goste
trapezmid
herserfire
disk
bone
vertangle
gobler
trapornid
elar
horstotone
disp
ansuttes
Zont
restangle
gabler
traperoid
harsedfoa
dist
Arnuits
(a) 2D Dataset.
GW
PGW
LGW
LPGW (ours)
airpiane
cabinet
guitar
skaleboard
pirplame
Cabinet
matar
slateboard
airlaane
canine
Buiar
Mareinard
Biplane
cabiret
gustar
skatetoard
sirplane
cabind
soaebiard
Dataset.
Figure 5; Confusion matrices computed from nearest neighbor classification experiments.
neighbor classification experiment. We choose a single representative at random from each class in the datasct and classify each shape according to its nearest representative. This is repeated over 10,000 iterations, and we generate a confusion matrix for each distance used.
Performance analysis. The pairwise distance matrices are visualized for each dataset in Figure 7, and the confusion matrices from the nearest neighbor classification experiment on each dataset are shown in Figure 5. Finally, the classification accuracy with the SVM experiments reported in Table 2. The results indicate that the LPGW distance able to obtain high performance across both data sets consistently.
From Figure 7, we observe that PGW and LPGW qualitatively admit more reasonable similarity measure compared to the other consid- ered methods. For example, the 2D dataset, class "bone" and "rectangle" should have a rel-
Ipgw
lgw
atively smaller distance than "bone" and "an-
Accuracy
300-
mulus". Ideally, reasonable distance should satisfy the following: 0 < d(bone, rectangle)
X2%-
d(bone, anulus). However, we do not observe this relation GW or LGW.
In the 3D dataset, the main challenge is the pres- ence of incomplete shapes, which represent only part of the corresponding complete shape and can have a large dissimilarity to each other. In observe that PGW /LPGW
2.30
Figure 6: We visualize the accuracy of LPGW for different. X. For each X, select the best a to compute the accuracy. We observe that when X > 0.08, LPGW and LGW have the same accuracy.
this experiment, admits slightly better performance. We sus- pect due the the unbalanced setting of these two methods, these two methods are more robust to the incomplete shape classification.
49

---

Published as a conference paper at ICLR 2025
CW
PSW
LGW
LPGW (ours)
bopcod)
poie
orspecee
survettee
oue
posior
goodes
aber
for
aid
(a)
2D Dataset.
GW
PGW
LGW
LPSW (ours)
Gatebcars
cxeveeren resiationd
erpaane
catinel
ine calleet
guisa
gotee
abyttend
retionel
qustis
guster
expraee
cantont iil
puttr
irc purte alaveiveed
anc crostican
inc.
(b) 3D Dataset.
Figure 7: Visualization of pairwise distance matrices resulting from each of the considered methods: GW, PGW, LGW, and LPGW (ours). In (b), the label Vinc. airplane" denotes the incomplete airplane shape class, and similarly for each of the other 3 such classes.
Note that in this dataset all shapes have the same size. Thus, when À is sufficiently large (i.e. À 0.5), LPGW can recover the performance of LGW. We refer to Figure 6 for visualization.
M DETAILS OF LEARNING WITH TRANSPORM-BASED EMBEDDINGS EXPERIMENT
Reference space. Similar the shape retrieval experiment, for each dlss/digtt we select one shape from the training set and compute the GW barycenter based the selected shapes. Note, in this slep, the reference space we obtain is (Mo E R pp)), where no N is the size of the reference space, Mo denotes the pairwise distance matrix, and pd is the PMF of the reference measure. Here, no, pd are inputs to the GW barycenter algorithm, and in this experiment, is set to be pd
set ng to be the mean of the sizes of the selected shapes, and pd n
However, My cannot be applied as reference space for the LOT method. Thus, we apply the MDS method for My and obtain the supported points X {af ......... xna of the reference space, i.e.,
arg min
[[(M))., - ||,, x,|ll? where x, = Vi.
We use (Mo. p., En 24) the reference space for LOT/LGW/LPGW. The wall-clock time of barycenter computation is 26 seconds.
Numerical details. Note, since the goal of this experiment is to test the performance of learning from embeddings under corruption by random rotation /flppping and noise, remove digits (5. 9} from the data since the rotated and flipped digit "2" is highly similar to "5". Similarly, rotated "6" is nearly identical to "9"
votation/flippnng
The classification model we selected is the logistic regression model as provided by the scikit- learn package. For the LOT and LGW methods, due to the balanced mass requirement,
50

---

Published as a conference paper at ICLR 2025
2
2
2
2
800
LOW
1P89
Figure 8: We visualize the interpolation between two shapes using GW, PGW, LGW, and LPGW. In the first column, the three shapes shown are the source shape, the target shape, and the reference space used in LGW and LPGW. The target shape, digit "4", is corrupted by the addition noise points, with a total mass of = 0.3.
normalize the PMF of all shapes the testing dataset. For LPGW, this normalization not applied.
Parameter sctting for LPGW. Note that in this case, the training data not cor- rupted. Thus, i. In this experiment, we set X = 40. In addition, to improve the computational speed of LGW CCW/P, the augmented training data obtained by rotation and flipping is NOT contained in these two methods since the rotated shape is equivalent to the original shape in the setting of GW/PGW.
set X Amaz max, C? where C2 is the cost matrix for shape
Performance analysis. The LOT method achieves 51.3% accuracy when 0. This indicates that even with the addition of rolated /aaued/fipped data the training set, the LOT embedding method struggles to classify the rotated digits with high accuracy. In contrast, LGW/LPGW achieve 82.5% accuracy, indicating that these two embedding techniques are more robust to corruption by ootationfflipiigg
When n) 2 0.1, the accuracy of both LOT and LGW drops to 10-20%. However, we observe that the LPGW embedding maintains strong accuracy between 70% and 85%. This demonstrates that the LPGW embedding is more robust to corrupted test data.
M.1 ToY EXAMPLE: POINT CLOUD INTERPOLATION
In this subsection, we select one shape from the training data and a noise-corrupted shape from the testing data (with rotation and flipping removed). We demonstrate the inter- polation between these two shapes using the GW barycenter (Peyré et al., 2016), PGW barycenter (Bai et al., 2024), LGW geodesic (Beier et al., 2022), and our LPGW interpo- lation. The goal to intuitively visualize the LGW/LPGW embeddings for the reader's understanding.
Our method and baseline methods. Let X be the reference mm-space applied in the classification experiment. Note, numerically, can be described by (C", X xx,p), where pd E R is the PMF; no is the size of p"; X E x is the set of 2D supported points; and CO0 = I| - X211 is the corresponding cost matrix.
That is, we can use (C".p") p") represent x Similarly, we use (O", and (C²,p²) to represent the source and target mm-spaces (shapes).
O is not required as C contains all the information of X in the GW/PGW problem.
51

---

Published as a conference paper at ICLR 2025
Now introduce the GW barycenter method. For each time E (0,1/6........... ..... ,6/6 1}, solve the barycenter problem
C = arg min ((1 CER"o Kno
(CC)
When t = 0, (C", pp)) and (C",p' represent similar shapes. In fact, if pd p² the two shapes are identical. Similarly, t 1, (C".p') is similar to the target (0²,p²) p²). For t (0,1), 1), (C", pO) represents interpolation shape between the source shape (C .p') and the target shape (C², p²).
The PGW barycenter method is defined similarly.
In the LGW geodesic method, let Σ= denote the barycentric projection obtained by 74 where is the optimal transportation plan for the GW problem between (C",p") and (C".") The numerical implementation the LGW embedding given by
= I1 5) Je.E(Lmoo noxoo
(we refer to (5) for the original formulation). Similarly, we can define the LGW embedding for the larget shape (C2, ,²), denoted as Eg R
Then for each i, the interpolation/
htt.olaaatiio/gooesiiii... geodessic of LGW is defined by
CO + +1 +t2
(110)
For the LPGW interpolation method, the numerical LPGW embeddings EG, E2 7 are defined similarly, and we refer to (24) for details. We use (110) for the interpolation.
To visualize these interpolations, for each C., we adapt the MDS method, and the solution X₃ E R is a point cloud. We visualize these point clouds in Figure 8.
Performance comparison. In this experiment, the size of these shapes is in the range of 200-250. GW SW/PGW requires 230-270 seconds, while LGW WLPWW requires 1-2 seconds. In Figure 8, we observe that the shapes generated by GW/LGW contain more noise points. Additionally, at times such as 3/6 and L = 4/6, the generated shapes are difficult to distinguish due to the noise points.
In contrast, the shapes generated by the PGW/LPGW methods contain significantly fewer noise points.
Note that at 1= 0 and / = 1, the shapes generated by the LGW /LPGW methods can be treated as visualizations of the corresponding embeddings for the source shape (C", ,p) and target shape (C), respectively.
M.2 OTHER BASELINES OT BT/CI /G//GW
Note that OT, GW, and PGW methods cannot be directly applied to this experiment since we use a linear model (logistic regression) as the classifier. However, we can adapt the kernel-SVM methods described in the shape retrieval experiment for this classification task as well. The primary distinction between these three methods and LOT, LGW, and LPGW lies in their computational complexity.
Suppose Nuain and Niett represent the sizes of the training and testing datasets, respectively. Let and denote the average size and dimension of all the point clouds digits. Addi- tionally, let N represent the average number of iterations required by the FW algorithms for GW and PGW.
The computational cost of these mothods is summarized as follows:
In methods OT and LOT, the term (n² + ndd) refers to the complexity of computing one OT distance, while nd represents the complexity of computing one LOT distance given two embeddings.
52

---

Published as a conference paper at ICLR 2025
Method
Training Process
Testing Process
OT
O ((eeran Grain
(n² n
O O(Nrain Noest (n² + +ndd)
LOT
O Nerain +n²++
O (n + n d) + Neett N train (nd))
GW
( N2 train
(n²N+)=d))
(
Nn + n n²d))
LGW
O Nirain
(n²N +
O (Niest (n²W n²ddd NN train (n²
PGW
(N train
(n (n²)))
( Nerain Nn² N n²)
LPGW
O (Ntrain N +ndd)
ONNestt ( (n n2d) + Nest Nerain (n²))
Table 5: Computational complexity of different methods.
Similarly, in methods GW and IGW, the term (n + n²d) refers to the computational complexity of computing one GW distance, and the term (n²) represents the complexity of computing one LGW distance given two embeddings.
The complexities for PGW and LPGW follow a similar pattern.
In this experiment, Ntrain 8000 and Nust 1000. OT-based methods require approx- imately 50 hours (2-3 days) to train the model, while GW and PGW require about 400 hours (over 15 days). In contrast, LOT, LGW, and LPGW take only 3 minutes.
N COMPLEMENTAL RESULTS MNIST CLASSIFICATION EXPERIMENT
Data reconstruction. We visualize the reconstrueted digits using LOT, LGW, and LPGW embeddings under two settings: data is not corrupted by noise points (n = 0), the reconstructed digits from all methods closcly resemble the original data. However, when 20% of noise points are added (n = 0.2), LPGW's reconstructed digits effectively exclude most of the noise points. In contrast, the emneddings produced by OT and LGW retain information from the noisy data. This demonstrates that the LPGW embedding leverages the partial matching property of PGW, ensuring that most of the noise points are excluded during the embedding process. This explains the robustness of LPGW embeddings to noise corruption.
and 1 0.2 (See figure 1b). When the
t-SNE. From the figure 9, greater separability than those of LOT or LGW.
observe that when 7 0.1, LPGW embeddings show
COMPUTE RESOURCES
All experiments presented in this paper are conducted on computational machine with an AMD EPYC 7713 64-Core Processor, 8 32GB DIMM DDR4, 3200 MHz, and an NVIDIA RTX A6000 GPU.
53

---

Published as a conference paper at ICLR 2025
LOW
lpgw
orig
0-0
n=0.1
n=0.3
n=0.5
Figure 9: t-SNE visualization of embeddings. In the first column, the label "orig" indicates the experimental results for the original testing dataset without random rotations /flips or noise. In the remaining columns, random rotations/flij are applied to the testing data, and denotes the total mass noise points.
54


Reviews:
[{"review_id": "Ylm0D0c8cB", "reviewer": "Reviewer_HYNr", "summary": "The authors propose the linear partial Gromov-Wasserstein (LPGW) embedding, a linearization technique for the PGW problem. Theoretically, they prove that LPGW admits a metric with certain assumptions, and numerically, they demonstrate that the utility of the proposed LPGW method in shape retrieval and learning with transform-based embedding tasks. They illustrate that the LPGW- based method can preserve the partial matching property of PGW, while significantly improving computational efficiency.", "questions": "I am not an expert in this area.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well organized and easy to follow.\n2. The paper contains many details, which is very helpful for understanding.\n3. The experiment is promising, justifying theoretic part.", "weaknesses": "I am not an expert in this area, I don't find weaknesses from my perspective.", "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": "kEB5ipdJ9J", "reviewer": "Reviewer_K3go", "summary": "This paper studies the linear partial Gromov-Wasserstein (GW) alignment problem. Specifically the paper extends ideas from linearized GW and partial GW, and combines them to LPGW which inherits the merits of both method and is applicable to wider tasks. To formulate, the paper gives detailed account for how to incorporate general measure instead of probability measures, and how to coordinate different marginals. Extensive numerical experiments are presented, showcasing better performance.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well motivated and the study of the proposed formulation is very thorough, covering both general and special cases under suitable assumptions. The proposed algorithm combines the advantages from both partial GW and linearized GW, and extensive experiments supports this extension.", "weaknesses": "1. The paper, though overall well motivated, is mostly combining existing methods and theoretical novelty is limited, with discussions following from the the original ideas and definitions of linearized/partial GW/OT. A further question: what if TV is replaced by a general divergence for unbalanced formulation as in [1]? \n\n\n2. Discussion of related works: the term \"linearization\" is from the tangent structure of gauged GW space as is first pointed out in [2]. Mapping based unbalanced GW formulations are also studied in [3],[4].\n\n\n3. Minor comment: \nIf the barycentric LGW is the version to use as in the second equality of (10), then this should be stated in the paper.\nNotation $\\gamma^1\\wedge\\gamma^2$ on line 260 seems to be incorrect and should be $\\inf_A \\gamma^1(A\\cap E)+\\gamma^2(A^C\\cap E)$.\n\n[1] Séjourné, Thibault, François-Xavier Vialard, and Gabriel Peyré. \"The unbalanced gromov wasserstein distance: Conic formulation and relaxation.\" Advances in Neural Information Processing Systems 34 (2021): 8766-8779.\n\n[2] Sturm, Karl-Theodor. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. Vol. 290. No. 1443. American Mathematical Society, 2023.\n\n[3] Hur, YoonHaeng, Wenxuan Guo, and Tengyuan Liang. \"Reversible Gromov–Monge sampler for simulation-based inference.\" SIAM Journal on Mathematics of Data Science 6.2 (2024): 283-310.\n\n[4] Zhang, Zhengxin, et al. \"Cycle consistent probability divergences across different spaces.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.", "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": "hZqx4PXWsw", "reviewer": "Reviewer_wRQx", "summary": "The paper proposes a modification of a variant of the Gromov-Wasserstein (GW) distance, known as the Partial GW (PGW) problem,  which enables to compare gauged measure (gm) spaces whose measures have different total masses. The modification consists of applying the linearization strategy proposed in (Beier et al., 2022) to the PGW problem, yielding the so-called Linear PGW discrepancy (LPGW). It is shown that if the PGW problem admits a solution that is induced by a deterministic map, then the LPGW problem recovers the PGW problem. For the purposes of computation, an approximated LPGW problem is considered. The paper concludes with some numerical experiments which exhibit the empirical performance of the proposed approach.", "questions": "1. Many results in the paper depend on the assumption that a Monge map exists. Can the authors comment on sufficient conditions for such a result to hold?\n\n2. Proposition 3.3 holds when $\\lambda$ is sufficiently large. Can the authors clarify this condition further in the main text? Moreover, if $\\lambda$ is too large, the regularizer dominates so there appears to be some tradeoff in terms of minimizing the first part of the objective. \n\n3. In the numerical experiments, in the experiments on MNIST, it seems that PGW would offer the best comparison (vs LOT and LGW which do not account for noise). Could these results be included?\n\n4. I believe that the robustness to noise is the most interesting feature of the PGW formulation. I would recommend that this be addressed more clearly in the text.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is, in my opinion well-written, and the theoretical findings appear correct. In the experiments, the LPGW algorithm compares favorably to the other approaches considered.", "weaknesses": "I believe that the paper is of a limited novelty. Indeed, both the linearized GW problem and the partial GW problem have appeared in previous works. Combining these two approaches to obtain a linearized partial GW problem appears to be incremental progress on the important question of efficient computation for the GW problem. \n\nFurthermore, the theoretical properties of the LPGW problem appear quite limited. Many of the results require the existence of a Monge map for the PGW problem, but sufficient conditions for these assumptions to hold are not discussed in the main text. This assumption is quite strong and, as such, these results appear to be of a limited applicability.    \n\nThe approximated LPGW is, in practice approximated as (20). This appears to be a very coarse approximation in general; no justifications are provided for when this might be a reasonable approximation. \n\nFinally, the experiments do not present any significantly new applications. The experiments in 4.1 and 4.2 are essentially the same as those from (Beier et al., 2022) the experiment in 4.3 is similar to that  from S. Nieter, R. Cummings, Z. Goldfeld, Outlier-Roubust Optimal Transport: Duality, Structure, and Statistical Analysis, AISTATS 2022. The main distinction is that a random rotation is performed on the dataset in the current paper, but this appears a bit contrived in the setting of MNIST.", "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": "hPhn1fE6p1", "reviewer": "Reviewer_ueVA", "summary": "This paper introduces the Linear Partial Gromov-Wasserstein (LPGW) embedding, a computationally efficient approximation of the Partial Gromov-Wasserstein (PGW) problem, which relaxes mass constraints for comparing measures across different metric spaces. By reducing the pairwise complexity from $\\mathcal{O}(K^2)$ to $\\mathcal{O}(K)$, LPGW preserves the partial matching capabilities of PGW while enhancing scalability. The authors provide theoretical guarantees and validate LPGW through experiments in shape retrieval and transport-based learning tasks.", "questions": "1. Could the authors extend the approximation results for LGW and LPGW to scenarios where the Monge mapping may not exist?\n  \n2. Could the authors provide empirical or theoretical results on the error introduced by the two layers of approximation? Specifically, how much error is accumulated when transitioning from LPGW to aLPGW (Equation (18)) and then from aLPGW to the final approximation (Equation (20))?\n  \n3. Proposition 3.1 (3) provides a result when the cost function $g_Y$​ is an inner product. Could this result be extended to the case of squared Euclidean distance with additional assumptions? This would be relevant since [A] also explores the existence of Monge mappings under squared Euclidean costs.\n  \n4. In the elliptical disks experiment, the choice of reference space has a significant impact on performance. Could the authors provide practical guidance or heuristics for selecting reference spaces to optimize the performance of LPGW?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow.\n  \n2. The authors introduce the Linear Partial Gromov-Wasserstein (LPGW) embedding, which addresses the computational challenges of PGW. They also provide a formal proof of the equivalence between LPGW and PGW under the PGW-Monge mapping assumption, contributing to the theoretical foundation of the method.\n  \n3. The paper presents a method to approximate LPGW efficiently, reducing computational overhead. Furthermore, the authors conduct extensive numerical experiments to demonstrate the effectiveness and computational advantages of LPGW.", "weaknesses": "1. The equivalence between LGW and GW (Proposition 2.1) and between LPGW and PGW (Proposition 3.1) critically relies on the existence of a Monge mapping. However, proving the existence of such a mapping for the GW problem requires satisfying strict conditions [A]. This raises concerns about the robustness of these approximations in practical scenarios where Monge mappings may not exist. The paper would benefit from \n    - providing theoretical bounds on the approximation error when a Monge mapping does not exist;\n    - including empirical experiments comparing performance on datasets known to violate Monge mapping conditions;\n    - discussing potential modifications to make the method more robust when Monge mappings do not exist.\n  \n2. The computational implementation of LPGW relies on two layers of approximations. First, the authors approximate LPGW using aLPGW, as introduced in Equation (18). Then, Equation (20) further approximates the aLPGW formulation. However, the paper lacks both theoretical guarantees and empirical evaluation of the error introduced by these sequential approximations. It would be beneficial if the authors could\n    - provide theoretical error bounds for each approximation step;\n    - include ablation studies quantifying the empirical error introduced at each approximation stage;\n    - discuss the tradeoffs between computational efficiency and approximation accuracy.\n  \n3. The paper primarily compares LPGW with PGW and LGW. However, other GW approximation methods could offer meaningful insights into the strengths and weaknesses of LPGW. Notably, comparisons with Low-Rank GW [B] and Sliced GW [C] could demonstrate whether LPGW provides any unique computational or approximation advantages.\n  \n\n[A] Dumont, Théo, Théo Lacombe, and François-Xavier Vialard. \"On the existence of Monge maps for the Gromov–Wasserstein problem.\" *Foundations of Computational Mathematics* (2024): 1-48.\n\n[B] Scetbon, Meyer, Gabriel Peyré, and Marco Cuturi. \"Linear-time gromov wasserstein distances using low rank couplings and costs.\" *International Conference on Machine Learning*. PMLR, 2022.\n\n[C] Titouan, Vayer, et al. \"Sliced gromov-wasserstein.\" *Advances in Neural Information Processing Systems* 32 (2019).", "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": "FY7PnZziCp", "reviewer": "Reviewer_gpEb", "summary": "The authors of this paper aim to improve on the partial Gromov-Wasserstein (PGW) method by creating linear partial Gromov-Wasserstein (LPGW) embedding. They begin the paper with a succinct coverage of optimal transport (OT). They further begin with covering the 2-Wasserstein distance, a common choice for OT-based methods, and proceed to lay out the fundamentals of the Gromov-Wasserstein (GW) distance. Next, the authors give a breakdown of the linear embedding technique, linear Gromov-Wasserstein (LGW). The mass constraint on OT methods motivated the creation of partial Gromov-Wasserstein, or PGW. Similar to the linearization of GW, the authors introduce the linearization of PGW through known techniques such as approximations; their work was further inspired by the need of having a faster solution for computing the distance between K different metric spaces. The authors claimed their algorithm can improve computing the PGW distances between K metric measure spaces from O(K^2) to O(K). While the authors have done a great job with the mathematical formulations, they have not provided a time-complexity analysis to back up their statement. Lastly, I believe the authors did not provide sufficient explanations for their experiments. For example, the simulation on the MNIST dataset, no clarifications are given on the details of training. For example, the authors state they will use a logistic regression for classification; this model is meant for binary classification and does not simply work on categorical cases. How exactly did they use logistic regression to predict classes when they range from 0-9? Furthermore, does this work with other models such as neural networks? It is always encouraged to be as specific as possible for reproducibility.", "questions": "Can you provide a time-complexity analysis to support your claim on a linear computation of the distances between K metric measure spaces?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper mathematically backs up their introduction of the linear partial Gromov-Wasserstein embedding algorithm. They also clearly demonstrate how previous work led to their contributions by breaking down and introducing each step along the way.", "weaknesses": "The authors claim that given K metric measure spaces, their algorithm can compute the distance between them in O(K) time. This claim was not supported with a time-complexity analysis and therefore remains unsubstantiated. It would strengthen the paper significantly to add a dedicated section, if even a small one, to prove the time-complexity (perhaps space-complexity if there's a tradeoff).", "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)