Partial Gromov Wasserstein Metric

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:03:04

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

Main paper: 
 introduction: 
 The classical optimal transport (OT) problem [1] 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 [2, 3] to domain adaptation [4] and representation learning [5] .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 [6] and partial OT [7] , and 2) enabling the comparison of probability measures across distinct metric spaces through Gromov-Wasserstein distances [8] , with applications spanning from quantum chemistry [9] to natural language processing [10] .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 [11] . 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 [7, 12, 13, 14] , Kantorovich-Rubinstein norm [15, 16, 17] , and the Hellinger-Kantorovich distance [18, 19] . These methods fall under the broad category of "unbalanced optimal transport". In this regard, we also highlight [20, 21, 22] , which enhance OT's robustness in the presence of outliers.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.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 [23, 24] , to graph partitioning and matching problems [25] . 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 [8, 24] as an adaptation of the Gromov-Hausdorff distance, which measures the discrepancy between two metric spaces [26, 27, 28, 29] . The GW distance [8, 30] 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 [8] . The conventional computational approach relies on the Frank-Wolfe (FW) algorithm [31, 32] . Optimal transport (OT) computational methods [15, 33, 34, 35, 36, 37, 38, 39, 40] , such as the Sinkhorn algorithm, can be incorporated into FW iterations, which yields the classical GW solvers [41, 42, 43] .Given that the GW distance is limited to the comparison of probability mm-spaces, recent works have introduced unbalanced and partial variations [44, 45, 46] . These variations have been applied in diverse contexts, including partial graph matching for social network analysis [47] and the alignment of brain images [48] . 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 [44] , which we named the Partial Gromov-Wasserstein (PGW) problem. In contrast to [44] , 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 [12] , 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 [32] , we prove that similar to the Frank-Wolfe solver presented in [45] , 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. 
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 [12] . We then introduce the GW distance.Let Ω ⊆ R d be, for simplicity, a compact subset of R d , and P(Ω) be the space of probability measures defined on the Borel σ-algebra of Ω.The Optimal Transport (OT) problem for µ, ν ∈ P(Ω), with transportation cost c(x, y) : Ω × Ω → R + being a lower-semi continuous function, is defined as:OT (µ, ν) := min γ∈Γ(µ,ν) γ(c),where γ(c) := Ω 2 c(x, y) dγ(x, y)and where Γ(µ, ν) denotes the set of all joint probability measures on Ω 2 := Ω × Ω with marginals µ, ν, i.e., γ 1 := π 1# γ = µ, γ 2 := π 2# γ = ν, where π 1 , π 2 : Ω 2 → Ω are the canonical projections π 1 (x, y) := x, π 2 (x, y) := y. A minimizer for (1) always exists [1, 49] and when c(x, y) = ∥x-y∥ p , for p ≥ 1, it defines a metric on P(Ω), which is referred to as the "p-Wasserstein distance":W p p (µ, ν) := min γ∈Γ(µ,ν) Ω 2 ∥x -y∥ p dγ(x, y).(2)The Partial Optimal Transport (POT) problem [6, 13, 50] extends the OT problem to the set of Radon measures M + (Ω), i.e., non-negative and finite measures. For λ > 0 and µ, ν ∈ M + (Ω), the POT problem is defined as:EQUATIONwhere, in general, |σ| denotes the total variation norm of a measure σ, i.e., |σ| := σ(Ω). The constraint γ ∈ M + (Ω 2 ) in ( 3) can be further restricted to γ ∈ Γ ≤ (µ, ν):Γ ≤ (µ, ν) := {γ ∈ M + (Ω 2 ) : γ 1 ≤ µ, γ 2 ≤ ν},denoting γ 1 ≤ µ if for any Borel set B ⊆ Ω, γ 1 (B) ≤ µ(B) (respectively, for γ 2 ≤ ν) [7] . Roughly speaking, the linear penalization indicates that if the classical transportation cost exceeds 2λ, it is better to create/destroy' mass (see [40] for further details).The relationship between POT and OT. By using the techniques in [12] , 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. [12, 40] Given µ, ν ∈ M + (Ω), construct the following measures on Ω := Ω∪{ ∞}, for an auxiliary point ∞: EQUATIONThen, there exists a bijection F : Γ ≤ (µ, ν) → Γ(μ, ν) given byEQUATIONsuch that γ is optimal for the POT problem (3) if and only if F (γ) is optimal for the OT problem (5) .It is worth noting that instead of considering the same underlying space Ω for both measures µ and ν, the OT and POT problems can be formulated in the scenario where µ and ν are defined on different metric spaces X and Y , respectively. In this setting, one needs a cost function c : X × Y → R + to formulate the OT and POT problems. However, in practice it is usually difficult to define reasonable 'distance' or ground cost c(•, •) between the two spaces X and Y . In particular, the p-Wasserstein distance cannot be adopted if µ, ν are defined on different spaces. To relax this requirement, in the next section, we will review the fundamentals of the Gromov-Wasserstein problem [8] .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 µ. As in [8, Ch.5], we will assume that X is compact and that supp(µ) = X. Given two probability mm-spacesX = (X, d X , µ), Y = (Y, d Y , ν), with µ ∈ P(X) and ν ∈ P(Y ), and a non-negative lower semi-continuous cost function L : R 2 → R + (e.g., the Euclidean distance or the KL-loss), the Gromov-Wasserstein (GW) matching problem is defined as:EQUATIONwhere, for brevity, we employ the notation γ ⊗2 for the product measure dγ ⊗2 ((x, y),(x ′ , y ′ )) = dγ(x, y)dγ(x ′ , y ′ ). If L(a, b) = |a-b| p , for 1 ≤ p < ∞, we denote GW L (•, •) simply by GW p (•, •).In this case, the expression (7) defines an equivalence relation ∼ among probability mm-spaces, i.e., X ∼ Y if and only if GW p (X, Y) = 01 . 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 ∼. For details, we refer to [8, Ch. 5 and 10]. 
the partial gromov-wasserstein (pgw) problem: 
 The Unbalanced Gromov-Wasserstein (UGW) problem for general (compact) mm-spaces [44] is defined as:X = (X, d X , µ), Y = (Y, d Y , ν), with µ ∈ M + (X), ν ∈ M + (Y ), studied inEQUATIONwhere λ > 0 is a fixed linear penalization parameter, and D ϕ is a Csiszár or ϕ-divergence. The above formulation extends the classical GW problem (7) into the unbalanced setting (µ and ν are no longer necessarily probability measures but general Radon measures).We underline two points: First, as discussed in [44] , while the above quantity allows us to 'compare' the mm-spaces X and Y, its metric property is unclear. Secondly, when D ϕ is the KL divergence, aSinkhorn solver has been proposed in [44] . However, a solver for general ϕ-divergences has not yet been proposed.In this paper, we will analyze the case when D ϕ is the total variation norm. Specifically, for q ≥ 1, we consider the following problem, which we refer to as the Partial Gromov-Wasserstein (PGW) problem:EQUATIONRemark 3.1. Given γ ∈ Γ ≤ (µ, ν), the above cost functional can be rewritten asγ ⊗2 (L(d q X , d q Y )) + λ(|µ ⊗2 -γ ⊗2 1 | + |ν ⊗2 -γ ⊗2 2 |) = γ ⊗2 (L(d q X , d q Y ) -2λ) + λ |µ| 2 + |ν| 2 does not depend on γ . Proposition 3.2. Given mm-spaces X = (X, d X , µ), Y = (Y, d Y , ν), the minimization problem (9)can be restricted to the setEQUATIONFor the proof, inspired by [50] , we direct the reader to Appendix B.We notice that a similar Partial Gromov-Wasserstein problem (and its solver) has been studied [45] .Indeed, in [45] , the λ-penalization in the optimization problem (10) is avoided, but the constraint set is replaced by the subset of all γ ∈ Γ ≤ (µ, ν) such that |γ| = ρ for a fixed ρ ∈ [0, min{|µ|, |ν|}]. 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 N, O, P, we analyze the performance of the different solvers through different experiments. ) , we use P GW p λ,q to denote P GW L λ,q . In this case, (9) and (10) admit a minimizer.Proposition 3.3. If L(r 1 , r 2 ) = |r 1 -r 2 | p , for p ∈ [1, ∞The proof is given in Appendix C: Its idea extends results from [8] 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.Proposition 3.4. Let λ > 0, 1 ≤ q, p < ∞ and L(r 1 , r 2 ) = |r 1 -r 2 | p . Then (P GW p λ,q (•, •)) 1/pdefines 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-spacesX = (X, d X , µ), Y = (Y, d Y , ν), that is, |µ| = |ν| = 1. Assume that L is a continuous funtion. Then lim λ→∞ P GW L λ,1 (X, Y) = GW L (X, Y). 
computation of the partial gw distance: 
 In the discrete setting, consider mm-spaces X = (X, d X ,n i=1 p X i δ xi ), Y = (Y, d Y , m j=1 q Y j δ yj ),where X = {x 1 , . . . , x n }, Y = {y 1 , . . . , y m }, the weights p X i , q Y j are non-negative numbers, andEQUATIONLet p := [q X 1 , . . . , q X n ] ⊤ and q := [q Y 1 , . . . , q Y m ] ⊤ denote the weight vectors corresponding to the given discrete measures. We view the sets of transportation plans Γ(p, q) and Γ ≤ (p, q) for the GW and PGW problems, respectively, as the subsets of n × m matricesEQUATIONfor any pair of non-negative vectors p ∈ R n + , q ∈ R m + , where 1 n is the vector with all ones in R n (resp. 1 m ), and γ1 m ≤ p means that component-wise the ≤ relation holds.Given by a non-negative function L : R n×n × R m×m → R + , he transportation cost M and the 'partial' transportation con M are represented by the n × m × n × m tensors:EQUATIONwhere 1 n,m,n,m is the tensor with ones in all its entries. For each n × m × n × m tensor M and each n × m matrix γ, we define tensor-matrix multiplicationM • γ ∈ R n×m by (M • γ) ij = i ′ ,j ′ (M i,j,i ′ ,j ′ )γ i ′ ,j ′ .Then, the Partial GW problem in (10) can be written asEQUATIONEQUATIONand ⟨•, •⟩ F stands for the Frobenius dot product. The constant term λ(|p| 2 + |q| 2 ) will be ignored in the rest of this paper since it does not depend on γ.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 [32] to our context, showing that the FW algorithm achieves a stationary point at a rate of O(1/ √ 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 byEQUATION)The classical method to compute M • γ is the following: First, convert M into an (n × m) × (n × m) matrix, denoted as v(M ), and convert γ into an (n × m) × 1 vector v(γ). Then, the computation of M • γ is equivalent to the matrix multiplication v(M )v(γ). The computational cost and the Algorithm 1: Frank-Wolfe Algorithm for PGW, ver 1Input: µ = n i=1 p X i δ xi , ν = m j=1 q Y j δ yj , γ (1) Output: γ (f inal) Compute C X , C Y for k = 1, 2, . . . do G (k) ← 2 M • γ (k) // Compute gradient γ (k) ′ ← arg min γ∈Γ ≤ (p,q) ⟨G (k) , γ⟩ F // Solve the POT problem. Compute α (k) ∈ [0, 1] via (18) // Line search γ (k+1) ← (1 -α (k) )γ (k) + α (k) γ (k) ′ // Update γ if convergence, break end for γ (f inal) ← γ (k)required storage space are O(n 2 m 2 ). In certain conditions, the above computation can be reduced to O(n 2 + m 2 ). We refer to Appendices F and H for details.Next, we aim to solve the following problem:γ (k) ′ ← arg min γ∈Γ ≤ (p,q) ⟨∇L M (γ (k) ), γ⟩ F ,which is a discrete POT problem since it is equivalent tomin γ∈Γ ≤ (p,q) ⟨2M • γ (k) , γ⟩ F + λ|γ (k) |(|p| + |q| -2|γ|).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:α (k) = arg min α∈[0,1] {L M ((1 -α)γ (k) + αγ (k) ′ )}.The optimal α (k) takes the following values (see Appendix I for details):Let α (k) =    0 if a ≤ 0, a + b > 0, 1 if a ≤ 0, a + b ≤ 0, clip( -b 2a , [0, 1]) if a > 0,whereEQUATIONand clip( -b 2a , [0, 1]) = min{max{-b 2a , 0}, 1}.Step 3: Updateγ (k+1) ← (1 -α (k) )γ (k) + α (k) γ (k) ′ .The initial guess, γ (1) . In the GW problem, the initial guess is simply set to γ (1) = pq ⊤ if there is no prior knowledge. In PGW, however, as µ, ν may not necessarily be probability measures (i.e., i p X i , j q Y j ̸ = 1 in general), we set γ (1) = pq ⊤ max(|p|,|q|) . It is straightforward to verify that γ (1) ∈ Γ ≤ (p, q) as γ (1) 1 m = |q|p max(|p|, |q|) ≤ p, γ (1)⊤ 1 n = |p|q max(|p|, |q|) ≤ 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 [40] ), during the POT solving step, for each i ∈ [1 : n] (or j ∈ [1 : m]), if the i th row (j th column) of M • γ (k) contains a non-negative entry, all the mass of p X i (q Y j ) will be destroyed (created). Thus, we can remove the corresponding row (column) to improve the computational efficiency. 
experiments: 
 In addition to the three experiments detailed here, we also perform a wall-clock time comparison of our proposed PGW solvers in Appendix O and a positive-unlabeled (PU) learning experiment in Appendix P.We use the moon dataset and synthetic 2D/3D spherical data in this experiment. Let {x i } n i=1 , {y j } n j=1 denote the source and target point clouds. In addition, we add ηn (where η = 20%) outliers to the target point cloud. See Figure 1 for visualization.We visualize the transportation plans given by the GW [8] , MPGW [45] , UGW [44] , 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. 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.Experiment setup. We now employ the PGW distance to distinguish between 2D shapes, as done in [51] , and use GW, MPGW, and UGW as baselines for comparison. Given a series of 2D shapes, we represent the shapes as mm-spacesX i = (R 2 , ∥ • ∥ 2 , µ i ), where µ i = n i k=1 α i δ x i k .For the GW method, we normalize the mass for the balanced mass constraint setting (i.e. α i = 1 n i ), and for the remaining methods we let α i = α for all the shapes, where α > 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 [51, 52] , 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(-σ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 [51] , consisting of 20 shapes in Hence, the final dataset consists of 160 shapes across 8 total classes. This dataset is visualized in Figure 6a .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 6b .Performance analysis. We refer to Appendix N 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 1a .In addition, we report the wall-clock time required to compute all pairwise distances for each distance in Table 1b . We observe that GW, MPGW, and PGW have similar wall-clock times across both experiments (30-50 seconds for Dataset I, 80-140 seconds for Dataset II), with PGW admitting a slightly faster runtime in both cases. Meanwhile, UGW requires almost 1500 seconds on the experiment with Dataset I and over 500 seconds on the experiment with Dataset II.By [41] , 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 X 1 , . . . , X K , whereEQUATIONwhere each γ k ∈ Γ ≤ (p, 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 shapesX = {x i } n i=1 ⊂ R d1 and Y = {y i } m i=1 ⊂ R d2 , modeled as mm-spaces X = (X, ∥ • ∥ R d 1 , n i=1 δ xi ) and Y = (Y, ∥ • ∥ R d 2 ,m i=1 δ yi ), we wish to find interpolations between them. In addition, we assume Y is corrupted by noise, i.e., Y is redefined asY = ( Ỹ , ∥ • ∥ R d 2 , m i=1 δ yi + mη i=1 δ ỹi ) with Ỹ = Y ∪ {ỹ i } m i=1, where η ∈ [0, 1] is the noise level and each ỹi is randomly selected from a particular region R ⊂ R d2 .Dataset setup. We adapt the dataset given in [41] . See Appendix M.1 for further details on the dataset. In this experiment, we test η = 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 X and the target 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. 
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 PGW admits a more robust result when the data are corrupted by outliers/noisy data.• OT: Optimal Transport.• POT: Partial Optimal Transport.• GW: Gromov-Wasserstein.• PGW: Partial Gromov-Wasserstein.• FW: Frank-Wolfe.• MPGW: Mass-Constrained Partial Gromov-Wasserstein.• ∥ • ∥: Euclidean norm.• X 2 = X × X.• M + (X): set of all positive (non-negative) Randon (finite) measures defined on X.• P 2 (X): set of all probability measures defined on X, whose second moment is finite.• R + : set of all non-negative real numbers.• R n×m : set of all n × m matrices with real coefficients.• R n×m + (resp. R n + ): set of all n × m matrices (resp., n-vectors) with non-negative coefficients.• R n×m×n×m : set of all n × m × n × m tensors with real coefficients.• 1 n , 1 n×m , 1 n×m×n×m : vector, matrix, and tensor of all ones.• 1 E : characteristic function of a measurable set E1 E (z) = 1 if z ∈ E, 0 otherwise. • X, Y: metric measure spaces (mm-spaces): X = (X, d X , µ), Y = (Y, d Y , ν). • C X : given a discrete mm-space X = (X, d X , µ), where X = {x 1 , . . . , x n }, the symmetric matrix C X ∈ R n×n is defined as C X i,i ′ = d q X (x i , x ′ i ).• µ ⊗2 : product measure µ ⊗ µ.• T # σ: T : X → Y is a measurable function and σ is a measure on X. T # σ is the pushforward measure of σ, i.e., its is the measure on Y such that for all Borel set A ⊂ Y ,T # σ(A) = σ(T -1 (A)).• γ, γ 1 , γ 2 : γ is a joint measure defined in a product space having γ 1 , γ 2 as its first and second marginals, respectively. In the discrete setting, they are viewed as matrices and vectors, i.e.,EQUATIONγ 1 = γ1 m ∈ R n + , γ 2 = γ ⊤ 1 n ∈ R m + .• π 1 : X ×Y → X, canonical projection mapping, with (x, y) → x. Similarly, π 2 : X ×Y → Y is canonical projection mapping, with (x, y) → y.• π 1,2 : S × X × Y → X × Y , canonical projection mapping, with (s, x, y) → (x, y).Similarly, π 0,1 maps (s, x, y) to (s, x); π 0,2 maps (s, x, y) to (s, y).• Γ(µ, ν), where µ ∈ P 2 (X), ν ∈ P 2 (Y ) (where X, Y may not necessarily be the same set):it is the set of all the couplings (transportation plans) between µ and ν, i.e., Γ(µ, ν):= {γ ∈ P 2 (X × Y ) : γ 1 = µ, γ 2 = ν}.• Γ(p, q): set of all the couplings between the discrete probability measures µ =EQUATION)That is, Γ(p, q) coincides with Γ(µ, ν), but it is viewed as a subset of n × m matrices defined in (12) .• p, q: real numbers 1 ≤ p, q < ∞.• p, q: vectors of weights as in (20) .• p = [p 1 , . . . , p n ] ≤ p ′ = [p ′ 1 , . . . , p ′ n ] if p j ≤ p ′ j for all 1 ≤ j ≤ n. • |p| = n i=1 p i for p = [p 1 , . . . , p n ].• c(x, y) : X × Y → R + denotes the cost function used for classical and partial optimal transport problems. lower-semi continuous function.• OT (µ, ν): it is the classical optimal transport (OT) problem between the probability measures µ and ν defined in (1).• W p (µ, ν): it is the p-Wasserstein distance between the probability measures µ and ν defined in (2), for 1 ≤ p < ∞.• P OT (µ, ν; λ): the Partial Optimal Transport (OPT) problem defined in (3).• |µ|: total variation norm of the positive Randon (finite) measure µ defined on a measurable space X, i.e., |µ| = µ(X).• µ ≤ σ: denotes that for all Borel set B ⊆ X we have that the measures µ, σ ∈ M + (X)satisfy µ(B) ≤ σ(B). • Γ ≤ (µ, ν), where µ ∈ M + (X), ν ∈ M + (Y ): set of all "partial transportation plans"Γ ≤ (µ, ν) := {γ ∈ M + (X × Y ) : γ 1 ≤ µ, γ 2 ≤ ν}.• Γ ≤ (p, q): set of all the "partial transportation plans" between the discrete probabilitymeasures µ = n i=1 p X i δ xi and ν = m j=1 q Y j δ yj with weight vectors p = [p X 1 , . . . , p X n ] and q = [q Y 1 , . . . , q Y m ]. That is, Γ ≤ (p, q) coincides with Γ ≤ (µ, ν), but it is viewed as a subset of n × m matrices defined in (13) .• λ > 0: positive real number.• ∞: auxiliary point.• X = X ∪ { ∞}.• μ, ν: given in (4).• p, q: given in (53).• γ: given in (6).• ĉ(•, •) : X × Ŷ → R + : cost as in (5) .• L : R × R → R: cost function for the GW problems.• D : R × R → R: generic distance on R used for GW problems.• GW L (•, •): GW optimization problem given in (7) .• GW p (•, •): GW optimization problem given in (7) when L(a, b) = |a -b| p .• GW L q (•, •): general GW optimization problem for g ≥ 1 given in (33) .• GW p q (•, •): general GW optimization problem for q ≥ 1 and L(a, b) = |a -b| p given in (34) .• GW p λ,q (•, •): generalized GW problem given in (39) .• GW : GW-variant problem given in (51) for the general case, and in (55) for the discrete setting.• L: cost given in ( 16) for the GW-variant problem.• d : X × X → R + ∪ {∞}: "generalized" metric given in (50) for X.• X ∼ Y: equivalence relation in for mm-spaces, X ∼ Y if and only if they have the same total mass and GW p q (X, Y) = 0.• P GW L λ,q (•, •): partial GW optimization problem given in (9) or, equivalently, in (10) .• P GW p λ,q (•, •): partial GW optimization problem given in (10) when L(a, b) = |a -b| p .• P GW λ (•, •): is is the PGW problem P GW p λ,q (•, •) for the case when p = 2 = q.• µ(ϕ): given a measure µ and a function ϕ, µ(ϕ) := ϕ(x)dµ(x).• C(γ; λ, µ, ν): the transportation cost induced by transportation plan γ ∈ Γ ≤ (µ, ν) in the Partial GW problem 10,C(γ; λ, µ, ν) := γ ⊗2 (L(d q X , d q Y )) + λ(|µ| 2 + |ν| 2 -2|γ| 2 ). • L: functional for the optimization problem P GW λ (•, •).• M , M , and M : see (14) , and (54) . Notice that, (M -2λ) i,i ′ ,j,j ′ := M i,i ′ ,j,j ′ -2λ.• ⟨•, •⟩ F : Frobenius inner product for matrices, i.e., ⟨A,B⟩ F = trace(A ⊤ B) = n,m i,j A i,j B i,j for all A, B ∈ R n×m .• M • γ: product between the tensor M and the matrix γ.• ∇: gradient.• [1 : n] = {1, . . . , n}.• α: step size based on the line search method.• γ (1) : initialization of the algorithm.• γ (k) , γ (k) ′ : previous and new transportation plans before and after step 1 in the k-th iteration of version 1 of our proposed FW algorithm.• γ(k) , γ(k) ′ : previous and new transportation plans before and after step 1 in the k-th iteration of version 2 of our proposed FW algorithm. • (δγ, a, b) and (δγ, a, b): given in ( 18) and ( 56) for versions 1 and 2 of the algorithm, respectively.• G = 2 M • γ, Ĝ = 2 M • γ: Gradient of• C 1 -function: continuous and with continuous derivatives.• M P GW ρ (•, •): Mass-Constrained Partial Gromov-Wasserstein defined in (73)• Γ ρ ≤ (µ, ν): set transport plans defined in (74) for the Mass-Constrained Partial Gromov-Wasserstein problem.• Γ P U,π (p, q): defined in (87).The idea of the proof is inspired by the proof of Proposition 1 in [50] .The goal is to verify thatEQUATION)Consider γ ∈ M + (X × Y ) such that γ 1 ≤ µ does not hold. Then we can write the Lebesgue decomposition of γ 1 with respect to µ:γ 1 = f µ + µ ⊥ ,where f ≥ 0 is the Radon-Nikodym derivative of γ 1 with respect to µ, and µ ⊥ , µ are mutually singular, that is, there exist measurable sets A, B such thatA ∩ B = ∅, X = A ∪ B and µ ⊥ (A) = 0, µ(B) = 0.Without loss of generality, we can assume that the support of f lies on A, sinceγ 1 (E) = E∩A f (x) dµ(x) + µ ⊥ (E ∩ B) ∀E ⊆ X measurable. Define A 1 = {x ∈ A : f (x) > 1}, A 2 = {x ∈ A : f (x) ≤ 1} (both are measurable, since f is measurable), and define μ = min{f, 1}µ. Then, μ ≤ µ and μ ≤ f µ ≤ f µ + µ ⊥ = γ 1 .There exists a γ ∈ M + (X × Y ) such that γ1 = μ, γ ≤ γ, and γ2 ≤ γ 2 . Indeed, we can construct γ in the following way: First, let {γ x } x∈X be the set of conditional measures (disintegration) such that for every measurable (test) function ψ : X × Y → R we haveψ(x, y) dγ(x, y) = X Y ψ(x, y) dγ x (y) dγ 1 (x).Then, define γ asγ(U ) := X Y 1 U (x, y) dγ x (y) dμ(x) ∀U ⊆ X × Y Borel.Then, γ verifies that γ1 = μ, and since μ ≤ γ 1 , we also have that γ ≤ γ, which implies γ2 ≤ γ 2 .Since|γ 1 | = |γ 2 | and |γ 1 | = |γ 2 |, then we have |γ ⊗2 1 -γ⊗2 1 | = |γ ⊗2 2 -γ⊗2 2 |.We claim thatEQUATION• Left-hand side of (22): Since {A, B} is a partition of X, we first spit the left-hand side of (22) as|µ ⊗2 -γ ⊗2 1 | = (µ ⊗2 -γ ⊗2 1 )(A × A) (I) + (µ ⊗2 -γ ⊗2 1 )(A × B) + (µ ⊗2 -γ ⊗2 1 )(B × A) (II) + (µ ⊗2 -γ ⊗2 1 )(B × B) (III).Then we have(III) = (µ ⊗2 -γ ⊗2 1 )(B × B) = µ ⊥ ⊗ µ ⊥ (B × B) = |µ ⊥ | 2 , (II) = (µ ⊗2 -γ ⊗2 1 )(A × B) + (µ ⊗2 -γ ⊗2 1 )(B × A) = 2|µ ⊥ |(µ -γ 1 )(A). Since γ 1 = f µ in A, then γ1 = γ 1 in A 2 and γ1 = µ in A 1 , so we have (µ -γ 1 )(A) = (µ -γ 1 )(A 1 ) + (µ -γ 1 )(A 2 ) = (γ 1 -γ1 )(A 1 ) + (µ -γ1 )(A 2 ) = (γ 1 -γ1 )(A) + (µ -γ1 )(A).Thus,(II) = 2|µ ⊥ |((γ 1 -γ1 )(A) + (µ -γ1 )(A)),and we also get that(I) = (µ ⊗2 -γ ⊗2 1 )(A × A) = (µ ⊗2 -γ ⊗2 1 )(A 1 × A 1 ) + (µ ⊗2 -γ ⊗2 1 )(A 2 × A 2 ) + (µ ⊗2 -γ ⊗2 1 )(A 1 × A 2 ) + (µ ⊗2 -γ ⊗2 1 )(A 2 × A 1 ) = (γ ⊗2 1 -γ⊗2 1 )(A 1 × A 1 ) + (µ ⊗2 -γ⊗2 1 )(A 2 × A 2 )+ + |γ 1 ⊗ µ -γ 1 ⊗ γ1 |(A 1 × A 2 ) + |µ ⊗ γ1 -γ1 ⊗ γ 1 |(A 2 × A 1 ) = (γ ⊗2 1 -γ⊗2 1 )(A 1 × A 1 ) + (µ ⊗2 -γ⊗2 1 )(A 2 × A 2 ) + 2(γ 1 -γ 1 )(A 1 )(µ -γ1 )(A 2 ) = (γ ⊗2 1 -γ⊗2 1 )(A × A) + (µ ⊗2 -γ⊗2 1 )(A × A) + 2(γ 1 -γ 1 )(A 1 )(µ -γ1 )(A 2 ) ≥0 .• Right-hand side of (22): First notice that(γ 1 -γ1 )(B) = (γ 1 -γ1 )(B) ≤ γ 1 (B) = |µ ⊥ |,and since γ1 ≤ µ and µ(B) = 0, we have(µ -γ1 )(B) = 0.Then,|µ ⊗2 -γ⊗2 1 | + |γ ⊗2 1 -γ⊗2 1 | = = (µ ⊗2 -γ⊗2 1 )(A × A) + (γ ⊗2 1 -γ⊗2 1 )(A × A) + (µ ⊗2 -γ⊗2 1 )(B × B) + (γ ⊗2 1 -γ⊗2 1 )(B × B) + (µ ⊗2 -γ⊗2 1 )(A × B) + (γ ⊗2 1 -γ⊗2 1 )(A × B) + (µ ⊗2 -γ⊗2 1 )(B × A) + (γ ⊗2 1 -γ⊗2 1 )(B × A) ≤ (µ ⊗2 -γ⊗2 1 )(A × A) + (γ ⊗2 1 -γ⊗2 1 )(A × A) ≤(I) + |µ ⊥ | 2 =(III) + 2|µ ⊥ |(γ 1 -γ1 )(A) =(II).Thus, (22) holds.We finish the proof of the proposition by noting that|µ ⊗2 -γ⊗2 1 | + |ν ⊗2 -γ⊗2 2 | ≤ |µ ⊗2 -γ ⊗2 1 | -|γ ⊗2 1 -γ⊗2 1 | + |ν ⊗2 -γ⊗2 2 | = |µ ⊗2 -γ ⊗2 1 | -|γ ⊗2 2 -γ⊗2 2 | + |ν ⊗2 -γ⊗2 2 | ≤ |µ ⊗2 -γ ⊗2 1 | + |ν ⊗2 -γ ⊗2 2 |where the first inequality follows from (22) , and the second inequality holds from the fact the total variation norm | • | satisfies triangular inequality. Therefore γ induces a smaller transport GW cost than γ (since γ ≤ γ), and also γ decreases the mass penalty in comparison that corresponding to γ. Thus, γ is a better GW transportation plan, which satisfies γ1 ≤ µ. Similarly, we can further construct γ′ based on γ such that γ′ 1 ≤ µ, γ′ 2 ≤ ν. Therefore, we can restrict the minimization in ( 9)from M + (X × Y ) to Γ ≤ (µ, ν).Thus, the equality ( 21) is satisfied.Proof of Remark 3.1. Given γ ∈ Γ ≤ (µ, ν), since γ 1 ≤ µ, γ 2 ≤ ν, and γ 1 (X) = |γ 1 | = |γ| = |γ 2 | = γ 2 (Y ), we have |µ ⊗2 -γ ⊗2 1 | + |ν ⊗2 -γ ⊗2 2 | = µ ⊗2 (X 2 ) -γ ⊗2 1 (X 2 ) + ν ⊗2 (Y 2 ) -γ ⊗2 2 (Y 2 ) = |µ| 2 + |ν| 2 -2|γ| 2 ,and so the transportation cost in partial GW problem (10) becomesEQUATION)C Proof of Proposition 3.3In this section, we discuss the minimizer of the Partial GW problem (9) . Trivially, Γ ≤ (µ, ν) ⊆ M + (X × Y ) and by using Proposition 3.2 it is enough to show that a minimizer for problem (10) exists.We refer the reader to [8, Chapters 5 and 10] for similar ideas.Suppose X, Y are compact sets, then exists compact set [0, β] ⊂ R, such thatd(x, x ′ ), d(y, y ′ ) ∈ [0, β], ∀x, x ′ ∈ X, y, y ′ ∈ Y Let A = [0, β q ]. Let L A 2 denote the restriction of L on A 2 , i.e. L A 2 : A 2 → R with L A 2 (r 1 , r 2 ) = L(r 1 , r 2 ), ∀r 1 , r 2 ∈ A. Suppose L satisfies the following: there exists 0 < K < ∞ such that for every r 1 , r ′ 1 , r 2 , r ′ 2 ∈ A,|L A 2 (r 1 , r 2 ) -L A 2 (r ′ 1 , r 2 )| ≤ K|r 1 -r ′ 1 |, |L A 2 (r 1 , r 2 ) -L A 2 (r 1 , r ′ 2 )| ≤ K|r 2 -r ′ 2 | (24) (i.e., L A 2 is Lipschitz on each variable). Then P GW L λ (•, •) 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 ≤ p < ∞, then L satisfies the condition (24).Proof. Assume that L is defined on an interval of the form [0, M ], for some M > 0. Considerr 1 , r ′ 1 , r 2 , r ′ 2 ∈ [0, M ]. If p = 1, by triangle inequality we have|L(r 1 , r 2 ) -L(r ′ 1 , r 2 )| = ||r 1 -r 2 | -|r ′ 1 -r 2 || ≤ |r 1 -r ′ 1 | and similarly, |L(r 1 , r 2 ) -L(r 1 , r ′ 2 )| ≤ |r 2 -r ′ 2 |. From [8, page 473], since for 1 ≤ p < ∞, the function t → t p , for t ∈ [0, M ], is Lipschitz with constant bounded by pM p-1 , we have |L(r 1 , r 2 ) -L(r ′ 1 , r 2 )| ≤ pM p-1 |r 1 -r ′ 1 |. and similarly, |L(r 1 , r 2 ) -L(r 1 , r ′ 2 )| ≤ pM p-1 |r 2 -r ′ 2 |. Lemma C.2. Given q ≥ 1, consider β > 0. Then [0, β] ∋ c → c q ∈ [0, β q ] is a Lipschitz function.Proof. Given c 1 , c 2 ∈ [0, β], we haveEQUATIONThus, c → c q is a Lipschitz function.If a sequence {γ n } converges weakly to γ, we write γ n w ⇀ γ. In this setting, if γ n w ⇀ γ, it does not imply that (γ n ) ⊗2 w ⇀ γ ⊗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 [8] , we introduce the following lemma.Lemma C.3. Given metric space (Z, d Z ), suppose ϕ : R 2 → R is a Lipschitz continuous function with respect to (Z 2 , d + Z ), where d + Z ((z 1 , z 2 ), (z ′ 1 , z ′ 2 )) := d Z (z 1 , z ′ 1 ) + d Z (z 2 , z ′ 2 ), ∀(z 1 , z 2 ), (z ′ 1 , z ′ 2 ) ∈ Z 2 . Given γ ∈ M + (Z), and a sequence {γ n } n≥1 ∈ M + (Z) such that converges weakly to γ,γ n w ⇀ γ (n → ∞).Finally, consider the mappingZ ∋ z → γ(ϕ(z, •)) := Z ϕ(z, z ′ )dγ(z ′ ) ∈ R.Then we have the following results:(1) γ n (ϕ(z, •)) → γ(ϕ(z, •)) uniformly (when n → ∞).(EQUATION(3) If M ⊂ M + (Z) is compact for the weak convergence, then inf γ∈M γ ⊗2 (ϕ(•, •)) admits a minimizer.Proof. The main idea of the proof is similar to [8, Lemma 10.3]: we extend it from P + (Z) to M + (Z).(1) Since γ n w ⇀ γ, and Z is compact, we have |γ n | → |γ|. Then, given ϵ > 0, for n sufficiently large we have|γ n | ≤ |γ| + ϵ.Let us denote by ∥ϕ∥ Lip the Lipschitz constant of ϕ. For any z 1 , z 2 ∈ Z, we have:|γ n (ϕ(z 1 , •)) -γ n (ϕ(z 2 , •))| ≤ Z |ϕ(z 1 , z) -ϕ(z 2 , z)|γ n (z) ≤ max z∈Z |ϕ(z 1 , z) -ϕ(z 2 , z)|(|γ| + ϵ) ≤ (|γ| + ϵ)∥ϕ∥ Lip d Z (z 1 , z 2 ) = Kd Z (z 1 , z 2 ),where K = (|γ| + ϵ)∥ϕ∥ Lip is a finite positive value. Note that the above inequality also holds if we replace γ n by γ.Since (Z, d Z ) is compact, Z = N i=1 B(z i , ϵ/K) for some z 1 , . . . , z N ∈ Z, where B(z i , ϵ/3K) = {z ∈ Z : d Z (z, z i ) ≤ ϵ/3K}is the closed ball centered at z i , with radius ϵ/K. By definition of weak convergence, when n is sufficiently large,|γ n (ϕ(z i , •)) -γ(ϕ(z i , •))| < ϵ/3, for each i ∈ [1 : N ].Given z ∈ Z, then z ∈ B(z i ) for some z i . For sufficiently large n, we have:EQUATION)Thus we prove the first statement.(2) We recall that we do not have(γ n ) ⊗2 w ⇀ γ ⊗2 .Consider an arbitrary ϵ > 0. We have,EQUATION≤ lim sup n→∞ |(γ n ⊗ γ n )(ϕ) -(γ ⊗ γ n )(ϕ)| An + lim sup n→∞ |(γ n ⊗ γ)(ϕ) -(γ ⊗ γ)(ϕ)| Bn .For the first term, when n is sufficiently large, by statement (1), we have:EQUATIONThus, lim sup n A = lim n A = 0.Similarly, for the second term, when n is sufficiently large, we haveEQUATIONThus, lim sup n B n = lim n B n = 0.Therefore, from ( 27), ( 28) and ( 29), we obtainEQUATION(3) Let γ n ∈ M be a sequence such that (γ n ) ⊗2 (ϕ) (weakly) converges to inf γ∈M γ ⊗2 (ϕ).Since M is compact, there exists a sub-sequence γ n k w ⇀ γ for some γ ∈ M. Then, by statement (2), we have: γ ⊗2 (ϕ) = lim k (γ n k ) ⊗2 (ϕ) = inf γ∈M γ ⊗2 (ϕ),Define (Z, d Z ) as Z := X × Y , with d Z ((x, y), (x ′ , y ′ )) := d X (x, x ′ ) + d Y (y, y ′ ).We claim that the following mapping(X × Y ) 2 = Z 2 → R ((x, y), (x ′ , y ′ )) → ϕ((x, y), (x ′ , y ′ )) := L(d q X (x, x ′ ), d q Y (y, y ′ )) -2λ is a Lipschitz function with respect to d + Z, where L satisfies (24) . Indeed, givenEQUATION)) ∈ Z 2 , we have:|ϕ((x 1 , y 1 ), (x ′ 1 , y ′ 1 )) -ϕ((x 2 , y 2 ), (x ′ 2 , y ′ 2 ))| = |L(d X (x 1 , x ′ 1 ), d Y (y 1 , y ′ 1 )) -L(d X (x 2 , x ′ 2 ), d Y (y 2 , y ′ 2 ))| ≤ |L(d X (x 1 , x ′ 1 ), d Y (y 1 , y ′ 1 )) -L(d X (x 2 , x ′ 2 ), d Y (y 1 , y ′ 1 ))| + |L(d X (x 2 , x ′ 2 ), d Y (y 1 , y ′ 1 )) -L(d X (x 2 , x ′ 2 ), d Y (y 2 , y ′ 2 ))| ≤ K|d q X (x 1 , x ′ 1 ) -d q X (x 2 , x ′ 2 )| + K|d q Y (y 1 , y ′ 1 ) -d q Y (y 2 , y ′ 2 )| ≤ K ′ |d X (x 1 , x ′ 1 ) -d X (x 2 , x ′ 2 )| + K ′ |d Y (y 1 , y ′ 1 ) -d Y (y 2 , y ′ 2 )| (31) ≤ K ′ (d X (x 1 , x ′ 2 ) + d X (x ′ 1 , x ′ 2 )) + K ′ (d Y (y 1 , y 2 ) + d Y (y ′ 1 , y ′ 2 )) (32) = K ′ [((d X (x 1 , x 2 ) + d Y (y 1 , y 2 )) + ((d X (x ′ 1 , x ′ 2 ) + d Y (y ′ 1 , y ′ 2 ))] = K ′ [d Z ((x 1 , y 1 ), (x 2 , y 2 )) + d Z ((x ′ 1 , y ′ 1 ), (x ′ 2 , y ′ 2 ))] = K ′ d +Z (((x 1 , y 1 ), (x 2 , y 2 )), ((x 1 , y 1 ), (x 2 , y 2 ))) where in (31) , K ′ = qβ q-1 K; the inequality holds by lemma C.2; The inequality (32) follows from the triangle inequality:d X (x 1 , x ′ 1 ) -d X (x 2 , x ′ 2 ) ≤ d X (x 1 , x 2 ) + d X (x 2 , x ′ 2 ) + d X (x ′ 2 , x ′ 1 ) -d X (x 2 , x ′ 2 ) = d X (x 1 , x 2 ) + d X (x ′ 1 , x ′ 2 ), and similarly, d X (x 2 , x ′ 2 ) -d X (x 1 , x ′ 1 ) ≤ d X (x 1 , x 2 ) + d X (x ′ 1 , x ′ 2 ). Let M = Γ ≤ (µ, ν). From [53, Proposition B.1],we have that Γ ≤ (µ, ν) 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 asinf γ∈Γ ≤ (µ,ν) γ ⊗2 (ϕ) + λ(|µ| 2 + |ν| 2 )admits a solution, i.e., a minimizer γ ∈ Γ ≤ (µ, ν). Therefore, we end the proof of Proposition 3. Consider the GW problem, for q ≥ 1,EQUATIONor, in particular,EQUATIONFor probability mm-spaces we have the equivalence relation X ∼ Y if and only if GW p q (X, Y) = 0.By [8, Chapter 5], X ∼ Y is equivalent to the following: there exists a bijective isometry mappingϕ : X → Y , such that d X (x, x ′ ) -d Y (ϕ(x), ϕ(x ′ )) = 0, µ ⊗2 -a.s. ϕ # µ = ν.Remark D.1. In the literature, the case where q = 1 is the most frequently considered problem. In particular, in [8] it is stated the equivalence relation X ∼ Y if and only if there exists ϕ :X → Y such that ϕ # µ = ν and d X (x, x ′ ) = d Y (ϕ(x), ϕ(x ′ )) µ ⊗2 -a.s. if and only if GW p 1 (X, Y) = 0.Thus, X ∼ Y is also equivalent to have ϕ :X → Y such that ϕ # µ = ν and d X (x, x ′ ) = d Y (y, y ′ ) γ ⊗2 -a.s.where γ is a minimizer for GW p 1 (X, Y). So, in this situation we also have d q X (x, x ′ ) = d q Y (y, y ′ ) γ ⊗2 -a.s. for any given q ≥ 1. Therefore, X ∼ Y if and only if GW p q (X, Y) = 0.We first introduce the formal statement of Proposition 3.4. To do so, we extend the equivalence relation ∼ to all mm-spaces (not only probability mm-spaces): Given arbitrary mm-spaces X = (X, d X , µ),Y = (Y, d Y , ν), where X, Y are compact and µ ∈ M + (X), ν ∈ M + (Y ), we write X ∼ Y if and only if they have the same total mass (i.e., |µ| = µ(X) = ν(Y ) = |ν|) and GW p q (X, Y) = 0.Formal statement of Proposition 3.4: Given λ > 0, 1 ≤ p, q < ∞, then (P GW p λ,q (•, •)) 1/p defines a metric among mm-spaces under taking quotient with respect to the equivalence relation ∼.Next, we discuss its proof.It is straightforward to verify P GW p λ,q (X, Y) ≥ 0, and that P GW p λ,q (X, Y) = P GW p λ,q (Y, X). In what follows, we will concentrate on proving P GW p λ,q (X, Y) = 0 if and only if X ∼ Y:If X ∼ Y, then |µ| = |ν|, and we have0 ≤ P GW p λ,q (X, Y) ≤ GW p q (X, Y) = 0,where the inequality follows from the fact Γ(µ, ν) ⊆ Γ ≤ (µ, ν). Thus, P GW p λ,q (X, Y) = 0.For the other direction, suppose that P GW p λ,q (X, Y) = 0. We claim that |µ| = |ν| and that there exist an optimal plan γ for P GW p λ,q (X, Y) such that |µ| = |γ| = |ν|. Let us prove this by contradiction.Assume |µ| < |ν|. For convenience, suppose |µ| 2 ≤ |ν| 2 -ϵ, for some ϵ > 0. Then, for each γ ∈ Γ ≤ (µ, ν), we have |γ ⊗2 | ≤ |µ| 2 ≤ |ν| 2 -ϵ, and soP GW p λ,q (X, Y) ≥ λ(|µ| 2 + |ν| 2 -2|γ| 2 ) ≥ λ(|ν 2 | -|γ| 2 ) ≥ λϵ > 0. Thus, P GW p λ,q (X, Y) > 0, which is a contradiction. So, |µ| = |ν|. In addition, if γ ∈ Γ ≤ (µ, ν)is optimal for P GW p λ,q (X, Y), we have |γ| = |µ| = |ν|, thus γ ∈ Γ(µ, ν). Therefore, since P GW p λ,q (X, Y) = 0, and for such optimal γ we have |γ| = |µ| = |ν|, we obtain(X×Y ) 2 |d q X (x, x ′ ) -d q Y (y, y ′ )| p dγ ⊗2 = 0.As a result, d q X (x, x ′ ) = d q Y (y, y ′ ) γ ⊗2 -a.s., which implies that GW p q (X, Y) = 0, and so X ∼ Y.Consider three arbitrary mm-spaces S = (S, d S , σ), X = (X, d X , µ), Y = (Y, d Y , ν). We define Ŝ = ( Ŝ, d Ŝ , σ), X = ( X, d X , μ), Ŷ = ( Ŷ , d Ŷ , ν) 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 ∞0 , ∞1 , ∞2 and set     Ŝ = S ∪ { ∞0 , ∞1 , ∞2 }, X = X ∪ { ∞0 , ∞1 , ∞2 }, Ŷ = Y ∪ { ∞0 , ∞1 , ∞2 }.Define σ, μ, ν as follows:EQUATIONNote that σ is not supported on point ∞0 , similarly, μ is not supported on ∞1 , ν is not supported on ∞2 . In addition, we have |μ| = |ν| = |σ| = |µ| + |ν| + |σ|. (For a similar idea in classical unbalanced optimal transport see, for example, [16] .)Finally, define d Ŝ : Ŝ2 → R ∪ {∞} as follows:EQUATION) Note, d Ŝ (•, •) is not a rigorous metric in Ŝ since we allow d Ŝ = ∞. Similarly, define d X , d Ŷ .As a result, we have constructed new spacesEQUATIONWe define the following mapping D λ : (R ∪ {∞}) × (R ∪ {∞}) → R + :EQUATIONNote that D λ 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 λ (•, •) denote the function defined in (38) . For any r 0 , r 1 , r 2 ∈ R ∪ {∞}, we have the following:• D λ (r 1 , r 2 ) ≥ 0. D λ (r 1 , r 2 ) = 0 if and only if r 1 = r 2 , where r 1 = r 2 denotes that r 1 = r 2 ∈ R or r 1 = r 2 = ∞.• Except the case r 1 , r 2 ∈ R, r 0 = ∞, for all other cases, we haveD λ (r 1 , r 2 ) ≤ D λ (r 1 , r 0 ) + D λ (r 2 , r 0 ). Proof of Lemma D.2. It is straightforward to verify D λ (•, •) ≥ 0. Now, consider r 0 , r 1 , r 2 ∈ R ∪ {∞}. If r 1 = r 2 ∈ R or r 1 = r 2 = ∞, we have D λ (r 1 , r 2 ) = 0. Otherwise, D λ (r 1 , r 2 ) > 0. So, D λ (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 ∈ R, D λ (r 1 , r 2 ) = |r 1 -r 2 | ≤ |r 1 -r 2 | + |r 2 -r 0 | = D λ (r 0 , r 1 ) + D λ (r 0 , r 2 )Case 2: r 1 , r 2 ∈ R, r 0 = ∞. We do not need to verify the inequality in this case.Case 3:r 1 ∈ R, r 2 , r 0 = ∞, or r 1 = ∞, r 2 ∈ R, r 0 = ∞.In this case, we haveD λ (r 1 , r 2 ) = D λ (r 1 , r 0 ) = √ λ, D λ (r 2 , r 0 ) = 0and it is straightforward to verify the inequality.Case 4: r 1 , r 2 = ∞, r 3 ∈ R. In this case, we have D λ (r 1 , r 2 ) = 0 ≤ D λ (r 0 , r 1 ) + D λ (r 0 , r 2 ).Case 5: r 1 , r 2 , r 0 = ∞. In this case, we haveD λ (r 1 , r 2 ) = D λ (r 1 , r 0 ) = D λ (r 2 , r 0 ) = 0and it is straightforward to verify the inequality.We construct the following generalized GW problem:EQUATIONSimilarly, we define GW p λ,q ( X, Ŝ), and GW p λ,q ( Ŝ, Ŷ).The mapping ( 6) is modified as:EQUATIONIt is straightforward to verify the above mappings are well-defined. In addition, we can observe that,EQUATIONEQUATIONγ12 ({ ∞0 } × Y ) = γ12 (X × { ∞0 }) = 0. Proposition D.3. If γ 12 ∈ Γ ≤ (µ, ν) is optimal in PGW problem P GW p λ,q (X, Y), then γ12 defined in (40) is optimal in generalized GW problem GW p λ,q ( X, Ŷ). Furthermore, Ĉ(γ 12 ; λ, μ, ν) = C(γ 12 ; λ, µ, ν), and thus, P GW p λ,q (X, Y) = GW p λ,q ( X, Ŷ).Proof of Proposition D.3. For each γ ∈ Γ ≤ (µ, ν), define γ by (40) .Note that if we merge the points ∞1 , ∞2 , ∞3 as ∞, i.e.∞ = ∞1 = ∞2 = ∞3 , the value Ĉ(γ; λ, μ, ν) will not change. Thus, we merge these three auxiliary points.We have:Ĉ(γ; λ, μ, ν) = ( X× Ŷ ) 2 D p λ (d q X (x, x ′ ), d q Ŷ (x, x ′ ))dγ ⊗2 = (X×Y ) 2 |d q X (x, x ′ ) -d q Y (y, y ′ )| p dγ ⊗2 + ({ ∞}×Y ) 2 λdγ ⊗2 + (X×{ ∞}) 2 λγ ⊗2 + 2 ({ ∞}×Y )×(X×Y ) λdγ ⊗2 + 2 (X×{ ∞})×(X×Y ) λdγ ⊗2 + ({ ∞}×{ ∞}) 2 D p λ (∞, ∞)dγ ⊗2 + 2 ({ ∞}×Y )×(X×{ ∞}) D p λ (∞, ∞)dγ ⊗2 + 2 ({ ∞}×{ ∞})×(X×Y ) D p λ (∞, ∞)dγ ⊗2 + 2 ({ ∞}×{Y })×{ ∞} 2 D p λ (∞, ∞)dγ ⊗2 + 2 (X×{ ∞})×{ ∞} 2 D p λ (∞, ∞)dγ ⊗2 = (X×Y ) 2 |d q X (x, x ′ ) -d q Y (y, y ′ )| p dγ ⊗2 + 2λ(|ν| -|γ|)|γ| + λ(|ν| -|γ|) 2 + 2λ(|µ| -|γ|)|γ| + λ(|µ| -|γ|) 2 = (X×Y ) 2 |d q X (x, y ′ ) -d q Y (y, y ′ )| p dγ ⊗2 ) + λ(|ν 2 | + |µ| 2 -2|γ| 2 ) = C(γ; λ, µ, ν).As we merged the points ∞1 , ∞2 , ∞3 , by [40, Proposition B.1.] , the mapping γ → γ defined in ( 40) is a bijection. Then, if γ ∈ Γ ≤ (µ, ν) is optimal for the PGW problem P GW p λ,q (X, Y) (defined in ( 10)), γ ∈ Γ(μ, ν) is optimal for generalized GW problem GW p λ,q ( X, Ŷ) (defined in (39) ). Therefore, GW p λ,q ( X, Ŷ) = P GW p λ,q (X, Y).Proposition D.4 (Triangle inequality for GW p λ,q (•, •)). Consider the generalized GW problem (39) . Then, for any p ∈ [1, ∞), we have GW p λ,q ( X, Ŷ) ≤ GW p λ,q ( Ŝ, X) + GW p λ,q ( Ŝ, Ŷ).Proof of Proposition D.4. We prove the case p = 2. For general p ≥ 1, it can be proved similarly.Choose an optimal γ 12 ∈ Γ ≤ (µ, ν) for P GW 2 λ,q (X, Y), an optimal γ 01 ∈ Γ ≤ (σ, µ) for P GW 2 λ,q (S, X), and an optimal γ 02 ∈ Γ ≤ (σ, ν) for P GW 2 λ,q (S, Y). Construct γ12 , γ01 , γ02 by (40) .By Proposition D.3, we have that γ12 , γ01 , γ02 are optimal for GW 2 λ,q ( X, Ŷ), GW 2 λ,q ( Ŝ, X), GW 2 λ,q ( Ŝ, Ŷ), respectively.Define canonical projection mappingπ 0,1 :( Ŝ × X × Ŷ ) → ( Ŝ × X) (s, x, y) → (s, x).Similarly, we define π 0,2 , π 1,2 .By gluing lemma (see Lemma 5.5 [54] ), there exists γ ∈ M + ( Ŝ × X × Ŷ ), such that (π 0,1 ) # γ = γ01 , (π 0,2 ) # γ = γ02 . Thus, (π 1,2 ) # γ is a coupling between μ, ν. We haveEQUATION)The inequality holds since (π 1,2 ) # γ, γ12 ∈ Γ(μ, ν), and γ12 is optimal.Next, we will show that( Ŝ× X× Ŷ ) 2 D 2 λ (d q X (x, x ′ ), d q Ŷ (y, y ′ ))dγ ⊗2 ≤ ( Ŝ× X× Ŷ ) 2 (D λ (d q Ŝ (s, s ′ ), d q X (x, x ′ )) + D λ (d q Ŝ (s, s ′ ), d q Ŷ (y, y ′ ))) 2 dγ ⊗2 .Let ((s, x, y), (s ′ , x ′ , y ′ )) ∈ ( Ŝ, X, Ŷ ) 2 , and assume thatEQUATIONBy Lemma D.2, (44) implies d X (x, x ′ ), d Ŷ (y, y ′ ) ∈ R, d Ŝ (s, s ′ ) = ∞.Thus, by definition (36) , it also impliesEQUATION)Define the following sets:A α = Ŝ × X × Y, A 0 = { ∞0 } × X × Y, A 1 = { ∞1 } × X × Y, A 2 = { ∞2 } × X × Y.Notice that, (44) =⇒ (45) is equivalent to (44) =⇒ ((s, x, y), (s, x ′ , y ′ ))EQUATIONNext, we will show γ⊗2 (A) = 0. Indeed,γ(A 0 ) ≤ γ({∞ 0 } × X × Ŷ ) = σ({∞ 0 }) = 0 by definition (35) of σ , γ(A 1 ) ≤ γ({∞ 1 } × X × Y ) = γ02 ({ ∞1 × Y }) = 0 by (42), γ(A 2 ) ≤ γ({∞ 2 } × X × Ŷ ) = γ01 ({ ∞2 × X}) = 0 by (41). Thus, γ⊗2 (A) = 0. By considering B = ( Ŝ × X × Y ) 2 \ A, we obtain ( Ŝ× X× Ŷ ) 2 D 2 λ (d q X (x, x ′ ), d q Ŷ (y, y ′ ))dγ ⊗2 = B D 2 λ (d q X (x, x ′ ), d q Ŷ (y, y ′ ))dγ ⊗2 since γ ⊗2 (A) = 0 ≤ B D λ (d q Ŝ (s, s ′ ), d q X (x, x ′ ) + D λ (d q Ŝ (s, s ′ ), d q Ŷ (y, y ′ )) 2 dγ ⊗2by ( 46)EQUATION)Following ( 43) and ( 47), we haveGW 2 λ,q ( X, Ŷ) ≤ ( Ŝ× X× Ŷ ) 2 D 2 λ (d q X (x, x ′ ), d q Ŷ (y, y ′ ))dγ ⊗2 1/2 ≤ ( Ŝ× X× Ŷ ) 2 D λ (d q Ŝ (s, s ′ ), d q X (x, x ′ )) + D λ (d q Ŝ (s, s ′ ), d q Ŷ (y, y ′ )) 2 dγ ⊗2 1/2 ≤ ( Ŝ× X× Ŷ ) 2 D 2 λ (d q Ŝ (s, s ′ ), d q X (x, x ′ ))dγ ⊗2 1/2 + ( Ŝ× X× Ŷ ) 2 D 2 λ (d q Ŝ (s, s ′ ), d q Ŷ (y, y ′ ))dγ ⊗2 1/2 (48) = ( Ŝ× X× Ŷ ) 2 D 2 λ (d q Ŝ (s, s ′ ), d q X (x, x ′ ))d(γ 01 ) ⊗2 1/2 + ( Ŝ× X× Ŷ ) 2 D 2 λ (d q Ŝ (s, s ′ ), d q Ŷ (y, y ′ ))d(γ 02 ) ⊗2 1/2 = GW 2 λ,q ( Ŝ, X) + GW 2 λ,q ( Ŝ, Ŷ),where in the third inequality (48) we used the Minkowski inequality inL 2 (( Ŝ × X × Ŷ ) 2 , γ⊗2 ).Now, we can complete the proof of Proposition 3.4: By the Propositions D.3, we have P GW p λ,q (X, Y) = GW p λ,q ( X, Ŷ) and similarly for P GW p λ,q and (S, X), P GW p λ,q (S, Y). By the Proposition D.4, GW p λ,q (•, •) satisfies the triangle inequality, thus we complete the proof: P GW p λ,q (X, Y) = GW p λ,q ( X, Ŷ) ≤ GW p λ,q ( Ŝ, X) + GW p λ,q ( Ŝ, Ŷ) = P GW p λ,q (S, X) + P GW p λ,q (S, Y).E Proof of Proposition 3.5: PGW converges to GW as λ → ∞.In the main text, we set λ ∈ R. In this section, we discuss the limit case that when λ → ∞.Lemma E.1. Suppose |µ| ≤ |ν|, for each γ ∈ Γ ≤ (µ, ν), there exists γ ′ ∈ Γ ≤ (µ, ν) such that γ ≤ γ ′ and (π 1 ) # γ ′ = µ. Proof. Let γ ∈ Γ ≤ (µ, ν). If |γ| = |µ|, then we have (π 1 ) # γ = µ. If |γ| < |µ|, let µ r = µ -(π 1 ) # γ, ν r = ν -(π 2 ) # γ.We have that µ r , ν r are non-negative measures,with |µ r | = |µ| -|γ| > 0. If we define γ ′ := γ + 1 |ν| -|γ| µ r ⊗ ν r ,we obtain γ ≤ γ ′ . In addition, we have:(π 1 ) # γ ′ = (π 1 ) # γ + µ r |ν r | |ν| -|γ| = (π 1 ) # γ + µ r = µ, (π 2 ) # γ ′ = (π 2 ) # γ + ν r |µ r | |ν| -|γ| ≤ (π 2 ) # γ + ν r |ν r | |ν| -|γ| = ν. Thus, γ ′ ∈ Γ ≤ (µ, ν) and (π 1 ) # γ ′ = µ.γ λ into C(γ λ ; λ, µ, ν), we obtain:P GW L λ,q (X, Y) = (X×Y ) 2 L(d q X (x, x ′ ), d q Y (y, y ′ ))dγ ⊗2 λ + λ(1 2 + 1 2 -2 • 1 2 ) = (X×Y ) 2 L(d q X (x, x ′ ), d q Y (y, y ′ ))dγ ⊗2 λ ≥ GW (X, Y).By Lemma E.3, we also have P GW L λ,q (X, Y) ≤ GW L q (X, Y) and we complete the proof.Lemma F.1. Given a tensor M ∈ R n×m×n×n and γ, γ ′ ∈ R n×m , the tensor product operator M • γ satisfies the following:(i) The mapping γ → M • γ is linear with respect to γ.(ii) If M is symmetric, in particular, M i,j,i ′ ,j ′ = M i ′ ,j ′ ,i,j , ∀i, i ′ ∈ [1 : n], j, j ′ ∈ [1 : m], then ⟨M • γ, γ ′ ⟩ F = ⟨M • γ ′ , γ⟩ F .Proof.(i) For the first part, consider γ, γ ′ ∈ R n×m and k ∈ R.For each i, j ∈ [1 : n] × [1 : m],we have we have(M • (γ + γ ′ )) ij = i ′ ,j ′ M i,j,i ′ ,j ′ (γ + γ ′ ) i ′ j ′ = i ′ ,j ′ M i,j,i ′ ,j ′ γ i ′ j ′ + i ′ ,j ′ M i,j,i ′ ,j ′ γ ′ i ′ j ′ = (M • γ) ij + (M • γ) i ′ j ′ , (M • (kγ)) ij = i ′ ,j ′ M i,j,i ′ ,j ′ (kγ) ij = k i ′ ,j ′ M i,j,i ′ ,j ′ γ ij = k(M • γ) ij . Thus, M • (γ + γ ′ ) = M • γ + M • γ ′ and M • (kγ) = kM • γ. Therefore, γ → M • γ is linear.(ii) For the second part, we haveEQUATION= ⟨M γ ′ , γ⟩ where (49) follows from the fact that M is symmetric.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. Proposition G.1. Let X = (X, d X , µ) be a mm-space. Consider an auxiliary point ∞ and let X = ( X, d X , μ), where X = X ∪ { ∞}, μ is constructed by (4), and considering ∞ as an auxiliary point to R such that x ≤ ∞ for every x ∈ R, we extend d X into d X : X2 → R ∪ {∞} and define L λ : R ∪ {∞} → R as follows:EQUATION)Consider the following GW-variant 2 problem:EQUATIONThen, when considering the bijection γ → γ defined in (6) we have that γ is optimal for PGW problem (10) if and only if γ is optimal for the GW-variant problem (51) .Proof. The mapping F defined by ( 6) well-defined bijection, as shown in [40, 12] .Given γ ∈ Γ ≤ (µ, ν), we have γ = F (γ) ∈ Γ(μ, ν). Let Ĉ(γ; µ, ν) denote the transportation cost in the GW-variant problem (51) , that is,Ĉ(γ; µ, ν) := ( X× Ŷ ) 2 L λ (d q X (x, x ′ ), d q Ŷ (y, y ′ )) dγ(x, y)dγ(x ′ , y ′ )Then, we haveC(γ; λ, µ, ν) = (X×Y ) 2 (L(d q X (x, x ′ ), d q Y (y, y ′ )) -2λ) dγ ⊗2 + λ(|µ| + |ν|) does not depend on γ = (X×Y ) 2 (L(d q X (x, x ′ ), d q Y (y, y ′ )) -2λ) dγ ⊗2 + λ(|µ| + |ν|) (since γ| X×Y = γ) = (X×Y ) 2 (L(d q X (x, x ′ ), d q Ŷ (y, y ′ )) -2λ) dγ ⊗2 + λ(|µ| + |ν|) (as d X | X×X = d X , d Ŷ | Y ×Y = d Y ) = (X×Y ) 2 L λ (d q X (x, x ′ ), d q Ŷ (y, y ′ )) dγ ⊗2 + λ(|µ| + |ν|) (since L| R×R (•, •) = (L(•, •) -2λ)) = ( X× Ŷ ) 2 L λ (d q X (x, x ′ ), d q Ŷ (y, y ′ )) dγ ⊗2 + λ(|µ| + |ν|)does not depend on γ . (since L assigns 0 to ∞) Combining this with the fact that F : γ → γ is a bijection, we have that γ is optimal for (10) if and only if γ is optimal for (51) . Under the assumptions of Proposition 3.3, there exists an optimal γ ∈ Γ ≤ (µ, ν) for the PGW problem exists, and so we have:EQUATION)Remark G.2. 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.G.1 Frank-Wolfe for the PGW Problem -Solver 2Similarly to the discrete PGW problem (15) , consider the discrete version of (4):EQUATION2 GW L λ ( X, Ŷ) is not a rigorous GW problem since d X = ∞ is possible, thus it is not a metric. Also, X, Y are not necessarily probability mm-spaces Algorithm 2: Frank-Wolfe Algorithm for partial GW, ver 2EQUATION) // Line search γ(k+1) ← (1 -α (k) )γ (k) ′ + αγ (k) // Update γ if convergence, break end for γ (f inal) ← γ(k) [1 : n, 1 : m]and, in a similar fashion, we defineEQUATIONThen, the GW-variant problem (51) can be written asEQUATIONBased on Proposition G.1 (which relates P GW L λ (•, •) with GW (•, •)), we propose two versions of the Frank-Wolfe algorithm [31] that can solve the PGW problem (15) . Apart from Algorithm 1 in [45] , which solves a different formulation of partial GW, and Algorithm 1 in [44] , 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 p, q, 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:γ(k) ′ ← arg min γ∈Γ(p,q) ⟨L M (γ (k) ), γ⟩ F .The gradient L M (γ (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 α (k) :α (k) = arg min α∈[0,1] {L M ((1 -α)γ (k) + αγ (k) ′ )}.Similar to Solver 1, letEQUATIONThen the optimal α (k) is given by formula (18) . See Appendix J for a detailed discussion.Step 3. Update γ(k+1)← (1 -α (k) )γ (k) + α (k) γ(k) ′ .In this section, we discuss the derivation of the line search algorithm.We observe that in the partial GW setting, for each γ ∈ Γ ≤ (µ, ν), the marginals of γ are not fixed.Thus, we can not directly apply the classical algorithm (e.g. [43] ).In iteration k, let γ (k) , γ (k) ′ be the previous and new transportation plans from step 1 of the algorithm.For convenience, we denote them as γ, γ ′ , respectively.The goal is to solve the following problem:EQUATIONwhereEQUATIONc =⟨ M • γ, γ⟩ F ,where the second identity in (63) follows from Lemma F.1 and the fact thatEQUATIONTherefore, the above problem (62) becomes min α∈[0,1]aα 2 + bα + c.The solution is the following:EQUATION( -b 2a , [0, 1]) = min 1, max{0, -b 2a } =    -b 2a if -b 2a ∈ [0, 1], 0 if -b 2a < 0, 1 if -b 2a > 1.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 haveEQUATIONNote that in the classical GW setting [43] , the term u(C X , C Y , δγ) = 0 n×m and |δγ| = 0. Therefore, in such line search algorithm (Algorithm 2 in [43] ), the terms u(C X , C Y , δγ), 2λ|δγ|1 n×m are not required. In addition, in equation (66), M • γ, 2λ|γ| have been computed in the gradient computation step, thus these two terms can be directly applied in this step.whereL 1 := L M (γ (1) ) -min γ∈Γ ≤ (p,q) L M (γ)is the initial global suboptimal bound for the initialization γ (1) of the algorithm, andD L := Lip • (diam(Γ ≤ (p, q))) 2 , where Lip is the Lipschitz constant of ∇L M and diam(Γ ≤ (p, q)) is the ∥ • ∥ F diameter of Γ ≤ (p, q) in R n×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 [32] , the rate on gK is O(1/ √ K). That is, the algorithm takes at most O(1/ε 2 ) iterations to find an approximate stationary point with a gap smaller than ε.Finally, we adapt Lemma 1 in Appendix B.2 in [45] to our case characterizing the convergence guarantee, precisely, determining such a constant max{2L 1 , D L } in (71). Essentially, we will estimate upper bounds for the Lipschitz constant Lip and for the diameter diam(Γ ≤ (p, q)).• Let us start by considering the diameter of the couplings of Γ ≤ (p, q) with respect to theFrobenious norm ∥ • ∥ F . By definition, diam(Γ ≤ (p, q)) := sup γ,γ ′ ∈Γ ≤ (p,q) ∥γ -γ ′ ∥ F .For any γ ∈ Γ ≤ (p, q), since γ 1 ≤ p and γ 2 ≤ q, we obtain that, in particular,EQUATION i,j |γ ′ i,j |   2 = 2|γ| 2 + 2|γ ′ | 2 ≤ 4s(essentially, we used that ∥ • ∥ F is the 2-norm for matrices viewed as vectors, that | • | is the 1-norm for matrices viewed as vectors, and the fact thatEQUATIONwhere s only depends on p and q that are fixed weight vectors in R n + and R m + , respectively.• Now, let us analyze the Lipschitz constant of ∇L M with respect to ∥ • ∥ F . For any γ, γ ′ ∈ Γ ≤ (p, q) we have,∥∇L M (γ) -∇L M (γ ′ )∥ 2 F = ∥ M • γ -M • γ ′ ∥ 2 F = ∥[M -2λ] • (γ -γ ′ )∥ 2 F = ⟨[M -2λ] • (γ -γ ′ ), [M -2λ] • (γ -γ ′ )⟩ F = i,j [(M -2λ) • (γ -γ ′ )] i,j 2 = i,j   i ′ ,j ′ (M i,j,i ′ ,j ′ -2λ)(γ i ′ ,j ′ -γ ′ i ′ ,j ′ )   2 ≤ max i,j,i ′ ,j ′ {M i,j,i ′ ,j ′ -2λ} 2    n,m i,j   n,m i ′ ,j ′ (γ i ′ ,j ′ -γ ′ i ′ ,j ′ )   2    = (max(M ) -2λ) 2   n,m i,j ∥γ -γ ′ ∥ 2 F   ≤ nm (max(M ) -2λ) 2 ∥γ -γ ′ ∥ 2 F .Hence, the Lipschitz constant of the gradient of L M is byLip ≤ √ nm max i,j,i ′ ,j ′ {M i,j,i ′ ,j ′ } -2λ .In the particular case where L(r 1 , r2 ) = |r 1 -r 2 | 2 we have M i,j,i ′ ,j ′ = |C X i,i ′ -C Y j,j ′ | 2 (as in (14))where C X , C Y are given n × n and m × m non-negative symmetric matrices defined in (11) , that depend on the given discrete mm-spaces X and Y. Here, we obtainmax i,j,i ′ ,j ′ {M i,j,i ′ ,j ′ } = max i,j,i ′ ,j ′ {|C X i,i ′ -C Y j,j ′ | 2 } ≤ (max i,i ′ {C X i,i ′ }) 2 + (max j,j ′ {C Y j,j ′ }) 2and so the Lipschitz constant verifiesLip ≤ √ nm ((max(C X ) 2 + max(C Y ) 2 ) -2λCombining all together, we obtain that after K iterations, the minimal Frank-Wolf gap verifiesgK = min 1≤k≤K g k ≤ max{2L 1 , 4s √ nm |max i,j,i ′ ,j ′ {M i,j,i ′ ,j ′ } -2λ|} √ K ≤ 2 max{L 1 , 2s √ nm (max(C X ) 2 + max(C Y ) 2 ) -2λ } √ K (if M is as in (14))where L 1 dependents on the initialization of the algorithm.Finally, we mention that there is a dependence in the constant max{2L 1 , D L } on the number of points (n and m) of our discrete spaces X = {x 1 , . . . x n } and Y = {y 1 , . . . , y m } which was not pointed out in [45] .Partial Gromov-Wasserstein is first introduced in [45] . To distinguish the PGW problem in [45] and the PGW problem in this paper, we call the former one the Mass-Constrained Gromov-Wasserstein problem (MPGW):EQUATIONwhere ρ ∈ [0, min{|µ|, |ν|}], andEQUATIONUnlike 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 functionEQUATIONis not a convex function even if (r 1 , r 2 ) → L(r 1 , r 2 ) is convex [37] : (If the problems were convex, MPGW, as the 'Lagrangian formulation' of PGW-adding the constraint of PGW in the functional à la Lagrange Multiplierswould 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 relation by the following lemma, based on which we design the wall-clock time experiment in Section O.Proposition L.1. Suppose γ ∈ Γ ≤ (µ, ν) is optimal for P GW λ (X, Y). Let ρ = |γ|, we have γ is also optimal in M P GW ρ (X, Y).Proof. Pick γ ′ ∈ Γ ρ ≤ (µ, ν) ⊂ Γ ≤ (µ, ν), since γ is optimal in P GW λ (µ, ν), we have0 ≤ C(γ; λ, µ, ν) -C(γ ′ ; λ, µ, ν) = (X×Y ) 2 L(d 2 X (x, x ′ ), d 2 Y (y, y ′ ))d(γ ⊗2 -γ ′⊗2 )Thus, γ is optimal in Γ ρ ≤ (µ, ν) for M P GW ρ (X, Y) and we complete the proof.where each γ k ∈ Γ ≤ (p, p k ).The problem (77) can be solved iterative by two steps:Minimization with respect to C: For each k, we solve the PGW problemmin γ k ∈Γ ≤ (p,p k ) ⟨M (C, C k ) • γ k , γ k ⟩ -2λ k |γ k | 2via solver 1 or 2.Minimization with respect to {γ k } k :min C k ξ k ⟨M (C, C k ) • γ k , γ k ⟩ (78)Note, we can ignore the -2λ k |γ k | 2 terms as γ k is fixed in this case.It has closed form solution due to the following lemma and proposition:Lemma M.1. Given matrices A ∈ R n,m , B ∈ R m,l , C ∈ R n,l , let L = ⟨AB, C⟩, then dL dA = CB ⊤ . Proof. For any i ∈ [1 : n], j ∈ [1 : m], we have dL dA ij := i ′ ,j ′ d dA ij C i ′ ,j ′ (AB) i ′ ,j ′ = i ′ ,j ′ C i ′ ,j ′ d( k A i ′ ,k B k,j ′ ) dA ij = j ′ C i,j ′ B k,j ′ = (CB ⊤ ) ij .Proposition M.2. If L satisfies (57), and f ′ 1 /h ′ 1 is invertible, then (78) can be solved byEQUATIONwhere Proof. From Proposition H.1, the objective in (78) becomesA B = A ij B ij ij , with convention 0 0 = 0.L = k ξ k ⟨f 1 (C)γ 1 1 1 ⊤ n k + 1 n (γ k 2 ) ⊤ f 2 (C k ) -h 1 (C)γ k h 2 (C k ) ⊤ , γ k ⟩ = k ξ k ⟨f 1 (C)γ 1 1 1 ⊤ n k , γ k ⟩ + k ξ k ⟨1 n (γ k 2 ) ⊤ f 2 (C k ), γ k ⟩ constant - k ξ k ⟨h 1 (C)γ k h 2 (C k ) ⊤ , γ k ⟩We set dL dC = 0. From Lemma M.1, we have:EQUATIONWe claim A B is well-defined, i.e., ifB ij = 0, then A ij = 0.For each i, j ∈ [1 : n], if B ij = 0, we have two cases:Case 1: ∀k ∈ [1 : K], we have γ k 1 [i] = 0. Thus, γ k [i, :] = 0 ⊤ n k . So A[i, :] = (γ k h 2 (C k )(γ k ) ⊤ )[i, :] = 0 ⊤ n k . Case 2: ∀k ∈ [1 : K], we have γ k 1 [j] = 0. It implies (γ k ) ⊥ [:, j] = 0 n , thus A[:, j] = (γ k h 2 (C k ))(γ k ) ⊤ [:, j] = 0 n k . Therefore, A ij = 0.Thus A B is well-defined.In addition, in these two cases, if we change the value C k ij , L will not change.From (80), we have:f ′ 1 h ′ 1 (C) ij = k ξ k γ k h 2 (C k )(γ k ) ⊤ ij k ξ k γ k 1 (γ k 1 ) ⊤ 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 L. Thus, we have the following is a solution:C = f ′ 1 h ′ 1 -1 k ξ k γ k h 2 (C k )(γ k ) ⊤ k ξ k γ k 1 (γ k 1 ) ⊤ .In particular case:|p| ≤ |p k |, ∀k, suppose λ > max{c 2 : c ∈ k C k ∪ C}, by lemma E.1, we have for each k, |γ k | = min(|p|, |p| k ) = |p|, that is γ k 1 = p.Thus,EQUATIONSince in this case, we can set Similarly, we can also extend the above PGW Barycenter into the MPGW setting: f 1 (x) = x 2 , f 2 (y) = y 2 , h 1 (x) = 2x, h 2 (y) = y. Thus f ′ 1 h ′ 1 (x) = 2x 2 = x and f ′ 1 h ′ 1 -1 (x) = x.min C,γ k K k=1 ξ k ⟨L(C, C k ) • γ k , γ k ⟩,We represent the shapes in each dataset as mm-spacesX i = R 2 , ∥ • ∥ 2 , µ i = n i k=1 α i δ x i k .We use α i = 1 n i to compute the GW distances for the balanced mass constraint setting. For the remaining distances, we set α = 1 N , where N is the median number of points across all shapes in the dataset. For the SVM experiments, we use exp(-σD) as the kernel for the SVM model, and we set σ = 10 for all distances. Moreover, we normalize the matrix D to facilitate a fair comparison of each distance used, since the considered distance may have different scales. We note that the resulting kernel matrix is not necessarily positive semidefinite.In computing the pairwise distances, for the PGW method, we set λ such that λ ≤ λ max = max i (|C i | 2 ). In particular, we compute λ max for each dataset and use λ = 1 5 λ max for each experiment. For UGW, we use ε = 10 -1 and ρ 1 = ρ 2 = 1 for both experiments. Finally, for MPGW, we set the mass-constrained term to be ρ = min(|µ i |, |µ j |) when computing the similarity between shape X i and 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 1a . 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(bone, rectangle) < d(bone, anulus).However, we do not observe this relation in GW and UGW 3 , and for the MPGW method, M P GW (bone, rectangle) ≈ 0, which is also undesirable. For PGW, however, we do observe this relation. Additionally, we report the wall-clock time comparison in Table 1b . "POT initialization" is firstly introduced in [45] .When X 1 , X 2 are in the same dimensional space, i.e. d 1 = d 2 . The initial guess, γ (1) is given by the following partial OT variant problem:EQUATIONwhere L(X, Y ) ∈ R n×m , (L(X, Y )) ij = ∥x i -y j ∥ 2 andEQUATIONThe above problem can be solved by a Lasso (L 1 norm) regularized OT solver.When d 1 ̸ = d 2 , the above technique can not be applied since the problem (86) (in particular L(X, Y ))is not well-defined.The second method "FLB-UOT" is induced in [44] :EQUATIONwhere s X,2 (x) = X |x -x ′ | 2 dµ(x) and s Y,2 is defined similarly. The problem (88) is called Hellinger Kantorovich, which is a classical unbalanced optimal transport problem. It can be solved by the Sinkhorn solver [38] .Analog to the above method, we propose the third method, called "FLB-POT" (first lower boundpartial optimal transport)EQUATIONThe above problem is a partial OT problem and can be solved by classical linear programming [12] .P.5 Numerical details and performance.Accuracy Comparison. In Table 2 and 4, we present the accuracy results for the MPGW, UGW, and the proposed PGW methods when using three different initialization methods: POT, FLB-UOT, and FLB-POT.Following [45] , in the MPGW and PGW methods, we incorporate the prior knowledge π into the definition of p and q. Thus it is sufficient to set mass = π for MPGW and choose a sufficiently large value for λ in the PGW method. This configuration ensures that the mass matched in the target domain Y is exactly equal to π. However, in the UGW method [44] , the setting is p = 1 n 1 n and q = 1 m 1 m . Therefore, in each experiment, we test different parameters (ρ, ρ 2 , ϵ) and select the ones that result in transported mass close to π.Overall, all methods show improved performance in MNIST and EMNIST datasets. One possible reason for this could be the better separability of the embeddings in MNIST and EMNIST, as For the convergence criteria, we set the tolerance term for Frank-Wolfe convergence and the main loop in the UGW algorithm to be 1e -5. Additionally, the tolerance for Sinkhorn convergence in UGW was set to 1e -6. The maximum number of iterations for the POT solver in PGW and MPGW was set to 500n. In addition, for MPGW, we set mass = 0.2 and for PGW method, based on lemma E.2, we set λ to be constant such that 2λ ≥ (max(|C X |) 2 + max(|C Y |) 2 ).Regarding data types, we used 64-bit floating-point numbers for MPGW and PGW, and 32-bit floating-point numbers for UGW. We report the initialization method and its wall-clock time, followed by the wall-clock time of each of the methods MPGW, UGW, and PGW. The units of all reported wall-clock times is seconds. The prior distribution π = p(l = 1) is set to be 0.2 in all experiments. To guarantee the SCAR assumption, for Surf(A) and Decaf(A), we set n = 50, which is the half of the total number of data in one single class. m is set to be 250. Similarly, we set suitable n, m for Surf(D), Decaf(D), Surf(W), Decaf(W).Compatibility Between Linear Search and Frank-Wolf SolverIn practice, we have found that in some experiments, the linear search algorithm (see Sections I, J) may cause the Frank Wolfe algorithms (1, 2) to stop running earlier than expected. This may hurt the performance observed in the PU learning experiments (see Appendix P). As such, we disable line search in these experiments.However, in other experiments, for example PGW barycenter (Appendix M.1), we do not find a significant effect of the linear search algorithm on the results.In the point cloud interpolation experiment (see Appendix M), for the classical GW barycenter method [41] or our PGW barycenter method, the last step is the same: applying MDS on the barycenter minimizer C to construct interpolation point cloud X t . However, such construction is not unique.As a consequence, for each constructed X t , we need to manually set up the rotation and flipping matrices.This problem follows from the fact that the GW and PGW formulations cannot distinguish the data from its rotated (and flipped) version. We refer to Section M.1 for details.All experiments presented in this paper are conducted on a computational machine with an AMD EPYC 7713 64-Core Processor, 8 × 32GB DIMM DDR4, 3200 MHz, and a NVIDIA RTX A6000 GPU.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.Moreover, given two probability mm-spaces X and Y, GW (X, Y) = 0 if and only if there exists a bijective isometry ϕ : X → Y such that ϕ # µ = ν. In particular, the GW distance is invariant under rigid transformations (translations and rotations) of a given probability mm-space.For UGW, this is due to the Sinkhorn regularization term.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.In the classical setting, the goal is to learn a classifier for all x. In this experiment, we follow the setting in[44].In the classical setting, the prior distribution π is the ratio of positive samples of the original dataset. For convenience, we ignore the difference between this ratio in the original dataset and the test dataset. 
 
 Appendix:  


Decision: The reviewers noted that the paper presents a variation on existing unbalanced Gromov-Wasserstein (GW) methods and emphasized that preserving the triangular inequality is an important feature. However, they felt that the contribution is too incremental compared to the method proposed by Chapel et al. ("Partial Optimal Transport with Applications on Positive-Unlabeled Learning"). Methodologically, the proposed contribution (a penalized formulation, denoted PGW) is closely related to the method of Chapel et al. (a constrained formulation, denoted MPGW). From a numerical perspective, the proposed approach relies on the same Frank-Wolfe (F-W) algorithm. 

In making this decision, there was a discussion with the reviewers, who argued that "solutions of PGW can be obtained via MPGW through appropriate hyper-parameters." While there may be cases where the solutions are non-unique, meaning the mapping is not a bijection of parameters, it remains unclear whether this difference is significant from a practical standpoint, particularly when the parameters are cross-validated. Furthermore, the reviewers pointed out that "Tables 2 and 4 in the appendix discuss experiments on real-world datasets. In those experiments, MPGW achieves the same generalization performance as PGW in both tables." These numerical experiments do not clearly demonstrate that preserving the triangular inequality is a crucial feature for machine learning applications of unbalanced GW.

For these reasons, I cannot recommend acceptance.

Reviews: review: paper_summary: paper_summary: This paper proposes a partial Gromov -Wasserstein (PGW) formulation, which relaxes the original constraints present in Gromov-Wasserstein (GW) formulation. In PGW, the marginal equality constraints of GW are replaced by marginal inequality constraints. Following existing works in partial GW setting, the paper additional imposes TV-based marginal regularization in the objective. The paper showed that the proposed PGW approach defines a metric between metric measure spaces. The PGW problem is solved via Frank-Wolfe (FW) and empirical results are shown on shape interpolation  in the main paper.
strength_weakness: strength_weakness: - The paper is poorly written due to the following reasons:
    - The abstract and introduction states that the paper propose two variants of FW algorithm for solving the proposed PGW. However, the main paper does not describe two variants of FW algorithm. Only one variant is discussed in Sections 4-5. The other variant is described only in Appendix G. If the algorithm Typically, the main paper should be self contained, having the necessary details of the contributions claimed in the abstract and introduction. It should be noted that going through the supplementary material is a reviewer's discretion. 
    - The paper provides very less discussion on how its differences with MPGW [45] in the main paper (lines 148-149). While Appendix L contains this discussion, important parts of it should be discussed in the main paper. As mentioned above, going through the supplementary material is a reviewer's discretion. 
    - There are multiple grammatical and spelling errors throughout the paper. Eg. he -> the, con -> cost, etc. 

- The main paper contained experiments only on synthetic dataset. Tables 2 and 4 in appendix discuss experiments on real-world datasets. MPGW obtains same generalization performance as PGW in both the tables. This should be discussed in the main paper as well.
questions: questions: - In (14), let \beta =  minimum entry in cost tensor M. Then, what is the solution of PGW (16) when \beta > 2\lambda ?

- Why does MPGW obtains 0.0813 and 0 mean accuracy in Table (a) while other methods get > 0.89 and > 0.78 scores, respectively? It should be noted that in Tables 2 and 4 in appendix, MPGW performs at par with PGW.
limitations: limitations: N/A
paper_summary: paper_summary: This paper introduces the Partial Gromov-Wasserstein (PGW) metric as a means to handle unbalanced Gromov-Wasserstein problems between non-probability mm-spaces. The authors develop and demonstrate two computationally efficient variants of the Frank-Wolfe algorithm for solving the PGW problem. They establish that PGW is a well-defined metric, providing theoretical proofs and applications in shape matching, shape retrieval, and interpolation. The metric and algorithms are validated through numerical experiments against established baselines, showcasing improved results in handling outlier data with a robust performance.
strength_weakness: strength_weakness: 1. While the paper provides a comparison with existing methods, it could benefit from a broader range of comparative baselines, especially newer techniques that might provide a stiffer benchmark.

2. The paper does not extensively discuss the sensitivity of the PGW algorithm to the choice of its parameter (e.g., the regularization coefficient - lambda), which is crucial for understanding its robustness and adaptability in diverse real-world scenarios.

3. There is limited discussion on the scalability (or the time complexity) of the proposed methods, particularly in high-dimensional or large-scale settings, which is vital for their applicability in big data applications.
questions: questions: 1. The regularization coefficient lambda is referenced in Equations (9), (10), and (14) of $\tilde{M}$. However, it appears that two of the algorithms do not explicitly incorporate lambda. Could you clarify whether these algorithms require the use of lambda?

2. If lambda is indeed utilized in these algorithms, how does the selection of lambda influence the performance of the PGW metric? Are there guidelines or methods for choosing this parameter optimally based on the dataset characteristics?

3. In practical applications, especially in high-dimensional spaces, what are the computational limitations of the proposed algorithms, and how might these be mitigated?

4. Are there potential extensions of the PGW metric that could handle non-metric spaces, given the increasing interest in such spaces in various applications?
limitations: limitations: Including limitations on the scalability and time complexity, such as the maximum solvable problem size within one hour, would be beneficial for its applications.
paper_summary: paper_summary: The paper considers an unbalanced version of the Gromov-Wasserstein distance, where the discrepancy terms correspond to the total variation between certain product measures for the given marginal and the marginal of the solution, respectively. Different (re)formulations of this distance is considered in both the discrete case and for general measures, existence of optimal solution and metric properties are shown for certain cost functions, as well as numerical methods for computing (local) optimal solutions. Finally a number of numerical experiments are considered.

The paper is well written and extensive. In the main paper the results are stated and with proofs in the  appendix.
strength_weakness: strength_weakness: One weakness with the methods in the paper is that it only provides local optimal solutions. This is a problem with many non-convex problems, but in some cases global solutions can be guaranteed. In the abstract it is stated the methods solve the PGW problem. This is probably to strong statement since they are not guaranteed to converge to the global solution.
questions: questions: 1) In the abstract it is stated the methods solve the PGW problem. This is probably to strong statement since they are not guaranteed to converge to the global solution. 

2) I think that some early references on the partial/unbalanced OT problem are missing. Neither of the following two papers are mentioned in the introduction. Both papers contain the problem formulation (3).

Georgiou, Tryphon T., etal. "Metrics for power spectra: an axiomatic approach." IEEE Transactions on Signal Processing 57.3 (2008): 859-867.

Piccoli, Benedetto, and Francesco Rossi. "Generalized Wasserstein distance and its application to transport equations with source." Archive for Rational Mechanics and Analysis 211 (2014): 335-358.
 
3) Some minor typos: 
line 174: he --> the
line 175: con --> cost
line 574: spit --> split
limitations: limitations: NA
paper_summary: paper_summary: This paper introduces the an unbalance Gromov-Wasserstein distance, which adopted the formulation of unbalance optimal transport into the Gromov-Wasserstein with total variance (TV) penalty instead of KL. This new distance allows comparison of probability measures from different space with partial amount of mass, and so they name it Partial Gromov-Wasserstein (PGW). They further prove the metric properties of this distance and proposed two algorithms to solve PGW: Frank-Wolfe algorithms and Line search method. In experiment section, they test PGW with different tasks including: shape-matching, shape retrieval and barycenter problem.
strength_weakness: strength_weakness: - It's worth to note in literature review the similar works formulating partial Waserstein as a metric with TV constraints [1] [2].
- The proof of the metric properties is not well displayed in the main text, as this is the main highlight of this work.
- Further comparison with KL version was lack as regards to robustness against outliers. And also, further discussion on the scalability (very large dataset) will be appreciated.
- In experiment section, the selection of hyperparameter is not clear. The justification of choosing $\lambda$ value for both PGW and MPGW method was not presented. 

