Linear Partial Gromov-Wasserstein Embedding

## Abstract

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, which relaxes the equal mass constraint, enabling 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 𝐾 K italic_K different metric measure spaces, the pairwise computation of the PGW distance requires solving the PGW problem 𝒪 ⁢ ( K 2 ) 𝒪 superscript 𝐾 2 \mathcal{O}(K^{2}) caligraphic_O ( italic_K start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) times. In contrast, the proposed linearization technique reduces this to 𝒪 ⁢ ( K ) 𝒪 𝐾 \mathcal{O}(K) caligraphic_O ( italic_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.

## 1 Introduction

Optimal transport (OT), unbalanced and partial OT, and linearized OT. The core objective of this work, and a general challenge in machine learning, is 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 modeling [, ], domain adaptation [, ], representation learning [], and many other domains. The classical OT problem, as detailed by [], involves matching two probability distributions to minimize the expected transportation cost, giving rise to the so-called Wasserstein distances. Although the classical 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 for partial matching of sets through the unbalanced and partial OT frameworks [, , , ]. Additionally, in large-scale machine learning applications, since the OT approach is computationally expensive, it has motivated numerous approximations that lead to significant speedups, such as those in [, , ], and the linearization technique, termed linear optimal transportation (LOT), proposed by []. There have also been advances in reducing the computational complexity of comparing unbalanced measures [, ].

The Gromov-Wasserstein (GW) distance, unbalanced and partial GW, and linearized GW. Another line of research has focused on the comparison of probability measures across different metric spaces using Gromov-Wasserstein (GW) distances []. These innovations have applications in areas ranging from quantum chemistry [] to natural language processing [], enhancing fundamental tasks such as clustering [], dimensionality reduction [], shape correspondence [], shape analysis [], and inference-based simulation []. 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 different total masses [, , , ]. Furthermore, to address the computational expense of pairwise GW distance calculations in large-scale applications, a linearized version of GW has been proposed in []. Similar to the LOT framework [], this approach is based on barycentric projection 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 this, we propose the so-called LPGW distance, which we prove to be a metric under certain assumptions.
- •
Given $K$ different metric measure spaces, computing their pairwise PGW distances requires solving the PGW problem $\mathcal{O}(K^{2})$ times. However, computing the LPGW distance pairwise requires only $\mathcal{O}(K)$ distance 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.

## 2 Background

### 2.1 The Wasserstein Distance

Let $\mathcal{P}(\mathbb{R}^{d})$ be the space of probability measures on the Borel $\sigma$-algebra on $\mathbb{R}^{d}$, and let $\mathcal{P}_{2}(\mathbb{R}^{d}):=\{\mu\in\mathcal{P}(\mathbb{R}^{d}):\int_{
\mathbb{R}^{d}}|x|^{2}d\mu(x)<\infty\}$.
Given a (measurable) mapping $T:\mathbb{R}^{d}\to\mathbb{R}^{d}$, the pushforward measure $T_{\#}\mu$ is defined as $T_{\#}\mu(B):=\mu(T^{-1}(B))$ for all Borel sets $B\subseteq\mathbb{R}^{d}$, where $T^{-1}(B):=\{x:T(x)\in B\}$ is the preimage of $B$ under $T$.

Given $\mu,\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$, the 2-Wasserstein distance is defined as

$$ $\displaystyle W_{2}^{2}(\mu,\nu):=\min_{\gamma\in\Gamma(\mu,\nu)}\int_{\mathbb {R}^{d}\times\mathbb{R}^{d}}\|x-y\|^{2}d\gamma(x,y)$ (1) $$

where $\Gamma(\mu,\nu)$ is set of joint probability measures on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ whose first and second marginals are $\mu$ and $\nu$, respectively. The classical OT theory [, ] 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 $\Gamma^{*}(\mu,\nu)$ the set of all optimal transportation plans for problem (1).

When an optimal transportation plan $\gamma$ is induced by a mapping $T:\mathbb{R}^{d}\to\mathbb{R}^{d}$, that is,

$$ $\displaystyle\gamma=(\mathrm{id}\times T)_{\#}\mu\in\Gamma^{*}(\mu,\nu),\qquad \text{ with }\quad T_{\#}\mu=\nu,$ (2) $$

we say that the Monge mapping assumption holds, and the function
$T$ is called a Monge mapping. In particular, by Brenier’s theorem, when $\mu$ is a continuous measure (i.e., absolutely continuous with respect to the Lebesgue measure on $\mathbb{R}^{d}$), a Monge mapping $T$ always exists and it is unique.

We refer to Appendix A for a detailed introduction to the LOT formulation.

### 2.2 The Gromov-Wasserstein Distance

Consider two compact gauged measure spaces (gm-spaces) $\mathbb{X}=(X,g_{X},\mu)$ and $\mathbb{Y}=(Y,g_{Y},\nu)$, where $X\subset\mathbb{R}^{d_{x}},Y\subset\mathbb{R}^{d_{y}}$ are non-empty (compact) convex sets (with $d_{x},d_{y}\in\mathbb{N}$);
$g_{X}:X^{\otimes 2}\to\mathbb{R}$ is a gauge function in $L_{sys}^{2}(X^{\otimes 2},\mu^{\otimes 2})$, i.e., the space of symmetric, real-valued functions on $X^{\otimes 2}:=X\times X$ that are square-integrable with respect to $\mu^{\otimes 2}:=\mu\otimes\mu$ (similarly for $g_{Y}\in L_{sys}^{2}(Y^{\otimes 2},{\nu^{\otimes 2}})$; and $\mu,\nu$ are probability measures defined on $X,Y$ respectively.
In addition, assume that $\mathbb{X}$ and $\mathbb{Y}$ are metric measure spaces (mm-spaces); that is, there exist distances $d_{X}$ and $d_{Y}$ on $X$ and $Y$, respectively. In general, we will assume that $g_{X}$ is a continuous function on $X^{\otimes 2}$ with respect to the metric $d_{X^{\otimes 2}}((x_{1},x_{1}^{\prime}),(x_{2},x_{2}^{\prime})):=d_{X}(x_{1},
x_{2})+d_{X}(x_{1}^{\prime},x_{2}^{\prime})$ on $X^{\otimes 2}$ (respectively, for $g_{Y}$). Thus, since $X$ is compact, $g_{X}$ (respectively, $g_{Y}$) is a Lipschitz continuous function, i.e., there exists $K\in\mathbb{R}_{>0}$ such that

$$ $\displaystyle|g_{X}(x_{1},x_{1}^{\prime})-g_{X}(x_{2},x_{2}^{\prime})|\leq K(d _{X}(x_{1},x_{2})+d_{X}(x_{1}^{\prime},x_{2}^{\prime})),\quad\forall x_{1},x_{ 1}^{\prime},x_{2},x_{2}^{\prime}\in X.$ (3) $$

For the reader’s convenience, unless stated otherwise, we default to $g_{X}(x_{1},x_{2})=d_{X}^{2}(x_{1},x_{2})$ (which is the classical setting for the Gromov-Wasserstein problem [, ]), or to the inner product
$g_{X}(x_{1},x_{2})=x_{1}^{\top}x_{2}$ (which has been studied in [, ]). The same applies to $g_{Y}$.

The Gromov-Wasserstein (GW) problem between $\mathbb{X}$ and $\mathbb{Y}$ is defined as

$$ $GW^{2}(\mathbb{X},\mathbb{Y}):=\min_{\gamma\in\Gamma(\mu,\nu)}\langle|g_{X}-g_ {Y}|^{2},\gamma^{\otimes 2}\rangle$ (4) $$

where

$$ $\langle|g_{X}-g_{Y}|^{2},\gamma^{\otimes 2}\rangle:=\int_{(X\times Y)^{\otimes 2 }}|g_{X}(x,x^{\prime})-g_{Y}(y,y{{}^{\prime}})|^{2}\,d\gamma(x,y)d\gamma(x^{ \prime},y^{\prime}).$ $$

A minimizer for (4) always exists [], and
we use $\Gamma^{*}(\mathbb{X},\mathbb{Y})$ to denote the set of all optimal transportation plans $\gamma\in\Gamma(\mu,\nu)$ for the GW problem defined in (4). In addition, when $g_{X}=d_{X}^{s}$ and $g_{Y}=d_{Y}^{s}$ for $s\geq 1$, $GW(\cdot,\cdot)$ defines a metric on the space of mm-spaces up to isomorphism(^*^**Two mm-spaces $\mathbb{X}$, $\mathbb{Y}$ are isomorphic is there exists an isometry $\psi:X\to Y$, i.e., $d_{X}(x,x^{\prime})=d_{Y}(\psi(x),\psi(x^{\prime}))$, which is surjective and such that $\nu=\psi_{\#}\mu$.).

Similar to classical OT theory, we say that the GW-Monge mapping assumption holds if there exists a minimizer $\gamma$ for (4) of the form $\gamma=(\mathrm{id}\times T)_{\#}\mu$, where $\mathrm{id}:X\to X$ is the identity map on $X$, and $T:X\to Y$ is a measurable function that pushes forward $\mu$ to $\nu$. In recent years, the existence of Monge mappings for the GW problem has been studied in works such as [, , ].

Note that the GW minimization problem defined in (4) is quadratic but non-convex. The computational cost of $GW(\cdot,\cdot)$ for discrete measures $\mu,\nu$ of size $n$ is $\mathcal{O}(n^{3}\cdot L)$ to obtain a solution that is a local minimum, where $n^{3}$ is the computational cost of one iteration and $L$ is the required number of iterations(^*^**We refer to Appendix C for details.). Thus, when faced with the task of computing the pairwise GW distances between discrete gm-spaces $\mathbb{Y}^{1},\ldots,\mathbb{Y}^{K}$ with $n$ points each, the resulting complexity is $\mathcal{O}(K^{2}\cdot n^{3}\cdot L)$. To reduce the complexity of computing the pairwise distances in this setting, [] introduce a linear embedding technique called linear Gromov-Wasserstein (LGW), which we discuss in the following section.

### 2.3 The Linear Gromov-Wasserstein Embedding and Distance

Consider a fixed gm-space $\mathbb{X}=(X,g_{X},\mu)$, which serves as a reference space. Given a target gm-space $\mathbb{Y}=(Y,g_{Y},\nu)$, suppose that the GW-Monge mapping assumption holds, i.e., there exists an optimal transportation plan $\gamma=(\mathrm{id}\times T)_{\#}\mu$ for the GW problem (4) between $\mathbb{X}$ and $\mathbb{Y}$. Then, the linear Gromov-Wasserstein (LGW) embedding is defined as the following mapping

$$ $\displaystyle\mathbb{Y}\mapsto k_{\gamma}:=g_{X}(\cdot_{1},\cdot_{2})-g_{Y}(T( \cdot_{1}),T(\cdot_{2})),$ (5) $$

which assigns each gm-space $\mathbb{Y}$ to a gauge function $k_{\gamma}:X\times X\to\mathbb{R}$ defined by (5). This embedding can recover the GW distance $GW(\mathbb{X},\mathbb{Y})$ by the following:

$$ $GW(\mathbb{X},\mathbb{Y})=\int_{X\times X}|k_{\gamma}(x,x^{\prime})|^{2}d\mu(x )d\mu(x^{\prime}).$ $$

Given two gm-spaces $\mathbb{Y}^{1}=\{Y^{1},g_{Y^{1}},\nu^{1}\},\mathbb{Y}^{2}=\{Y^{2},g_{Y^{2}},
\nu^{2}\}$, assume that there exist optimal transportation plans $\gamma^{1}=(\mathrm{id}\times T^{1})_{\#}\mu\in\Gamma^{*}(\mathbb{X},\mathbb{Y
}^{1}),\gamma^{2}=(\mathrm{id}\times T^{2})_{\#}\mu\in\Gamma^{*}(\mathbb{X},
\mathbb{Y}^{2})$.
Let $k_{\gamma^{1}},k_{\gamma^{2}}$ denote the corresponding linear GW embeddings as defined by (5). Then, the LGW distance conditioned on $\gamma^{1},\gamma^{2}$, is defined as

$$ $\displaystyle LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{ 2}):=\|k_{\gamma^{1}}-k_{\gamma^{2}}\|_{L^{2}(\mu^{\otimes 2})}.$ (6) $$

When the GW-Monge mapping assumption does not hold, [] extend the above distance conditioned on a pair of arbitrary plans $\gamma^{1}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}\in\Gamma^{*}(
\mathbb{X},\mathbb{Y}^{2})$:

$$ $\displaystyle LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{ 2})=\inf_{\gamma\in\Gamma(\gamma^{1},\gamma^{2};\mu)}\langle|g_{Y^{1}}-g_{Y^{2 }}|^{2},\gamma^{\otimes 2}\rangle$ (7) $\displaystyle=\inf_{\gamma\in\Gamma(\gamma^{1},\gamma^{2};\mu)}\int_{(X\times Y ^{1}\times Y^{2})^{\otimes 2}}|g_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})-g_{Y^{2}}(y ^{2},y^{2}{{}^{\prime}})|^{2}d\gamma(x,y^{1},y^{2})\gamma(x^{\prime},y^{1}{{}^ {\prime}},y^{2}{{}^{\prime}}),$ $$

where

$$ $\Gamma(\gamma^{1},\gamma^{2};\mu):=\{\gamma\in\mathcal{M}_{+}(X\times Y^{1} \times Y^{2}):(\pi_{X,Y^{1}})_{\#}\gamma=\gamma^{1},(\pi_{X,Y^{2}})_{\#}\gamma =\gamma^{2},(\pi_{X})_{\#}\gamma=\mu\},$ $$

for $\pi_{X,Y^{i}}(x,y^{1},y^{2}):=(x,y^{i})$ for $i=1,2$, and $\pi_{X}(x,y^{1},y^{2}):=x$.
Finally, the LGW distance between $\mathbb{Y}^{1}$ and $\mathbb{Y}^{2}$ is defined as

$$ $\displaystyle LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})=\inf_{\begin{ subarray}{c}\gamma^{1}\in\Gamma^{*}(\mu,\nu^{1})\\ \gamma^{2}\in\Gamma^{*}(\mu,\nu^{2})\end{subarray}}LGW(\mathbb{Y}^{1},\mathbb{ Y}^{2};\mathbb{X},\gamma^{1},\gamma^{2}).$ (8) $$

We refer to Appendix B for further details.

To simplify the computation of the above formulation, [] propose the barycentric projection method, which we will briefly review here.

Let $\gamma\in\Gamma(\mu,\nu)$ be a transportation plan between $\mu\in\mathcal{P}(X)$ and $\nu\in\mathcal{P}(Y)$. By using [Definition 5.4.2, []], the barycentric projection map $\mathcal{T}_{\gamma}:X\to Y$ is defined as

$$ $\displaystyle\mathcal{T}_{\gamma}(x)$ $\displaystyle:=\int_{Y}y\,d\gamma_{Y|X}(y|x).$ (9) $$

where $\{\gamma_{Y|X}(\cdot|x)\}_{x\in X}$ is the corresponding disintegration of $\gamma$ with respect to its first marginal $\mu$. That is, $\{\gamma_{Y|X}(\cdot|x)\}_{x\in X}$ is a family of measures satisfying

$$ $\displaystyle\int_{X\times Y}\phi(x,y)\,d\gamma(x,y)=\int_{X}\int_{Y}\phi(x,y) \,d\gamma_{Y|X}(y|x)d\mu(x),\quad\forall\phi\in C(X\times Y).$ $$

If $\gamma^{*}\in\Gamma^{*}(\mathbb{X},\mathbb{Y})$, we define the measure
$\widetilde{\nu}_{\gamma^{*}}:=(\mathcal{T}_{\gamma^{*}})_{\#}\mu\in\mathcal{P}
(Y)$ and the gm-space
$\widetilde{\mathbb{Y}}_{\gamma^{*}}:=(Y,g_{Y},\nu_{\gamma^{*}})$. We provide the following results as a complement to the work in [].

###### Proposition 2.1 .

Let $\gamma^{*}\in\Gamma^{*}(\mathbb{X},\mathbb{Y})$ and $\gamma^{0}\in\Gamma^{*}(\mathbb{X},\mathbb{X})$. Then, we have the following:

- (1)
The LGW embedding of $\mathbb{Y}$ can recover the GW distance, i.e.,
$LGW(\mathbb{X},\mathbb{Y};\mathbb{X},\gamma^{0},\gamma^{*})=GW(\mathbb{X},
\mathbb{Y}).$
- (2)
If $T$ is a Monge mapping for $GW(\mathbb{X},\mathbb{Y})$ such that $\gamma^{*}=(\mathrm{id}\times T)_{\#}\mu$, then $\mathcal{T}_{\gamma^{*}}=T$, $\mu$-a.e. As a consequence, $\widetilde{\nu}_{\gamma^{*}}=\nu$, and thus $\widetilde{\mathbb{Y}}_{\gamma^{*}}=\mathbb{Y}$.
- (3)
If $g_{Y}(\cdot_{1},\cdot_{2})=\alpha\langle\cdot_{1},\cdot_{2}\rangle_{Y}$, where $\langle\cdot_{1},\cdot_{2}\rangle_{Y}$ is an inner product restricted to $Y$ and $\alpha\in\mathbb{R}$, then the barycentric projection map $\mathcal{T}_{\gamma^{*}}$ defined by (9) is a Monge mapping in the sense that $\widetilde{\gamma}=(\mathrm{id}\times\mathcal{T}_{\gamma^{*}})_{\#}\mu$ is optimal for the GW problem $GW(\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{*}})$.

We refer the reader to Appendix D for the proof.

Based on the above proposition, given $\mathbb{Y}^{1}=(Y^{1},g_{Y^{1}},\nu^{1})$ and $\mathbb{Y}^{2}=(Y^{2},g_{Y^{2}},\nu^{2})$, let $\gamma^{1}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{1})$ and $\gamma^{2}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{2})$. The following
approximated LGW (aLGW) distance can be used as proxy for the LGW and GW distances. Furthermore, in practice, we can fix a single pair $(\gamma^{1},\gamma^{2})$ to compute the distance, rather than compute the infimum:

$$ $\displaystyle aLGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})$ $\displaystyle:=\inf_{\begin{subarray}{c}\gamma^{1}\in\Gamma^{*}(\mathbb{X}, \mathbb{Y}^{1})\\ \gamma^{2}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{2})\end{subarray}}LGW(\mathbb{Y }^{1}_{\gamma^{1}},\mathbb{Y}^{2}_{\gamma^{2}};\mathbb{X},\gamma^{1},\gamma^{2})$ $\displaystyle=\inf_{\begin{subarray}{c}\gamma^{1}\in\Gamma^{*}(\mathbb{X}, \mathbb{Y}^{1})\\ \gamma^{2}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{2})\end{subarray}}\|g_{Y^{1}}( \mathcal{T}_{\mathcal{\gamma}^{1}}(\cdot_{1}),\mathcal{T}_{\mathcal{\gamma}^{1 }}(\cdot_{2}))-g_{Y^{2}}(\mathcal{T}_{\gamma^{2}}(\cdot_{1}),\mathcal{T}_{ \gamma^{2}}(\cdot_{2}))\|_{L^{2}(\mu^{\otimes 2})}^{2}$ (10) $\displaystyle\approx\|g_{Y^{1}}(\mathcal{T}_{\mathcal{\gamma}^{1}}(\cdot_{1}), \mathcal{T}_{\mathcal{\gamma}^{1}}(\cdot_{2}))-g_{Y^{2}}(\mathcal{T}_{\gamma^{ 2}}(\cdot_{1}),\mathcal{T}_{\gamma^{2}}(\cdot_{2}))\|_{L^{2}(\mu^{\otimes 2})} ^{2}.$ $$

###### Proposition 2.1 .

### 2.4 The Partial Gromow-Wasserstein Distance

Partial Gromov-Wasserstein (PGW), or more generally, unbalanced GW, relaxes the assumption that $\mu,\nu$ are normalized probability measures [, , ]. In particular, the PGW distance is defined as

$$ $\displaystyle PGW^{2}_{\lambda}(\mathbb{X},\mathbb{Y})$ $\displaystyle:=\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\langle|g_{X}-g_{Y}|^{2}, \gamma^{\otimes 2}\rangle+\lambda(|\mu^{\otimes 2}-\gamma_{X}^{\otimes 2}|+| \nu^{\otimes 2}-\gamma_{Y}^{\otimes 2}|),$ (11) $$

where $\lambda>0$ is a parameter; $\gamma_{X}:=(\pi_{X})_{\#}\gamma,\gamma_{Y}:=(\pi_{Y})_{\#}\gamma$ are the corresponding marginals of $\gamma$ on $X$ and $Y$, respectively; and $\Gamma_{\leq}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(X\times Y):\gamma_{X}\leq
\mu,\gamma_{Y}\leq\nu\}$, where $\mathcal{M}_{+}(X\times Y)$ denotes the set of finite non-negative measures on $X\times Y$, and $\gamma_{X}\leq\mu$ denotes that for any Borel set $A$, $\gamma_{X}(A)\leq\mu(A)$ (similarly for $\gamma_{Y}\leq\nu$).

In the discrete setting, the PGW problem can be solved by variants of the Frank-Wolfe algorithm (see the algorithms in [] for details). From a theoretical perspective, there always exists a minimizer for the optimization problem in (11) (see [Proposition 3.3, []]), and we use $\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y})$ to denote the set of all optimal transportation plans for $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$.
We say that the PGW-Monge mapping assumption holds if there exists an optimal transportation plan $\gamma$ for the optimization problem in (11) of the form $\gamma=(\mathrm{id}\times T)_{\#}\gamma_{X}$ for some $T:X\to Y$.

## 3 Linear Partial Gromov-Wasserstein Embedding and Distance

Inspired by the work in [], we extend the LGW distance to the unbalanced setting. In particular, we present a linearization technique for the PGW problem proposed in [].

Given gm-spaces $\mathbb{X}=(X,g_{X},\mu)$ and $\mathbb{Y}=(Y,g_{Y},\nu)$, let $\gamma\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y})$. We first suppose that the
PGW-Monge mapping assumption holds; that is, $\gamma=(\mathrm{id}\times T)_{\#}\gamma_{X}$ for some $T:X\to Y$. We subsequently define the linear partial Gromov-Wasserstein (LPGW) embedding as

$$ $\mathbb{Y}\mapsto(\gamma_{X},k_{\gamma},\gamma_{c}),$ (12) $$

where $\gamma_{X}:=(\pi_{X})_{\#}\gamma$, $k_{\gamma}(\cdot_{1},\cdot_{2}):=g_{X}(\cdot_{1},\cdot_{2})-g_{Y}(T(\cdot_{1})
,T(\cdot_{2}))$, and $\gamma_{c}:=\nu^{\otimes 2}-\left(\gamma_{Y}\right)^{\otimes 2}$ for $\gamma_{Y}=(\pi_{Y})_{\#}\gamma$. Here, the first component of the embedding, $\gamma_{X}$, encodes the mass transportation from the source domain $X$. The second component, $k_{\gamma},$ describes the transportation cost function. Finally, the third component, $\gamma_{c}$, encodes the mass creation in the target domain $Y$.

Similarly to the LGW embedding given by (5), we show in Proposition 3.1 that the above embedding can recover $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ in the sense that

$$ $\|k_{\gamma^{*}}\|^{2}_{L^{2}((\gamma_{X}^{*})^{\otimes 2})}+\lambda(|\mu|^{2} -|\gamma_{X}^{*}|^{2}+|\gamma^{*}_{c}|)=PGW_{\lambda}(\mathbb{X},\mathbb{Y}).$ $$

Given two gm-spaces $\mathbb{Y}^{1},\mathbb{Y}^{2}$, let $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1})$ and $\gamma^{2}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})$. Suppose $\gamma^{1},\gamma^{2}$ are induced by Monge mappings $T^{1},T^{2}$ and compute the corresponding LPGW embeddings via (12). We define the LPGW discrepancy conditioned on $\gamma^{1},\gamma^{2}$ by

$$ $LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{2}) :=\inf_{\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_{X}}\|k_{\gamma^{1}}-k_ {\gamma^{2}}\|^{2}_{L^{2}(\mu^{\prime\otimes 2})}+\lambda(|\nu^{1}|^{2}+|\nu^{ 2}|^{2}-2|\mu^{\prime}|^{2}),$ (13) $$

where $(\gamma^{1}_{X}\wedge\gamma^{2}_{X})(E)=\min\{\gamma^{1}_{X}(E),\gamma^{2}_{X}
(E)\}$. Note that the above formulation can be written entirely in terms of the LPGW embeddings since $|\nu^{1}|^{2}=|\gamma^{1}_{c}|+|\gamma^{1}_{X}|^{2}$, and similarly $|\nu^{2}|^{2}=|\gamma^{2}_{c}|+|\gamma^{2}_{X}|^{2}$.

When the PGW-Monge mapping assumption does not hold, we extend the above LPGW discrepancy conditioned on arbitrary transportation plans $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}
\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})$ as follows:

$$ $\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{ 1},\gamma^{2}):=$ $\displaystyle\inf_{\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)}\|g_{Y^{1 }}-g_{Y^{2}}\|^{2}_{L^{2}(\gamma^{\otimes 2})}+\lambda(|\nu^{1}|^{2}-|\nu^{2}| ^{2}-2|\gamma|^{2}),$ (14) $$

where

$$ $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu):=\{\gamma\in\mathcal{M}_{+}(X\times Y ^{1}\times Y^{2}):(\pi_{X,Y^{1}})_{\#}\gamma\leq\gamma^{1},(\pi_{X,Y^{2}})_{\# }\gamma\leq\gamma^{2}\}.$ $$

Finally, to gain independence from the transportation plans $\gamma^{1},\gamma^{2}$, we formally define the LPGW discrepancy as

$$ $\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}):=\inf_{ \begin{subarray}{c}\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y }^{1})\\ \gamma^{2}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})\end{subarray }}LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{2 }).$ (15) $$

###### Proposition 3.1 .

Given compact gm-spaces $\mathbb{X}=(X,g_{X},\mu)$ and $\mathbb{Y}=(Y,g_{Y},\nu)$, let $\gamma^{0}\in\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{X})$ and $\gamma^{*}\in\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y})$. We have the following:

- (1)
Problem (14) admits a minimizer.
- (2)
Under the PGW-Monge mapping assumption, the problems (13) and (14) coincide.
- (3)
Under the PGW-Monge mapping assumption, when $\lambda$ is sufficiently large, problem (13) achieves the value
$\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{
1},\gamma^{2}):=\|k_{\gamma^{1}}-k_{\gamma^{2}}\|^{2}_{L^{2}((\gamma^{1}_{X}
\wedge\gamma^{2}_{X})^{\otimes 2})}+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|
\gamma^{1}_{X}\wedge\gamma^{2}_{X}|^{2}).$
(16)
- (4)
The LPGW embedding of $\mathbb{Y}$ can recover $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ in the sense that, under the PGW-Monge mapping assumption, we have
$\|k_{\gamma^{*}}\|^{2}_{L^{2}((\gamma_{X}^{*})^{\otimes 2})}+\lambda(|\mu|^{2}
-|\gamma_{X}^{*}|^{2}+|\gamma^{*}_{c}|)=PGW_{\lambda}(\mathbb{X},\mathbb{Y}),$
and in general, we have
$LPGW_{\lambda}(\mathbb{X},\mathbb{Y};\gamma^{0},\gamma^{*})=PGW_{\lambda}(
\mathbb{X},\mathbb{Y}).$
- (5)
The LPGW discrepancies defined in (14) and (15) are pseudo-metrics. Indeed, under certain conditions (15) is a rigorous metric. We refer to Appendix E for detailed discussion.

The proof of the above proposition is included in Appendix E.

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 G.

###### Theorem 3.2 .

