Partial Gromov-Wasserstein Metric

## Abstract

Abstract The Gromov-Wasserstein (GW) distance has gained increasing interest in the machine learning community in recent years, as it allows for the comparison of measures in different metric spaces. To overcome the limitations imposed by the equal mass requirements of the classical GW problem, researchers have begun exploring its application in unbalanced settings. However, Unbalanced GW (UGW) can only be regarded as a discrepancy rather than a rigorous metric/distance between two metric measure spaces (mm-spaces). In this paper, we propose a particular case of the UGW problem, termed Partial Gromov-Wasserstein (PGW). We establish that PGW is a well-defined metric between mm-spaces and discuss its theoretical properties, including the existence of a minimizer for the PGW problem and the relationship between PGW and GW, among others. We then propose two variants of the Frank-Wolfe algorithm for solving the PGW problem and show that they are mathematically and computationally equivalent. Moreover, based on our PGW metric, we introduce the analogous concept of barycenters for mm-spaces. Finally, we validate the effectiveness of our PGW metric and related solvers * * * Rigorously speaking, due to the non-convexity of the GW problem and its variants, current methods achieve only local minima rather than global minima. We use the term “solver” following the convention of previous related works [ 1 , 2 ] , but it should be emphasized that the proposed methods aim to find local minima rather than global minima, similar to related and classical computational GW works. in applications such as shape matching, shape retrieval, and shape interpolation, comparing them against existing baselines.

## 1 Introduction

The classical optimal transport (OT) problem [] seeks to match two probability measures while minimizing the expected transportation cost. At the heart of classical OT theory lies the principle of mass conservation, which aims to optimize the transfer between two probability measures, assuming they have the same total mass and strictly preserving it. Statistical distances that arise from OT, such as Wasserstein distances, have been widely applied across various machine learning domains, ranging from generative modeling [, ] to domain adaptation [] and representation learning []. Recent advancements have extended the OT problem to address certain limitations within machine learning applications. These advancements include: 1) facilitating the comparison of non-negative measures that possess different total masses via unbalanced [] and partial OT [], and 2) enabling the comparison of probability measures across distinct metric spaces through Gromov-Wasserstein distances [], with applications spanning from quantum chemistry [] to natural language processing [].

Regarding the first aspect, many applications in machine learning involve comparing non-negative measures (often empirical measures) with varying total amounts of mass, e.g., domain adaptation []. Moreover, OT distances (or dissimilarity measures) are often not robust against outliers and noise, resulting in potentially high transportation costs for outliers. Many recent publications have focused on variants of the OT problem that allow for comparing non-negative measures with unequal mass. For instance, the optimal partial transport problem [, , , , , ], Kantorovich–Rubinstein norm [, , ], and the Hellinger–Kantorovich distance [, ]. Recent works formulating the metric properties of a Partial OT with Total Variation constraints include [, ].
These methods fall under the broad category of “unbalanced optimal transport”. In this regard, we also highlight [, , ], which enhance OT’s robustness in the presence of outliers.

Regarding the second aspect, comparing probability measures across different metric spaces is essential in many machine learning applications, ranging from computer graphics, where shapes and surfaces are compared
[, ], to graph partitioning and matching problems []. Source and target distributions often arise from varied conditions, such as different times, contexts, or measurement techniques, creating substantial differences in intrinsic distances among data points. The conventional OT framework necessitates a meaningful distance across diverse domains, a requirement that is not always achievable. To circumvent this issue, the Gromov-Wasserstein (GW) distances were proposed in [, ] as an adaptation of the Gromov-Hausdorff distance, which measures the discrepancy between two metric spaces [, , , ]. The GW distance [, ] extends OT-based distances to metric measure spaces (mm-spaces) up to isometries. Its invariance across isomorphic mm-spaces makes the GW distance particularly valuable for applications like shape comparison and matching, where invariance to rigid motion transformations is crucial.

The main computational challenge of the GW metric is the non-convexity of its formulation []. The conventional computational approach relies on the Frank-Wolfe (FW) algorithm [, ]. Optimal transport (OT) computational methods [, , , , , , , , ], such as the Sinkhorn algorithm, can be incorporated into FW iterations, which yields the classical GW solvers [, , ].

Given that the GW distance is limited to the comparison of probability mm-spaces, recent works have introduced unbalanced and partial variations [, , ]. These variations have been applied in diverse contexts, including partial graph matching for social network analysis [] and the alignment of brain images []. Although solving these unbalanced variants of the GW problem yields notions of discrepancies between mm-spaces, their metric properties remain unclear in the literature.

Motivated by the emerging applications of the GW problem in unbalanced settings, this paper focuses on developing a metric between general (not necessarily probability) mm-spaces and providing efficient solvers for its computation. Our proposed metric arises from formulating a variant of the GW problem for unbalanced contexts, rooted in the framework provided by [], which we named the Partial Gromov-Wasserstein (PGW) problem. In contrast to [], which introduces a KL-divergence penalty and a Sinkhorn solver, we employ a total variation penalty, demonstrate the resulting metric properties, and provide novel, efficient solvers for this problem.
To the best of our knowledge, this paper presents the first metric for non-probability mm-spaces based on the GW distance.

Contributions. Our specific contributions in this paper are:

- •
GW metric in unbalanced settings. We propose the Partial Gromov-Wasserstein (PGW) problem and prove that it gives rise to a metric between arbitrary mm-spaces.
- •
PGW solver.Analogous to the technique presented in [], we show that the PGW problem can be turned into a variant of the GW problem. Based on this relation, we propose two mathematically equivalent, but distinct in numerical implementation, Frank-Wolfe solvers for the discrete PGW problem. Inspired by the results of [], we prove that similar to the Frank-Wolfe solver presented in [], our proposed solvers for the PGW problem converge linearly to a stationary point.
- •
Numerical experiments. We demonstrate the performance of our proposed algorithms in terms of computation time and efficacy on a series of tasks: shape-matching with outliers between 2D and 3D objects, shape retrieval between 2D shapes, and shape interpolation using the concept of PGW barycenters. We compare the performance of our proposed algorithms against existing baselines for each task.

## 2 Background

In this section, we review the basics of OT theory, one of its variants in unbalanced contexts called Partial OT (POT), and their connection as established in []. We then introduce the GW distance.

### 2.1 Optimal Transport and Partial Optimal Transport

Let $\Omega\subseteq\mathbb{R}^{d}$ be, for simplicity, a compact subset of $\mathbb{R}^{d}$, and $\mathcal{P}(\Omega)$ be the space of probability measures defined on the Borel $\sigma$-algebra of $\Omega$.

The Optimal Transport (OT) problem for $\mu,\nu\in\mathcal{P}(\Omega)$, with transportation cost $c(x,y):\Omega\times\Omega\to\mathbb{R}_{+}$ being a
lower-semi continuous function, is defined as:

$$ $OT(\mu,\nu):=\min_{\gamma\in\Gamma(\mu,\nu)}\gamma(c),\qquad\text{ where } \quad\gamma(c):=\int_{\Omega^{2}}c(x,y)\,d\gamma(x,y)$ (1) $$

and where $\Gamma(\mu,\nu)$ denotes the set of all joint probability measures on $\Omega^{2}:=\Omega\times\Omega$ with marginals $\mu,\nu$, i.e., $\gamma_{1}:=\pi_{1\#}\gamma=\mu,\gamma_{2}:=\pi_{2\#}\gamma=\nu$,
where $\pi_{1},\pi_{2}:\Omega^{2}\to\Omega$ are the canonical projections $\pi_{1}(x,y):=x,\pi_{2}(x,y):=y$. A minimizer for (1) always exists [, ] and when $c(x,y)=\|x-y\|^{p}$, for $p\geq 1$, it defines a metric on $\mathcal{P}(\Omega)$, which is referred to as the “$p$-Wasserstein distance”:

$$ $\displaystyle W_{p}^{p}(\mu,\nu):=\min_{\gamma\in\Gamma(\mu,\nu)}\int_{\Omega^ {2}}\|x-y\|^{p}d\gamma(x,y).$ (2) $$

The Partial Optimal Transport (POT) problem [, , ] extends the OT problem to the set of Radon measures $\mathcal{M}_{+}(\Omega)$, i.e., non-negative and finite measures. For $\lambda>0$ and $\mu,\nu\in\mathcal{M}_{+}(\Omega)$, the POT problem is defined as:

$$ $POT(\mu,\nu;\lambda):=\inf_{\gamma\in\mathcal{M}_{+}(\Omega^{2})}\gamma(c)+ \lambda(|\mu-\gamma_{1}|+|\nu-\gamma_{2}|),$ (3) $$

where, in general, $|\sigma|$ denotes the total variation norm of a measure $\sigma$, i.e., $|\sigma|:=\sigma(\Omega)$.
The constraint $\gamma\in\mathcal{M}_{+}(\Omega^{2})$ in (3) can be further restricted to $\gamma\in\Gamma_{\leq}(\mu,\nu)$:

$$ $\Gamma_{\leq}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(\Omega^{2}):\,\gamma_{1} \leq\mu,\gamma_{2}\leq\nu\},$ $$

denoting $\gamma_{1}\leq\mu$ if for any Borel set $B\subseteq\Omega$, $\gamma_{1}(B)\leq\mu(B)$ (respectively, for $\gamma_{2}\leq\nu$) []. Roughly speaking, the linear penalization indicates that if the classical transportation cost exceeds
$2\lambda$, it is better to create/destroy’ mass (see [] for further details).

The relationship between POT and OT.
By using the techniques in [], the POT problem can be transferred into an OT problem, and thus, OT solvers (e.g., network simplex) can be employed to solve the POT problem.

###### Proposition 2.1 .

[, ] Given $\mu,\nu\in\mathcal{M}_{+}(\Omega)$, construct the following measures on $\hat{\Omega}:=\Omega\cup\{\hat{\infty}\}$, for an auxiliary point $\hat{\infty}$:

$$ $\hat{\mu}=\mu+|\nu|\delta_{\hat{\infty}}\quad\text{ and }\quad\hat{\nu}=\nu+| \mu|\delta_{\hat{\infty}}.$ (4) $$

Consider the following OT problem

$$ $\text{OT}(\hat{\mu},\hat{\nu})=\min_{\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu} )}\hat{\gamma}(\hat{c}),\qquad\text{where}\quad\hat{c}(x,y):=\begin{cases}c(x, y)-2\lambda&\text{ if }x,y\in\Omega,\\ 0&\text{ elsewhere}.\end{cases}$ (5) $$

Then, there exists a bijection $F:\Gamma_{\leq}(\mu,\nu)\to\Gamma(\hat{\mu},\hat{\nu})$
given by

$$ $F(\gamma):=\gamma+(\mu-\gamma_{1})\otimes\delta_{\hat{\infty}}+\delta_{\hat{ \infty}}\otimes(\nu-\gamma_{2})+|\gamma|\delta_{\hat{\infty},\hat{\infty}}.$ (6) $$

such that $\gamma$ is optimal for the POT problem (3) if and only if $F(\gamma)$ is optimal for the OT problem (5).

It is worth noting that instead of considering the same underlying space $\Omega$ for both measures $\mu$ and $\nu$, the OT and POT problems can be formulated in the scenario where $\mu$ and $\nu$ are defined on different metric spaces
$X$ and $Y$, respectively. In this setting, one needs a cost function $c:X\times Y\to\mathbb{R}_{+}$ to formulate the OT and POT problems. However, in practice it is usually difficult to define reasonable ‘distance’ or ground cost $c(\cdot,\cdot)$ between the two spaces $X$ and $Y$. In particular, the $p$-Wasserstein distance cannot be adopted if $\mu,\nu$ are defined on different spaces.
To relax this requirement, in the next section, we will review the fundamentals of the Gromov-Wasserstein problem [].

###### Proposition 2.1 .

### 2.2 The Gromov-Wasserstein (GW) Problem

A metric measure space (mm-space) consists of a set $X$ endowed with a metric structure, that is, a notion of distance $d_{X}$ between its elements, and equipped with a Borel measure $\mu$.
As in [, Ch. 5], we will assume that $X$ is compact and that $\operatorname{supp}(\mu)=X$.
Given two probability mm-spaces $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$, with $\mu\in\mathcal{P}(X)$ and $\nu\in\mathcal{P}(Y)$, and a non-negative lower semi-continuous cost function $L:\mathbb{R}^{2}\to\mathbb{R}_{+}$ (e.g., the Euclidean distance or the KL-loss), the Gromov-Wasserstein (GW) matching problem is defined as:

$$ $GW^{L}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\gamma^{\otimes 2 }(L(d_{X}(\cdot,\cdot),d_{Y}(\cdot,\cdot))),$ (7) $$

where, for brevity, we employ the notation $\gamma^{\otimes 2}$ for the product measure $d\gamma^{\otimes 2}((x,y),(x^{\prime},y^{\prime}))=d\gamma(x,y)d\gamma(x^{
\prime},y^{\prime})$. If
$L(a,b)=|a-b|^{p}$,
for $1\leq p<\infty$, we denote $GW^{L}(\cdot,\cdot)$ simply by $GW^{p}(\cdot,\cdot)$.
In this case, the expression (7) defines an equivalence relation $\sim$ among probability mm-spaces, i.e., $\mathbb{X}\sim\mathbb{Y}$ if and only if $GW^{p}(\mathbb{X},\mathbb{Y})=0$(^*^**Moreover, given two probability mm-spaces $\mathbb{X}$ and $\mathbb{Y}$, $GW(\mathbb{X},\mathbb{Y})=0$ if and only if there exists a bijective isometry $\phi:X\to Y$ such that $\phi_{\#}\mu=\nu$. In particular, the GW distance is invariant under rigid transformations (translations and rotations) of a given probability mm-space.). A minimizer of the GW problem (7) always exists, and thus, we can replace $\inf$ by $\min$. Moreover, similar to OT, the above GW problem defines a distance for probability mm-spaces after taking the quotient under $\sim$. For details, we refer to [, Ch. 5 and 10].

## 3 The Partial Gromov-Wasserstein (PGW) Problem

The Unbalanced Gromov-Wasserstein (UGW) problem for general (compact)
mm-spaces $\mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu)$, with $\mu\in\mathcal{M}_{+}(X),\nu\in\mathcal{M}_{+}(Y)$, studied in [, ] is defined as:

$$ $\displaystyle UGW^{L}_{\lambda}(\mathbb{X},\mathbb{Y}):=$ $\displaystyle\inf_{\gamma\in\mathcal{M}_{+}(X\times Y)}\gamma^{\otimes 2}(L(d_ {X},d_{Y}))+\lambda(D_{\phi}(\gamma_{1}^{\otimes 2}\parallel\mu^{\otimes 2})+D _{\phi}(\gamma_{2}^{\otimes 2}\parallel\nu^{\otimes 2})),$ (8) $$

where $\lambda>0$ is a fixed linear penalization parameter, and $D_{\phi}$ is a Csiszár or $\phi$-divergence. The above formulation extends the classical GW problem (7) into the unbalanced setting ($\mu$ and $\nu$ are no longer necessarily probability measures but general Radon measures).

We underline two points: First, as discussed in [], while the above quantity allows us to ‘compare’ the mm-spaces $\mathbb{X}$ and $\mathbb{Y}$, its metric property is unclear. Secondly, when $D_{\phi}$ is the KL divergence, a Sinkhorn solver has been proposed in []. However, a solver for general $\phi$-divergences has not yet been proposed.

In this paper, we will analyze the case when $D_{\phi}$ is the total variation norm. Specifically, for $q\geq 1$, we consider the following problem, which we refer to as the Partial Gromov-Wasserstein (PGW) problem:

$$ $PGW_{\lambda,q}^{L}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\mathcal{M}_{+}(X \times Y)}\gamma^{\otimes 2}(L(d_{X}^{q},d_{Y}^{q}))+\lambda(|\mu^{\otimes 2}- \gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_{2}^{\otimes 2}|).$ (9) $$

###### Remark 3.1 .

If $\gamma\in\Gamma\leq(\mu,\nu)$, the above cost functional can be rewritten as

$$ $\displaystyle\gamma^{\otimes 2}(L(d_{X}^{q},d_{Y}^{q}))+\lambda(|\mu^{\otimes 2 }-\gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_{2}^{\otimes 2}|)=\gamma^{ \otimes 2}\left(L(d_{X}^{q},d_{Y}^{q})-2\lambda\right)+\underbrace{\lambda \left(|\mu|^{2}+|\nu|^{2}\right)}_{\text{does not depend on $\gamma$}}.$ $$

###### Proposition 3.2 .

Given mm-spaces $\mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu)$, the minimization problem (9) can be restricted to the set
$\Gamma_{\leq}(\mu,\nu)=\{\gamma\in\mathcal{M}_{+}(X\times Y):\,\gamma_{1}\leq
\mu,\gamma_{2}\leq\nu\}$. That is,

$$ $PGW_{\lambda,q}^{L}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\Gamma_{\leq}(\mu, \nu)}\gamma^{\otimes 2}\left(L(d_{X}^{q},d_{Y}^{q})-2\lambda\right)+\lambda(| \mu|^{2}+|\nu|^{2}).$ (10) $$

For the proof, inspired by [], we direct the reader to Appendix B.

We notice that a similar Partial Gromov-Wasserstein problem (and its solver) has been studied []. Indeed, in [], the $\lambda$-penalization in the optimization problem (10) is avoided, but the constraint set is replaced by the subset of all $\gamma\in\Gamma_{\leq}(\mu,\nu)$ such that $|\gamma|=\rho$ for a fixed $\rho\in[0,\min\{|\mu|,|\nu|\}]$. We will call this formulation the Mass-Constrained Partial Gromov-Wasserstein (MPGW) problem. In Appendix L, we explore the relations between PGW and MPGW, and in Section 5 and Appendices O, P, we analyze the performance of the different solvers through different experiments.

###### Proposition 3.3 .

If $L(r_{1},r_{2})=|r_{1}-r_{2}|^{p}$, for $p\in[1,\infty)$,
we use $PGW^{p}_{\lambda,q}$ to denote $PGW^{L}_{\lambda,q}$. In this case,
(9) and (10) admit a minimizer.

The proof is given in Appendix C: Its idea extends results from [] from probability mm-spaces to arbitrary mm-spaces.

Next, we state one of our main results: The PGW problem gives rise to a metric between mm-spaces. The rigorous statement as well as its proof is given in Appendix D: The formal statement is based on the definition of equivalence classes among mm-spaces (see Remark D.1). The most difficult part of the proof is the triangle inequality and the main technique used relies on the relation between PGW and GW (see Appendix D.3).

###### Proposition 3.4 .

Let $\lambda>0$, $1\leq q,p<\infty$ and $L(r_{1},r_{2})=|r_{1}-r_{2}|^{p}$. Then $(PGW^{p}_{\lambda,q}(\cdot,\cdot))^{1/p}$ defines a metric between mm-spaces.

Finally, for consistency, we provide the following result when the penalization tends to infinity. Its proof is given in Appendix E.

###### Proposition 3.5 .

Consider probability mm-spaces $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$, that is, $|\mu|=|\nu|=1$. Assume that $L$ is a continuous funtion.
Then
$\lim_{\lambda\to\infty}PGW_{\lambda,q}^{L}(\mathbb{X},\mathbb{Y})=GW^{L}(
\mathbb{X},\mathbb{Y}).$

###### Remark 3.1 .

###### Proposition 3.2 .

###### Proposition 3.3 .

###### Proposition 3.4 .

###### Proposition 3.5 .

## 4 Computation of the Partial GW Distance

In the discrete setting, consider mm-spaces $\mathbb{X}=(X,d_{X},\sum_{i=1}^{n}p_{i}^{X}\delta_{x_{i}})$, $\mathbb{Y}=(Y,d_{Y},\sum_{j=1}^{m}q_{j}^{Y}\delta_{y_{j}})$, where $X=\{x_{1},\dots,x_{n}\}$, $Y=\{y_{1},\dots,y_{m}\}$, the weights $p_{i}^{X}$, $q_{j}^{Y}$ are non-negative numbers, and the distances $d_{X}$, $d_{Y}$ are determined by the matrices $C^{X}\in\mathbb{R}^{n\times n}$, $C^{Y}\in\mathbb{R}^{m\times m}$ defined by

$$ $C^{X}_{i,i^{\prime}}:=d_{X}^{q}(x_{i},x_{i^{\prime}})\quad\forall i,i^{\prime} \in[1:n]\quad\text{and}\quad C^{Y}_{j,j^{\prime}}:=d_{Y}^{q}(y_{j},y_{j^{ \prime}})\quad\forall j,j^{\prime}\in[1:m].$ (11) $$

Let $\mathrm{p}:=[q_{1}^{X},\dots,q_{n}^{X}]^{\top}$ and $\mathrm{q}:=[q_{1}^{Y},\dots,q_{m}^{Y}]^{\top}$ denote the weight vectors corresponding to the given discrete measures.
We view the sets of transportation plans $\Gamma(\mathrm{p},\mathrm{q})$ and $\Gamma_{\leq}(\mathrm{p},\mathrm{q})$ for the GW and PGW problems, respectively, as the subsets of $n\times m$ matrices

$$ $\Gamma(\mathrm{p},\mathrm{q}):=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\,\gamma 1 _{m}=\mathrm{p},\gamma^{\top}1_{n}=\mathrm{q}\},\quad\text{if }|\mathrm{p}|= \sum_{i=1}^{n}{p_{i}^{X}}=1=\sum_{j=1}^{m}{q_{j}^{Y}}=|\mathrm{q}|;$ (12) $$

$$ $\Gamma_{\leq}(\mathrm{p},\mathrm{q}):=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\, \gamma 1_{m}\leq\mathrm{p},\gamma^{\top}1_{n}\leq\mathrm{q}\},$ (13) $$

for any pair of non-negative vectors $\mathrm{p}\in\mathbb{R}^{n}_{+}$, $\mathrm{q}\in\mathbb{R}^{m}_{+}$,
where $1_{n}$ is the vector with all ones in $\mathbb{R}^{n}$ (resp. $1_{m}$), and $\gamma 1_{m}\leq\mathrm{p}$ means that component-wise the $\leq$ relation holds.

Given by a non-negative function $L:\mathbb{R}^{n\times n}\times\mathbb{R}^{m\times m}\to\mathbb{R}_{+}$,the transportation cost $M$ and the ‘partial’ transportation cost $\tilde{M}$ are represented by the $n\times m\times n\times m$ tensors:

$$ $M_{i,j,i^{\prime},j^{\prime}}=L(C_{i,i^{\prime}}^{X},C_{j,j^{\prime}}^{Y}) \qquad\text{ and }\qquad\tilde{M}:=M-2\lambda:=M-2\lambda 1_{n,m,n,m},$ (14) $$

where $1_{n,m,n,m}$ is the tensor with ones in all its entries.
For each $n\times m\times n\times m$ tensor $M$ and each $n\times m$ matrix $\gamma$, we define tensor-matrix multiplication
$M\circ\gamma\in\mathbb{R}^{n\times m}$
by

$$ $(M\circ\gamma)_{ij}=\sum_{i^{\prime},j^{\prime}}(M_{i,j,i^{\prime},j^{\prime}} )\gamma_{i^{\prime},j^{\prime}}.$ $$

Then, the Partial GW problem in (10) can be written as

$$ $PGW_{\lambda}^{L}(\mathbb{X},\mathbb{Y})=\min_{\gamma\in\Gamma_{\leq}(\mathrm{ p},\mathrm{q})}\mathcal{L}_{\tilde{M}}(\gamma)+\lambda(|\mathrm{p}|^{2}+| \mathrm{q}|^{2}),\quad\text{ where}$ (15) $$

$$ $\mathcal{L}_{\tilde{M}}(\gamma):=\tilde{M}\gamma^{\otimes 2}:=\sum_{i,j,i^{ \prime},j^{\prime}}\tilde{M}_{i,j,i^{\prime},j^{\prime}}\gamma_{i,j}\gamma_{i^ {\prime},j^{\prime}}=\sum_{ij}(\tilde{M}\circ\gamma)_{ij}\gamma_{ij}=:\langle \tilde{M}\circ\gamma,\gamma\rangle_{F},$ (16) $$

and $\langle\cdot,\cdot\rangle_{F}$ stands for the Frobenius dot product. The constant term $\lambda(|\mathrm{p}|^{2}+|\mathrm{q}|^{2})$ will be ignored in the rest of this paper since it does not depend on $\gamma$.

### 4.1 Frank-Wolfe for the PGW Problem – Solver 1

In this section, we discuss the Frank-Wolfe (FW) algorithm for the PGW problem (15). A second variant of the FW solver is provided in the Appendix G.

As a summary, in our proposed method, we address the discrete PGW problem (15), highlighting that the direction-finding subproblem in the Frank-Wolfe (FW) algorithm is a POT problem for (15). Specifically, (15) is treated as a discrete POT problem in our Solver 1, where we apply Proposition 2.1 to solve a discrete OT problem.

For each iteration $k$, the procedure is summarized in three steps detailed below.

The convergence analysis, detailed in Appendix K, applies the results from [] to our context, showing that the FW algorithm achieves a stationary point at a rate of $\mathcal{O}(1/\sqrt{k})$ for non-convex objectives with a Lipschitz continuous gradient in a convex and compact domain.

### Step 1. Computation of gradient and optimal direction.

It is straightforward to verify that
the gradient of the objective function (16) in (15) is given by

$$ $\displaystyle\nabla\mathcal{L}_{\tilde{M}}(\gamma)$ $\displaystyle=2\tilde{M}\circ\gamma.$ (17) $$

The classical method to compute $M\circ\gamma$ is the following:
First, convert $M$ into an $(n\times m)\times(n\times m)$ matrix, denoted as $v(M)$, and convert $\gamma$ into an $(n\times m)\times 1$ vector $v(\gamma)$.
Then, the computation of $M\circ\gamma$ is equivalent to the matrix multiplication $v(M)v(\gamma)$.
The computational cost and the required storage space are $\mathcal{O}(n^{2}m^{2})$. In certain conditions, the above computation can be reduced to $\mathcal{O}(n^{2}+m^{2})$. We refer to Appendices F and H for details.