[1] Raghvendra, Sharath, Pouyan Shirzadian, and Kaiyi Zhang. "A New Robust Partial $ p $-Wasserstein-Based Metric for Comparing Distributions." arXiv preprint arXiv:2405.03664 (2024).

[2] Nietert, Sloan, Rachel Cummings, and Ziv Goldfeld. "Robust estimation under the Wasserstein distance." arXiv preprint arXiv:2302.01237 (2023).
questions: questions: - Could you add the parameter sensitivity analysis in experiment section? 
- The table under line 271 doesn't have a title, and in (a) the performance of MPGW is $0$ on Dataset II which looks abnormal to me. Is this the actual experiment result or just a typo?
limitations: limitations: None

Comments: title: Response to Answers to new comments 5
Answers to new comments 5
Response to answers to new comments 4
answers to new comments 4
Reviewer response
Comment
comment
comment
answers to new comments 3
Reviewer response
answers to new comments 2
Response to authors #2
answer to the further questions 4
answers to the further questions 1,2,3
Response to authors
comment: > This statement contradicts the reviewer's original claim (from Response to authors #2):

Previously, I was wondering if the set of solution can be shown to be same for individual values of hyper-parameters. The authors have shown with example that this is not the case. 

However, please note that my previous response was more in the form of a question to the authors (albeit without a question mark) rather than a definite claim about the paper's contribution.