Given gm-spaces $\mathbb{X}=(X,g_{X},\mu)$ and $\mathbb{Y}=(Y,g_{Y},\nu)$, let $\gamma^{0}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{X})$ and $\gamma^{*}\in\mathcal{M}_{+}(X\times Y)$. Further, let
$\widetilde{\nu}:=\widetilde{\nu}_{\gamma^{*}}:=(\mathcal{T}_{\gamma^{*}})_{\#}\gamma$ and $\widetilde{\mathbb{Y}}_{\gamma^{*}}=(Y,d_{Y},\widetilde{\nu})$. Then,

- (1)
If $\gamma^{*}$ is induced by a mapping $T$, then $\mathcal{T}_{\gamma^{*}}=T,\gamma^{*}_{X}-a.s.$
- (2)
If $\gamma^{*}\in\Gamma^{*}_{\leq}(\mathbb{X},\mathbb{Y})$, and the conditions for $g_{Y}(\cdot_{1},\cdot_{2})$ in statement 3 of Proposition 2.1 hold, then
$\widetilde{\gamma}:=(\mathrm{id}\times\mathcal{T}_{\gamma^{*}})_{\#}{\gamma^{*
}_{X}}$ is optimal for $PGW_{\lambda}(\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{*}})$.
- (3)
If $\gamma^{1}\in\Gamma^{*}_{\leq}(\mathbb{X},\mathbb{Y}^{1})$ and $\gamma^{2}\in\Gamma^{*}_{\leq}(\mathbb{X},\mathbb{Y}^{2})$, and the PGW-Monge mapping assumption holds, then
$\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{
1},\gamma^{2})=LPGW_{\lambda}(\widetilde{\mathbb{Y}}_{\gamma^{1}},\widetilde{
\mathbb{Y}}_{\gamma^{2}};\mathbb{X},\widetilde{\gamma}^{1},\widetilde{\gamma}^
{2})+\lambda(|\gamma^{1}_{c}|+|\gamma^{2}_{c}|).$
(17)

Based on part 3 in the above theorem, we define the approximated LPGW (aLPGW) discrepancy by

$$ $\displaystyle aLPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}):=\inf_ {\begin{subarray}{c}\gamma^{1}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{1}),\\ \gamma^{2}\in\Gamma^{*}(\mathbb{X},\mathbb{Y}^{2})\end{subarray}}LPGW_{\lambda }(\widetilde{\mathbb{Y}}_{\gamma^{1}},\widetilde{\mathbb{Y}}_{\gamma^{2}}; \mathbb{X},\gamma^{1},\gamma^{2})+\lambda(|\gamma^{1}_{c}|+|\gamma^{2}_{c}|).$ (18) $$

###### Proposition 3.3 .

If $X,Y$ are compact sets, when $\lambda$ is sufficiently large, the above formulation becomes:

$$ $\displaystyle aLPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})=\inf_{ \begin{subarray}{c}\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y }^{1}),\\ \gamma^{2}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})\end{subarray}}$ $\displaystyle\|k_{{\gamma}^{1}}-k_{{\gamma}^{2}}\|^{2}_{(\gamma^{1}_{X}\wedge \gamma^{2}_{X})^{\otimes 2}}+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|\gamma^{1}_ {X}\wedge\gamma^{2}_{X}|^{2}).$ (19) $$

In practice, similar to LGW, we only select one pair of optimal transportation plans $\gamma^{1},\gamma^{2}$ to compute the embedding and the above aLPGW discrepancy. In addition, we apply (19) to approximate the original formula (18). That is, in our experiments we directly compute

$$ $\displaystyle\|k_{{\gamma}^{1}}-k_{{\gamma}^{2}}\|^{2}_{(\gamma^{1}_{X}\wedge \gamma^{2}_{X})^{\otimes 2}}+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|\gamma^{1}_ {X}\wedge\gamma^{2}_{X}|^{2}).$ (20) $$

###### Proposition 3.1 .

###### Theorem 3.2 .

###### Proposition 3.3 .

### 3.1 Numerical implementation of LPGW in discrete setting

In practice, we consider discrete distributions (or more generally, discrete Radon measures). Suppose $\mathbb{X}=\{X,\|\cdot\|_{d_{0}},\mu=\sum_{i=1}^{n}p_{i}\delta_{x_{i}}\}$, where $X\subset\mathbb{R}^{d_{0}}$ is a convex compact set containing $\{0_{d_{0}},x_{1},\ldots x_{n}\}$.
We similarly let
$\mathbb{Y}^{1}=(Y^{1},\|\cdot\|_{d_{1}},\nu=\sum_{j=1}^{m_{1}}q_{j}^{1}\delta_
{y_{j}^{1}})$ and $\mathbb{Y}^{2}=(Y^{2},\|\cdot\|_{d^{2}},\nu^{2}=\sum_{j=1}^{m_{2}}q_{j}^{2}
\delta_{y_{j}^{2}})$.

Suppose $\gamma^{1}\in\mathbb{R}_{+}^{n\times m_{1}}$ is an optimal transportation plan for $PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{1})$. By convexity of $Y$, the barycentric projection given by (9) becomes

$$ $\displaystyle\mathcal{T}_{\gamma^{1}}(x_{i})=\begin{cases}\widetilde{y}_{i}= \frac{1}{\widetilde{q}_{i}}[\gamma^{1}y^{1}]_{i}&\text{if }\widetilde{q}_{i}>0 \\ 0_{d_{1}}&\text{if }\widetilde{q}_{i}=0\end{cases}\quad\text{where }\widetilde {q}=\gamma_{X}^{1}=\gamma^{1}1_{m_{1}}.$ (21) $$

Thus, the corresponding projected measure becomes
$\widetilde{\nu}_{\gamma^{1}}=\sum_{i}\widetilde{q}_{i}\delta_{\widetilde{y}_{i}}$. In addition, we have
$|\gamma_{c}|=(\sum_{i=1}^{n}p_{i})^{2}-(\sum_{i\in 1}^{n}\widetilde{q}_{i}^{1}
)^{2}$. Let

$$ $\displaystyle\widetilde{K}^{1}:=k_{\widetilde{\gamma}^{*}}=[\|\widetilde{y}_{i }-\widetilde{y}^{\prime}_{i}\|^{2}-\|x_{i}-x_{i}^{\prime}\|^{2}]_{i,i^{\prime} \in[1:n]}\in\mathbb{R}^{n\times n}.$ (22) $$

Suppose $\gamma^{2}\in\mathbb{R}_{+}^{n\times m_{2}}$ is an optimal transportation plan for $PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{2})$. We define all corresponding terms analogously.

Let $\widetilde{q}^{1,2}=\widetilde{q}^{1}\wedge\widetilde{q}^{2},|\widetilde{q}^{1
}-\widetilde{q}^{2}|_{TV}=\sum_{i=1}^{n}|\widetilde{q}_{i}^{1}-\widetilde{q}_{
i}^{2}|,|q^{1}|=\sum_{i=1}^{m_{1}}q_{i}^{1}$. The aLPGW distance given by (18) and (19) becomes

$$ $\displaystyle aLPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})$ $\displaystyle\approx\sum_{i=1}^{n}\left(\|\widetilde{y}^{1}_{i}-\widetilde{y}^ {1}_{i^{\prime}}\|^{2}-\|\widetilde{Y}^{2}_{i}-\widetilde{Y}^{2}_{i^{\prime}} \|^{2}\right)^{2}\widetilde{q}_{i}^{12}\widetilde{q}_{i^{\prime}}^{12}+\lambda (|q^{1}|^{2}+|q^{2}|^{2}-2|\widetilde{q}^{12}|^{2})$ $\displaystyle=(\widetilde{q}^{12})^{\top}\left[(\widetilde{K}_{1}-\widetilde{K }_{2})^{2}\right](\widetilde{q}^{12})+\lambda(|\gamma^{1}_{c}|+|\gamma^{2}_{c} |+|\widetilde{q}_{1}^{\otimes 2}-\widetilde{q}_{2}^{\otimes 2}|_{TV}),$ (23) $$

where $(\widetilde{K}_{1}-\widetilde{K}_{2})^{2}$ denotes the element-wise squared matrix and $\widetilde{q}_{1}^{\otimes 2}=\widetilde{q}_{1}\widetilde{q}_{1}^{\top}$ (similarly for $\widetilde{q}_{2}^{\otimes 2}$). The above quantity (23) can be used to approximate the original PGW distance between $\mathbb{Y}^{1}$ and $\mathbb{Y}^{2}$.

In addition, the original LPGW embedding (12) of $\mathbb{Y}^{1}$ (in fact, of $\widetilde{\mathbb{Y}}^{1}$) is $(\widetilde{K}^{1},\widetilde{\nu}_{\gamma^{1}},\gamma^{1}_{c})$. We reduce this embedding to $(\widetilde{K}^{1},\widetilde{q}^{1},|\gamma^{1}_{c}|)$ which is sufficient to compute the above aLPGW discrepancy. Thus, $(\widetilde{K}^{1},\widetilde{q}^{1},|\gamma^{1}_{c}|)$ can be regarded as numerical implementation of the LPGW embedding (12).

## 4 Experiments

### 4.1 Elliptical Disks

In this experiment, we apply the LPGW distance and the PGW distance to the 2D dataset presented in [], consisting of 100 elliptical disks. We compute the pairwise distances between the samples first using the PGW distance and then comparing 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 mean relative error (MRE) and Pearson correlation coefficient (PCC).