Next, we aim to solve the following problem:

$$ $\gamma^{(k)^{\prime}}\leftarrow\arg\min_{\gamma\in\Gamma_{\leq}(\mathrm{p}, \mathrm{q})}\langle\nabla\mathcal{L}_{\tilde{M}}(\gamma^{(k)}),\gamma\rangle_{ F},$ $$

which is a discrete POT problem since it is equivalent to

$$ $\min_{\gamma\in\Gamma_{\leq}(\mathrm{p},\mathrm{q})}\langle 2M\circ\gamma^{(k) },\gamma\rangle_{F}+\lambda|\gamma^{(k)}|(|\mathrm{p}|+|\mathrm{q}|-2|\gamma|).$ $$

The solver can be obtained by firstly converting the POT problem into an OT problem via Proposition 2.1 and then solving the proposed OT problem.

### Step 2: Line search method.

In this step, at the $k$-th iteration, we need to determine the optimal step size:

$$ $\alpha^{(k)}=\arg\min_{\alpha\in[0,1]}\{\mathcal{L}_{\tilde{M}}((1-\alpha) \gamma^{(k)}+\alpha\gamma^{(k)^{\prime}})\}.$ $$

The optimal $\alpha^{(k)}$ takes the following values (see Appendix I for details):

$$ $\text{Let }\alpha^{(k)}=\begin{cases}0&\text{if }a\leq 0,a+b>0,\\ 1&\text{if }a\leq 0,a+b\leq 0,\\ \operatorname{clip}(\frac{-b}{2a},[0,1])&\text{if }a>0,\end{cases}\text{ where }\begin{cases}&\delta\gamma^{(k)}=\gamma^{(k)^{\prime}}-\gamma^{(k)},\\ &a=\langle\tilde{M}\circ\delta\gamma^{(k)},\delta\gamma^{(k)}\rangle_{F}\\ &b=2\langle\tilde{M}\circ\gamma^{(k)},\delta\gamma^{(k)}\rangle_{F}.\end{cases},$ (18) $$

and
$\operatorname{clip}(\frac{-b}{2a},[0,1])=\min\{\max\{-\frac{b}{2a},0\},1\}$.

### Step 3: Update γ ( k + 1 ) ← ( 1 − α ( k ) ) ⁢ γ ( k ) + α ( k ) ⁢ γ ( k ) ′ ← superscript 𝛾 𝑘 1 1 superscript 𝛼 𝑘 superscript 𝛾 𝑘 superscript 𝛼 𝑘 superscript 𝛾 superscript 𝑘 ′ \gamma^{(k+1)}\leftarrow(1-\alpha^{(k)})\gamma^{(k)}+\alpha^{(k)}\gamma^{(k)^{%
\prime}} italic_γ start_POSTSUPERSCRIPT ( italic_k + 1 ) end_POSTSUPERSCRIPT ← ( 1 - italic_α start_POSTSUPERSCRIPT ( italic_k ) end_POSTSUPERSCRIPT ) italic_γ start_POSTSUPERSCRIPT ( italic_k ) end_POSTSUPERSCRIPT + italic_α start_POSTSUPERSCRIPT ( italic_k ) end_POSTSUPERSCRIPT italic_γ start_POSTSUPERSCRIPT ( italic_k ) start_POSTSUPERSCRIPT ′ end_POSTSUPERSCRIPT end_POSTSUPERSCRIPT .

Figure: Algorithm 1 Frank-Wolfe Algorithm for PGW, ver 1

### 4.2 Numerical Implementation Details

The initial guess, $\gamma^{(1)}$. In the GW problem, the initial guess is simply set to $\gamma^{(1)}=\mathrm{p}\mathrm{q}^{\top}$ if there is no prior knowledge.
In PGW, however, as $\mu,\nu$ may not necessarily be probability measures (i.e., $\sum_{i}p_{i}^{X},\sum_{j}q_{j}^{Y}\neq 1$ in general), we set
$\gamma^{(1)}=\frac{\mathrm{p}\mathrm{q}^{\top}}{\max(|\mathrm{p}|,|\mathrm{q}|
)}.$
It is straightforward to verify that $\gamma^{(1)}\in\Gamma_{\leq}(\mathrm{p},\mathrm{q})$ as

$$ $\displaystyle\gamma^{(1)}1_{m}=\frac{|\mathrm{q}|\mathrm{p}}{\max(|\mathrm{p}| ,|\mathrm{q}|)}\leq\mathrm{p},\leavevmode\nobreak\ \leavevmode\nobreak\ \gamma ^{(1)\top}1_{n}=\frac{|\mathrm{p}|\mathrm{q}}{\max(|\mathrm{p}|,|\mathrm{q}|)} \leq\mathrm{q}.$ $$

Column/Row-Reduction.
According to the interpretation of the penalty weight parameter in the Partial OT problem (e.g. see Lemma 3.2 in []), during the POT solving step,
for each $i\in[1:n]$ (or $j\in[1:m]$), if the $i^{th}$ row ($j^{th}$ column) of $\tilde{M}\circ\gamma^{(k)}$ contains a non-negative entry, all the mass of $p_{i}^{X}$ ($q_{j}^{Y}$) will be destroyed (created). Thus, we can remove the corresponding row (column) to improve the computational efficiency.

## 5 Experiments

In addition to the three experiments detailed here, we also perform a wall-clock time comparison of our proposed PGW solvers in Appendix P.

### 5.1 Toy Example: Shape Matching with Outliers

We use the [moon](https://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_moons.html) dataset and synthetic 2D/3D spherical data in this experiment.
Let $\{x_{i}\}_{i=1}^{n},\{y_{j}\}_{j=1}^{n}$ denote the source and target point clouds. In addition, we add $\eta n$ (where $\eta=20\%$) outliers to the target point cloud. See Figure 1 for visualization.

We visualize the transportation plans given by the GW [], MPGW [], UGW [], and our proposed PGW problems. For MPGW, UGW, and PGW, we set the mass to be 1 for each point in the source and target point clouds. For GW, we normalize the mass of these points so that the source and target have the same total mass. From Figure 1, we observe that PGW and MPGW induce a one-by-one relation in both cases and no outlier points are matched to the source point cloud. Meanwhile, GW matches all of the outliers. For UGW, as it applies the Sinkhorn algorithm, we observe mass-splitting transportation plans in both cases. Moreover, we observe that some mass from the outliers has been matched, which is not desired.

Figure: Figure 1: The set of red points comprises the source point cloud. The union of the dark blue (outliers) and light blue points comprises the target point cloud. For UGW, MPGW, and PGW, we set the mass for each point to be the same. For GW, we normalize the mass for the balanced mass constraint setting.
Refer to caption: extracted/5880363/pics/shape_match.png

Figure: Figure 2: In each row, the first figure visualizes an example shape from each class, and the second figure visualizes the resulting pairwise distance matrices. The first row corresponds to Dataset I, and the second corresponds to Dataset II.
Refer to caption: x1.png

### 5.2 Shape Retrieval

Experiment setup. We now employ the PGW distance to distinguish between 2D shapes, as done in [], and use GW, MPGW, and UGW as baselines for comparison. Given a series of 2D shapes, we represent the shapes as mm-spaces $\mathbb{X}^{i}=(\mathbb{R}^{2},\|\cdot\|_{2},\mu^{i})$, where $\mu^{i}=\sum_{k=1}^{n^{i}}\alpha^{i}\delta_{x^{i}_{k}}$. For the GW method, we normalize the mass for the balanced mass constraint setting (i.e. $\alpha^{i}=\frac{1}{n^{i}}$), and for the remaining 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.

We then use the computed distances for nearest neighbor classification. We do this by choosing a representative at random from each class in the dataset and then classifying each shape according to its nearest representative. This is repeated over 10,000 iterations, and we generate a confusion matrix for each distance used. Finally, using the approach given by [, ], we combine each distance 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 two datasets in this experiment, which we refer to as Dataset I and Dataset II. We construct Dataset I by adapting the 2D shape dataset given in [], consisting of 20 shapes in each of the classes bone, goblet, star, and horseshoe. For each class, we augment the dataset with an additional class by selecting either a subset of points from each shape of that class (rectangle/bone, trapezoid/goblet, disk/star) or adding additional points to each shape of that class (annulus/horseshoe). Hence, the final dataset consists of 160 shapes across 8 total classes. This dataset is visualized in Figure 6(a).

For Dataset II, we generate 20 shapes for each of the classes rectangle, house, arrow, double arrow, semicircle, and circle. These shapes were generated in pairs, such that each shape of class rectangle is a subset of the corresponding shape of class house, and similarly for arrow/double arrow and semicircle/circle. This dataset is visualized in Figure 6(b).

**(a) Mean accuracy of SVM using each distance in kernel.**
| Distance | Dataset I | Dataset II |
| --- | --- | --- |
| GW | 0.9813 | 0.8083 |
| MPGW | 0.2375 | 0.2500 |
| UGW | 0.89375 | 0.9000 |
| PGW (ours) | 0.9625 | 1.0000 |

Performance analysis.
We refer to Appendix O for full numerical details, parameter settings, and the visualization of the resulting confusion matrices. We visualize the two considered datasets and the resulting pairwise distance matrices in Figure 2. For the SVM experiments, GW achieves the highest accuracy on Dataset I, 98.13%, while the second best method is PGW, 96.25%. For Dataset II, PGW achieves the highest accuracy, correctly classifying 100% of the samples. The complete set of accuracies for all considered distances on each dataset is reported in Table 1(a).

In addition, we report the wall-clock time required to compute all pairwise distances for each distance in Table 1(b). We observe that GW, MPGW, and PGW have similar wall-clock times across both experiments (30-50 seconds for Dataset I, 80-140 seconds for Dataset II), with PGW admitting a slightly faster runtime in both cases. Meanwhile, UGW requires almost 1500 seconds on the experiment with Dataset I and over 500 seconds on the experiment with Dataset II.

### 5.3 Partial Gromov-Wasserstein Barycenter and Shape Interpolation

Figure: Figure 3: In the first column, the first and second figures are the source and target point clouds in the first experiment ($\eta=5\%$); the third and fourth figures are the source and target point clouds in the second experiment ($\eta=10\%$).
Refer to caption: x5.png

By [], Gromov-Wasserstein can be applied to interpolate two shapes via the concept of Gromov-Wasserstein Barycenters. In this paper, we introduce Partial Gromov-Wasserstein Barycenters by extending the GW Barycenter to the setting of PGW as follows.

Consider the discrete mm-spaces $\mathbb{X}^{1},\ldots,\mathbb{X}^{K}$, where $\mathbb{X}^{k}=(X^{k},\|\cdot\|_{\mathbb{R}^{d_{k}}},\sum_{i=1}^{n_{k}}p_{i}^{
k}\delta_{x^{k}_{i}})$, with $X^{k}=\{x_{i}^{k}\}_{i=1}^{n_{k}}\subset\mathbb{R}^{d_{k}}$. We denote $C^{k}=[\|x^{k}_{i}-x^{k}_{i^{\prime}}\|^{2}]_{i,i^{\prime}}$ and $\mathrm{p}^{k}=[p_{1}^{k},\dots,p^{k}_{n_{k}}]$. Given positive constants $\lambda_{1},\ldots,\lambda_{K}>0$, the PGW Barycenter is defined by:

$$ $\displaystyle\min_{C,\gamma_{k}}\sum_{k}\xi_{k}\langle M(C,C^{k})\circ\gamma^{ k},\gamma^{k}\rangle-2\lambda_{k}|\gamma^{k}|^{2}$ (19) $$

where each $\gamma^{k}\in\Gamma_{\leq}(\mathrm{p},\mathrm{p}^{k})$.
We refer to Appendix M for the solver of (19) and details.

Experiment setup. We apply the PGW barycenter to the following problem:
Given two shapes $X=\{x_{i}\}_{i=1}^{n}\subset\mathbb{R}^{d_{1}}$ and $Y=\{y_{i}\}_{i=1}^{m}\subset\mathbb{R}^{d_{2}}$, modeled as mm-spaces $\mathbb{X}=(X,\|\cdot\|_{\mathbb{R}^{d_{1}}},\sum_{i=1}^{n}\delta_{x_{i}})$ and $\mathbb{Y}=(Y,\|\cdot\|_{\mathbb{R}^{d_{2}}},\sum_{i=1}^{m}\delta_{y_{i}})$, we wish to find interpolations between them. In addition, we assume $\mathbb{Y}$ is corrupted by noise, i.e., $\mathbb{Y}$ is redefined as
$\mathbb{Y}=(\tilde{Y},\|\cdot\|_{\mathbb{R}^{d_{2}}},\sum_{i=1}^{m}\delta_{y_{
i}}+\sum_{i=1}^{m\eta}\delta_{\tilde{y}_{i}})$ with $\tilde{Y}=Y\cup\{\tilde{y}_{i}\}_{i=1}^{m}$,
where $\eta\in[0,1]$ is the noise level and each $\tilde{y}_{i}$ is randomly selected from a particular region $\mathcal{R}\subset\mathbb{R}^{d_{2}}$.

Dataset setup. We adapt the dataset given in []. See Appendix M.1 for further details on the dataset. In this experiment, we test $\eta=5\%,10\%$. We visualize the barycenter interpolation from $t=0/7$ to $t=7/7$, where $(1-t),t$ are the weight of the source $\mathbb{X}$ and the target $\mathbb{Y}$, respectively, in the barycenter (19). The visualization given in Figure 3 is obtained by applying SMACOF MDS (multidimensional scaling) of the minimizer $C$.

Performance analysis. From Figure 3, we observe that in this two scenarios, the interpolation derived from GW is clearly disturbed by the noise data points. For example, in rows $1,3$, columns $t=1/7,2/7,3/7$, we see that the point clouds reconstructed by MDS have significantly different width-height ratios from those of the source and target point clouds. In contrast, PGW is significantly less disturbed, and the interpolation is more natural. The width-height ratio of the point clouds generated by the PGW barycenter is consistent with that of the source/target point clouds.

## 6 Summary

In this paper, we propose the Partial Gromov-Wasserstein (PGW) problem and introduce two Frank-Wolfe solvers for it. As a byproduct, we provide pertinent theoretical results, including the relation between PGW and GW, the metric property of PGW, and the PGW barycenter. Furthermore, we demonstrate the efficacy of the PGW solver in solving shape-matching, shape-retrieval, and shape-interpolation tasks. For the shape retrieval experiment, we observe that due to the metric property, PGW and GW have similar accuracy and outperform the other methods evaluated. In the shape matching and point cloud interpolation experiments, we demonstrate that PGW admits a more robust result when the data are corrupted by outliers/noisy data.

## Appendix A Notation and Abbreviations

- •
OT: Optimal Transport.
- •
POT: Partial Optimal Transport.
- •
GW: Gromov-Wasserstein.
- •
PGW: Partial Gromov-Wasserstein.
- •
FW: Frank-Wolfe.
- •
MPGW: Mass-Constrained Partial Gromov-Wasserstein.
- •
$\|\cdot\|$: Euclidean norm.
- •
$X^{2}=X\times X$.
- •
$\mathcal{M}_{+}(X)$: set of all positive (non-negative) Randon (finite) measures defined on $X$.
- •
$\mathcal{P}_{2}(X)$: set of all probability measures defined on $X$, whose second moment is finite.
- •
$\mathbb{R}_{+}$: set of all non-negative real numbers.
- •
$\mathbb{R}^{n\times m}$: set of all $n\times m$ matrices with real coefficients.
- •
$\mathbb{R}^{n\times m}_{+}$ (resp. $\mathbb{R}^{n}_{+}$): set of all $n\times m$ matrices (resp., $n$-vectors) with non-negative coefficients.
- •
$\mathbb{R}^{n\times m\times n\times m}$: set of all $n\times m\times n\times m$ tensors with real coefficients.
- •
$1_{n},1_{n\times m},1_{n\times m\times n\times m}$: vector, matrix, and tensor of all ones.
- •
$\mathbbm{1}_{E}$: characteristic function of a measurable set $E$
$\mathbbm{1}_{E}(z)=\begin{cases}1&\text{ if }z\in E,\\
0&\text{ otherwise.}\end{cases}$
- •
$\mathbb{X},\mathbb{Y}$: metric measure spaces (mm-spaces): $\mathbb{X}=(X,d_{X},\mu),\,\mathbb{Y}=(Y,d_{Y},\nu).$
- •
$C^{X}$: given a discrete mm-space $\mathbb{X}=(X,d_{X},\mu)$, where $X=\{x_{1},\dots,x_{n}\}$, the symmetric matrix $C^{X}\in\mathbb{R}^{n\times n}$ is defined as $C^{X}_{i,i^{\prime}}=d_{X}^{q}(x_{i},x_{i}^{\prime})$.
- •
$\mu^{\otimes 2}$: product measure $\mu\otimes\mu$.
- •
$T_{\#}\sigma$: $T:X\to Y$ is a measurable function and $\sigma$ is a measure on $X$. $T_{\#}\sigma$ is the push-forward measure of $\sigma$, i.e., its is the measure on $Y$ such that for all Borel set $A\subset Y$, $T_{\#}\sigma(A)=\sigma(T^{-1}(A))$.
- •
$\gamma,\gamma_{1},\gamma_{2}$: $\gamma$ is a joint measure defined in a product space having $\gamma_{1},\gamma_{2}$ as its first and second marginals, respectively. In the discrete setting, they are viewed as matrices and vectors, i.e., $\gamma\in\mathbb{R}_{+}^{n\times m}$, and $\gamma_{1}=\gamma 1_{m}\in\mathbb{R}_{+}^{n}$, $\gamma_{2}=\gamma^{\top}1_{n}\in\mathbb{R}_{+}^{m}$.
- •
$\pi_{1}:X\times Y\to X$, canonical projection mapping, with $(x,y)\mapsto x$.
Similarly, $\pi_{2}:X\times Y\to Y$ is canonical projection mapping, with $(x,y)\mapsto y$.
- •
$\pi_{1,2}:S\times X\times Y\to X\times Y$, canonical projection mapping, with $(s,x,y)\to(x,y)$.
Similarly, $\pi_{0,1}$ maps $(s,x,y)$ to $(s,x)$;
$\pi_{0,2}$ maps $(s,x,y)$ to $(s,y)$.
- •
$\Gamma(\mu,\nu)$, where $\mu\in\mathcal{P}_{2}(X),\nu\in\mathcal{P}_{2}(Y)$ (where
$X,Y$ may not necessarily be the same set): it is the set of all the couplings (transportation plans) between $\mu$ and $\nu$, i.e.,
$\Gamma(\mu,\nu):=\{\gamma\in\mathcal{P}_{2}(X\times Y):\,\gamma_{1}=\mu,\gamma
_{2}=\nu\}.$
- •
$\Gamma(\mathrm{p},\mathrm{q})$: set of all the couplings between the discrete probability measures $\mu=\sum_{i=1}^{n}p_{i}^{X}\delta_{x_{i}}$ and $\nu=\sum_{j=1}^{m}q_{j}^{Y}\delta_{y_{j}}$
with weight vectors
$\mathrm{p}=[p_{1}^{X},\dots,p_{n}^{X}]^{\top}\qquad\text{ and }\qquad\mathrm{q
}=[q_{1}^{Y},\dots,q_{m}^{Y}]^{\top}.$
(20)
That is, $\Gamma(\mathrm{p},\mathrm{q})$ coincides with $\Gamma(\mu,\nu)$, but it is viewed as a subset of $n\times m$ matrices defined in (12).
- •
$p,q$: real numbers $1\leq p,q<\infty$.
- •
$\mathrm{p},\mathrm{q}$:
vectors of weights as in (20).
- •
$\mathrm{p}=[p_{1},\dots,p_{n}]\leq\mathrm{p}^{\prime}=[p^{\prime}_{1},\dots,p^
{\prime}_{n}]$ if $p_{j}\leq p_{j}^{\prime}$ for all $1\leq j\leq n$.
- •
$|\mathrm{p}|=\sum_{i=1}^{n}p_{i}$ for $\mathrm{p}=[p_{1},\dots,p_{n}]$.
- •
$c(x,y):X\times Y\to\mathbb{R}_{+}$ denotes the cost function used for classical and partial optimal transport problems. lower-semi continuous function.
- •
$OT(\mu,\nu)$: it is the classical optimal transport (OT) problem between the probability measures $\mu$ and $\nu$ defined in (1).
- •
$W_{p}(\mu,\nu)$: it is the $p$-Wasserstein distance between the probability measures $\mu$ and $\nu$ defined in (2), for $1\leq p<\infty$.
- •
$POT(\mu,\nu;\lambda)$: the Partial Optimal Transport (OPT) problem defined in (3).
- •
$|\mu|$: total variation norm of the positive Randon (finite) measure $\mu$ defined on a measurable space $X$, i.e., $|\mu|=\mu(X)$.
- •
$\mu\leq\sigma$: denotes that for all Borel set $B\subseteq X$ we have that the measures $\mu,\sigma\in\mathcal{M}_{+}(X)$ satisfy $\mu(B)\leq\sigma(B)$.
- •
$\Gamma_{\leq}(\mu,\nu)$, where $\mu\in\mathcal{M}_{+}(X),\nu\in\mathcal{M}_{+}(Y)$: set of all “partial transportation plans”
$\Gamma_{\leq}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(X\times Y):\,\gamma_{1}\leq
\mu,\gamma_{2}\leq\nu\}.$
- •
$\Gamma_{\leq}(\mathrm{p},\mathrm{q})$: set of all the “partial transportation plans” between the discrete probability measures $\mu=\sum_{i=1}^{n}p_{i}^{X}\delta_{x_{i}}$ and $\nu=\sum_{j=1}^{m}q_{j}^{Y}\delta_{y_{j}}$
with weight vectors $\mathrm{p}=[p_{1}^{X},\dots,p_{n}^{X}]$ and $\mathrm{q}=[q_{1}^{Y},\dots,q_{m}^{Y}]$. That is, $\Gamma_{\leq}(\mathrm{p},\mathrm{q})$ coincides with $\Gamma_{\leq}(\mu,\nu)$, but it is viewed as a subset of $n\times m$ matrices defined in (13).
- •
$\lambda>0$: positive real number.
- •
$\hat{\infty}$: auxiliary point.
- •
$\hat{X}=X\cup\{\hat{\infty}\}$.
- •
$\hat{\mu},\hat{\nu}$: given in (4).
- •
$\hat{\mathrm{p}},\hat{\mathrm{q}}$: given in (53).
- •
$\hat{\gamma}$: given in (6).
- •
$\hat{c}(\cdot,\cdot):\hat{X}\times\hat{Y}\to\mathbb{R}_{+}$: cost as in (5).
- •
$L:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$: cost function for the GW problems.
- •
$D:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$: generic distance on $\mathbb{R}$ used for GW problems.
- •
$GW^{L}(\cdot,\cdot)$: GW optimization problem given in (7).
- •
$GW^{p}(\cdot,\cdot)$: GW optimization problem given in (7) when $L(a,b)=|a-b|^{p}$.
- •
$GW^{L}_{q}(\cdot,\cdot)$: general GW optimization problem for $g\geq 1$ given in (33).
- •
$GW^{p}_{q}(\cdot,\cdot)$: general GW optimization problem for $q\geq 1$ and $L(a,b)=|a-b|^{p}$ given in (34).
- •
$GW^{p}_{\lambda,q}(\cdot,\cdot)$: generalized GW problem given in (39).
- •
$\widehat{GW}$: GW-variant problem given in (51) for the general case, and in (55) for the discrete setting.
- •
$\hat{L}$: cost given in (16) for the GW-variant problem.
- •
$d:\hat{X}\times\hat{X}\to\mathbb{R}_{+}\cup\{\infty\}$: “generalized” metric given in (50) for $\hat{X}$.
- •
$\mathbb{X}\sim\mathbb{Y}$: equivalence relation in for mm-spaces, $\mathbb{X}\sim\mathbb{Y}$ if and only if
they have the same total mass and
$GW_{q}^{p}(\mathbb{X},\mathbb{Y})=0$.
- •
$PGW_{\lambda,q}^{L}(\cdot,\cdot)$: partial GW optimization problem given in (9) or, equivalently, in (10).
- •
$PGW_{\lambda,q}^{p}(\cdot,\cdot)$:
partial GW optimization problem given in (10) when
$L(a,b)=|a-b|^{p}$.
- •
$PGW_{\lambda}(\cdot,\cdot)$: is is the PGW problem $PGW_{\lambda,q}^{p}(\cdot,\cdot)$ for the case when $p=2=q$.
- •
$\mu(\phi)$: given a measure $\mu$ and a function $\phi$,
$\mu(\phi):=\int\phi(x)d\mu(x).$
- •
$C(\gamma;\lambda,\mu,\nu)$: the transportation cost induced by transportation plan $\gamma\in\Gamma_{\leq}(\mu,\nu)$ in the Partial GW problem 10,
$C(\gamma;\lambda,\mu,\nu):=\gamma^{\otimes 2}(L(d_{X}^{q},d_{Y}^{q}))+\lambda(
|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}).$
- •
$\mathcal{L}$: functional for the optimization problem $PGW_{\lambda}(\cdot,\cdot)$.
- •
$M$, $\tilde{M}$, and $\hat{M}$: see (14), and (54). Notice that, $(M-2\lambda)_{i,i^{\prime},j,j^{\prime}}:=M_{i,i^{\prime},j,j^{\prime}}-2\lambda.$
- •
$\langle\cdot,\cdot\rangle_{F}$: Frobenius inner product for matrices, i.e., $\langle A,B\rangle_{F}=\mathrm{trace}(A^{\top}B)=\sum_{i,j}^{n,m}A_{i,j}B_{i,j}$ for all $A,B\in\mathbb{R}^{n\times m}$.
- •
$M\circ\gamma$: product between the tensor $M$ and the matrix $\gamma$.
- •
$\nabla$: gradient.
- •
$[1:n]=\{1,\dots,n\}$.
- •
$\alpha$: step size based on the line search method.
- •
$\gamma^{(1)}$: initialization of the algorithm.
- •
$\gamma^{(k)}$, $\gamma^{(k)^{\prime}}$: previous and new transportation plans before and after step 1 in the $k-$th iteration of version 1 of our proposed FW algorithm.
- •
$\hat{\gamma}^{(k)}$, $\hat{\gamma}^{(k)^{\prime}}$: previous and new transportation plans before and after step 1 in the $k-$th iteration of version 2 of our proposed FW algorithm.
- •
$G=2\tilde{M}\circ\gamma$, $\hat{G}=2\hat{M}\circ\hat{\gamma}$: Gradient of the objective function in version 1 and version 2, respectively, of our proposed FW algorithm for solving the discrete version of partial GW problem.
- •
$(\delta\gamma,a,b)$ and $(\delta\hat{\gamma},a,b)$: given in (18) and (56) for versions 1 and 2 of the algorithm, respectively.
- •
$C^{1}$-function: continuous and with continuous derivatives.
- •
$MPGW_{\rho}(\cdot,\cdot)$: Mass-Constrained Partial Gromov-Wasserstein defined in (77)
- •
$\Gamma^{\rho}_{\leq}(\mu,\nu)$: set transport plans defined in (78) for the Mass-Constrained Partial Gromov-Wasserstein problem.
- •
$\Gamma_{PU,\pi}(\mathrm{p},\mathrm{q})$: defined in (LABEL:eq:pot_init_constraint).