> As stated previously, the authors hoped to clarify exactly this point; namely, that the solution sets to the two problems are different, although particular solutions can coincide.

While this is true for specific values of hyper-parameter values, practically, one does not run the model on one hyper-parameter value. A common practice is to run the model on multiple hyper-parameter values (tuning/cross-validation) and choose one (based on some other criteria). Hence, can the solutions of PGW as one tunes PGW over $lambda$ be obtained by MPGW as one tunes over $\rho$?

I would also increase my score to the original score.
> In this case, we could set $\rho = |\gamma_{PGW}|$ where $\gamma_{PGW}$ is the "another solution". Then $\gamma_{PGW}$ should be a solution for $MPGW_{|\gamma_{PGW}|}(\mu, \nu)$.

This follows immediately from Statement 1 in the global response.

> Since $\lambda$ and $\rho$ are not comparable hyper-parameters, one should not expect that all PGW solutions corresponding to fixed $\lambda$ would be obtained by a MPGW with a fixed $\rho$ and vice-versa.

This statement contradicts the reviewer's original claim (from [**Response to authors \#2**](https://openreview.net/forum?id=nrcFNxF57E&noteId=Mf06ckbj0f)):
 >> Then, in the setting of Example 1 of the global response, it does seem that the solution set of PGW and MPGW can be identical - with appropriate value of $\rho$.