Experiment setup.
We represent each 2D shape as an mm-space $\mathbb{X}^{i}=(\mathbb{R}^{2},\|\cdot\|_{2},\mu^{i})$, where $\mu^{i}=\sum_{i=1}^{n}\frac{1}{n}\delta_{x_{i}}$. We normalize each shape so that the largest pairwise distance in each mm-space is $1$. Based on [Lemma E.2, []], the largest possible choice of $\lambda$ is given by $2\lambda=1$. We hence test $\lambda\in\{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 I for full numerical details, MDS visualizations, and complete results.

##### Performance analysis.

We present the results when $\lambda=0.1$ in Table 1. First, we observe that LPGW is significantly faster than PGW as it only requires $N=100$ transport plan computations, whereas the PGW methods require $\binom{N}{2}$ transport plan computations. Second, we observe that when the reference space is one of $\mathbb{S}_{6},\mathbb{S}_{7},\mathbb{S}_{8},\mathbb{S}_{9}$, LPGW admits a relatively smaller MRE and higher PCC, demonstrating the importance of the chosen reference space.

**Table 1: Experimental results when $\lambda=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.**
|  | PGW | $\mathbb{S}_{1}$ | $\mathbb{S}_{2}$ | $\mathbb{S}_{3}$ | $\mathbb{S}_{4}$ | $\mathbb{S}_{5}$ | $\mathbb{S}_{6}$ | $\mathbb{S}_{7}$ | $\mathbb{S}_{8}$ | $\mathbb{S}_{9}$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  |  |  |  |  |  |  |  |  |  |
| points |  | 441 | 676 | 625 | 52 | 289 | 545 | 882 | 882 | 317 |
| time (min) | 46.97 | 0.76 | 3.78 | 3.13 | 0.08 | 0.62 | 1.56 | 1.91 | 1.98 | 0.71 |
| MRE $\downarrow$ | — | 0.1941 | 0.1264 | 0.1431 | 0.2542 | 0.0538 | 0.0444 | 0.0205 | 0.0198 | 0.0245 |
| PCC $\uparrow$ | — | 0.5781 | 0.5738 | 0.5881 | 0.8581 | 0.9871 | 0.9930 | 0.9952 | 0.9954 | 0.9949 |

### 4.2 Shape Retrieval

Figure: (a) 2D Dataset.
Refer to caption: extracted/5973430/images/bone_star/bone_star_dists.png

Experiment setup. We now employ the PGW distance to distinguish between 2D and 3D shapes, similarly to as done in []. We use GW, LGW, and PGW as baselines for comparison against the results of our proposed LPGW. Given a series of shapes, we represent the shapes as mm-spaces $\mathbb{X}^{i}=(\mathbb{R}^{d},\|\cdot\|_{2},\mu^{i})$, where $\mu^{i}=\sum_{k=1}^{n^{i}}\alpha^{i}\delta_{x^{i}_{k}}$. For the GW and LGW method, we normalize the mass for the balanced mass constraint setting (i.e. $\alpha^{i}=\frac{1}{n^{i}}$), and for the PGW and LPGW methods we let $\alpha^{i}=\alpha$ for all the shapes, where $\alpha>0$ is a fixed constant. In this manner, we compute the pairwise distances between the shapes.

Next, using the approach given by [], 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(-\sigma D)$ 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 dataset presented in [], consisting of 8 classes each containing 20 shapes. The 3D dataset is given by [], which provides 100-200 complete shapes in each of 16 different classes, and for each complete shape, provides 26 corresponding “incomplete shapes.“ We choose 4 classes of shapes from this dataset, and for each we sample 15 complete and 45 incomplete shapes, yielding a total of 240 shapes. The datasets are visualized in Figure 6 in the Appendix.

**Table 2: Accuracy and wall-clock time comparison in shape retrieval experiment.**
|  | GW | PGW | LGW | LPGW<br>(ours) |
| --- | --- | --- | --- | --- |
| 2D Dataset |  |  |  |  |
| Accuracy $\uparrow$ | 98.1% | 96.2% | 93.7% | 97.5% |
| Time (s) $\downarrow$ | 43s | 39s | 0.4s | 0.5s |
| 3D Dataset |  |  |  |  |
| Accuracy $\uparrow$ | 92.5% | 93.8% | 92.5% | 93.7% |
| Time (m) $\downarrow$ | 203.0m | 203.6m | 1.3m | 1.8m |

##### Performance analysis.

We refer to Appendix J for full numerical details, parameter settings, and the visualization of the resulting confusion matrices. We visualize the resulting pairwise distance matrices in Figure 1. For the SVM experiments, on the 2D dataset, GW achieves the highest accuracy, 98.1%, while the second best method is LPGW, 97.5%. On the 3D dataset, PGW achieves the highest accuracy of of 93.8%, and LPGW achieves the next highest accuracy of 93.7%. We refer to Table 2 for details.

In addition, we report the wall-clock time required to compute all pairwise distances for each distance in Table 2. In both datasets, we observe that LGW/LPGW admit similar computational time, and are much faster than GW/PGW. This difference is more obvious on the 3D dataset. We note that when $\lambda$ is sufficiently large, the performance between the LPGW method and the LGW method are the same (see Appendix J for details).

### 4.3 Learning with Transform-Based Embeddings

In this experiment, we perform machine learning tasks using transform-based embeddings. Specifically, given training and testing datasets, we apply various transform-based embedding methods to both. Additionally, we assume that the testing data is randomly rotated and has been corrupted with random noise. The objective is to evaluate the robustness of machine learning models trained using the different embedding techniques. The full numerical details for this experiment can be found in Appendix K.

##### Baseline methods.

In this experiment, we consider several classical embedding methods, namely the LOT embedding [, , ], LGW embedding [], and our proposed LPGW embedding.

Figure: Figure 2: MNIST point cloud data.
Refer to caption: extracted/5973430/images/mnist/data.png

##### Dataset setup.

We adapt the [MNIST 2D point cloud dataset](https://www.kaggle.com/datasets/cristiangarcia/pointcloudmnist2d) for this experiment. Specifically, for each digit, we sample $N_{1}=500$ point clouds per class from the training set and $N_{2}=100$ point clouds per class from the testing set. Each point cloud is represented as a gm-space in $\mathbb{R}^{2}$ with measure
$\mu=\sum_{i=1}^{n}p_{i}\delta_{x_{i}}$, where $p_{i}>0,\forall i\in\{1,\dots,n\}$ are the pixel intensities provided by the original dataset. We normalize $p_{i}$ such that $\sum_{i=1}^{n}p_{i}=1$ for all sampled point clouds.

For each shape in the training set, we randomly rotate or flip the shape horizontally and add the transformed shape to the training set. As a result, each class contains $500\times 2=1000$ shapes in the training set. For each test shape, we first randomly rotate or flip the shape, and we then “corrupt” the shape by adding uniformly distributed noise. The mass of each added point is $\frac{1}{n}$, where $n$ is the number of points in the original shape, and the total mass of the added points is $\eta\in\{0,0.1,0.3,0.5\}$.

Figure: Figure 3: 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/flips are applied to the testing data, and $\eta$ denotes the total mass of noise points.
Refer to caption: extracted/5973430/images/mnist/embeddings_pca.png

##### Performance analysis.

For each method (LOT, LGW, and LPGW), we first compute the embeddings of the training data and optimize a classification 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 embeddings. The results are presented in Table 3. In this table, we observe that for the original test dataset, LOT achieves the highest accuracy at 89.0%. However, on the corrupted dataset, LOT’s performance drops significantly, classifying only 51% correctly when $\eta=0$ (no noise but with random rotation/flip) and falling dropping to 12.5% (i.e. random guessing) when $\eta>0.1$. LGW is more robust to the data with random rotations/flips, but its accuracy also reduces to random guessing as $\eta$ is increased. In contrast, LPGW embeddings exhibit substantially greater performance, with its accuracy ranging from 70-85% when $\eta\geq 0.1$. Additionally, we provide a t-SNE visualization of the embeddings produced by each method in Figure 3. From this figure, we can observe that when $\eta\geq 0.1$, LPGW embeddings show greater separability than those of LOT or LGW.

**Table 3: Accuracy and wall-clock time comparison for learning with transform-based embeddings experiments. We report each time as $t_{1}+t_{2}$, where $t_{1}$ is the time required to compute the training set embeddings and $t_{2}$ is the time required to compute the testing set embeddings.**
| Data | Method | LOT | LGW | LPGW (ours) |
| --- | --- | --- | --- | --- |
| no rotation | Accuracy $\uparrow$ | 89.0% | 82.5% | 82.5% |
| Time $\downarrow$ | 183s$+$16s | 405s$+$77s | 309s$+$84s |  |
| $\eta=0$ | Accuracy $\uparrow$ | 51.2% | 82.5% | 82.5% |
| Time $\downarrow$ | 183s$+$15s | 405s$+$77s | 309s$+$84s |  |
| $\eta=0.1$ | Accuracy $\uparrow$ | 13.4% | 17.0% | 81.8% |
| Time $\downarrow$ | 183s$+$17s | 405s$+$88s | 309s$+$91s |  |
| $\eta=0.3$ | Accuracy $\uparrow$ | 12.5% | 13.3% | 75.8% |
| Time $\downarrow$ | 183s$+$23s | 405s$+$145s | 309s$+$123s |  |
| $\eta=0.5$ | Accuracy $\uparrow$ | 12.5% | 12.5% | 72.9% |
| Time $\downarrow$ | 183s$+$27s | 405s$+$248s | 309s$+$168s |  |

## 5 Summary

In this paper, we propose the linear partial Gromov-Wasserstein (LPGW) embedding, a linearization technique for the PGW problem. Theoretically, we prove that LPGW admits a metric with certain assumptions, and numerically, we demonstrate that the utility of our proposed LPGW method in shape retrieval and learning with transform-based embedding tasks. We demonstrate that the LPGW-based method can preserve the partial matching property of PGW, while significantly improving computational efficiency.

## 6 Acknowledgment

This research was partially supported by the NSF CAREER Award No. 2339898.

## Appendix A Background: Linear Optimal Transportation Distance

The space of measures $\mathcal{P}_{2}(\mathbb{R}^{d})$ can be endowed with the two-Wasserstein metric $W_{2}$, and the resulting space defines a Riemannian manifold (see, e.g., []), which is referred to in the literature as
the Wasserstein space. Under the Monge mapping assumption, consider $\mu\in\mathcal{P}_{2}(\mathbb{R}^{d})$ and let $\mathrm{Tan}_{\mu}(\mathcal{P}_{2}(\mathbb{R}^{d}))$ denote the corresponding tangent space at $\mu$. Then, each tangent vector $v\in\mathrm{Tan}_{\mu}(\mathcal{P}_{2}(\mathbb{R}^{d}))$ can be regarded as an $L^{2}(\mu)-$function, that is, $v:\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that

$$ $\|v\|_{L^{2}(\mu)}^{2}=\int_{\mathbb{R}^{d}}\|v(x)\|^{2}\,\ d\mu(x)<\infty.$ $$

Given $\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$, suppose $\gamma=(\mathrm{id}\times T)_{\#}\mu$ is an optimal transportation plan for $W_{2}(\mu,\nu)$. Then, the logarithm mapping is defined by

$$ $\displaystyle\mathcal{P}_{2}(\mathbb{R}^{d})\ni\nu\mapsto v_{\gamma}:=(T- \mathrm{id})\in\mathrm{Tan}_{\mu}(\mathcal{P}_{2}(\mathbb{R}^{d})),$ (24) $$

and the resulting image $v_{\gamma}$ is the so-called Linear Optimal Transportation (LOT) embedding [].

The LOT embedding $v_{\gamma}$ is a “representation” of the measure $\nu$ and encodes the optimal displacement from the fixed measure $\mu$ to $\nu$. Indeed,

$$ $W_{2}^{2}(\mu,\nu)=\|v_{\gamma}-0\|_{L^{2}(\mu)}^{2}.$ $$

In general, given two probability measures $\nu^{1},\nu^{2}\in\mathcal{P}_{2}(\mathbb{R}^{d})$, if $\gamma^{1},\gamma^{2}$ are optimal solutions for $W_{2}(\mu,\nu^{1}),W_{2}(\mu,\nu^{2})$ of the form (2),
one can use the following so-called LOT distance to approximate the original OT distance $W_{2}(\nu^{1},\nu^{2})$ []:

$$ $LOT_{2}^{2}(\nu^{1},\nu^{2};\mu,\gamma^{1},\gamma^{2}):=\|v_{\gamma^{1}}-v_{ \gamma^{2}}\|_{L^{2}(\mu)}^{2}.$ (25) $$

The above definition relies on the Monge mapping assumption. In [, ], 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 a geodesic in the classical OT setting. Suppose $\gamma$ is an optimal transportation plan for the OT problem between $\mu,\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$. Then, the geodesic from $\mu$ to $\nu$ is defined by

$$ $\displaystyle t\mapsto\gamma_{t}:=((1-t)\pi_{X}+t\pi_{Y})_{\#}\gamma\qquad(0 \leq t\leq 1).$ (26) $$

###### Remark A.1 .

In the particular case where $\gamma$ is of the form $\gamma=(\mathrm{id}\times T)_{\#}\mu$, the above formula reduces to

$$ $t\mapsto((1-t)\mathrm{id}+tT)_{\#}\mu\qquad(0\leq t\leq 1).$ $$

###### Remark A.2 .

In the discrete case, $\mu=\sum_{i=1}^{n}p_{i}\delta_{x_{i}}$ and $\nu=\sum_{j=1}^{m}q_{j}\delta_{y_{j}}$. By abuse of notation, let $\gamma\in\Gamma^{*}(\mu,\nu)$ be interpreted as a matrix.
Then, the above geodesic becomes

$$ $t\mapsto\sum_{i=1}^{n}\sum_{j=1}^{m}\delta_{(1-t)x_{i}+ty_{j}}\gamma_{ij} \qquad(0\leq t\leq 1).$ $$

Given curves $\{\gamma^{1}_{t}\}_{t\in[0,1]},\{\gamma^{2}_{t}\}_{t\in[0,1]}$ both originating from $\mu$, we claim they are equivalent if there exists $\epsilon>0$ such that for all $t\in[0,\epsilon]$, $\gamma_{t}^{1}=\gamma_{t}^{2}$. Let $G_{\mu}$ denote the set of all the equivalence classes. The generalized tangent space at $\mu$, denoted by $\text{Tan}_{\mu}^{g}(\mathcal{P}_{2}(\mathbb{R}^{d}))$, is defined as the closure of $G_{\mu}$ (see [] for details).

Now, given $\nu^{1},\nu^{2}\in\mathcal{P}_{2}(\mathbb{R}^{d})$, let $\gamma^{1},\gamma^{2}$ be some optimal transportation plan in $\Gamma^{*}(\mu,\nu^{1})$, $\Gamma^{*}(\mu,\nu^{2})$, respectively. We define the following distance, defined on the space $\text{Tan}_{\mu}^{g}\mathcal{P}_{2}(\mathbb{R}^{d})$, as the LOT distance conditioned on $\gamma^{1},\gamma^{2}$:

$$ $\displaystyle LOT_{2}^{2}(\nu^{1},\nu^{2};\mu,\gamma^{1},\gamma^{2}):=\inf_{ \gamma\in\Gamma(\gamma^{1},\gamma^{2};\mu)}\int_{\mathbb{R}^{3d}}\|y^{1}-y^{2} \|^{2}d\gamma(x,y^{1},y^{2}).$ (27) $$

where $\Gamma(\gamma^{1},\gamma^{2};\mu):=\{\gamma\in\mathcal{P}(\mathbb{R}^{3d}):(
\pi_{01})_{\#}\gamma=\gamma^{1},(\pi_{02})_{\#}\gamma=\gamma^{2}\}$, where $\pi_{01}(x,y^{1},y^{2})=(x,y^{1})$, $\pi_{02}(x,y^{1},y^{2})=(x,y^{2})$.

###### Remark A.3 .

When $\gamma^{1}=(\mathrm{id}\times T^{1})_{\#}\mu,\gamma^{2}=(\mathrm{id}\times T^{
2})_{\#}\mu$ for some mappings $T^{1},T^{2}$, there exists only one element in $\Gamma(\gamma^{1},\gamma^{2};\mu)$, which is
$(\mathrm{id}\times T^{1}\times T^{2})_{\#}\mu$. Thus, the right-hand side of (27) becomes

$$ $\displaystyle\|T^{1}(x)-T^{2}(x)\|_{L^{2}(\mu)}^{2}.$ (28) $$

That is, (27) and (25) coincide.

Finally, to formulate a distance that is independent of the optimal transportation plans $\gamma^{1},\gamma^{2}$, we define the LOT distance between $\nu^{1},\nu^{2}$ with respect to $\mu$ by

$$ $\displaystyle LOT_{2}^{2}(\nu^{1},\nu^{2};\mu):=\inf_{\begin{subarray}{c} \gamma^{1}\in\Gamma^{*}(\mu,\nu^{1})\\ \gamma^{2}\in\Gamma^{*}(\mu,\nu^{2})\end{subarray}}LOT_{2}^{2}(\nu^{1},\nu^{2} ;\mu,\gamma^{1},\gamma^{2}).$ (29) $$

Barycentric projection.
The above LOT distance is complicated to compute. To simplify the computation, [] introduces the “barycentric projection” method that we will recall here.

First, we review some basic concepts in measure theory.
Given
$\gamma\in\mathcal{P}(\mathbb{R}^{2d})$, with $\pi_{1\#}\gamma=\mu$, where $\pi_{1}:\mathbb{R}^{2d}\to\mathbb{R}^{d}$ is given by $\pi_{1}(x,y)=x$, by the disintegration theorem (see, for e.g., [, Thm 5.3.1] and [, Theorem 6]), there exists a $\mu-$a.e. uniquely defined family of probability measures $\{\gamma(\cdot|x)\}_{x\in\mathbb{R}^{d}}\subset\mathcal{P}(\mathbb{R}^{d})$, such that

$$ $\displaystyle\int_{\mathbb{R}^{2d}}\phi(x,y)d\gamma(x,y)=\int_{\mathbb{R}^{d}} \int_{\mathbb{R}^{d}}\phi(x,y)d\gamma(y|x)d\mu(x),\qquad\forall\phi\in C_{0}( \mathbb{R}^{2d}).$ (30) $$

In this paper, we call $\gamma(\cdot|x)$ the disintegration of $\gamma$ with respect to its first marginal ($\mu$), given $x$ (for each $x\in\text{supp}(\mu)$).

The barycentric projection map $\mathcal{T}_{\gamma}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ of $\gamma$ is defined by

$$ $\displaystyle\mathcal{T}_{\gamma}(x):=\arg\min_{y\in Y}\int_{Y}\|y-y^{\prime} \|^{2}\,d\gamma(y^{\prime}|x^{\prime})=\int_{Y}y^{\prime}d\gamma(y^{\prime}|x^ {\prime}).$ (31) $$

Note that the second equality holds since the distance between $y,y^{\prime}$ is simply the quadratic Euclidean distance. In the third term, we have a vector integration.

Given an optimal transportation plan $\gamma\in\Gamma^{*}(\mu,\nu)$, we define
$\widetilde{\nu}_{\gamma}:=(\mathcal{T}_{\gamma})_{\#}\mu$.

###### Proposition A.4 (Prop. II.4 [ 28 ] ) .

If $\gamma\in\Gamma^{*}(\mu,\nu)$, then the transportation plan induced by the barycentric projection map $\mathcal{T}_{\gamma}$, denoted as $\widetilde{\gamma}:=(\mathrm{id}\times\mathcal{T}_{\gamma})_{\#}\mu$ is optimal for the OT problem $W_{2}(\mu,\widetilde{\nu}_{\gamma})$.

In addition, if $\gamma=(\mathrm{id}\times T)_{\#}\mu$
satisfies the Monge mapping assumption, then $\mathcal{T}_{\gamma^{*}}=T$ $\mu$-a.e. and is a Monge map.

Thus, if we replace $\nu$ by $\widetilde{\nu}_{\gamma}$, the OT problem $W_{2}(\mu,\widetilde{\nu}_{\gamma})$ can be solved by the map $\mathcal{T}_{\gamma}$. Based on this property, given $\nu^{1},\nu^{2}\in\mathcal{P}(\mathbb{R}^{d})$, consider optimal transportation plans $\gamma^{1}\in\Gamma^{*}(\mu,\nu^{1}),\gamma^{2}\in\Gamma(\mu,\nu^{2})$, then define the following approximated LOT distance (aLOT) to estimate $W_{2}(\nu^{1},\nu^{2})$:

$$ $\displaystyle aLOT^{2}_{2}(\nu,\nu;\mu):=\inf_{\begin{subarray}{c}\gamma^{1} \in\Gamma^{*}(\mu,\nu^{1})\\ \gamma^{2}\in\Gamma^{*}(\mu,\nu^{2})\end{subarray}}LOT_{2}^{2}(\widetilde{\nu} _{\gamma^{1}},\widetilde{\nu}_{\gamma^{2}};\mu,\widetilde{\gamma}^{1}, \widetilde{\gamma}^{2})=\inf_{\begin{subarray}{c}\gamma^{1}\in\Gamma^{*}(\mu, \nu^{1})\\ \gamma^{2}\in\Gamma^{*}(\mu,\nu^{2})\end{subarray}}\|\mathcal{T}_{\gamma^{1}}- \mathcal{T}_{\gamma^{2}}\|_{L^{2}(\mu)}^{2}.$ (32) $$

Note, in most of the literature, $aLOT_{2}$ is referred to as $LOT_{2}$, and for simplicity, it is approximated by any pair of optimal transportation plans $(\gamma^{1},\gamma^{2})$.

###### Remark A.1 .

###### Remark A.2 .

###### Remark A.3 .

###### Proposition A.4 (Prop. II.4 [ 28 ] ) .

## Appendix B Background: Linear Gromov-Wasserstein Distance

Let $X\subset\mathbb{R}^{d_{0}}$ be a compact and convex subset, and consider a Borel measure $\mu$ on $X$. A symmetric function $g_{X}:X^{\otimes 2}\to\mathbb{R}$ with $\int_{X^{\otimes 2}}g_{X}(x,x^{\prime})d\mu^{\otimes 2}<\infty$ is called a gauge function. The space of all gauge functions is denoted as
$L_{sym}^{2}(X^{\otimes 2},\mu^{\otimes 2})$. In this paper, without specific description, we default set $g_{X}$ to be continuous (thus, Lipschitz continuous) on $X$. For example $g_{X}(x,x^{\prime})=\|x-x^{\prime}\|^{2}$ or $g_{X}(x,x^{\prime})=x^{\top}x^{\prime}$.
The space $\mathbb{X}=(X,g_{X},\mu)$ is called a gauged measure space (gm-space), which can be regarded as a generalized version of an mm-space. The GW problem between two gm-spaces $\mathbb{X},\mathbb{Y}$ is:

$$ $\displaystyle GW^{2}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)} \int_{(X\times X)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(y,y{{}^{\prime}})|^{2 }d\gamma^{\otimes 2}.$ $$

###### Lemma B.1 .

There exists a minimizer $\gamma$ of $GW(\mathbb{X},\mathbb{Y})$ in $\Gamma(\mu,\nu)$.

The existence of minimizers of $GW(\mathbb{X},\mathbb{Y})$ could be shown by a standard compact-SNEss argument, see for instance, Lemma 10.3 in [].
Suppose $\gamma$ is one optimal solution of the above generalized GW problem. The geodesic between $\mathbb{X}$ and $\mathbb{Y}$ is defined by

$$ $\displaystyle t\mapsto\gamma_{t}:=(X\times Y,(1-t)g_{X}+tg_{Y},\gamma),t\in[0, 1].$ (33) $$

Note, even if $g_{X},g_{Y}$ are metrics, $\gamma_{t}$ is a gm-space (rather than mm-space), and this is the reason mm-space is generalized to gm-spaces in [] and in this paper.

Two gm-spaces $\mathbb{X},\mathbb{Y}$ are “equivalent” if $GW^{2}(\mathbb{X},\mathbb{Y})=0$.
Let $[\mathbb{X}]$ denote the equivalence class of $\mathbb{X}$.
The tangent space at $[\mathbb{X}]$ is defined by

$$ $\displaystyle\text{Tan}_{\mathbb{X}}:=\left(\bigcup_{(X^{\prime},g_{X^{\prime} },\mu^{\prime})\in[\mathbb{X}]}L_{sym}^{2}(X^{\prime}\times X^{\prime},\mu{{}^ {\prime}}^{\otimes 2})\right)/\sim$ (34) $$

where, if
$\mathbb{T}_{k_{1}}=(X^{1},g_{X^{1}},\mu^{1}),\mathbb{T}_{k_{2}}=(X^{2},g_{X^{2
}},\mu^{2})\in[\mathbb{X}]$ are representatives of $k_{1}\in L_{sys}^{2}((X^{1})^{\otimes 2},(\mu^{1})^{\otimes 2}),k_{2}\in L_{
sys}^{2}((X^{2})^{\otimes 2},(\mu^{2})^{\otimes 2})$, we say that $k_{1}\sim k_{2}$ if there exists $\gamma\in\Gamma(\mathbb{X}^{1},\mathbb{X}^{2})$ such that $GW(\mathbb{X}^{1},\mathbb{X}^{2})=0.$ (We refer to [] for more details.)

Given spaces $\mathbb{X}^{1}:=(X\times Y^{1},d_{X},\gamma^{1}),\mathbb{X}^{2}:=(X\times Y^{2
},d_{X},\gamma^{2})$ where $\gamma^{1},\gamma^{2}$ are optimal transportation plans for $GW(\mathbb{X},\mathbb{Y}^{1}),GW(\mathbb{X},\mathbb{Y}^{2})$, respectively, it is straightforward to verify

$$ $GW(\mathbb{X},\mathbb{X}^{1})=GW(\mathbb{X},\mathbb{X}^{2})=0,$ $$

thus $\mathbb{X}^{1},\mathbb{X}^{2}\in[\mathbb{X}]$.

In addition, choose $k_{1}\in L_{sys}^{2}(X^{1})^{\otimes 2},(\gamma^{1})^{\otimes 2}),k_{2}\in L_{
sys}^{2}((X^{2})^{\otimes 2},(\gamma^{2})^{\otimes 2})$, then we have

$$ $k_{1},k_{2}\in\text{Tan}_{\mathbb{X}},$ $$

where $\Gamma^{*}(\mathbb{T}_{k_{1}},\mathbb{T}_{k_{2}})$ is same to $\Gamma^{*}(\gamma^{1},\gamma^{2})$ in $GW(\mathbb{X}^{1},\mathbb{X}^{2})$.

Their inner product distance is defined by

$$ $D^{2}(k_{1},k_{2}):=\inf_{\gamma\in\Gamma^{*}(\mathbb{T}_{k_{1}},\mathbb{T}_{k _{2}})}\|k_{1}-k_{2}\|^{2}_{\gamma^{\otimes 2}}.$ $$

Now, we set
$k_{1}=k_{\gamma^{1}}=g_{Y^{1}}-g_{X},k_{2}=k_{\gamma^{2}}=g_{Y^{2}}-g_{X}$.
Thus, the linear GW distance between $\mathbb{Y}^{1}$ and $\mathbb{Y}^{2}$ given $\gamma^{1},\gamma^{2}$ is defined by the above inner product distance. That is,

$$ $\displaystyle\text{LGW}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1}, \gamma^{2})$ $\displaystyle:=D(k_{1},k_{2})$ $\displaystyle=\inf_{\gamma\in\Gamma^{*}(\mathbb{T}_{k_{1}},\mathbb{T}_{k_{2}}) }\|k_{1}-k_{2}\|^{2}_{L^{2}(\gamma^{\otimes 2})}$ $\displaystyle=\inf_{\gamma\in\Gamma(\gamma^{1},\gamma^{2};\mu)}\int_{(X\times Y ^{1}\times Y^{2})^{\otimes 2}}\|g_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})-g_{Y^{2}}( y^{2},y^{2^{\prime}})\|^{2}d\gamma^{\otimes 2}$ (35) $$

where $\Gamma(\gamma^{1},\gamma^{2};\mu):=\{\gamma\in\mathcal{P}(X\times Y^{1}\times Y
^{2}):(\pi_{X,Y^{1}})_{\#}\gamma=\gamma^{1},(\pi_{X,Y^{2}})_{\#}\gamma=\gamma^
{2}\}$. The third line follows from Proposition III.1 in [] (or equivalently from the identity (39) in the next section).
Note, under Monge mapping assumptions, $\gamma^{1}=(\mathrm{id}\times T^{1})_{\#}\mu,\gamma^{2}=(\mathrm{id}\times T^{
2})_{\#}\mu$, $\Gamma(\gamma^{1},\gamma^{2};\mu)=\{(\mathrm{id}\times T^{1}\times T^{2})_{\#}\mu\}$ and the above distance
(35) coincides with (7).

The original Linear Gromov-Wasserstein distance between $\mathbb{Y}^{1}$ and $\mathbb{Y}^{2}$ with respect to $\mathbb{X}$ is defined as

$$ $\displaystyle\text{LGW}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}):=\inf_{ \begin{subarray}{c}\gamma^{1}\in\Gamma(\mathbb{X},\mathbb{Y}^{1})\\ \gamma^{2}\in\Gamma(\mathbb{X},\mathbb{Y}^{2})\end{subarray}}LGW(\mathbb{Y}^{1 },\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{2}).$ (36) $$

###### Lemma B.1 .

## Appendix C 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 [, ].

Consider metric measure spaces $\mathbb{X}$ and $\mathbb{Y}$, with measures given by $\mu=\sum_{i=1}^{n}p_{i}\delta_{x_{i}}$ and $\nu=\sum_{j=1}^{m}q_{j}\delta_{y_{j}}$, respectively. To achieve an $\epsilon-$accurate solution for the GW problem, the number of required iterations of the FW algorithm is

$$ $\displaystyle\frac{\max\Bigg{\{}2L_{1},2\cdot n^{2}m^{2}\max(\{2(C^{X})^{2}+2( C^{Y})^{2}\})\Bigg{\}}^{2}}{\epsilon^{2}},$ $$

and for PGW is

$$ $\displaystyle\frac{\max\Bigg{\{}2L_{1},2\min(|\mathrm{p}|,|\mathrm{q}|)\cdot n ^{2}m^{2}\max(\{2(C^{X})^{2}+2(C^{Y})^{2},2\lambda\})\Bigg{\}}^{2}}{\epsilon^{ 2}}.$ $$

Here, $L_{1}$ is a value determined by the initial guess $\gamma^{0}$ used in the FW algorithm, and $C^{X},C^{Y}$ are the corresponding cost matrices for $\mathbb{X},\mathbb{Y}$. Note, since the largest value for $\lambda$ is $2\lambda=\max(2(C^{X})^{2},2(C^{Y})^{2})$, the above two quantities coincide.

In each iteration of FW, we are required to solve an OT/POT problem, whose complexity is $\mathcal{O}(nm(n+m))$ []. Thus, the theoretical time complexity to solve GW/PGW is $\mathcal{O}(\frac{1}{\epsilon^{2}}nm(n+m)n^{2}m^{2})$.

Given $K$ mm-spaces, $\mathbb{X}_{1},\ldots\mathbb{X}_{K}$, then, computing their pairwise GW/PGW distances requires
$\binom{K}{2}\cdot\mathcal{O}(\frac{1}{\epsilon^{2}}nm(n+m)n^{2}m^{2})$. Meanwhile, computing the pairwise LPGW distances between them only requires

$$ $K\mathcal{O}(\frac{1}{\epsilon^{2}}nm(n+m)n^{2}m^{2})+\binom{K}{2}(n^{2}_{0}),$ $$

where the term $n^{2}_{0}$ is the time complexity to compute the distance between two embeddings and $n_{0}$ is the size of reference space. In general, we would like to set $n_{0}$ to be the mean/median/maximum of the sizes of $K$ mm-spaces, and thus this term can be ignored as compared to the first term.

###### Remark C.1 .

We generally impose a fixed limit on the maximum number of iterations to be used in the FW algorithm (e.g., in PythonOT [], 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 $\mathcal{O}(nm(n+m))$.

###### Remark C.1 .

## Appendix D Proof of Proposition 2.1

### D.1 Clarification

Although statements 1 and 2 in this proposition are not explicitly introduced in [], 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 [].

### D.2 Conjecture and Understanding

Regarding statement 3, we conjecture that this conclusion can be extended to the case where $g_{X}$ and $g_{Y}$ are squared Euclidean distances. However, this statement may not hold for other gauge mappings. In our understanding, for general gauge mappings, achieving a similar result to 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 mapping, and the generalized version of statement 3 is left for future work.

### D.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 $\gamma^{*}$ satisfies the Monge mapping, i.e.
$\gamma^{*}=(\mathrm{id}\times T)_{\#}\mu$, where $T:X\to Y$, and $\gamma^{0}=(\mathrm{id}\times\mathrm{id})_{\#}\mu\in\Gamma^{*}(\mathbb{X},
\mathbb{X})$.
Then $k_{\gamma^{0}}\equiv 0$ and thus

$$ $\displaystyle LGW(\mathbb{X},\mathbb{Y};\mathbb{X},\gamma^{0},\gamma^{*})$ $\displaystyle=\|k_{\gamma^{*}}-k_{\gamma^{0}}\|^{2}_{\mu^{\otimes 2}}=\|k_{ \gamma^{*}}\|^{2}_{\mu^{\otimes 2}}$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(T(x),T( x^{\prime}))|^{2}d\mu^{\otimes 2}$ $\displaystyle=GW(\mathbb{X},\mathbb{Y}).$ $$

Proof in the general case.
Consider $\gamma^{0}\in\Gamma^{*}(\mathbb{X},\mathbb{X})$, and $\gamma\in\Gamma(\gamma^{0},\gamma^{*})$.

We claim the following lemma

###### Lemma D.1 .

Choose $\gamma^{0}\in\Gamma^{*}(\mathbb{X},\mathbb{X})$, $\gamma^{*}\in\mathcal{M}_{+}(\mathbb{X},\mathbb{Y})$, for each $\gamma\in\Gamma(\gamma^{0},\gamma^{*};\mu)$,
we have the following identity:

$$ $\displaystyle\int_{(X\times X\times Y)^{\otimes 2}}|g_{X}(x^{2},x^{2}{{}^{ \prime}})-g_{Y}(y,y^{\prime})|^{2}d(\gamma)^{\otimes 2}((x^{1},x^{1}{{}^{ \prime}}),(x^{2},x^{2}{{}^{\prime}}),(y,y^{\prime}))$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(y,y^{ \prime})|^{2}d(\gamma^{*})^{\otimes 2}((x,x^{\prime}),(y,y^{\prime}))$ (37) $$

###### Proof of Lemma ( D.1 ).

Since

$$ $GW(\mathbb{X},\mathbb{X})=\int_{(X\times X)^{\otimes 2}}|g_{X}(x^{1},x^{1}{{}^ {\prime}})-g_{X}(x^{2},x^{2}{{}^{\prime}})|^{2}d\gamma^{0}=0,$ $$

we have

$$ $g_{X}(x^{1},x^{1}{{}^{\prime}})-g_{X}(x^{2},x^{2}{{}^{\prime}})=0,\quad\gamma^ {0}-a.s.$ $$

For convenience, let $X^{1}=X^{2}=X$ be independent copies of $X$. We have:

$$ $\displaystyle\int_{(X\times X\times Y)^{\otimes 2}}|g_{X}(x^{2},x^{2}{{}^{ \prime}})-g_{Y}(y,y{{}^{\prime}})|^{2}d\gamma^{\otimes 2}((x^{1},x^{1}{{}^{ \prime}}),(x^{2},x^{2}{{}^{\prime}}),(y,y{{}^{\prime}}))$ $\displaystyle=\int_{(X\times X^{0}\times Y)^{\otimes 2}}|g_{X}(x^{2},x^{2}{{}^ {\prime}})-g_{X}(x^{1},x^{1}{{}^{\prime}})+g_{X}(x^{1},x^{1}{{}^{\prime}})-g_{ Y}(y,y{{}^{\prime}})|^{2}d\gamma^{\otimes 2}((x^{1},x^{1}{{}^{\prime}})(x^{2}, x^{2}{{}^{\prime}}),(y,y{{}^{\prime}}))$ $\displaystyle=\int_{(X^{1}\times X^{2})^{\otimes 2}}\left[\int_{(Y)^{\otimes 2 }}|g_{X}(x^{2},x^{2}{{}^{\prime}})-g_{X}(x^{1},x^{1}{{}^{\prime}})+g_{X}(x^{1} ,x^{1}{{}^{\prime}})-g_{Y}(y,y^{\prime})|^{2}\right.$ $\displaystyle\left.\qquad\qquad d\gamma_{Y|(X^{1},X^{2})}^{\otimes 2}((y,y{{}^ {\prime}})|(x^{1},x^{1}{{}^{\prime}}),(x^{2},x^{2}{{}^{\prime}}))\right]d( \gamma^{0})^{\otimes 2}((x^{1},x^{1}{{}^{\prime}}),(x^{2},x^{2}{{}^{\prime}}))$ (38) $\displaystyle=\int_{(X^{1}\times X^{2})^{\otimes 2}}\left[\int_{Y^{\otimes 2}} |g_{X}(x^{1},x^{1}{{}^{\prime}})-g_{Y}(y,y{{}^{\prime}})|^{2}d\gamma_{Y|X^{1}, X^{2}}^{\otimes 2}((y,y{{}^{\prime}})|(x^{1},x^{1}{{}^{\prime}}),(x^{2},x^{2}{ {}^{\prime}})\right]$ $\displaystyle\qquad\qquad d(\gamma^{0})^{\otimes 2}((x^{1},x^{1}{{}^{\prime}}) ,(x^{2},x^{2}{{}^{\prime}}))$ $\displaystyle=\int_{(X^{1}\times Y)^{\otimes 2}}|g_{X}(x^{1},x^{1}{{}^{\prime} })-g_{Y}(y,y{{}^{\prime}})|^{2}d\gamma^{\otimes 2}((x^{1},x^{2},y),(x^{1}{{}^{ \prime}},x^{2}{{}^{\prime}},y{{}^{\prime}}))$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(y,y{{}^ {\prime}})|^{2}d(\gamma^{*})^{\otimes 2}((x,y),(x^{\prime},y{{}^{\prime}}))$ (39) $$

where in (38) $\gamma_{Y|X^{1},X^{2}}(\cdot|x^{1},x^{2})$ is the disintegration of $\gamma$ with respect to $(\pi_{X^{1},X^{2}})_{\#}\gamma=\gamma^{0}$. ∎

Based on the identity (37) and the fact $\gamma^{1}$ is optimal for problem $GW(\mathbb{X},\mathbb{Y})$, we have:

$$ $\displaystyle LGW(\mathbb{X},\mathbb{Y};\mathbb{X},\gamma^{0},\gamma^{*})$ $\displaystyle=\inf_{\gamma\in\Gamma(\gamma^{0},\gamma^{*})}\int_{(X\times X \times Y)^{\otimes 2}}|d_{X}(x^{0},x^{0}{{}^{\prime}})-d_{Y}(y,y{{}^{\prime}}) |^{2}d\gamma^{\otimes 2}((x,x^{\prime}),(x^{0},x^{0}{{}^{\prime}}),(y,y{{}^{ \prime}}))$ $\displaystyle=\inf_{\gamma\in\Gamma(\gamma^{0},\gamma^{*})}GW(\mathbb{X}, \mathbb{Y})$ $\displaystyle=GW(\mathbb{X},\mathbb{Y}),$ $$

and we have completed the proof.

###### Lemma D.1 .

###### Proof of Lemma ( D.1 ).

### D.4 Proof of Proposition 2.1 : Part 2

In this case, $\gamma^{*}=(\mathrm{id}\times T)_{\#}\mu$, for each $x\in\text{Supp}(\mu)$, we have that the disintegration of $\gamma^{*}$ with respect to its first marginal $(\pi_{X})_{\#}\gamma^{*}=\gamma_{X}^{*}$, given first component is $x$, is

$$ $\gamma^{*}_{Y|X}(\cdot_{2}|y^{\prime})=\delta(\cdot_{2}-T(x)),$ $$

where $\delta$ is the Dirac measure. Thus, for all $x\in\text{supp}(\mu)$, we have:

$$ $\mathcal{T}_{\gamma^{*}}(x)=\int_{Y}yd\gamma^{*}_{Y|X}(y|x)=\int_{Y}y\,d\delta (y-T(x))=T(x).$ $$

where the last equality holds from the fact $T(x)\in\text{supp}(\nu)\subset Y$.
Therefore, $\mathcal{T}_{\gamma^{*}}=T$ $\mu-$a.s.
Since $T_{\#}\mu=\nu$, we have $\widetilde{\nu}_{\gamma^{*}}:=(\mathcal{T}_{\gamma^{*}})_{\#}\mu=T_{\#}\mu=\nu$.

### D.5 Proof of Proposition 2.1 : Part 3

#### D.5.1 Proof in the Discrete Case

We first demonstrate the proof in the following simplified discrete case: Suppose $g_{X}(x,x^{\prime})=x^{\top}x^{\prime}$ and $g_{Y}(y,y^{\prime})=y^{\top}y^{\prime}$, and consider

$$ $\mu=\sum_{i=1}^{n}p_{i}\delta_{x_{i}},\qquad\nu=\sum_{j=1}^{m}q_{j}\delta_{y_{ j}}\qquad\text{with }\sum_{i=1}^{n}p_{i}=1=\sum_{j=1}^{m}q_{k}.$ $$

In addition, we suppose that
$X$, $Y$ are compact convex sets which contains 0 0 (besides containing $\{x_{1},\dots,x_{n}\}$ and $\{y_{1},\dots,y_{m}\}$, respectively).

Let $\gamma^{*}\in\Gamma^{*}(\mathbb{X},\mathbb{Y})$ be an optimal transportation plan. Then the corresponding barycentric projected measure is given by

$$ $\widetilde{\nu}=\widetilde{\nu}_{\gamma^{*}}:=\sum_{i=1}^{n}p_{i}\delta_{ \widetilde{y}_{i}},\qquad\text{where }\widetilde{y}_{i}:=\frac{1}{p_{i}}\sum_{ j=1}^{m}\gamma^{*}_{ij}y_{j}.$ $$

By convexity, $\widetilde{y}_{1},\ldots,\widetilde{y}_{n}\in Y$. Thus $\widetilde{\mathbb{Y}}:=\widetilde{\mathbb{Y}}_{\gamma^{*}}=(X,g_{Y},
\widetilde{\nu})$.

Then, it induces a transportation plan $\widetilde{\gamma}^{*}:={\rm diag}(p_{1}^{0},\cdots,p_{n}^{0})\in\mathbb{R}_{+
}^{{n}\times n}$ with first and second marginals $\mu$ and $\widetilde{\nu}$, respectively. We will show that for any transportation plan $\widetilde{\gamma}\in\Gamma(\mu,\widetilde{\nu})$, it holds that

$$ $C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}})\leq C(\widetilde{ \gamma};\mathbb{X},\widetilde{\mathbb{Y}}),$ $$

where

$$ $C(\gamma;\mathbb{X},\mathbb{Y})=\sum_{i,i^{\prime}=1}^{n}\sum_{j,j^{\prime}=1} ^{m}(x_{i}^{\top}x_{i^{\prime}}-y_{j}^{\top}y_{j^{\prime}})^{2}\gamma_{ij} \gamma_{i^{\prime}j^{\prime}},$ $$

in other words, we will show that $\widetilde{\gamma}^{*}$ is optimal for ${\rm GW}(\mathbb{X},\widetilde{\mathbb{Y}})$.

First, we notice that $(\widetilde{\gamma}^{*})^{-1}={\rm diag}(1/p_{1}^{0},\cdots,1/p_{n}^{0})$. Then, we set

$$ $\gamma:=\widetilde{\gamma}(\widetilde{\gamma}^{*})^{-1}\gamma^{*}\in\mathbb{R} _{+}^{n\times m}.$ $$

Secondly, we check that ${\gamma}\in\Gamma(\mu,\nu).$ In fact, let $p=(p_{1},\dots,p_{n})$, $q=(q_{1},\dots,q_{m})$ be the vectors of the weights of finite discrete measures $\mu$ and $\nu$, respectively, then, since
$\gamma^{*}1_{m}=p$ and $\tilde{\gamma}^{T}1_{n}=q$, we have

$$ $\displaystyle\gamma 1_{m}$ $\displaystyle=\widetilde{\gamma}(\widetilde{\gamma}^{*})^{-1}\gamma^{*}1_{m}= \widetilde{\gamma}(\widetilde{\gamma}^{*})^{-1}p=\widetilde{\gamma}1_{n}=q,$ $\displaystyle\gamma^{\top}1_{n}$ $\displaystyle=(\gamma^{*})^{\top}(\widetilde{\gamma}^{*})^{-1}\widetilde{ \gamma}^{\top}1_{n}=(\gamma^{*})^{\top}(\widetilde{\gamma}^{*})^{-1}q=(\gamma^ {*})^{\top}1_{m}=p.$ $$

Lastly, we compute the costs as follows:

$$ $\displaystyle C(\gamma^{*};\mathbb{X},\mathbb{Y})$ $\displaystyle=\sum_{i,i^{\prime}=1}^{n}(x_{i}^{\top}x_{i^{\prime}})^{2}p_{i}p_ {i^{\prime}}+\sum_{j,j^{\prime}=1}^{m}(y_{j}^{\top}y_{j^{\prime}})^{2}q_{j}q_{ j^{\prime}}-2\sum_{i,i^{\prime}=1}^{n}\sum_{j,j^{\prime}=1}^{m}(x_{i}^{\top}x_ {i^{\prime}})(y_{j}^{\top}y_{j^{\prime}})\gamma^{*}_{ij}\gamma^{*}_{i^{\prime} j^{\prime}}$ $\displaystyle=J_{1}-2\sum_{i,i^{\prime}=1}^{n}\sum_{j,j^{\prime}=1}^{m}(x_{i}^ {\top}x_{i^{\prime}})(y_{j}^{\top}y_{j^{\prime}})\gamma^{*}_{ij}\gamma^{*}_{i^ {\prime}j^{\prime}}.$ $$

where $J_{1}=\sum_{i,i^{\prime}=1}^{n}(x_{i}^{\top}x_{i^{\prime}})^{2}p_{i}p_{i^{
\prime}}+\sum_{j,j^{\prime}=1}^{m}(y_{j}^{\top}y_{j^{\prime}})^{2}q_{j}q_{j^{
\prime}}$ is independent of $\gamma^{*}$.
By the multi-linearity of the last term in the identity, we can show

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}})$ $\displaystyle=J_{2}-2\sum_{i,i^{\prime}=1}^{n}\sum_{\ell,\ell^{\prime}=1}^{n}( x_{i}^{\top}x_{i^{\prime}})(\widetilde{y}_{\ell}^{\top}\widetilde{y}_{\ell^{ \prime}})\widetilde{\gamma}_{i\ell}^{*}\widetilde{\gamma}_{i^{\prime},\ell^{ \prime}}^{*}$ (40) $\displaystyle=J_{2}-2\sum_{i,i^{\prime}=1}^{n}\sum_{\ell,\ell^{\prime}=1}^{n}x _{i}^{\top}x_{i^{\prime}}\sum_{j,j^{\prime}=1}^{m}\left(\frac{\gamma^{*}_{\ell j }y_{j}^{\top}}{p_{\ell}}\frac{\gamma^{*}_{\ell^{\prime}j^{\prime}}y_{j^{\prime }}}{p_{\ell^{\prime}}}\right)\widetilde{\gamma}_{i\ell}\widetilde{\gamma}_{i^{ \prime}\ell^{\prime}}$ $\displaystyle=J_{2}-J_{1}+C(\gamma^{*};\mu,\nu^{1}),$ $$

where $J_{2}=\sum_{i,i^{\prime}=1}^{n}(x_{i}^{\top}x_{i^{\prime}})^{2}p_{i}p_{i^{
\prime}}^{0}+\sum_{\ell,\ell^{\prime}=1}^{n}(\widetilde{y}_{\ell}^{\top}
\widetilde{y}_{\ell^{\prime}})^{2}p_{\ell}^{0}p_{\ell^{\prime}}^{0}$.
Similarly, we can compute

$$ $\displaystyle C(\widetilde{\gamma};\mathbb{X},\widetilde{\mathbb{Y}})=J_{2}-J_ {1}+C(\gamma;\mathbb{X},\mathbb{Y})$ (41) $$

The optimality of $\gamma^{*}$ together with identities (40) and (41) implies that $C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}})\leq C(\widetilde{
\gamma};\mathbb{X},\widetilde{\mathbb{Y}}).$

#### D.5.2 Proof in the General Case

Similar to the discrete case, given $\gamma^{*}\in\Gamma^{*}(\mathbb{X},\mathbb{Y})$, the barycentric projeciton is given by

$$ $\mathcal{T}_{\gamma^{*}}(x)=\int_{Y}y\,d\gamma^{*}_{Y|X}(y|x).$ $$

We have that
$\widetilde{\gamma}^{*}=(\mathrm{id}\times\mathcal{T}_{\gamma^{*}})_{\#}\mu$ is a joint measure with first and second marginals $\mu$ and $\widetilde{\nu}:=\widetilde{\nu}_{\gamma^{*}}:=(\mathcal{T}_{\gamma^{*}})_{\#}\mu$, respectively. The goal is to show that $\widetilde{\gamma}^{*}$ is optimal for $GW(\mathbb{X},\widetilde{\mathbb{Y}})$ where $\widetilde{\mathbb{Y}}:=\widetilde{\mathbb{Y}}_{\gamma^{*}}:=(\mathcal{T}_{
\gamma^{*}})_{\#}\mu$.

Let $\widetilde{\gamma}\in\Gamma(\mu,\widetilde{\nu}_{\gamma^{*}})$ be an arbitrary plan. Let $\widetilde{\gamma}(\cdot_{2}|x):=\widetilde{\gamma}_{Y|X}(\cdot_{2}|x)$ denote the disintegration of $\widetilde{\gamma}$ with respect to $\mu$, given that the first component is $x$, for each $x\in\text{Supp}(\mu)$.
Similarly, we adopt the notation $\gamma^{*}(\cdot_{2}|x)$ for each $x\in\text{Supp}(\mu)$.

We define joint measure

$$ $\displaystyle\gamma:=\gamma^{*}_{Y|X}\widetilde{\gamma}^{*}_{X|Y}\widetilde{\gamma}$ (42) $$

on $X\times Y$. In particular, the above notation means that for each test function $\phi\in C_{0}(X\times Y)$, we have

$$ $\displaystyle\int_{X\times Y}\phi(x,y)d\gamma(x,y)$ $\displaystyle=\int_{X\times Y\times X\times Y}\phi(x,y)d\gamma^{*}(y|x^{0})d \widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}^{*}(x, \widetilde{y})$ $\displaystyle=\int_{X\times Y}\left(\int_{X}\left(\int_{Y}\phi(x,y)d\gamma^{*} (y|x^{0})\right)d\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})\right)d\widetilde {\gamma}^{*}(x,\widetilde{y})$ $$