## Appendix B Proof of Proposition 3.2

The idea of the proof is inspired by the proof of Proposition 1 in [].

The goal is to verify that

$$ $\displaystyle P$ $\displaystyle GW_{\lambda,q}^{L}(\mathbb{X},\mathbb{Y})$ $\displaystyle:=\inf_{\gamma\in\mathcal{M}_{+}(X,Y)}\underbrace{\int_{(X\times Y )^{2}}L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{\prime}))d\gamma^{\otimes 2}}_{ \text{transport GW cost}}+\underbrace{\lambda\left(|\mu^{\otimes 2}-\gamma_{1} ^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_{2}^{\otimes 2}|\right)}_{\text{mass penalty}}$ $\displaystyle={\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{(X\times Y)^{2}}L(d _{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{\prime}))d\gamma^{\otimes 2}}+{\lambda \left(|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_{2}^{ \otimes 2}|\right)}.$ (21) $$

Consider $\gamma\in\mathcal{M}_{+}(X\times Y)$ such that $\gamma_{1}\leq\mu$ does not hold.
Then we can write the Lebesgue decomposition of $\gamma_{1}$ with respect to $\mu$:

$$ $\gamma_{1}=f\mu+\mu^{\perp},$ $$

where
$f\geq 0$ is the Radon-Nikodym derivative of $\gamma_{1}$ with respect to $\mu$, and $\mu^{\perp},\mu$ are mutually singular, that is,
there exist measurable sets $A,B$ such that $A\cap B=\emptyset$, $X=A\cup B$ and $\mu^{\perp}(A)=0,\mu(B)=0$. Without loss of generality, we can assume that the support of $f$ lies on $A$, since

$$ $\gamma_{1}(E)=\int_{E\cap A}f(x)\,d\mu(x)+\mu^{\perp}(E\cap B)\qquad\forall E \subseteq X\text{ measurable}.$ $$

Define $A_{1}=\{x\in A:\,f(x)>1\},A_{2}=\{x\in A:\,f(x)\leq 1\}$ (both are measurable, since $f$ is measurable), and define $\bar{\mu}=\min\{f,1\}\mu$. Then,

$$ $\bar{\mu}\leq\mu\qquad\text{ and }\qquad\bar{\mu}\leq f\mu\leq f\mu+\mu^{\perp }=\gamma_{1}.$ $$

There exists a $\bar{\gamma}\in\mathcal{M}_{+}(X\times Y)$ such that $\bar{\gamma}_{1}=\bar{\mu},\bar{\gamma}\leq\gamma$, and $\bar{\gamma}_{2}\leq\gamma_{2}$. Indeed, we can construct $\bar{\gamma}$ in the following way: First, let $\{\gamma^{x}\}_{x\in X}$ be the set of conditional measures (disintegration) such that for every measurable (test) function $\psi:X\times Y\to\mathbb{R}$ we have

$$ $\int\psi(x,y)\,d\gamma(x,y)=\int_{X}\int_{Y}\psi(x,y)\,d\gamma^{x}(y)\,d\gamma _{1}(x).$ $$

Then, define $\bar{\gamma}$ as

$$ $\bar{\gamma}(U):=\int_{X}\int_{Y}\mathbbm{1}_{U}(x,y)\,d\gamma^{x}(y)\,d\bar{ \mu}(x)\qquad\forall U\subseteq X\times Y\text{ Borel}.$ $$

Then, $\bar{\gamma}$ verifies that $\bar{\gamma}_{1}=\bar{\mu}$, and since $\bar{\mu}\leq\gamma_{1}$, we also have that
$\bar{\gamma}\leq\gamma$, which implies $\bar{\gamma}_{2}\leq\gamma_{2}$.

Since $|\gamma_{1}|=|\gamma_{2}|$ and $|\bar{\gamma}_{1}|=|\bar{\gamma}_{2}|$, then we have $|\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2}|=|\gamma_{2}^{\otimes 2}-
\bar{\gamma}_{2}^{\otimes 2}|$.

We claim that

$$ $|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|\geq|\mu^{\otimes 2}-\bar{\gamma}_{1}^ {\otimes 2}|+|\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2}|.$ (22) $$

- •
Left-hand side of (22):
Since $\{A,B\}$ is a partition of $X$, we first split the left-hand side of (22) as
$\displaystyle|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|$
$\displaystyle=\underbrace{(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(A\times A)}
_{(I)}+\underbrace{(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(A\times B)+(\mu^{
\otimes 2}-\gamma_{1}^{\otimes 2})(B\times A)}_{(II)}$
$\displaystyle\quad+\underbrace{(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(B
\times B)}_{(III)}.$
Then we have
$\displaystyle(III)=(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(B\times B)=\mu^{
\perp}\otimes\mu^{\perp}(B\times B)=|\mu^{\perp}|^{2},$
$\displaystyle(II)=(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(A\times B)+(\mu^{
\otimes 2}-\gamma_{1}^{\otimes 2})(B\times A)=2|\mu^{\perp}|(\mu-\gamma_{1})(A).$
Since $\gamma_{1}=f\mu$ in $A$, then $\bar{\gamma}_{1}=\gamma_{1}$
in $A_{2}$ and $\bar{\gamma}_{1}=\mu$ in $A_{1}$, so we have
$\displaystyle(\mu-\gamma_{1})(A)$
$\displaystyle=(\mu-\gamma_{1})(A_{1})+(\mu-\gamma_{1})(A_{2})=(\gamma_{1}-\bar
{\gamma}_{1})(A_{1})+(\mu-\bar{\gamma}_{1})(A_{2})$
$\displaystyle=(\gamma_{1}-\bar{\gamma}_{1})(A)+(\mu-\bar{\gamma}_{1})(A).$
Thus,
$\displaystyle(II)$
$\displaystyle=2|\mu^{\perp}|((\gamma_{1}-\bar{\gamma}_{1})(A)+(\mu-\bar{\gamma
}_{1})(A)),$
and we also get that
$\displaystyle(I)$
$\displaystyle=(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(A\times A)$
$\displaystyle=(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})({A_{1}\times A_{1}})+(
\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(A_{2}\times A_{2})+(\mu^{\otimes 2}-
\gamma_{1}^{\otimes 2})(A_{1}\times A_{2})$
$\displaystyle\qquad+(\mu^{\otimes 2}-\gamma_{1}^{\otimes 2})(A_{2}\times A_{1})$
$\displaystyle=(\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})({A_{1}
\times A_{1}})+(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A_{2}\times A_{2
})+$
$\displaystyle\qquad+|\bar{\gamma}_{1}\otimes\mu-\gamma_{1}\otimes\bar{\gamma}_
{1}|(A_{1}\times A_{2})+|\mu\otimes\bar{\gamma}_{1}-\bar{\gamma}_{1}\otimes
\gamma_{1}|(A_{2}\times A_{1})$
$\displaystyle=(\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})({A_{1}
\times A_{1}})+(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A_{2}\times A_{2
})+2(\bar{\gamma}_{1}-\gamma_{1})(A_{1})(\mu-\bar{\gamma}_{1})(A_{2})$
$\displaystyle=(\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})({A\times A
})+(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A\times A)+\underbrace{2(
\bar{\gamma}_{1}-\gamma_{1})(A_{1})(\mu-\bar{\gamma}_{1})(A_{2})}_{\geq 0}.$
- •
Right-hand side of (22):
First notice that
$(\gamma_{1}-\bar{\gamma}_{1})(B)=(\gamma_{1}-\bar{\gamma}_{1})(B)\leq\gamma_{1
}(B)=|\mu^{\perp}|,$
and since $\bar{\gamma}_{1}\leq\mu$ and $\mu(B)=0$, we have
$(\mu-\bar{\gamma}_{1})(B)=0.$
Then,
$\displaystyle|\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2}|+|\gamma_{1}^{
\otimes 2}-\bar{\gamma}_{1}^{\otimes 2}|=$
$\displaystyle=(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A\times A)+(
\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A\times A)+(\mu^{\otimes 2
}-\bar{\gamma}_{1}^{\otimes 2})(B\times B)$
$\displaystyle\quad+(\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(B
\times B)+{(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A\times B)}+(\gamma_
{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A\times B)$
$\displaystyle\quad+{(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(B\times A)}
+(\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(B\times A)$
$\displaystyle\leq\underbrace{(\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A
\times A)+(\gamma_{1}^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2})(A\times A)}_{
\leq(I)}+\underbrace{|\mu^{\perp}|^{2}}_{=(III)}+\underbrace{2|\mu^{\perp}|(
\gamma_{1}-\bar{\gamma}_{1})(A)}_{=(II)}.$

Thus, (22) holds.

We finish the proof of the proposition by noting that

$$ $\displaystyle|\mu^{\otimes 2}-\bar{\gamma}_{1}^{\otimes 2}|+|\nu^{\otimes 2}- \bar{\gamma}_{2}^{\otimes 2}|$ $\displaystyle\leq|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|-|\gamma_{1}^{\otimes 2 }-\bar{\gamma}_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\bar{\gamma}_{2}^{\otimes 2}|$ $\displaystyle=|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|-|\gamma_{2}^{\otimes 2} -\bar{\gamma}_{2}^{\otimes 2}|+|\nu^{\otimes 2}-\bar{\gamma}_{2}^{\otimes 2}|$ $\displaystyle\leq|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}- \gamma_{2}^{\otimes 2}|$ $$

where the first inequality follows from (22), and the second inequality holds from the fact the total variation norm $|\cdot|$ satisfies triangular inequality.
Therefore $\bar{\gamma}$ induces a smaller transport GW cost than $\gamma$ (since $\bar{\gamma}\leq\gamma$), and also $\bar{\gamma}$ decreases the mass penalty in comparison that corresponding to $\gamma$.
Thus, $\bar{\gamma}$ is a better GW transportation plan, which satisfies $\bar{\gamma}_{1}\leq\mu$. Similarly, we can further construct $\bar{\gamma}^{\prime}$ based on $\bar{\gamma}$ such that $\bar{\gamma}^{\prime}_{1}\leq\mu,\bar{\gamma}^{\prime}_{2}\leq\nu$. Therefore, we can restrict the minimization in (9) from $\mathcal{M}_{+}(X\times Y)$ to $\Gamma_{\leq}(\mu,\nu)$.
Thus, the equality (21) is satisfied.

###### Proof of Remark 3.1 .

Given $\gamma\in\Gamma_{\leq}(\mu,\nu)$, since $\gamma_{1}\leq\mu$, $\gamma_{2}\leq\nu$, and $\gamma_{1}(X)=|\gamma_{1}|=|\gamma|=|\gamma_{2}|=\gamma_{2}(Y)$, we have

$$ $\displaystyle|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_ {2}^{\otimes 2}|$ $\displaystyle=\mu^{\otimes 2}(X^{2})-\gamma_{1}^{\otimes 2}(X^{2})+\nu^{ \otimes 2}(Y^{2})-\gamma_{2}^{\otimes 2}(Y^{2})$ $\displaystyle=|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2},$ $$

and so the transportation cost in partial GW problem (10) becomes

$$ $\displaystyle C$ $\displaystyle(\gamma;\lambda,\mu,\nu)$ $\displaystyle:=\int_{(X\times Y)^{2}}L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{ \prime}))\,d\gamma(x,y)d\gamma(x^{\prime},y^{\prime})+\lambda\left(|\mu^{ \otimes 2}-\gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_{2}^{\otimes 2}|\right)$ $\displaystyle=\int_{(X\times Y)^{2}}L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{ \prime}))\,d\gamma(x,y)d\gamma(x^{\prime},y^{\prime})+\lambda\left(|\mu|^{2}+| \nu|^{2}-2|\gamma|^{2}\right)$ $\displaystyle=\int_{(X\times Y)^{2}}\left(L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}( y,y^{\prime})-2\lambda\right)\,d\gamma(x,y)d\gamma(x^{\prime},y^{\prime})+ \underbrace{\lambda\left(|\mu|^{2}+|\nu|^{2}\right)}_{\text{does not depend on $\gamma$}}.$ (23) $$

∎

###### Proof of Remark 3.1 .

## Appendix C Proof of Proposition 3.3

In this section, we discuss the minimizer of the Partial GW problem (9).
Trivially, $\Gamma_{\leq}(\mu,\nu)\subseteq\mathcal{M}_{+}(X\times Y)$ and
by using Proposition 3.2 it is enough to show that a minimizer for problem (10) exists.

We refer the reader to [, Chapters 5 and 10] for similar ideas.

### C.1 Formal Statement of Proposition 3.3

Suppose $X,Y$ are compact sets, then exists compact set $[0,\beta]\subset\mathbb{R}$, such that

$$ $d(x,x^{\prime}),\,d(y,y^{\prime})\in[0,\beta],\qquad\forall x,x^{\prime}\in X, y,\,y^{\prime}\in Y$ $$

Let $A=[0,\beta^{q}]$.
Let $L_{A^{2}}$ denote the restriction of $L$ on $A^{2}$, i.e.
$L_{A^{2}}:A^{2}\to\mathbb{R}$ with
$L_{A^{2}}(r_{1},r_{2})=L(r_{1},r_{2})$, $\forall r_{1},r_{2}\in A$.
Suppose $L$ satisfies the following:
there exists $0<K<\infty$ such that for every $r_{1},r_{1}^{\prime},r_{2},r_{2}^{\prime}\in A$,

$$ $\displaystyle|L_{A^{2}}(r_{1},r_{2})-L_{A^{2}}(r_{1}^{\prime},r_{2})|\leq K|r_ {1}-r_{1}^{\prime}|,\,\,\,|L_{A^{2}}(r_{1},r_{2})-L_{A^{2}}(r_{1},r_{2}^{ \prime})|\leq K|r_{2}-r_{2}^{\prime}|$ (24) $$

(i.e., $L_{A^{2}}$ is Lipschitz on each variable).
Then $PGW^{L}_{\lambda}(\cdot,\cdot)$ admits a minimizer.

Note, the condition (24) contains the case $L(r_{1},r_{2})=|r_{1}-r_{2}|^{p}$ as a special case:

###### Lemma C.1 .

If $L(r_{1},r_{2})=|r_{1}-r_{2}|^{p}$, for $1\leq p<\infty$, then $L$ satisfies the condition (24).

###### Proof.

Assume that $L$ is defined on an interval of the form $[0,M]$, for some $M>0$.
Consider $r_{1},r_{1}^{\prime},r_{2},r_{2}^{\prime}\in[0,M]$.
If $p=1$, by triangle inequality we have

$$ $\displaystyle|L(r_{1},r_{2})-L(r_{1}^{\prime},r_{2})|$ $\displaystyle=||r_{1}-r_{2}|-|r_{1}^{\prime}-r_{2}||\leq|r_{1}-r_{1}^{\prime}|$ $$

and similarly,

$$ $\displaystyle|L(r_{1},r_{2})-L(r_{1},r_{2}^{\prime})|$ $\displaystyle\leq|r_{2}-r_{2}^{\prime}|.$ $$

From [, page 473], since for $1\leq p<\infty$, the function $t\mapsto t^{p}$, for $t\in[0,M]$, is Lipschitz with constant bounded
by $pM^{p-1}$, we have

$$ $\displaystyle|L(r_{1},r_{2})-L(r_{1}^{\prime},r_{2})|$ $\displaystyle\leq pM^{p-1}|r_{1}-r_{1}^{\prime}|.$ $$

and similarly,

$$ $\displaystyle|L(r_{1},r_{2})-L(r_{1},r_{2}^{\prime})|$ $\displaystyle\leq pM^{p-1}|r_{2}-r_{2}^{\prime}|.$ $$

∎

###### Lemma C.2 .

Given $q\geq 1$, consider $\beta>0$. Then $[0,\beta]\ni c\mapsto c^{q}\in[0,\beta^{q}]$ is a Lipschitz function.

###### Proof.

Given $c_{1},c_{2}\in[0,\beta]$, we have

$$ $\displaystyle|c_{1}^{q}-c_{2}^{q}|\leq q\beta^{q-1}|c_{1}-c_{2}|$ (25) $$

Thus, $c\mapsto c^{q}$ is a Lipschitz function.
∎

###### Lemma C.1 .

###### Proof.

###### Lemma C.2 .

###### Proof.

### C.2 Convergence Auxiliary Result

If a sequence $\{\gamma^{n}\}$ converges weakly to $\gamma$, we write $\gamma^{n}\overset{w}{\rightharpoonup}\gamma$. In this setting, if $\gamma^{n}\overset{w}{\rightharpoonup}\gamma$, it does not imply that $(\gamma^{n})^{\otimes 2}\overset{w}{\rightharpoonup}\gamma^{\otimes 2}$. Thus, the technique used in classical OT for proving the existence of a minimizer for the optimal transport optimization problem as a consequence of the Stone-Weierstrass theorem does not apply directly in the Gromov-Wasserstein context.

Inspired by [], we introduce the following lemma.

###### Lemma C.3 .

Given metric space $(Z,d_{Z})$, suppose $\phi:Z^{2}\to\mathbb{R}$ is a Lipschitz continuous function with respect to $(Z^{2},d_{Z}^{+})$, where

$$ $d_{Z}^{+}((z_{1},z_{2}),(z_{1}^{\prime},z_{2}^{\prime})):=d_{Z}(z_{1},z_{1}^{ \prime})+d_{Z}(z_{2},z_{2}^{\prime}),\qquad\forall(z_{1},z_{2}),(z_{1}^{\prime },z_{2}^{\prime})\in Z^{2}.$ $$

Given $\gamma\in\mathcal{M}_{+}(Z)$, and a sequence $\{\gamma^{n}\}_{n\geq 1}\in\mathcal{M}_{+}(Z)$ such that converges weakly to $\gamma$,

$$ $\gamma^{n}\overset{w}{\rightharpoonup}\gamma\qquad({n\to\infty}).$ $$

Finally, consider the mapping

$$ $Z\ni z\mapsto\gamma(\phi(z,\cdot)):=\int_{Z}\phi(z,z^{\prime})d\gamma(z^{ \prime})\in\mathbb{R}.$ $$

Then we have the following results:

- (1)
$\gamma^{n}(\phi(z,\cdot))\to\gamma(\phi(z,\cdot))$ uniformly (when $n\to\infty$).
- (2)
$(\gamma^{n})^{\otimes 2}(\phi(\cdot,\cdot))\to\gamma^{\otimes 2}(\phi(\cdot,
\cdot))$ (when $n\to\infty$).
- (3)
If $\mathcal{M}\subset\mathcal{M}_{+}(Z)$ is compact for the weak convergence, then
$\inf_{\gamma\in\mathcal{M}}\gamma^{\otimes 2}(\phi(\cdot,\cdot))$ admits a minimizer.

###### Proof.

The main idea of the proof is similar to [, Lemma 10.3]: we extend it from $\mathcal{P}_{+}(Z)$ to $\mathcal{M}_{+}(Z)$.