As stated previously, the authors hoped to clarify exactly this point; namely, that the solution sets to the two problems are different, although particular solutions can coincide.
> Choose $i\in[1:n],j\in[1:m]$, $\delta_{(x_i,y_j)}$ is another solution for $PGW_0(\mu,\nu)$. But $\delta_{(x_i,y_j)}$ is not a solution for $MPGW_0(\mu,\nu)$.

In this case, we could set $\rho=|\gamma_{PGW}|$ where $\gamma_{PGW}$ is the "another solution". Then $ \gamma_{PGW}$ should be a solution for $MPGW_{|\gamma_{PGW}|}(\mu,\nu)$. Since $\lambda$ and $\rho$ are not comparable hyper-parameters, one should not expect that all PGW solutions corresponding to fixed $\lambda$ would be obtained by a MPGW with a fixed $\rho$ and vice-versa.
> I am not sure what the phrase another solution of ... 

**Answer**: 

We have explained this in Author Rebuttal example 1 and in the comment “**answers to new comments 2**”.

When $\gamma_{PGW}$ is the zero measure, we set $\rho=|\gamma_{PGW}|=0$:
- The zero measure is a solution for $PGW_0(\mu,\nu)$ and also for $MPGW_0(\mu,\nu)$.
- Choose $i\in[1:n],j\in[1:m]$,  $\delta_{(x_i,y_j)}$  is **another solution** for $PGW_0(\mu,\nu)$. But $\delta_{(x_i,y_j)}$ is **not** a solution for $MPGW_0(\mu,\nu)$.
> However, this does not imply that another solution of of $PGW_{0}(\mu,\nu)$ ...