For any test functions $\phi_{X}\in C_{0}(X),\phi_{Y}\in C_{0}(Y)$ we have

$$ $\displaystyle\int_{X\times Y}\phi_{X}(x)d\gamma(x,y)$ $\displaystyle=\int_{X\times Y\times X\times Y}\phi_{X}(x)d\gamma^{*}(y|x^{0})d \widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}(x,\widetilde{y})$ $\displaystyle=\int_{X\times Y}\phi_{X}(x)d\widetilde{\gamma}(x,\widetilde{y})$ $\displaystyle=\int_{X}\phi_{X}(x)d\mu(x)$ $\displaystyle\int_{X\times Y}\phi_{Y}(y)d\gamma(x,y)$ $\displaystyle=\int_{X\times Y\times X\times Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d \widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}(x,\widetilde{y})$ $\displaystyle=\int_{X\times Y\times X}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d \widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\nu}(\widetilde{y})$ $\displaystyle=\int_{X\times Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d\mu(x^{0})$ $\displaystyle=\int_{X\times Y}\phi_{Y}(y)d\gamma^{*}(x^{0},y)$ $\displaystyle=\int_{Y}\phi_{Y}(y)d\nu(y)$ $$

Thus $\gamma\in\Gamma(\mu,\nu)$.

In addition, we observe that we have the following property that holds for the case of considering inner products:

###### Lemma D.2 .

Suppose $X\subset\mathbb{R}^{d_{x}},Y\subset\mathbb{R}^{d_{y}}$ are finite-dimensional, convex compact sets. Let $\gamma\in\mathcal{M}_{+}(X\times Y)$ and define $\mathcal{T}_{\gamma}$ as in (9). In addition, let
$g_{Y}(y,y^{\prime})=\alpha\langle y,y^{\prime}\rangle$, where $(y,y^{\prime})\mapsto\langle y,y^{\prime}\rangle:=\sum_{i=1}^{d_{1}}y_{i}y_{i}
^{\prime}$ is an inner product (the standard one, for example). Then for each $x,x^{\prime}\in X$, let $\widetilde{y}=\mathcal{T}_{\gamma}(x),\widetilde{y}^{\prime}=\mathcal{T}_{
\gamma}(x^{\prime})$, we have:

$$ $\displaystyle g_{Y}(\widetilde{y},\widetilde{y}^{\prime})=\int_{Y\times Y}g_{Y }(y,y^{\prime})d\gamma(y|x)d\gamma(y^{\prime}|x^{\prime}).$ (43) $$

###### Proof of Lemma D.2 .

For each $i\in[1:d_{y}]$, we have:

$$ $\displaystyle\widetilde{y}[i]\widetilde{y}^{\prime}[i]$ $\displaystyle=\int_{X}y[i]d\gamma(y|x)\int_{X}y^{\prime}[i]d\gamma(y^{\prime}| x^{\prime})$ $\displaystyle=\int_{X}y[i]\int_{y^{\prime}}y^{\prime}[i]d\gamma(y|x)d\gamma(y^ {\prime}|x^{\prime})$ $\displaystyle=\int_{Y\times Y}y[i]y^{\prime}[i]d\gamma(y|x)d\gamma(y^{\prime}| x^{\prime})$ $$

where the third equality follows from Fubini’s theorem.

Thus,

$$ $\displaystyle g_{Y}(\widetilde{y},\widetilde{y}^{\prime})$ $\displaystyle=\alpha\sum_{i=1}^{d_{y}}\widetilde{y}[i]\widetilde{y}^{\prime}[i]$ $\displaystyle=\alpha\int_{Y\times Y}y[i]y^{\prime}[i]d\gamma(y|x)d\gamma(y^{ \prime}|x^{\prime})$ $\displaystyle=\int_{Y\times Y}\alpha\sum_{i=1}^{d_{y}}y[i]y^{\prime}[i]d\gamma (y|x)d\gamma(y^{\prime}|x^{\prime})$ $\displaystyle=\int_{Y\times Y}g_{X}(y,y^{\prime})d\gamma(y|x)d\gamma(y^{\prime }|x^{\prime})$ $$

∎

Now, we continue with the proof of Proposition 2.1, part (3).

We have

$$ $\displaystyle C(\gamma^{*};\mathbb{X},\mathbb{Y})\>=\int_{(X\times Y)^{\otimes 2 }}|g_{X}(x,x^{\prime})-g_{Y}(y,y^{\prime})|^{2}d\gamma^{*}(x,y)d\gamma^{*}(x^{ \prime},y^{\prime})$ $\displaystyle=\|g_{X}(x,x^{\prime})\|^{2}_{L^{2}(\mu^{\otimes 2})}+\|g_{Y}(y,y ^{\prime})\|^{2}_{L^{2}(\nu^{\otimes 2})}-2\int_{(X\times X)^{\otimes 2}}g_{X} (x,x^{\prime})g_{Y}(y,y^{\prime})d\gamma^{*}(x,y)d\gamma^{*}(x^{\prime},y^{ \prime})$ $\displaystyle=J_{1}-2\langle g_{X}g_{Y},(\gamma^{*})^{\otimes 2}\rangle$ (44) $$

where $J_{1}=\|g_{X}\|^{2}_{L^{2}(\mu^{\otimes 2})}+\|g_{Y}\|^{2}_{L^{2}(\nu^{\otimes
2
})}$ is independent to $\gamma^{*}$.
Similarly,

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}})$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}( \widetilde{y},\widetilde{y}^{\prime})|^{2}d\widetilde{\gamma}^{*}(x,y)d \widetilde{\gamma}^{*}(x^{\prime},y^{\prime})$ $\displaystyle=\|g_{X}\|^{2}_{L^{2}(\mu^{\otimes 2})}+\|g_{Y}\|^{2}_{L^{2}( \widetilde{\nu}^{\otimes 2})}-2\int_{(X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime })g_{Y}(\widetilde{y},\widetilde{y}^{\prime})d\widetilde{\gamma}^{*}(x, \widetilde{y})d\widetilde{\gamma}^{*}(x^{\prime},\widetilde{y}^{\prime})$ $\displaystyle=J_{2}-2\int_{X^{\otimes 2}}g_{X}(x,x^{\prime})g_{Y}(\mathcal{T}_ {\gamma^{*}}(x),\mathcal{T}_{\gamma^{*}}(x^{\prime}))d\mu(x)d\mu(x^{\prime})$ (45) $\displaystyle=J_{2}-2\int_{X^{\otimes 2}}g_{X}(x,x^{\prime})\left[\int_{Y^{ \otimes 2}}g_{Y}(y,y^{\prime})d\gamma^{*}(y|x)d\gamma^{*}(y^{\prime}|y^{\prime })\right]d\mu(x)d\mu(x^{\prime})$ (46) $\displaystyle=J_{2}-2\int_{(X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime})g_{Y}(y, y^{\prime})d\gamma^{*}(x,y)d\gamma^{*}(x^{\prime},y^{\prime})$ $\displaystyle=J_{2}-2\langle g_{X}g_{Y},(\gamma^{*})^{\otimes 2}\rangle$ (47) $$

where in (45), $J_{2}=\|g_{X}(\cdot_{1},\cdot_{2})\|^{2}_{L^{2}(\mu^{\otimes 2})}+\|g_{Y}(
\cdot_{1},\cdot_{2})\|^{2}_{L^{2}(\widetilde{\nu}^{\otimes 2})}$ (which is independent of $\widetilde{\gamma}^{*}$); and (46) follows from Lemma D.2. Combining (44) and (47), we have

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}})=C( \gamma^{*};\mathbb{X},\mathbb{Y})-J_{1}+J_{2}.$ (48) $$

Similarly, we can show that

$$ $\displaystyle C(\widetilde{\gamma};\mathbb{X},\widetilde{\mathbb{Y}})=C(\gamma ;\mathbb{X},\mathbb{Y})-J_{1}+J_{2}.$ (49) $$

Also, similarly to (44) and (47), we have

$$ $\displaystyle C(\gamma;\mathbb{X},\mathbb{Y})=J_{1}-2\langle g_{X}g_{Y},\gamma ^{\otimes 2}\rangle$ (50) $\displaystyle C(\widetilde{\gamma};\mathbb{X},\widetilde{\mathbb{Y}})=J_{2}-2 \langle g_{X}g_{Y},\widetilde{\gamma}^{\otimes 2}\rangle$ (51) $$

It remains to show

$$ $\displaystyle\langle g_{X}g_{Y},\gamma^{\otimes 2}\rangle=\langle g_{X}g_{Y}, \widetilde{\gamma}^{\otimes 2}\rangle.$ (52) $$

Indeed,

$$ $\displaystyle\langle g_{X}g_{Y},\widetilde{\gamma}^{\otimes 2}\rangle=\int_{(X \times Y)^{\otimes 2}}g_{X}(x,x^{\prime})g_{Y}(\widetilde{y},\widetilde{y}^{ \prime})d\widetilde{\gamma}(x,\widetilde{y})d\widetilde{\gamma}(x^{\prime}, \widetilde{y}^{\prime})$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime})g_{Y}( \widetilde{y},\widetilde{y}^{\prime})d\widetilde{\gamma}(\widetilde{y}|x)d \widetilde{\gamma}(\widetilde{y}^{\prime}|x^{\prime\prime})d\mu(x)d\mu(x^{ \prime})$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime})\left[\int_{X^{ \otimes 2}}g_{Y}(\mathcal{T}_{\gamma^{*}}(x^{0}),\mathcal{T}_{\gamma^{*}}(x^{0 }{{}^{\prime}}))d\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma }^{*}(x^{0}{{}^{\prime}}|\widetilde{y}{{}^{\prime}})\right]$ $\displaystyle\qquad d\widetilde{\gamma}(\widetilde{y}|x)d\widetilde{\gamma}( \widetilde{y}^{\prime}|x^{\prime})d\mu(x)d\mu(x^{\prime})$ (53) $\displaystyle=\int_{(X\times Y\times X)^{\otimes 2}}g_{X}(x,x^{\prime})g_{Y}( \mathcal{T}_{\gamma^{*}}(x^{0}),\mathcal{T}_{\gamma^{*}}(x^{0}{{}^{\prime}}))$ $\displaystyle\qquad d\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{ \gamma}^{*}(x^{0}{{}^{\prime}}|\widetilde{y}{{}^{\prime}})d\widetilde{\gamma}( \widetilde{y}|x)d\widetilde{\gamma}(\widetilde{y}^{\prime}|x^{\prime\prime})d \mu(x)d\mu(x^{\prime})$ $\displaystyle=\int_{(X\times Y\times X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime} )\left[\int_{Y^{\otimes 2}}g_{Y}(y,y^{\prime})d\gamma^{*}(y|x^{0})d\gamma^{*}( y^{\prime}|x^{0}{{}^{\prime}})\right]$ $\displaystyle\qquad d\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{ \gamma}^{*}(x^{0}{{}^{\prime}}|\widetilde{y}^{\prime})d\widetilde{\gamma}( \widetilde{y}|x)d\widetilde{\gamma}(\widetilde{y}^{\prime}|x^{\prime})d\mu(x)d \mu(x^{\prime})$ (54) $\displaystyle=\int_{(X\times Y\times X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime} )g_{Y}(y,y^{\prime})\Bigl{(}d\gamma^{*}(y|x^{0})d\widetilde{\gamma}^{*}(x^{0}| \widetilde{y})d\widetilde{\gamma}(\widetilde{y}|x)d\mu(x)\Bigl{)}$ $\displaystyle\qquad\Bigl{(}d\gamma^{*}(y^{\prime}|x^{\prime 0}{{}^{\prime}})d \widetilde{\gamma}^{*}(x^{0}{{}^{\prime}}|\widetilde{y}^{\prime})d\widetilde{ \gamma}(\widetilde{y}^{\prime}|x^{\prime})d\mu(x^{\prime})\Bigl{)}$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}g_{X}(x,x^{\prime})g_{Y}(y,y^{ \prime})d\gamma(x,x)d\gamma(x^{\prime},y^{\prime})$ $\displaystyle=\langle g_{X}g_{Y},\gamma^{\otimes 2}\rangle$ $$

where (53) holds since given $\widetilde{y}$, theprobability measure $\widetilde{\gamma}^{*}(\cdot_{1}|\widetilde{y})$ is only supported on $\{x^{0}\in X:\,\widetilde{y}=\mathcal{T}_{\gamma^{*}}(x^{0})\}$, similarly to measure $\gamma(\cdot_{1}|\widetilde{y}{{}^{\prime}})$; (54) follows from Lemma D.2 (that is, from equality (43)).

Combining (49), (48), (52) and the fact
$C(\gamma^{*};\mathbb{X},\mathbb{Y})\leq C(\gamma;\mathbb{X},\mathbb{Y})$, we obtain that
$C(\widetilde{\gamma}^{*};\mathbb{X},\mathbb{Y})\leq C(\widetilde{\gamma};
\mathbb{X},\mathbb{Y})$ which
completes the proof.

###### Lemma D.2 .

###### Proof of Lemma D.2 .

## Appendix E Proof of Proposition 3.1

Consider gm-spaces $\mathbb{X},\mathbb{Y}^{1},\mathbb{Y}^{2}$, and select $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}
\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})$. Inspired by the LGW distance (35), we propose the LPGW distance (conditioned on $\gamma^{1},\gamma^{2}$) (14) in the general case:

$$ $\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{ 1},\gamma^{2}):=$ $\displaystyle\inf_{\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)}\int_{(X \times Y^{1}\times Y^{2})^{\otimes 2}}|g_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})-g_{ Y^{2}}(y^{2},y^{2}{{}^{\prime}})|^{2}d\gamma^{\otimes 2}$ $\displaystyle+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|\gamma|^{2}).$ (55) $$

where $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu):=\{\gamma\in\mathcal{M}_{+}(X\times Y
^{1}\times Y^{2}):(\pi_{X,Y^{1}})_{\#}\gamma\leq\gamma^{1},(\pi_{X,Y^{2}})_{\#
}\gamma\leq\gamma^{2}\}$.

Next, we discuss the proof of Proposition 3.1.

### E.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 a minimizer to the LPGW problem.

First, we introduce a series of lemmas.

###### Lemma E.1 .

Given Radon measures $\mu,\nu^{1},\nu^{2}$, and $\gamma^{1}\in\Gamma_{\leq}(\mu,\nu^{1}),\gamma^{2}\in\Gamma_{\leq}(\mu,\nu^{2})$, then

$$ $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ $$

is sequentially compact set.

###### Proof.

The main idea is similar to the proof in e.g. Lemma B.2 [].
In particular, consider a sequence $(\gamma^{n})\subset\Gamma_{\leq,X}(\gamma_{X},\gamma_{Y})$. It is straightforward to verify this sequence is upper bounded in total variation since $\gamma^{1},\gamma^{2}$ are finite measures and that it is a tight sequence (in this context it is even easier since the spaces $X,Y^{1},Y^{2}$ are compact).
Thus, by Prokhorov’s theorem for signed measures, the closure of $\Gamma_{\leq}(\gamma^{1},\gamma^{2})$ (in the weak topology) is weakly sequentially compact in $\mathcal{M}(X\times Y^{1}\times Y^{2})$.

It remains to show $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ is closed.

Suppose $\gamma^{n}\overset{w\ast}{\rightharpoonup}\gamma\in\mathcal{M}(X\times Y^{1}
\times Y^{2})$, for each nonnegative test function $\phi\in C(X\times Y^{1})$, we have

$$ $\displaystyle\lim_{n\to\infty}\int_{X\times Y^{1}}\phi(x,y^{1})d(\pi_{X,Y^{1}} )_{\#}\gamma^{n}(x,y^{1})$ $\displaystyle=\lim_{n\to\infty}\int_{X\times Y^{1}\times Y^{2}}\phi(x,y^{1})d \gamma^{n}(x,y^{1},y^{2})$ $\displaystyle=\int_{X\times Y^{1}\times Y^{2}}\phi(x,y^{1})d\gamma(x,y^{1},y^{ 2})$ $\displaystyle=\int_{X\times Y^{1}}\phi(x,y^{1})d(\pi_{X,Y^{1}})_{\#}\gamma(x,y ^{1})$ $$

That is, $(\pi_{X,Y^{1}})_{\#}\gamma^{n}\overset{w\ast}{\rightharpoonup}(\pi_{X,Y^{1}})_
{\#}\gamma$. By Lemma B.1 in [], we have $(\pi_{X,Y^{1}})_{\#}\gamma\leq\gamma^{1}$. Similarly we have $(\pi_{X,Y^{2}})_{\#}\gamma\leq\gamma^{2}$.

Thus, $\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ and we have completed the proof.
∎

###### Lemma E.2 .

Suppose $g_{X},g_{Y}$ are continuous functions (see assumption (3)), we claim that the mapping

$$ $(X\times Y)^{\otimes 2}\ni((x,y),(x^{\prime},y^{\prime}))\mapsto|g_{X}(x,x^{ \prime})-g_{Y}(y,y^{\prime})|^{2}\in\mathbb{R}$ $$

is a Lipschitz function with respect to metric

$$ $D_{X\times Y}((x,y),(x^{\prime},y^{\prime}))=d_{X}(x,x^{\prime})+d_{Y}(y,y^{ \prime}).$ $$

###### Proof of Lemma E.2 .

Let the mapping in the statement of the lemma be denoted by $\Phi$. For $x_{1},x_{1}^{\prime},x_{2},x_{2}^{\prime}\in X,y_{1},y_{1}^{\prime},y_{2},y_{2
}^{\prime}\in Y$ we have

$$ $\displaystyle|\Phi((x_{1},y_{1}),(x_{1}^{\prime},x_{1}^{\prime}))-\Phi((x_{2}, y_{2}),(x_{2}^{\prime},y_{2}^{\prime}))|$ $\displaystyle=||g_{X}(x_{1},x_{1}^{\prime})-g_{Y}(y_{1},y_{1}^{\prime})|^{2}-| g_{X}(x_{2},x_{2}^{\prime})-g_{Y}(y_{2},y_{2}^{\prime})|^{2}|$ $\displaystyle\leq||g_{X}(x_{1},x_{1}^{\prime})-g_{Y}(y_{1},y_{1}^{\prime})|^{2 }-|g_{X}(x_{2},x_{2}^{\prime})-g_{Y}(y_{1},y_{1}^{\prime})|^{2}|$ $\displaystyle+||g_{X}(x_{2},x_{2}^{\prime})-g_{Y}(y_{1},y_{1}^{\prime})|^{2}-| g_{X}(x_{2},x_{2}^{\prime})-g_{Y}(y_{2},y_{2}^{\prime})|^{2}|$ $\displaystyle\leq K_{1}(|g_{X}(x_{1},x_{1}^{\prime})-g_{X}(x_{2},x_{2}^{\prime })|+|g_{Y}(y_{1},y_{1}^{\prime})-g_{Y}(y_{2},y_{2}^{\prime})|)$ (56) $\displaystyle=K_{1}K_{2}|d_{X}(x_{1},x_{2})+d_{X}(x_{1}^{\prime},x_{2}^{\prime })+d_{Y}(y_{1},y_{2})+d_{Y}(y_{1}^{\prime},y_{2}^{\prime})|$ (57) $$

where (56) follows from the fact $r_{1}\mapsto|r_{1}-r_{2}|^{2}$ is Lipschitz function (see e.g. Lemma C.1. in []) on compact set; in addition, $K_{1}\geq 0$ is the corresponding Lipschitz constant. (57) holds by assumption (3) for $g_{X}$ and $g_{Y}$, $K_{2}\geq 0$ is the maximum of their Lipschitz constant.
∎

Consider $(\gamma^{n})\subset\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$, such that

$$ $\langle|g_{Y^{1}}-g_{Y^{2}}|^{2}-2\lambda,(\gamma^{n})^{\otimes 2}\rangle\to \inf_{\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)}\langle|g_{Y^{1}}-g_{Y ^{2}}|^{2}-2\lambda,\gamma^{\otimes 2}\rangle.$ $$

By compactness of $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ (see Lemma E.1), we have that there exists $\gamma^{*}\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ which is sub-sequence limit of $\gamma^{n}$ (in weak convergence).

By Lemma E.2 and Lemma C.2.(3) in [], we have

$$ $\displaystyle\langle|g_{Y^{1}}-g_{Y^{2}}|^{2}-2\lambda,(\gamma^{*})^{\otimes 2 }\rangle=\inf_{\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)}\langle|g_{Y^ {1}}-g_{Y^{2}}|^{2}-2\lambda,\gamma^{\otimes 2}\rangle.$ $$

Thus $\gamma^{*}$ is a minimizer and we have completed the proof.

###### Lemma E.1 .

###### Proof.

###### Lemma E.2 .

###### Proof of Lemma E.2 .

### E.2 Proof of Proposition 3.1 : Part 2

###### Proof.

Under the Monge mapping assumptions, we have

$$ $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)=\{(\mathrm{id}\times T^{1}\times T^{2 })_{\#}\mu^{\prime}:\,\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_{X}\}.$ $$

Thus, (55) becomes

$$ $\displaystyle LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^ {2})$ $\displaystyle=\inf_{\mu^{\prime}\leq\gamma^{1}_{x}\wedge\gamma^{2}_{X}}\int_{X ^{\otimes 2}}|g_{Y^{1}}(T^{1}(x),T^{1}(x^{\prime}))-g_{Y^{2}}(T^{2}(x),T^{2}(x ^{\prime}))|^{2}+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|(\mathrm{id}\times T^{1 }\times T^{2})_{\#}\mu^{\prime}|^{2})$ $\displaystyle=\inf_{\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_{X}}\int_{X ^{\otimes 2}}|g_{Y^{1}}(T^{1}(x),T^{1}(x^{\prime}))-g_{Y^{2}}(T^{2}(x),T^{2}(x ^{\prime}))|^{2}+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|\mu^{\prime}|^{2})$ $\displaystyle=(\ref{eq:lpgw_gamma_monge}).$ $$

and we have proven the statement.
∎

###### Proof.

### E.3 Proof of Proposition 3.1 : Part 3

Since $X,Y^{1},Y^{2}$ are compact, by continuity (see (3)), we have that $g_{X},g_{Y^{1}},g_{Y^{2}}$ are bounded functions.

By Lemma E.2 in [], when $2\lambda>\max(|g_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})-g_{Y^{2}}(y^{2},y^{2}{{}^{
\prime}})|^{2})$, pick any optimal

$$ $\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)=\{(\mathrm{id}\times T^{1} \times T^{2})_{\#}\mu^{\prime}:\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_ {X}\},$ $$

we have $|\gamma|=\min(|\gamma^{1}|,|\gamma^{2}|)=\min(|\gamma^{1}_{X}|,|\gamma^{2}_{X}|)$.
Thus $\gamma=(\mathrm{id}\times T^{1}\times T^{2})_{\#}\gamma^{1}_{X}\wedge\gamma^{2
}_{X}$.
Plug in this optimal $\gamma$ into the LPGW problem (13) (or (14)), we obtain

$$ $\displaystyle LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^ {2})$ $\displaystyle=\langle|g_{Y^{1}}-g_{Y^{2}}|^{2},(\gamma^{1}_{X}\wedge\gamma^{2} _{X})^{\otimes 2}\rangle+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|\gamma^{1}_{X} \wedge\gamma^{2}_{X}|^{2})$ $\displaystyle=\langle|k_{\gamma^{1}}-k_{\gamma^{2}}|^{2},(\gamma^{1}_{X}\wedge \gamma^{2}_{X})^{\otimes 2}\rangle+\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2| \gamma^{1}_{X}\wedge\gamma^{2}_{X}|^{2})$ $$

and we complete the proof.

### E.4 Proof of Proposition 3.1 : Part 4