- (1)
Since $\gamma^{n}\overset{w}{\rightharpoonup}\gamma$, and $Z$ is compact, we have $|\gamma^{n}|\to|\gamma|$. Then, given $\epsilon>0$, for $n$ sufficiently large we have $|\gamma^{n}|\leq|\gamma|+\epsilon$.
Let us denote by $\|\phi\|_{Lip}$ the Lipschitz constant of $\phi$. For any $z_{1},z_{2}\in Z$, we have:
$\displaystyle|\gamma^{n}(\phi(z_{1},\cdot))-\gamma^{n}(\phi(z_{2},\cdot))|$
$\displaystyle\leq\int_{Z}|\phi(z_{1},z)-\phi(z_{2},z)|\gamma^{n}(z)$
$\displaystyle\leq\max_{z\in Z}|\phi(z_{1},z)-\phi(z_{2},z)|(|\gamma|+\epsilon)$
$\displaystyle\leq(|\gamma|+\epsilon)\|\phi\|_{Lip}\,d_{Z}(z_{1},z_{2})=Kd_{Z}(
z_{1},z_{2}),$
where $K=(|\gamma|+\epsilon)\|\phi\|_{Lip}$ is a finite positive value.
Note that the above inequality also holds if we replace $\gamma^{n}$ by $\gamma$.
Since $(Z,d_{Z})$ is compact, $Z=\bigcup_{i=1}^{N}B(z_{i},\epsilon/K)$ for some $z_{1},\ldots,z_{N}\in Z$, where $B(z_{i},\epsilon/3K)=\{z\in Z:\,d_{Z}(z,z_{i})\leq\epsilon/3K\}$ is the closed ball centered at $z_{i}$, with radius $\epsilon/K$. By definition of weak convergence, when $n$ is sufficiently large,
$|\gamma^{n}(\phi(z_{i},\cdot))-\gamma(\phi(z_{i},\cdot))|<\epsilon/3,\qquad
\text{for each }i\in[1:N].$
Given $z\in Z$, then $z\in B(z_{i})$ for some $z_{i}$. For sufficiently large $n$, we have:
$\displaystyle|\gamma^{n}(\phi(z,\cdot))-\gamma(\phi(z,\cdot))|$
$\displaystyle\leq|\gamma^{n}(\phi(z,\cdot))-\gamma^{n}(\phi(z_{i},\cdot))|+|
\gamma^{n}(\phi(z_{i},\cdot))-\gamma(\phi(z_{i},\cdot))|+|\gamma(\phi(z_{i},
\cdot))-\gamma(\phi(z,\cdot))|$
$\displaystyle\leq Kd(z,z_{i})+\epsilon/3+Kd(z,z_{i})=\epsilon/3+\epsilon/3+
\epsilon/3=\epsilon.$
(26)
Thus we prove the first statement.
- (2)
We recall that we do not have $(\gamma^{n})^{\otimes 2}\overset{w}{\rightharpoonup}\gamma^{\otimes 2}$.
Consider an arbitrary $\epsilon>0$. We have,
$\displaystyle 0$
$\displaystyle\leq\limsup_{n\to\infty}|(\gamma^{n})^{\otimes 2}(\phi)-(\gamma)^
{\otimes 2}(\phi)|$
(27)
$\displaystyle\leq\limsup_{n\to\infty}\underbrace{|(\gamma^{n}\otimes\gamma^{n}
)(\phi)-(\gamma\otimes\gamma^{n})(\phi)|}_{A_{n}}+\limsup_{n\to\infty}
\underbrace{|(\gamma^{n}\otimes\gamma)(\phi)-(\gamma\otimes\gamma)(\phi)|}_{B_
{n}}.$
For the first term, when $n$ is sufficiently large, by statement (1), we have:
$\displaystyle A_{n}$
$\displaystyle=\int\left(\gamma^{n}(\phi(z,\cdot))-\gamma(\phi(z,\cdot)\right)d
\gamma^{n}(z)$
$\displaystyle\leq\max_{z}|\gamma^{n}(\phi(z,\cdot))-\gamma(\phi(z,\cdot)||
\gamma^{n}|$
$\displaystyle\leq\epsilon(|\gamma|+\epsilon)$
(28)
Thus, $\limsup_{n}A=\lim_{n}A=0$.
Similarly, for the second term, when $n$ is sufficiently large, we have
$\displaystyle B_{n}$
$\displaystyle:=\int(\gamma^{n}(\phi(z,\cdot))-\gamma(\phi(z,\cdot)))d\gamma(z)
\leq\epsilon|\gamma|.$
(29)
Thus, $\limsup_{n}B_{n}=\lim_{n}B_{n}=0$.
Therefore, from (27), (28) and (29), we obtain
$\displaystyle\limsup_{n\to\infty}|(\gamma^{n})^{\otimes 2}(\phi)-(\gamma)^{
\otimes 2}(\phi)|=\lim_{n\to\infty}|(\gamma^{n})^{\otimes 2}(\phi)-(\gamma)^{
\otimes 2}(\phi)|=0.$
(30)
- (3)
Let $\gamma^{n}\in\mathcal{M}$ be a sequence such that $(\gamma^{n})^{\otimes 2}(\phi)$ (weakly) converges to $\inf_{\gamma\in\mathcal{M}}\gamma^{\otimes 2}(\phi)$.
Since $\mathcal{M}$ is compact, there exists a sub-sequence $\gamma^{n_{k}}\overset{w}{\rightharpoonup}\gamma$ for some $\gamma\in\mathcal{M}$.
Then, by statement (2), we have:
$\gamma^{\otimes 2}(\phi)=\lim_{k}(\gamma^{n_{k}})^{\otimes 2}(\phi)=\inf_{
\gamma\in\mathcal{M}}\gamma^{\otimes 2}(\phi),$
and we complete the proof.

∎

###### Lemma C.3 .

###### Proof.

### C.3 Proof of the Formal Statement for Proposition 3.3

The proof follows the ideas of [, Corollary 10.1].

Define $(Z,d_{Z})$ as
$Z:=X\times Y$, with $d_{Z}((x,y),(x^{\prime},y^{\prime})):=d_{X}(x,x^{\prime})+d_{Y}(y,y^{\prime})$.

We claim that the following mapping

$$ $\displaystyle(X\times Y)^{2}=Z^{2}$ $\displaystyle\to\mathbb{R}$ $\displaystyle((x,y),(x^{\prime},y^{\prime}))$ $\displaystyle\mapsto\phi((x,y),(x^{\prime},y^{\prime})):=L(d_{X}^{q}(x,x^{ \prime}),d_{Y}^{q}(y,y^{\prime}))-2\lambda$ $$

is a Lipschitz function with respect to $d_{Z}^{+}$, where $L$ satisfies (24).
Indeed, given $((x_{1},y_{1}),(x^{\prime}_{1},y^{\prime}_{1})),((x_{2},y_{2}),(x^{\prime}_{2}
,y^{\prime}_{2}))\in Z^{2}$, we have:

$$ $\displaystyle|\phi((x_{1},y_{1}),(x^{\prime}_{1},y^{\prime}_{1}))-\phi((x_{2}, y_{2}),(x^{\prime}_{2},y^{\prime}_{2}))|$ $\displaystyle=|L(d_{X}(x_{1},x_{1}^{\prime}),d_{Y}(y_{1},y_{1}^{\prime}))-L(d_ {X}(x_{2},x_{2}^{\prime}),d_{Y}(y_{2},y_{2}^{\prime}))|$ $\displaystyle\leq|L(d_{X}(x_{1},x_{1}^{\prime}),d_{Y}(y_{1},y_{1}^{\prime}))-L (d_{X}(x_{2},x_{2}^{\prime}),d_{Y}(y_{1},y_{1}^{\prime}))|$ $\displaystyle\quad+|L(d_{X}(x_{2},x_{2}^{\prime}),d_{Y}(y_{1},y_{1}^{\prime})) -L(d_{X}(x_{2},x_{2}^{\prime}),d_{Y}(y_{2},y_{2}^{\prime}))|$ $\displaystyle\leq K|d_{X}^{q}(x_{1},x^{\prime}_{1})-d_{X}^{q}(x_{2},x^{\prime} _{2})|+K|d_{Y}^{q}(y_{1},y^{\prime}_{1})-d_{Y}^{q}(y_{2},y^{\prime}_{2})|$ $\displaystyle\leq K^{\prime}|d_{X}(x_{1},x^{\prime}_{1})-d_{X}(x_{2},x^{\prime }_{2})|+K^{\prime}|d_{Y}(y_{1},y^{\prime}_{1})-d_{Y}(y_{2},y^{\prime}_{2})|$ (31) $\displaystyle\leq K^{\prime}(d_{X}(x_{1},x^{\prime}_{2})+d_{X}(x_{1}^{\prime}, x^{\prime}_{2}))+K^{\prime}(d_{Y}(y_{1},y_{2})+d_{Y}(y_{1}^{\prime},y_{2}^{ \prime}))$ (32) $\displaystyle=K^{\prime}\left[\left((d_{X}(x_{1},x_{2})+d_{Y}(y_{1},y_{2}) \right)+\left((d_{X}(x_{1}^{\prime},x_{2}^{\prime})+d_{Y}(y_{1}^{\prime},y_{2} ^{\prime})\right)\right]$ $\displaystyle=K^{\prime}\left[d_{Z}((x_{1},y_{1}),(x_{2},y_{2}))+d_{Z}((x_{1}^ {\prime},y_{1}^{\prime}),(x_{2}^{\prime},y_{2}^{\prime}))\right]$ $\displaystyle=K^{\prime}d_{Z}^{+}(((x_{1},y_{1}),(x_{2},y_{2})),((x_{1},y_{1}) ,(x_{2},y_{2})))$ $$

where in (31), $K^{\prime}=q\beta^{q-1}K$; the inequality holds by lemma C.2; The inequality (32) follows from the triangle inequality:

$$ $\displaystyle d_{X}(x_{1},x^{\prime}_{1})-d_{X}(x_{2},x_{2}^{\prime})$ $\displaystyle\leq d_{X}(x_{1},x_{2})+d_{X}(x_{2},x_{2}^{\prime})+d_{X}(x_{2}^{ \prime},x_{1}^{\prime})-d_{X}(x_{2},x_{2}^{\prime})$ $\displaystyle=d_{X}(x_{1},x_{2})+d_{X}(x_{1}^{\prime},x_{2}^{\prime}),$ $$

and similarly,

$$ $d_{X}(x_{2},x^{\prime}_{2})-d_{X}(x_{1},x_{1}^{\prime})\leq d_{X}(x_{1},x_{2}) +d_{X}(x_{1}^{\prime},x_{2}^{\prime}).$ $$

Let $\mathcal{M}=\Gamma_{\leq}(\mu,\nu)$.
From [, Proposition B.1], we have that $\Gamma_{\leq}(\mu,\nu)$ is a compact set with respect to the weak convergence topology.

By Lemma (C.3) part (3), we have the PGW problem, which can be written as

$$ $\displaystyle\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\gamma^{\otimes 2}(\phi)+ \lambda(|\mu|^{2}+|\nu|^{2})$ $$

admits a solution, i.e., a minimizer $\gamma\in\Gamma_{\leq}(\mu,\nu)$. Therefore, we end the proof of Proposition 3.3.

## Appendix D Proof of Proposition 3.4 : Metric Property of Partial GW

Let $L(r_{1},r_{2})=D^{p}(r_{1},r_{2})$ for a metric $D$ on $\mathbb{R}$, and since all the metrics in $\mathbb{R}$ are equivalent, for simplicity, consider $D(r_{1},r_{2})=|r_{1}-r_{2}|$. (Notice that this satisfies the hypothesis of Proposition H.1 used in the experiments).

Consider the GW problem, for $q\geq 1$,

$$ $GW^{L}_{q}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{(X \times Y)^{2}}L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{\prime}))\,d\gamma^{ \otimes 2},$ (33) $$

or, in particular,

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

For probability mm-spaces we have the equivalence relation $\mathbb{X}\sim\mathbb{Y}$ if and only if $GW^{p}_{q}(\mathbb{X},\mathbb{Y})=0$.

By [, Chapter 5], $\mathbb{X}\sim\mathbb{Y}$ is equivalent to the following: there exists a bijective isometry mapping $\phi:X\to Y$, such that

$$ $\displaystyle d_{X}(x,x^{\prime})-d_{Y}(\phi(x),\phi(x^{\prime}))=0,\quad\mu^{ \otimes 2}-a.s.$ $\displaystyle\phi_{\#}\mu=\nu.$ $$

###### Remark D.1 .

In the literature, the case where $q=1$ is the most frequently considered problem. In particular, in [] it is stated the equivalence relation
$\mathbb{X}\sim\mathbb{Y}$ if and only if there exists $\phi:X\to Y$ such that $\phi_{\#}\mu=\nu$ and
$d_{X}(x,x^{\prime})=d_{Y}(\phi(x),\phi(x^{\prime}))$ $\mu^{\otimes 2}-a.s.$ if and only if $GW^{p}_{1}(\mathbb{X},\mathbb{Y})=0$. Thus, $\mathbb{X}\sim\mathbb{Y}$ is also equivalent to have $\phi:X\to Y$ such that $\phi_{\#}\mu=\nu$ and
$d_{X}(x,x^{\prime})=d_{Y}(y,y^{\prime})$ $\gamma^{\otimes 2}-a.s.$ where $\gamma$ is a minimizer for $GW^{p}_{1}(\mathbb{X},\mathbb{Y})$. So, in this situation we also have $d_{X}^{q}(x,x^{\prime})=d_{Y}^{q}(y,y^{\prime})$ $\gamma^{\otimes 2}-a.s.$ for any given $q\geq 1$. Therefore, $\mathbb{X}\sim\mathbb{Y}$ if and only if $GW^{p}_{q}(\mathbb{X},\mathbb{Y})=0$.

###### Remark D.1 .

### D.1 Formal Statement of Proposition 3.4

We first introduce the formal statement of Proposition 3.4. To do so, we extend the equivalence relation $\sim$ to all mm-spaces (not only probability mm-spaces):
Given arbitrary mm-spaces $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$, where $X,Y$ are compact and $\mu\in\mathcal{M}_{+}(X)$, $\nu\in\mathcal{M}_{+}(Y)$, we write $\mathbb{X}\sim\mathbb{Y}$ if and only if they have the same total mass (i.e., $|\mu|=\mu(X)=\nu(Y)=|\nu|$) and $GW^{p}_{q}(\mathbb{X},\mathbb{Y})=0$.

Formal statement of Proposition 3.4: Given $\lambda>0$, $1\leq p,q<\infty$, then $(PGW_{\lambda,q}^{p}(\cdot,\cdot))^{1/p}$ defines a metric among mm-spaces under taking quotient with respect to the equivalence relation $\sim$.

Next, we discuss its proof.

### D.2 Non-Negativity and Symmetry Properties

It is straightforward to verify $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})\geq 0$, and that $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})=PGW_{\lambda,q}^{p}(\mathbb{Y},
\mathbb{X})$. In what follows, we will concentrate on proving $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})=0$ if and only if $\mathbb{X}\sim\mathbb{Y}$:

If $\mathbb{X}\sim\mathbb{Y}$, then $|\mu|=|\nu|$, and we have

$$ $0\leq PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})\leq GW_{q}^{p}(\mathbb{X}, \mathbb{Y})=0,$ $$

where the inequality follows from the fact
$\Gamma(\mu,\nu)\subseteq\Gamma_{\leq}(\mu,\nu)$.
Thus, $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})=0$.

For the other direction, suppose that $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})=0$.
We claim that $|\mu|=|\nu|$ and that there exist an optimal plan $\gamma$ for $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})$ such that $|\mu|=|\gamma|=|\nu|$. Let us prove this by contradiction.
Assume $|\mu|<|\nu|$. For convenience, suppose $|\mu|^{2}\leq|\nu|^{2}-\epsilon$, for some $\epsilon>0$. Then, for each $\gamma\in\Gamma_{\leq}(\mu,\nu)$, we have $|\gamma^{\otimes 2}|\leq|\mu|^{2}\leq|\nu|^{2}-\epsilon$, and so

$$ $\displaystyle PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})\geq\lambda(|\mu|^{2}+ |\nu|^{2}-2|\gamma|^{2})\geq\lambda(|\nu^{2}|-|\gamma|^{2})\geq\lambda\epsilon >0.$ $$

Thus, $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})>0$, which is a contradiction. So, $|\mu|=|\nu|$. In addition, if $\gamma\in\Gamma_{\leq}(\mu,\nu)$ is optimal for $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})$, we have $|\gamma|=|\mu|=|\nu|$, thus $\gamma\in\Gamma(\mu,\nu)$.
Therefore, since $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})=0$,
and for such optimal $\gamma$ we have
$|\gamma|=|\mu|=|\nu|$, we obtain

$$ $\displaystyle\int_{(X\times Y)^{2}}|d_{X}^{q}(x,x^{\prime})-d_{Y}^{q}(y,y^{ \prime})|^{p}d\gamma^{\otimes 2}=0.$ $$

As a result, $d_{X}^{q}(x,x^{\prime})=d_{Y}^{q}(y,y^{\prime})$ $\gamma^{\otimes 2}-a.s.$, which implies that
$GW_{q}^{p}(\mathbb{X},\mathbb{Y})=0$, and so $\mathbb{X}\sim\mathbb{Y}$.

### D.3 Triangle Inequality – Strategy: Convert the PGW Problem into a GW Problem

Consider three arbitrary mm-spaces $\mathbb{S}=(S,d_{S},\sigma)$, $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$. We define
$\hat{\mathbb{S}}=(\hat{S},d_{\hat{S}},\hat{\sigma})$, $\hat{\mathbb{X}}=(\hat{X},d_{\hat{X}},\hat{\mu})$, $\hat{\mathbb{Y}}=(\hat{Y},d_{\hat{Y}},\hat{\nu})$ in a similar way to that of Proposition G.1 but now aiming to have new spaces with equal total mass:

First, introduce auxiliary points $\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2}$ and set

$$ $\displaystyle\begin{cases}\hat{S}&=S\cup\{\hat{\infty}_{0},\hat{\infty}_{1}, \hat{\infty}_{2}\},\\ \hat{X}&=X\cup\{\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2}\},\\ \hat{Y}&=Y\cup\{\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2}\}.\end{cases}$ $$

Define $\hat{\sigma},\hat{\mu},\hat{\nu}$ as follows:

$$ $\begin{cases}\hat{\sigma}&=\sigma+|\mu|\delta_{\hat{\infty}_{1}}+|\nu|\delta_{ \hat{\infty}_{2}},\\ \hat{\mu}&=\mu+|\sigma|\delta_{\hat{\infty}_{0}}+|\nu|\delta_{\hat{\infty}_{2} },\\ \hat{\nu}&=\nu+|\sigma|\delta_{\hat{\infty}_{0}}+|\mu|\delta_{\hat{\infty}_{1} }.\end{cases}$ (35) $$

Note that $\hat{\sigma}$ is not supported on point $\hat{\infty}_{0}$, similarly, $\hat{\mu}$ is not supported on $\hat{\infty}_{1}$, $\hat{\nu}$ is not supported on $\hat{\infty}_{2}$.
In addition, we have $|\hat{\mu}|=|\hat{\nu}|=|\hat{\sigma}|=|\mu|+|\nu|+|\sigma|$.
(For a similar idea in classical unbalanced optimal transport see, for example, [].)

Finally, define $d_{\hat{S}}:\hat{S}^{2}\to\mathbb{R}\cup\{\infty\}$ as follows:

$$ $\displaystyle d_{\hat{S}}(s,s^{\prime})=\begin{cases}d_{S}(s,s^{\prime})&\text {if }(s,s^{\prime})\in S^{2},\\ \infty&\text{elsewhere. }\end{cases}$ (36) $$

Note, $d_{\hat{S}}(\cdot,\cdot)$ is not a rigorous metric in $\hat{S}$ since we allow $d_{\hat{S}}=\infty$. Similarly, define
$d_{\hat{X}},d_{\hat{Y}}$.
As a result, we have constructed new spaces

$$ $\displaystyle\hat{\mathbb{S}}=(\hat{S},d_{\hat{S}},\hat{\sigma}),\quad\hat{ \mathbb{X}}=(\hat{X},d_{\hat{X}},\hat{\mu}),\quad\hat{\mathbb{Y}}=(\hat{Y},d_{ \hat{Y}},\hat{\nu}).$ (37) $$

We define the following mapping $D_{\lambda}:(\mathbb{R}\cup\{\infty\})\times(\mathbb{R}\cup\{\infty\})\to
\mathbb{R}_{+}$:

$$ $\displaystyle D^{p}_{\lambda}(r_{1},r_{2})=\begin{cases}|r_{1}-r_{2}|^{p}& \text{if }r_{1},r_{2}<\infty,\\ \lambda&\text{if }r_{1}=\infty,r_{2}<\infty\text{ or vice versa},\\ 0&\text{if }r_{1}=r_{2}=\infty.\end{cases}$ (38) $$

Note that $D_{\lambda}$ is not a rigorous metric since it may sometimes violate triangle inequality. See the following lemma for a detailed and precise explanation.

###### Lemma D.2 .

Let $D_{\lambda}(\cdot,\cdot)$ denote the function defined in (38).
For any
$r_{0},r_{1},r_{2}\in\mathbb{R}\cup\{\infty\}$, we have the following:

- •
$D_{\lambda}(r_{1},r_{2})\geq 0$. $D_{\lambda}(r_{1},r_{2})=0$ if and only if $r_{1}=r_{2}$, where $r_{1}=r_{2}$ denotes that
$r_{1}=r_{2}\in\mathbb{R}$ or $r_{1}=r_{2}=\infty$.
- •
Except the case $r_{1},r_{2}\in\mathbb{R},r_{0}=\infty$, for all other cases, we have
$D_{\lambda}(r_{1},r_{2})\leq D_{\lambda}(r_{1},r_{0})+D_{\lambda}(r_{2},r_{0}).$

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

It is straightforward to verify $D_{\lambda}(\cdot,\cdot)\geq 0$.

Now, consider $r_{0},r_{1},r_{2}\in\mathbb{R}\cup\{\infty\}$.
If $r_{1}=r_{2}\in\mathbb{R}$ or $r_{1}=r_{2}=\infty$,
we have
$D_{\lambda}(r_{1},r_{2})=0$.
Otherwise, $D_{\lambda}(r_{1},r_{2})>0$.
So, $D_{\lambda}(r_{1},r_{2})=0$ if and only if $r_{1}=r_{2}$.

For the second item, we have the following cases:

Case 1: $r_{1},r_{2},r_{0}\in\mathbb{R}$,

$$ $\displaystyle D_{\lambda}(r_{1},r_{2})$ $\displaystyle=|r_{1}-r_{2}|$ $\displaystyle\leq|r_{1}-r_{2}|+|r_{2}-r_{0}|$ $\displaystyle=D_{\lambda}(r_{0},r_{1})+D_{\lambda}(r_{0},r_{2})$ $$

Case 2: $r_{1},r_{2}\in\mathbb{R},r_{0}=\infty$. We do not need to verify the inequality in this case.

Case 3: $r_{1}\in\mathbb{R},r_{2},r_{0}=\infty$, or $r_{1}=\infty,r_{2}\in\mathbb{R},r_{0}=\infty$.
In this case, we have

$$ $\displaystyle D_{\lambda}(r_{1},r_{2})=D_{\lambda}(r_{1},r_{0})=\sqrt{\lambda} ,D_{\lambda}(r_{2},r_{0})=0$ $$

and it is straightforward to verify the inequality.

Case 4: $r_{1},r_{2}=\infty,r_{3}\in\mathbb{R}$. In this case, we have
$D_{\lambda}(r_{1},r_{2})=0\leq D_{\lambda}(r_{0},r_{1})+D_{\lambda}(r_{0},r_{2})$.

Case 5: $r_{1},r_{2},r_{0}=\infty$.
In this case, we have

$$ $\displaystyle D_{\lambda}(r_{1},r_{2})=D_{\lambda}(r_{1},r_{0})=D_{\lambda}(r_ {2},r_{0})=0$ $$

and it is straightforward to verify the inequality.
∎

We construct the following generalized GW problem:

$$ $\displaystyle GW^{p}_{\lambda,q}(\hat{\mathbb{X}},\hat{\mathbb{Y}})$ $\displaystyle:=\inf_{\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})}\underbrace{ \int_{(\hat{X}\times\hat{Y})^{2}}D_{\lambda}^{p}(d^{q}_{\hat{X}}(x,x^{\prime}) ,d^{q}_{\hat{Y}}(y,y^{\prime}))\,d\hat{\gamma}^{\otimes 2}}_{\hat{C}(\hat{ \gamma};\lambda,\hat{\mu},\hat{\nu})}.$ (39) $$

Similarly, we define $GW^{p}_{\lambda,q}(\hat{\mathbb{X}},\hat{\mathbb{S}})$, and $GW^{p}_{\lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{Y}})$.

The mapping (6) is modified as:

$$ $\displaystyle\Gamma_{\leq}(\sigma,\mu)\ni\gamma^{01}\mapsto\hat{\gamma}^{01} \in\Gamma(\hat{\sigma},\hat{\mu}),$ $\displaystyle\hat{\gamma}^{01}:=\gamma^{01}+(\sigma-\gamma_{1}^{01})\otimes \delta_{\hat{\infty}_{0}}+\delta_{\hat{\infty}_{1}}\otimes(\mu-\gamma_{2}^{01} )+|\gamma|\delta_{\hat{\infty}_{1},\hat{\infty}_{0}}+|\nu|\delta_{\hat{\infty} _{2},\hat{\infty}_{2}};$ $\displaystyle\Gamma_{\leq}(\sigma,\nu)\ni\gamma^{02}\mapsto\hat{\gamma}^{02} \in\Gamma(\hat{\sigma},\hat{\nu}),$ $\displaystyle\hat{\gamma}^{02}:=\gamma^{02}+(\sigma-\gamma_{1}^{02})\otimes \delta_{\hat{\infty}_{0}}+\delta_{\hat{\infty}_{2}}\otimes(\nu-\gamma_{2}^{02} )+|\gamma|\delta_{\hat{\infty}_{2},\hat{\infty}_{0}}+|\mu|\delta_{\hat{\infty} _{1},\hat{\infty}_{1}};$ $\displaystyle\Gamma_{\leq}(\mu,\nu)\ni\gamma^{12}\mapsto\hat{\gamma}^{12}\in \Gamma(\hat{\mu},\hat{\nu}),$ $\displaystyle\hat{\gamma}^{12}:=\gamma^{12}+(\mu-\gamma_{1}^{12})\otimes\delta _{\hat{\infty}_{1}}+\delta_{\hat{\infty}_{2}}\otimes(\nu-\gamma_{2}^{12})+| \gamma|\delta_{\hat{\infty}_{2},\hat{\infty}_{1}}+|\mu|\delta_{\hat{\infty}_{0 },\hat{\infty}_{0}}.$ (40) $$

It is straightforward to verify the above mappings are well-defined.
In addition, we can observe that, for each $\gamma^{01}\in\Gamma_{\leq}(\sigma,\mu),\gamma^{02}\in\Gamma_{\leq}(\sigma,\nu
),\gamma^{12}\in\Gamma_{\leq}(\mu,\nu)$,

$$ $\displaystyle\hat{\gamma}^{01}(\{\hat{\infty}_{2}\}\times X)=\hat{\gamma}^{01} (S\times\{\hat{\infty}_{2}\})=0,$ (41) $\displaystyle\hat{\gamma}^{02}(\{\hat{\infty}_{1}\}\times Y)=\hat{\gamma}^{02} (S\times\{\hat{\infty}_{1}\})=0,$ (42) $\displaystyle\hat{\gamma}^{12}(\{\hat{\infty}_{0}\}\times Y)=\hat{\gamma}^{12} (X\times\{\hat{\infty}_{0}\})=0.$ $$

###### Proposition D.3 .

If $\gamma^{12}\in\Gamma_{\leq}(\mu,\nu)$ is optimal in PGW problem $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})$, then $\hat{\gamma}^{12}$ defined in (40) is optimal in generalized GW problem $GW_{\lambda,q}^{p}(\hat{\mathbb{X}},\hat{\mathbb{Y}})$.
Furthermore,
$\hat{C}(\hat{\gamma}^{12};\lambda,\hat{\mu},\hat{\nu})=C(\gamma^{12};\lambda,
\mu,\nu),$
and thus,

$$ $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})=GW_{\lambda,q}^{p}(\hat{\mathbb{X}} ,\hat{\mathbb{Y}}).$ $$

###### Proof of Proposition D.3 .

For each $\gamma\in\Gamma_{\leq}(\mu,\nu)$, define $\hat{\gamma}$ by (40).

Note that if we merge the points $\hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3}$ as $\hat{\infty}$, i.e.

$$ $\hat{\infty}=\hat{\infty}_{1}=\hat{\infty}_{2}=\hat{\infty}_{3},$ $$

the value $\hat{C}(\hat{\gamma};\lambda,\hat{\mu},\hat{\nu})$ will not change. Thus, we merge these three auxiliary points.

We have:

$$ $\displaystyle\hat{C}(\hat{\gamma};\lambda,\hat{\mu},\hat{\nu})=\int_{(\hat{X} \times\hat{Y})^{2}}D_{\lambda}^{p}(d^{q}_{\hat{X}}(x,x^{\prime}),d^{q}_{\hat{Y }}(x,x^{\prime}))d\hat{\gamma}^{\otimes 2}$ $\displaystyle=\int_{(X\times Y)^{2}}|d^{q}_{X}(x,x^{\prime})-d^{q}_{Y}(y,y^{ \prime})|^{p}d\hat{\gamma}^{\otimes 2}+\int_{(\{\hat{\infty}\}\times Y)^{2}} \lambda d\hat{\gamma}^{\otimes 2}+\int_{(X\times\{\hat{\infty}\})^{2}}\lambda \hat{\gamma}^{\otimes 2}$ $\displaystyle\quad+2\int_{(\{\hat{\infty}\}\times Y)\times(X\times Y)}\lambda d \hat{\gamma}^{\otimes 2}+2\int_{(X\times\{\hat{\infty}\})\times(X\times Y)} \lambda d\hat{\gamma}^{\otimes 2}+\int_{(\{\hat{\infty}\}\times\{\hat{\infty} \})^{2}}D_{\lambda}^{p}(\infty,\infty)d\hat{\gamma}^{\otimes 2}$ $\displaystyle\quad+2\int_{(\{\hat{\infty}\}\times Y)\times(X\times\{\hat{ \infty}\})}D_{\lambda}^{p}(\infty,\infty)d\hat{\gamma}^{\otimes 2}+2\int_{(\{ \hat{\infty}\}\times\{\hat{\infty}\})\times(X\times Y)}D_{\lambda}^{p}(\infty, \infty)d\hat{\gamma}^{\otimes 2}$ $\displaystyle\quad+2\int_{(\{\hat{\infty}\}\times\{Y\})\times\{\hat{\infty}\}^ {2}}D_{\lambda}^{p}(\infty,\infty)d\hat{\gamma}^{\otimes 2}+2\int_{(X\times\{ \hat{\infty}\})\times\{\hat{\infty}\}^{2}}D_{\lambda}^{p}(\infty,\infty)d\hat{ \gamma}^{\otimes 2}$ $\displaystyle=\int_{(X\times Y)^{2}}|d^{q}_{X}(x,x^{\prime})-d^{q}_{Y}(y,y^{ \prime})|^{p}d\gamma^{\otimes 2}$ $\displaystyle\quad+2\lambda(|\nu|-|\gamma|)|\gamma|+\lambda(|\nu|-|\gamma|)^{2 }+2\lambda(|\mu|-|\gamma|)|\gamma|+\lambda(|\mu|-|\gamma|)^{2}$ $\displaystyle=\int_{(X\times Y)^{2}}|d^{q}_{X}(x,y^{\prime})-d^{q}_{Y}(y,y^{ \prime})|^{p}\,d\gamma^{\otimes 2})+\lambda(|\nu^{2}|+|\mu|^{2}-2|\gamma|^{2}) =C(\gamma;\lambda,\mu,\nu).$ $$