I am not sure what the phrase *another solution of $PGW_{0}(\mu,\nu)$* implies. The solution of PGW was taken to be $\gamma_{PGW}$, without any assumption. 

> In the shape retrieval experiment,... 

While the author response is true for synthetic shape retrieval experiments, it would be great to see the practical utility of PGW in real world applications involving real-world datasets. Appendix sections contained such experiments where PGW and MPGW had same generalization performance. 

> The definition of $M$ is provided ...

I thank the authors for clarifying my doubts for this question.
Thank you for your comments. 
These two references will be added. 
We will also make other modifications (e.g. a section about parameter selection/sensitivity) based on the reviewer's comments.
Thank you for your comments.
These two references will be added to the paper.
We will also make other modifications based on the reviewer's comments.
The authors thank the reviewer's comment. 

The related results in "computational complexity" section will be added to the paper.
Thank you for your detailed response. Since some of my concerns have been addressed, I will maintain my positive score.
> Let me clarify my question. In Example 1, will the solution of PGW be a first-order critical point of MPGW for an appropriate value of $\rho$? 

**Answer**: 
- In Example 1, we assert that the **solution sets** of $PGW_0(\mu,\nu)$ and $MPGW_\rho$ are different. We have already explained the distinction between these **sets** in our author rebuttal and in previous comment.  
   > In my earlier question, "Given $\lambda=0$, solve PGW and obtain the solution $\gamma_{PGW}$. Then set $\rho=|\gamma_{PGW}|$. Now, would the first-order critical points of MPGW contain $\gamma_{PGW}$?", the author responded "yes." 