First, under the Monge mapping assumption, an optimal PGW plan is of the form $\gamma^{*}=(\mathrm{id}\times T)_{\#}\gamma^{*}_{X}$ for some $\gamma^{*}_{X}\leq\mu$, we have

$$ $\displaystyle\|k_{\gamma^{*}}\|^{2}_{L^{2}((\gamma_{X}^{*})^{\otimes 2})}+ \lambda(|\mu|^{2}-|\gamma_{X}^{*}|^{2}+|\gamma_{c}|)$ $\displaystyle=\int_{X^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(T(x),T(x^{\prime} ))|^{2}d(\gamma^{*})^{\otimes 2}+\lambda(|\mu^{\otimes 2}-(\gamma^{*}_{X})^{ \otimes 2}|+|\nu^{\otimes 2}-(\gamma^{*}_{Y})^{\otimes 2}|)$ $\displaystyle=PGW_{\lambda}(\mathbb{X},\mathbb{Y}).$ $$

In the general case, we first introduce the following lemma.

###### Lemma E.3 .

If $\gamma^{0}\in\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{X})$, then $(\pi_{X})_{\#}\gamma^{0}=\mu,(\pi_{Y})_{\#}\gamma^{0}=\mu$.

###### Proof of Lemma E.3 .

Pick any $\gamma\in\Gamma_{\leq}(\mathbb{X},\mathbb{X})$, suppose $|\gamma|<|\mu|$, we have

$$ $\displaystyle C(\gamma;\mathbb{X},\mathbb{X},\lambda)$ $\displaystyle=\int_{X^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{X}(x^{0},x^{0}{{}^{ \prime}})|d\gamma^{\otimes 2}+\lambda(2|\mu|^{2}-2|\gamma|^{2})$ $\displaystyle\geq\lambda(2|\mu|^{2}-2|\gamma|^{2})$ $\displaystyle>0.$ (58) $$

However, $PGW_{\lambda}(\mathbb{X},\mathbb{X})=0$. Thus $\gamma$ is not optimal.
∎

By the above lemma, we have $|\gamma^{*}|\leq|\gamma^{0}|$. For each $\gamma\in\Gamma_{\leq}(\gamma^{0},\gamma^{*};\mu)$, from [], there exists $\gamma^{\prime}\in\Gamma_{\leq}(\gamma^{0},\gamma^{*})$ such that $(\pi_{X,Y})_{\#}\gamma^{\prime}=\gamma^{*}$ and $\gamma\leq\gamma^{\prime}$. Thus we have $|\gamma^{\prime}|=|\gamma^{*}|$.

Let

$$ $\displaystyle C(\gamma;\mathbb{X},\mathbb{X},\mathbb{Y},\lambda)$ $\displaystyle:=\int_{(X\times X\times Y)^{\otimes 2}}|g_{X}(x,x^{{}^{\prime}}) -g_{Y}(y,y{{}^{\prime}})|^{2}d\gamma^{\otimes 2}((x,x^{\prime}),(x,x^{{}^{ \prime}}),(y,y^{\prime}))$ $\displaystyle\qquad+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2})$ $$

and similarly we define $C(\gamma^{\prime};\mathbb{X},\mathbb{X},\mathbb{Y},\lambda)$.
Then

$$ $\displaystyle C(\gamma^{\prime};\mathbb{X},\mathbb{X},\mathbb{Y},\lambda)-C( \gamma;\mathbb{X},\mathbb{X},\mathbb{Y},\lambda)$ $\displaystyle=\int_{(X\times X\times Y)^{\otimes 2}}\left[|g_{X}(x,x{{}^{ \prime}})-g_{Y}(y,y{{}^{\prime}})|^{2}-2\lambda\right]d(\gamma^{\prime}{{}^{ \otimes 2}}-\gamma{{}^{\otimes 2}})((x,x^{\prime}),(x,x{{}^{\prime}}),(y,y^{ \prime}))$ $\displaystyle\leq 0.$ $$

In addition,

$$ $\displaystyle C(\gamma^{\prime};\mathbb{X},\mathbb{X},\mathbb{Y},\lambda)$ $\displaystyle=\int_{(X\times X\times Y)^{\otimes 2}}|g_{X}(x,x^{{}^{\prime}})- g_{Y}(y,y{{}^{\prime}})|^{2}d\gamma^{\prime}{{}^{\otimes 2}}((x,x^{\prime}),(x ,x^{{}^{\prime}}),(y,y^{\prime}))+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma^{\prime }|^{2})$ $\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x{{}^{\prime}})-g_{Y}(y,y {{}^{\prime}})|^{2}d(\gamma^{*})^{\otimes 2}((x,x^{\prime}),(y,y^{\prime}))+ \lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma^{*}|^{2})$ $\displaystyle=PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ $$

where the second equality holds by (39) and the fact $|\gamma^{\prime}|=|\gamma^{*}|$.
Thus, we have

$$ $\displaystyle LPGW_{\lambda}(\mathbb{X},\mathbb{Y};\mathbb{X},\gamma^{0}, \gamma^{*})\leq C(\gamma^{\prime};\mathbb{X},\mathbb{X},\mathbb{Y},\lambda)= PGW_{\lambda}(\mathbb{X},\mathbb{Y}).$ $$

Another direction is trivial since for each $\gamma\in\Gamma_{\leq}(\gamma^{0},\gamma^{*};\mu)$, $(\pi_{2,3})_{\#}\gamma:=(\pi_{X,Y})_{\#}\gamma\in\Gamma_{\leq}(\mu,\nu)$. Thus

$$ $PGW_{\lambda}(\mathbb{X},\mathbb{Y};\gamma)\leq C(\gamma;\mathbb{X},\mathbb{X} ,\mathbb{Y},\lambda)\leq LPGW_{\lambda}(\mathbb{X},\mathbb{Y};\mathbb{X}, \gamma^{0},\gamma^{*}).$ $$

and we have completed the proof.

###### Lemma E.3 .

###### Proof of Lemma E.3 .

### E.5 Proof of Proposition 3.1 : Part 5

This section discusses the proof of statement 5 of Proposition 3.1. That is, we discuss the metric properties of the proposed LPGW distance.

#### E.5.1 Formal Statement

In this section, we set $g_{Y}=d_{Y}^{s}$.
Let

$$ $\mathcal{G}:=\{\mathbb{Y}=(Y,g_{Y},\nu)\}$ $$

where $Y\subset\mathbb{R}^{d}$ for some $d\in\mathbb{N}$ such that $Y$ is nonempty convex compact set;
$\nu\in\mathcal{M}_{+}(Y)$ with $\nu^{\otimes 2}(|g_{Y}|)<\infty$.

Then $\forall\mathbb{Y}^{1},\mathbb{Y}^{2}\in\mathcal{G}$, we define $\mathbb{Y}^{1}\sim\mathbb{Y}^{2}$ iff $GW(\mathbb{Y}^{1},\mathbb{Y}^{2})=0$. By [], in this case, optimal transportation plan $GW(\mathbb{Y}^{1},\mathbb{Y}^{2})$ is induced by the Monge mapping $T$. Furthermore, $T$ is bijection $\nu^{1}$-a.s. and is called “isomorphism” since

$$ $d_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})=d_{Y^{2}}(T(y^{1}),T(y^{1}{{}^{\prime}})), \nu^{1}-a.s.$ $$

Next, given $\mathcal{G}^{\prime}\subset\mathcal{G}$ we introduce the following assumptions:

###### Assumption E.4 .

For each $\mathbb{Y}\in\mathcal{G}^{\prime}$, the problem $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ admits a unique solution.

###### Assumption E.5 .

For subset $\mathcal{G}^{\prime}$, define $K_{1},K_{2}$ by

$$ $\displaystyle K_{1}=\sup\{|\nu|,\mathbb{Y}=(Y,g_{Y},\nu)\in\mathcal{G}^{\prime }\},$ $\displaystyle K_{2}=\sup\{\max_{y,y^{\prime}\in\text{supp}(\nu)}|g_{Y}(y,y^{ \prime})|^{2}:\,\mathbb{Y}=(X,g_{Y},\nu)\in\mathcal{G}^{\prime})\}$ $$

We suppose $K_{1},K_{2}<\infty$.

###### Assumption E.6 .

$g_{X},g_{Y^{1}},g_{Y^{2}}$ are induced by metrics. In particular, $g_{X}(\cdot,\cdot)=d_{X}^{q}(\cdot,\cdot)$, $g_{Y^{1}}(\cdot,\cdot)=d_{Y^{1}}^{q}(\cdot,\cdot)$, $g_{Y^{2}}(\cdot,\cdot)=d_{Y^{2}}^{q}(\cdot,\cdot)$, where
$d_{X}$ is a metric defined in $X$, $q\geq 1$, similar to $d_{Y^{1}},d_{Y^{2}}$.

###### Remark E.7 .

The uniqueness of optimal transportation plan assumption (E.4) is also introduced by [] to prove the triangle inequality of linear optimal transport. The assumption (E.5) discusses the bounded total mass and transportation cost.

###### Proposition E.8 (Metric property of LPGW) .

Fix $\mathbb{X}\in\mathcal{G}$ and for each $\mathbb{Y}^{1}$, we select $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}
\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})$. In addition, set $g_{X}=d_{X}^{s},g_{Y}=d_{Y}^{s}$ where $s\geq 1$. Then we have:

- (1)
The LPGW distances (14),(15) are nonnegative:
$\displaystyle LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^
{2},\lambda),LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})\geq 0$
(59)
- (2)
The LPGW distances (14),(15) are symmetric:
$\displaystyle LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^
{2},\lambda)=LPGW(\mathbb{Y}^{2},\mathbb{Y}^{1}\mathbb{X},\gamma^{2},\gamma^{1
},\lambda)$
$\displaystyle LPGW(\mathbb{Y}^{2},\mathbb{Y}^{1};\mathbb{X},\lambda)=LPGW_{
\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}).$
(60)
- (3)
The LPGW distances (14) satisfy triangle inequality.
In addition, under assumption (E.4), (15) satisfies the triangle inequality.
- (4)
Under assumption (E.6), if $LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{2})=0$, we have $\mathbb{Y}^{1}\sim\mathbb{Y}^{2}$.
Similarly to $LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})$.
- (5)
Under assumption (E.5), suppose $|\mu|\geq K_{1}$, and $2\lambda\geq K_{2}+\sup_{x,x^{\prime}\in\text{supp}(\mu)}|g_{X}(x,x^{\prime})|
^{2}$, and $\mathbb{Y}^{1}\sim\mathbb{Y}^{2}$, where $K_{1},K_{2}$ are defined in (E.5).
Then there exists $\gamma^{1},\gamma^{2}$ such that
$\displaystyle LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^
{2},\lambda)=LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})=0.$

Therefore, under the assumptions (E.4), (E.5), and (E.6), we have
that (15) defines a metric in $\mathcal{G}^{\prime}/\sim$.

Note, the above statement implies metric property of LGW by setting $\lambda\to\infty$. We refer the next section for details.

###### Assumption E.4 .

###### Assumption E.5 .

###### Assumption E.6 .

###### Remark E.7 .

###### Proposition E.8 (Metric property of LPGW) .

#### E.5.2 Proof of Proposition E.8 : Parts 1 , 2 , 4 , 5

###### Proof.

Choose $\mathbb{Y}^{1},\mathbb{Y}^{2},\mathbb{Y}^{3}\in\mathcal{G}$.

- 1, 2
It is straightforward to verify the nonnegativity (1) and symmetry (2).
- 4
In this setting, we have:
$\displaystyle 0$
$\displaystyle=LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{
1},\gamma^{2})$
$\displaystyle=\inf_{\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)}\int_{(X
\times Y^{1}\times Y^{2})^{\otimes 2}}|g_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})-g_{
Y^{2}}(y^{2},y^{2}{{}^{\prime}})|^{2}d\gamma^{\otimes 2}+\lambda(|\nu^{1}|^{2}
+|\nu^{2}|-2|\gamma|^{2})$
Pick one corresponding minimizer $\gamma$, we obtain
$\int_{(X\times Y^{1}\times Y^{2})^{\otimes 2}}|g_{Y^{1}}(y^{1},y^{1}{{}^{
\prime}})-g_{Y^{2}}(y^{2},y^{2}{{}^{\prime}})|^{2}d\gamma^{\otimes 2}=0,$
and
$|\nu^{1}|^{2}+|\nu^{2}|^{2}-2|\gamma|^{2}=0.$
Thus $\gamma\in\Gamma(\nu^{1},\nu^{2})$ and therefore
$GW(\mathbb{Y}^{1},\mathbb{Y}^{2})=0.$
That is $\mathbb{Y}^{1}\sim\mathbb{Y}^{2}$.
By a similar process, if $LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})=0$, we have $\mathbb{Y}^{1}\sim\mathbb{Y}^{2}$.
- 5
Since $\mathbb{Y}^{1}\sim\mathbb{Y}^{2}$, from triangle inequality of $PGW_{\lambda}(\cdot,\cdot)$, we have
$PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{1})=PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{
2}).$
In addition, there exists a bijection mapping $T:\text{supp}(\nu^{1})\to\text{supp}(\nu^{2})$ such that $g_{Y^{1}}(x_{1},x_{1}^{\prime})=g_{X_{2}}(T(x_{1}),T(x_{1}^{\prime})),\nu^{1}-$a.s.
such that $T_{\#}\nu^{1}=\nu^{2}$.
Pick $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1})$. Let
$\gamma^{2}:=(\mathrm{id}\times T)_{\#}\gamma^{1}$, that is, for each test function $\phi\in C_{0}(X\times Y^{2})$,
$\gamma^{2}(\phi):=\int_{X\times Y^{1}}\phi(x,T(y^{1}))d\gamma^{1}(x,y^{1}).$
We claim $\gamma^{2}$ is optimal for $PGW_{\lambda}(\mathbb{X}^{1},\mathbb{Y}^{2})$.
$\displaystyle(\pi_{1})_{\#}\gamma^{2}=(\pi_{1})_{\#}\gamma^{1}\leq\mu,$
$\displaystyle(\pi_{2})_{\#}\gamma^{2}=T_{\#}((\pi_{2})_{\#}\gamma^{1}))\leq\nu
^{2}\qquad\text{since }(\pi_{Y})_{\#}\gamma^{1}\leq\nu^{1}.$
Thus, $\gamma^{2}\in\Gamma_{\leq}(\mu,\nu^{2})$.
In addition,
$\displaystyle C(\gamma^{2};\mathbb{X},\mathbb{Y}^{2})$
$\displaystyle=\int_{(X\times Y^{1})^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y^{2}}
(T(y^{1}),T(y^{1}){{}^{\prime}})|^{2}d(\gamma^{1})^{\otimes 2}+\lambda(|\mu|^{
2}+|\nu^{2}|^{2}-2|\gamma^{2}|^{2})$
$\displaystyle=\int_{(X\times Y^{1})^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y^{2}}
(T(y^{1}),T(y^{1}){{}^{\prime}})|^{2}d(\gamma^{1})^{\otimes 2}(x,x^{\prime}|y^
{1},y^{1}{{}^{\prime}}))d(\nu^{1})^{\otimes 2}(y^{1},y^{1}{{}^{\prime}})$
$\displaystyle\qquad+\lambda(|\mu|^{2}+|\nu^{1}|-2|\gamma^{1}|^{1})$
$\displaystyle=\int_{(X\times Y^{1})^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y^{1}}
(y^{1},y^{1}{{}^{\prime}})|^{2}d(\gamma^{1})^{\otimes 2}(x,x^{\prime}|y^{1},y^
{1}{{}^{\prime}}))d(\nu^{1})^{\otimes 2}(y^{1},y^{1}{{}^{\prime}})$
$\displaystyle\qquad+\lambda(|\mu|^{2}-|\gamma^{1}|^{2})$
(61)
$\displaystyle=PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{1})=PGW_{\lambda}(\mathbb{X
},\mathbb{Y}^{2}).$
and thus $\gamma^{2}$ is optimal in $PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{2})$.
Since $2\lambda$ is sufficiently large,
by lemma E.2 in [], there exists optimal $\gamma^{1}$ such that:
$|\gamma^{1}|=\min(|\mu|,|\nu^{1}|)=|\nu^{1}|.$
Thus we have $|\gamma^{2}|=|\gamma^{1}|=|\nu^{1}|=|\nu^{2}|.$
Plug $\gamma^{1},\gamma^{2}$ into (14), we have:
$\displaystyle LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^
{2})$
$\displaystyle=\int g_{Y^{1}}(y^{1},y^{1}{{}^{\prime}})-g_{Y^{2}}(T(y^{1}),T(y^
{1}{{}^{\prime}}))d(\nu^{1})^{\otimes 2}(y^{1},y^{1}{{}^{\prime}})$
$\displaystyle=0.$
(62)

∎

###### Proof.

#### E.5.3 Proof of Proposition E.8 : Part 3

##### Notation Setup and Summary

Choose $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}
\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2}),\gamma^{3}\in\Gamma^{*
}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{3})$, the goal is to show triangle inequality in this section:

$$ $\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{ 1},\gamma^{2})\leq LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{3};\mathbb{X}, \gamma^{1},\gamma^{3})+LPGW_{\lambda}(\mathbb{Y}^{2},\mathbb{Y}^{3};\mathbb{X} ,\gamma^{2},\gamma^{3}).$ (63) $$

##### Related Lemmas

###### Lemma E.9 (Varient Gluing lemma) .

Suppose $\gamma^{1}\in\Gamma(\mu,\nu^{1}),\gamma^{2}\in\Gamma(\mu,\nu^{2}),\gamma^{3}
\in\Gamma(\mu,\nu^{3})$ are probability measures. Pick $\gamma^{1,2}\in\Gamma(\gamma^{1},\gamma^{2};\mu),\gamma^{1,3}\in\Gamma(\gamma^
{1},\gamma^{3};\mu),\gamma^{2,3^{\prime}}\in\Gamma(\gamma^{1},\gamma^{3}{{}^{
\prime}};\mu)$, there exists $\gamma\in\mathcal{P}(X\times Y^{1}\times Y^{2}\times Y^{3})$ such that