As we merged the points $\hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3}$, by [, Proposition B.1.],
the mapping $\gamma\mapsto\hat{\gamma}$ defined in (40) is a bijection.
Then, if $\gamma\in\Gamma_{\leq}(\mu,\nu)$ is optimal for the PGW problem $PGW_{\lambda,q}^{p}(\mathbb{X},\mathbb{Y})$ (defined in (10)), $\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})$ is optimal for generalized GW problem $GW_{\lambda,q}^{p}(\hat{\mathbb{X}},\hat{\mathbb{Y}})$ (defined in
(39)).
Therefore,

$$ $GW_{\lambda,q}^{p}(\hat{\mathbb{X}},\hat{\mathbb{Y}})=PGW_{\lambda,q}^{p}( \mathbb{X},\mathbb{Y}).$ $$

∎

###### Proposition D.4 (Triangle inequality for $GW_{\lambda,q}^{p}(\cdot,\cdot)$ ) .

Consider the generalized GW problem (39). Then, for any $p\in[1,\infty)$, we have

$$ $GW_{\lambda,q}^{p}(\hat{\mathbb{X}},\hat{\mathbb{Y}})\leq GW_{\lambda,q}^{p}( \hat{\mathbb{S}},\hat{\mathbb{X}})+GW_{\lambda,q}^{p}(\hat{\mathbb{S}},\hat{ \mathbb{Y}}).$ $$

###### Proof of Proposition D.4 .

We prove the case $p=2$. For general $p\geq 1$, it can be proved similarly.

Choose an optimal $\gamma^{12}\in\Gamma_{\leq}(\mu,\nu)$ for $PGW_{\lambda,q}^{2}(\mathbb{X},\mathbb{Y})$, an optimal $\gamma^{01}\in\Gamma_{\leq}(\sigma,\mu)$ for $PGW_{\lambda,q}^{2}(\mathbb{S},\mathbb{X})$, and an optimal $\gamma^{02}\in\Gamma_{\leq}(\sigma,\nu)$ for
$PGW_{\lambda,q}^{2}(\mathbb{S},\mathbb{Y})$. Construct $\hat{\gamma}^{12},\hat{\gamma}^{01},\hat{\gamma}^{02}$ by (40).

By Proposition D.3, we have that
$\hat{\gamma}^{12}$, $\hat{\gamma}^{01}$, $\hat{\gamma}^{02}$ are optimal for $GW^{2}_{\lambda,q}(\hat{\mathbb{X}},\hat{\mathbb{Y}})$, $GW^{2}_{\lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{X}})$, $GW^{2}_{\lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{Y}})$, respectively.

Define canonical projection mapping

$$ $\displaystyle\pi_{0,1}:$ $\displaystyle(\hat{S}\times\hat{X}\times\hat{Y})\to(\hat{S}\times\hat{X})$ $\displaystyle(s,x,y)\mapsto(s,x).$ $$

Similarly, we define $\pi_{0,2},\pi_{1,2}$.

By gluing lemma (see Lemma 5.5 []), there exists $\hat{\gamma}\in\mathcal{M}_{+}(\hat{S}\times\hat{X}\times\hat{Y})$, such that $(\pi_{0,1})_{\#}\hat{\gamma}=\hat{\gamma}^{01},(\pi_{0,2})_{\#}\hat{\gamma}=
\hat{\gamma}^{02}$.
Thus, $(\pi_{1,2})_{\#}\hat{\gamma}$ is a coupling between $\hat{\mu},\hat{\nu}$. We have

$$ $\displaystyle GW^{2}_{\lambda,q}(\mathbb{X},\mathbb{Y})$ $\displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}D^{2}_{\lambda}(d^{q}_{\hat{X}} (x,x^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d(\hat{\gamma}^{12})^{\otimes 2}$ $\displaystyle\leq\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_{\lambda} (d^{q}_{\hat{X}}(x,x^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d\hat{\gamma}^{ \otimes 2}.$ (43) $$

The inequality holds since $(\pi_{1,2})_{\#}\hat{\gamma},\hat{\gamma}^{12}\in\Gamma(\hat{\mu},\hat{\nu})$, and $\hat{\gamma}^{12}$ is optimal.

Next, we will show that

$$ $\displaystyle\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_{\lambda}(d^{ q}_{\hat{X}}(x,x^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d\hat{\gamma}^{ \otimes 2}$ $\displaystyle\leq\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}(D_{\lambda}(d^ {q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{X}}(x,x^{\prime}))+D_{\lambda}(d^{q}_{ \hat{S}}(s,s^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime})))^{2}d\hat{\gamma}^{ \otimes 2}.$ $$

Let $((s,x,y),(s^{\prime},x^{\prime},y^{\prime}))\in(\hat{S},\hat{X},\hat{Y})^{2}$, and assume that

$$ $\displaystyle D_{\lambda}(d_{\hat{X}}^{2}(x,x^{\prime}),d_{\hat{Y}}^{2}(y,y^{ \prime}))>D_{\lambda}(d_{\hat{S}}^{2}(s,s^{\prime}),d_{\hat{X}}^{2}(x,x^{ \prime}))+D_{\lambda}(d_{\hat{S}}^{2}(s,s^{\prime}),d_{\hat{Y}}^{2}(y,y^{ \prime})).$ (44) $$

By Lemma D.2, (44) implies $d_{\hat{X}}(x,x^{\prime}),d_{\hat{Y}}(y,y^{\prime})\in\mathbb{R},d_{\hat{S}}(s
,s^{\prime})=\infty$.
Thus,
by definition (36), it also implies

$$ $(x,x^{\prime})\in X^{2},(y,y^{\prime})\in Y^{2},(s,s^{\prime})\in\hat{S}^{2} \setminus S^{2}.$ (45) $$

Define the following sets:

$$ $\displaystyle A_{\alpha}$ $\displaystyle=\hat{S}\times X\times Y,$ $\displaystyle A_{0}$ $\displaystyle=\{\hat{\infty}_{0}\}\times X\times Y,$ $\displaystyle A_{1}$ $\displaystyle=\{\hat{\infty}_{1}\}\times X\times Y,$ $\displaystyle A_{2}$ $\displaystyle=\{\hat{\infty}_{2}\}\times X\times Y.$ $$

Notice that, (44)
$\Longrightarrow$ (45) is equivalent to

$$ $\eqref{pf:tri_inq_violate}\Longrightarrow((s,x,y),(s,x^{\prime},y^{\prime})) \in A:=\bigcup_{i=0}^{2}(A_{i}\times A_{\alpha})\cup\bigcup_{i=0}^{2}(A_{ \alpha}\times A_{i}).$ (46) $$

Next, we will show $\hat{\gamma}^{\otimes 2}(A)=0$. Indeed,

$$ $\displaystyle\hat{\gamma}(A_{0})\leq\hat{\gamma}(\{\infty_{0}\}\times\hat{X} \times\hat{Y})=\hat{\sigma}(\{\infty_{0}\})=0\qquad\text{by definition \eqref{ pf:sigma_hat,mu_hat,nu_hat} of $\hat{\sigma}$ , }$ $\displaystyle\hat{\gamma}(A_{1})\leq\hat{\gamma}(\{\infty_{1}\}\times\hat{X} \times Y)=\hat{\gamma}^{02}(\{\hat{\infty}_{1}\times Y\})=0\qquad\text{by } \eqref{pf:gamma02_cond},$ $\displaystyle\hat{\gamma}(A_{2})\leq\hat{\gamma}(\{\infty_{2}\}\times X\times \hat{Y})=\hat{\gamma}^{01}(\{\hat{\infty}_{2}\times X\})=0\qquad\text{by } \eqref{pf:gamma01_cond}.$ $$

Thus, $\hat{\gamma}^{\otimes 2}(A)=0$. By considering
$B=(\hat{S}\times\hat{X}\times{Y})^{2}\setminus A,$
we obtain

$$ $\displaystyle\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D_{\lambda}^{2}(d^{ q}_{\hat{X}}(x,x^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d\gamma^{\otimes 2}$ $\displaystyle=\int_{B}D_{\lambda}^{2}(d^{q}_{\hat{X}}(x,x^{\prime}),d^{q}_{ \hat{Y}}(y,y^{\prime}))d\gamma^{\otimes 2}\qquad\text{since }\gamma^{\otimes 2 }(A)=0$ $\displaystyle\leq\int_{B}\left(D_{\lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q} _{\hat{X}}(x,x^{\prime})+D_{\lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat {Y}}(y,y^{\prime}))\right)^{2}d\gamma^{\otimes 2}\qquad\text{by }\eqref{pf:set _A}$ $\displaystyle\leq\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}\left(D_{ \lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{X}}(x,x^{\prime})+D_{ \lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))\right)^{ 2}d\gamma^{\otimes 2}.$ (47) $$

Following (43) and (47), we have

$$ $\displaystyle GW^{2}_{\lambda,q}(\hat{\mathbb{X}},\hat{\mathbb{Y}})\leq\left( \int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_{\lambda}(d^{q}_{\hat{X}}( x,x^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d\hat{\gamma}^{\otimes 2}\right)^{ 1/2}$ $\displaystyle\leq\left(\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}\left(D_{ \lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{X}}(x,x^{\prime}))+D_{ \lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))\right)^{ 2}d\gamma^{\otimes 2}\right)^{1/2}$ $\displaystyle\leq\left(\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_{ \lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{X}}(x,x^{\prime}))d\gamma^{ \otimes 2}\right)^{1/2}$ $\displaystyle\qquad+\left(\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_ {\lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d\gamma^ {\otimes 2}\right)^{1/2}$ (48) $\displaystyle=\left(\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_{ \lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{X}}(x,x^{\prime}))d(\gamma^ {01})^{\otimes 2}\right)^{1/2}$ $\displaystyle\qquad+\left(\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}D^{2}_ {\lambda}(d^{q}_{\hat{S}}(s,s^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))d(\gamma ^{02})^{\otimes 2}\right)^{1/2}$ $\displaystyle=GW^{2}_{\lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{X}})+GW^{2}_{ \lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{Y}}),$ $$

where in the third inequality (48) we used the Minkowski inequality in $L^{2}((\hat{S}\times\hat{X}\times\hat{Y})^{2},\hat{\gamma}^{\otimes 2})$.
∎

Now, we can complete the proof of Proposition 3.4:
By the Propositions D.3, we have

$$ $PGW^{p}_{\lambda,q}(\mathbb{X},\mathbb{Y})=GW^{p}_{\lambda,q}(\hat{\mathbb{X}} ,\hat{\mathbb{Y}})$ $$

and similarly for $PGW^{p}_{\lambda,q}$ and $(\mathbb{S},\mathbb{X}),PGW^{p}_{\lambda,q}(\mathbb{S},\mathbb{Y})$.
By the Proposition D.4, $GW^{p}_{\lambda,q}(\cdot,\cdot)$ satisfies the triangle inequality, thus
we complete the proof:

$$ $\displaystyle PGW^{p}_{\lambda,q}(\mathbb{X},\mathbb{Y})$ $\displaystyle=GW^{p}_{\lambda,q}(\hat{\mathbb{X}},\hat{\mathbb{Y}})$ $\displaystyle\leq GW^{p}_{\lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{X}})+GW^{p} _{\lambda,q}(\hat{\mathbb{S}},\hat{\mathbb{Y}})$ $\displaystyle=PGW^{p}_{\lambda,q}(\mathbb{S},\mathbb{X})+PGW^{p}_{\lambda,q}( \mathbb{S},\mathbb{Y}).$ $$

###### Lemma D.2 .

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

###### Proposition D.3 .

###### Proof of Proposition D.3 .

###### Proposition D.4 (Triangle inequality for G ⁢ W λ , q p ⁢ ( ⋅ , ⋅ ) 𝐺 superscript subscript 𝑊 𝜆 𝑞 𝑝 ⋅ ⋅ GW_{\lambda,q}^{p}(\cdot,\cdot) italic_G italic_W start_POSTSUBSCRIPT italic_λ , italic_q end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_p end_POSTSUPERSCRIPT ( ⋅ , ⋅ ) ) .

###### Proof of Proposition D.4 .

## Appendix E Proof of Proposition 3.5 : PGW converges to GW as λ → ∞ → 𝜆 \lambda\to\infty italic_λ → ∞ .

In the main text, we set $\lambda\in\mathbb{R}$. In this section, we discuss the limit case that when $\lambda\to\infty$.

###### Lemma E.1 .

Suppose $|\mu|\leq|\nu|$, for each $\gamma\in\Gamma_{\leq}(\mu,\nu)$, there exists $\gamma^{\prime}\in\Gamma_{\leq}(\mu,\nu)$ such that $\gamma\leq\gamma^{\prime}$ and $(\pi_{1})_{\#}\gamma^{\prime}=\mu$.

###### Proof.

Let $\gamma\in\Gamma_{\leq}(\mu,\nu)$.

If $|\gamma|=|\mu|$, then we have $(\pi_{1})_{\#}\gamma=\mu$.

If $|\gamma|<|\mu|$, let $\mu^{r}=\mu-(\pi_{1})_{\#}\gamma,\nu^{r}=\nu-(\pi_{2})_{\#}\gamma$. We have that $\mu^{r},\nu^{r}$ are non-negative measures, with $|\mu^{r}|=|\mu|-|\gamma|>0$.
If we define

$$ $\gamma^{\prime}:=\gamma+\frac{1}{|\nu|-|\gamma|}\mu^{r}\otimes\nu^{r},$ $$

we obtain $\gamma\leq\gamma^{\prime}$.
In addition, we have:

$$ $\displaystyle(\pi_{1})_{\#}\gamma^{\prime}$ $\displaystyle=(\pi_{1})_{\#}\gamma+\mu^{r}\frac{|\nu^{r}|}{|\nu|-|\gamma|}=( \pi_{1})_{\#}\gamma+\mu^{r}=\mu,$ $\displaystyle(\pi_{2})_{\#}\gamma^{\prime}$ $\displaystyle=(\pi_{2})_{\#}\gamma+\nu^{r}\frac{|\mu^{r}|}{|\nu|-|\gamma|}\leq (\pi_{2})_{\#}\gamma+\nu^{r}\frac{|\nu^{r}|}{|\nu|-|\gamma|}=\nu.$ $$

Thus, $\gamma^{\prime}\in\Gamma_{\leq}(\mu,\nu)$ and $(\pi_{1})_{\#}\gamma^{\prime}=\mu$.
∎

###### Lemma E.2 .

Given general mm-spaces $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$, where $\mu,\nu$ are supported on bounded sets (in general, it is assumed that $X$ and $Y$ are compact, and that $\text{supp}(\mu)=X$, $\text{supp}(\nu)=Y$), consider the problem the problem $PGW^{L}_{\lambda,q}(\mathbb{X},\mathbb{Y})$
with $L(r_{1},r_{2})$ a continuous functions. If $\lambda$ is sufficiently large, in particular:

$$ $\lambda\geq\max_{\begin{subarray}{c}x,x^{\prime}\in\text{supp}(\mu)\\ y,y^{\prime}\in\text{supp}(\nu)\end{subarray}}L(d_{X}(x,x^{\prime}),d_{Y}(y,y^ {\prime})),$ $$

then there exists optimal $\gamma$ for $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ such that $|\gamma|=\min(|\mu|,|\nu|)$.

Furthermore, when

$$ $\lambda>\max_{\begin{subarray}{c}x,x^{\prime}\in\text{supp}(\mu)\\ y,y^{\prime}\in\text{supp}(\nu)\end{subarray}}L(d_{X}(x,x^{\prime}),d_{Y}(y,y^ {\prime})),$ $$

the for all optimal $\gamma\in\Gamma_{\leq}(\mu,\nu)$, we have $|\gamma|=\min(|\mu|,|\nu|)$.

###### Proof.

We prove it for $q=1$, for a general $q\geq 1$, it can be proved similarly.

Without loss of generality, suppose $|\mu|\leq|\nu|$.

Since $\mu,\nu$ are supported on bounded sets, there exists $A=[0,M]$ such that $d_{X}(x,x^{\prime}),d_{Y}(y,y^{\prime})\in A$ for all $x,x^{\prime}\in\text{supp}(\mu),y,y^{\prime}\in\text{supp}(\nu)$.

Thus, the restriction of $L$ on $A^{2}$, denoted as $L_{A^{2}}$, is continuous on $A^{2}$, and thus it is bounded.
So, consider

$$ $\mathrm{m}:=\max_{r_{1},r_{2}\in A}(L(r_{1},r_{2}))\geq L(d_{X}(x,x^{\prime}), d_{Y}(y,y^{\prime})),\quad\forall x,x^{\prime}\in\text{supp}(\mu),y,y^{\prime} \in\text{supp}(\nu).$ $$

Suppose $2\lambda\geq\mathrm{m}+1$, and assume that there exists a optimal $\gamma\in\Gamma_{\leq}(\mu,\nu)$ such that $|\gamma|<|\mu|$. By Lemma E.1, there exists $\gamma^{\prime}$ such that $\gamma\leq\gamma^{\prime},(\pi_{1})_{\#}\gamma^{\prime}=\mu$. Thus, we have

$$ $\displaystyle C(\gamma^{\prime};\lambda,\mu,\nu)-C(\gamma;\lambda,\mu,\nu)$ $\displaystyle=\int_{(X\times Y)}L(d_{X}(x,x^{\prime}),d_{Y}(y,y^{\prime}))-2 \lambda\,d((\gamma^{\prime})^{\otimes 2}-(\gamma)^{\otimes 2})$ $\displaystyle\leq\int_{(X\times Y)}\mathrm{m}-2\lambda\,d((\gamma^{\prime})^{ \otimes 2}-(\gamma)^{\otimes 2})$ $\displaystyle=-(|\gamma^{\prime}|^{2}-|\gamma|^{2})=-(|\mu|^{2}-|\gamma|^{2})<0,$ $$

which is contradiction since $\gamma$ is optimal, and so we have completed the proof.
∎

###### Lemma E.3 .

Consider probability mm-spaces $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$, that is, with $|\mu|=|\nu|=1$. Then, for each $\lambda>0$, we have

$$ $\displaystyle PGW_{\lambda,q}^{L}(\mathbb{X},\mathbb{Y})\leq GW^{L}_{q}( \mathbb{X},\mathbb{Y}).$ $$

###### Proof.

In this setting, we have $\Gamma(\mu,\nu)\subset\Gamma_{\leq}(\mu,\nu)$, and thus

$$ $\displaystyle PGW^{L}_{\lambda,q}(\mathbb{X},\mathbb{Y})$ $\displaystyle=\inf_{\Gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{(X\times Y)^{2}}L(d_ {X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{\prime}))d\gamma^{\otimes 2}+\lambda(|\mu |^{2}+|\nu|^{2}-2|\gamma|^{2})$ $\displaystyle\leq\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{(X\times Y)^{2}}L(d_{X}^ {q}(x,x^{\prime}),d_{Y}^{q}(y,y^{\prime}))+\lambda(|\mu|^{2}+|\nu|^{2}-2| \gamma|^{2})d\gamma^{\otimes 2}$ $\displaystyle=\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{(X\times Y)^{2}}L(d_{X}^{q} (x,x^{\prime}),d_{Y}^{q}(y,y^{\prime}))d\gamma^{\otimes 2}$ $\displaystyle=GW^{L}_{q}(\mathbb{X},\mathbb{Y}).$ $$

∎

Based on the above properties, we can now prove Proposition 3.5:

###### Proposition E.4 (Generalization of Proposition 3.5 ) .

Consider general probability mm-spaces $\mathbb{X}=(X,d_{X},\mu)$, $\mathbb{Y}=(Y,d_{Y},\nu)$, that is, with $|\mu|=|\nu|=1$, where $X,Y$ are bounded. Assume that $L$ is continuous.
Then

$$ $\lim_{\lambda\to\infty}PGW_{\lambda,q}^{L}(\mathbb{X},\mathbb{Y})=GW^{L}_{q}( \mathbb{X},\mathbb{Y}).$ $$

###### Proof.

When $\lambda$ is sufficiently large, by Lemma E.2, for each optimal $\gamma_{\lambda}\in\Gamma_{\leq}(\mu,\nu)$ of the minimization problem $PGW^{L}_{\lambda,q}(\mathbb{X},\mathbb{Y})$, we have $|\gamma_{\lambda}|=\min(|\mu|,|\nu|)=1$. That is, $\gamma_{\lambda}\in\Gamma(\mu,\nu)$. Plugging $\gamma_{\lambda}$ into $C(\gamma_{\lambda};\lambda,\mu,\nu)$, we obtain:

$$ $\displaystyle PGW^{L}_{\lambda,q}(\mathbb{X},\mathbb{Y})$ $\displaystyle=\int_{(X\times Y)^{2}}L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{ \prime}))d\gamma_{\lambda}^{\otimes 2}+\lambda(1^{2}+1^{2}-2\cdot 1^{2})$ $\displaystyle=\int_{(X\times Y)^{2}}L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{ \prime}))d\gamma_{\lambda}^{\otimes 2}\geq GW(\mathbb{X},\mathbb{Y}).$ $$

By Lemma E.3, we also have
$PGW^{L}_{\lambda,q}(\mathbb{X},\mathbb{Y})\leq GW^{L}_{q}(\mathbb{X},\mathbb{Y})$ and we complete the proof.
∎

###### Lemma E.1 .

###### Proof.

###### Lemma E.2 .

###### Proof.

###### Lemma E.3 .

###### Proof.

###### Proposition E.4 (Generalization of Proposition 3.5 ) .

###### Proof.

## Appendix F Tensor Product Computation

###### Lemma F.1 .

Given a tensor $M\in\mathbb{R}^{n\times m\times n\times n}$ and $\gamma,\gamma^{\prime}\in\mathbb{R}^{n\times m}$, the tensor product operator
$M\circ\gamma$ satisfies the following:

- (i)
The mapping $\gamma\mapsto M\circ\gamma$ is linear with respect to $\gamma$.
- (ii)
If $M$ is symmetric, in particular, $M_{i,j,i^{\prime},j^{\prime}}=M_{i^{\prime},j^{\prime},i,j},\forall i,i^{
\prime}\in[1:n],j,j^{\prime}\in[1:m]$, then
$\langle M\circ\gamma,\gamma^{\prime}\rangle_{F}=\langle M\circ\gamma^{\prime},
\gamma\rangle_{F}.$

###### Proof.

- (i)
For the first part, consider $\gamma,\gamma^{\prime}\in\mathbb{R}^{n\times m}$ and $k\in\mathbb{R}$.
For each $i,j\in[1:n]\times[1:m]$, we have
we have
$\displaystyle(M\circ(\gamma+\gamma^{\prime}))_{ij}$
$\displaystyle=\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}(\gamma
+\gamma^{\prime})_{i^{\prime}j^{\prime}}$
$\displaystyle=\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}\gamma_
{i^{\prime}j^{\prime}}+\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime
}}\gamma^{\prime}_{i^{\prime}j^{\prime}}$
$\displaystyle=(M\circ\gamma)_{ij}+(M\circ\gamma)_{i^{\prime}j^{\prime}},$
$\displaystyle(M\circ(k\gamma))_{ij}$
$\displaystyle=\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}(k
\gamma)_{ij}$
$\displaystyle=k\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}\gamma
_{ij}$
$\displaystyle=k(M\circ\gamma)_{ij}.$
Thus, $M\circ(\gamma+\gamma^{\prime})=M\circ\gamma+M\circ\gamma^{\prime}$ and $M\circ(k\gamma)=kM\circ\gamma$. Therefore, $\gamma\mapsto M\circ\gamma$ is linear.
- (ii)
For the second part, we have
$\displaystyle\langle M\circ\gamma,\gamma^{\prime}\rangle_{F}$
$\displaystyle=\sum_{iji^{\prime}j^{\prime}}M_{i,j,i^{\prime},j^{\prime},}
\gamma_{ij}\gamma^{\prime}_{i^{\prime}j^{\prime}}$
$\displaystyle=\sum_{i,j,i^{\prime},j^{\prime}}M_{i^{\prime},j^{\prime},i,j}
\gamma_{i^{\prime},j^{\prime}}\gamma_{i,j}$
(49)
$\displaystyle=\langle M\gamma^{\prime},\gamma\rangle$
where (49) follows from the fact that $M$ is symmetric.

∎

###### Lemma F.1 .

###### Proof.

## Appendix G Another Algorithm for Computing PGW Distance – Solver 2

Our Algorithm 2 for solving the proposed PGW problem is based on a theoretical result that relates GW and PGW. The details of our computational method, as well as the proof of Proposition G.1 stated below, are provided in Appendix G.1. Based on such proposition, we
extend the PGW problem to a discrete GW-variant problem (55), leading to a solution for the original PGW problem by truncating the GW-variant solution.

###### Proposition G.1 .

Let $\mathbb{X}=(X,d_{X},\mu)$ be a mm-space.
Consider an auxiliary point $\hat{\infty}$ and let $\hat{\mathbb{X}}=(\hat{X},d_{\hat{X}},\hat{\mu})$, where $\hat{X}=X\cup\{\hat{\infty}\}$, $\hat{\mu}$ is constructed by (4), and considering $\infty$ as an auxiliary point to $\mathbb{R}$ such that $x\leq\infty$ for every $x\in\mathbb{R}$, we extend $d_{X}$ into $d_{\hat{X}}:\hat{X}^{2}\to\mathbb{R}\cup\{\infty\}$ and define $L_{\lambda}:\mathbb{R}\cup\{\infty\}\to\mathbb{R}$ as follows:

$$ $\displaystyle d_{\hat{X}}(x,x^{\prime})=\begin{cases}d_{X}(x,x^{\prime})&\text { if }x,x^{\prime}\in X\\ \infty&\text{ otherwise}\end{cases},L_{\lambda}(r_{1},r_{2}):=\begin{cases}L(r _{1},r_{2})-2\lambda&\text{ if }r_{1},r_{2}\in\mathbb{R}\\ 0&\text{ elsewhere}\end{cases}.$ (50) $$

Consider the following GW-variant(^*^**$\widehat{GW}^{L_{\lambda}}(\hat{\mathbb{X}},\hat{\mathbb{Y}})$ is not a rigorous GW problem since $d_{\hat{X}}=\infty$ is possible, thus it is not a metric. Also, $\mathbb{X}$, $\mathbb{Y}$ are not necessarily probability mm-spaces) problem:

$$ $\displaystyle\widehat{GW}^{L_{\lambda}}(\hat{\mathbb{X}},\hat{\mathbb{Y}})= \inf_{\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})}$ $\displaystyle\hat{\gamma}^{\otimes 2}(L_{\lambda}(d_{\hat{X}}^{q},d_{\hat{Y}}^ {q}))$ (51) $$

Then, when considering the bijection $\gamma\mapsto\hat{\gamma}$ defined in (6) we have that $\gamma$ is optimal for PGW problem (10) if and only if $\hat{\gamma}$ is optimal for the GW-variant problem (51).

###### Remark G.2 .

Intuitively, the above proposition states that, by introducing auxiliary points $\hat{\infty}$, we can build an equivalent relation between PGW and GW problem. This idea is firstly discussed in [] in classical optimal partial transport setting. In this paper, we extend the technique to the partial GW setting. However, this technique cannot be extended to the MPGW setting; we refer to [, Appendix A.3] for details.

###### Proof.

The mapping $F$ defined by (6) well-defined bijection, as shown in[, ].

Given $\gamma\in\Gamma_{\leq}(\mu,\nu)$, we have $\hat{\gamma}=F(\gamma)\in\Gamma(\hat{\mu},\hat{\nu})$.
Let $\hat{C}(\hat{\gamma};\mu,\nu)$ denote the transportation cost in the GW-variant problem (51), that is,

$$ $\displaystyle\hat{C}(\hat{\gamma};\mu,\nu):=\int_{(\hat{X}\times\hat{Y})^{2}}L _{\lambda}(d^{q}_{\hat{X}}(x,x^{\prime}),d^{q}_{\hat{Y}}(y,y^{\prime}))\,d\hat {\gamma}(x,y)d\hat{\gamma}(x^{\prime},y^{\prime})$ $$

Then, we have

$$ $\displaystyle C(\gamma;\lambda,\mu,\nu)$ $\displaystyle=\int_{(X\times Y)^{2}}(L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{ \prime}))-2\lambda)\,d\gamma^{\otimes 2}+\underbrace{\lambda(|\mu|+|\nu|)}_{ \text{does not depend on $\gamma$}}$ $\displaystyle=\int_{(X\times Y)^{2}}(L(d_{X}^{q}(x,x^{\prime}),d_{Y}^{q}(y,y^{ \prime}))-2\lambda)\,d\hat{\gamma}^{\otimes 2}+{\lambda(|\mu|+|\nu|)}\qquad( \text{since }\hat{\gamma}|_{X\times Y}=\gamma)$ $\displaystyle=\int_{(X\times Y)^{2}}(L(d_{\hat{X}}^{q}(x,x^{\prime}),d_{\hat{Y }}^{q}(y,y^{\prime}))-2\lambda)\,d\hat{\gamma}^{\otimes 2}+\lambda(|\mu|+|\nu| )\quad(\text{as }d_{\hat{X}}|_{X\times X}=d_{X},\,d_{\hat{Y}}|_{Y\times Y}=d_{ Y})$ $\displaystyle=\int_{(X\times Y)^{2}}L_{\lambda}(d_{\hat{X}}^{q}(x,x^{\prime}), d_{\hat{Y}}^{q}(y,y^{\prime}))\,d\hat{\gamma}^{\otimes 2}+\lambda(|\mu|+|\nu|) \quad(\text{since }\hat{L}|_{\mathbb{R}\times\mathbb{R}}(\cdot,\cdot)=(L(\cdot ,\cdot)-2\lambda))$ $\displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}L_{\lambda}(d_{\hat{X}}^{q}(x,x ^{\prime}),d_{\hat{Y}}^{q}(y,y^{\prime}))\,d\hat{\gamma}^{\otimes 2}+ \underbrace{\lambda(|\mu|+|\nu|)}_{\text{does not depend on }\hat{\gamma}}. \quad(\text{since }\hat{L}\text{ assigns }0\text{ to }\hat{\infty})$ $$

Combining this with the fact that $F:\gamma\mapsto\hat{\gamma}$ is a bijection, we have that $\gamma$ is optimal for (10) if and only if $\hat{\gamma}$ is optimal for (51).
Under the assumptions of Proposition 3.3, there exists an optimal $\gamma\in\Gamma_{\leq}(\mu,\nu)$ for the PGW problem exists, and so
we have:

$$ $\arg\min_{\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})}\hat{C}(\hat{\gamma};\mu, \nu)=\arg\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}C(\gamma;\lambda,\mu,\nu).$ (52) $$

∎

###### Remark G.3 .

Both algorithms (Algorithm 1, and 2) are mathematically and computationally equivalent, owing to the equivalence between the POT problem in Solver 1 and the OT problem in Solver 2.

###### Proposition G.1 .

###### Remark G.2 .

###### Proof.

###### Remark G.3 .

### G.1 Frank-Wolfe for the PGW Problem – Solver 2

Similarly to the discrete PGW problem (15), consider the discrete version of (4):

$$ $\hat{\mathrm{p}}=[\mathrm{p};|\mathrm{q}|]\in\mathbb{R}^{n+1},\quad\hat{ \mathrm{q}}=[\mathrm{q};|\mathrm{p}|]\in\mathbb{R}^{m+1},$ (53) $$

and, in a similar fashion, we define $\hat{M}\in\mathbb{R}^{(n+1)\times(m+1)\times(n+1)\times(m+1)}$ as

$$ $\displaystyle\hat{M}_{i,j,i^{\prime},j^{\prime}}=\begin{cases}\tilde{M}_{i,j,i ^{\prime},j^{\prime}}&\text{if }i,i^{\prime}\in[1:n],j,j^{\prime}\in[1:m],\\ 0&\text{elsewhere}.\end{cases}$ (54) $$

Then, the GW-variant problem (51) can be written as

$$ $\displaystyle\widehat{GW}(\hat{\mathbb{X}},\hat{\mathbb{Y}})=\min_{\hat{\gamma }\in\Gamma(\hat{\mathrm{p}},\hat{\mathrm{q}})}\mathcal{L}_{\hat{M}}(\hat{ \gamma}).$ (55) $$

Based on Proposition G.1 (which relates $PGW_{\lambda}^{L}(\cdot,\cdot)$ with $\widehat{GW}(\cdot,\cdot)$),
we propose two versions of the Frank-Wolfe algorithm [] that can solve the PGW problem (15). Apart from Algorithm 1 in [], which solves a different formulation of partial GW, and Algorithm 1 in [], which applies the Sinkhorn algorithm to solve an entropic regularized version of (8), to the best of our knowledge, a precise computational method for the discrete PGW problem (15) has not been studied.

Here, we discuss another version of the FW Algorithm for solving the PGW problem (15).
The main idea relies on solving first the GW-variant problem (51), and, at the end of the iterations, by using Proposition G.1, convert the solution of the GW-variant problem to a solution for the original partial GW problem (15).

First, construct $\hat{\mathrm{p}},\hat{\mathrm{q}},\hat{\mathrm{M}}$ as described in Proposition G.1. Then, for each iteration $k$, perform the following three steps.

Step 1: Computation of gradient and optimal direction.
Solve the OT problem:

$$ $\displaystyle\hat{\gamma}^{(k)^{\prime}}$ $\displaystyle\leftarrow\arg\min_{\hat{\gamma}\in\Gamma(\hat{\mathrm{p}},\hat{ \mathrm{q}})}\langle\mathcal{L}_{\hat{M}}(\hat{\gamma}^{(k)}),\hat{\gamma} \rangle_{F}.$ $$

The gradient $\mathcal{L}_{\hat{M}}(\gamma^{(k)})$ can be computed in a similar way as described in Lemma H.2. We refer to Section H for details.

Step 2: Line search method.
Find optimal step size $\alpha^{(k)}$:

$$ $\alpha^{(k)}=\arg\min_{\alpha\in[0,1]}\{\mathcal{L}_{\hat{M}}((1-\alpha)\hat{ \gamma}^{(k)}+\alpha\hat{\gamma}^{(k)^{\prime}})\}.$ $$

Similar to Solver 1, let

$$ $\displaystyle\begin{cases}&\delta\hat{\gamma}^{(k)}=\hat{\gamma}^{(k)^{\prime} }-\hat{\gamma}^{(k)},\\ &a=\langle\hat{M}\circ\delta\hat{\gamma}^{(k)},\delta\hat{\gamma}^{(k)}\rangle _{F},\\ &b=2\langle\hat{M}\circ\delta\hat{\gamma}^{(k)},\hat{\gamma}^{(k)}\rangle_{F}. \end{cases}$ (56) $$

Then the optimal $\alpha^{(k)}$ is given by formula (18).
See Appendix J for a detailed discussion.

Step 3. Update $\hat{\gamma}^{(k+1)}\leftarrow(1-\alpha^{(k)})\hat{\gamma}^{(k)}+\alpha^{(k)}
\hat{\gamma}^{(k)^{\prime}}$.

Figure: Algorithm 2 Frank-Wolfe Algorithm for partial GW, ver 2

## Appendix H Gradient Computation in Algorithms 1 and 2

In this section, we discuss the computation of Gradient $\nabla\mathcal{L}_{\tilde{M}}(\gamma)$ in Algorithm 1 and $\nabla\mathcal{L}_{\hat{M}}(\hat{\gamma})$ in Algorithm 2.

###### Proposition H.1 (Proposition 1 [ 47 ] ) .

If the cost function can be written as

$$ $L(r_{1},r_{2})=f_{1}(r_{1})+f_{2}(r_{2})-h_{1}(r_{1})h_{2}(r_{2})$ (57) $$

then

$$ $M\circ\gamma=u(C^{X},C^{Y},\gamma)-h_{1}(C^{X})\gamma h_{2}(C^{Y})^{\top},$ (58) $$

where $u(C^{X},C^{Y},\gamma):=f_{1}(C^{X})\gamma_{1}1_{m}^{\top}+1_{n}\gamma_{2}^{
\top}f_{2}(C^{Y})$.

Additionally, the following lemma builds the connection between $\tilde{M}\circ\gamma$ and $M\circ\gamma$.

###### Lemma H.2 .

For any $\gamma\in\mathbb{R}^{n\times m}$, we have:

$$ $\tilde{M}\circ\gamma=M\circ\gamma-2\lambda|\gamma|1_{n,m}.$ (59) $$

###### Proof.

For any $\gamma\in\mathbb{R}^{n\times m}$, we have

$$ $\displaystyle\tilde{M}\circ\gamma$ $\displaystyle=(M1_{n,n,m,m}-2\lambda)\circ\gamma$ $\displaystyle=(M-2\lambda 1_{n,n,m,m})\circ\gamma$ $\displaystyle=M\circ\gamma-2\lambda 1_{n,m,n,m}\circ\gamma$ $\displaystyle=M\circ\gamma-2(\langle 1_{n,m},\gamma\rangle_{F})1_{n,m}$ $\displaystyle=M\circ\gamma-2\lambda|\gamma|1_{n,m}$ $$

where the second equality follows from Lemma F.1.
∎

Next, in the setting of Algorithm 2, for any $\hat{\gamma}\in\mathbb{R}^{(n+1)\times(m+1)}$, we have

$$ $\displaystyle\nabla\mathcal{L}_{\hat{M}}(\hat{\gamma})=2\hat{M}\circ\hat{\gamma}$ (60) $$

and $\hat{M}\circ\hat{\gamma}$ can be computed by the following lemma.

###### Lemma H.3 .

For each $\hat{\gamma}\in\mathbb{R}^{(n+1)\times(m+1)}$, we have
$\hat{M}\circ\hat{\gamma}\in\mathbb{R}^{(n+1)\times(m+1)}$ with the following:

$$ $\displaystyle(\hat{M}\circ\hat{\gamma})_{ij}=\begin{cases}(\tilde{M}\circ\hat{ \gamma}[1:n,1:m])_{ij}&\text{if }i\in[1:n],j\in[1:m]\\ 0&\text{elsewhere}\end{cases}.$ (61) $$

###### Proof.

Recall the definition of $\hat{M}$ is given by (54), choose $i\in[1:n],j\in[1:m]$, we have

$$ $\displaystyle(\hat{M}\circ\hat{\gamma})_{ij}$ $\displaystyle=\sum_{i^{\prime}=1}^{n}\sum_{j^{\prime}=1}^{m}\hat{M}_{i,j,i^{ \prime},j^{\prime}}\hat{\gamma}_{i^{\prime},j^{\prime}}+\sum_{j^{\prime}=1}^{m }\hat{M}_{i,j,n+1,j}\hat{\gamma}_{n+1,j^{\prime}}+\sum_{i^{\prime}=1}^{n}\hat{ M}_{i,j,i^{\prime},m+1}\hat{\gamma}_{i,m+1}$ $\displaystyle\qquad+\hat{M}_{i,j,n+1,m+1}\hat{\gamma}_{n+1,m+1}$ $\displaystyle=\sum_{i^{\prime}=1}^{n}\sum_{j^{\prime}=1}^{m}\hat{M}_{i,j,i^{ \prime},j^{\prime}}\hat{\gamma}_{i^{\prime},j^{\prime}}+0+0+0=\sum_{i^{\prime} =1}^{n}\sum_{j^{\prime}=1}^{m}\tilde{M}_{i,j,i^{\prime},j^{\prime}}\hat{\gamma }_{i^{\prime},j^{\prime}}$ $\displaystyle=(\tilde{M}\circ(\hat{\gamma}[1:n,1:m]))_{ij}$ $$

If $i=n+1$, we have

$$ $(\hat{M}\circ\hat{\gamma})_{n+1,j}=\sum_{i^{\prime}=1}^{n+1}\sum_{j^{\prime}=1 }^{m+1}\hat{M}_{n+1,j,i^{\prime},j^{\prime}}\hat{\gamma}_{i^{\prime},j^{\prime }}=0$ $$

Similarly, $(\hat{M}\circ\hat{\gamma})_{i,m+1}=0$.
Thus, we complete the proof.
∎

###### Proposition H.1 (Proposition 1 [ 47 ] ) .

###### Lemma H.2 .

###### Proof.

###### Lemma H.3 .

###### Proof.

## Appendix I Line Search in Algorithm 1

In this section, we discuss the derivation of the line search algorithm.

We observe that in the partial GW setting, for each $\gamma\in\Gamma_{\leq}(\mu,\nu)$, the marginals of $\gamma$ are not fixed. Thus, we can not directly apply the classical algorithm (e.g. []).

In iteration $k$, let $\gamma^{(k)},\gamma^{(k)^{\prime}}$ be the previous and new transportation plans from step 1 of the algorithm. For convenience, we denote them as $\gamma$, $\gamma^{\prime}$, respectively.

The goal is to solve the following problem:

$$ $\displaystyle\min_{\alpha\in[0,1]}\mathcal{L}(\tilde{M},(1-\alpha)\gamma+ \alpha\gamma^{\prime})$ (62) $$

where
$\mathcal{L}(\tilde{M},\gamma)=\langle\tilde{M}\circ\gamma,\gamma\rangle_{F}$. By denoting
$\delta\gamma=\gamma^{\prime}-\gamma$, we have

$$ $\mathcal{L}(\tilde{M},(1-\alpha)\gamma+\alpha\gamma^{\prime})=\mathcal{L}( \tilde{M},\gamma+\alpha\delta\gamma).$ $$

Then,

$$ $\displaystyle\langle\tilde{M}\circ(\gamma+\alpha\delta\gamma),(\gamma+\alpha \delta\gamma)\rangle_{F}$ $\displaystyle=\langle\tilde{M}\circ\gamma,\gamma\rangle_{F}+\alpha\left( \langle\tilde{M}\circ\gamma,\delta\gamma\rangle_{F}+\langle\tilde{M}\circ \delta\gamma,\gamma\rangle_{F}\right)+\alpha^{2}\langle\tilde{M}\circ\delta \gamma,\delta\gamma\rangle_{F}$ $$

Let

$$ $\displaystyle a=$ $\displaystyle\langle\tilde{M}\circ\delta\gamma,\delta\gamma\rangle_{F},$ $\displaystyle b=$ $\displaystyle\langle\tilde{M}\circ\gamma,\delta\gamma\rangle_{F}+\langle\tilde {M}\circ\delta\gamma,\gamma\rangle_{F}=2\langle\tilde{M}\circ\gamma,\delta \gamma\rangle_{F},$ (63) $\displaystyle c=$ $\displaystyle\langle\tilde{M}\circ\gamma,\gamma\rangle_{F},$ $$

where the second identity in (63) follows from Lemma F.1 and the fact that $\tilde{M}=M1_{n,n,m,m}-2\lambda 1_{n,m,n,m}$ is symmetric.

Therefore, the above problem (62) becomes

$$ $\min_{\alpha\in[0,1]}a\alpha^{2}+b\alpha+c.$ $$

The solution is the following:

$$ $\displaystyle\alpha^{*}=\begin{cases}1&\text{if }a\leq 0,a+b\leq 0,\\ 0&\text{if }a\leq 0,a+b>0,\\ \text{clip}(\frac{-b}{2a},[0,1])&\text{if }a>0,\end{cases}$ (64) $$

where

$$ $\text{clip}(\frac{-b}{2a},[0,1])=\min\left\{1,\max\{0,\frac{-b}{2a}\}\right\}= \begin{cases}\frac{-b}{2a}&\text{if }\frac{-b}{2a}\in[0,1],\\ 0&\text{if }\frac{-b}{2a}<0,\\ 1&\text{if }\frac{-b}{2a}>1.\end{cases}$ $$

We can further discuss the difference in computation of $a$ and $b$ in PGW setting and the classical GW setting.
If the assumption in Proposition H.1 holds, by (58) and (59), we have

$$ $\displaystyle a$ $\displaystyle=\langle\tilde{M}\circ\delta\gamma,\delta\gamma\rangle_{F}$ $\displaystyle=\langle(M\circ\delta\gamma-2\lambda|\delta\gamma|I_{n,m}),\delta \gamma\rangle_{F}$ $\displaystyle=\langle M\circ\delta\gamma,\delta\gamma\rangle_{F}-2\lambda| \delta\gamma|^{2}$ (65) $\displaystyle=\left\langle u(C^{X},C^{Y},\delta\gamma)-h_{1}(C^{X})\delta \gamma h_{2}(C^{Y})^{\top},\delta\gamma\right\rangle_{F}-2\lambda|\delta\gamma |^{2},$ $\displaystyle b$ $\displaystyle=2\langle\tilde{M}\circ\gamma,\delta\gamma\rangle_{F}$ $\displaystyle=2\langle M\circ\gamma-2\lambda|\gamma|I_{n,m},\delta\gamma\rangle$ $\displaystyle=2(\langle M\circ\gamma,\delta\gamma\rangle_{F}-2\lambda|\delta \gamma||\gamma|)$ (66) $$

Note that in the classical GW setting [], the term $u(C^{X},C^{Y},\delta\gamma)=0_{n\times m}$ and $|\delta\gamma|=0$. Therefore, in such line search algorithm (Algorithm 2 in []), the terms $u(C^{X},C^{Y},\delta\gamma),2\lambda|\delta\gamma|1_{n\times m}$ are not required. In addition, in equation (66), $M\circ\gamma,2\lambda|\gamma|$ have been computed in the gradient computation step, thus these two terms can be directly applied in this step.

## Appendix J Line Search in Algorithm 2

Similar to the previous section, in iteration $k$, let $\hat{\gamma}^{(k)},\hat{\gamma}^{(k)^{\prime}}$ denote the previous transportation plan and the updated transportation plan. For convenience, we denote them as $\hat{\gamma},\hat{\gamma}^{\prime}$, respectively.

Let $\delta\hat{\gamma}=\hat{\gamma}-\hat{\gamma}^{\prime}$.

The goal is to find the following optimal $\alpha$:

$$ $\displaystyle\alpha=\arg\min_{\alpha\in[0,1]}\mathcal{L}(\hat{M},(1-\alpha) \hat{\gamma},\alpha\hat{\gamma}^{\prime})=\arg\min_{\alpha\in[0,1]}\mathcal{L} (\hat{M},\alpha\delta\hat{\gamma}+\hat{\gamma}),$ (67) $$

where $\hat{M}\in\mathbb{R}^{(n+1)\times(m+1)\times(n+1)\times(m+1)}$, with $\hat{M}[1:n,1:m,1:n,1:m]=\tilde{M}=M-2\lambda 1_{n\times m\times n\times m}$.

Similar to the previous section,
let

$$ $\displaystyle a$ $\displaystyle=\langle\hat{M}\circ\delta\hat{\gamma},\delta\hat{\gamma}\rangle_ {F},$ $\displaystyle b$ $\displaystyle=\langle\hat{M}\circ\delta\hat{\gamma},\hat{\gamma}\rangle_{F}+ \langle\hat{M}\circ\hat{\gamma},\delta\hat{\gamma}\rangle_{F}=2\langle\hat{M} \circ\delta\hat{\gamma},\hat{\gamma}\rangle_{F},$ (68) $\displaystyle c$ $\displaystyle=\langle\hat{M}\circ\hat{\gamma},\hat{\gamma}\rangle_{F},$ $$

where $\eqref{pf: b v2}$ holds since $\hat{M}$ is symmetric.
Then, the optimal $\alpha$ is given by (64).

It remains to discuss the computation. By Lemma F.1, we set $\gamma=\hat{\gamma}[1:n,1:m],\delta\gamma=\delta\hat{\gamma}[1:n,1:m]$. Then,

$$ $\displaystyle a$ $\displaystyle=\langle(\hat{M}\circ\delta\hat{\gamma})[1:n,1:m],\delta\gamma \rangle_{F}=\langle(\tilde{M}\circ\delta\gamma,\delta\gamma\rangle_{F},$ $\displaystyle b$ $\displaystyle=\langle(\hat{M}\circ\delta\hat{\gamma})[1:n,1:m],\gamma\rangle_{ F}=\langle(\tilde{M}\circ\delta\gamma,\gamma\rangle_{F}.$ $$

Thus, we can apply (65), (66) to compute $a,b$ in this setting by plugging in $\gamma=\hat{\gamma}[1:n,1:m]$ and $\delta\gamma=\delta\hat{\gamma}[1:n,1:m]$.

## Appendix K Convergence

As in [] we will use the results from [] on the convergence of the Frank-Wolfe algorithm for non-convex objective functions.

Consider the minimization problems

$$ $\min_{\gamma\in\Gamma_{\leq}(\mathrm{p},\mathrm{q})}\mathcal{L}_{\tilde{M}}( \gamma)\qquad\text{ and }\qquad\min_{\hat{\gamma}\in\Gamma(\hat{\mathrm{p}}, \hat{\mathrm{q}})}\mathcal{L}_{\hat{M}}(\hat{\gamma})$ (69) $$

that corresponds to the discrete partial GW problem, and the discrete GW-variant problem (used in version 2), respectively.
The objective functions
$\gamma\mapsto\mathcal{L}_{\hat{M}}(\gamma)=\tilde{M}\gamma^{\otimes 2}$ (where $\tilde{M}=M-2\lambda 1_{n,m}$ for a fixed matrix $M\in\mathbb{R}^{n\times m}$ and $\lambda>0$), and
$\hat{\gamma}\mapsto\mathcal{L}_{\hat{M}}(\hat{\gamma})=\hat{M}\hat{\gamma}^{
\otimes 2}$ (where $\hat{M}$ is given by (54)) are non-convex in general (for $\lambda>0$, the matrices $\tilde{M}$ and $\hat{M}$ symmetric but not positive semi-definite), but the constraint sets $\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})$ and $\Gamma(\hat{\mathrm{p}},\hat{\mathrm{q}})$ are convex and compact on $\mathbb{R}^{n\times m}$ (see Proposition B.2 []) and on $\mathbb{R}^{(n+1)\times(m+1)}$, respectively.

From now on we will concentrate on the first minimization problem in (69) and the convergence analysis for the second one will be analogous.

Consider the Frank-Wolfe gap of $\mathcal{L}_{\tilde{M}}$ at the approximation $\gamma^{(k)}$ of the optimal plan $\gamma$:

$$ $g_{k}=\min_{\gamma\in\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})}\langle\nabla \mathcal{L}_{\tilde{M}}(\gamma^{(k)}),\gamma^{(k)}-\gamma\rangle_{F}.$ (70) $$

It provided a good criterion to measure the distance to a stationary point at iteration $k$. Indeed, a plan $\gamma^{(k)}$ is a stationary transportation plan for the corresponding constrained optimization problem in (69) if and only if $g_{k}=0$. Moreover, $g_{k}$ is always non-negative ($g_{k}\geq 0$).

From Theorem 1 in [], after $K$ iterations we have the following upper bound for the minimal Frank-Wolf gap:

$$ $g_{K}:=\min_{1\leq k\leq K}g_{k}\leq\frac{\max\{2L_{1},\mathrm{Lip}\cdot(\text {diam}(\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})))^{2}\}}{\sqrt{K}},$ (71) $$

where

$$ $L_{1}:=\mathcal{L}_{\tilde{M}}(\gamma^{(1)})-\min_{\gamma\in\Gamma_{\leq}({ \mathrm{p}},{\mathrm{q}})}\mathcal{L}_{\tilde{M}}(\gamma)$ $$

is the initial global sub-optimal bound for the initialization $\gamma^{(1)}$ of the algorithm; Lip is the Lipschitz constant of function
$\gamma\mapsto\nabla\mathcal{L}_{\tilde{M}}$; and

$$ $\text{diam}(\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}}))=\sup_{\gamma,\gamma^{ \prime}\in\Gamma_{\leq}(\mu,\nu)}\|\gamma-\gamma^{\prime}\|_{F}$ $$

is the $\|\cdot\|_{F}$ diameter of $\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})$ in $\mathbb{R}^{n\times m}$.

The important thing to notice is that the constant $\max\{2L_{1},D_{L}\}$ does not depend on the iteration step $k$. Thus, according to Theorem 1 in [], the rate in $\tilde{g}_{K}$ is $\mathcal{O}(1/\sqrt{K})$. That is, the algorithm takes at most $\mathcal{O}(1/\varepsilon^{2})$ iterations to find an approximate stationary point with a gap smaller than $\varepsilon$.