- The answer to this earlier question remains yes, as we previously explained. This particular $\gamma_{PGW}$ is also a solution for $MPGW_\rho(\mu,\nu)$ since $\rho=|\gamma_{PGW}|$. However, this does not imply that **another** solution of $PGW_0(\mu,\nu)$ will also be a solution for this specific $MPGW_\rho(\mu,\nu)$. 
- Therefore, there is no contradiction to our claim "**the solution sets of the two problems are different**", although particular solutions might coincide. 

> In the global response, it was stated that PGW has the advantage of being a metric (whereas MPGW is not). Perhaps some experiments should be conducted to demonstrate the utility of PGW as a metric. 

**Answer**: In the shape retrieval experiment, we obtained GW/UGW/MPGW/PGW costs to describe the similarity between two shapes. 
Since PGW and GW are metrics, they induce better performance than the other two methods. 
That is shown in table on page 8.  

> I am not sure why $\min M$ should be zero....

**Answer**: The definition of $M$ is provided in Eq (14), and the definitions of $C^X$ and $C^Y$ are given in Eq (11). 

In particular $(C^X)_{i,i}=d_X(x_i,x_i')$ where $d_X$ is a metric. 

Thus, when $i=i'$, $C^X_{i,i'}=0$. That is, diagonal elements of matrix $C^X$ are zero. Similarly, diagonal elements of matrix $C^Y$ are zero. 