$$ $\displaystyle\begin{cases}(\pi_{X,Y^{1},Y^{3}})_{\#}\gamma=\gamma^{1,3},\\ (\pi_{X,Y^{2},Y^{3}})_{\#}\gamma=\gamma^{2,3}.\end{cases}$ (64) $$

Note, if we set $X=\{0\}$ and $\mu=\delta_{0}$, the above lemma becomes the classical Gluing lemma (see e.g. Lemma 5.5 []). For this, we call it the variant gluing lemma.

###### Proof of Lemma E.9 .

For convenience, let $X^{\prime},Y^{3}{{}^{\prime}}$ be independent copy of $X,Y^{3}$.
By gluing lemma, there exists $\gamma^{\prime}\in\mathcal{P}((X\times Y^{1}\times Y^{2})\times X{{}^{\prime}})$ such that

$$ $\displaystyle\begin{cases}(\pi_{X,Y^{1},Y^{2}})_{\#}\gamma=\gamma^{1,2},\\ (\pi_{X,X^{\prime}})_{\#}\gamma=(\text{id}\times\text{id})_{\#}\mu.\end{cases}$ (65) $$

Apply gluing lemma again between $\gamma^{\prime}$ and $\gamma^{1,3}$, we can find $\gamma^{\prime\prime}\in\mathcal{P}((X\times Y^{1}\times Y^{3})\times(X^{
\prime}\times Y^{2}\times Y^{3}{{}^{\prime}}))$
such that

$$ $\displaystyle\begin{cases}(\pi_{X,Y^{1},Y^{3},X^{\prime}})_{\#}\gamma=\gamma^{ \prime},\\ (\pi_{X^{\prime},Y^{2},Y^{3}})_{\#}\gamma=\gamma^{2,3}.\end{cases}$ $$

Applying $\gamma=(\pi_{X,Y^{1},Y^{2},Y^{3}})_{\#}\gamma^{\prime\prime}$ we complete the proof.

Alternatively, we can set

$$ $\displaystyle\gamma=\gamma^{1,3}_{Y^{1},Y^{3}|X}\gamma^{2,3}_{Y^{2},Y^{3}|X} \mu(x)$ $$

and it is straightforward to verify $\gamma$ satisfies (64).
∎

###### Lemma E.10 (Triangle inequality for LGW) .

Suppose $\mathbb{X},\mathbb{Y}^{1},\mathbb{Y}^{2},\mathbb{Y}^{3}$ are under the balanced GW setting, choose $\gamma^{1}\in\Gamma^{*}(\mu,\nu^{1}),\gamma^{2}\in\Gamma^{*}(\mu,\nu^{2}),
\gamma^{3}\in\Gamma^{*}(\mu,\nu^{3})$, we have

$$ $\displaystyle LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{ 2})\leq LGW(\mathbb{Y}^{1},\mathbb{Y}^{3};\mathbb{X},\gamma^{1},\gamma^{3})+ LGW(\mathbb{Y}^{2},\mathbb{Y}^{3};\mathbb{X},\gamma^{2},\gamma^{3})$ (66) $$

###### Proof of lemma E.10 .

Pick the $\gamma$ from lemma E.9, we have

$$ $\displaystyle(\pi_{X,Y^{1}})_{\#}\gamma_{X,Y^{1}}=(\pi_{X,Y^{1}})_{\#}\gamma^{ 1,3}=\gamma^{1},$ $\displaystyle(\pi_{X,Y^{2}})_{\#}\gamma_{X,Y^{2}}=(\pi_{X,Y^{2}})_{\#}\gamma^{ 2,3}=\gamma^{2}.$ $$

Thus $(\pi_{X,Y^{1},Y^{2}})_{\#}\gamma\in\Gamma(\gamma^{1},\gamma^{2};\mu)$.
Then we have

$$ $\displaystyle LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{ 2})$ $\displaystyle=\left\langle|g_{Y^{1}}-g_{Y^{2}}|^{2},(\gamma^{1,2})^{\otimes 2} \right\rangle^{1/2}$ $\displaystyle\leq\left\langle|g_{Y^{1}}-g_{Y^{2}}|^{2},((\pi_{X,Y^{1},Y^{2}})_ {\#}\gamma)^{\otimes 2}\right\rangle^{1/2}$ (67) $\displaystyle=\left(\int_{X\times Y\times Y^{2}\times Y^{3}}|g_{Y^{1}}(y^{1},y ^{1}{{}^{\prime}})-g_{Y^{2}}(y^{2},y^{2}{{}^{\prime}})|^{2}d\gamma^{\otimes 2} ((x,x^{\prime}),(y^{1},y^{1}{{}^{\prime}}),(y^{2},y^{2}{{}^{\prime}}),(y^{3},y ^{3}{{}^{\prime}}))\right)^{1/2}$ $\displaystyle\leq\left(\int_{X\times Y\times Y^{2}\times Y^{3}}\left(|g_{Y^{1} }(y^{1},y^{1}{{}^{\prime}})-g_{Y^{3}}(y^{3},y^{3}{{}^{\prime}})|+|g_{Y^{2}}(y^ {2},y^{2}{{}^{\prime}})-g_{Y^{3}}(y^{3},y^{3}{{}^{\prime}}|\right)^{2}d\gamma^ {\otimes 2}\right)^{1/2}$ $\displaystyle\leq\left(\int_{X\times Y\times Y^{2}\times Y^{3}}\left(|g_{Y^{1} }(y^{1},y^{1}{{}^{\prime}})-g_{Y^{3}}(y^{3},y^{3}{{}^{\prime}})|\right)^{2}d \gamma^{\otimes 2}\right)^{1/2}$ $\displaystyle\qquad+\left(\int_{X\times Y\times Y^{2}\times Y^{3}}\left(|g_{Y^ {2}}(y^{2},y^{2}{{}^{\prime}})-g_{Y^{3}}(y^{3},y^{3}{{}^{\prime}}|\right)^{2}d \gamma^{\otimes 2}\right)^{1/2}$ (68) $\displaystyle=LGW(\mathbb{Y}^{1},\mathbb{Y}^{3};\mathbb{X},\gamma^{1},\gamma^{ 3})+LGW(\mathbb{Y}^{2},\mathbb{Y}^{3};\mathbb{X},\gamma^{2},\gamma^{3})$ $$

where (67) follows from the fact $\gamma^{1,2}$ is optimal in $\Gamma(\gamma^{1},\gamma^{2};\mu)$; (68) holds by the Minkowski inequality.
In the uniqueness assumption (E.4), we have

$$ $\displaystyle LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})\leq LGW(\mathbb{Y} ^{1},\mathbb{Y}^{3};\mathbb{X})+LGW(\mathbb{Y}^{2},\mathbb{Y}^{3};\mathbb{X}).$ $$

∎

###### Lemma E.9 (Varient Gluing lemma) .

###### Proof of Lemma E.9 .

###### Lemma E.10 (Triangle inequality for LGW) .

###### Proof of lemma E.10 .

##### Convert LPGW to LGW

The main idea of this step is similar to the proof of Proposition 3.3 in [].

Notations Setup

We can redefine $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ as

$$ $\displaystyle\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)=$ $\displaystyle\left\{\gamma\in\mathcal{M}_{+}(X\times Y^{1}\times X\times Y^{2} ):(\pi_{1,2})_{\#}\gamma\leq\gamma^{1},(\pi_{3,4})_{\#}\gamma\leq\gamma^{2},\right.$ $\displaystyle\qquad\left.(\pi_{1,3})_{\#}\gamma=(\text{id}\times{\text{id}})_{ \#}\mu^{\prime},\mu^{\prime}\leq\mu\right\}.$ (69) $$

We define auxilary points $\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3}$ and then define

$$ $\displaystyle\hat{X}$ $\displaystyle=X\cup\{\hat{\infty}_{0}\},$ $\displaystyle\hat{Y}^{1}$ $\displaystyle=Y^{1}\cup\{\hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3}\},$ $\displaystyle\hat{Y}^{2}$ $\displaystyle=Y^{2}\cup\{\hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3}\},$ $\displaystyle\hat{Y}^{3}$ $\displaystyle=Y^{3}\cup\{\hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3}\}.$ $$

and

$$ $\displaystyle\hat{\gamma}^{1}$ $\displaystyle=\gamma^{1}+|\gamma^{2}|\delta_{\hat{\infty}_{0},\hat{\infty}_{2} }+|\gamma^{3}|\delta_{\hat{\infty}_{0},\hat{\infty}_{3}}\in\mathcal{M}_{+}( \hat{X}\times\hat{Y}^{1}),$ $\displaystyle\hat{\gamma}^{2}$ $\displaystyle=\gamma^{2}+|\gamma^{1}|\delta_{\hat{\infty}_{0},\hat{\infty}_{1} }+|\gamma^{3}|\delta_{\hat{\infty}_{0},\hat{\infty}_{3}}\in\mathcal{M}_{+}( \hat{X}\times\hat{Y}^{2}),$ $\displaystyle\hat{\gamma}^{3}$ $\displaystyle=\gamma^{3}+|\gamma^{1}|\delta_{\hat{\infty}_{0},\hat{\infty}_{1} }+|\gamma^{2}|\delta_{\hat{\infty}_{0},\hat{\infty}_{2}}\in\mathcal{M}_{+}( \hat{X}\times\hat{Y}^{3}).$ $$

Define

$$ $g_{\hat{Y}^{1}}(y^{1},y^{1}{{}^{\prime}})=\begin{cases}g_{Y^{1}}(y^{1},y^{1}{{ }^{\prime}})&\text{if }y^{1},y^{1}\in Y^{1},\\ \infty&\text{elsewhere}\end{cases}$ $$

and $g_{\hat{Y}^{2}},g_{\hat{Y}^{3}}$ are defined similarly.

Finally, define

$$ $D_{\lambda}(r_{1},r_{2})=\begin{cases}|r_{1}-r_{2}|&\text{if }r_{1},r_{2}\in \mathbb{R},\\ \sqrt{\lambda}&\text{elsewhere}.\end{cases}.$ $$

Let $\hat{X}^{\prime}=X^{\prime}\cup\{\hat{\infty}_{0}\}$ to be a copy of set $\hat{X}$. Then we can set

$$ $\displaystyle\hat{\Gamma}(\hat{\gamma}^{1},\hat{\gamma}^{2};\mu):=$ $\displaystyle\left\{\hat{\gamma}\in\mathcal{M}_{+}(\hat{X}\times\hat{Y}^{1} \times\hat{X}\times\hat{Y}^{2}),(\pi_{1,2})_{\#}\hat{\gamma}=\hat{\gamma}^{1}, (\pi_{3,4})_{\#}\hat{\gamma}=\hat{\gamma}^{2},\right.$ (70) $\displaystyle\qquad\left.(\pi_{1,3})_{\#}\hat{\gamma}\mid_{X^{\otimes 2}}=( \mathrm{id}\times\mathrm{id})_{\#}\mu^{\prime},\mu^{\prime}\leq\mu\right\}.$ (71) $$

Consider the mapping:

$$ $\displaystyle\mathcal{F}:\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)\mapsto\hat{ \Gamma}(\hat{\gamma}^{1},\gamma^{2};\mu)$ $\displaystyle\gamma\mapsto\hat{\gamma}:=\gamma+(\gamma^{1}-(\pi_{1,2})_{\#} \gamma)\otimes\delta_{(\hat{\infty}_{0},\hat{\infty}_{1})}+\delta_{(\hat{ \infty}_{0},\hat{\infty}_{2})}\otimes(\gamma^{2}-(\pi_{3,4})_{\#}\gamma)+| \gamma|\delta_{(\hat{\infty}_{0},\hat{\infty}_{2}),(\infty_{0},\hat{\infty}_{1 })}$ $\displaystyle\qquad\qquad+|\gamma^{3}|\delta_{(\hat{\infty}_{0},\hat{\infty}_{ 3}),(\hat{\infty}_{0},\hat{\infty}_{3})}.$ (72) $$

By the following lemma, we show that $\mathcal{F}$ defines a equivalent relation between the two sets.

###### Lemma E.11 .

The mapping $\mathcal{F}$ defined in (72) is well-defined. In addition, it is a bijection if we set the identity $\hat{\infty}_{0}=\hat{\infty}_{1}=\hat{\infty}_{2}=\hat{\infty}_{3}$.

###### Proof of Lemma E.11 .

By [, Proposition B.1] we have for each $\gamma\in\Gamma(\gamma^{1},\gamma^{2};\mu)$,

$$ $(\pi_{1,2})_{\#}\hat{\gamma}=\hat{\gamma}^{1},(\pi_{3,4})_{\#}\hat{\gamma}= \hat{\gamma}^{2}.$ $$

In addition,

$$ $\displaystyle(\pi_{1,3})_{\#}\hat{\gamma}$ $\displaystyle=(\pi_{1,3})_{\#}\bar{\gamma}+((\pi_{1})_{\#}\gamma^{1}-(\pi_{1}) _{\#}\gamma)\otimes\delta_{\hat{\infty}_{0}}+\delta_{\hat{\infty}_{0}}\otimes( (\pi_{1})_{\#}\gamma^{2}-(\pi_{3})_{\#}\gamma)+(|\bar{\gamma}|+|\gamma^{3}|) \delta_{\hat{\infty}_{0},\hat{\infty}_{0}}.$ $$

Thus,

$$ $(\pi_{1,3})_{\#}\hat{\gamma}\mid_{X^{\otimes 2}}=(\pi_{1,3})_{\#}\gamma=( \mathrm{id}\times\mathrm{id})_{\#}(\pi_{1})_{\#}\gamma,$ $$

where $(\pi_{1})_{\#}\gamma\leq(\pi_{1})_{\#}\gamma^{1}\leq\mu$,
and we have $\mathcal{F}$ is well-defined.

It remains to show $\mathcal{F}$ is a bijection.
For each $\hat{\gamma}\in\hat{\Gamma}_{\leq}(\hat{\gamma}^{1},\hat{\gamma}^{2})$ and we define mapping

$$ $\displaystyle\mathcal{F}^{-1}:\widehat{\Gamma}(\hat{\gamma}^{1},\hat{\gamma}^{ 2};\mu)\to\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ (73) $\displaystyle\hat{\gamma}\mapsto\hat{\gamma}\mid_{X\times Y^{1}\times X\times Y ^{2}}$ $$

It remains to show $\mathcal{F}^{-1}$ is inverse of $\mathcal{F}$.

First, we claim $\mathcal{F}^{-1}$ is well-defined.
Pick $\hat{\gamma}\in\hat{\Gamma}(\hat{\gamma}^{1},\hat{\gamma}^{2})$, by Lemma [, Lemma B.1.], we have $(\pi_{X,Y^{1}})_{\#}\hat{\gamma}\leq\gamma^{1},(\pi_{3,4})_{\#}\hat{\gamma}
\leq\gamma^{2}.$
In addition,

$$ $(\pi_{1,3})_{\#}\gamma=(\pi_{1,3})_{\#}\hat{\gamma}\mid_{X^{\otimes 2}}=( \mathrm{id}\times\mathrm{id})_{\#}\mu^{\prime},$ $$

where $\mu^{\prime}\leq\mu$.
Thus, $\mathcal{F}^{-1}(\hat{\gamma})\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$.

In addition, it is straightforward to verify $\mathcal{F}^{-1}(\mathcal{F}(\gamma))=\gamma,\forall\bar{\gamma}\in\Gamma_{
\leq}(\gamma^{1},\gamma^{2};\mu)$,and then we complete the proof.
∎

It is straightforward to verify

$$ $\langle D^{2}_{\lambda}(g_{\hat{Y}^{1}},g_{\hat{Y}^{2}},\hat{\gamma}^{\otimes 2 })\rangle=\langle|g_{Y^{1}}-g_{Y^{2}}|^{2},\gamma^{\otimes 2}\rangle+\lambda(| \gamma^{1}|^{2}+|\gamma^{2}|^{2}-|\gamma|^{2})$ $$

Combine it with the above lemma, take the infimum over $\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ (equivalently, over $\hat{\Gamma}(\hat{\gamma}^{1},\hat{\gamma}^{2};\mu)$, we obtain:

$$ $\displaystyle\inf_{\hat{\gamma}\in\widehat{\Gamma}(\hat{\gamma}^{1},\hat{ \gamma}^{2};\mu)}\langle D^{2}_{\lambda}(g_{\hat{Y}^{1}},g_{\hat{Y}^{2}},\hat{ \gamma}^{\otimes 2})\rangle$ $\displaystyle=\inf_{\gamma\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)}\langle| g_{Y^{1}}-g_{Y^{2}}|^{2},\gamma^{\otimes 2}\rangle+\lambda(|\gamma^{1}|^{2}+| \gamma^{2}|^{2}-|\gamma|^{2})$ $\displaystyle=LPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^ {2})$ $$

where the second equality holds from the fact $|\nu^{1}|=|\nu^{2}|=|\nu^{3}|=|\gamma^{1}|=|\gamma^{2}|=|\gamma^{3}|$.
Similar identity holds for $LPGW(\mathbb{Y}^{1},\mathbb{Y}^{3};\mathbb{X},\gamma^{1},\gamma^{3}),LPGW(
\mathbb{Y}^{2},\mathbb{Y}^{3};\mathbb{X},\gamma^{2},\gamma^{3})$.

###### Lemma E.11 .

###### Proof of Lemma E.11 .

##### Verifying Inequality

It remains to show

$$ $\inf_{\hat{\gamma}\in\widehat{\Gamma}(\hat{\gamma}^{1},\hat{\gamma}^{2};\mu)} \langle D^{2}_{\lambda}(g_{\hat{Y}^{1}},g_{\hat{Y}^{2}},\hat{\gamma}^{\otimes 2 })\rangle^{1/2}\leq\inf_{\hat{\gamma}\in\widehat{\Gamma}(\hat{\gamma}^{1},\hat {\gamma}^{3};\mu)}\langle D^{2}_{\lambda}(g_{\hat{Y}^{1}},g_{\hat{Y}^{3}},\hat {\gamma}^{\otimes 2})\rangle^{1/2}+\inf_{\hat{\gamma}\in\widehat{\Gamma}(\hat{ \gamma}^{2},\hat{\gamma}^{3};\mu)}\langle D^{2}_{\lambda}(g_{\hat{Y}^{2}},g_{ \hat{Y}^{3}},\hat{\gamma}^{\otimes 2})\rangle^{1/2}.$ $$

Pick $\gamma^{1,2}\in\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$ that is optimal for $\langle D^{2}_{\lambda}(g_{\hat{Y}^{1}},g_{\hat{Y}^{2}},\hat{\gamma}^{\otimes 2
})\rangle^{1/2}$.
Similalry, pick optimal $\gamma^{1,3}\in\Gamma_{\leq}(\gamma^{1},\gamma^{3}),\gamma^{2,3}\in\Gamma_{
\leq}(\gamma^{2},\gamma^{3})$, we construct the corresponding optimal $\hat{\gamma}^{1,3}\in\Gamma(\hat{\gamma}^{1},\hat{\gamma}^{3};\mu),\hat{\gamma
}^{2,3}\in\Gamma(\hat{\gamma}^{2},\hat{\gamma}^{3};\mu)$.

Thus, by Gluing lemma, there exists $\gamma\in\mathcal{M}_{+}((X\times Y^{1})\times(X\times Y^{2})\times(X\times Y^
{3})))$ such that

$$ $\displaystyle(\pi_{(1,2),(5,6)})_{\#}\gamma=\hat{\gamma}^{1,3},$ $\displaystyle(\pi_{(3,4),(5,6)})_{\#}\gamma=\hat{\gamma}^{2,3}.$ $$

Now by the definition of $\hat{\Gamma}(\hat{\gamma}^{1},\hat{\gamma}^{3};\mu),\hat{\Gamma}(\hat{\gamma}^
{2},\hat{\gamma}^{3};\mu)$, we have

$$ $\displaystyle(\pi_{1,5})_{\#}\gamma=(\mathrm{id}\times\mathrm{id})_{\#}\mu^{ \prime},$ (74) $\displaystyle(\pi_{3,5})_{\#}\gamma=(\mathrm{id}\times\mathrm{id})_{\#}\mu^{ \prime\prime}$ (75) $$

for some radon measures $\mu^{\prime},\mu^{\prime\prime}\leq\mu$. Thus, we have $\mu^{\prime}=\mu^{\prime\prime}\leq\mu$. Therefore,

$$ $(\pi_{1,3})_{\#}\gamma=(\text{id}\times\text{id})_{\#}\mu^{\prime}.$ $$

In addition,

$$ $\displaystyle(\pi_{1,2})_{\#}\gamma=(\pi_{1,2})_{\#}\hat{\gamma}^{1,3}=\hat{ \gamma}^{1},$ $\displaystyle(\pi_{3,4})_{\#}\gamma=(\pi_{1,2})_{\#}\hat{\gamma}^{2,3}=\hat{ \gamma}^{2}.$ $$

So $(\pi_{1,2,3,4})_{\#}\gamma\in\Gamma(\hat{\gamma}^{1},\hat{\gamma}^{2};\mu)$.

Therefore, we have

$$ $\displaystyle\left\langle D^{2}_{\lambda}(k_{Y^{1}},k_{Y^{2}}),(\hat{\gamma}^{ 1,2})^{\otimes 2}\right\rangle^{1/2}$ $\displaystyle\leq\left\langle D^{2}_{\lambda}(k_{Y^{1}},k_{Y^{2}}),\gamma^{ \otimes 2}\right\rangle^{1/2}$ $\displaystyle\leq\left\langle D^{2}_{\lambda}(k_{Y^{1}},k_{Y^{3}}),\gamma^{ \otimes 2}\right\rangle^{1/2}+\left\langle D^{2}_{\lambda}(k_{Y^{2}},k_{Y^{3}} ),\gamma^{\otimes 2}\right\rangle^{1/2}$ $$

where the second inequality holds from [, Eq.(57)].

## Appendix F Relation Between LPGW and LGW

###### Theorem F.1 .

Suppose $|\mu|=|\nu^{1}|=|\nu^{2}|=1$ and $x,x$ is bounded, $g_{Y^{1}},g_{Y^{2}}$ are continuous function.

Choose sequence $\lambda_{n}\to\infty$, if $n$ is sufficiently large, we have $\lambda_{n}$,
then

$$ $\displaystyle LPGW_{\lambda_{n}}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})\to LGW _{\lambda_{n}}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}),$ $\displaystyle aLPGW_{\lambda_{n}}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})\to aLGW (\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}).$ $$

###### Proof of theorem F.1 .

By the lemma F.1 in [], when $n$ is sufficiently large, in particular, when

$$ $\lambda_{n}>M:=\sup_{\begin{subarray}{c}y^{1},y^{1}{{}^{\prime}}\in Y^{1}\\ y^{2},y^{2}{{}^{\prime}}\in Y^{2}\end{subarray}}|g_{Y^{1}}(y^{1},y^{1}{{}^{ \prime}})-g_{Y^{2}}(y^{1},y^{1}{{}^{\prime}})|,$ $$

for each $\gamma^{1}\in\Gamma_{\leq}^{*}(\mathbb{X},\mathbb{Y}^{1}),$ $|\gamma^{1}|=\min(|\mu|,|\nu^{1}|)=1$. That is

$$ $\Gamma^{*}_{\leq,\lambda_{n}}(\mathbb{X},\mathbb{Y}^{1})=\Gamma^{*}(\mathbb{X} ,\mathbb{Y}^{1}).$ $$

Similarly, when $n$ is sufficiently large, we have
$,\Gamma^{*}_{\leq,\lambda_{n}}(\mathbb{X},\mathbb{Y}^{2})=\Gamma^{*}(\mathbb{X
},\mathbb{Y}^{2})$.

Pick $\gamma^{1}\in\Gamma_{\leq}^{*}(\mathbb{X},\mathbb{Y}^{1})=\Gamma^{*}(\mathbb{X
},\mathbb{Y}^{1}),\gamma^{2}\in\Gamma_{\leq}^{*}(\mathbb{X},\mathbb{Y}^{2})=
\Gamma^{*}(\mathbb{X},\mathbb{Y}^{2})$, since $|\gamma^{1}|=|\mu|=|\nu^{1}|=|\nu^{2}|=1$, the mass penalty term vanishes in (55), thus we have

$$ $LPGW_{\lambda_{n}}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^ {2})=LGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1},\gamma^{2}).$ $$

Take the infimum over all $\gamma^{1},\gamma^{2}$ and the take a limit for $n\to\infty$, we prove

$$ $LPGW_{\lambda_{n}}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})\to LGW(\mathbb{Y} ^{1},\mathbb{Y}^{2};\mathbb{X}).$ $$

Similarly, in this case, $\gamma^{1}_{c}=\gamma^{2}_{c}=0$

$$ $\displaystyle LPGW_{\lambda_{n}}(\widetilde{\mathbb{Y}}_{\gamma^{1}}, \widetilde{\mathbb{Y}}_{\gamma^{2}};\mathbb{X},\widetilde{\gamma}^{1}, \widetilde{\gamma}^{2})+\lambda(|\gamma^{1}_{c}|+|\gamma^{2}_{c}|)=LGW( \widetilde{\mathbb{Y}}_{\gamma^{1}},\widetilde{\mathbb{Y}}_{\gamma^{2}}; \mathbb{X},\widetilde{\gamma}^{1},\widetilde{\gamma}^{2}).$ $$

Take the infimum on both sides over $\gamma^{1},\gamma^{2}$ and take $\lambda_{n}\to\infty$, we obtain

$$ $aLPGW(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})\to aLGW(\mathbb{Y}^{1},\mathbb {Y}^{2};\mathbb{X}).$ $$

∎

###### Theorem F.1 .

###### Proof of theorem F.1 .

## Appendix G Proof of Theorem 3.2

### G.1 Proof of Theorem 3.2 : Parts 1 , 3

- 1
Similar to proof in Theorem 2.1, in this case, we have $\mathcal{T}_{\gamma^{*}}=T$, $\gamma^{*}_{X}-a.s.$
- 3
Based on statement 2 of Theorem 3.2 (see the proof in next section), we have $\widetilde{\gamma}^{1},\widetilde{\gamma}^{2}$ are optimal solutions for $PGW_{\lambda}(\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{1}}),PGW_{\lambda}(
\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{2}})$ respectively.
By 1, we have $T^{1}=\mathcal{T}_{\gamma^{1}},T^{2}=\mathcal{T}_{\gamma^{2}}$ $\gamma^{1}_{X}\wedge\gamma^{2}_{Y}-$a.s. Thus we have:
$\displaystyle LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{
1},\gamma^{2})$
$\displaystyle=\inf_{\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_{X}}\int_{X
^{\otimes 2}}|d_{Y^{1}}(T^{1}(\cdot_{1}),T^{1}(\cdot_{2}))-d_{Y^{2}}(T^{1}(
\cdot_{1}),T^{2}(\cdot_{2}))|^{2}d(\mu^{\prime})^{\otimes 2}+\lambda(|\nu^{1}|
^{2}+|\nu^{2}|^{2}-2|\mu^{\prime}|^{2})$
$\displaystyle=\inf_{\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_{X}}\int_{X
^{\otimes 2}}|d_{Y^{1}}(\mathcal{T}_{\gamma^{1}}(\cdot_{1}),\mathcal{T}_{
\gamma^{1}}(\cdot_{2}))-d_{Y^{2}}(\mathcal{T}_{\gamma^{2}}(\cdot_{1}),\mathcal
{T}_{\gamma^{2}}(\cdot_{1})|^{2}d(\mu^{\prime})^{\otimes 2}+\lambda(|
\widetilde{\nu}_{\gamma^{1}}|^{2}+|\widetilde{\nu}_{\gamma^{2}}|^{2}-2|\mu^{
\prime}|^{2})$
$\displaystyle\qquad+\lambda(|\nu^{1}|^{2}-|\widetilde{\nu}_{\gamma^{1}}|^{2}+|
\nu^{2}|^{2}-|\widetilde{\nu}_{\gamma^{2}}|^{2})$
$\displaystyle=\inf_{\mu^{\prime}\leq\gamma^{1}_{X}\wedge\gamma^{2}_{X}}\left[
\int_{X^{\otimes 2}}|d_{Y^{1}}(\mathcal{T}_{\gamma^{1}}(\cdot_{1}),\mathcal{T}
_{\gamma^{1}}(\cdot_{2}))-d_{Y^{2}}(\mathcal{T}_{\gamma^{2}}(\cdot_{1}),
\mathcal{T}_{\gamma^{2}}(\cdot_{1})|^{2}d(\mu^{\prime})^{\otimes 2}+\lambda(|
\widetilde{\nu}_{\gamma^{1}}|^{2}+|\widetilde{\nu}_{\gamma^{2}}|^{2}-2|\mu^{
\prime}|^{2})\right]$
$\displaystyle\qquad+\lambda(|\gamma^{1}_{c}|+|\gamma_{c}^{2}|)$
(76)
$\displaystyle=LPGW_{\lambda}(\widetilde{\mathbb{Y}}_{\gamma^{1}},\widetilde{
\mathbb{Y}}_{\gamma^{2}};\mathbb{X},\gamma^{1},\gamma^{2})+\lambda(|\gamma_{c}
|^{1}+|\gamma_{c}|^{2})$
where (76) holds since
$\widetilde{\nu}^{1}=\mathcal{T}_{\gamma^{1}}\gamma^{1}_{1}=T^{1}\gamma^{1}_{1}
=(\pi_{Y})_{\#}\gamma^{1}\leq\nu^{1}.$
Thus $|\nu^{1}|^{2}-|\widetilde{\nu}^{1}|^{2}=|(\nu^{1})^{\otimes 2}-((\pi_{Y})_{\#}
\gamma^{1})^{\otimes 2}|=|\gamma^{1}_{c}|$; and similarly we have
$|\nu^{2}|^{2}-|\widetilde{\nu}^{2}|^{2}=|\gamma^{2}_{c}|$.

### G.2 Proof of Theorem 3.2 : Part 2

#### G.2.1 Proof in the discrete case.

Notation setup

We first demonstrate a simplified proof in the discrete case. Next, we will provide the proof of the statement in the general case.

Suppose

$$ $\displaystyle\mu=\sum_{i=1}^{n}p_{i}x_{i},\qquad\nu=\sum_{j=1}^{m}q_{j}y_{j},$ $\displaystyle g_{X}(x,x^{\prime})=x^{\top}x^{\prime},\qquad\forall x,x^{\prime }\in X,$ $\displaystyle g_{X}(y,y^{\prime})=y^{\top}y^{\prime},\qquad\forall y,y^{\prime }\in Y.$ $$

Choose $\gamma^{*}\in\Gamma^{*}_{\leq}(\mathbb{X},\mathbb{Y})$, we obtain the corresponding barycentric projected measure:

$\widetilde{\nu}:=\widetilde{\nu}_{\gamma^{*}}=\sum_{i=1}^{n}\widetilde{q}_{i}
\widetilde{y}_{i}$ with

$$ $\displaystyle\widetilde{q}_{i}=\sum_{j=1}^{n}\gamma^{*}_{i,j},\qquad\forall i \in[1:n],$ (77) $\displaystyle\widetilde{y}_{i}=\begin{cases}\frac{1}{\widetilde{q}_{i}^{1}} \gamma_{ij}^{*}x_{i}&\text{if }\widetilde{q}_{i}>0,\\ 0&\text{elsewhere}.\end{cases}.$ (78) $$

Then $\widetilde{\mathbb{Y}}_{\gamma^{*}}=(Y,g_{Y},\widetilde{\nu})$,
$\widetilde{\gamma}^{*}=\text{diag}(\widetilde{q}_{1},\ldots\widetilde{q}_{n})$. Our goal is to show $\widetilde{\gamma}^{*}=\text{diag}(\widetilde{q}_{1},\ldots,\widetilde{q}_{n})$ is optimal in $PGW_{\lambda}(\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{*}})$.

Pick $\widetilde{\gamma}\in\Gamma_{\leq}(p,\widetilde{q}):=\Gamma_{\leq}(\mu,
\widetilde{\nu})$, similar to section D.5, we set diagonal matrix
$(\widetilde{\gamma}^{*})^{-1}\in\mathbb{R}_{+}^{n\times n}$ as

$$ $\displaystyle(\widetilde{\gamma}^{*})^{-1}_{ii}=\begin{cases}\frac{1}{ \widetilde{q}_{i}}&\text{if }\widetilde{q}_{i}>0,\\ 0&\text{elsewhere}.\end{cases}$ $$

Let $\gamma:=\widetilde{\gamma}(\widetilde{\gamma}^{*})^{-1}\gamma^{*}\in\mathbb{R}
_{+}^{n\times m}$.
Let $\gamma_{X}:=\gamma 1_{m}$ and $\gamma_{Y}:=\gamma^{\top}1_{n}$.

In addition, we set $D=\{i:\widetilde{q}_{i}>0\}$, and $1_{D}\in\mathbb{R}^{n}$ with $1_{D}[i]=1,\forall i\in D$ and $1_{D}[i]=0$ elsewhere. Then we have:

$$ $\displaystyle\gamma 1_{m}=\widetilde{\gamma}(\widetilde{\gamma}^{*})^{-1} \gamma^{*}1_{m}=\widetilde{\gamma}(\widetilde{\gamma}^{*})^{-1}\widetilde{q}= \widetilde{\gamma}1_{D}=\widetilde{\gamma}_{X}\leq p_{0},$ (79) $\displaystyle\gamma^{\top}1_{n}=(\gamma^{*})^{\top}(\widetilde{\gamma}^{*})^{- 1}\widetilde{\gamma}^{\top}1_{n}\leq(\gamma^{*})^{\top}(\widetilde{\gamma}^{*} )^{-1}\widetilde{q}=(\gamma^{*})^{\top}1_{D}=\gamma^{*}_{Y}\leq q.$ (80) $$

Therefore, $\gamma_{X}\leq\widetilde{\gamma}_{X}\leq p$, $\gamma_{Y}\leq\gamma^{*}_{Y}\leq q$. Thus,
$\gamma\in\Gamma_{\leq}(p,q)$.

Relation between $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ and $PGW_{\lambda}(\mathbb{X},\widetilde{\mathbb{Y}})$.

Similar to (44),(47), we obtain

$$ $\displaystyle C(\gamma^{*};\mathbb{X},\mathbb{Y},\lambda)$ $\displaystyle=\langle(x^{\top}x^{\prime})^{2},(\gamma^{*}_{X})^{\otimes 2} \rangle+\langle(y^{\top}y^{\prime})^{2},(\gamma^{*}_{Y})^{\otimes 2}\rangle+ \lambda(|p|^{2}+|q|^{2}-2|\gamma^{*}|)$ $\displaystyle-2\sum_{i,i^{\prime}=1}^{n}\sum_{j,j^{\prime}=1}^{m}x_{i}^{\top}x _{i}^{\prime}y_{j}^{\top}y_{j}^{\prime}\gamma^{*}_{i,j}\gamma^{*}_{i^{\prime}, j^{\prime}}$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}},\lambda)$ $\displaystyle=\langle(x^{\top}x^{\prime})^{2},(\widetilde{\gamma}^{*}_{X})^{ \otimes 2}\rangle+\langle(y^{\top}y^{\prime})^{2},(\widetilde{\gamma}^{*}_{Y}) ^{\otimes 2}\rangle+\lambda(|p|^{2}+|\widetilde{q}|^{2}-2|\widetilde{\gamma}^{ *}|)$ $\displaystyle-2\sum_{i,i^{\prime}=1}^{n}\sum_{j,j^{\prime}=1}^{m}x_{i}^{\top}x _{i}^{\prime}y_{j}^{\top}y_{j}\gamma^{*}_{i,j}\gamma^{*}_{i^{\prime},j^{\prime}}$ $$

where $(x^{\top}x^{\prime})^{2}:=[(x_{i}^{\top}x^{\prime}_{i^{\prime}})^{2}]_{i,i^{
\prime}\in[1:n]}\in\mathbb{R}^{n\times n}$, $(\gamma_{X}^{*})^{\otimes 2}=\gamma_{X}^{*}(\gamma_{X}^{*})^{\top}$,
$\langle(x^{\top}x^{\prime})^{2},(\gamma^{*}_{X})^{\otimes 2}\rangle:=\sum_{i,i
^{\prime}=1}^{n}(x_{i}^{\top}x^{\prime}_{i^{\prime}})^{2}(\gamma^{*}_{X})_{i}(
\gamma^{*}_{X})_{i^{\prime}}$, is the element-wise dot product.
All other notations are defined similarly.

Combined the above two equalities with the fact $|\gamma^{*}|=|\gamma^{*}_{Y}|$ and $\gamma_{X}^{*}=\widetilde{\gamma}_{X}^{*}$, we obtain:

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mu,\widetilde{\nu},\lambda)=C(\gamma^{ *};\mathbb{X},\mathbb{Y},\lambda)+\langle(\widetilde{y}^{\top}\widetilde{y}^{ \prime})^{2},(\widetilde{\gamma}^{*}_{Y})^{\otimes 2}\rangle-\langle(y^{\top}y ^{\prime})^{2},(\gamma^{*}_{Y})^{\otimes 2}\rangle+\lambda(|q|^{2}-|\widetilde {q}|^{2}).$ (81) $$

Similarly, from the fact $\gamma_{X}=\widetilde{\gamma}_{X}$ (see (79)) we obtain

$$ $\displaystyle C(\widetilde{\gamma};\mu,\widetilde{\nu},\lambda)=C(\gamma; \mathbb{X},\mathbb{Y},\lambda)+\langle(\widetilde{y}^{\top}\widetilde{y}^{ \prime})^{2},(\widetilde{\gamma}_{Y})^{\otimes 2}\rangle-\langle(y^{\top}y^{ \prime})^{2},(\gamma_{Y})^{\otimes 2}\rangle+\lambda(|q|^{2}-|\widetilde{q}|^{ 2}).$ (82) $$