###### Lemma K.1 .

In discrete PGW problem, we have

$$ $\displaystyle\text{diam}(\Gamma_{\leq}(p,q))\leq 2s:=2\min(|p|,|q|)$ (72) $$

###### Proof.

Choose $\gamma,\gamma^{\prime}\in\Gamma_{\leq}(p,q)$,
we apply the property

$$ $\displaystyle(a-b)^{2}\leq 2a^{2}+2b^{2},\forall a,b\in\mathbb{R}$ (73) $$

and obtain

$$ $\displaystyle\|\gamma-\gamma^{\prime}\|_{F}^{2}$ $\displaystyle=\sum_{i,j}^{n,m}|\gamma_{i,j}-\gamma^{\prime}_{i,j}|^{2}$ $\displaystyle\leq\sum_{i,j}^{n,m}2|\gamma_{i,j}|^{2}+2|\gamma^{\prime}_{i,j}|^ {2}$ $\displaystyle\leq 2\left[(\sum_{i,j}\gamma_{i,j})^{2}+(\sum_{i,j}\gamma^{ \prime}_{i,j})^{2}\right]$ $\displaystyle=2(|\gamma|^{2}+|\gamma^{\prime}|^{2})$ (74) $\displaystyle\leq 2\min(|p|,|q|)^{2}+2\min(|p|,|q|)^{2}$ $\displaystyle=4\min(|p|,|q|)^{2}$ $$

and thus we complete the proof.
∎

###### Lemma K.2 .

For the Lip term in (71) can be bounded as following:

$$ $\displaystyle\text{Lip}\leq nm\max_{i,i,j,j^{\prime}}(2(C^{X}_{i,i^{\prime}})^ {2}+2(C^{Y}_{j,j^{\prime}})^{2},2\lambda)$ (75) $$

###### Proof.

Pick $\gamma,\gamma^{\prime}\in\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})$ we have,

$$ $\displaystyle\|\nabla\mathcal{L}_{\tilde{M}}(\gamma)-\nabla\mathcal{L}_{\tilde {M}}(\gamma^{\prime})\|_{F}^{2}$ $\displaystyle=\|\tilde{M}\circ\gamma-\tilde{M}\circ\gamma^{\prime}\|_{F}^{2}$ $\displaystyle=\|[M-2\lambda]\circ(\gamma-\gamma^{\prime})\|_{F}^{2}$ $\displaystyle=\sum_{i,j}\left(\left[(M-2\lambda)\circ(\gamma-\gamma^{\prime}) \right]_{i,j}\right)^{2}$ $\displaystyle=\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}(M_{i,j,i^{\prime},j ^{\prime}}-2\lambda)(\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime },j^{\prime}})\right)^{2}$ $\displaystyle\leq\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}|M_{i,j,i^{\prime },j^{\prime}}-2\lambda||\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{ \prime},j^{\prime}}|\right)^{2}$ $\displaystyle\leq\underbrace{\left(\max_{i,j,i^{\prime},j^{\prime}}\{M_{i,j,i^ {\prime},j^{\prime}}-2\lambda\}\right)^{2}}_{A}\cdot\underbrace{\sum_{i,j}^{n, m}\left(\sum_{i^{\prime},j^{\prime}}^{n,m}|\gamma_{i^{\prime},j^{\prime}}- \gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2}}_{B}$ $$

For the first term, we have:

$$ $\displaystyle A$ $\displaystyle\leq\max\{2(C^{X})^{2}+2(C^{Y})^{2},2\lambda\}^{2}$ $$

where

$$ $\max\{2(C^{X})^{2}+2(C^{Y})^{2},2\lambda\}:=\max\{\max_{i,i^{\prime},j^{\prime },j^{\prime}}2(C^{X}_{i,i^{\prime}})^{2}+2(C^{Y}_{j,j^{\prime}})^{2},2\lambda\}$ $$

For the second term, we have:

$$ $\displaystyle\sum_{i,j}^{n,m}\left(\sum_{i^{\prime},j^{\prime}}^{n,m}|\gamma_{ i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2}$ $\displaystyle\leq\sum_{i,j}^{n,m}\left(nm\sum_{i^{\prime},j^{\prime}}^{n,m} \left|\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}} \right|^{2}\right)$ $\displaystyle\leq n^{2}m^{2}\|\gamma-\gamma^{\prime}\|^{2}_{F}$ $$

Thus we obtain

$$ $\displaystyle\text{Lip}\leq\frac{\max(2(C^{X})^{2}+2(C^{Y})^{2},2\lambda)nm\| \gamma-\gamma^{\prime}\|_{F}}{\|\gamma-\gamma^{\prime}\|_{F}}=nm\max(2(C^{X})^ {2}+2(C^{Y})^{2},2\lambda)$ $$

and we complete the proof.
∎

Combined the above two lemmas, we derive the convergence rate of Frank-Wolf gap (70):

###### Proposition K.3 .

When $L(r_{1},r_{2})=|r_{1}-r_{2}|^{2}$ in the PGW problem, the Frank-Wolfe gap of algorithm 1, defined in (70) at iteration $k$ satisfies the following:

$$ $\displaystyle g_{k}\leq\frac{\max\Bigg{\{}2L_{1},4\min(|\mathrm{p}|,|\mathrm{q }|)^{2}\cdot nm(\max\{2(C^{X})^{2}+2(C^{Y})^{2},2\lambda\})\Bigg{\}}}{\sqrt{k}}$ (76) $$

###### Proof.

The proof directly follows from the upper bounds (72),(75) and the inequality (71).
∎

###### Remark K.4 .

Note, if the cost function in PGW is defined by $|r_{1}-r_{2}|^{p}$ for some $p\neq 2$, it is straightforward to verify that, the upper bound of $g_{k}$ is obtained by replacing the term $\max((C^{X})^{2}+(C^{Y})^{2},2\lambda)$ should be replaced by

$$ $\max_{i,j,i^{\prime},j^{\prime}}\left[2^{p-1}((C^{X})^{p}+(C^{Y})^{p}),2 \lambda\right].$ $$

###### Remark K.5 .

It is straight-forward to verify that, the Frank-Wolf gap for algorithm 2 is also upper bounded by (76).

###### Remark K.6 .

From the proposition (K.3), to achieve an $\epsilon-$accurate solution, the required number of iterations 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}}$ $$

In practice, by lemma E.2, when $\lambda$ is large, it is equivalent to set $\lambda=\max((C^{X})^{2}-(C^{Y})^{2})$ and thus, the value $\lambda$ will not affect the number of iterations.

###### Remark K.7 .

In this remark, we compare the upper (40) and the upper bounds in previous works, including [] and cang2024supervised. We observe that:

If we ignore the term $\lambda$ (or equivalently, set $\lambda=\max_{i,i^{\prime},j,j^{\prime}}(2(C^{X})^{2}+2(C^{Y})^{2})$), the upper bound (76) aligns with the upper bound for the Frank-Wolfe Gap in Mass-constraint PGW (see [, Eq. (10)]) and balanced GW (see [, p. 18].

However, there exists several differences in details between our result and the result in [].

- •
First, in [], the term $nm$ is omitted. We suspect this omission is a typo, as $nm$ term is contained in [].
- •
In [], “$s$” plays the role of $\min(|\mathrm{p}|,|\mathrm{q}|)$ in our result.
The assumption in [, Lemma 1] is
$|\gamma|=|\gamma^{\prime}|=1$
If we normalize $\mathrm{p},\mathrm{q}$ such that $\max(|\mathrm{p}|,|\mathrm{q}|)\leq 1$,
we will obtain
$2\min(|\mathrm{p}|,|\mathrm{q}|)^{2}\leq 2\min(|\mathrm{p}|,|\mathrm{q}|),$
and our result will induce the upper bound in [, Lemma 1].

###### Lemma K.1 .

###### Proof.

###### Lemma K.2 .

###### Proof.

###### Proposition K.3 .

###### Proof.

###### Remark K.4 .

###### Remark K.5 .

###### Remark K.6 .

###### Remark K.7 .

## Appendix L Related Work: Mass-Constrained Partial Gromov-Wasserstein

Partial Gromov-Wasserstein is first introduced in []. To distinguish the PGW problem in [] and the PGW problem in this paper, we call the former one the Mass-Constrained Gromov-Wasserstein problem (MPGW):

$$ $MPGW_{\rho}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma_{\leq}^{\rho}(\mu, \nu)}\gamma^{\otimes 2}(L(d_{X}^{q},d_{Y}^{q})),$ (77) $$

where $\rho\in[0,\min\{|\mu|,|\nu|\}]$, and

$$ $\Gamma_{\leq}^{\rho}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(X\times Y):\gamma_{1 }\leq\mu,\,\gamma_{2}\leq\nu,\,\,|\gamma|=\rho\}.$ (78) $$

Unlike the relation between Partial OT and OT, it is not rigorous to say that the PGW and the MPGW problems are equivalent, since the objective function

$$ $\gamma\mapsto\int_{(X\times Y)^{2}}L(d_{X}^{2}(x,x^{\prime}),d_{Y}^{2}(y,y^{ \prime}))d\gamma^{\otimes 2}$ (79) $$

is not a convex function even if $(r_{1},r_{2})\mapsto L(r_{1},r_{2})$ is convex []: (If the problems were convex, MPGW, as the ‘Lagrangian formulation’ of PGW—adding the constraint of PGW in the functional à la Lagrange Multipliers— would be equivalent to PGW. However, since these problems are not convex, we cannot claim that they are equivalent in principle.)

We can still investigate their relationship by the following lemma, based on which we design the wall-clock time experiment in Section P.

###### Proposition L.1 .

For each $\lambda\geq 0$, there exists $\rho\in[0,\min(|\mu|,|\nu|)]$ such that, for each $\gamma\in\Gamma_{\leq}(\mu,\nu)$ with $|\gamma|=\rho$, $\gamma$ is optimal in $PGW_{\lambda}(\mathbb{X},\mathbb{Y})$ iff $\gamma$ is optimal in $MPGW_{\rho}(\mathbb{X},\mathbb{Y})$. Furthermore,

$$ $PGW_{\lambda}(\mu,\nu)=MPGW_{\rho}(\mu,\nu)+\lambda(|\mu|^{2}+|\nu|^{2}-2\rho^ {2}).$ $$

###### Proof.

Pick $\gamma^{\prime}\in\Gamma^{\rho}_{\leq}(\mu,\nu)\subset\Gamma_{\leq}(\mu,\nu)$, since $\gamma$ is optimal in $PGW_{\lambda}(\mu,\nu)$, we have

$$ $\displaystyle 0$ $\displaystyle\leq C(\gamma;\lambda,\mu,\nu)-C(\gamma^{\prime};\lambda,\mu,\nu)$ $\displaystyle=\int_{(X\times Y)^{2}}L(d_{X}^{2}(x,x^{\prime}),d_{Y}^{2}(y,y^{ \prime}))d(\gamma^{\otimes 2}-\gamma^{\prime\otimes 2})$ $$

Thus, $\gamma$ is optimal in $\Gamma^{\rho}_{\leq}(\mu,\nu)$ for $MPGW_{\rho}(\mathbb{X},\mathbb{Y})$ and we complete the proof.
∎

###### Remark L.2 .

The above proposition clarifies a connection between $PGW$ and $MPGW$. Specifically, it implies that an optimal transportation plan for $PGW$ can be derived from $MPGW$ by appropriately setting $\rho$.
However, it is important to note that MPGW does not define a metric, whereas PGW does.
Therefore, in experiments that require transportation cost, such as the shape retrieval experiment described in the main text, the results produced by the two methods will differ significantly. Moreover, there may, in fact, exist instances of the two problems for which the solution sets are not equal for any value of the hyperparameters $\lambda$ and $\rho$; we illustrate this in Example L.3. We further illustrate their differences with Example L.5.

###### Example L.3 .

Consider the mm-spaces given by

$$ $\mathbb{X}_{1}=(\mathbb{R}^{d_{1}},\|\cdot\|,\sum_{i=1}^{n}\delta_{x_{i}}) \quad\text{and}\quad\mathbb{X}_{2}=(\mathbb{R}^{d_{2}},\|\cdot\|,\sum_{j=1}^{m }\delta_{y_{j}}.$ $$

If we let $\lambda=0$, then $PGW_{0}(\mathbb{X}_{1},\mathbb{X}_{2})$ has $\delta_{(x_{i},y_{j})}$ as a solution for all $(i,j)$, as well as the zero measure.

Now, we observe that for $\rho=0$, $\delta_{(x_{i},y_{j})}$ is not a solution of $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$; meanwhile, for any $\rho>0$, the zero measure is not a solution of $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$.

Hence, we see that the set of solutions between $PGW_{0}(\mathbb{X}_{1},\mathbb{X}_{2})$ and $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$ are distinct for all $\rho$.

###### Remark L.4 .

The other direction of the “equivalence relation” between PGW and MPGW given by Proposition L.1 may not hold. In particular, we can find an instance of $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$ such that for all $\lambda>0$, each solution to $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$ is not a solution to $PGW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2})$, and each solution to $PGW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2})$ is not a solution to $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$.

As an example, consider $\mathbb{X}_{1}=(\mathbb{R}^{d},\|\cdot\|,\sum_{i=1}^{100}\delta_{x_{i}})$ and $\mathbb{X}_{2}=(\mathbb{R}^{d},\|\cdot\|,\sum_{i=1}^{2}00\delta_{x_{i}}$, where $x_{1},\ldots x_{200}$ are distinct. Then for each $\rho\in[0,100]$, any solution to $MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2})$ is not a solution for $PGW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2})$, and vice versa.

###### Example L.5 .

Consider the following three mm-spaces

$$ $\mathbb{X}_{1}=(\mathbb{R}^{3},\|\cdot\|,\sum_{i=1}^{1000}\alpha\delta_{x_{i}} ),\quad\mathbb{X}_{2}=(\mathbb{R}^{3},\|\cdot\|,\sum_{i=1}^{800}\alpha\delta_{ x_{i}}),\quad\mathbb{X}_{3}=(\mathbb{R}^{3},\|\cdot\|,\sum_{i=1}^{400}\alpha \delta_{x_{i}}),$ $$

where $\alpha>0$ is the mass of each point. For numerical stability reasons, we set $\alpha=1/1000$.
On the one hand, if we compute MPGW, the mass is fixed to be a value $\rho\in[0,0.4]$, since the total mass in $\mathbb{X}_{3}$ is $0.4$. For our experiment, we set $\rho=0.4$, and we observe:

$$ $\displaystyle MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_{2};\rho=0.4)=MPGW_{\rho}( \mathbb{X}_{2},\mathbb{X}_{3};\rho=0.4)=MPGW_{\rho}(\mathbb{X}_{1},\mathbb{X}_ {3};\rho=0.4)=0$ $$

On the other hand, if we compute our PGW, considering any $\lambda>0$, (in particular, we set $\lambda=10$), we obtain

$$ $\displaystyle PGW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{2};\lambda=10)=3.6$ $\displaystyle PGW_{\lambda}(\mathbb{X}_{2},\mathbb{X}_{3};\lambda=10)=4.8$ $\displaystyle PGW_{\lambda}(\mathbb{X}_{1},\mathbb{X}_{3};\lambda=10)=8.4$ $$

In particular, one can verify the triangular inequality.

As a conclusion, in this example, MPGW can not describe the dissimilarity of any two datasets taken from $\{\mathbb{X}_{1},\mathbb{X}_{2},\mathbb{X}_{3}\}$. They are three distinct datasets, but MPGW returns zero for each pair. On the contrary, our PGW can measure dissimilarity.

In addition, the discrepancy provided by our PGW formulation is consistent with the following intuitive observation: One expects the dissimilarity between $\mathbb{X}_{1}$ and $\mathbb{X}_{3}$ to be larger than the difference $\mathbb{X}_{1}$ and $\mathbb{X}_{2}$, and than the difference between $\mathbb{X}_{1}$ and $\mathbb{X}_{2}$. This is because we are considering discrete measures, with the same mass at each point concentrated on the sets $\{x_{1},\dots,x_{400}\}\subset\{x_{1},\dots,x_{400},\dots,x_{800}\}\subset\{x_
{1},\dots,x_{400},\dots,x_{800},\dots,x_{1000}\}$ for the datasets $\mathbb{X}_{3},\mathbb{X}_{2},\mathbb{X}_{1}$, respectively.

###### Proposition L.1 .

###### Proof.

###### Remark L.2 .

###### Example L.3 .

###### Remark L.4 .

###### Example L.5 .

## Appendix M Partial Gromov-Wasserstein Barycenter

We first introduce the classical Gromov-Wasserstein problem []:
Consider finite discrete probability measures $\mu^{1},\ldots,\mu^{K}$, where $\mu^{k}=\sum_{i=1}^{n_{k}}p^{k}_{i}\delta_{x^{k}_{i}}$ and each $x^{k}_{i}\in\mathbb{R}^{d_{k}}$ for some $d_{k}\in\mathbb{N}$. Let $C^{k}=[\|x^{k}_{i}-x^{k}_{i^{\prime}}\|^{2}]_{i,i^{\prime}\in[1:n_{k}]}$ and $\mathrm{p}^{k}=[p^{k}_{1},\dots,p^{k}_{n_{k}}]^{\top}$.
Given $\mathrm{p}\in\mathbb{R}_{+}^{n}$ with $|\mathrm{p}|=1$ for some $n\in\mathbb{N}$ and $\xi_{1},\ldots,\xi_{K}\geq 0$ with $\sum_{k=1}^{K}\xi_{k}=1$, the GW barycenter problem is defined by:

$$ $\displaystyle\min_{C,\gamma^{k}}\sum_{k=1}^{K}\xi_{k}\langle L(C,C^{k})\circ \gamma^{k},\gamma^{k}\rangle,$ (80) $$

where the minimization is over all matrices $C\in\mathbb{R}^{n\times n},\gamma^{k}\in\Gamma(\mathrm{p},\mathrm{p}^{k}),
\forall k\in[1:K]$.

Similarly, we can extend the above definition into PGW setting. In particular, we relax the assumptions $|\mathrm{p}|=1$ and $|\mathrm{p}^{k}|=1$ for each $k\in[1:K]$. Given $\lambda_{1},\ldots,\lambda_{K}>0$, the PGW barycenter is the follow problem:

$$ $\displaystyle\min_{C,\gamma_{k}}\sum_{k}\xi_{k}\langle M(C,C^{k})\circ\gamma^{ k},\gamma^{k}\rangle-2\lambda_{k}|\gamma^{k}|^{2}$ (81) $$

where each $\gamma^{k}\in\Gamma_{\leq}(\mathrm{p},\mathrm{p}^{k})$.

The problem (81) can be solved iterative by two steps:

Minimization with respect to $C$:
For each $k$, we solve the PGW problem

$$ $\min_{\gamma^{k}\in\Gamma_{\leq}(p,p^{k})}\langle M(C,C^{k})\circ\gamma^{k}, \gamma^{k}\rangle-2\lambda_{k}|\gamma^{k}|^{2}$ $$

via solver 1 or 2.

Minimization with respect to $\{\gamma^{k}\}_{k}$:

$$ $\displaystyle\min_{C}\sum_{k}\xi_{k}\langle M(C,C^{k})\circ\gamma^{k},\gamma^{ k}\rangle$ (82) $$

Note, we can ignore the $-2\lambda_{k}|\gamma^{k}|^{2}$ terms as $\gamma^{k}$ is fixed in this case.

It has closed form solution due to the following lemma and proposition:

###### Lemma M.1 .

Given matrices $A\in\mathbb{R}^{n,m},B\in\mathbb{R}^{m,l},C\in\mathbb{R}^{n,l}$, let

$$ $\mathcal{L}=\langle AB,C\rangle,$ $$

then $\frac{d\mathcal{L}}{dA}=CB^{\top}$.

###### Proof.

For any $i\in[1:n],j\in[1:m]$, we have

$$ $\displaystyle\frac{d\mathcal{L}}{dA_{ij}}$ $\displaystyle:=\sum_{i^{\prime},j^{\prime}}\frac{d}{dA_{ij}}C_{i^{\prime},j^{ \prime}}(AB)_{i^{\prime},j^{\prime}}$ $\displaystyle=\sum_{i^{\prime},j^{\prime}}C_{i^{\prime},j^{\prime}}\frac{d( \sum_{k}A_{i^{\prime},k}B_{k,j^{\prime}})}{dA_{ij}}$ $\displaystyle=\sum_{j^{\prime}}C_{i,j^{\prime}}B_{k,j^{\prime}}=(CB^{\top})_{ ij}.$ $$

∎

###### Proposition M.2 .

If $L$ satisfies (57), and $f_{1}^{\prime}/h_{1}^{\prime}$ is invertible, then (82) can be solved by

$$ $\displaystyle C=\left(\frac{f_{1}^{\prime}}{h_{1}^{\prime}}\right)^{-1}\left( \frac{\sum_{k}\xi_{k}\gamma^{k}h_{2}(C^{k})(\gamma_{k})^{\top}}{\sum_{k}\xi_{k }\gamma^{k}_{1}(\gamma^{k}_{1})^{\top}}\right),$ (83) $$

where

$$ $\frac{A}{B}=\left[\frac{A_{ij}}{B_{ij}}\right]_{ij},\text{with convention } \frac{0}{0}=0.$ $$

Special case: if $|\mathrm{p}|\leq|\mathrm{p}^{k}|,\forall k$, when $\lambda$ is sufficiently large, (83) and [, Proposition 3] coincide.

###### Proof.

From Proposition H.1, the objective in (82) becomes

$$ $\displaystyle\mathcal{L}=$ $\displaystyle\sum_{k}\xi_{k}\langle f_{1}(C)\gamma_{1}^{1}1^{\top}_{n_{k}}+1_{ n}(\gamma_{2}^{k})^{\top}f_{2}(C^{k})-h_{1}(C)\gamma^{k}h_{2}(C^{k})^{\top}, \gamma^{k}\rangle$ $\displaystyle=\sum_{k}\xi_{k}\langle f_{1}(C)\gamma_{1}^{1}1^{\top}_{n_{k}}, \gamma^{k}\rangle+\underbrace{\sum_{k}\xi_{k}\langle 1_{n}(\gamma_{2}^{k})^{ \top}f_{2}(C^{k}),\gamma^{k}\rangle}_{\text{constant}}-\sum_{k}\xi_{k}\langle h _{1}(C)\gamma^{k}h_{2}(C^{k})^{\top},\gamma^{k}\rangle$ $$

We set $\frac{d\mathcal{L}}{dC}=0$. From Lemma M.1, we have:

$$ $\displaystyle 0$ $\displaystyle=\frac{d\mathcal{L}}{dC}$ $\displaystyle=\sum_{k}\xi_{k}f_{1}^{\prime}(C)\odot\gamma^{k}1_{n_{k}}(\gamma_ {1}^{k})^{\top}-\sum_{k}\xi_{k}h_{1}^{\prime}(C)\odot\gamma^{k}h_{2}(C^{k})( \gamma^{k})^{\top}$ $\displaystyle=f_{1}^{\prime}(C)\odot\sum_{k}\xi_{k}\gamma^{k}1_{n_{k}}(\gamma_ {1}^{k})^{\top}-h_{1}^{\prime}(C)\odot\sum_{k}\xi_{k}\gamma^{k}h_{2}(C^{k})( \gamma^{k})^{\top}$ $\displaystyle=f_{1}^{\prime}(C)\odot\underbrace{\sum_{k}\xi_{k}\gamma^{k}_{1}( \gamma_{1}^{k})^{\top}}_{B}-h_{1}^{\prime}(C)\odot\underbrace{\sum_{k}\xi_{k} \gamma^{k}h_{2}(C^{k})(\gamma^{k})^{\top}}_{A}.$ (84) $$

We claim $\frac{A}{B}$ is well-defined, i.e., if $B_{ij}=0$, then $A_{ij}=0$.

For each $i,j\in[1:n]$, if $B_{ij}=0$, we have two cases:

Case 1: $\forall k\in[1:K]$, we have $\gamma^{k}_{1}[i]=0$.

Thus,
$\gamma^{k}[i,:]=0_{n_{k}}^{\top}$. So $A[i,:]=(\gamma^{k}h_{2}(C^{k})(\gamma^{k})^{\top})[i,:]=0_{n_{k}}^{\top}$.

Case 2: $\forall k\in[1:K]$, we have $\gamma^{k}_{1}[j]=0$.

It implies $(\gamma^{k})^{\perp}[:,j]=0_{n}$, thus $A[:,j]=(\gamma^{k}h_{2}(C^{k}))(\gamma^{k})^{\top}[:,j]=0_{n_{k}}$. Therefore, $A_{ij}=0$.

Thus $\frac{A}{B}$ is well-defined.

In addition, in these two cases, if we change the value $C_{ij}^{k}$, $\mathcal{L}$ will not change.

From (84), we have:

$$ $\displaystyle\left(\frac{f_{1}^{\prime}}{h_{1}^{\prime}}(C)\right)_{ij}=\frac{ \left(\sum_{k}\xi_{k}\gamma^{k}h_{2}(C^{k})(\gamma^{k})^{\top}\right)_{ij}}{ \left(\sum_{k}\xi_{k}\gamma^{k}_{1}(\gamma_{1}^{k})^{\top}\right)_{ij}}$ $$

if $B_{ij}>0$. In addition, if $B_{ij}=0$, there is no constraint for $C_{ij}$.

Combining it with the fact that if $B_{i,j}=0$, then $C_{i,j}$ has no effect on $\mathcal{L}$.
Thus,

we have the following is a solution:

$$ $C=\left(\frac{f_{1}^{\prime}}{h_{1}^{\prime}}\right)^{-1}\left(\frac{\sum_{k} \xi_{k}\gamma^{k}h_{2}(C^{k})(\gamma^{k})^{\top}}{\sum_{k}\xi_{k}\gamma^{k}_{1 }(\gamma_{1}^{k})^{\top}}\right).$ $$