Based on the definition of $M$, we have 
$$\min M=|C_{1,1}^X-C_{1,1}^Y|^2=|d_X(x_1,x_1)-d_Y(y_1,y_1)|^2=|0-0|^2=0.$$
Regarding 
> There may have been some confusion here. 

Let me rephrase my question. In this example 1, will the solution of PGW be a first order critical point of MPGW with appropriate value of $\rho$? In my earlier question "Given $lambda=0$, solve PGW and obtain the solution $\gamma_{PGW}$. Then set $\rho=|\gamma_{PGW}|$. Now, would the first order critical points of MPGW contain $\gamma_{PGW}$?", the author response was "yes"


> If the reviewer is instead concerned with the similar performance of PGW and MPGW in Tables 2 and 4 in the appendix, this is discussed in the global response under the heading "Positive Label Unsupervised Learning", as stated earlier.

In the global response, it has been stated that PGW has the advantage of being a metric (while MPGW is not). Then, perhaps some experiments where the utility of PGW being a metric comes out -  should be performed. 

> There still seems to be some confusion here. 

I am not sure why $\min M$ should be zero. It would be great if the authors could explain it. My understanding is as follows: M is computed using (14) - using $C^X$ and $C^Y$ matrices. If none of the entries of $C^X$ is equal to $C^Y$, $\min M$ would not be zero. So $\beta = \min M$ seems to be a positive entry and for any $0<\lambda < \beta/2$, the PGW distance has a closed form solution $\lambda(|p|^2 + |q|^2)$. So there is no question of setting $\lambda=0$.
> Then, in the setting of Example 1 of the global response, it does seem that the solution set of PGW and MPGW can be identical - with appropriate value of $\rho$.