Thus

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}}, \lambda)-C(\widetilde{\gamma};\mathbb{X},\widetilde{\mathbb{Y}},\lambda)$ $\displaystyle=C(\gamma^{*};\mathbb{X},\mathbb{Y},\lambda)-C(\gamma;\mathbb{X}, \mathbb{Y},\lambda)+\langle(\widetilde{y}^{\top}\widetilde{y}^{\prime})^{2},( \widetilde{\gamma}^{*}_{Y})^{\otimes 2}-(\widetilde{\gamma}_{Y})^{\otimes 2} \rangle-\langle(y^{\top}y^{\prime})^{2},(\gamma_{Y}^{*})^{\otimes 2}-(\gamma_{ Y})^{\otimes 2}\rangle$ $\displaystyle\leq\langle(\widetilde{y}^{\top}\widetilde{y}^{\prime})^{2},( \widetilde{\gamma}^{*}_{Y})^{\otimes 2}-(\widetilde{\gamma}_{Y})^{\otimes 2} \rangle-\langle(y^{\top}y^{\prime})^{2},(\gamma_{Y}^{*})^{\otimes 2}-(\gamma_{ Y})^{\otimes 2}\rangle$ (83) $\displaystyle=\sum_{i,i^{\prime}\in D}(\widetilde{y}^{\top}_{i}\widetilde{y}_{ i^{\prime}})^{2}((\widetilde{\gamma}^{*}_{Y})_{i}(\widetilde{\gamma}^{*}_{Y})_ {i^{\prime}}-(\widetilde{\gamma}_{Y})_{i}(\widetilde{\gamma}_{Y})_{i^{\prime}} )-\sum_{j,j^{\prime}=1}^{m}(y_{j}^{\top}y_{j^{\prime}})^{2}((\gamma^{*}_{Y})_{ j}(\gamma^{*}_{Y})_{j^{\prime}}-(\gamma_{Y})_{j}(\gamma_{Y})_{j^{\prime}})$ $\displaystyle\leq\sum_{i,i^{\prime}\in D}\sum_{j,j^{\prime}=1}^{m}\frac{\gamma ^{*}_{i,j}\gamma^{*}_{i,j^{\prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{ \prime}}^{1}}((x_{i}^{\top}x_{i^{\prime}})^{2})((\widetilde{\gamma}^{*}_{Y})_{ i}(\widetilde{\gamma}^{*}_{Y})_{i^{\prime}}-(\widetilde{\gamma}_{Y})_{i}( \widetilde{\gamma}_{Y})_{i^{\prime}})$ $\displaystyle\qquad-\sum_{j,j^{\prime}=1}^{m}(y^{\top}_{j}y_{j^{\prime}})^{2}( (\gamma^{*}_{Y})_{j}(\gamma^{*}_{Y})_{j^{\prime}}-(\gamma_{Y})_{j}(\gamma_{Y}) _{j^{\prime}})$ (84) $\displaystyle=\sum_{j,j^{\prime}=1}^{m}(y_{j}^{\top}y_{j^{\prime}})^{2}\left( \sum_{i,i^{\prime}\in D}\frac{\gamma^{*}_{i,j}\gamma^{*}_{i,j^{\prime}}}{ \widetilde{q}_{i}^{1}\widetilde{q}_{i^{\prime}}^{1}}((\widetilde{\gamma}^{*}_{ Y})_{i}(\widetilde{\gamma}^{*}_{Y})_{i^{\prime}}-(\widetilde{\gamma}_{Y})_{i}( \widetilde{\gamma}_{Y})_{i^{\prime}})-((\gamma^{*}_{Y})_{j}(\gamma^{*}_{Y})_{j ^{\prime}}-(\gamma_{Y})_{j}(\gamma_{Y})_{j^{\prime}})\right)$ $\displaystyle=0$ (85) $$

where (83) holds since $\gamma^{1}$ is optimal in $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$; (84) follows from the facts $\gamma_{Y}\leq\gamma^{*}_{Y}$ (see (80)), and the fact

$$ $\widetilde{y}_{i}^{\top}\widetilde{y}_{i}^{\prime}=\sum_{j=1}^{m}\sum_{j^{ \prime}=1}^{m}\frac{\gamma_{i,j}\gamma_{i^{\prime},j^{\prime}}y_{j}^{\top}y^{ \prime}_{j^{\prime}}}{\widetilde{q}_{i}\widetilde{q}_{i}^{\prime}},\forall i,i ^{\prime}\in D$ $$

and Jensen’s inequality:

$$ $(\widetilde{y}^{\top}_{i}\widetilde{y}^{\prime}_{i})^{2}\leq\sum_{j=1}^{m}\sum _{j^{\prime}=1}^{m}\frac{\gamma_{i,j}\gamma_{i^{\prime},j^{\prime}}(y^{\top}_{ j}y^{\prime}_{i})^{2}}{\widetilde{q}_{i}\widetilde{q}_{i}^{\prime}}.$ $$

The last equality (85) holds from the following:

For each $(j,j^{\prime}\in[1:m])$, we have

$$ $\displaystyle\sum_{i,i^{\prime}\in D}\frac{\gamma^{*}_{i,j}\gamma^{*}_{i,j^{ \prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{\prime}}^{1}}((\widetilde{ \gamma}_{Y}^{1})_{i}(\widetilde{\gamma}^{*}_{Y})_{i^{\prime}}-(\widetilde{ \gamma}_{Y})_{i}(\widetilde{\gamma}_{Y})_{i^{\prime}})-((\gamma^{*}_{Y})_{j}( \gamma^{*}_{Y})_{j^{\prime}}-(\gamma_{Y})_{j}(\gamma_{Y})_{j^{\prime}})$ $\displaystyle=\underbrace{\left(\sum_{i,i^{\prime}\in D}\frac{\gamma^{*}_{i,j} \gamma^{*}_{i,j^{\prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{\prime}}^{1} }(\widetilde{\gamma}^{*}_{Y})_{i}(\widetilde{\gamma}^{*}_{Y})_{i^{\prime}} \right)-(\gamma^{*}_{Y})_{j}(\gamma^{*}_{Y})_{j^{\prime}}}_{A}-\underbrace{ \left(\sum_{i,i^{\prime}\in D}\frac{\gamma^{*}_{i,j}\gamma^{*}_{i,j^{\prime}}} {\widetilde{q}_{i}\widetilde{q}_{i^{\prime}}}(\widetilde{\gamma}_{Y})_{i}( \widetilde{\gamma}_{Y})_{i^{\prime}}\right)-(\gamma_{Y})_{j}(\gamma_{Y})_{j^{ \prime}}}_{B},$ $$

where

$$ $\displaystyle A$ $\displaystyle=\sum_{i,i^{\prime}\in D}\frac{\gamma^{*}_{i,j}\gamma^{*}_{i^{ \prime},j^{\prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{\prime}}^{1}} \widetilde{q}_{i}^{1}\widetilde{q}_{i^{\prime}}^{1}-\widetilde{q}_{j}^{1} \widetilde{q}_{j^{\prime}}^{1}$ $\displaystyle=\sum_{i,i^{\prime}\in D}\gamma^{*}_{i,j}\gamma^{*}_{i^{\prime},j ^{\prime}}-\widetilde{q}_{j}^{1}\widetilde{q}_{j^{\prime}}^{1}$ $\displaystyle=\left(\sum_{i\in D}\gamma^{*}_{i,j}\right)\left(\sum_{i^{\prime} \in D}\gamma^{*}_{i^{\prime},j^{\prime}}\right)-\widetilde{q}_{j}^{1} \widetilde{q}_{j^{\prime}}^{1}=0$ $\displaystyle B$ $\displaystyle=\sum_{i,i^{\prime}\in D}\frac{\gamma^{*}_{i,j}\gamma^{*}_{i,j^{ \prime}}}{\widetilde{q}_{i}\widetilde{q}_{i^{\prime}}}\sum_{k,k^{\prime}=1}^{n }\widetilde{\gamma}_{k,i}\widetilde{\gamma}_{k^{\prime},i^{\prime}}-\sum_{k,k^ {\prime}=1}^{n}\gamma_{k,j}\gamma_{k^{\prime},j^{\prime}}$ $\displaystyle=\sum_{i,i^{\prime}\in D}\sum_{k,k^{\prime}=1}^{n}\frac{\gamma^{* }_{i,j}\gamma^{*}_{i,j^{\prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{ \prime}}}\widetilde{\gamma}_{k,i}\widetilde{\gamma}_{k^{\prime},i^{\prime}}- \sum_{k,k^{\prime}=1}^{n}(\sum_{i\in D}\frac{\widetilde{\gamma}_{k,i}\gamma^{* }_{i,j}}{\widetilde{q}_{i}})(\sum_{i\in D}\frac{\widetilde{\gamma}_{k^{\prime} ,i^{\prime}}\gamma^{*}_{i^{\prime},j^{\prime}}}{\widetilde{q}_{i^{\prime}}})$ $\displaystyle=\sum_{i,i^{\prime}\in D}\sum_{k,k^{\prime}=1}^{n}\frac{\gamma^{* }_{i,j}\gamma^{*}_{i,j^{\prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{ \prime}}}\widetilde{\gamma}_{k,i}\widetilde{\gamma}_{k^{\prime},i^{\prime}}- \sum_{i,i^{\prime}\in D}\sum_{k,k^{\prime}=1}^{n}\frac{\widetilde{\gamma}_{k,i }\widetilde{\gamma}_{k^{\prime},i^{\prime}}\gamma^{*}_{i,j}\gamma^{*}_{i^{ \prime},j^{\prime}}}{\widetilde{q}_{i}^{1}\widetilde{q}_{i^{\prime}}^{1}}$ $\displaystyle=0$ $$

and thus we complete the proof.

### G.3 Proof for the general case

#### G.3.1 Notation setup and related lemma

Suppose

$$ $g_{X}(x,x^{\prime})=\alpha_{0}x^{\top}x^{\prime},g_{Y}=\alpha x^{\top}y^{ \prime},\forall x,x^{\prime}\in X,Y,y^{\prime}\in X.$ $$

Choose $\gamma^{*}\in\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y})$. The barycentric projection mapping is

$$ $\mathcal{T}_{\gamma^{*}}(x):=\int y^{\prime}d\gamma^{*}(y^{\prime}|x^{\prime}) ,\forall x\in\text{supp}(\mu).$ $$

We obtain:
$\widetilde{\nu}:=\widetilde{\nu}_{\gamma^{*}}=(\mathcal{T}_{\gamma^{*}})_{\#}\mu$, $\widetilde{\gamma}^{*}=(\mathrm{id}\times\mathcal{T}_{\gamma^{*}})_{\#}\mu$ and we $\widetilde{\mathbb{Y}}_{\gamma^{*}}:=(X,g_{Y},\widetilde{\nu})$.

Our goal is to show $\widetilde{\nu}$ is optimal in $PGW_{\lambda}(\mathbb{X},\widetilde{\mathbb{Y}})$. Equivalently, pick $\widetilde{\gamma}\in\Gamma_{\leq}(\mu,\widetilde{\nu})$, we need to show

$$ $C(\widetilde{\gamma}^{*};\mathbb{X},\mathbb{Y},\lambda)\leq C(\widetilde{ \gamma};\mathbb{X},\mathbb{Y},\lambda).$ $$

Set $\gamma$ from (42):

$$ $\gamma=\gamma^{*}_{Y|X}\widetilde{\gamma}^{*}_{X|Y}\widetilde{\gamma},$ $$

we have $\gamma$ satisfies the following two lemma:

###### Lemma G.1 .

Choose $\gamma^{*}\in\Gamma_{\leq}(\mu,\nu),\widetilde{\gamma}\in\Gamma_{\leq}(\mu,
\widetilde{\nu})$. Set $\widetilde{\nu}=(\mathcal{T}_{\gamma^{*}})_{\#}\mu$,
then $\gamma$ defined in (42) satisfies the following:

- (a)
$\gamma\in\Gamma_{\leq}((\pi_{X})_{\#}\widetilde{\gamma},(\pi_{Y})_{\#}\gamma^{
*})\subset\Gamma_{\leq}(\mu,\nu^{1})$, furthermore:
$\displaystyle(\pi_{X})_{\#}\gamma$
$\displaystyle=(\pi_{X})_{\#}\widetilde{\gamma}$
(86)
$\displaystyle(\pi_{Y})_{\#}\gamma$
$\displaystyle\leq(\pi_{Y})_{\#}\gamma^{*}$
(87)
- (b)
If $\widetilde{\gamma}=\widetilde{\gamma}^{*}$, then $\gamma=\gamma^{*}$.
- (c)
Regarding the second marginal of $\gamma$, we have for each test function $\phi_{X}\in C_{0}(X)$:
$\displaystyle\int_{X}\phi_{Y}(y)d\gamma_{Y}(y)=\int_{Y\times X\times Y\times X
}\phi_{Y}(y)d\widetilde{\gamma}^{*}(y|x^{0})d\widetilde{\gamma}^{*}(x^{0}|
\widetilde{y})d\widetilde{\gamma}_{Y}(\widetilde{y}).$
(88)

###### Proof.

- (a)
Note, in discrete setting, this statement has been proved in (79),(80).
Pick test functions $\phi_{X}\in C_{0}(X),\phi_{Y}\in C_{0}(Y)$ with $\phi_{Y}\geq 0$, we have:
$\displaystyle\langle\phi_{X},\gamma\rangle$
$\displaystyle=\int_{X\times Y}\phi_{X}(x)d\gamma(x,y)$
$\displaystyle=\int_{X\times Y}\int_{X}\int_{Y}\phi_{X}(x)d\gamma^{*}(y|x^{0})d
\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}(x,\widetilde{y})$
$\displaystyle=\int_{X\times Y}\phi_{X}(x)d\widetilde{\gamma}(x,\widetilde{y})$
$\displaystyle=\int_{X}\phi_{X}(x)d\widetilde{\gamma}_{X}(x)$
$\displaystyle\langle\phi_{Y},\gamma_{Y}\rangle$
$\displaystyle=\int_{X\times Y}\phi_{Y}(y)d\gamma(x,y)$
$\displaystyle=\int_{X\times Y\times X\times Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d
\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}(x,\widetilde{y})$
$\displaystyle=\int_{X\times X}\int_{X}\int_{Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d
\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}_{Y}(\widetilde{
y})$
$\displaystyle\leq\int_{X\times Y}\int_{X}\int_{Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0
})d\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}^{*}_{Y}(
\widetilde{y})$
$\displaystyle=\int_{X\times Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d\widetilde{
\gamma}^{*}_{X}(x^{0})$
$\displaystyle=\int_{X\times Y}\phi_{Y}(y)d\gamma^{*}(y|x^{0})d\gamma^{*}_{X}(x
^{0})$
$\displaystyle=\int_{Y}\phi_{Y}(y)d\gamma^{*}_{Y}(y)$
where the inequality holds from the fact $\widetilde{\gamma}_{Y}\leq\widetilde{\gamma}^{*}_{Y}$.
- (b)
If $\widetilde{\gamma}=\widetilde{\gamma}^{*}$, pick $\phi\in C_{0}(X\times X)$, we have:
$\displaystyle\langle\phi,\gamma\rangle$
$\displaystyle=\int_{X\times Y}\int_{X}\int_{Y}\phi(x,y)d\gamma^{*}(y|x^{0})d
\widetilde{\gamma}^{*}(x^{0}|\widetilde{y})d\widetilde{\gamma}^{*}(\widetilde{
y}|x)d\widetilde{\gamma}^{*}_{X}(x)$
$\displaystyle=\int_{X\times Y}\int_{X}\int_{Y}\phi(x,y)d\gamma^{*}(y|x^{0})d
\widetilde{\gamma}^{*}_{X}(x)$
$\displaystyle=\int_{X\times Y}\int_{X}\phi(x,y)d\gamma^{*}(y|x^{0})\delta(x-x^
{0})d\gamma^{*}_{X}(x)$
$\displaystyle=\int_{X\times Y}\phi(x,y)d\gamma^{*}(y|x)d\gamma^{*}_{X}(x)$
$\displaystyle=\int_{X\times X}\phi(x,y)d\gamma^{*}(x,y)$
- (c)
It follows directly from the definition of $\gamma$.

∎

###### Lemma G.1 .

###### Proof.

#### G.3.2 Relation between P ⁢ G ⁢ W λ ⁢ ( 𝕏 , 𝕐 ) 𝑃 𝐺 subscript 𝑊 𝜆 𝕏 𝕐 PGW_{\lambda}(\mathbb{X},\mathbb{Y}) italic_P italic_G italic_W start_POSTSUBSCRIPT italic_λ end_POSTSUBSCRIPT ( blackboard_X , blackboard_Y ) and P ⁢ G ⁢ W λ ⁢ ( 𝕏 , 𝕐 ~ ) 𝑃 𝐺 subscript 𝑊 𝜆 𝕏 ~ 𝕐 PGW_{\lambda}(\mathbb{X},\widetilde{\mathbb{Y}}) italic_P italic_G italic_W start_POSTSUBSCRIPT italic_λ end_POSTSUBSCRIPT ( blackboard_X , over~ start_ARG blackboard_Y end_ARG ) .

From (44),(47),(50),(51) and (52), we obtain:

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}},\lambda)$ $\displaystyle=C(\gamma^{*};\mathbb{X},\mathbb{Y},\lambda)+\langle g^{2}_{Y},( \widetilde{\gamma}^{*}_{Y})^{\otimes 2}\rangle-\langle g_{Y}^{2},(\gamma^{*}_{ Y})^{\otimes 2}\rangle+\lambda(|\nu|^{2}-|\widetilde{\nu}|^{2})$ (89) $\displaystyle C(\widetilde{\gamma};\mathbb{X},\widetilde{\mathbb{Y}},\lambda)$ $\displaystyle=C(\gamma;\mathbb{X},\mathbb{Y},\lambda)+\langle g^{2}_{Y},( \widetilde{\gamma}_{Y})^{\otimes 2}\rangle-\langle g_{Y}^{2},(\gamma_{Y})^{ \otimes 2}\rangle+\lambda(|\nu|^{2}-|\widetilde{\nu}|^{2})$ (90) $$

From (89)-(90), we obtain

$$ $\displaystyle C(\widetilde{\gamma}^{*};\mathbb{X},\widetilde{\mathbb{Y}}, \lambda)-C(\widetilde{\gamma};\mathbb{X},\widetilde{\mathbb{Y}},\lambda)$ $\displaystyle=\left(C(\gamma^{*};\mathbb{X},\mathbb{Y},\lambda)-C(\gamma; \mathbb{X},\mathbb{Y},\lambda)\right)+((\widetilde{\gamma}^{*})^{\otimes 2}- \widetilde{\gamma}^{\otimes 2}))(g_{Y}^{2}(\widetilde{y},\widetilde{y}^{\prime }))-((\gamma^{*})^{\otimes 2}-\gamma^{\otimes 2})(g_{Y}^{2}(x,y^{\prime}))$ $\displaystyle\leq\underbrace{\langle g_{Y}^{2},(\widetilde{\gamma}^{*}_{Y})^{ \otimes 2}-(\widetilde{\gamma}_{Y})^{\otimes 2}\rangle}_{A}-\langle g_{Y}^{2}, (\gamma^{*}_{Y})^{\otimes 2}-\gamma_{Y}^{\otimes 2}\rangle$ (91) $$

where $(\ref{pf:pgw_bp_gamma*_opt})$ holds from the fact $\gamma^{*}$ is optimal in $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$.

In addition, pick $\widetilde{y},\widetilde{y}^{\prime}\in\text{supp}(\widetilde{\gamma}_{Y}^{*})$, then
for each $x\in\text{supp}(\widetilde{\gamma}^{*}(\cdot_{1}|y)),x^{\prime}\in\text{supp}(
\widetilde{\gamma}^{*}(\cdot_{1}|y^{\prime}))$, we have:

$$ $\widetilde{y}=\mathcal{T}_{\gamma^{*}}(x),\widetilde{y}^{\prime}=\mathcal{T}_{ \gamma^{*}}(x^{\prime}).$ $$

Thus,

$$ $A=\int_{(X\times Y)^{\otimes 2}}\int_{X^{\otimes 2}}g_{Y}^{2}(\mathcal{T}_{ \gamma^{*}}(x^{0}),\mathcal{T}_{\gamma^{*}}(x^{0}{{}^{\prime}}))d(\gamma^{ \otimes 2}_{X|Y})((x^{0},x^{0}{{}^{\prime}})|\widetilde{(}y,\widetilde{y}^{ \prime}))d((\widetilde{\gamma}_{Y}^{*})^{\otimes 2}-(\widetilde{\gamma}_{Y})^{ \otimes 2})((x,x^{\prime}),(\widetilde{y},\widetilde{y}^{\prime}))$ $$

From Lemma D.2 and Jensen’s inequality

$$ $\displaystyle g_{Y}^{2}(\mathcal{T}_{\gamma^{*}}(x^{0}),\mathcal{T}_{\gamma^{* }}(x^{0}{{}^{\prime}}))$ $\displaystyle=\left(\int_{Y^{\otimes 2}}g_{Y}(y,y^{\prime})d\gamma^{*}(y|x^{0} )d\gamma^{*}(y^{\prime}|x^{\prime 0}{{}^{\prime}})\right)^{2}$ $\displaystyle\leq\int_{Y^{\otimes 2}}g_{Y}^{2}(y,y^{\prime})d\gamma^{*}(y|x^{0 })d\gamma^{*}(y^{\prime}|x^{\prime 0}{{}^{\prime}}).$ $$

Combined it with the fact $\widetilde{\gamma}^{*}_{Y}\leq\widetilde{\gamma}_{Y}$ (see Lemma G.1 (a)), we obtain

$$ $\displaystyle A$ $\displaystyle\leq\int_{(X\times Y)^{\otimes 2}}\int_{X^{\otimes 2}}g_{Y}^{2}(y ,y^{\prime})d\gamma^{*}(y|x^{0})d\gamma^{*}(y^{\prime}|x^{\prime 0}{{}^{\prime }})d\widetilde{\gamma}^{*}(x^{0}|y)d\widetilde{\gamma}^{*}(x^{0}{{}^{\prime}}| y^{\prime})d\left((\widetilde{\gamma}^{*}_{Y})^{\otimes 2}-\widetilde{\gamma}_ {Y}^{\otimes 2})\right)((x,x^{\prime}),(y,y^{\prime}))$ $\displaystyle=\langle g_{Y}^{2},(\gamma^{*})^{\otimes 2}_{Y|X}(\widetilde{ \gamma}^{*})^{\otimes 2}_{X|Y}((\widetilde{\gamma}_{Y}^{*})^{\otimes 2}-( \widetilde{\gamma}_{Y})^{\otimes 2})\rangle.$ (92) $$

Thus, we can continue bound (91):

$$ $\displaystyle(\ref{pf:pgw_bp_gamma*_opt})$ $\displaystyle\leq\langle g_{Y}^{2},(\gamma^{*})^{\otimes 2}_{Y|X}(\widetilde{ \gamma}^{*})^{\otimes 2}_{X|Y}((\widetilde{\gamma}_{Y}^{*})^{\otimes 2}-( \widetilde{\gamma}_{Y})^{\otimes 2})\rangle-\langle g_{Y}^{2},(\gamma^{*}_{Y}) ^{\otimes 2}-\gamma_{Y}^{\otimes 2}\rangle$ $\displaystyle=\underbrace{\langle g_{Y},(\gamma^{*})^{\otimes 2}_{Y|X}( \widetilde{\gamma}^{*})^{\otimes 2}_{X|Y}(\widetilde{\gamma}_{Y}^{*})^{\otimes 2 }-(\gamma^{*}_{Y})^{\otimes 2}\rangle}_{B_{1}}$ $\displaystyle-\underbrace{\langle g_{Y},(\gamma^{*})^{\otimes 2}_{Y|X}( \widetilde{\gamma}^{*})^{\otimes 2}_{X|Y}(\widetilde{\gamma}_{Y})^{\otimes 2}- (\gamma_{Y})^{\otimes 2}\rangle}_{B_{2}},$ (93) $$

where
$B_{2}=0$ from lemma G.1 (c) and
$B_{1}=B_{2}$ from lemma G.1(b).
Therefore we complete the proof.

## Appendix H Special Case: Linear Mass-Constrained Partial Gromov-Wasserstein Distance

In this section, we introduce the linearization technique for the “mass-constraint” 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:

$$ $\displaystyle MPGW_{\rho}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\Gamma_{\leq}^ {\eta}(\mu,\nu)}\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(y,y{{ }^{\prime}})|^{2}d\gamma^{\otimes},$ (94) $$

where $\eta\in[0,\min(|\mu|,|\nu^{1}|)]$ is a fixed number.

$$ $\Gamma_{\leq}^{\eta}(\mu,\nu)=\{\gamma\in\mathcal{M}_{+}(X\times Y):(\pi_{X})_ {\#}\gamma\leq\mu,(\pi_{Y})_{\#}\gamma\leq\nu,|\gamma|=\eta\},$ $$

We use $\Gamma^{\eta}_{\leq}(\mathbb{X},\mathbb{Y}^{1})$ to denote the set of all optimal transportation plans.

Consider the following gm-spaces $\mathbb{X}=(X,g_{X},\mu),\mathbb{Y}^{1}=(Y^{1},g_{Y^{1}},\nu^{1}),\mathbb{Y}^{
2}=(Y^{2},g_{Y^{2}},\nu^{2})$, given $\eta\in[0,\min(|\nu^{1}|,|\nu^{2}|)$ and we suppose $|\mu|=\eta$. Choose $\gamma^{1}\in\Gamma^{\eta}_{\leq}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}\in
\Gamma^{\eta}_{\leq}(\mathbb{X},\mathbb{Y}^{2})$. Suppose the Monge mapping assumption hold and let $T^{1},T^{2}$ be the corresponding transportation plan. We define

$$ $k_{\gamma^{1}}:(\cdot_{1},\cdot_{2})\mapsto d_{X}(\cdot_{1},\cdot_{2})-d_{Y^{1 }}(T_{1}(\cdot_{1}),T_{1}(\cdot_{2}))$ $$

as linear MPGW embedding of $\mathbb{Y}^{1}$ given $\gamma^{1}$. $k_{\gamma^{2}}$ is defined similalry.

Thus, similar to (14) and (7), the linear M-PGW distance between $\mathbb{Y}^{1},\mathbb{Y}^{2}$, given $\gamma^{1},\gamma^{2}$ is defined as

$$ $\displaystyle LMPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1} ,\gamma^{2})$ $\displaystyle:=\|k_{\gamma^{1}}-k_{\gamma^{2}}\|^{2}_{\mu^{\otimes 2}}.$ (95) $$

and similar to (7),(14), the general case without Monge mapping assumption is

$$ $\displaystyle LMPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y};\mathbb{X},\gamma^{1}, \gamma^{2})$ $\displaystyle:=\inf_{\gamma\in\Gamma_{\leq}^{\eta}(\gamma^{1},\gamma^{2};\mu)} \int_{(X\times Y)^{\otimes 2}}|g_{X}-g_{Y}|^{2}d\gamma^{\otimes 2},$ (96) $$

where $\Gamma_{\leq}^{\rho}(\gamma^{1},\gamma^{2};\mu):=\{\gamma\in\mathcal{M}_{+}(X
\times Y^{1}\times Y^{2}):(\pi_{X,Y^{1}})_{\#}\gamma\leq\gamma^{1},(\pi_{X,Y^{
2}})_{\#}\gamma\leq\gamma^{2},|\gamma|=\eta\}.$
And similar to (10),(18), by applying barycentric projection $\mathcal{T}_{\gamma^{1}},\mathcal{T}_{\gamma^{2}}$, we define the approximated linear-MPGW distance as follows:

$$ $\displaystyle aLMPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X}):=\inf_{ \begin{subarray}{c}\gamma^{1}\in\Gamma^{\rho}_{\leq}(\mathbb{X},\mathbb{Y}^{1} )\\ \gamma^{2}\in\Gamma^{\rho}_{\leq}(\mathbb{X},\mathbb{Y}^{2})\end{subarray}} LMPGW(\widehat{\mathbb{Y}}^{1},\widehat{\mathbb{Y}}^{2};\mathbb{X})$ $\displaystyle=\inf_{\begin{subarray}{c}\gamma^{1}\in\Gamma^{\rho}_{\leq}( \mathbb{X},\mathbb{Y}^{1})\\ \gamma^{2}\in\Gamma^{\rho}_{\leq}(\mathbb{X},\mathbb{Y}^{2})\end{subarray}} \int_{X^{\otimes 2}}|d_{Y^{1}}(\mathcal{T}_{\gamma^{1}}(x),\mathcal{T}_{\gamma ^{1}}(x^{\prime})-d_{Y^{2}}(\mathcal{T}_{\gamma^{2}}(x),\mathcal{T}_{\gamma^{2 }}(x^{\prime}))|d\mu^{\otimes 2}.$ (97) $$

Similar to theorem 3.2, we have:

###### Proposition H.1 .

Choose $\gamma^{*}\in\Gamma_{\leq}^{\rho,*}(\mathbb{X},\mathbb{Y}),\gamma^{1}\in\Gamma
_{\leq}^{\rho,*}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}\in\Gamma_{\leq}^{\rho,*
}(\mathbb{X},\mathbb{Y}^{2})$, we have:

- (1)
linear MPGW embedding of $\mathbb{Y}^{1}$ can recover MPGW discrepancy between $\mathbb{X}$ and $\mathbb{Y}^{1}$, i.e.
$\|k_{\gamma^{*}}\|^{2}_{\mu^{\otimes 2}}=MPGW_{\eta}(x).$
In general, we have:
$LMPGW_{\eta}(\mathbb{X},\mathbb{Y};\gamma^{0},\gamma^{*}):=MPGW_{\eta}(\mathbb
{X},\mathbb{Y}),\forall\gamma^{0}\in\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{
X}).$
- (2)
If Monge mapping assumption hold for $\gamma^{1},\gamma^{2}$, then (96),(95) coincide.
- (3)
$\hat{\gamma}^{*}=(\mathrm{id}\times\mathcal{T}_{\gamma^{*}})_{\#}\mu$ is optimal for $MPGW_{\eta}(\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{*}})=GW(\mathbb{X},
\widetilde{\mathbb{Y}}_{\gamma^{*}})$.
- (4)
When $\lambda$ is sufficiently large, we have:
$\displaystyle LMPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})$
$\displaystyle=LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})-\lambda
(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2\eta^{2}).$
$\displaystyle aLMPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})$
$\displaystyle=aLPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})-
\lambda(|\nu^{1}|^{2}+|\nu^{2}|^{2}-2\eta^{2}).$
- (5)
If $|\mu|=|\nu^{1}|=|\nu^{2}|=\eta=1$, $LMPGW_{\eta},LGW$ coincide and $aLMPGW_{\eta},aLGW$ coincide.

###### Proof.