In particular case: $|\mathrm{p}|\leq|\mathrm{p}^{k}|,\forall k$, suppose $\lambda>\max\{c^{2}:c\in\bigcup_{k}C^{k}\cup C\}$, by lemma E.1, we have for each $k$, $|\gamma^{k}|=\min(|\mathrm{p}|,|\mathrm{p}|^{k})=|\mathrm{p}|$, that is $\gamma^{k}_{1}=\mathrm{p}$.

Thus,

$$ $\displaystyle\sum_{k}\xi_{k}\gamma^{k}_{1}(\gamma_{1}^{1})^{\top}=\sum_{k}\xi_ {k}\gamma_{1}^{k}(\gamma_{1}^{k})^{\top}=\sum_{k}\xi_{k}\mathrm{p}\mathrm{p}^{ \top}=\mathrm{p}\mathrm{p}^{\top}$ $$

Thus, $C=\left(\frac{f_{1}^{\prime}}{h_{1}^{\prime}}\right)^{-1}\left(\frac{\sum_{k}
\xi_{k}\gamma^{k}h_{2}(C^{k})(\gamma^{k})^{\top}}{\mathrm{p}\mathrm{p}^{\top}}
\right).$
∎

###### Remark M.3 .

In $l^{2}$ loss case, i.e. $L(r_{1},r_{2})=|r_{1}-r_{2}|^{2}$, (83) becomes

$$ $\displaystyle C=\frac{\sum_{k}\xi_{k}\gamma^{k}C^{k}(\gamma^{k})^{\top}}{\sum_ {k}\xi_{k}\gamma^{k}_{1}(\gamma^{k}_{1})^{\top}}.$ (85) $$

Since in this case, we can set

$$ $f_{1}(x)=x^{2},f_{2}(y)=y^{2},h_{1}(x)=2x,h_{2}(y)=y.$ $$

Thus $\frac{f_{1}^{\prime}}{h_{1}^{\prime}}(x)=\frac{2x}{2}=x$ and $\left(\frac{f_{1}^{\prime}}{h_{1}^{\prime}}\right)^{-1}(x)=x$. Therefore, (83) becomes (85).

Figure: Algorithm 3 Partial Gromov-Wasserstein Barycenter

Similarly, we can also extend the above PGW Barycenter into the MPGW setting:

$$ $\min_{C,\gamma^{k}}\sum_{k=1}^{K}\xi_{k}\langle L(C,C^{k})\circ\gamma^{k}, \gamma^{k}\rangle,$ $$

where, for each $k\in[1:K]$, $\rho_{k}\in[0,\min(|\mathrm{p}|,|\mathrm{p}^{k}|)]$, and the optimization is over $C\in\mathbb{R}^{n}$ and $\gamma_{k}\in\Gamma^{\rho_{k}}_{\leq}(\mathrm{p},\mathrm{p}^{k})$ for $k\in[1:K]$.

It can be solved by the following algorithm 4.

Figure: Algorithm 4 Mass-Constrained Partial Gromov-Wasserstein Barycenter

Figure: Figure 4: We visualize the dataset in point cloud interpolation. The first row is the original images in [Link](https://github.com/gpeyre/2016-ICML-gromov-wasserstein). The second row is the point clouds obtained by the k-mean method, where $k=1024$.
Refer to caption: extracted/5880363/pics/interpolation_data.png

Figure: Figure 5: We test interpolation tasks in 3 scenarios: source data is clean, target data is selected from three cases as described in section dataset and data processing. In each scenario, we test $\eta=5\%,10\%$ respectively. In the first column, we present the source and target point cloud visualization in each task. In columns 2-9, we present GW, PGW barycenter for $t=0/7,1/7,\ldots,7/7$.
Refer to caption: extracted/5880363/pics/interporlation_u.png

###### Lemma M.1 .

###### Proof.

###### Proposition M.2 .

###### Proof.

###### Remark M.3 .

### M.1 Details of Point Cloud Interpolation Experiment

Dataset and data processing.
We apply the dataset in [] with download [link](https://github.com/gpeyre/2016-ICML-gromov-wasserstein). The original data are images, which we convert into a point cloud using the k-mean algorithm, where $k=1024$ (see the second row of Figure 4).

Suppose $\mathcal{D}\subset\mathbb{R}^{2}$ is a region that contains these point clouds.
Let $\mathcal{R}\subset\mathbb{R}^{2}$ denote another region. In $\mathcal{R}$, we randomly select and add $n\eta$ noise points to these point clouds. In particular, we consider noise corruption in the following three cases:

Case 1: $\mathcal{R}$ is a rectangle region which is disjoint to $\mathcal{D}$. See the third row in Figure 4.

Case 2:
$\mathcal{R}=\mathcal{R}_{1}\cup\mathcal{R}_{2}$, where $\mathcal{R}_{1},\mathcal{R}_{2}$ are rectangles which are disjoint to $\mathcal{D}$. See the fourth row in Figure 4.

Case 3: $\mathcal{R}$ contains $\mathcal{D}$. See the fifth row in Figure 4.

GW Barycenter and PGW Barycenter methods.
We select $t_{1},\ldots,t_{K}$ with
$0=t_{1}<t_{2}<\ldots<t_{K}=1$. For each $t\in\{t_{1},\ldots,t_{K}\}$, we compute the GW Barycenter

$$ $\displaystyle\arg\min_{C,\gamma^{1},\gamma^{2}}(1-t)\langle L(C,C^{1})\circ \gamma^{1},\gamma^{1}\rangle+t\langle L(C,C^{2})\circ\gamma^{2},\gamma^{2}\rangle,$ (86) $$

where $\gamma_{1}\in\Gamma(\mathrm{p},\mathrm{p}^{1}),\gamma_{2}\in\Gamma(\mathrm{p},
\mathrm{p}^{2})$.
Apply Smacof-MDS to the minimizer $C$, the resulting embedding, denoted as $X_{t}\in\mathbb{R}^{n\times 2}$ (where $n=1024$) is the GW-based interpolation.

Replacing the GW Barycenter with the PGW Barycenter

$$ $\displaystyle\arg\min_{C,\gamma^{1},\gamma^{2}}(1-t)(\langle L(C,C^{1})\circ \gamma^{1},\gamma^{1}\rangle+\lambda_{1}|\gamma^{1}|^{2})+t(\langle L(C,C^{2}) \circ\gamma^{2},\gamma^{2}\rangle+\lambda_{2}|\gamma^{2}|),$ (87) $$

where $\lambda_{1},\lambda_{2}>0,\gamma^{1}\in\Gamma_{\leq}(\mathrm{p},\mathrm{p}^{1}
),\gamma^{2}\in\Gamma_{\leq}(\mathrm{p},\mathrm{p}^{2})$. Then we obtain PGW-based interpolation.

Problem setup.
We select one point cloud from the clean dataset denoted as $X=\{x_{i}\}_{i=1}^{n}$ (source point cloud), $n=1024$.

Next, we select one noise-corrupted point cloud, as described in Case 1, Case 2, and Case 3, respectively.
In these three scenarios, we test $\eta=0.5\%$ and $\eta=10\%$ where $\eta$ is the noise level. Therefore, we test $3*2=6$ different interpolation tasks for these two methods.
The size of the target point cloud is then $m=n+n\eta$.
See Figure 5 for details.

Numerical details.
In the GW-barycenter method, because of the balanced mass setting, we set

$$ $\mathrm{p}^{1}=\frac{1}{n}1_{n},\mathrm{p}^{2}=\frac{1}{m}1_{m},\mathrm{p}= \frac{1}{n}1_{n}.$ $$

In PGW-barycenter, we set

$$ $\mathrm{p}^{1}=\frac{1}{n}1_{n},\mathrm{p}^{2}=\frac{1}{n}1_{m},\mathrm{p}= \frac{1}{n}1_{n}.$ $$

In addition, we set $\lambda_{1},\lambda_{2}$ such that $2\lambda_{1},2\lambda_{2}\geq\max(\max(C_{1})^{2},\max(C_{2})^{2})$.
We compute GW/PGW barycenter for $t=0/7,1/7,\ldots,7/7$.

In both GW and PGW barycenter algorithms, we set the largest number of iterations to be 100. The threshold for convergence is set to be 1e-5.

Performance analysis.
Each interpolation task is essentially unbalanced: the source point cloud contains clean data, while the target point cloud contains clean and noise points. We observe that in the first two scenarios, the interpolation derived from GW is clearly disturbed by the noise data points. For example, in rows $1,3,5,7$, columns $t=1/7,2/7,3/7$, we see that the point clouds reconstructed by MDS have significantly different width-height ratios from those of the source and target point clouds.

In contrast, PGW is significantly less disturbed, and the interpolation is more natural. The width-height ratio of the point clouds generated by the PGW barycenter is consistent with that of the source/target point clouds.

In the third scenario, the noise data is uniformly selected from a large region that contains the domain of all clean point clouds. In this case, we observe that the GW and PGW barycenters perform similarly. However, at $t=1/7,2/7,4/7$, GW-barycenters present more noise points than PGW-barycenters in the same truncated region.

Limitations and future work.
The main issue of the above GW/PGW techniques arises from the MDS method:

Given minimizer $C\in\mathbb{R}^{n\times n}$ of GW/PGW barycenter problem (86) (or (87)), MDS studies the following problem:

$$ $\displaystyle\min_{X\in\mathbb{R}^{n\times d}}\sum_{i,i^{\prime}=1}^{n}\left|C _{i,i^{\prime}}^{1/2}-\|X_{i}-X_{i^{\prime}}\|\right|^{2}$ (88) $$

Let $O(n)$ denote the set of all $n\times n$ orthonormal matrices. Suppose $X^{*}$ is a minimizer, then $RX^{*}$ is also a minimizer for the above problem for all $R\in O(n)$.

In practice, this means manually setting suitable rotation and flipping matrices for each method at each step, especially for the GW method.

However, we understand that this issue stems from the inherent properties of the GW/PGW method. GW can be seen as a tool that describes the similarity between two graphs, which are rotation-invariant and flipping-invariant. Therefore, the GW/PGW barycenter essentially describes the interpolation between two graphs rather than two point clouds.

## Appendix N Details of Point Cloud Matching

Dataset setup.
In the Moon dataset (see [link](https://scikit-learn.org/stable/modules/generated/sklearn.datasets.make_moons.html)),
we apply $n=200$ and set Gaussian variance to be $0.2$. The outliers are sampled from region $[[-2,-1.5]\times[-3.5,-3]]$.

In the second experiment, the circle data is uniformly sampled from 2D circle

$$ $\mathbb{S}^{1}=\{s\in\mathbb{R}^{2}:\|s\|^{2}=1\}$ $$

and spherical data is uniformly sampled from 3D sphere

$$ $\mathbb{S}^{2}=\{s+[0,0,4]\in\mathbb{R}^{2}:\|s\|^{2}=1\},$ $$

where the shift $[0,0,4]$ is applied for visualization.

We set sample size $n=200$ for both 2D and 3D samples.

In both experiment, the number of outliers is $\eta n=0.2n=40$.

Numerical details.
In GW, we normalize the two point clouds as

$$ $\mathbb{X}=(X,d_{X},\sum_{i=1}^{n}\frac{1}{n}\delta_{x_{i}}),\mathbb{Y}=(Y,d_{ Y},\sum_{j=1}^{n+n\eta}\frac{1}{n+n\eta}\delta_{y_{j}}).$ $$

In PGW, MPGW, UGW, we define the point clouds as

$$ $\mathbb{X}=(X,d_{X},\sum_{i=1}^{n}\frac{1}{n}\delta_{x_{i}}),\mathbb{Y}=(Y,d_{ Y},\sum_{j=1}^{n+n\eta}\frac{1}{n}\delta_{y_{j}}).$ $$

In PGW, we choose $\lambda$ such that $\lambda\geq\max(\max((C^{X})^{2}),\max((C^{Y})^{2}))$, in particular, $\lambda=10.0$.

In MPGW, we set $\rho=1.0$.

In UGW, we set $\rho_{1}=\rho_{2}=10.0$, $\epsilon=0.05$.

## Appendix O Details of Shape Retrieval Experiment

Figure: (a) Dataset I
Refer to caption: x6.png

Figure: (a) Dataset I
Refer to caption: x8.png

Figure: (a) Dataset I
Refer to caption: x10.png

Dataset details.
We test two datasets in this experiment, which we refer to as Dataset I and Dataset II. We visualize Dataset I in Figure 6(a) and Dataset II in Figure 6(b). The complete datasets can be accessed from the supplementary materials.

Numerical details.
We represent the shapes in each dataset as mm-spaces $\mathbb{X}^{i}=\left(\mathbb{R}^{2},\|\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 distances for the balanced mass constraint setting. For the remaining 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,10,100,1000,10000\}$ 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.

In computing the pairwise distances, for the PGW method, we set $\lambda$ such that $\lambda\leq\lambda_{max}=\max_{i}{(|C^{i}|^{2})}$. In particular, we compute $\lambda_{max}$ for each dataset and use $\lambda=\frac{1}{5}\lambda_{max}$ for each experiment. For UGW, we use $\varepsilon=10^{-1}$ and $\rho_{1}=\rho_{2}=1$ for both experiments. Finally, for MPGW, we set the mass-constrained term to be $\rho=\min(|\mu^{i}|,|\mu^{j}|)$ when computing the similarity between shape $\mathbb{X}^{i}$ and $\mathbb{X}^{j}$.

Performance analysis.
The pairwise distance matrices are visualized for each dataset in Figure 7, and the confusion matrices computed with each dataset are given in Figure 8. Finally, the classification accuracy with the SVM experiments is reported in Table 1(a). The results indicate that the PGW distance is able to consistently obtain high performance across both datasets.

In addition, from Figure 7, we observe that PGW qualitatively admits a more reasonable similarity measure compared to other methods. For example, in Dataset I, class “bone” and “rectangle” should have relatively smaller 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 and UGW(^*^**For UGW, this is due to the Sinkhorn regularization term.), and for the MPGW method, $MPGW(\text{bone},\text{rectangle})\approx 0$, which is also undesirable. For PGW, however, we do observe this relation. Additionally, we report the wall-clock time comparison in Table 1(b).

## Appendix P Wall-Clock Time Comparison for Partial GW Solvers

In this section, we present the wall-clock time comparison between our method Algorithms 1, 2, the Frank-Wolf algorithm proposed in [], and its Sinkhorn version [, ]. Note that these two baselines solve a mass constraint version of the PGW problem, which we refer to as the “MPGW” problem. The proposed PGW formulation in this paper can be regarded as a “Lagrangian formulation” of MPGW(^*^**Due to the non-convexity of GW, we do not have a strong duality in some of the GW representations. Thus, the Lagrangian form is not a rigorous description.) formulation to the PGW problem defined in (10).
In this paper, we call these two baselines as “MPGW algorithm” and “Sinkhorn PGW algorithm”.

Numerical details.
The data is generated as follows: let $\mu=\text{Unif}([0,2]^{2})$ and $\nu=\text{Unif}([0,2]^{3})$, we select i.i.d. samples $\{x_{i}\sim\mu\}_{i=1}^{n},\{y_{j}\sim\nu\}_{j=1}^{m}$, where $n$ is selected from $[10,50,100,150,...,10000]$ and $m=n+100$,
$\mathrm{p}=1_{n}/m,\mathrm{q}=1_{m}/m$. For each $n$, we set $\lambda=0.2,1.0,10.0$. The mass constraint parameter for the algorithm in [], and Sinkhorn is computed by the mass of the transportation plan obtained by Algorithm 1 or 2. The runtime results are shown in Figure 9.

Regarding the acceleration technique, for the POT problem in step 1, our algorithms and the MPGW algorithm apply the linear programming solver provided by Python OT package [], which is written in C++. The Sinkhorn algorithm from Python OT does not have an acceleration technique. Thus, we only test its wall-clock time for $n\leq 2000$. The data type is 64-bit float number.

From Figure 9, we can observe the Algorithms 1, 2 and MPGW algorithm have a similar order of time complexity. However, using the column/row-reduction technique for the POT computation discussed in previous sections, and the fact the convergence behaviors of Algorithms 1 and 2 are similar to the MPGW algorithm, we observe that the proposed algorithms 1, 2 admits a slightly faster speed than MPGW solver.

Figure: Figure 9: We test the wall-clock time of our Algorithm 1 and Algorithm 2, the MPGW solver (Algorithm 1 in []) , and the Sinkhorn algorithm []. We denote these methods as v1, v2, m, s respectively. The linear programming solver applied in the first three methods is from POT [], which is written in C++. The maximum number of iterations for all the methods is set to be $1000$. The maximum iteration for OT/OPT solvers is set to be $300n$. The maximum Sinkhorn iteration is set to be $1000$. The convergence tolerance for the Frank-Wolfe algorithm and the Sinkhorn algorithm are set to be $1e-5$. To achieve their best performance, the number of dummy points is set to be 1 for MPGW and PGW.
Refer to caption: x12.png

## Appendix Q 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.

## Appendix R Impact Statement

The work presented in this paper aims to advance the field of machine learning, particularly the supplementary theoretical developments and explorations of computational optimal transport. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: * Adequacy to Bregman divergences?
* Put synthetic examples in the beigning as a motivation and smooth the formal language.
soundness: 3
strengths: Nice formalization.
summary: This paper improves unbalanced approaches to the optimal transport (OT) problem. 
The objective is to compare probability measures between different metric spaces (GW distances).
To overcome the non-convexity of the  formulation, which usually relies on the Frank-Wolfe (FW) 
algorithm. 

The authors propose a new metric rooted in the so called Partial Gromov-Wasserstein (PGW) problem, 
and the main novelty is to use a total variation penalty as well as to provide efficient solvers. 

The paper commences by introducing OT and its partial extension POT.  Then, it comes out the regularization
term which in principle is the Kullback-Leibler divergence which is replaced by Total Variation (TV). 
Then, the FW algorithm is adopted. 

The toy experiment: 
"TOY EXAMPLE: SHAPE MATCHING WITH OUTLIERS
We use the moon dataset and synthetic 2D/3D spherical data in this experiment."

should be explained earlier in the paper to motivate the reader. Formal language should not be 
an enemy of intuition.

Pros: 
- Nice formal language. 

Cons:
- Not intuitive for general readers. 
- The contribution is relevant (avoid strong outliers) 

Questions:
- Is there any formalism for Bregman divergences?
weaknesses: Very hard to read even for an experienced reviewer.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: Please address the question in the weakness section.
soundness: 2
strengths: Pros:

They propose PGW, a total variation version of the UGW problem with theoretical properties analysis.

The experiment is showing their good performance in PGW.
summary: The Gromov-Wasserstein (GW) distance has drawn a lot of attention in recent years for the comparison of measures in different metric spaces. This paper focuses on the Unbalanced Gromov-Wasserstein (UGW) problem, which they called Partial Gromov-Wasserstein (PGW). They showed PGW is a well-defined metric between metric measuring spaces and discussed some theoretical properties. They designed a Frank-Wolfe algorithm-based method to solve PGW. Convergence analysis is provided. Numerically, they tested it on some datasets with existing baselines.
weaknesses: Cons:

1. The main concern is the novelty and significance since the problem itself is not well-generalizable to other problems. Meanwhile, some techniques are adopted from existing works. For example:

a. What is the unique technique of your method design compared to the Frank-Wolfe solver presented in (Chapel et al., 2020) except their problem setting is UGW?

b. How is the convergence analysis partially harder than the existing method?

c. Since the algorithm only guarantees stationary points (this is fine, the reviewer does not require a global optimality), how can we convinced it works well in more real scenarios? Is there any more evidence?



2. For the FW algorithm in the optimization problem in line 331, it’s the main subroutine in each iteration, how is the complexity of solving it? This is important in the analysis since FW usually could be dramatically slowed down by the subroutine.


3. Minor issue. There are some citation errors in lines 165 and 177.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: - The baseline selection of the experiment is too limited to demonstrate the effectiveness of your methods. Why don't you compare the methods [1,2,3] based on robust OT? Please add corresponding experiments.
- - [1] Nietert S, Goldfeld Z, Cummings R. Outlier-robust optimal transport: Duality, structure, and statistical analysis[C]//International Conference on Artificial Intelligence and Statistics. PMLR, 2022: 11691-11719.
- - [2] Wang X, Huang J, Yang Q, et al. On Robust Wasserstein Barycenter: The Model and Algorithm[C]//Proceedings of the 2024 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2024: 235-243.
- - [3] Le K, Nguyen H, Nguyen Q M, et al. On robust optimal transport: Computational complexity and barycenter computation[J]. Advances in Neural Information Processing Systems, 2021, 34: 21947-21959.
- In Wasserstein barycenter's experiment for robustness, why only show the interpolation between two shapes? Can you show me how the algorithm computes the average shape of several shapes?
- It seems that all the experiments you provide can be replaced by the equivalent of robust OT, which cannot truly reflect the advantages of robust Gromov-Wasserstein barycenter.
- Is the parameter $\lambda$ easy to search? Different proportions of noise seem to require different $\lambda$s. Does this hinder the practicality of this method? It seems that the specific $\lambda$ search process and the influence of $\lambda$ on the experimental effect are not given in the experiment.
soundness: 3
strengths: - The paper rigorously proves that PGW qualifies as a metric.
- The two Frank-Wolfe solvers for PGW demonstrate effective performance, making the method feasible for practical applications.
- Experimental results indicate that PGW outperforms traditional GW in handling unbalanced data with outliers, enhancing its utility in real-world tasks.
summary: This paper introduces the Partial Gromov-Wasserstein (PGW) metric, a novel adaptation of the Gromov-Wasserstein (GW) distance tailored for metric measure spaces. Unlike traditional GW, which requires equal mass in spaces for meaningful comparison, PGW accommodates unbalanced settings through the incorporation of a total variation penalty. The authors present theoretical results, including proof of PGW as a metric, and develop two Frank-Wolfe solvers for computational efficiency. Experiments on shape matching, retrieval, and interpolation demonstrate PGW's robustness to some extent.
weaknesses: - Comparisons with alternative unbalanced OT metrics are somewhat limited, which leaves the practical performance of PGW against state-of-the-art methods less explored.
- The robustness parameter $\lambda$ requires careful tuning, which could pose a challenge for practical applications.
- The computational efficiency of PGW may still be restrictive in high-dimensional settings or for very large datasets.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1, Please read the paper thoroughly and correct any other typos.

2, Is the proposed Algorithm 1 the same as Algorithm 1 in the paper "Partial Optimal Transport with Applications on Positive-Unlabeled Learning"? What are the novelties in the optimization algorithms?
soundness: 4
strengths: 1, The main contribution is to establish the metric property of partial GW. 

2, Simulations in subsection 6.2 clearly demonstrate improved performance of PGW compared to MPGW.

2, The simulation examples are interesting and illustrative.
summary: The Gromov-Wasserstein (GW) distance is a metric on probability measures supported on different metric spaces. This paper extends this notion to more general Radon measures, not necessarily probability measures, termed partial Gromov-Wasserstein (PGW) distance. The authors show that PGW is indeed a metric. Two Frank-Wolfe (FW) algorithms are proposed to compute PGW, and three examples are provided to illustrate the performance of PGW.
weaknesses: 1, The current manuscript has many typos. For example, the citations on lines 165 and 177 are not displaying properly.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. Could the authors incorporate other experiments, such as PU learning (positive-unlabeled learning), to provide a broader evaluation?
  
2. Could the authors report the results of varying hyperparameters in the baselines to examine their impact on performance?
  
3. While the KL divergence in UGW is not a rigorous metric, it has desirable properties such as robustness to outliers. Could the authors explain why the TV norm used in PGW results in better performance in the numerical experiments compared to UGW? Alternatively, is the improved performance due to the use of the Frank-Wolfe (FW) algorithm instead of Sinkhorn?
soundness: 3
strengths: 1. This paper is well-written and easy to follow.
  
2. The paper rigorously proves that PGW, a specific case of UGW with the TV norm as the chosen $f$-divergence, defines a valid metric between mm-spaces, contributing to the theoretical understanding of these transport frameworks.
  
3. The authors propose using the Frank-Wolfe algorithm to solve the PGW problem and provide a convergence guarantee, enhancing the computational tractability of the method.
summary: This paper introduces Partial Gromov-Wasserstein (PGW), a particular case of UGW, and prove that it is a metric between mm-spaces. The authors propose Frank-Wolfe-based algorithms with convergence guarantees for solving the PGW problem and extend the concept of barycenters to mm-spaces. PGW’s effectiveness is demonstrated through applications like shape matching, retrieval, and interpolation, showing improved performance over existing baselines.
weaknesses: 1. Limited Experimental Scope: The experimental evaluation in this paper could be expanded. It might be helpful to include experiments on PU learning (positive-unlabeled learning), similar to those conducted in the UGW paper, for a more comprehensive comparison.
  
2. Hyperparameter Tuning in Baselines: For the toy examples and point cloud matching experiments, the baselines' performance might improve with more thorough hyperparameter tuning since authors use fixed values mentioned in Appendix N. Given that UGW has been shown to be robust to outliers both theoretically and empirically (as demonstrated in the original UGW paper and also [A]), better-tuned baselines could potentially mitigate the impact of outliers more effectively in these experiments.

3. Minor Issues: Several broken references and citations are present in the paper, such as those on lines 165-166, 894, and 1025. Addressing these would improve the paper's readability and professionalism.


[A] Tran, Quang Huy, et al. "Unbalanced co-optimal transport." *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 37. No. 8. 2023.

Meta-review: The paper is a nice contribution, introducing the Partial Gromov-Wasserstein (PGW) metric, which addresses limitations in existing Gromov-Wasserstein formulations for unbalanced settings. The authors provide rigorous theoretical guarantees, such as proving that PGW is a well-defined metric, and propose two effective solvers with convergence guarantees. Some reviewers raised concerns about the experimental assumptions, particularly regarding the equivalence of UOT-based approaches and PGW in practice, and the effect of entropy regularization. The authors adequately addressed these concerns by clarifying the role of regularization and demonstrating PGW’s superior robustness through additional experiments. Overall, the paper’s theoretical depth, algorithmic design, and experimental validation make it a valuable addition to the field, justifying acceptance.

Decision: Accept (Poster)