**Answer**: There may have been some confusion here. In Example 1, the **solution sets** of PGW and MPGW are **NOT** identical for any $\rho\in [0, \min{(|\mu|,|\nu|)}]$.

- The solution set of $PGW_0(\mu, \nu)$ contains $\{\delta_{(x_i, y_j)} : i\in[1:n], j\in[1:m]\} \cup \{0\}$. 
- When $\rho>0$, the zero measure is a solution for $PGW_0(\mu,\nu)$, but it is not a solution for $MPGW_\rho(\mu,\nu)$. 
- When $\rho=0$, $\delta_{(x_i,y_j)}$ is a solution of $PGW_\lambda(\mu,\nu)$, but it is not a solution for $MPGW_0(\mu,\nu)$. 

> From the author response, I think we are on the same page. In the original review, I had written - "The main paper contained experiments only on synthetic dataset. Tables 2 and 4 in appendix discuss experiments on real-world datasets. MPGW obtains same generalization performance as PGW in both the tables."

**Answer**: Thank you for the clarification. We would once again like to note that the scope of our numerical experiments is consistent with existing literature on GW and unbalanced GW. If the reviewer is instead concerned with the similar performance of PGW and MPGW in Tables 2 and 4 in the appendix, this is discussed in the global response under the heading "Positive Label Unsupervised Learning", as stated earlier.

> 5. The response of one of my questions in my original review was a bit unclear. The question was "In (14), let \beta = minimum entry in cost tensor M. Then, what is the solution of PGW (16) when \beta > 2\lambda ?"
>
> The solution of (16) seems to be zero when \beta > 2\lambda. If this is indeed the case, then the PGW distance between two distributions with marginals p and q, respectively, and with \lambda < \beta/2 will be \lambda(|q|^2 + |p|^2) (from 15) - which is a constant dependent on hyper-parameter and marginals. This restricts PGW's ability to distinguish the source distribution with target distributions of same marginal norm (|q|=|q_1|=|q_2|). No geometric information is being taken into account.

**Answer**: There still seems to be some confusion here. When $\beta=\min M$ as specified in the reviewer's original comment, this results in $\beta = 0$. To be precise, since $\lambda$ cannot be negative number, we first correct $2\lambda<\beta=0$ to $2\lambda\leq \beta=0$, i.e., $\lambda = 0$. As a result, $PGW_0(\mu, \nu)$ admits the zero measure as one solution, and the PGW distance will be $\lambda(|q|^2+|p|^2)=0$ as $\lambda=0$.

> This restricts PGW's ability to distinguish the source distribution with target distributions of same marginal norm (|q|=|q_1|=|q_2|).

As stated in Proposition 3.4, PGW is a metric which can distinguish two measures if $\lambda>0$. In this case, $\lambda=0$ and thus PGW  cannot distinguish the difference between the source and target distributions. The resulting analysis given by the reviewer simply reflects the fact that $\lambda=0$ is a **bad** choice of hyperparameter when we aim to apply PGW as a metric.
> Answer: Yes.
> In this case, if we select the zero measure, which is an optimal solution for PGW, and set , the global solution coincides with the first-order critical point of MPGW. In fact, the space $\Gamma_{\leq}^{\rho}(\mu,\nu)$ contains only a single element for MPGW.

Then, in the setting of Example 1 of the global response, it does seem that the solution set of PGW and MPGW can be identical - with appropriate value of $\rho$. 

 > Our statement regarding our use of both synthetic and real-world data remains to be correct. To clarify:

From the author response, I think we are on the same page. In the original review, I had written - "The main paper contained experiments only on synthetic dataset. Tables 2 and 4 in appendix discuss experiments on real-world datasets. MPGW obtains same generalization performance as PGW in both the tables."

> No, it does not contradict with Lemma E.2.

Please excuse my oversight. I had written incorrectly statement 3 in my previous response. 

5. The response of one of my questions in my original review was a bit unclear. The question was "In (14), let \beta = minimum entry in cost tensor M. Then, what is the solution of PGW (16) when \beta > 2\lambda ?"

The solution of (16) seems to be zero when \beta > 2\lambda. If this is indeed the case, then the PGW distance between two distributions with marginals p and q, respectively, and with \lambda < \beta/2 will be \lambda(|q|^2 + |p|^2) (from 15) - which is a constant dependent on hyper-parameter and marginals. This restricts PGW's ability to distinguish the source distribution with target distributions of same marginal norm (|q|=|q_1|=|q_2|). No geometric information is being taken into account.
I appreciate your rebuttal. Your response addressed my concerns. I think this work is worth for publication and so I raise my score.
Thank you for your rebuttal and the additional clarifications.

About the comment: "We apologize for only citing the classical reference from the authors who introduced this concept (Mccann and Figalli) initially."

No need to apologize. However, note that the reference above introduced the same "optimal partial transport" formulation (3) and was published 2 years before the earliest references on this that was provided in the paper.
4. In the appendix L.1 example, does $MPGW_\rho(X_i,X_j)=0$ for all values of $\rho$? What about $\rho = |\gamma_{PGW}|?$

**Answer:** Yes, $MPGW_\rho(X_i,X_j)=0$ for all values of $\rho$, including $\rho = |\gamma_{PGW}|$.

Below, we provide the reasoning to clarify this point. In this example:

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

where $\alpha=1e-3$, $\lambda=1e+1$, and $x_i \in [0,1]^2$ for all $i$.

Let $\gamma_{1,2}$ be the optimal solution for $PGW_\lambda(X_1,X_2)$, then we have $|\gamma_{1,2}|=0.8$. Similarly, we define $\gamma_{1,3}$ and $\gamma_{2,3}$, where $|\gamma_{1,3}|=0.4$ and $|\gamma_{2,3}|=0.4$. The numerical results are consistent with our Lemma E.2.
We can verify the following:

$$MPGW_{0.8}(\mathbb{X}^1,\mathbb{X}^2)=0, \text{ where } |\gamma_{1,2}|=0.8,$$
$$MPGW_{0.4}(\mathbb{X}^1,\mathbb{X}^3)=0, \text{ where } |\gamma_{1,3}|=0.4,$$
$$MPGW_{0.4}(\mathbb{X}^2,\mathbb{X}^3)=0, \text{ where } |\gamma_{2,3}|=0.4.$$

For the case of arbitrary $\rho > 0$, we may first consider the problem $MPGW_{\rho}(\mathbb{X}^1,\mathbb{X}^2)$. Let $\gamma^*=\sum_{i=1}^{800}\alpha\delta_{(x_i,x_i)}$ denote the transportation plan induced by the Monge mapping $x_i \mapsto x_i$ for all $i \in [1:800]$. Then, $\frac{\rho}{|\gamma^*|}\gamma$ will be an optimal solution for $MPGW_{\rho}(\mathbb{X}^1,\mathbb{X}^2)$. Consequently, $MPGW_{\rho}(\mathbb{X}^1,\mathbb{X}^2) = 0$. 
We may apply similar reasoning to see that $MPGW_{\rho}(\mathbb{X}^1,\mathbb{X}^3),MPGW_{\rho}(\mathbb{X}^2,\mathbb{X}^3)=0$ for any $\rho\in[0,0.4]$ as well, where 0.4 is the largest value we can choose for $\rho$ in these two MPGW problems.

Run [this link](https://anonymous.4open.science/r/PGW_metric-5DCB/example_gw.ipynb) (cell 1 and cell 3) to see a numerical example. Note that, as we set the tolerance of PGW/MPGW algorithms to 1e-5, the values of $MPGW_{0.8}(\mathbb{X}^1,\mathbb{X}^2)$, $MPGW_{0.4}(\mathbb{X}^1,\mathbb{X}^3)$, and $MPGW_{0.4}(\mathbb{X}^2,\mathbb{X}^3)$ are of the order $\mathcal{O}(1e-5)$, rather than exactly 0.
We appreciate the reviewer’s engagement with our work and the response to our rebuttal. While we respect the reviewer's perspective, we have concerns that the current evaluation may not fully reflect the scientific and technical merits of our paper. The original review did not identify any theoretical flaws, instead raising minor clarification questions that we have thoroughly addressed. We also recognize the reviewer's comments regarding the paper's organization and the request for additional experiments on real-world data. However, these concerns do not appear to undermine the fundamental theoretical contributions of our work, which we feel may have been overlooked. Furthermore, we would like to highlight that the scope of our numerical experiments is consistent with prior work on Gromov-Wasserstein (GW) and unbalanced GW. We would welcome further discussion rooted in specific scientific reasoning and detailed feedback, which would enhance the constructive nature of this review process.

1. "Regarding global response Statement 1 example 1:..." 

**Answer:** Yes. 

In this case, if we select the zero measure, which is an optimal solution for PGW, and set $\rho=|\gamma|=0$, the global solution coincides with the first-order critical point of MPGW. In fact, the space $\Gamma_\leq^\rho(\mu,\nu)$ contains only a single element for MPGW.

Otherwise, as explained in the author rebuttal, if we choose $\gamma=\delta_{(x_i,y_j)}$, where $i \in [1:n]$ and $j \in [1:m]$, which is also an optimal solution for $PGW_0(\mathbb{X},\mathbb{Y})$, and we set $\rho=|\gamma|=1$, then $\gamma=\delta_{(x_i,y_j)}$ would be one of the first-order critical points of $MPGW_1(\mathbb{X},\mathbb{Y})$ and a  solution to the MPGW problem.

2. "Regarding the authors' response "both synthetic and real datasets are applied in this paper..." 

**Answer:** Our statement regarding our use of both synthetic and real-world data remains to be correct. To clarify:

- In the shape retrieval experiment (Section 5.2), “Dataset I” is derived from [51] and “Dataset II” is entirely synthetic. Dataset I is also synthetic; we do not mean to claim otherwise, only to outline the sources of data in our experiments.
- The data for the point cloud interpolation experiment comes from [41]. This dataset is also synthetic, but nevertheless used in prior GW papers for method evaluation.
- MNIST and EMNIST are real-world yet small-scale problems commonly used for demonstration purposes, and the Amazon, Webcam, and DSLR are clearly real-world datasets.

3. "Regarding, "In (14), let \beta = minimum entry in cost tensor M", I agree with the authors that the optimal solution will be a zero measure if lambda is sufficiently large. However, does the author response contract their Lemma E.2. 

**Answer:** No, it does not contradict with Lemma E.2. 

Here, we point out that the reviewer might have misinterpreted our response or there might have been a confusion. The optimal solution will be a zero measure if $\lambda$ is sufficiently **small** (e.g., $\lambda \leq\min(M)$).  When $\lambda$ is sufficiently large, based on our Lemma E.2., the $|\gamma|$ will achieve its maximum, that is $|\gamma|=\min(|\mu|,|\nu|)$.
I thank the authors for their rebuttal. Please find my (further) questions below. 

1. Regarding global response Statement 1 example 1: Given $lambda=0$, solve PGW and obtain the solution $\gamma_{PGW}$. Then set $\rho=|\gamma_{PGW}|$. Now, would the first order critical points of MPGW contain $\gamma_{PGW}$?

2. Regarding the authors' response "both synthetic and real datasets are applied in this paper:"
- By the statement "In the shape retrieval experiment (Section 5.2), the dataset is given in [51].", are the authors claiming that this experiment use real-world dataset?
- By the statement "In the point cloud interpolation experiment (Section 5.3), the dataset is from Github (link)", are the authors claiming that this experiment use real-world dataset?
- Regarding experiments in Section P, I have already acknowledged that they are the only real-world experiments in the whole manuscript. 

3. Regarding, "In (14), let \beta = minimum entry in cost tensor M", I agree with the authors that the optimal solution will be a zero measure if lambda is sufficiently large. However, does the author response contract their Lemma E.2. 

4. In the appendix L.1 example, does $MPGW_\rho(X_i,X_j)$ = 0 for all values of rho? What about $\rho=|\gamma_{PGW}|$? 

Overall, I have found the author response underwhelming. Hence, for now, I am reducing my score by one.