- (1)
If Monge mapping assumption holds for $\gamma^{*}$, i.e. $\gamma^{*}=(\mathrm{id}\times T)_{\#}\mu$, we have:
$\displaystyle MPGW_{\eta}(\mathbb{X},\mathbb{Y})$
$\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(y,y{{}^
{\prime}})|^{2}d(\gamma^{*})^{\otimes 2}$
$\displaystyle=\|k_{\gamma^{*}}\|^{2}_{\mu^{\otimes 2}}.$
Without Monge mapping assumption, pick $\gamma^{0}\in\Gamma^{\eta,*}_{\leq}(\mathbb{X},\mathbb{X})$, since $|\gamma^{0}|=\eta=|\mu|$, we have
$\gamma^{0}\in\Gamma(\mu,\mu)$. Thus
$\int_{(X\times X)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{X}(x^{0},x^{0}{{}^{
\prime}})|^{2}d((\gamma^{0})^{2})^{\otimes 2}=MPGW_{\eta}(\mathbb{X},\mathbb{X
})=0=GW(\mathbb{X},\mathbb{X}).$
Therefore $\gamma^{0}\in\Gamma^{*}(\mathbb{X},\mathbb{X})$.
Pick $\gamma\in\Gamma^{\eta}_{\leq}(\gamma^{0},\gamma^{*})=\Gamma(\gamma^{0},\gamma^
{*})$, by (39), we have
$\displaystyle\int_{(X\times X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(
y,y{{}^{\prime}})|^{2}d\gamma^{\otimes 2}$
$\displaystyle=\int_{(X\times Y)^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y}(y,y{{}^
{\prime}})|^{2}d(\gamma^{*})^{\otimes 2}$
$\displaystyle=MPGW_{\eta}(\mathbb{X},\mathbb{Y}^{1};\mathbb{X},\gamma^{0},
\gamma^{*})$
It holds for all $\gamma\in\Gamma^{\eta}_{\leq}(\gamma^{0},\gamma^{*})$, thus
$LMPGW_{\eta}(\mathbb{X},\mathbb{Y};\mathbb{X},\gamma^{0},\gamma^{*})=MPGW_{
\eta}(\mathbb{X},\mathbb{Y}^{*}).$
- (2)
Under Monge mapping assumption, we have $\gamma^{1}=(\text{id}\times T^{1})_{\#}\mu^{\prime},\gamma^{2}=(\text{id}
\times T^{2})_{\#}\mu^{\prime\prime}$ for some mappings $T^{1},T^{2}$, where $\mu^{\prime},\mu^{\prime\prime}\leq\mu$.
Since $|\mu^{\prime}|=|\mu^{\prime\prime}|=\eta=|\mu|$, then we have $\mu^{\prime\prime}=\mu^{\prime}=\mu$.
Thus,
$\displaystyle\Gamma_{\leq}(\gamma^{1},\gamma^{2};\mu)$
$\displaystyle=\{(\text{id}\times T^{1}\times T^{2})_{\#}\mu^{\prime},\mu^{
\prime}\leq\mu,|\mu^{\prime}|=\eta\}$
$\displaystyle=\{(\text{id}\times T^{1}\times T^{2})_{\#}\mu\}$
and we have (96),(95) coincide.
- (3)
Since $\eta=|\mu|$, we have $|\widetilde{\nu}_{\gamma^{1}}|=|\gamma^{*}|=\eta=|\mu|$, thus
$\Gamma_{\leq}^{\eta}(\mu,\widetilde{\nu}_{\gamma^{1}})=\Gamma(\mu,\widetilde{
\nu}_{\gamma^{1}}).$
Thus, $MPGW_{\eta}(\mathbb{X},\widetilde{\mathbb{Y}}_{\gamma^{*}})=GW(\mathbb{X},
\widetilde{\mathbb{Y}}_{\gamma^{*}})$.
Since $\gamma^{*}$ is optimal in $MPGW_{\eta}(\mathbb{X},\mathbb{Y})=GW(\mathbb{X},\mathbb{Y})$,
from Proposition 2.1, we have $\widetilde{\gamma}_{\gamma^{1}}$ is optimal for $GW(\mathbb{X},\mathbb{Y}_{\gamma^{1}})=MPGW_{\eta}(\mathbb{X},\widetilde{
\mathbb{Y}}_{\gamma^{1}})$ and we complete the proof.
- (4)
Since $X,Y^{1},Y^{2}$ are compact, by Lemma E.2 in [] when $\lambda$ is sufficiently large, for each $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}
\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{2})$, we have $|\gamma^{1}|=|\gamma^{2}|=\eta=|\mu|$.
By Proposition M.1. [], we have $\gamma^{1},\gamma^{2}$ are optimal for $MPGW_{\eta}(\mathbb{X},\mathbb{Y}^{1}),MPGW_{\eta}(\mathbb{X},\mathbb{Y}^{2})$.
That is
$\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y}^{1})\subset\Gamma_{\leq}^{\eta
,*}(\mathbb{X},\mathbb{Y}^{1}),\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y}
^{2})\subset\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{Y}^{2}).$
For the other direction, pick $\gamma^{1}\in\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{Y}^{1})$, $\gamma^{\prime}\in\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y}^{1})$. Thus $|\gamma^{\prime}|=\eta$, and
we have
$\displaystyle C(\gamma^{1};\mathbb{X},\mathbb{Y}^{1},\lambda)$
$\displaystyle=\int_{(X\times Y^{1})^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y^{1}}
(y^{1},y^{1}{{}^{\prime}})|^{2}d(\gamma^{1})^{\otimes 2}+\gamma(|\mu|^{2}+|\nu
^{1}|^{2}-2\eta^{2})$
$\displaystyle\leq\int_{(X\times Y^{1})^{\otimes 2}}|g_{X}(x,x^{\prime})-g_{Y^{
1}}(y^{1},y^{1}{{}^{\prime}})|^{2}d(\gamma^{\prime})^{\otimes 2}+\gamma(|\mu|^
{2}+|\nu^{1}|^{2}-2\eta^{2})$
$\displaystyle=C(\gamma^{\prime};\mathbb{X},\mathbb{Y}^{1},\lambda)$
$\displaystyle=PGW_{\lambda}(\mathbb{X},\mathbb{Y}^{1})$
Thus, $\gamma^{1}\in\Gamma^{*}_{\leq,\lambda}(\mathbb{X},\mathbb{Y}^{1})$.
Therefore,
$\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y}^{1})=\Gamma_{\leq}^{\eta,*}(
\mathbb{X},\mathbb{Y}^{1}),\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y}^{2}
)=\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{Y}^{2}).$
Pick $\gamma^{1}\in\Gamma_{\leq,\lambda}^{*}(\mathbb{X},\mathbb{Y}^{1})=\Gamma_{\leq
}^{\eta,*}(\mathbb{X},\mathbb{Y}^{1}),\gamma^{2}\in\Gamma_{\leq,\lambda}^{*}(
\mathbb{X},\mathbb{Y}^{2})=\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{Y}^{2})$, we have
$\displaystyle MLPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1}
,\gamma^{2})=LPGW_{\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X},\gamma^{1
},\gamma^{2})-\lambda(|\nu^{1}|+|\nu^{2}|-2\eta^{2})$
Take the infimum over all $\gamma^{1},\gamma^{2}$, we obtain
$\displaystyle MLPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})=LPGW_{
\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})-\lambda(|\nu^{1}|^{2}+|\nu^
{2}|^{2}-2\eta^{2})$
And similarly, we have
$\displaystyle aMLPGW_{\eta}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})=aLPGW_{
\lambda}(\mathbb{Y}^{1},\mathbb{Y}^{2};\mathbb{X})-\lambda(|\nu^{1}|^{2}+|\nu^
{2}|^{2}-2\eta^{2})$
(98)
- (5)
In this case, we have $\Gamma_{\leq}^{\eta}(\mu,\nu^{1})=\Gamma(\mu,\nu^{1}),\Gamma_{\leq}^{\eta}(\mu
,\nu^{2}=\Gamma(\mu,\nu^{2})$.
Thus
$\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{Y}^{1})=\Gamma^{*}(\mathbb{X},
\mathbb{Y}^{1}),\Gamma_{\leq}^{\eta,*}(\mathbb{X},\mathbb{Y}^{2})=\Gamma^{*}(
\mathbb{X},\mathbb{Y}^{2}).$
Thus $LMPGW,LGW$ coincide, $aLMPGW,aLGW$ coincide.

∎

Figure: (a) Shapes in ellipse dataset.
Refer to caption: extracted/5973430/images/ellipse/ellipse_data.png

###### Proposition H.1 .

###### Proof.

## Appendix I Details of Elliptical Disks Experiment

In this section, we present the details of the elliptical disks experiment.

##### Dataset and numerical setting details.

The dataset we used is the [ellipse dataset](https://github.com/Gorgotha/LGW) given by [], which consists of 100 distinct ellipses. Each ellipse is represented as an $n\times 2$ matrix, where $n$ ranges from 90 to 600. For reference shapes, we selected 9 different 2D shapes, including disks, squares, triangles, and others. See Figure 4 for a visualization of the dataset and the reference spaces. In this experiment, each shape is modeled with an empirical measure $\sum_{i=1}^{n}\frac{1}{n}\delta_{x_{i}}$.

**Table 4: In the first column, the values $0.05,0.08,0.1,0.5$, represent the selected $\lambda$ values. For each $\lambda$, 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.**
|  |  | PGW | $\mathbb{S}_{1}$ | $\mathbb{S}_{2}$ | $\mathbb{S}_{3}$ | $\mathbb{S}_{4}$ | $\mathbb{S}_{5}$ | $\mathbb{S}_{6}$ | $\mathbb{S}_{7}$ | $\mathbb{S}_{8}$ | $\mathbb{S}_{9}$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\lambda$ |  |  |  |  |  |  |  |  |  |  |  |
| points |  | 441 | 676 | 625 | 52 | 289 | 545 | 882 | 882 | 317 |  |
| $0.05$ | time (mins) | 45.34 | 0.86 | 3.8 | 3.08 | 0.66 | 0.63 | 1.43 | 1.89 | 2.1 | 0.69 |
| MRE | — | 0.1982 | 0.1263 | 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 |  |
| $0.08$ | time (mins) | 43.86 | 1.02 | 3.33 | 3.55 | 0.34 | 0.99 | 1.25 | 1.29 | 1.55 | 1.22 |
| MRE | — | 0.1941 | 0.1264 | 0.1431 | 0.2542 | 0.0705 | 0.0444 | 0.0205 | 0.0198 | 0.0245 |  |
| PCC | — | 0.5781 | 0.5738 | 0.5881 | 0.8581 | 0.8741 | 0.993 | 0.9952 | 0.9954 | 0.9949 |  |
| $0.1$ | time (mins) | 46.97 | 0.76 | 3.78 | 3.13 | 0.08 | 0.62 | 1.56 | 1.91 | 1.98 | 0.71 |
| MRE | — | 0.1941 | 0.1264 | 0.1431 | 0.2542 | 0.0538 | 0.0444 | 0.0205 | 0.0198 | 0.0245 |  |
| PCC | — | 0.5781 | 0.5738 | 0.5881 | 0.8581 | 0.9871 | 0.993 | 0.9952 | 0.9954 | 0.9949 |  |
| $0.5$ | time (mins) | 44.77 | 0.74 | 3.68 | 3.02 | 0.08 | 0.61 | 1.51 | 1.89 | 1.98 | 0.69 |
| MRE | — | 0.1932 | 0.1262 | 0.1428 | 0.2542 | 0.0538 | 0.0443 | 0.0205 | 0.0198 | 0.0246 |  |
| PCC | — | 0.5779 | 0.5737 | 0.5879 | 0.8583 | 0.9871 | 0.993 | 0.9952 | 0.9953 | 0.9949 |  |

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 $\binom{N}{2}$ computations. Furthermore, we observe that for some reference spaces (e.g. $\mathbb{S}_{5}$, $\mathbb{S}_{7}$, $\mathbb{S}_{9}$), the MRE is relatively lower. Moreover, for most reference spaces, including $\mathbb{S}_{7}$, $\mathbb{S}_{8}$, and $\mathbb{S}_{9}$, LPGW admits a PCC greater than 0.85. Finally, when $\lambda$ is larger, the PCC tends to be higher and the MRE is lower across all reference spaces, as discussed further in the next section. These results highlight the importance of the choice of reference space, as is commonly the case for linear OT-based methods.

Relative error analysis.
Given $\nu^{1},\nu^{2},\ldots,\nu^{K}$ and reference measure $\mu$, the relative error is defined as:

$$ $\displaystyle\text{MRE}=\frac{1}{\binom{K}{2}}\sum_{i\neq j}\frac{|PGW(\nu^{i} ,\nu^{j})-LPGW(\nu^{i},\nu^{j};\mu)|}{PGW(\nu^{i},\nu^{j})}.$ (99) $$

###### Remark I.1 .

For numerical stability, when $\lambda$ is small (i.e., $\lambda=0.05,0.08$), we remove the PGW/LPGW distance whenever $PGW\leq 1\cdot 10^{-10}$ since $1\cdot 10^{-10}$ is the tolerance in the PGW algorithm. In this case, $PGW\approx 1\cdot 10^{-10}$ and $LPGW\approx 1\cdot 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, we use the barycentric projected measure $\hat{\nu}^{i}$ to approximate $\nu^{i}$ for each $i$. These two measures can be distinct, especially when the optimal transportation plan is not generated by the Monge mapping.
- •
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 minimizer instead of a global one. Therefore, the computed PGW transportation plan might not be optimal.
- •
In practice, we approximate the original LPGW distance (15) (or (10)) using the approximation formulation (20). This introduces a gap between the real LPGW distance and the approximation.

It 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 linear OT-based methods [, , , ]. The third issue stems from the non-convexity of GW/PGW, affecting both LGW and LPGW similarly. The final error is specific to LPGW due to the approximation formulation used.

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. [, ]), as these methods do not require mass normalization. With high probability, this will result in a Monge mapping, reducing the second error. Additionally, to minimize the last error, as stated in Theorem 3.2, using a higher $\lambda$ leads to lower error, and when $\lambda$ is sufficiently large, this error becomes zero.

###### Remark I.1 .

##### MDS visualization and analysis.

We visualize the multi-dimensional scaling (MDS) embeddings for both PGW and LPGW with respect to each reference space in Figure 5. We observe that when $\lambda$ is large (i.e. $\lambda=0.1,0.5$), LPGW with reference space $\mathbb{S}_{5},\mathbb{S}_{6},\mathbb{S}_{7},\mathbb{S}_{8},\mathbb{S}_{9}$ admit similar patterns. When $\lambda=0.05$ or $\lambda=0.08$, we observe $LPGW$ with reference $\mathbb{S}_{7},\mathbb{S}_{8},\mathbb{S}_{9}$ and PGW admit similar patterns. From this figure, we observe that $\mathbb{S}_{7},\mathbb{S}_{8},\mathbb{S}_{9}$ admit better performance than other reference spaces.

##### Summary.

Although LPGW methods are subject to potential errors, the high PCC observed between LPGW and PGW (when, e.g., the reference space is $\mathbb{S}_{7},\mathbb{S}_{8},\mathbb{S}_{9}$), suggests that LPGW can serve as a good proxy for PGW, rather than simply as an approximation.

Figure: (a) $\lambda=0.05$
Refer to caption: extracted/5973430/images/ellipse/lpgw_mds_0.050.png

## Appendix J Details of Shape Retrieval Experiment

Figure: (a) 2D Dataset
Refer to caption: extracted/5973430/images/bone_star/bone_star_data.png

Dataset details.
We test two datasets in this experiment, a 2D dataset and a 3D dataset. The visualization of the two datasets is presented in Figure
6.

In addition, for each shape $X=\{x_{1},\ldots x_{n}\}$, we normalize the scaling such that $\max_{i\neq j}\|x_{i}-x_{j}\|=1$. For the 3D dataset, we apply the $k$-means clustering to reduce the size of each shape to $500$, from its original size $2048$.

##### Numerical details.

We represent the shapes in each dataset as mm-spaces $\mathbb{X}^{i}=\left(\mathbb{R}^{d},\|\cdot\|_{2},\mu^{i}=\sum_{k=1}^{n^{i}}
\alpha^{i}\delta_{x^{i}_{k}}\right)$. We use $\alpha^{i}=\frac{1}{n^{i}}$ to compute the GW/LGW distances for the balanced mass constraint setting.

For the PGW/LPGW distances, we set $\alpha=\frac{1}{N}$, where $N$ is the median number of points across all shapes in the dataset.

For the SVM experiments, we use $\exp(-\sigma D)$ as the kernel for the SVM model. Here, we normalize the matrix $D$ and choose the best $\sigma\in\{0.001,0.01,0.1,1,5,8,10,100\}$ for each method used in order to facilitate a fair comparison of the resulting performances. We note that the resulting kernel matrix is not necessarily positive semidefinite.

Figure: (a) 2D Dataset.
Refer to caption: x1.png

##### Parameter selection for PGW and LPGW.

The parameter $\lambda$ for PGW and LPGW is chosen as follows. For the 2D dataset, we set $\lambda$ such that $\lambda\leq\lambda_{max}=\frac{1}{2}\max_{i}{(|C^{i}|^{2})}=0.5$, since all shapes are normalized to a scale of 1. We perform a line search for $\lambda$ over the set $\{0.2,0.3,0.5\}$ and select $\lambda=0.2$ for both PGW and LPGW.

For the 3D dataset, we randomly select 2-3 shapes and compute the PGW distance between these shapes and the reference space. We find that $\lambda_{max}\approx 0.15$. Thus, we conduct a line search for $\lambda$ over the range $\{0.02,0.03,0.05,0.06,0.070.08,0.080.1,0.15\}$ and choose $\lambda=0.06$ for both PGW and LPGW.

##### Reference space setting for LGW and LPGW.

Similar to the classical OT method [], the ideal reference space should represent the “center” of the tested measures. In practice, we typically use the GW barycenter [] or the PGW barycenter [].

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 5 minutes. For fairness in comparison, we apply the same reference space for both the LGW and LPGW methods in all experiments.

##### Nearest neighbor classification.

Once the pairwise distance matrices have been computed between the shapes using each method, we use the computed distances for a nearest neighbor classification experiment. We choose a single representative at random from each class in the dataset 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.

Figure: Figure 8: We visualize the accuracy of LPGW for different $\lambda$. For each $\lambda$, we select the best $\sigma$ to compute the accuracy. We observe that, when $\lambda\geq 0.08$, LPGW, and LGW have same accuracy.
Refer to caption: extracted/5973430/images/mvp/lpgw_lgw.png

Performance analysis.
The pairwise distance matrices are visualized for each dataset in Figure 1, and the confusion matrices from the nearest neighbor classification experiment on each dataset are shown in Figure 7. Finally, the classification accuracy with the SVM experiments is reported in Table 2. The results indicate that the LPGW distance is able to consistently obtain high performance across both data sets.

From Figure 1, we observe that PGW and LPGW qualitatively admit a more reasonable similarity measure compared to the other considered methods. For example, on the 2D dataset, class “bone” and “rectangle” should have a relatively smaller distance than “bone” and “annulus”. Ideally, a reasonable distance should satisfy the following:
$0<d(\text{bone},\text{rectangle})<d(\text{bone},\text{anulus}).$
However, we do not observe this relation in GW or LGW.

In the 3D dataset, the main challenge is the presence of incomplete shapes, which represents only a part of the corresponding complete shape and can have a large dissimilarity to each other. In this experiment, we observe that PGW/LPGW admits slightly better performance. We suspect due the the unbalanced setting of these two methods, these two methods are more robust to the incomplete shape classification.

Note that in this dataset all shapes have the same size. Thus, when $\lambda$ is sufficiently large (i.e. $\lambda=0.5$), LPGW can recover the performance of LGW. We refer to Figure 8 for visualization.

## Appendix K Details of Learning with Transform-Based Embeddings Experiment

##### Reference space.

Similar to the shape retrieval experiment, for each class/digit, we select one shape from the training set and compute the GW barycenter based on the selected shapes. Note, in this step, the reference space we obtain is $(M_{0}\in\mathbb{R}^{n_{0}\times n_{0}},p^{0})$, where $n_{0}\in\mathbb{N}$ is size of the reference space, $M_{0}$ denotes the pairwise distance matrix, and $p^{0}$ is the PMF of the reference measure. Here, $n_{0},p^{0}$ are inputs to the GW barycenter algorithm, and in this experiment, we set $n_{0}$ to be the mean of the sizes of the selected shapes, and $p^{0}$ is set to be $p^{0}=\frac{1}{n_{0}}1_{n_{0}}$.

However, $M_{0}$ cannot be applied as reference space for the LOT method. Thus, we adapt the MDS method for $M_{0}$ and obtain the supported points $X^{0}=\{x^{0}_{1},\ldots x^{0}_{n_{0}}\}$ of the reference space, i.e.,

$$ $X=\arg\min_{X}\sum_{i=1}^{n}\|(M_{0})_{i,j}-\|x_{i}-x_{j}\|\|^{2},\text{where }x_{i}=X[i,:],\forall i.$ $$

We adapt $(M_{0},p^{0},\sum_{i=1}^{n}x_{i})$ as 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/flipping and noise, we 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”.

The classification model we selected is the logistic regression model as provided by the [scikit-learn package](https://scikit-learn.org/1.5/modules/generated/sklearn.linear_model.LogisticRegression.html). For the LOT and LGW methods, due to the balanced mass requirement, we normalize the PMF of all shapes in the testing dataset. For LPGW, this normalization is not applied.

##### Parameter setting for LPGW.

Note, in this case, the training data is not corrupted. Thus, we can set $\lambda=\lambda_{max}=\frac{1}{2}\max_{i}C_{i}^{2}$ where $C_{i}$ is the cost matrix for shape $i$. In this experiment, we set $\lambda=40$. In addition, to improve the computational speed of LGW/LPGW, 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.

##### Performance analysis.

The LOT method achieves 51.3% accuracy when $\eta=0$. This indicates that even with the addition of rotated/flipped data to 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 rotation/flipping.

When $\eta\geq 0.1$, the accuracy of both LOT and LGW drops to 10-20%. However, we observe that the LPGW embedding maintains a strong accuracy between 70% and 85%. This demonstrates that the LPGW embedding is more robust to corrupted test data.

### K.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 interpolation between these two shapes using the GW barycenter [], PGW barycenter [], LGW geodesic [], and our LPGW interpolation. The goal is to intuitively visualize the LGW/LPGW embeddings for the reader’s understanding.

Figure: Figure 9: We visualize the interpolation between two digit shapes using GW, PGW, LGW, and LPGW. In the first column, the three shapes shown are the source shape, target shape, and the reference space used in LGW and LPGW. The target shape, digit “4”, is corrupted by the addition of noise points, with a total mass of $\eta=0.3$.
Refer to caption: extracted/5973430/images/mnist/interporlation.png

##### Our method and baseline methods.

Let $\mathbb{X}$ be the reference mm-space applied in the classification experiment. Note, numerically, it can be described by $(C^{0},X^{0},p^{0})$, where $p^{0}\in\mathbb{R}_{+}^{n_{0}}$ is the PMF; $n_{0}$ is the size of $p^{0}$; $X^{0}\in\mathbb{R}^{n_{0}\times 2}$ is the set of 2D supported points; and $C^{0}=[\|X^{0}_{i}-X^{0}_{j}\|^{2}_{i,j\in[1:n_{0}]}]$ is the corresponding cost matrix.

That is, we can use $(C^{0},p^{0})$ to represent $\mathbb{X}$(^*^**$X^{0}$ is not required as $C^{0}$ contains all the information of $X^{0}$ in the GW/PGW problem.). Similarly, we use $(C^{1},p^{1})$ and $(C^{2},p^{2})$ to represent the source and target mm-spaces (shapes).

Now we introduce the GW barycenter method. For each time $t\in\{0,1/6,\ldots,6/6=1\}$, we solve the barycenter problem

$$ $\displaystyle C^{*}=\arg\min_{C\in\mathbb{R}^{n_{0}\times n_{0}}}$ (100) $$

When $t=0$, $(C^{*},p^{0})$ and $(C^{1},p^{1})$ represent similar shapes.
In fact, if $p^{0}=p^{1}$, the two shapes are identical. Similarly, if $t=1$, $(C^{*},p^{1})$ is similar to the target $(C^{2},p^{2})$. For $t\in(0,1)$, $(C^{*},p^{0})$ represents an interpolation shape between the source shape $(C^{1},p^{1})$ and the target shape $(C^{2},p^{2})$.

The PGW barycenter method is defined similarly.

In the LGW geodesic method, let $\sum_{i=1}^{n}\delta_{\hat{y}^{1}_{i}}p^{0}_{i}$ denote the barycentric projection obtained by $\gamma$, where $\gamma$ is the optimal transportation plan for the GW problem between $(C^{0},p^{0})$ and $(C^{1},p^{1})$. The numerical implementation of the LGW embedding is given by

$$ $E^{1}=C^{0}-[\|\hat{y}^{1}_{i}-\hat{y}^{1}_{j}\|^{2}]_{i,j\in[1:n_{0}]}\in \mathbb{R}^{n_{0}\times n_{0}}$ $$

(we refer to (5) for the original formulation).
Similarly, we can define the LGW embedding for the target shape $(C^{2},p^{2})$, denoted as $E_{2}\in\mathbb{R}^{n_{0}\times n_{0}}$.

Then for each $t$, the interpolation/geodesic of LGW is defined by

$$ $\displaystyle C^{0}+(1-t)E_{1}+tE_{2}.$ (101) $$

For the LPGW interpolation method, the numerical LPGW embeddings $E_{1},E_{2}\in\mathbb{R}^{n_{0}\times n_{0}}$ are defined similarly, and we refer to (22) for details. We use (101) for the interpolation.

To visualize these interpolations, for each $C_{t}$, we adapt the MDS method, and the solution $X_{t}\in\mathbb{R}^{n_{0}\times 2}$ is a point cloud. We visualize these point clouds in Figure 9.

##### Performance comparison.

In this experiment, the size of these shapes is in the range of 200–250. GW/PGW requires 230–270 seconds, while LGW/LPGW requires 1–2 seconds. In Figure 9, we observe that the shapes generated by GW/LGW contain more noise points. Additionally, at times such as $t=3/6$ and $t=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 $t=0$ and $t=1$, the shapes generated by the LGW/LPGW methods can be treated as visualizations of the corresponding embeddings for the source shape $(C^{1},p^{1})$ and target shape $(C^{2},p^{2})$, respectively.

## Appendix L Compute Resources

All experiments presented in this paper are conducted on a computational machine with an AMD EPYC 7713 64-Core Processor, 8 $\times$ 32GB DIMM DDR4, 3200 MHz, and a NVIDIA RTX A6000 GPU.

## Peer Reviews

confidence: 1
contribution: 3
initial_rating: 8
presentation: 4
questions: I am not an expert in this area.
soundness: 4
strengths: 1. The paper is well organized and easy to follow.
2. The paper contains many details, which is very helpful for understanding.
3. The experiment is promising, justifying theoretic part.
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.
weaknesses: I am not an expert in this area, I don't find weaknesses from my perspective.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 2
questions: See above.
soundness: 3
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.
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.
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]? 


2. 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].


3. Minor comment: 
If the barycentric LGW is the version to use as in the second equality of (10), then this should be stated in the paper.
Notation $\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)$.

[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.

[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.

[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.

[4] Zhang, Zhengxin, et al. "Cycle consistent probability divergences across different spaces." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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?

2. 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. 

3. 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?

4. 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.
soundness: 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.
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.
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. 

Furthermore, 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.    

The 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. 

Finally, 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. Could the authors extend the approximation results for LGW and LPGW to scenarios where the Monge mapping may not exist?
  
2. 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))?
  
3. 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.
  
4. 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?
soundness: 3
strengths: 1. The paper is well-written and easy to follow.
  
2. 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.
  
3. 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.
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.
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 
    - providing theoretical bounds on the approximation error when a Monge mapping does not exist;
    - including empirical experiments comparing performance on datasets known to violate Monge mapping conditions;
    - discussing potential modifications to make the method more robust when Monge mappings do not exist.
  
2. 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
    - provide theoretical error bounds for each approximation step;
    - include ablation studies quantifying the empirical error introduced at each approximation stage;
    - discuss the tradeoffs between computational efficiency and approximation accuracy.
  
3. 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.
  

[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.

[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.

[C] Titouan, Vayer, et al. "Sliced gromov-wasserstein." *Advances in Neural Information Processing Systems* 32 (2019).

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: Can you provide a time-complexity analysis to support your claim on a linear computation of the distances between K metric measure spaces?
soundness: 3
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.
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.
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).

Meta-review: The paper proposes the Linear Partial Gromov-Wasserstein embedding, which significantly improves the computational efficiency of Partial Gromov-Wasserstein distance while preserving its partial matching properties. Reviewers initially raised concerns regarding the novelty of the work, questioning whether the combination of linearization and partial GW techniques constituted a significant advancement. Additionally, the reviewer noted the reliance on strong assumptions, such as the existence of Monge maps, and the coarse nature of the approximations. However, the authors clarified that their primary contribution lies in the embedding formulation, distinct from PGW distance, and provided empirical results to validate its robustness and practical utility, even in scenarios where Monge mappings do not exist.

Decision: Accept (Poster)