Fused Partial Gromov–Wasserstein for Structured Objects Yikun Bai, Shuang Wang, Huy Tran, Hengrong Du, Juexin Wang, Soheil Kolouri Abstract Structured data, such as graphs, is vital in machine learning due to its capacity to capture complex relationships and interactions. In recent years, the Fused Gromov-Wasserstein (FGW) distance has attracted growing interest because it enables the comparison of structured data by jointly accounting for feature similarity and geometric structure. However, as a variant of optimal transport (OT), classical FGW assumes an equal mass constraint on the compared data. In this work, we relax this mass constraint and propose the Fused Partial Gromov-Wasserstein (FPGW) framework, which extends FGW to accommodate unbalanced data. Theoretically, we establish the relationship between FPGW and FGW and prove the metric properties of FPGW. Numerically, we introduce Frank-Wolfe solvers and Sinkhorn solvers for the proposed FPGW framework. Finally, we evaluate the FPGW distance through graph matching, graph classification and graph clustering experiments, demonstrating its robust performance. 1 Introduction Figure 1 : An intuitive understanding of the fused-PGW problems ( 9 ). The distance between node features is modeled as d(\cdot,\cdot) . The structural information of each graph is represented by their shortest path distances, C_{1}(\cdot,\cdot) and C_{2}(\cdot,\cdot) . Analyzing structured data, which combines feature-based and relational information, is a longstanding challenge in machine learning, data science, and statistics. One classical type of structure-based data is the graph, where the nodes with attributes can model the data feature while the edges can describe the structure. Examples of such data structures are abundant, including molecular graphs for drug discovery [ 1 ] , functional and structural brain networks [ 2 ] , and social network graphs [ 3 ] . Beyond graphs, structured data encompasses a wide variety of domains, such as sequences [ 4 ] , hierarchical structures such as trees [ 5 ] , and even pixel-based data, such as images [ 6 ] . In recent years, the Optimal Transport (OT) distance [ 7 ] and its extensions, including unbalanced Optimal Transport [ 8 , 9 ] , linear Optimal Transport [ 10 , 11 , 12 , 13 ] , sliced optimal transport [ 14 , 15 , 16 ] , and expected optimal transport [ 17 ] have been widely used in machine learning tasks due to their capacity to measure the similarity between datasets. Based on the classical OT, Gromov-Wasserstein problem and its unbalanced extension [ 18 , 19 , 20 , 21 , 22 , 23 ] has been proposed, which can capture the inherent structure of the data. Classical OT can incorporate the features of data to measure the similarity and Gromov-Wasserstein formulations capture the structure information. Inspired by these works, fused Gromov-Wasserstein [ 24 , 25 ] , which can be treated as a “linear combination” of classical OT and Gromov-Wasserstein has been proposed in recent years to analyze the structured feature data. Despite its successful applications in graph data analysis, similar to classical OT, fused GW formulation requires equal mass constraint. To address this issue, in recent years, Fused Unbalanced Gromov Wasserstein (FUGW) [ 26 , 27 ] and related Sinkhorn solvers have been proposed and applied in brain image analysis. However, FUGW relies on the Sinkhorn solver, and its metric property is still unclear. To address this limitation and complete the theoretical gap, in this paper, we introduce the fused-partial Gromov-Wasserstein formulations: – We introduce the fused partial Gromov Wasserstein formulations ( 11 ), which allow the comparison of structured objects with unequal total mass. Theoretically, we demonstrate that the FPGW admits a (semi-)metric. – We propose the related Frank-Wolfe algorithms and Sinkhorn Algorithms to solve the FPGW problem. In addition, we present the FPGW barycenter and related computational solvers. – We applied FPGW in graph matching, clustering and classification experiments and demonstrated that the FPGW-based methods admit more robust performance. 2 Background: Gromov-Wasserstein (GW) Problems Note, graph-structured data can be measured as a metric measure space (mm-space) consisting of a set X endowed with a metric structure, that is, a notion of distance d_{X} between its elements, and equipped with a Borel measure \mu . As in ( 18 , Ch. 5) , we will assume that X is compact and that \operatorname{supp}(\mu)=X . Given two probability mm-spaces \mathbb{X}=(X,d_{X},\mu) , \mathbb{Y}=(Y,d_{Y},\nu) , with \mu\in\mathcal{P}(X) and \nu\in\mathcal{P}(Y) , and a non-negative lower semi-continuous cost function L:\mathbb{R}^{2}\to\mathbb{R}_{+} (e.g., the Euclidean distance or the KL-loss), the Gromov-Wasserstein (GW) matching problem is defined as: GW_{r,L}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\gamma^{\otimes 2}(L(d_{X}^{r}(\cdot,\cdot),d_{Y}^{r}(\cdot,\cdot))), (1) where r\geq 1 and \displaystyle\Gamma(\mu,\nu):=\{\gamma\in\mathcal{P}(X\times Y):\gamma_{1}=\mu,\gamma_{2}=\nu\}. (2) For brevity, we employ the notation \gamma^{\otimes 2} for the product measure d\gamma^{\otimes 2}((x,y),(x^{\prime},y^{\prime}))=d\gamma(x,y)d\gamma(x^{\prime},y^{\prime}) . If L(a,b)=|a-b|^{q} , for 1\leq q<\infty , we denote GW_{r,L}(\cdot,\cdot) by d_{GW,r,q}^{q}(\cdot,\cdot) . In this case, the expression ( 1 ) defines an equivalence relation \sim among probability mm-spaces, i.e., \mathbb{X}\sim\mathbb{Y} if and only if d_{GW,r,q}(\mathbb{X},\mathbb{Y})=0 1 1 1 Moreover, given two probability mm-spaces \mathbb{X} and \mathbb{Y} , d_{GW,r,q}(\mathbb{X},\mathbb{Y})=0 if and only if there exists a bijective isometry \phi:X\to Y such that \phi_{\#}\mu=\nu . In particular, the GW distance is invariant under rigid transformations (translations and rotations) of a given probability mm-space. . A minimizer of the GW problem ( 1 ) always exists, and thus, we can replace \inf by \min . Moreover, similar to OT, the above GW problem defines a distance for probability mm-spaces after taking the quotient under \sim . For details, we refer to ( 18 , 28 , Ch. 5 and 10) . Classical GW requires an equal mass assumption, i.e., |\mu|=|\nu| , which limits its application in many machine learning tasks, e.g., positive unsupervised learning [ 21 , 29 ] . To address this issue, in recent years, the above formulation has been extended to the unbalanced setting [ 21 , 29 , 28 , 12 ] . In particular, two equivalent extensions of the Gromov-Wasserstein problem, named Partial Gromov-Wasserstein problem and Mass-constrained Partial Gromov-Wasserstein problem have been proposed: \displaystyle PGW_{r,L}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r}))+\lambda(|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|+|\nu^{\otimes 2}-\gamma_{2}^{\otimes 2}|) (3) \displaystyle MPGW_{r,L}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r})). (4) where \displaystyle\Gamma_{\leq}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(X\times Y):\gamma_{1}\leq\mu,\gamma_{2}\leq\nu\}, (5) \displaystyle\Gamma_{\leq}^{\rho}(\mu,\nu):=\{\gamma\in\Gamma_{\leq}(\mu,\nu):|\gamma|=\rho\},\rho\in[0,\min(|\mu|,|\nu|)], (6) and the notation \gamma_{1}\leq\mu denotes that for each Borel set B\subset X , \gamma_{1}(B)\leq\mu(B) . Note that both GW and its unbalanced extension can measure the similarity of structure data by utilizing their in-structure distance d_{X} and d_{Y} . The above formulation can naturally measure similarity between graph data (X,E_{X}),(Y,E_{Y}) , since we can define d_{X} (and d_{Y} ) by the (weights of) edges E_{X} (and E_{Y} ). However, suppose that nodes X,Y contain features (e.g., attributed graphs), and thus we can define the distance between (x,y) where for each pair of nodes x\in X,y\in Y , classical GW/PGW can not incorporate this information. To address this limitation, Fused Gromov-Wasserstein distance has been proposed. 2.1 Fused Gromov-Wasserstein problem Given two mm- spaces \mathbb{X},\mathbb{Y},\omega_{1},\omega_{2}\geq 0 with \omega_{1}+\omega_{2}=1 , a cost function C:X\times Y\to\mathbb{R}_{+} , the fused Gromov-Wasserstein problem is defined as: \displaystyle FGW_{r,L}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\omega_{1}\gamma(C)+\omega_{2}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r})). (7) Similar to the original GW problem, the above problem admits a minimizer. In addition, when C(x,y)=\|x-y\|^{q} , and L(\cdot_{1},\cdot_{2})=|\cdot_{1}-\cdot_{2}|^{q} , it defines a semi-metric [ 30 ] . 2.2 Fused Unbalanced Gromov-Wasserstein problem. The above formulation relies on the equal mass assumption, i.e., |\mu|=|\nu| . By relaxing this constraint, the authors in [ 26 ] have proposed the following fused-UGW problem: \displaystyle FUGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\mathcal{M}_{+}(X\times Y)}\omega_{1}\gamma(C)+\omega_{2}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r}))+\lambda(D_{\phi_{1}}(\gamma_{1}^{\otimes 2}\parallel\mu^{\otimes 2})+D_{\phi_{2}}(\gamma_{2}^{\otimes 2}\parallel\nu^{\otimes 2})), (8) where \mathcal{M}_{+}(X\times Y) denotes the set of all positive Radon measures defined on X\times Y , D_{\phi_{i}},i\in[1:2] are the f-divergence terms. In [ 26 ] , the authors set D_{\phi_{i}},i\in[1:2] as KL divergence. They adapt entropic regularization and propose the related Sinkhorn solver. 3 Fused Partial Gromov-Wasserstein problem Inspired by these previous works, by setting the f-divergence terms D_{\phi_{i}} to be the Total variation, we propose the following “fused partial Gromov Wasserstein problem”, and the corresponding mass-constrained version: \displaystyle FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\mathcal{M}_{+}(X\times Y)}\omega_{1}\gamma(C)+\omega_{2}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r}))+\lambda(|\mu^{\otimes 2}-\gamma_{1}^{\otimes 2}|_{TV}+|\nu^{\otimes 2}-\gamma_{2}^{\otimes 2}|_{TV}), (9) \displaystyle FMPGW_{r,L,\rho}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\Gamma^{\rho}_{\leq}(\mu,\nu)}\omega_{1}\gamma(C)+\omega_{2}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r})). (10) where \lambda\geq 0 . 2 2 2 The discrete version of formulation 10 has been discussed in [ 31 ] and one of its special case ( 10 ) has been introduced by [ 32 ] . However, to the best of our knowledge, its fundamental properties and computational methods are not formally discussed in the previous works. We present this formulation as a byproduct of the main contribution of this paper and serve it as a completion of the previous work. Theorem 3.1 . We have the following: (1) When C(x,y)\geq 0,\forall x,y,L(\mathrm{r}_{1},\mathrm{r}_{2})\geq 0,\forall\mathrm{r}_{1},\mathrm{r}_{2}\in\mathbb{R} , the problem ( 9 ) can be further simplified as \displaystyle FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y})=\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\omega_{1}\gamma(C)+\omega_{2}\gamma^{\otimes 2}(L(d_{X}^{r},d_{Y}^{r})-2\lambda)+\lambda(|\mu|^{2}+|\nu|^{2}) (11) (2) The problems ( 9 ), ( 11 ) and ( 10 ) admit minimizer \gamma . (3) When C(x,y)=|x-y|^{q},L(\cdot_{1},\cdot_{2})=|\cdot_{1}-\cdot_{2}|^{q} , \omega_{2},\lambda>0 , the above formulation ( 11 ) admits a semi-metric. Furthermore, when q=1 , ( 11 ) defines a metric. 3.1 Algorithms for Discrete FPGW In discrete case, say \mu=\sum_{i=1}^{n}p_{i}\delta_{x_{i}},\nu=\sum_{i=1}^{m}q_{j}\delta_{y_{j}} . Let C^{X}=[d_{X}(x_{i},x_{i^{\prime}})]_{i,i^{\prime}}\in\mathbb{R}^{n\times n},C^{Y}=[d_{Y}(y_{j},y_{j^{\prime}})]_{j,j^{\prime}} . Thus, (C^{X},\mu),(C^{Y},\nu) can represent the mm-spaces \mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) , respectively. We only discuss the Frank Wolfe solver and Sinkhorn solver for FPGW 11 in the main text. The solvers for FMPGW 10 are discussed in the appendix. 3.2 Frank-Wolfe Algorithm The above FPGW problem ( 11 ) becomes the following: \displaystyle FPGW_{\rho}(\mathbb{X},\mathbb{Y})= \displaystyle\min_{\gamma\in\gamma_{\leq}^{\rho}(p,q)}\underbrace{\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle(M-2\lambda)\circ\gamma,\gamma}_{\mathcal{L}_{C,M-2\lambda}}\rangle+\underbrace{\lambda(|\mu|^{2}+|\nu|^{2})}_{\text{constant}}\rangle (12) where C=[d(x_{i},y_{j})]_{i\in[1:n],j\in[1:m]},M=[|d_{X}(x_{i},x_{i^{\prime}})-d_{Y}(y_{j},y_{j^{\prime}})|^{2}]_{i,i^{\prime}\in[1:n],j,j^{\prime}\in[1:m]} are defined in the previous subsection, M-2\lambda denote the elementwise subtraction, and the constant term will be ignored in the remainder of the paper. Similarly to the Fused Gromov-Wasserstein problem, we propose the following Frank-Wolfe algorithm as a solver: The above problem will be solved iteratively. In every iteration, say k , we will adapt the following steps: Step 1. Gradient computation. Suppose \gamma^{(k-1)} is the transportation plan in the previous iteration; it is straightforward to verify: \nabla\mathcal{L}_{C,M-2\lambda}(\gamma)=\omega_{1}C+\omega_{2}(M+M^{\top}-4\lambda)\circ\gamma. Next, we aim to find the optimal \gamma\in\Gamma_{\leq}(\mu,\nu) for the following partial OT problem: \displaystyle\gamma^{(k)}{{}^{\prime}}:=\arg\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\langle\nabla\mathcal{L}_{C,M-2\lambda}(\gamma^{(k-1)}),\gamma^{k}\rangle. (13) Step 2. linear search algorithm. In this step, we aim to find the optimal step size \alpha^{*}\in[0,1] . In particular, \displaystyle\alpha^{*}:=\arg\min_{\alpha\in[0,1]}\mathcal{L}_{C,M-2\lambda}((1-\alpha)\gamma^{(k-1)}+\alpha\gamma^{(k)}{{}^{\prime}}). and \alpha^{*} is given by the following: \displaystyle\alpha^{*}=\begin{cases}1&\text{if }a\leq 0,a+b\leq 0,\\ 0&\text{if }a\leq 0,a+b>0\\ \text{clip}(\frac{-b}{2a},[0,1]),&\text{if }a>0\end{cases},\begin{cases}a&=\omega_{2}\langle(M-2\lambda)\circ\delta\gamma,\delta\gamma\rangle\\ b&=\langle\omega_{2}(M+M^{\top}-4\lambda)\circ\gamma^{(k-1)}+\omega_{2}C,\delta\gamma\rangle\\ \delta\gamma&=\gamma^{(k)^{\prime}}-\gamma^{(k-1)}\end{cases} (14) Algorithm 1 Frank-Wolfe Algorithm for FPGW Input: C\in\mathbb{R}^{n\times m},C^{X}\in\mathbb{R}^{n\times n},C^{Y}\in\mathbb{R}^{m\times m},p\in\mathbb{R}^{n}_{+},q\in\mathbb{R}^{m}_{+} , \omega_{2}\in[0,1],\lambda\geq 0 . Output: \gamma^{(final)} for k=1,2,\ldots do G^{(k)}\leftarrow\omega_{1}C+\omega_{2}(M+M^{\top}-4\lambda)\circ\gamma^{(k)} // Compute gradient \gamma^{(k)}{{}^{\prime}}\leftarrow\arg\min_{\gamma\in\Gamma_{\leq}(\mathrm{p},\mathrm{q})}\langle G^{(k)},\gamma\rangle_{F} // Solve the POT problem. Compute \alpha^{(k)}\in[0,1] via ( 14 ) // Line Search \gamma^{(k+1)}\leftarrow(1-\alpha^{(k)})\gamma^{(k)}+\alpha^{(k)}\gamma^{(k)^{\prime}} // Update \gamma if convergence, break end for \gamma^{(final)}\leftarrow\gamma^{(k)} In algorithm ( 1 ), the computational complexity can be written as \mathcal{O}(\mathrm{C}\cdot\mathrm{L}) , where \mathrm{C} is the complexity of each iteration and \mathcal{L} is number of iterations that the algorithms converge. When a linear programming solver [ 33 ] for partial OT is adopted, \mathcal{C}=(n+m)nm . If we adapt Sinknorn algorithm [ 34 ] , \mathcal{C}=\mathcal{O}(\frac{1}{\epsilon}\ln(n+m)nm) . The number of iterations \mathcal{L} refers to the convergence analysis of the FW algorithm. We refer to the Appendix ( H ) for details. 3.3 Sinkhorn Algorithm Another popular solver for the Gromov Wasserstein problem is the Sinkhorn algorithm [ 29 ] . In Fused-PGW setting, the problem is defined as: \displaystyle EFPGW(\mathbb{X},\mathbb{Y}) \displaystyle:=\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\mathcal{L}(\gamma)+\epsilon\overline{D}_{KL}(\gamma^{\otimes 2}\parallel(\mu\otimes\nu)^{\otimes 2}) (15) \displaystyle\overline{D}_{KL}(A\parallel B)=\int\frac{dA}{dB}dA,\text{ for any postivie radon measures }A,B \displaystyle\mathcal{L}(\gamma):=\mathcal{L}_{C,M-2\lambda}=\omega_{1}\langle c,\gamma\rangle+\omega_{2}\langle L(d_{X}^{r},d_{Y}^{r}),\gamma^{\otimes 2}\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}). Problem ( 15 ) can be further relaxed as: \displaystyle\min_{\gamma,\pi\in\Gamma_{\leq}(\mu,\nu)}\mathcal{F}(\gamma,\pi)+\epsilon\overline{D}_{KL}(\pi\otimes\gamma\parallel(\mu\otimes\nu)^{\otimes 2}) (16) \displaystyle\mathcal{F}(\mu,\nu):=\omega_{1}\langle d(x,y),\frac{\gamma+\pi}{2}\rangle+\omega_{2}\langle L(d_{X}^{r},d_{Y}^{r}),\gamma\otimes\pi\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma||\pi|) It is clear \mathcal{F}(\gamma,\gamma)=\mathcal{F}(\gamma) . Thus, (\ref{eq:entropy-fpgw-2-main})\leq(\ref{eq:entropy-fpgw-main}) , and we denote ( 16 ) as LB-FPGW_{\lambda}(\mathbb{X},\mathbb{Y}) (lower bound of Fused Partial Gromov Wasserstein). Essentially, the Sinkhorn algorithm aims to solve LB-FPGW . We first introduce the following fundamental proposition. Note, a similar version can be found in ( 20 , Proposition 4) : Proposition 3.2 . Given a fixed \pi\in\Gamma_{\leq}(\mu,\nu) , considering the problem: \min_{\gamma\in\mathcal{M}_{+}(X\times Y)}\mathcal{F}(\pi,\gamma)+\epsilon\overline{D}_{KL}(\pi\otimes\gamma\parallel(\mu\otimes\nu)^{\otimes 2}), it is equivalent to solve the following entropic optimal partial transport problem: \displaystyle\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{X\times Y}c_{\pi}(x,y)d\gamma+\lambda|\pi|(|\mu|+|\nu|-2|\gamma|)+\epsilon|\pi|\overline{D}_{KL}(\gamma\parallel\mu\otimes\nu), (17) where \displaystyle c_{\pi}(x,y) \displaystyle=\frac{1}{2}\omega_{1}d(x,y)+\omega_{2}[L(d_{X}^{r},d_{Y}^{r})\circ\pi](x,y)+\epsilon\overline{D}_{KL}(\pi\parallel\mu\otimes\nu). Given these fundamental results, we can present the Sinkhorn algorithm 2 . Algorithm 2 Sinkhorn Algorithm for FPGW Input: C\in\mathbb{R}^{n\times m},C^{X}\in\mathbb{R}^{n\times n},C^{Y}\in\mathbb{R}^{m\times m},p\in\mathbb{R}^{n}_{+},q\in\mathbb{R}^{m}_{+} , \omega_{2}\in[0,1],\lambda\geq 0 . Output: \gamma for k=1,2,\ldots do \pi\leftarrow\gamma Solve the Sinkhorn partial OT problem ( 17 ): \gamma\leftarrow\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{X\times Y}c_{\pi}(x,y)d\gamma+\lambda|\pi|(|\mu|+|\nu|-2|\gamma|)+\epsilon|\pi|D_{KL}(\gamma\parallel\mu\otimes\nu) Fix \gamma and solve the similar Sinkhorn partial OT problem ( 17 ): \pi\leftarrow\min_{\pi\in\Gamma_{\leq}(\mu,\nu)}\int_{X\times Y}c_{\gamma}(x,y)d\gamma+\lambda|\gamma|(|\mu|+|\nu|-2|\pi|)+\epsilon|\pi|D_{KL}(\pi\parallel\mu\otimes\nu) Rescale \gamma\leftarrow\sqrt{|\pi|/|\gamma|}\gamma Break if \pi\approx\gamma end for 4 Numerical Applications (a) FGW-kmeans (b) FPGW-kmeans Figure 2 : We present the clustering results of the FGW and FPGW k-means methods. In the first column, we visualize the centroids obtained using both methods. The centroids are represented by their features and structure (distance matrix). The edges of these graphs are either reconstructed or approximated based on the returned distance matrix. Additionally, the color of each node corresponds to its feature. The clustering results are shown in the remaining columns. For each graph, the color of regular nodes represents their features, while all outlier nodes are depicted as black squares. 4.1 Toy example: Graph clustering Given a set of unlabeled graphs \{G_{1},\ldots G_{K}\} , we compare the performance of FGW and FPGW in the graph clustering task. Dataset setup. We adapt the dataset generated by [ 24 ] . Each graph follows a simple Stochastic Block Model, and the groups are defined w.r.t. the number of communities inside each graph and the distribution of their labels. The dataset contains three different types of graphs, and each type contains five graphs. Each graph contains 30 or 40 nodes, and the feature of each node is randomly selected in a compact set [-2,2] . In addition, we randomly generate outliers and add them to graphs. In particular, we select 50% of graphs and add 30\% outliers. These outlier nodes are randomly connected or connected to the original nodes. For each outlier node, we define its feature as a random value in [2,2+2\text{std}] , where std is the standard deviation of all features of nodes in the graph. Similar to the setting of graph classification, for each graph G , we suppose N_{G} is the number of nodes that are not outliers. We assume N_{G} is known in this experiment. We refer to figure 2 for the visualization of these graphs. Baseline: FGW K-means. We consider the FGW K-means method introduced in Section 4.3 of [ 24 ] as the baseline method. Specifically, given graphs \{G_{1},\ldots,G_{K}\} and the number of clusters K^{\prime}\leq K , the method iteratively alternates between the following two steps: – Step 1. For each i\in[1:K] and j\in[1:K^{\prime}] , compute the distance between each graph G_{i} and centroid G_{j}^{\prime} . Assign each graph G_{i} to the closest centroid based on the computed distances. – Step 2. Using the updated assignments, recompute each centroid G_{j}^{\prime} , where j^{\prime}\in[1:K^{\prime}] , as the center of the graphs assigned to it. In the FGW K-means method, the Fused-GW distance is used to define the distance in Step 1, while the Fused-GW barycenter is used to compute the “center” in Step 2. Our method: FPGW K-means. Inspired by the FGW K-means method, we introduce the FPGW K-means method. In summary, we adapt the FMPGW discrepancy to measure the distance in Step 1, and introduce the FPGW barycenter to define the “center” in Step 2. First, we convert the graphs to mm-spaces using the formulation introduced in Section L . Specifically, given a graph G=(V=\{v_{1},\ldots,v_{N}\},E) , we define \mathbb{X}=\left(V,C,\sum_{i=1}^{N}\frac{1}{N_{G}}\delta_{v_{i}}\right), where C=[c(v_{i},v_{i^{\prime}})]_{i,i^{\prime}\in[1:N]}\in\mathbb{R}^{N\times N} , and c(v_{i},v_{i^{\prime}}) is the “shortest path distance” determined by E . Here, N_{G} is the number of nodes that are not outliers, and its value is known based on the experiment setup. The feature distance between nodes v_{i} and v_{j} is defined as the Euclidean distance. We then use the Fused-PGW discrepancy ( 10 ) to measure the distance between each pair of graphs and centroids in Step 1 of the K-means method. For Step 2, suppose the set of graphs \bm{G}^{k}\subset\{G_{1},\ldots,G_{K}\} is assigned to cluster k^{\prime} for each k^{\prime}\in[1:K^{\prime}] . We define the “center” using the following Fused-PGW barycenter : \displaystyle\min_{G}\sum_{G_{k}\in\bm{G}^{k}}\frac{1}{|\bm{G}^{k}|}\text{FMPGW}_{\rho_{k}}(G,G_{k}), (18) where \rho_{k}=1 for all k . The solution to this problem provides the updated centroid for cluster k^{\prime} . Details of the formal formulation and solver are provided in Appendix J . We iteratively repeat the above two steps until all centroids/assignments converge. Other parameter setting. In this experiment, we set \omega_{2}=0.999 for both the FGW and FPGW methods. In addition, we set the number of clustering K^{\prime}=3 for both methods. For each centroid, we initialize it as a random connected graph with 40 nodes. Performance analysis. We present the clustering results of FGW K-means and FPGW K-means in Figure 2 . The performance of the FGW method is significantly impacted due to the presence of outlier nodes in half of the graphs. In sharp contrast, FPGW demonstrates a more robust performance, with clustering results closely aligning with the ground truth. This robustness is attributed to the partial matching property of FPGW. From the centroids visualization for FGW/FPGW methods, it is evident that FPGW effectively excludes most of the information from outliers, whereas FGW incorporates it into the centroids. Regarding the wall-clock time, FGW requires 41.9 seconds, while FPGW requires 82.7 seconds. 4.2 Graph Matching Dataset setup . We apply our method on seven widely used graph datasets with continuous node attributes: Synthetic [ 35 ] , Enzymes, Protein, AIDS [ 36 ] , Cuneiform [ 37 ] , COX2, and BZR [ 38 ] . Each dataset consists of hundreds or thousands of connected graphs. For each graph, we use its adjacency matrix as structural information and its attributes as node features. To create a partial matching task, we utilize the BFS (Breadth-first search ) method to randomly extract subgraphs containing 50% of the original nodes and their corresponding edges. We also benchmark performance on the Douban dataset [ 39 ] , which provides a large online graph (3,906 nodes) and a smaller offline subgraph (1,118 nodes), using user locations as node features. Baselines. We compare sink-FPGW against competitive methods including balanced GW methods, SpecGW [ 40 ] , eBPG [ 41 ] , BPG [ 42 ] , BAPG [ 43 ] , srGW [ 44 ] , and unbalanced GW methods: UGW [ 20 ] , PGW [ 21 , 28 ] , RGW [ 23 ] , FUGW [ 26 ] . Settings of GW methods and our method. In all these method, we first convert grpahs into mm-spaces (see appendix L ). In all these methods, we default the probability mass function of the query graph and original graph as \mu=\sum_{i=1}^{m}p_{i}\delta_{v_{i}},\nu_{i=1}^{n}q_{j}\delta_{v_{i}} , with p_{i}=1/m,q_{j}=1/n , where m and n denote the numbers of the source and target nodes. For the computation of the cost matrix C in ( 11 ), we use the Euclidean distance among the continuous node attributes. Evaluation metric and performance analysis. Accuracy is defined as the fraction of ground-truth elements correctly recovered in the predicted set, \mathrm{Acc}=\frac{\lvert S_{\mathrm{gt}}\cap S_{\mathrm{pred}}\rvert}{\lvert S_{\mathrm{gt}}\rvert}\times 100\% , following [ 23 ] . As shown in Table 2, our proposed sink-FPGW achieves superior accuracy on most datasets while remaining highly efficient. The key advantage comes from its ability to leverage both node features (linear part) and structure information (quadratic part), unlike methods limited to structural cues. This design not only boosts accuracy but also yields significant computational efficiency, making sink-FPGW consistently faster than existing alternatives. Table 1 : Comparison of methods on multiple datasets. Acc = accuracy, Time = runtime. For the first seven datasets (excluding Douban), Time corresponds to the total graph set matching time, while for Douban it reflects the runtime of a single matching instance. Synthetic Enzymes Cuneiform COX2 Method Acc Time Acc Time Acc Time Acc Time SpecGW 0.00^{\pm 0.00} 5.25 9.98 ±0.11 3.13 7.15 ±0.12 1.06 5.27 ±0.06 2.82 eBPG 2.00^{\pm 0.00} 121.84 12.68 ±0.12 9950.78 5.99 ±0.09 4310.76 8.99 ±0.06 5760.38 BPG 4.00^{\pm 0.00} 21.12 28.18 ±0.20 90.71 5.81 ±0.07 12.13 23.32 ±0.13 48.88 BAPG 88.03^{\pm 0.05} 45.85 62.07 ±0.24 14.34 72.05 ±0.17 2.02 21.23 ±0.10 15.68 srGW 0.00^{\pm 0.00} 60.27 15.22 ±0.24 64.24 19.94 ±0.09 7.24 1.67 ±0.02 33.12 PGW 0.00^{\pm 0.00} 6.19 9.74 ±0.13 17.26 9.94 ±0.09 14.73 9.41 ±0.11 11.69 UGW 2.00^{\pm 0.00} 12.84 17.83 ±0.26 732.21 04.17 ±0.08 375.36 3.93 ±0.05 65.03 RGW 37.24^{\pm 0.23} 424.68 77.20 ±0.28 137.70 85.33 ±0.21 25.87 37.05 ±0.15 188.99 FGW 46.68^{\pm 0.06} 5.05 62.92 ±0.24 9.26 86.78 ±0.08 1.20 73.28 ±0.22 5.32 FUGW 99.89 ±0.01 70.76 90.91 ±0.19 335.71 96.88 ±0.04 109.74 90.73 ±0.23 166.92 sink-FPGW(ours) 99.70 ±0.01 4.90 93.47 ±0.18 1.81 99.96 ±0.01 0.3245 92.62 ±0.23 1.38 BZR Protein AIDS Douban Method Acc Time Acc Time Acc Time Acc Time SpecGW 9.51 ±0.07 2.08 12.24 ±0.15 9.29 23.89 ±0.19 7.36 0.00 65.11 eBPG 14.21 ±0.10 5540.20 14.88 ±0.16 15936.79 25.98 ±0.20 26182.34 0.09 13.24 BPG 25.67 ±0.18 48.78 30.07 ±0.19 134.55 30.49 ±0.22 106.86 58.59 391.00 BAPG 34.54 ±0.15 11.11 25.52 ±0.22 66.90 50.08 ±0.25 15.42 53.94 2194.70 srGW 3.20 ±0.04 26.55 18.96 ±0.26 149.17 23.76 ±0.24 150.31 4.38 1584.68 PGW 6.80 ±0.08 9.59 13.22 ±0.18 97.74 22.48 ±0.21 22.89 2.06 1363.59 UGW 6.76 ±0.07 152.98 15.57 ±0.22 1280.80 21.32 ±0.20 1152.91 0.09 702.53 RGW 39.54 ±0.19 120.97 38.26 ±0.30 511.67 57.05 ±0.34 340.94 51.88 17784.09 FGW 74.10 ±0.27 8.09 63.95 ±0.24 29.29 84.31 ±0.21 6.76 24.60 367.15 FUGW 89.21 ±0.23 133.96 74.87 ±0.23 733.48 97.12 ±0.10 617.36 66.37 226.22 sink-FPGW(ours) 93.51 ±0.24 0.97 96.21 ±0.15 7.17 98.89 ±0.09 2.33 66.99 540.33 4.3 Geometry Matching Dataset setup . We evaluate our method on a partial geometry matching task using the ’Victoria’ model from the TOSCA [ 45 ] 3D mesh dataset. This high-resolution mesh consists of 10,000 nodes, which are segmented into two parts: an upper body (4,691 nodes) and a lower body (5,436 nodes). Our methods. For mesh objects, we encode them to mm-spaces by the approach described in section L and then apply ( 2 ) (sink-FPGW) to solve the optimization problem ( 11 ) for the geometry matching task. In particular, we define the source and target mass distribution functions as p_{i}=q_{j}=\frac{1}{\max(n,m)} for all the methods, where m,n denotes the number of nodes of the source and target graphs. For both complete and partial geometries, we construct node features using the Euclidean distances from each node to a single randomly selected anchor node, while the mesh structure is encoded via the adjacency matrix. Baselines. We benchmark our proposed sink-FPGW method against two competitive baselines, RGW and FUGW. To ensure a fair comparison, RGW is initialized with a transport plan derived from node features, and the regularization hyperparameters for both FUGW and sink-FPGW are optimized via line search. Evaluation metric and performance analysis. Following the RGW evaluation protocol, sink-FPGW achieves matching accuracies of 99.47\% and 99.77\% on the two partial matching tasks ( 43.47\% and 48.05\% in RGW, and 98.99\% and 56.09\% in FUGW), where \mathrm{Acc}=\frac{\lvert S_{\mathrm{gt}}\cap S_{\mathrm{pred}}\rvert}{\lvert S_{\mathrm{gt}}\rvert}\times 100\% . We visualize the one-hot transport plans as real shapes (Figure 3 (b)-(d)) and heatmaps (Figure 3 (e)-(h)), confirming that sink-FPGW yields the most accurate matches. The one-hot plans are obtained by taking the argmax match for each source node from the transport plans. Figure 3 : Qualitative results for the partial geometry matching experiment. (a): Schematic illustrating the two whole-to-partial matching tasks; (b)-(d): Visualizations of the partial mesh reconstructed from the whole source mesh using the transport plans computed by RGW, FUGW, and sink-FPGW.; (e)-(h) Corresponding heatmap visualizations for the ground truth, RGW, FUGW, and sink-FPGW, the top row corresponding to the first partial matching task (upper body) and the bottom row to the second (lower body). The x- and y-axes represent the vertex indices of the whole and partial meshes, respectively. 5 Summary. In this paper, we proposed a novel formulation called “fused-partial Gromov-Wasserstein” (fused-PGW) for comparing structured objects. Theoretically, we demonstrated the metric properties of fused-PGW, and numerically, we introduced the corresponding Frank-Wolfe solver, Sinkhorn Solver and barycenter algorithms. Finally, we applied fused-PGW to graph matching and clustering experiments, showing that it achieves more robust performance due to its partial matching property. Appendix A Notation and Abbreviations. Abbreviations – OT: Optimal Transport problem; see ( 19 ). – POT: Partial Optimal Transport problem; see ( 21 ). – GW: Gromov–Wasserstein problem; see ( 1 ). – PGW: Partial Gromov–Wasserstein problem; see ( 3 ). – MPGW: Mass-Constrained Partial Gromov–Wasserstein; see ( 4 ). – FW: Frank–Wolfe algorithm [ 46 ] . – EFUGW(\mathbb{X},\mathbb{Y}) : entropic fused unbalanced GW objective (cf. ( 86 )). – EFPGW(\mathbb{X},\mathbb{Y}) : entropic fused partial GW objective (cf. ( 88 )). – LB - FPGW_{\lambda}(\mathbb{X},\mathbb{Y}) : relaxed lower-bound formulation (cf. ( 89 )). – EFMPGW(\mathbb{X},\mathbb{Y}) : entropic fused mass-constrained PGW (cf. ( 92 )); LB - EFMPGW its relaxation. – c(x,y) : feature cost; d_{X},d_{Y} : intra-space distances; |d_{X}-d_{Y}|^{2} : structural discrepancy. Sets, Spaces, and Indices – \mathbb{R}^{d} : Euclidean space; \mathbb{R}_{+} : nonnegative reals. – X,Y\subset\mathbb{R}^{d} : non-empty, convex, compact sets (default setting). – X^{2}=X^{\otimes 2}=X\times X . – [1\!:\!n]=\{1,\dots,n\} . – r,p,q\in[1,\infty) : real exponents used in costs/metrics. Vector, Norms and Basic Operators – \|\cdot\| : Euclidean norm; \|\cdot\|_{\rm TV} : total variation norm. – \langle A,B\rangle=\mathrm{tr}(A^{\top}B) : Frobenius inner product. – 1_{n} , 1_{n\times m} , 1_{n\times m\times n\times m} : all-ones vector, matrix, and tensor. – \mathbbm{1}_{E} : indicator of a measurable set E , \mathbbm{1}_{E}(z)=1 if z\in E , else 0 . – \nabla : gradient. Measures and Pushforwards – \mathcal{M}_{+}(X) : finite nonnegative Radon measures on X ; – \mathcal{P}_{2}(X) : probability measures on X with finite second moment. – |\mu|=\mu(X) : total mass (TV-norm) of \mu . – \mu\leq\sigma : measure domination, i.e., \mu(B)\leq\sigma(B) for all Borel B\subseteq X . – \mu^{\otimes 2}=\mu\otimes\mu : product measure. – \mu(\phi):=\langle\phi,\mu\rangle:=\int\phi(x)\,d\mu(x) . – T_{\#}\sigma : pushforward of \sigma by measurable T\!:\!X\!\to\!Y , i.e., T_{\#}\sigma(A)=\sigma(T^{-1}(A)) . Metric-Measure (mm) Spaces and Distance Matrices – \mathbb{X}=(X,d_{X},\mu) , \mathbb{Y}=(Y,d_{Y},\nu) : mm-spaces. – For discrete \mathbb{X} with X=\{x_{i}\}_{i=1}^{n} , define C^{X}\in\mathbb{R}^{n\times n} by C^{X}_{i,i^{\prime}}=d_{X}^{q}(x_{i},x_{i^{\prime}}) ; similarly C^{Y} . – \mathbb{X}\sim\mathbb{Y} : mm-space equivalence if they have equal total mass and GW_{q}^{p}(\mathbb{X},\mathbb{Y})=0 . Couplings and Partial Couplings – \Gamma(\mu,\nu):=\{\gamma\in\mathcal{P}_{2}(X\times Y):\ \gamma_{1}=\mu,\ \gamma_{2}=\nu\} . – Discrete weights: \mathrm{p}=[p_{1}^{X},\dots,p_{n}^{X}]^{\top} , \mathrm{q}=[q_{1}^{Y},\dots,q_{m}^{Y}]^{\top} , |\mathrm{p}|=\sum_{i}p_{i} , \mathrm{p}\leq\mathrm{p}^{\prime} if p_{j}\leq p^{\prime}_{j}\ \forall j . – \Gamma(\mathrm{p},\mathrm{q})=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\ \gamma\,1_{m}=\mathrm{p},\ \gamma^{\top}1_{n}=\mathrm{q}\} . – \Gamma_{\leq}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(X\times Y):\ \gamma_{1}\leq\mu,\ \gamma_{2}\leq\nu\} . – \Gamma_{\leq}(\mathrm{p},\mathrm{q}):=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\ \gamma\,1_{m}\leq\mathrm{p},\ \gamma^{\top}1_{n}\leq\mathrm{q}\} . – \gamma,\gamma_{1},\gamma_{2} : joint and marginal measures; in discrete form \gamma\in\mathbb{R}_{+}^{n\times m} , \gamma_{1}=\gamma 1_{m} , \gamma_{2}=\gamma^{\top}1_{n} . – \pi_{1}:X\times Y\to X , \pi_{2}:X\times Y\to Y . – \pi_{1,2}:S\times X\times Y\to X\times Y , (s,x,y)\mapsto(x,y) ; similarly \pi_{0,1},\pi_{0,2} for other coordinate pairs. Optimal Transport Problems – c:X\times Y\to\mathbb{R}_{+} : lower semicontinuous cost for (partial) OT. – OT(\mu,\nu) : classical OT; W_{p}(\mu,\nu) : p -Wasserstein distance; POT_{\lambda}(\mu,\nu) : partial OT with parameter \lambda>0 ; see ( 19 ), ( 20 ), ( 21 ). – L:\mathbb{R}\times\mathbb{R}\to\mathbb{R} , D:\mathbb{R}\times\mathbb{R}\to\mathbb{R} : GW loss and scalar distance. – GW^{L}(\cdot,\cdot) : GW objective with loss L ; d_{GW,r}^{q} : GW with L(a,b)=|a-b|^{q} ; see ( 1 ). – PGW_{r,L,\lambda}(\cdot,\cdot) : partial GW objective; see ( 3 ). – C(\gamma;\lambda,\mu,\nu):=\gamma^{\otimes 2}\!\big(L(d_{X}^{q},d_{Y}^{q})\big)+\lambda\big(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}\big) : PGW transport cost for \gamma\in\Gamma_{\leq}(\mu,\nu) . – UGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) : unbalanced GW; FUGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) : fused unbalanced GW. – d_{FGW,r,q}(\mathbb{X},\mathbb{Y}) : fused GW distance; d_{FPGW,r,q,\lambda}^{p}(\mathbb{X},\mathbb{Y}) : fused partial GW distance. Discrete Tensorized Forms – Discrete measure setting: \mu=\sum_{i=1}^{n}\mathrm{p}_{i}\delta_{x_{i}},\nu=\sum_{j=1}^{m}\mathrm{q}_{j}\delta_{y_{j}} . – M\in\mathbb{R}^{n\times m\times n\times m} with M_{i,j,i^{\prime},j^{\prime}}=L(C^{X}_{i,i^{\prime}},C^{Y}_{j,j^{\prime}}) ; M^{\top} swaps index pairs: M^{\top}_{i,j,i^{\prime},j^{\prime}}=M_{i^{\prime},j^{\prime},i,j} . In default, L is L2 norm square, and we denote M=\|C_{X}-C_{Y}\|^{2} – (M-2\lambda)_{i,j,i^{\prime},j^{\prime}}:=M_{i,j,i^{\prime},j^{\prime}}-2\lambda . – M\circ\gamma\in\mathbb{R}^{n\times m} with [M\circ\gamma]_{i,j}=\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}\,\gamma_{i^{\prime},j^{\prime}} . – \langle\cdot,\cdot\rangle_{F} : Frobenius inner product on \mathbb{R}^{n\times m} . Frank-Wolfe Optimization and Algorithmic Symbols – \mathcal{L} : objective functional for PGW_{\lambda}(\cdot,\cdot) . – \alpha\in[0,1] : line-search step size. – \gamma^{(1)} : initialization; \gamma^{(k)} , \gamma^{(k)^{\prime}} : transport plans before/after Step 1 in the k -th FW iteration. – G_{C,M}=\omega_{1}C+\omega_{2}\tilde{M}+M^{\top}\!\circ\!\gamma , G=2\hat{M}\!\circ\!\hat{\gamma} : gradients in two FW variants. – a,b,c\in\mathbb{R} : coefficients defined in ( 64 ) (For FPGW, replace M by M-2\lambda ). – MPGW_{r,L,\rho} and \Gamma^{\rho}_{\leq}(\mu,\nu) : mass-constrained partial GW and its feasible set; see ( 4 ), ( 6 ). Entropic / Sinkhorn Notation – \epsilon>0 : entropic regularization parameter. – D_{\phi}(\cdot\|\cdot) : \phi -divergence; special cases below. – D_{KL}(\mu\|\nu)=\bar{D}_{KL}(\mu\|\nu)+|\nu|-|\mu| with \bar{D}_{KL}(\mu\|\nu)=\int\log\!\left(\frac{d\mu}{d\nu}\right)\,d\mu when \mu\ll\nu , +\infty otherwise. – D_{PTV}(\mu\|\nu)=\begin{cases}\|\mu-\nu\|_{\rm TV}=|\nu-\mu|&\text{if }\mu\leq\nu,\\ +\infty&\text{otherwise.}\end{cases} – \Gamma_{\leq}(\mu,\nu) , \Gamma_{\leq}^{\rho}(\mu,\nu) : partial feasible sets (mass-unconstrained and mass-constrained with |\gamma|=\rho ). – |\gamma|=\gamma(X\times Y) , |\mu|=\mu(X) , |\nu|=\nu(Y) : total mass. – \mathcal{L}(\gamma) : fused GW functional (feature + structure + penalties) used in EFUGW/EFPGW. – c_{\pi}(x,y)=\tfrac{1}{2}\omega_{1}d(x,y)+\omega_{2}\,[L(d_{X}^{r},d_{Y}^{r})\!\circ\!\pi](x,y)+\epsilon\,\bar{D}_{KL}(\pi\|\mu\!\otimes\!\nu) : \pi -conditioned cost (cf. Prop. I.1 ). – [L(d_{X},d_{Y})\!\circ\!\pi](x,y)=\int_{X\times Y}L(d_{X}^{r}(x,x^{\prime}),d_{Y}^{r}(y,y^{\prime}))\,d\pi(x^{\prime},y^{\prime}) . – K=\exp(-c/\epsilon) : Gibbs kernel for feature cost; elementwise exponential. – u\in\mathbb{R}^{n}_{+} , v\in\mathbb{R}^{m}_{+} : Sinkhorn scaling vectors. – \odot , \oslash : elementwise (Hadamard) product and division. – \mathrm{diag}(a) : diagonal matrix with vector a on the diagonal. – \text{Proj}^{KL}_{\mathcal{C}_{i}} : Bregman (KL) projection onto constraint set \mathcal{C}_{i} (cf. Alg. 6 ). – \mathcal{C}_{1}=\{\gamma\geq 0:\ \gamma_{2}\leq q\} , \mathcal{C}_{2}=\{\gamma\geq 0:\ \gamma_{1}\leq p\} , \mathcal{C}_{3}=\{\gamma\geq 0:\ |\gamma|=\rho\} : partial-marginal and mass constraints. – \gamma^{\otimes 2} , (\mu\otimes\nu)^{\otimes 2} : product measures on (X\times Y)^{2} . – \pi,\gamma\in\mathcal{M}_{+}(X\times Y) : current and updated couplings in alternating minimization; \rho\in[0,\min(|p|,|q|)] target mass. – Stopping criteria: norms/duality gap on (u,v) or fixed-point tolerance on \gamma . Graph-Specific Notation – G=(V,E) : graph with nodes V=\{v_{1},\dots,v_{N}\} and edges E\subset V^{2} . – d_{V}:V^{2}\to\mathbb{R} : structural distance (default: shortest-path distance). – f:V\to\mathcal{F} : node feature map; \mathcal{F} is the feature space. – wl:\mathcal{F}\to S^{H} : Weisfeiler–Lehman feature map [ 47 ] for discrete \mathcal{F} ; S finite alphabet, H\in\mathbb{N} . – d_{\mathcal{F}} : feature-space metric. Default: Euclidean if \mathcal{F}=\mathbb{R}^{d} ; if \mathcal{F} is discrete, Hamming on wl(\mathcal{F}) : d_{\mathcal{F}}\!\big(f(v_{1}),f(v_{2})\big):=\sum_{h=1}^{H}\delta\!\big(wl(f(v_{1}))_{h}\neq wl(f(v_{2}))_{h}\big). Appendix B Background of optimal transport problems The Optimal Transport (OT) problems for \mu,\nu\in\mathcal{P}(\Omega) , with transportation cost c(x,y):\Omega\times\Omega\to\mathbb{R}_{+} being a lower-semi continuous function, is defined as: \displaystyle OT(\mu,\nu):=\min_{\gamma\in\Gamma(\mu,\nu)}\gamma(c), (19) \displaystyle\text{ where }\quad\gamma(c):=\int_{\Omega^{2}}c(x,y)\,d\gamma(x,y) and where \Gamma(\mu,\nu) denotes the set of all joint probability measures on \Omega^{2}:=\Omega\times\Omega with marginals \mu,\nu , i.e., \gamma_{1}:=\pi_{1\#}\gamma=\mu,\gamma_{2}:=\pi_{2\#}\gamma=\nu , where \pi_{1},\pi_{2}:\Omega^{2}\to\Omega are the canonical projections \pi_{1}(x,y):=x,\pi_{2}(x,y):=y . A minimizer for ( 19 ) always exists [ 7 , 48 ] and when c(x,y)=\|x-y\|^{p} , for p\geq 1 , it defines a metric on \mathcal{P}(\Omega) , which is referred to as the “ p -Wasserstein distance”: \displaystyle W_{p}^{p}(\mu,\nu):=\min_{\gamma\in\Gamma(\mu,\nu)}\int_{\Omega^{2}}\|x-y\|^{p}d\gamma(x,y). (20) The Partial Optimal Transport (POT) problem [ 8 , 49 , 50 ] extends the OT problem to the set of Radon measures \mathcal{M}_{+}(\Omega) , i.e., non-negative and finite measures. For \lambda>0 and \mu,\nu\in\mathcal{M}_{+}(\Omega) , the POT problem is defined as: POT(\mu,\nu;\lambda):=\inf_{\gamma\in\mathcal{M}_{+}(\Omega^{2})}\gamma(c)+\lambda(|\mu-\gamma_{1}|+|\nu-\gamma_{2}|), (21) where, in general, |\sigma| denotes the total variation norm of a measure \sigma , i.e., |\sigma|:=\sigma(\Omega) . The constraint \gamma\in\mathcal{M}_{+}(\Omega^{2}) in ( 21 ) can be further restricted to \gamma\in\Gamma_{\leq}(\mu,\nu) : \Gamma_{\leq}(\mu,\nu):=\{\gamma\in\mathcal{M}_{+}(\Omega^{2}):\,\gamma_{1}\leq\mu,\gamma_{2}\leq\nu\}, denoting \gamma_{1}\leq\mu if for any Borel set B\subseteq\Omega , \gamma_{1}(B)\leq\mu(B) (respectively, for \gamma_{2}\leq\nu ) [ 9 ] . Roughly speaking, the linear penalization indicates that if the classical transportation cost exceeds 2\lambda , it is better to create/destroy’ mass (see [ 16 ] for further details). In addition, the above formulation has an equivalent form, to distinguish them, we call it “mass-constraint partial optimal transport problem” (MPOT): \displaystyle MOPT(\mu,\nu;\rho):=\inf_{\gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\gamma(c). (22) Appendix C (fused)-Unbalanced Gromov Wasserstein and (fused) Partial Gromov Wasserstein. The unbalanced Gromov Wasserstein problem is firstly proposed by [ 20 , 21 , 28 ] . Given two mm- spaces, \mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) , the UGW problem is defined by \displaystyle UGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\mathcal{M}_{+}(X\times Y)}\langle L(d_{X}^{r},d_{Y}^{r}),\gamma^{\otimes 2}\rangle+\lambda(D_{\phi_{1}}(\gamma_{1}^{\otimes 2}\parallel\mu^{\otimes 2})+D_{\phi_{2}}(\gamma_{2}^{\otimes 2}\parallel\nu^{\otimes 2})), (23) where D_{\phi_{1}},D_{\phi_{2}} are f-divergence and can be distinct in the general setting. Similar to this work, the fused-Unbalanced Gromov Wasserstein, proposed by [ 26 ] is defined as: FUGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\mathcal{M}_{+}(X\times Y)}\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle L(d_{X}^{r},d_{Y}^{r}),\gamma^{\otimes 2}\rangle+\lambda(D_{\phi_{1}}(\gamma_{1}^{\otimes 2}\parallel\mu^{\otimes 2})+D_{\phi_{2}}(\gamma_{2}^{\otimes 2}\parallel\nu^{\otimes 2})). And when the f -divergence terms D_{\phi_{1}},D_{\phi_{2}} are KL divergences, the authors in [ 26 ] propose a Sinkhorn computational solver. At the end of this section, we introduce the following relation between FUGW and FPGW, which is equivalent to the statement (1) in Theorem 3.1 . Proposition C.1 . When D_{\phi_{1}},D_{\phi_{2}} are total variation, then we have: \displaystyle FUGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) \displaystyle=FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) \displaystyle=\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle L(d_{X}^{r},d_{Y}^{r}),\gamma^{\otimes 2}\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}). Equivalently speaking, one can restrict the searching space from \mathcal{M}_{+}(X\times Y) to \Gamma_{\leq}(\mu,\nu) . Proof. Choose \gamma\in\mathcal{M}_{+}(X\times Y) and let \gamma_{Y|X}(\cdot|x) denote the conditional measure of \gamma given x\in X . Let \gamma^{\prime}=\gamma_{Y|X}(\cdot|X)\cdot(\gamma_{1}\wedge\mu) , by proposition L.2, we have \gamma^{\prime}\leq\gamma,\gamma^{\prime}_{1}\leq\mu , and \omega_{2}\langle\|d_{X}-d_{Y}\|^{p},\gamma{{}^{\prime}}^{\otimes 2}\rangle+\lambda(\|\mu-\gamma_{1}^{\prime}\|_{TV}+\|\nu-\gamma_{2}^{\prime}\|_{TV})\leq\omega_{2}\langle\|d_{X}-d_{Y}\|^{p},\gamma^{\otimes 2}\rangle+\lambda(\|\mu-\gamma_{1}\|_{TV}+\|\nu-\gamma_{2}\|_{TV}). Since C\geq 0,\gamma^{\prime}\leq\gamma , we have \langle C,\gamma^{\prime}\rangle\leq\langle C,\gamma\rangle . Therefore, we have \displaystyle\omega_{1}\langle C,\gamma^{\prime}\rangle+\omega_{2}\langle\|d_{X}-d_{Y}\|^{p},\gamma{{}^{\prime}}^{\otimes 2}\rangle+\lambda(\|\mu-\gamma_{1}^{\prime}\|_{TV}+\|\nu-\gamma_{2}^{\prime}\|_{TV}) \displaystyle\leq\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle\|d_{X}-d_{Y}\|^{p},\gamma^{\otimes 2}\rangle+\lambda(\|\mu-\gamma_{1}\|_{TV}+\|\nu-\gamma_{2}\|_{TV}). That is, based on \gamma , we can construct \gamma^{\prime} such that \gamma^{\prime}_{1}\leq\mu\wedge\gamma_{1},\gamma^{\prime}\leq\gamma and the \gamma^{\prime} admits smaller cost. Based on the same process, based on \gamma^{\prime} , we can construct \gamma^{\prime\prime} such that \gamma^{\prime\prime}\leq\gamma^{\prime} , \gamma^{\prime\prime}\leq\nu . That is \gamma^{\prime\prime}\in\Gamma_{\leq}(\mu,\nu) and admits smaller cost than \gamma^{\prime} . Therefore, we can restrict the searching space for ( 8 ) in this case from \mathcal{M}_{+}(X\times Y) to \Gamma_{\leq}(X\times Y) . ∎ Figure 4 : In this toy example, we illustrate the relationships and differences between OT, Unbalanced OT, Partial OT, GW, Unbalanced GW, Partial GW, fused GW, fused unbalanced GW, and Fused Partial GW. The source shape consists of the union of the pink and red points, and the target shape is the grey shape. The objective is to establish a reasonable matching between the two shapes. Remark C.2 . In Figure 4 , we illustrate the transportation plans of various methods, including optimal transport (OT), unbalanced optimal transport (UOT), partial optimal transport (POT), \ldots and fused-Partial Gromov-Wasserstein (FPGW). Due to the balanced mass setting, OT, GW, and fused GW match all points from the source shape to the target shape. In contrast, the Sinkhorn entropic regularization in UOT, UGW, and FUGW allows for mass splitting, resulting in a small amount of mass between the grey shape and the pink points. PGW and fused PGW achieve the desired one-to-one matching, where the straight-line segment in the source shape (red points) corresponds to the straight-line segment in the target shape (grey points). However, since PGW does not account for the spatial location of points, there is a 50% chance of obtaining “anti-identity” matching as demonstrated in Figure 4 . C.1 Existence of minimizes of Fused PGW. In this section, we discuss the basic properties of the fused PGW. Proposition C.3 . Given mm-spaces \mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) , where X,Y are compact sets, the fused-PGW problems ( 11 ) and ( 10 ) admit minimizers. That is, we can replace \inf by \min in the formulations. Note, this proposition is equivalent to the statement (2) in Theorem 3.1 . We first introduce the following statements: Proposition C.4 . The set \Gamma_{\leq}(\mu,\nu) and \Gamma_{\leq}^{\rho}(\mu,\nu) are weakly compact, convex sets, where \rho\in[0,\min(|\mu|,|\nu|)] . Proof. By [ 51 ] Lemma B.1, we have \Gamma_{\leq}(\mu,\nu) is a weakly compact set. By e.g. [ 52 , 16 ] , we have \Gamma_{\leq}(\mu,\nu) is convex. It remains to show the compactness and convexity of set \Gamma^{\rho}_{\leq}(\mu,\nu) . Pick \gamma^{1},\gamma^{2}\in\Gamma^{\rho}_{\leq}(\mu,\nu) and \omega\in[0,1] and let \gamma=(1-\omega)\gamma^{1}+\omega\gamma^{2} . We have \gamma\in\Gamma_{\leq}(\mu,\nu) by the convexity of \Gamma_{\leq}(\mu,\nu) . In addition, |(1-\omega)\gamma^{1}+\omega\gamma^{2}|=(1-\omega)|\gamma^{1}|+\omega|\gamma^{2}|\geq(1-\omega)\rho+\omega\rho=\rho, thus we have: \gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu) . Pick sequence (\gamma^{n})_{n=1}^{\infty}\subset\Gamma^{\rho}_{\leq}(\mu,\nu)\subset\Gamma_{\leq}(\mu,\nu) . By the compactness of \Gamma_{\leq}(\mu,\nu) , there exists a subsequence (\gamma^{n_{k}})_{k=1}^{\infty} that converges to some \gamma^{*}\in\Gamma_{\leq}(\mu,\nu) weakly. It remains to show \gamma^{*}\in\Gamma_{\leq}^{\rho}(\mu,\nu) . Indeed, |\gamma^{*}|=\langle 1_{X\times Y}\times\gamma\rangle=\lim_{k\to\infty}\langle 1_{X\times Y},\gamma^{n_{k}}\rangle=\lim_{k\to\infty}|\gamma^{n_{k}}|. Since for each k\geq 1 , we have |\gamma^{n_{k}}|\geq\rho , thus |\gamma^{*}|\geq\rho . That is \gamma^{*}\in\Gamma_{\leq}^{\rho}(\mu,\nu) , and we complete the proof. ∎ Lemma C.5 . Suppose X,Y are compact sets. Let Z=(X\times Y) and d_{Z}((x^{1},y^{1}),(x^{2},y^{2}))=d_{X}(x^{1},x^{2})+d_{Y}(y^{1},y^{2}) . Suppose \phi:Z^{2}\to\mathbb{R} is Lipschitz continuous and C:Z\to\mathbb{R} is bounded, then the following problem admits a minimizer: \displaystyle\inf_{\gamma\in\mathcal{M}}\langle\phi,\gamma^{\otimes 2}\rangle+\langle C,\gamma\rangle (24) where \mathcal{M} is a non-empty weakly compact set. Proof. Pick weakly convergent (\gamma^{n})_{n=1}^{\infty}\subset\mathcal{M} , we have \gamma^{n}\overset{w}{\rightharpoonup}\gamma^{*}\in\mathcal{M} . From lemma C.3 in [ 28 ] , we have \langle\phi,(\gamma^{n})^{\otimes 2}\rangle\to\langle\phi,\gamma^{*}\rangle. By definition of weak convergence and the fact that the sets X,Y are compact, we have \displaystyle\langle C,\gamma^{n}\rangle\to\langle C,\gamma\rangle. (25) Thus, we have \langle\phi,(\gamma^{n})^{\otimes 2}\rangle+\langle C,\gamma^{n}\rangle\to\langle\phi,\gamma^{\otimes 2}\rangle+\langle C,\gamma\rangle. Choose a sequence \gamma^{n}\in\mathcal{M} such that \langle\phi,(\gamma^{n})^{\otimes 2}\rangle+\langle C,\gamma^{n}\rangle achieves the infimum of the problem ( 24 ). By compactness of \mathcal{M} , there exists a convergent subsequence \gamma^{(n_{k})}\overset{w}{\rightharpoonup}\gamma^{*}\in\mathcal{M} . By ( 25 ), we have \gamma^{*} is a minimizer of ( 24 ). Thus, we complete the proof. ∎ Proof of Proposition C.3 . From Lemma C.1. in [ 28 ] , we have (X\times Y)^{2}\ni((x^{1},y^{1}),(x^{2},y^{2}))\to|d_{X}^{r}(x^{1},x^{2})-d_{Y}^{r}(y^{1},y^{2})|^{q} is Lipschitz continuous. In addition, C:X\times Y is a bounded mapping. From lemma C.4 , we have \Gamma_{\leq}(\mu,\nu),\Gamma_{\leq}^{\rho}(\mu,\nu) are compact. From lemma C.5 , we complete the proof. ∎ Appendix D Metric property of Fused PGW In this section, we discuss the proof of Theorem 3.1 (3). We will discuss the details in the following subsections. The related conclusion can be treated as an extension of Theorem 6.3 in [ 53 ] and Theorem 3.1 in [ 25 ] . D.1 Background: Isometry, fused-GW semi-metric. Given \mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) , we say X,Y are equivalent, noted X\sim Y if and only if: There exists a mapping \phi:X\to Y such that – \phi_{\#}\mu=\nu – d_{X}(x,x^{\prime})=d_{Y}(\phi(x),\phi(x^{\prime})),\forall x,x^{\prime}\in X . Such a function \phi is called measure preserving isometry . In addition, in the formulation of fused-GW ( 11 ), we set d(x,y)=\|x-y\|^{q} and L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{q} . The reduced formulation is called “fused-Gromov Wasserstein distance” [ 25 ] : \displaystyle d_{FGW,r,q}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}d\gamma(x,y)d\gamma(x^{\prime},y^{\prime}). (26) and it defines a metric where the identity is induced by the above equivalence relation. Inspired by this formulation, we introduce the Fused Partial GW metric : \displaystyle d_{FPGW,r,q,\lambda}^{p}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}+\lambda\left(\frac{|\mu|^{2}}{|\gamma|^{2}}+\frac{|\nu|^{2}}{|\gamma|^{2}}-2\right)d\gamma(x,y)d\gamma(x^{\prime},y^{\prime}). (27) Remark D.1 . We adapt the convention \frac{1}{0}\cdot 0=1 , thus the above formulation is well-defined. In particular, when |\gamma|=0 , i.e., \gamma is zero measure, the above integration is defined by \displaystyle\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}+\lambda\left(\frac{|\mu|^{2}}{|\gamma|^{2}}+\frac{|\nu|^{2}}{|\gamma|^{2}}-2\right)d\gamma(x,y)d\gamma(x^{\prime},y^{\prime}) \displaystyle=\lambda(|\mu|^{2}+|\nu|^{2}) (28) \displaystyle=\lim_{|\gamma|\searrow 0}\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}+\lambda\left(\frac{|\mu|^{2}}{|\gamma|^{2}}+\frac{|\nu|^{2}}{|\gamma|^{2}}-2\right)d\gamma(x,y)d\gamma(x^{\prime},y^{\prime}). Remark D.2 . By Proposition C.3 , the above problem admits a minimizer. Next, we introduce the formal statement of Theorem 3.1 (2). Theorem D.3 . Define space for mm-spaces, \mathcal{G}=\{\mathbb{X}=(X,d_{X},\mu),X\subset\mathbb{R}^{d},X\text{ is compact};d_{X}\text{ is a metric};\mu\in\mathcal{M}_{+}(X)\}. Then Fused PGW ( 27 ) defines a semi-metric in quotient space \mathcal{G}/\sim . In particular: 1. d_{FPGW,r,q,\lambda}(\cdot,\cdot) is non-negative and symmetric. 2. Suppose \omega_{2},\lambda>0 , then d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})=0 iff \mathbb{X}\sim\mathbb{Y} . 3. If \omega_{2}>0 , for q\geq 1 , we have \displaystyle d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})\leq 2^{q-1}(d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Z})+d_{FPGW,r,q,\lambda}(\mathbb{Y},\mathbb{Z})). (29) In particular, when q=1 , fused-PGW satisfies the triangle inequality. D.2 Proof of the (1)(2) in Theorem D.3 For statement (1), by definition, for each \gamma\in\Gamma_{\leq}(\mu,\nu) , we have \int_{X\times Y}\|x-y\|^{q}d\gamma,\int_{(X\times Y)^{2}}\|d^{r}_{X}(x,x^{\prime})-d^{r}_{Y}(y,y^{\prime})\|^{q}d\gamma^{\otimes 2}\geq 0. Thus, d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})\geq 0 . In addition, \displaystyle d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y}) \displaystyle=\inf_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{(X\times Y)^{2}}\omega_{1}\|x-y\|^{q}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q})^{p}d\gamma(x,y)d\gamma(x^{\prime},y^{\prime})+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}) \displaystyle=\inf_{\gamma\in\Gamma_{\leq}(\nu,\mu)}\int_{(Y\times X)^{2}}\omega_{1}\|y-x\|^{q}+\omega_{2}|d_{Y}^{r}(y,y^{\prime})-d_{X}^{r}(x,x^{\prime})|^{q})^{p}d\gamma(y,x)d\gamma(y^{\prime},x^{\prime})+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}) \displaystyle=d_{FPGW,r,q,\lambda}(\mathbb{Y},\mathbb{X}). And we prove the symmetric. For statement (2), suppose measure preserving isometry \phi:X\to Y exists, then we have |\mu|=|\nu| . Let \gamma=(\text{id}\times\phi)_{\#}\mu , we have \gamma\in\Gamma(\mu,\nu)\subset\Gamma_{\leq}(\mu,\nu) . Thus |\gamma|=|\mu|=|\nu| . Furthermore, \displaystyle d_{FPGW,r,q,\lambda}^{p}(\mathbb{X},\mathbb{Y}) \displaystyle\leq\int_{(X\times Y)^{2}}\omega_{1}\|x-y\|^{q}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}d\gamma(x,y)d\gamma(x^{\prime},y^{\prime})+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}) \displaystyle=\int_{(X\times Y)^{2}}\omega_{1}\underbrace{\|x-\phi(x)\|^{q}}_{0}+\omega_{2}\underbrace{|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(\phi(x),\phi(x^{\prime}))|^{q}}_{0}d\mu(x)d\mu(x^{\prime})+\lambda(\underbrace{|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}}_{0}) \displaystyle=0. (30) For the other direction, suppose d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})=0 . We have two cases: Case 1: |\mu|=|\nu|=0 . We’ve done. Case 2: |\mu|>0 or |\nu|>0 . By the Proposition C.3 , a minimizer for problem ( 27 ) exists. Choose one minimizer, denoted as \gamma^{*} . First, we claim |\mu|=|\nu|=|\gamma^{*}| . Indeed, assume the above equation is not true. For convenience, we suppose |\mu|<|\nu| . Then |\gamma|\leq|\mu|<|\nu| . We have \displaystyle 0=d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})\geq\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma^{*}|^{2})>\lambda(|\mu|^{2}-|\gamma^{*}|^{2})\geq 0, (31) since \lambda>0 . Thus we have contradiction. Since \gamma^{*}\in\Gamma_{\leq}(\mu,\nu) , we have \gamma^{*}\in\Gamma(\mu,\nu) . Thus, we have \displaystyle 0 \displaystyle\leq d_{FPGW,r,q}(\mathbb{X},\mathbb{Y}) \displaystyle\leq\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}\,d\gamma^{*}(x,y)d\gamma^{*}(x^{\prime},y^{\prime}) \displaystyle=\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}+\lambda\left(\frac{|\mu|^{2}}{|\gamma|^{2}}+\frac{|\nu|^{2}}{|\gamma|^{2}}-2\right)\,d\gamma^{*}(x,y)d\gamma^{*}(x^{\prime},y^{\prime}) \displaystyle=d_{FPGW,r,q}(\mathbb{X},\mathbb{Y}) \displaystyle=0. That is, d_{FPGW,r,q}(\mathbb{X},\mathbb{Y})=0 . Since \omega_{2}>0 , by Proposition 5.2 in [ 25 ] or Theorem 6.4 in [ 53 ] , there exists measure preserving isometry \phi:X\to Y and thus we have \mathbb{X}\sim\mathbb{Y} and we complete the proof. D.3 Proof of statement (3) in Theorem D.3 . Choose mm-spaces \mathbb{S}=(S,d_{S},\sigma),\mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) . In this section, we will prove the triangle inequality d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})\leq d_{FPGW,r,q,\lambda}(\mathbb{S},\mathbb{X})+d_{FPGW,r,q,\lambda}(\mathbb{S},\mathbb{Y}). First, introduce auxiliary points \hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2} and set \displaystyle\begin{cases}\hat{S}&=S\cup\{\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2}\},\\ \hat{X}&=X\cup\{\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2}\},\\ \hat{Y}&=Y\cup\{\hat{\infty}_{0},\hat{\infty}_{1},\hat{\infty}_{2}\}.\end{cases} Define \hat{\sigma},\hat{\mu},\hat{\nu} as follows: \begin{cases}\hat{\sigma}&=\sigma+|\mu|\delta_{\hat{\infty}_{1}}+|\nu|\delta_{\hat{\infty}_{2}},\\ \hat{\mu}&=\mu+|\sigma|\delta_{\hat{\infty}_{0}}+|\nu|\delta_{\hat{\infty}_{2}},\\ \hat{\nu}&=\nu+|\sigma|\delta_{\hat{\infty}_{0}}+|\mu|\delta_{\hat{\infty}_{1}}.\end{cases} (32) Next, we define d_{\hat{S}}:\hat{S}^{2}\to\mathbb{R}\cup\{\infty\} as follows: \displaystyle d_{\hat{S}}(s,s^{\prime})=\begin{cases}d_{S}(s,s^{\prime})&\text{if }(s,s^{\prime})\in S^{2},\\ \infty&\text{elsewhere. }\end{cases} (33) Note, d_{\hat{S}}(\cdot,\cdot) is not a rigorous metric in \hat{S} since we allow d_{\hat{S}}=\infty , d_{\hat{X}},d_{\hat{Y}} are defined similarly. Then, we define the following mapping L_{\lambda}:(\mathbb{R}\cup\{\infty\})\times(\mathbb{R}\cup\{\infty\})\to\mathbb{R}_{+} : \displaystyle L^{q}_{\lambda}(\mathrm{r}_{1},\mathrm{r}_{2})=\begin{cases}|\mathrm{r}_{1}-\mathrm{r}_{2}|^{q}&\text{if }\mathrm{r}_{1},\mathrm{r}_{2}<\infty,\\ \lambda/\omega_{2}&\text{if }\mathrm{r}_{1}=\infty,\mathrm{r}_{2}<\infty\text{ or vice versa},\\ 0&\text{if }\mathrm{r}_{1}=\mathrm{r}_{2}=\infty;\end{cases} (34) and mapping \hat{D}:\mathbb{R}^{d}\cup\{\hat{\infty}_{i}:i\in[0:2]\}\to\mathbb{R} : \displaystyle\hat{D}^{q}(x,y):=\begin{cases}\|x-y\|^{q}&\text{if }x,y\in\mathbb{R}^{d}\\ 0&\text{elsewhere}.\end{cases} (35) Finally, we define the following mappings: \displaystyle\Gamma_{\leq}(\sigma,\mu)\ni\gamma^{01}\mapsto\hat{\gamma}^{01}\in\Gamma(\hat{\sigma},\hat{\mu}), \displaystyle\hat{\gamma}^{01}:=\gamma^{01}+(\sigma-\gamma_{1}^{01})\otimes\delta_{\hat{\infty}_{0}}+\delta_{\hat{\infty}_{1}}\otimes(\mu-\gamma_{2}^{01})+|\gamma|\delta_{\hat{\infty}_{1},\hat{\infty}_{0}}+|\nu|\delta_{\hat{\infty}_{2},\hat{\infty}_{2}}; \displaystyle\Gamma_{\leq}(\sigma,\nu)\ni\gamma^{02}\mapsto\hat{\gamma}^{02}\in\Gamma(\hat{\sigma},\hat{\nu}), \displaystyle\hat{\gamma}^{02}:=\gamma^{02}+(\sigma-\gamma_{1}^{02})\otimes\delta_{\hat{\infty}_{0}}+\delta_{\hat{\infty}_{2}}\otimes(\nu-\gamma_{2}^{02})+|\gamma|\delta_{\hat{\infty}_{2},\hat{\infty}_{0}}+|\mu|\delta_{\hat{\infty}_{1},\hat{\infty}_{1}}; \displaystyle\Gamma_{\leq}(\mu,\nu)\ni\gamma^{12}\mapsto\hat{\gamma}^{12}\in\Gamma(\hat{\mu},\hat{\nu}), \displaystyle\hat{\gamma}^{12}:=\gamma^{12}+(\mu-\gamma_{1}^{12})\otimes\delta_{\hat{\infty}_{1}}+\delta_{\hat{\infty}_{2}}\otimes(\nu-\gamma_{2}^{12})+|\gamma|\delta_{\hat{\infty}_{2},\hat{\infty}_{1}}+|\mu|\delta_{\hat{\infty}_{0},\hat{\infty}_{0}}. (36) Remark D.4 . It is straightforward to verify the above mappings are well-defined. In addition, we can observe that, for each \gamma^{01}\in\Gamma_{\leq}(\sigma,\mu),\gamma^{02}\in\Gamma_{\leq}(\sigma,\nu),\gamma^{12}\in\Gamma_{\leq}(\mu,\nu) , \displaystyle\hat{\gamma}^{01}(\{\hat{\infty}_{2}\}\times X)=\hat{\gamma}^{01}(S\times\{\hat{\infty}_{2}\})=0, (37) \displaystyle\hat{\gamma}^{02}(\{\hat{\infty}_{1}\}\times Y)=\hat{\gamma}^{02}(S\times\{\hat{\infty}_{1}\})=0, (38) \displaystyle\hat{\gamma}^{12}(\{\hat{\infty}_{0}\}\times Y)=\hat{\gamma}^{12}(X\times\{\hat{\infty}_{0}\})=0. Based on these concepts, we define the following fused-GW variant problem: \displaystyle\hat{d}_{FGW,r,q,\lambda}(\hat{\mathbb{X}},\hat{\mathbb{Y}}):=\inf_{\hat{\gamma}\in\Gamma(\hat{\mu},\hat{\nu})}\int_{(\hat{X}\times\hat{Y})^{2}}\omega_{1}\frac{1}{c}\hat{D}^{q}(x,y)+\omega_{2}L^{q}_{\lambda}(d_{\hat{X}}^{r}(x,x^{\prime}),d_{\hat{Y}}^{r}(y,y^{\prime}))d\hat{\gamma}(x,y)d\hat{\gamma}(x^{\prime},y^{\prime}). (39) where constant c=|\sigma|+|\mu|+|\nu| . Proposition D.5 . For each \gamma^{12}\in\Gamma(\mu,\nu) , construct \hat{\gamma}^{12}\in\Gamma(\hat{\mu},\hat{\nu}) , we have: \displaystyle\int_{(X\times Y)^{2}}\left(\omega_{1}\frac{\|x-y\|^{q}}{|\gamma^{12}|}+\omega_{2}\left|d^{r}_{X}(x,x^{\prime})-d^{r}_{Y}(y,y^{\prime})\right|^{q}+\lambda\left(\frac{|\mu|}{|\gamma^{12}|}+\frac{|\nu|}{|\gamma^{12}|}-2\right)\right)\,d(\gamma^{12})^{\otimes 2} \displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}\left(\omega_{1}\frac{D^{q}(x,y)}{c}+\omega_{2}L^{q}_{\lambda}(d_{\hat{X}}(x,x^{\prime}),d_{\hat{Y}}(y,y^{\prime}))\right)\,d(\hat{\gamma}^{12})^{\otimes 2} (40) Furthermore, we have: \displaystyle d_{FPGW,r,q,\lambda}(\mathbb{X},\mathbb{Y})=\hat{d}_{FGW,r,q,\lambda}(\hat{\mathbb{X}},\hat{\mathbb{Y}}). (41) Proof. We have: \displaystyle\int_{(X\times Y)^{2}}\omega_{1}\frac{\|x-y\|^{q}}{|\gamma^{12}|},d(\gamma^{12})^{\otimes 2} \displaystyle=\int_{(X\times Y)}\omega_{1}\|x-y\|^{q}d\gamma^{12} \displaystyle=\int_{(\hat{X}\times\hat{Y})}\omega_{1}D^{q}(x,y)d\hat{\gamma}^{1,2} \displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}\omega_{1}\frac{D^{p}(x,y)}{|\hat{\gamma}^{12}|}\,d(\hat{\gamma}^{12})^{\otimes 2} \displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}\omega_{1}\frac{1}{c}D^{p}(x,y),d(\hat{\gamma}^{12})^{\otimes 2}. (42) In addition, by [ 28 ] Proposition D.3. We have \displaystyle\int_{(X\times Y)^{2}}\omega_{2}|d_{X}^{r}(x,x^{\prime})-d_{Y}^{r}(y,y^{\prime})|^{q}d(\gamma^{12})^{\otimes 2}+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma^{12}|^{2}) \displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}\omega_{2}D_{\lambda}^{q}(d_{\hat{X}}^{r}(x,x^{\prime}),d_{\hat{Y}}^{r}(y,y^{\prime}))d(\hat{\gamma}^{12})^{\otimes 2}. (43) Combining the above two equalities, we prove ( 40 ). Now, we prove the second equality. Note, if we merge the three auxiliary points, i.e., \hat{\infty}_{1}=\hat{\infty}_{2}=\hat{\infty}_{3} . The optimal value for the above problem ( 39 ) is unchanged. As we merged the points \hat{\infty}_{1},\hat{\infty}_{2},\hat{\infty}_{3} , by Bai et al. [ 16 ] , the mapping \gamma^{12}\mapsto\hat{\gamma}^{12} defined in ( 36 ) is a bijection. Thus, by ( 40 ), we have \gamma^{12}\in\Gamma_{\leq}(\mu,\nu) is optimal in ( 27 ) iff \hat{\gamma}^{12} is optimal in ( 39 ) and we complete the proof. ∎ Lemma D.6 . Choose \gamma^{01}\in\Gamma_{\leq}(\sigma,\mu),\gamma^{02}\in\Gamma_{\leq}(\sigma,\nu),\gamma^{12}\in\Gamma_{\leq}(\mu,\nu) and construct \hat{\gamma}^{01},\hat{\gamma}^{02},\hat{\gamma}^{12} . Then there exists \hat{\gamma}\in\mathcal{M}_{+}(\hat{S}\times\hat{X}\times\hat{Y}) such that: \displaystyle(\pi_{0,1})_{\#}\hat{\gamma}=\hat{\gamma}^{01}, (44) \displaystyle(\pi_{0,2})_{\#}\hat{\gamma}=\hat{\gamma}^{02}, (45) \displaystyle\gamma(A_{i})=0,\forall i=0,1,2\text{ where }A_{i}=\{\hat{\infty}_{i}\}\times X\times Y. (46) Proof. By gluing lemma (see Lemma 5.5 [ 54 ] ), there exists \hat{\gamma}\in\mathcal{M}_{+}(\hat{S}\times\hat{X}\times\hat{Y}) , such that ( 44 ),( 45 ) are satisfied. For the third property, we have: \displaystyle\hat{\gamma}(A_{0})\leq\hat{\gamma}(\{\infty_{0}\}\times\hat{X}\times\hat{Y})=\hat{\sigma}(\{\infty_{0}\})=0\qquad\text{by definition (\ref{pf:sigma_hat,mu_hat,nu_hat}) of $\hat{\sigma}$ , } \displaystyle\hat{\gamma}(A_{1})\leq\hat{\gamma}(\{\infty_{1}\}\times\hat{X}\times Y)=\hat{\gamma}^{02}(\{\hat{\infty}_{1}\times Y\})=0\qquad\text{by }(\ref{pf:gamma02_cond}), \displaystyle\hat{\gamma}(A_{2})\leq\hat{\gamma}(\{\infty_{2}\}\times X\times\hat{Y})=\hat{\gamma}^{01}(\{\hat{\infty}_{2}\times X\})=0\qquad\text{by }(\ref{pf:gamma01_cond}), and we complete the proof. ∎ Now, we demonstrate the proof of triangle inequality for fused-PGW distance ( 27 ). Proof of Theorem D.3 (3). Note, by the Proposition D.5 , the triangle inequality for fused-PGW distance ( 27 ) is equivalent to show \displaystyle\hat{d}_{FGW,r,q,\lambda}(\hat{\mathbb{X}},\hat{\mathbb{Y}})\leq 2^{q-1}(\hat{d}_{FGW,r,q,\lambda}(\hat{\mathbb{S}},\hat{\mathbb{X}})+\hat{d}_{FGW,r,q,\lambda}(\hat{\mathbb{S}},\hat{\mathbb{Y}})). (47) Choose optimal transportation plans \gamma^{01},\gamma^{02},\gamma^{12} for fused PGW problems d_{FPGW,r,\lambda}(\mathbb{S},\mathbb{X}),d_{FPGW,r,\lambda}(\mathbb{S},\mathbb{Y}) and d_{FPGW,r,\lambda}(\mathbb{X},\mathbb{Y}) respectively. We construct the corresponding \hat{\gamma}^{01},\hat{\gamma}^{02},\hat{\gamma}^{12} . By the Proposition D.5 , \hat{\gamma}^{01},\hat{\gamma}^{02},\hat{\gamma}^{12} are optimal. Choose \hat{\gamma} in lemma D.6 . We have: \displaystyle\hat{d}_{FGW,r,q,\lambda}(\mathbb{X},\mathbb{Y}) \displaystyle=\int_{(\hat{X}\times\hat{Y})^{2}}\omega_{1}\frac{D^{q}(x,y)}{c}+\omega_{2}L^{q}_{\lambda}(d_{\hat{X}}(x,x^{\prime}),d_{\hat{Y}}(y,y^{\prime}))d\hat{\gamma}^{12}(x,y)d\hat{\gamma}^{12}(x^{\prime},y^{\prime}) \displaystyle\leq\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}\omega_{1}\frac{D^{q}(x,y)}{c}+\omega_{2}L^{q}_{\lambda}(x,y)d\hat{\gamma}(s,x,y)d\hat{\gamma}(s^{\prime},x^{\prime},y^{\prime}) \displaystyle=\underbrace{\int_{(\hat{S}\times\hat{X}\times\hat{Y})}\omega_{1}D^{q}(x,y)d\hat{\gamma}(s,x,y)}_{A}+\underbrace{\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}\omega_{2}L^{q}_{\lambda}(x,y)d\hat{\gamma}(s,x,y)d\hat{\gamma}(s^{\prime},x^{\prime},y^{\prime})}_{B}. To bound A , we consider the case D(x,y)>D(s,x)+D(s,y) for some (s,x,y)\in\hat{S}\times\hat{X}\times\hat{Y} . By definition of D , we have s\in\{\hat{\infty}_{i}:i\in[0:2]\},x\in X,y\in Y . That is, (s,x,y)\in\bigcup_{i=0}^{2}A_{i} . By lemma D.6 , we have \hat{\gamma}(\bigcup_{i=0}^{2}A_{i})=0 . That is, this case has a measure of 0. Thus, we have \displaystyle A\leq\int_{\hat{S}\times\hat{X}\times\hat{Y}}\omega_{1}(D(s,x)+D(s,y))^{q}d\hat{\gamma}(s,x,y) \displaystyle\leq\int_{\hat{S}\times\hat{X}\times\hat{Y}}\omega_{1}(2^{q-1}D(s,x)+2^{q-2}D(s,y))d\hat{\gamma}(s,x,y) \displaystyle=\int_{\hat{S}\times\hat{X}\times\hat{Y}}\omega_{1}2^{q-1}D(s,x)d\hat{\gamma}(s,x,y)+\int_{\hat{S}\times\hat{X}\times\hat{Y}}\omega_{1}2^{q-2}D(s,y)d\hat{\gamma}(s,x,y) \displaystyle=2^{q-1}\int_{\hat{S}\times\hat{X}}\omega_{1}\frac{D(s,x)}{c}d\hat{\gamma}^{01}(s,x)+2^{q-1}\int_{\hat{S}\times\hat{Y}}\omega_{1}\frac{D(s,y)}{c}d\hat{\gamma}^{02}(s,y). (48) where the second inequality follows from the fact \displaystyle(a+b)^{q}\leq 2^{q-1}a^{q}+2^{q-2}b^{q},\forall a,b\geq 0. (49) Now we bounde the term B . Proposition D.4 in [ 28 ] , we have \displaystyle B \displaystyle\leq\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}\omega_{2}(L_{\lambda}(s,x)+L_{\lambda}(s,y))^{q}d\hat{\gamma}(s,x,y)d\hat{\gamma}(s^{\prime},x^{\prime},y^{\prime}) \displaystyle\leq\int_{(\hat{S}\times\hat{X}\times\hat{Y})^{2}}\omega_{2}\left(2^{q-1}L_{\lambda}^{q}(s,x)+2^{q-1}L_{\lambda}^{q}(s,y)\right)d\hat{\gamma}(s,x,y)d\hat{\gamma}(s^{\prime},x^{\prime},y^{\prime}) \displaystyle=2^{q-1}\int_{(\hat{S}\times\hat{X})^{2}}\omega_{2}L_{\lambda}^{q}(s,x)d\hat{\gamma}^{01}(s,x)d\hat{\gamma}^{01}(s^{\prime},x^{\prime})+2^{q-1}\int_{(\hat{S}\times\hat{Y})^{2}}\omega_{2}L_{\lambda}^{q}(s,y)d\hat{\gamma}^{02}(s,y)d\hat{\gamma}^{02}(s^{\prime},y^{\prime}). (50) where the second inequality holds from ( 49 ). Combining ( 48 ) and ( 50 ), we prove the inequality ( 47 ) and we complete the proof. ∎ D.4 Future’s direction. Note, the general version for (the p-th power of) fused-Gromov Wasserstein distance is defined by \displaystyle d_{FGW,r,q,p}^{p}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\int\left(\omega_{1}\|x-y\|^{q}+|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})|^{q}\right)^{p}d\gamma^{\otimes 2}. (51) Inspired by the above formulation, we propose the following generalized fused-partial Gromov Wasserstein distance: \displaystyle d_{FGW,r,q,p}^{p}(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma(\mu,\nu)}\int\left(\omega_{1}\frac{\|x-y\|^{q}}{|\gamma|}+|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})|^{q}+\lambda(\frac{|\mu|^{2}}{|\gamma|^{2}}+\frac{|\nu|^{2}}{|\gamma|^{2}}-2)\right)^{p}d\gamma^{\otimes 2}. (52) The fused-PGW distance defined in ( 27 ) can be treated as a special case of this general formulation by setting p=1 . In our conjecture, a similar (semi-)metric property proposed in Theorem D.3 holds for the above general form. We leave the theoretical study of the metric property for our future work. Appendix E Frank Wolf Algorithm for the Fused Mass-constraint Partial Gromov Wasserstein problem In discrete setting, the FMPGW problem ( 10 ) becomes the following: \displaystyle FMPGW_{\rho}(\mathbb{X},\mathbb{Y})=\min_{\gamma\in\gamma_{\leq}^{\rho}(p,q)}\underbrace{\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle M\circ\gamma,\gamma}_{\mathcal{L}_{C,M}}\rangle (53) where \Gamma_{\leq}^{\rho}(\mathrm{p},\mathrm{q}):=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\gamma 1_{m}\leq\mathrm{p},\gamma^{\top}1_{n}\leq\mathrm{q},|\gamma|\geq\rho\} , C=[C(x_{i},y_{j})]_{i\in[1:n],j\in[1:m]} , M_{i,j,i^{\prime},j^{\prime}}:=L(C^{X},C^{Y}):=[L(C^{X}_{i,i^{\prime}},C^{Y}_{j,j^{\prime}})]_{i,i\in[1:n],j,j^{\prime}\in[1:n]} , M\circ\gamma=[\langle M[i,j,\cdot,\cdot],\gamma\rangle]_{i,j} . Similar to the Fused Gromov-Wasserstein problem, we propose the following Frank-Wolfe algorithm as a solver: The above problem will be solved iteratively. In every iteration, say k , we will adapt the following steps: Step 1. Gradient computation. Suppose \gamma^{(k-1)} is the transportation plan in the previous iteration; it is straightforward to verify: \nabla\mathcal{L}_{C,M}(\gamma)=\omega_{1}C+\omega_{2}((M+M^{\top})\circ\gamma), where M^{\top}=[M_{i^{\prime},j^{\prime},i,j}]_{i,i^{\prime}\in[1:n],j,j^{\prime}\in[1:m]}\in\mathbb{R}^{n\times m\times n\times m} . Next, we aim to find \gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu) for the following problem: \displaystyle\gamma^{(k)}{{}^{\prime}}:=\arg\min_{\gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\langle\nabla\mathcal{L}_{C,M}(\gamma^{(k-1)}),\gamma\rangle. (54) which is a mass-constraint partial OT problem. Step 2. linear search algorithm. In this step, we aim to find the optimal step size \alpha^{(k)}\in[0,1] . In particular, \displaystyle\alpha^{(k)}:=\arg\min_{\alpha\in[0,1]}\mathcal{L}_{C,M}((1-\alpha)\gamma^{(k-1)}+\alpha\gamma^{(k)}{{}^{\prime}}). Let \delta\gamma=\gamma^{(k)}{{}^{\prime}}-\gamma^{(k-1)} , the above problem is essentially quadratic problem: \displaystyle\mathcal{L}((1-\alpha)\gamma^{(k-1)}+\alpha\gamma^{(k)}{{}^{\prime}})=\alpha^{2}\underbrace{\langle\omega_{2}M\circ\delta\gamma,\delta\gamma\rangle}_{a} \displaystyle+\alpha\underbrace{\langle\omega_{2}(M+M^{\top})\circ\gamma^{(k-1)}+\omega_{1}C,\delta\gamma\rangle}_{b} \displaystyle+\underbrace{\langle\omega_{2}M\circ\gamma^{(k-1)}+\omega_{1}C,\gamma\rangle}_{c} (55) and \alpha^{*} is given by \displaystyle\alpha^{*}=\begin{cases}1&\text{if }a\leq 0,a+b\leq 0,\\ 0&\text{if }a\leq 0,a+b>0\\ \text{clip}(\frac{-b}{2a},[0,1]),&\text{if }a>0\end{cases}. (56) Then \gamma^{(k)}=(1-\alpha^{*})\gamma^{(k-1)}+\alpha^{*}\gamma^{(k)}{{}^{\prime}} . Algorithm 3 Frank-Wolfe Algorithm for FMPGW Input: C\in\mathbb{R}^{n\times m},C^{X}\in\mathbb{R}^{n\times n},C^{Y}\in\mathbb{R}^{m\times m},\mathrm{p}\in\mathbb{R}^{n}_{+},\mathrm{q}\in\mathbb{R}^{m}_{+} , \omega_{1}\in[0,1],\rho\in[0,\min(|\mathrm{p}|,|\mathrm{q}|)] . Output: \gamma^{(final)} for k=1,2,\ldots do G^{(k)}\leftarrow\omega_{1}C+\omega_{2}(M+M^{\top})\circ\gamma^{(k)} // Compute gradient \gamma^{(k)}{{}^{\prime}}\leftarrow\arg\min_{\gamma\in\Gamma^{\rho}_{\leq}(\mathrm{p},\mathrm{q})}\langle G^{(k)},\gamma\rangle_{F} // Solve the POT problem. Compute \alpha^{(k)}\in[0,1] via ( 14 ) // Line Search \gamma^{(k+1)}\leftarrow(1-\alpha^{(k)})\gamma^{(k)}+\alpha^{(k)}\gamma^{(k)^{\prime}} // Update \gamma if convergence, break end for \gamma^{(final)}\leftarrow\gamma^{(k)} In the next section, we provide a detailed introduction to how the FW algorithms are derived. Appendix F Gradient computation of FW algorithms In this section, we discuss in detail the gradient computation in fused-MPGW and fused-PGW. F.1 Basics in Tensor product In this section, we introduce some fundamental results for tensor computation. Suppose M\in\mathbb{R}^{n\times m\times n\times m} . We define the Transportation of tensor , denoted as M^{\top} , as: \displaystyle M^{\top}_{i,j,i^{\prime},j^{\prime}}=M_{i^{\prime},j^{\prime},i,j}, (57) and we say M is symmetric if M=M^{\top} . It is straightforward to verify the following: Proposition F.1 . Given tensor M\in\mathbb{R}^{n\times m\times n\times m} , then we have: – (M^{\top})^{\top}=M. – M^{\top}\circ\gamma=[\sum_{i^{\prime},j^{\prime}}M_{i^{\prime},j^{\prime},i,j}\gamma_{i,j}]_{i,j\in[1:n]\times[1:m]} . Proof. The first item follows from the definition of M^{\top} . For the second statement, pick (i,j)\in[1:n]\times[1:m] , we have \displaystyle\sum_{i^{\prime},j^{\prime}}M_{i^{\prime},j^{\prime},i,j}\gamma_{i^{\prime},j^{\prime}} \displaystyle=\sum_{i^{\prime},j^{\prime}}M^{\top}_{i,j,i^{\prime},j^{\prime}}\gamma_{i^{\prime},j^{\prime}} \displaystyle=\langle M^{\top}\circ\gamma\rangle. ∎ Therefore, we have: Proposition F.2 . The gradient for \mathcal{L}_{C,M}(\gamma) in Fused-PGW ( 10 ) is given by: \displaystyle\nabla\mathcal{L}_{C,M}(\gamma)=\omega_{1}C+\omega_{2}(M\circ\gamma+M^{\top}\circ\gamma). (58) . Similarly, the gradient for \mathcal{L}_{C,M-2\lambda} in fused-PGW ( 11 ) is given by: \displaystyle\nabla\mathcal{L}_{C,M-2\lambda}(\gamma)=\omega_{1}C+\omega_{2}((M-2\lambda)\circ\gamma+(M-2\lambda)^{\top}\circ\gamma). (59) . Proof. Pick (i,j)\in[1:n]\times[1:m] , we have: \displaystyle\frac{\partial}{\partial\gamma_{ij}}L_{C,M}(\gamma) \displaystyle=\frac{\partial}{\partial\gamma_{ij}}\sum_{i,j,i^{\prime},j^{\prime}}\omega_{1}C_{i,j}\gamma_{i,j}+\omega_{2}\sum_{i,j,i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}\gamma_{i,j}\gamma_{i^{\prime},j^{\prime}} \displaystyle=\omega_{1}C_{i,j}+\omega_{2}(\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}\gamma_{i,j}\gamma_{i^{\prime},j^{\prime}}+\sum_{i^{\prime},j^{\prime}}M_{i^{\prime},j^{\prime},i,j}\gamma_{i,j}\gamma_{i^{\prime},j^{\prime}}) Therefore, \nabla L_{C,M}(\gamma)=\omega_{1}C+\omega_{2}(M\circ\gamma+M^{\top}\circ\gamma) and we complete the proof. The gradient for Fused-PGW ( 11 ) can be derived similarly. ∎ At the end of this subsection, we discuss the computation of M\circ\gamma and M^{\top}\gamma . In general, the computation cost for M\circ\gamma is n^{2}m^{2} . However, if the cost function L satisfies: \displaystyle L(\mathrm{r}_{1},\mathrm{r}_{2})=f_{1}(\mathrm{r}_{1})+f_{2}(\mathrm{r}_{2})-h_{1}(\mathrm{r}_{1})h_{2}(\mathrm{r}_{2}), (60) \displaystyle M\circ\gamma=f_{1}(C^{X})\gamma_{1}1_{m}^{\top}+1_{n}\gamma_{2}^{\top}f_{2}(C^{Y})-h_{1}(C^{X})\gamma h_{2}(C^{Y}), (61) and the corresponding complexity is \mathcal{O}(n^{2}+m^{2}) (see e.g. [ 55 , 21 , 28 ] for details.) Therefore, we have the following: Lemma F.3 . Suppose M=[L(d_{X}(x_{i},x_{i^{\prime}}),d_{Y}(y_{j},y_{j^{\prime}}))] , then we have: (M^{\top})_{i,j,i^{\prime},j^{\prime}}=f_{1}((C^{X})^{\top}_{i,i^{\prime}})+f_{2}((C^{Y})^{\top}_{j,j^{\prime}})-h_{1}((C^{X})_{i,i^{\prime}})h_{2}((C^{Y})_{j,j^{\prime}}). It directly implies: M^{\top}\circ\gamma=f_{1}((C^{X})^{\top})\gamma_{1}1_{m}^{\top}+1_{n}\gamma_{2}^{\top}f_{2}((C^{Y})^{\top})-h_{1}((C^{X})^{\top})\gamma h_{2}((C^{Y})^{\top}). Proof. We have: \displaystyle M_{i,j,i^{\prime},j^{\prime}}^{\top} \displaystyle=M_{i^{\prime},j^{\prime},i,j} \displaystyle=f_{1}(C^{X}_{i^{\prime},i})+f_{2}(C^{Y}_{j^{\prime},j})-h_{1}(C^{X}_{i^{\prime},i})h_{2}(C^{Y}_{j^{\prime},j})) \displaystyle=f_{1}((C^{X})^{\top}_{i^{\prime},i})+f_{2}((C^{Y})^{\top}_{j^{\prime},j})-h_{1}((C^{X})^{\top}_{i^{\prime},i})h_{2}((C^{Y})^{\top}_{j^{\prime},j}).) And we complete the proof. ∎ F.2 Gradient in fused-MPGW. As we discussed in previous section, after iteration k-1 , the gradient is given by \nabla\mathcal{L}(\gamma)=\omega_{1}C+\omega_{2}(M\circ\gamma+M^{\top}\circ\gamma) , where M_{i,j,i^{\prime},j^{\prime}}=(L(C^{X}_{i,i^{\prime}},C^{Y}_{j,j^{\prime}}))\in\mathbb{R}_{+}^{n\times m\times n\times m} . Furthermore, the computational complexity for M\circ\gamma:=[\langle M[i,j,:,:],\gamma\rangle] can be improved to be \mathcal{O}(n^{2}+m^{2}) . Based on the gradient, we aim to solve the following to update the transportation plan in iteration k : \displaystyle\gamma^{(k)}{{}^{\prime}}=\arg\min_{\gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\langle\underbrace{\omega_{1}C+\omega_{2}(M\circ\gamma^{(k-1)}+M^{\top}\gamma^{(k-1)})}_{\mathcal{C}},\gamma\rangle. (62) The above problem is essentially the partial OT problem, where the cost function is defined by \mathcal{C} . F.3 Gradient of Fused-PGW. Similarly, after iteration k-1 , the gradient of cost \mathcal{L}_{C,M-2\lambda} in FPGW with respect to \gamma is given by \nabla\mathcal{L}(\gamma)=\omega_{1}C+\omega_{2}((M-2\lambda)\circ\gamma^{(k-1)}+(M^{\top}-2\lambda)\circ\gamma^{(k-1)}). We aim to solve the following problem: \displaystyle\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\langle\omega_{1}C+\omega_{2}((M-2\lambda)\circ\gamma^{(k-1)}+(M^{\top}-2\lambda)\circ\gamma^{(k-1)}),\gamma\rangle \displaystyle=\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\langle\underbrace{\omega_{1}C+\omega_{2}(M\circ\gamma^{(k-1)}+M^{\top}\circ\gamma^{(k-1)})}_{\mathcal{C}},\gamma\rangle+\lambda|\gamma^{(k-1)}|(|\mu|+|\nu|-2|\gamma|)-\underbrace{\lambda|\gamma^{(k-1)}|(|\mu|+|\nu|)}_{\text{constant}}. Note, if we ignore the constant term, the above problem is the partial OT problem and can be solved by [ 33 ] or [ 16 ] . Appendix G Line search algorithm The line search for Fused-MPGW is defined as \displaystyle\min_{\alpha\in[0,1]}\mathcal{L}((1-\alpha)\gamma^{(k-1)}+\alpha\gamma^{(k)}{{}^{\prime}}), (63) where \mathcal{L}(\gamma)=\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle M,\gamma^{\otimes 2}\rangle . Let \delta\gamma=\gamma^{(k)}{{}^{\prime}}-\gamma^{(k-1)} . The above problem is essentially a quadratic problem with respect to \alpha : \displaystyle\mathcal{L}((1-\alpha)\gamma^{(k-1)}+\alpha\gamma^{(k)}{{}^{\prime}}) \displaystyle=\mathcal{L}(\gamma^{(k-1)}+\alpha\delta\gamma) \displaystyle=\omega_{1}\langle C,(\gamma^{(k-1)}+\alpha\delta\gamma)\rangle+\omega_{2}\langle M\circ(\gamma^{(k-1)}+\alpha\delta\gamma),(\gamma^{(k-1)}+\alpha\delta\gamma)\rangle \displaystyle=\alpha^{2}\underbrace{\omega_{2}\langle M\circ\delta\gamma,\delta\gamma\rangle}_{a}+\alpha\underbrace{\langle\omega_{2}M\circ\gamma^{(k-1)}+\omega_{1}C,\delta\gamma\rangle+\langle\omega_{2}M\circ\delta\gamma,\gamma^{(k-1)}\rangle}_{b}+\underbrace{\langle\omega_{2}M\circ\gamma^{(k-1)}+\omega_{1}C,\gamma^{(k-1)}\rangle}_{c}, (64) and \alpha^{*} is given by \displaystyle\alpha^{*}=\begin{cases}1&\text{if }a\leq 0,a+b\leq 0,\\ 0&\text{if }a\leq 0,a+b>0\\ \text{clip}(\frac{-b}{2a},[0,1]),&\text{if }a>0\end{cases}. (65) Next, we simplify the term b in the above formula. We first introduce the following lemma: Lemma G.1 . Choose \gamma^{1},\gamma^{2}\in\mathbb{R}^{n\times m},M\in\mathbb{R}^{n\times m\times n\times m} , we have: \displaystyle\langle M\circ\gamma^{1},\gamma^{2}\rangle=\langle M^{\top}\circ\gamma^{2},\gamma^{1}\rangle. (66) Proof. We have \displaystyle\langle M\circ\gamma^{1},\gamma^{2}\rangle \displaystyle=\sum_{i,j}\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}\gamma^{1}_{i^{\prime},j^{\prime}}\gamma^{2}_{i,j} \displaystyle=\sum_{i^{\prime},j^{\prime}}\sum_{i,j}M_{i^{\prime},j^{\prime},i,j}^{\top}\gamma^{2}_{i,j}\gamma^{1}_{i,j} \displaystyle=\langle M^{\top}\circ\gamma^{2},\gamma^{1}\rangle. (67) ∎ Therefore, the term b can be further simplified as \displaystyle b \displaystyle=\omega_{1}\langle C,\delta\gamma\rangle+\omega_{2}(\langle M\circ\gamma^{(k-1)},\delta\gamma\rangle+\langle M^{\top}\circ\gamma^{(k-1)},\delta\gamma\rangle) \displaystyle=\langle\underbrace{\omega_{1}C+M\circ\gamma^{(k-1)}+M^{\top}\circ\gamma^{(k-1)}}_{\nabla L_{C,M}(\gamma)},\delta\gamma\rangle. (68) That is, we can directly adapt the gradient obtained before to compute b and improve the computation efficiency. Remark G.2 . When we select quadratic cost, i.e., L(\mathrm{r}_{1},\mathrm{r}_{2}):=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{2} , we can set f_{1}(\mathrm{r}_{1})=\mathrm{r}_{1}^{2},f_{2}(\mathrm{r}_{2})=\mathrm{r}_{2}^{2},h_{1}(\mathrm{r}_{1})=2\mathrm{r}_{1},h_{2}(\mathrm{r}_{2})=\mathrm{r}_{2} , then L(\mathrm{r}_{1},\mathrm{r}_{2}) satisfies ( 60 ). Furthermore, suppose the problem is in the balanced fused-GW setting, i.e., \rho=|\mu|=|\nu|=1 . We have: \displaystyle a \displaystyle=\omega_{2}\langle M\circ\delta\gamma,\delta\gamma\rangle \displaystyle=\omega_{2}\langle f_{1}(C^{X})\underbrace{\delta\gamma_{1}}_{0_{n}}1_{m}^{\top}+\underbrace{1_{n}\delta\gamma_{2}^{\top}}_{0_{m}}f_{2}(C^{Y})-h_{1}(C^{X})\gamma h_{2}(C^{Y}),\delta\gamma\rangle (69) \displaystyle=-2\omega_{2}\langle C^{X}\delta\gamma C^{Y},\delta\gamma\rangle. Similarly, \displaystyle b \displaystyle=\langle\omega_{2}(M+M^{\top})\circ\gamma^{(k-1)}+\omega_{1}C,\delta\gamma\rangle \displaystyle=\omega_{1}\langle C,\delta\gamma\rangle+\omega_{2}\langle(M+M^{\top})\circ\gamma^{(k-1)},\delta\gamma\rangle \displaystyle=\omega_{1}\langle C,\delta\gamma\rangle+\omega_{2}\langle(M+M^{\top})\circ\delta\gamma,\gamma^{(k-1)}\rangle \displaystyle=\omega_{1}\langle C,\delta\gamma\rangle-2\omega_{2}\langle C^{X}\delta\gamma C^{Y},\gamma^{(k-1)}\rangle-2\omega_{2}\langle(C^{X})^{\top}\delta\gamma(C^{Y})^{\top},\gamma^{(k-1)}\rangle+\omega_{2}\langle c_{C^{X},C^{Y}},\gamma^{(k-1)}\rangle \displaystyle+\omega_{2}\langle c_{(C^{X})^{\top},(C^{Y})^{\top}},\gamma^{(k-1)}\rangle. (70) where c_{C^{X},C^{Y}}=f_{1}(C^{X})\mathrm{p}1_{m}^{\top}+1_{m}\mathrm{q}^{\top}f_{2}(C^{Y}) . Thus, the above formulations recover the line search algorithm (see algorithm 2) in [ 55 ] . Next, we discuss the line search step in fused-PGW ( 7 ). Replacing M by M-2\lambda in ( 64 ), the solution is obtained by ( 14 ). Appendix H Convergence Analysis As in [ 21 ] , we will use the results from [ 56 ] on the convergence of the Frank-Wolfe algorithm for non-convex objective functions. H.1 Fused-MPGW Consider the minimization problems \min_{\gamma\in\Gamma^{\rho}_{\leq}(\mathrm{p},\mathrm{q})}\mathcal{L}_{C,M}(\gamma):=\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle M\circ\gamma,\gamma\rangle that corresponds to the discrete fused-PGW problem ( 11 ). The objective functions \gamma\mapsto\mathcal{L}_{\hat{M}}(\gamma)=\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle M\circ\gamma,\gamma\rangle, is non-convex in general. However, the constraint set \Gamma_{\leq}^{\rho}(p,q) are convex and compact on \mathbb{R}^{n\times m} (see Proposition C.4 .) Consider the Frank-Wolfe gap of \mathcal{L}_{C,M} at the approximation \gamma^{(k)} of the optimal plan \gamma : g_{k}=\max_{\gamma\in\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})}\langle\nabla\mathcal{L}_{\tilde{M}}(\gamma^{(k)}),\gamma^{(k)}-\gamma\rangle_{F}. (71) It provided a good criterion to measure the distance to a stationary point at iteration k . Indeed, a plan \gamma^{(k)} is a stationary transportation plan for the corresponding constrained optimization problem in ( H.1 ) if and only if g_{k}=0 . Moreover, g_{k} is always non-negative ( g_{k}\geq 0 ). From Theorem 1 in [ 56 ] , after K iterations, we have the following upper bound for the minimal Frank-Wolf gap: g_{K}:=\min_{1\leq k\leq K}g_{k}\leq\frac{\max\{2L_{1},\mathrm{Lip}\cdot(\text{diam}(\Gamma_{\leq}^{\rho}({\mathrm{p}},{\mathrm{q}})))^{2}\}}{\sqrt{K}}, (72) where L_{1}:=\mathcal{L}_{\tilde{M}}(\gamma^{(1)})-\min_{\gamma\in\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}})}\mathcal{L}_{\tilde{M}}(\gamma) is the initial global sub-optimal bound for the initialization \gamma^{(1)} of the algorithm; Lip is the Lipschitz constant of function \gamma\mapsto\nabla\mathcal{L}_{\tilde{M}} ; and \text{diam}(\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}}))=\sup_{\gamma,\gamma^{\prime}\in\Gamma_{\leq}(\mu,\nu)}\|\gamma-\gamma^{\prime}\|_{F} is the \|\cdot\|_{F} diameter of \Gamma_{\leq}({\mathrm{p}},{\mathrm{q}}) in \mathbb{R}^{n\times m} . The important thing to notice is that the constant \max\{2L_{1},D_{L}\} does not depend on the iteration step k . Thus, according to Theorem 1 in [ 56 ] , the rate in \tilde{g}_{K} is \mathcal{O}(1/\sqrt{K}) . That is, the algorithm takes at most \mathcal{O}(1/\varepsilon^{2}) iterations to find an approximate stationary point with a gap smaller than \varepsilon . Next, we will continue to simplify the upper bound ( 72 ). We first introduce the following fundamental results: Lemma H.1 . In the discrete setting, we have \displaystyle{\rm diam}(\Gamma_{\leq}(p,q))\leq 2\rho. (73) Proof. Choose \gamma,\gamma^{\prime}\in\Gamma_{\leq}^{\rho}(p,q) , we apply the property \displaystyle(a-b)^{2}\leq 2a^{2}+2b^{2},\quad\forall a,b\in\mathbb{R}. (74) and obtain \displaystyle\|\gamma-\gamma^{\prime}\|_{F}^{2} \displaystyle=\sum_{i,j}^{n,m}|\gamma_{i,j}-\gamma^{\prime}_{i,j}|^{2} \displaystyle\leq\sum_{i,j}^{n,m}2|\gamma_{i,j}|^{2}+2|\gamma^{\prime}_{i,j}|^{2} \displaystyle\leq 2\left[\left(\sum_{i,j}^{n,m}\gamma_{i,j}\right)^{2}+\left(\sum_{i,j}^{n,m}\gamma^{\prime}_{i,j}\right)^{2}\right] \displaystyle=2(|\gamma|^{2}+|\gamma^{\prime}|^{2}) (75) \displaystyle=2(\rho^{2}+\rho^{2})=4\rho^{2}, and thus, we complete the proof. ∎ Lemma H.2 . The Lipschitz constant term in ( 72 ) can be bounded as follows: \displaystyle\text{Lip}\leq\omega_{2}nm\max(|M|)^{2}. (76) In particular, when L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{p} where p\geq 1 , we have \text{Lip}\leq nm(2^{p-1}C^{X}+2^{p-1}C^{Y})^{2} . Proof. Pick \gamma,\gamma^{\prime}\in\Gamma_{\leq}({\mathrm{p}},{\mathrm{q}}) we have, \displaystyle\|\nabla\mathcal{L}_{M}(\gamma)-\nabla\mathcal{L}_{C,M}(\gamma^{\prime})\|_{F}^{2} \displaystyle=\|(\omega_{1}C+\omega_{2}(M\circ\gamma+M^{\top}\circ\gamma))-(\omega_{1}C+\omega_{2}(M\circ\gamma^{\prime}+M^{\top}\circ\gamma^{\prime}))\|_{F}^{2} \displaystyle=2\omega_{2}^{2}\|M\circ(\gamma-\gamma^{\prime})\|_{F}^{2}+2\omega_{2}^{2}\|M^{\top}\circ(\gamma-\gamma^{\prime})\|_{F}^{2} \displaystyle=2\omega_{2}^{2}\sum_{i,j}\left(\left[M\circ(\gamma-\gamma^{\prime})\right]_{i,j}\right)^{2}+2\omega_{2}^{2}\sum_{i,j}\left(\left[M^{\top}\circ(\gamma-\gamma^{\prime})\right]_{i,j}\right)^{2} \displaystyle=2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}M_{i,j,i^{\prime},j^{\prime}}(\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}})\right)^{2}+2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}M^{\top}_{i,j,i^{\prime},j^{\prime}}(\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}})\right)^{2} \displaystyle\leq 2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}|M_{i,j,i^{\prime},j^{\prime}}||\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2}+2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}|M^{\top}_{i,j,i^{\prime},j^{\prime}}||\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2} \displaystyle\leq 4\omega_{2}^{2}\underbrace{\max(M)^{2}}_{A}\cdot\underbrace{\sum_{i,j}^{n,m}\left(\sum_{i^{\prime},j^{\prime}}^{n,m}|\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2}}_{B} For the second term, we have: \displaystyle\sum_{i,j}^{n,m}\left(\sum_{i^{\prime},j^{\prime}}^{n,m}|\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2} \displaystyle\leq\sum_{i,j}^{n,m}\left(nm\sum_{i^{\prime},j^{\prime}}^{n,m}\left|\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}\right|^{2}\right) \displaystyle\leq n^{2}m^{2}\|\gamma-\gamma^{\prime}\|^{2}_{F} (77) For the first term, when L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{p} , from the inequality ( 49 ), we have: \displaystyle A \displaystyle=\max M\leq\max\{2^{p-1}(C^{X})^{p}+2^{p-1}(C^{Y})^{p}\}^{2}. where \max\{2^{p-1}(C^{X})^{p}+2^{p-1}(C^{Y})^{p}\}:=\max\{\max_{i,i^{\prime},j^{\prime},j^{\prime}}2^{p-1}(C^{X}_{i,i^{\prime}})^{p}+2^{p-1}(C^{Y}_{j,j^{\prime}})^{p}\}. Thus we obtain \displaystyle\text{Lip}\leq\frac{\max(2^{p-1}(C^{X})^{p}+2^{p-1}(C^{Y})^{p})nm\|\gamma-\gamma^{\prime}\|_{F}}{\|\gamma-\gamma^{\prime}\|_{F}}=\omega_{2}nm\max(2^{p-1}(C^{X})^{p}+2^{p-1}(C^{Y})^{p}). and we complete the proof. ∎ Combined the above two lemmas, we derive the convergence rate of the Frank-Wolfe gap ( 71 ): Proposition H.3 . When L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{2} in the PGW problem, the Frank-Wolfe gap of algorithm 3 , defined in ( 71 ) at iteration k satisfies the following: \displaystyle g_{k}\leq\frac{\max\Bigg\{2L_{1},4\omega_{2}\rho^{2}\cdot nm(\max\{2(C^{X})^{2}+2(C^{Y})^{2}\})\Bigg\}}{\sqrt{k}}. (78) Proof. The proof directly follows from the upper bounds ( 73 ),( 76 ) and the inequality ( 72 ). ∎ Remark H.4 . Note, if the cost function in PGW is defined by |\mathrm{r}_{1}-\mathrm{r}_{2}|^{p} for some p\neq 2 , it is straightforward to verify that the upper bound of g_{k} is obtained by replacing the term \max((C^{X})^{2}+(C^{Y})^{2}) should be replaced by \max_{i,j,i^{\prime},j^{\prime}}\left[2^{p-1}((C^{X})^{p}+(C^{Y})^{p})\right]. Remark H.5 . From the proposition ( H.3 ), to achieve an \epsilon- accurate solution, the required number of iterations is \displaystyle\frac{\max\Bigg\{2L_{1},4\rho\omega_{2}\cdot n^{2}m^{2}\max(\{2(C^{X})^{2}+2(C^{Y})^{2}\})\Bigg\}^{2}}{\epsilon^{2}}. Remark H.6 . Note, when \omega_{2}=1 , this convergence rate is constant to the convergence rate of the FW algorithm for MPGW in [ 21 ] . In addition, the convergence rate is independent of C . The main reason is that the part \omega_{1}\langle C,\gamma\rangle is linear with respect to \gamma . Thus, this part does not contribute to the Lipschitz of the mapping \gamma\mapsto\nabla_{M}(\mathcal{L}) . H.2 Convergence of Fused-PGW Similar to the above, in this subsection, we discuss the convergence rate for algorithm 2. Suppose \gamma is a solution for the fused-PGW problem ( 11 ). In iteration k , we define the gap between \gamma and the approximation \gamma^{(k)} and the Frank-Wolfe gap: \displaystyle g_{k}:=\max_{\gamma\in\Gamma_{\leq}(p,q)}\langle\nabla\mathcal{L}_{C,M-2\lambda}(\gamma^{(k)}),\gamma^{(k)}-\gamma\rangle_{F}. (79) \displaystyle g_{K}:=\min_{1\leq k\leq K}g_{k}. (80) Thus, the convergence rate for the FW algorithm for the fused-PGW problem ( 11 ) can be bounded by the following proposition: Proposition H.7 . When L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{2} in the Fused-PGW problem, the Frank-Wolfe gap of algorithm 1 , ( 71 ) at iteration k satisfies the following: \displaystyle g_{K}\leq\frac{\max\Bigg\{2L_{1},4\omega_{2}\min^{2}(|p|,|q|)\cdot nm(\max\{2(C^{X})^{2}+2(C^{Y})^{2},2\lambda\})\Bigg\}}{\sqrt{k}}, (81) where \max(2(C^{X})^{2}+2(C^{Y})^{2},2\lambda)=\max\{\max_{i,i^{\prime},j,j^{\prime}}(2(C^{X}_{i,i^{\prime}})^{2}+2(C^{Y}_{j,j^{\prime}})^{2},2\lambda\} . From Theorem 1 in [ 56 ] , we have: \displaystyle g_{K}\leq\frac{\max\{2L_{1},\text{Lip}\cdot(\text{diam}(\Gamma_{\leq}(p,q)))\}}{\sqrt{K}}, (82) where Lip is the Lipschitz constant of function \gamma\to\nabla_{M}\mathcal{L} (with respect to Fubini norm). By [ 28 ] , \displaystyle\text{diam}(\Gamma_{\leq}(p,q))\leq 2\min(|p|,|q|). (83) Next, we bound the Lipschitz constant. Lemma H.8 . The Lipschitz constant in ( 82 ) can be bounded as follows: \displaystyle\text{\rm Lip}\leq\omega_{2}nm\max|M-2\lambda|^{2}. (84) When L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{p} , we have: \displaystyle\text{\rm Lip}\leq\omega_{2}nm(\max(2^{p-1}(C^{X})^{2}+2^{p-1}(C^{Y})^{p},2\lambda))^{2}. (85) Proof. We have: \displaystyle\|\nabla\mathcal{L}_{C,M-2\lambda}(\gamma)-\nabla\mathcal{L}_{C,M-2\lambda}(\gamma^{\prime})\|_{F}^{2} \displaystyle=\|(\omega_{1}C+\omega_{2}((M-2\lambda)\circ\gamma+(M^{\top}-2\lambda)\circ\gamma))-(\omega_{1}C+\omega_{2}((M-2\lambda)\circ\gamma^{\prime}+(M^{\top}-2\lambda)\circ\gamma^{\prime}))\|_{F}^{2} \displaystyle=2\omega_{2}^{2}\|(M-2\lambda)\circ(\gamma-\gamma^{\prime})\|_{F}^{2}+2\omega_{2}^{2}\|(M^{\top}-2\lambda)\circ(\gamma-\gamma^{\prime})\|_{F}^{2} \displaystyle=2\omega_{2}^{2}\sum_{i,j}\left(\left[(M-2\lambda)\circ(\gamma-\gamma^{\prime})\right]_{i,j}\right)^{2}+2\omega_{2}^{2}\sum_{i,j}\left(\left[(M^{\top}-2\lambda)\circ(\gamma-\gamma^{\prime})\right]_{i,j}\right)^{2} \displaystyle=2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}(M_{i,j,i^{\prime},j^{\prime}}-2\lambda)(\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}})\right)^{2}+2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}(M^{\top}_{i,j,i^{\prime},j^{\prime}}-2\lambda)(\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}})\right)^{2} \displaystyle\leq 2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}|M_{i,j,i^{\prime},j^{\prime}}-2\lambda||\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2}+2\omega_{2}^{2}\sum_{i,j}\left(\sum_{i^{\prime},j^{\prime}}(|M^{\top}_{i,j,i^{\prime},j^{\prime}}-2\lambda||\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2} \displaystyle\leq 4\omega_{2}^{2}\underbrace{\max(|M-2\lambda|)^{2}}_{A}\cdot\underbrace{\sum_{i,j}^{n,m}\left(\sum_{i^{\prime},j^{\prime}}^{n,m}|\gamma_{i^{\prime},j^{\prime}}-\gamma^{\prime}_{i^{\prime},j^{\prime}}|\right)^{2}}_{B}. Term B can be bounded by ( 77 ). Thus, we obtain the upper bound ( 84 ). Furthermore, when L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{p} , from inequality ( 49 ), we have: \displaystyle\max(|M-2\lambda|)\leq\max(\max_{i,i^{\prime}}2^{p-1}(C^{X})^{p}_{i,i^{\prime}}+\max_{j,j^{\prime}}2^{p-1}(C^{Y})_{j,j^{\prime}}^{p},2\lambda):=\max(2^{p-1}(C^{X})^{p-1},2^{p-1}(C^{Y})^{p},2\lambda) and we obtain the bound ( 85 ). ∎ Proof of Proposition H.7 . Combining Lemma H.2 , ( 83 ) and ( 82 ), we obtain the upper bound ( 78 ) and complete the proof. ∎ Appendix I Sinkhon Algorithm for Fused Partial Gromov Wasserstein problem For convenience, in this section we default to setting L(d_{X}^{r},d_{Y}^{R})=\|d_{X}-d_{Y}\|^{2}, while all propositions, algorithms and proofs extend without loss of generality to a generic loss function L(d_{X}^{r},d_{Y}^{r}) . I.1 Sinkhorn Algorithm for FPGW metric Given mm-spaces \mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) , the general unbalanced Fused-Gromov Wasserstein setting, the entropic problem is defined as the following: \displaystyle\min_{\gamma\in\mathcal{M}_{+}(\mathcal{X}\times\mathcal{Y})} \displaystyle\mathcal{L}(\gamma)+\epsilon D_{KL}(\gamma^{\otimes 2}\parallel(\mu\otimes\nu)^{\otimes 2}) (86) \displaystyle\mathcal{L}(\gamma) \displaystyle:=\omega_{1}\int_{X\times Y}d(x,y)d\gamma+\omega_{2}\int_{X^{2}\times Y^{2}}|d_{X}-d_{Y}|^{2}d\gamma^{\otimes 2} \displaystyle\qquad+\lambda(D_{\phi}(\gamma_{1}^{\otimes 2}\parallel\mu^{\otimes 2})+D_{\phi}(\gamma_{2}^{\otimes 2}\parallel\nu^{\otimes 2})) where D_{\phi} is \phi- divergence, D_{KL}(\mu\parallel\nu)=\begin{cases}\underbrace{\int\ln(\frac{d\mu}{d\nu})d\mu}_{\bar{D}_{KL}(\mu\parallel\nu)}+|\nu|-|\mu|&\text{if }\mu\ll\nu\\ +\infty&\text{elsewhere}\end{cases}. In the Fused Partial GW setting, D_{\phi} becomes \displaystyle D_{PTV}(\mu\parallel\nu):=\begin{cases}|\mu-\nu|_{TV}=|\nu-\mu|&\text{if }\mu\leq\nu\\ +\infty&\text{elsewhere}\end{cases}. (87) Note, from the definition of ( 87 ), we can restrict the searching space for \gamma to \Gamma_{\leq}(\mu,\nu) : \displaystyle EFPGW(\mathbb{X},\mathbb{Y}) \displaystyle:=\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\mathcal{L}(\gamma)+\epsilon D_{KL}(\gamma^{\otimes 2}\parallel(\mu\otimes\nu)^{\otimes 2}) (88) \displaystyle\mathcal{L}(\gamma)=\omega_{1}\langle c,\gamma\rangle+\omega_{2}\langle|d_{X}-d_{Y}|^{2}\otimes\gamma^{\otimes 2}\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}) Problem ( 88 ) can be further relaxed as: \displaystyle\min_{\gamma,\pi\in\Gamma_{\leq}(\mu,\nu)}\mathcal{F}(\gamma,\pi)+\epsilon D_{KL}(\pi\otimes\gamma\parallel(\mu\otimes\nu)^{\otimes 2}) (89) \displaystyle\mathcal{F}(\mu,\nu):=\omega_{1}\langle d(x,y),\frac{\gamma+\pi}{2}\rangle+\omega_{2}\langle|d_{X}-d_{Y}|^{2},\gamma\otimes\pi\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma||\pi|) It is clear \mathcal{F}(\gamma,\gamma)=\mathcal{F}(\gamma) . Thus, (\ref{eq:entropy-fpgw-2})\leq(\ref{eq:entropy-fpgw}) , and we denote ( 89 ) as LB-FPGW_{\lambda}(\mathbb{X},\mathbb{Y}) (lower bound of Fused Partial Gromov Wasserstein). Essentially, the Sinkhorn algorithm aims to solve LB-FPGW . We first introduce the following fundamental proposition. Note, a similar version can be found in [ 20 , Proposition 4] : Proposition I.1 . Given a fixed \pi\in\Gamma_{\leq}(\mu,\nu) , considering the problem: \min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\mathcal{F}(\pi,\gamma)+\epsilon D_{KL}(\pi\otimes\gamma\parallel(\mu\otimes\nu)^{\otimes 2}), it is equivalent to solve the following entropic optimal partial transport problem: \displaystyle\min_{\gamma\in\Gamma_{\leq}(\mu,\nu)}\int_{X\times Y}c_{\pi}(x,y)d\gamma+\lambda|\pi|(|\mu|+|\nu|-2|\gamma|)+\epsilon|\pi|D_{KL}(\gamma\parallel\mu\otimes\nu) (90) where \displaystyle c_{\pi}(x,y) \displaystyle=\frac{1}{2}\omega_{1}d(x,y)+\omega_{2}[|d_{X}-d_{Y}|^{2}\circ\pi](x,y)+\epsilon\overline{D}_{KL}(\pi\parallel\mu\otimes\nu) \displaystyle[|d_{X}-d_{Y}|^{2}\circ\pi](x,y) \displaystyle=\int_{X\times Y}|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})|d\pi(x^{\prime},y^{\prime}) Proof. Fix \pi\in\Gamma_{\leq}(\mu,\nu) in ( 89 ). Since \pi,\gamma\leq\mu\otimes\nu , we have \pi,\gamma\ll\mu\otimes\nu , thus we have: \displaystyle D_{KL}(\pi\otimes\gamma\parallel(\mu\otimes\nu)^{\otimes 2}) \displaystyle=\int_{(X\times Y)^{2}}\ln(\frac{d\pi d\gamma}{d\mu\otimes\nu\cdot d\mu\otimes\nu})d\mu d\gamma+(|\mu||\nu|)^{2}-|\pi||\gamma| \displaystyle=\int_{X\times Y}\left[\int_{X\times Y}\ln(\frac{d\pi}{d\mu\otimes\nu})d\pi\right]d\gamma+\int_{X\times Y}\left[\int_{X\times Y}\ln(\frac{d\gamma}{d\mu\otimes\nu})d\gamma\right]d\pi+(|\mu||\nu|)^{2}-|\pi||\gamma| \displaystyle=\int_{X\times Y}d\pi\overline{D}_{KL}(\gamma\parallel\mu\otimes\nu)+\int_{X\times Y}d\gamma\overline{D}_{KL}(\pi\parallel\mu\otimes\nu)+(|\mu||\nu|)^{2}-|\pi||\gamma| \displaystyle=|\pi|D_{KL}(\gamma\parallel\mu\otimes\nu)+|\gamma|\overline{D}_{KL}(\pi\parallel\mu\otimes\nu)+((|\mu||\nu|)^{2}-|\pi||\mu||\nu|) (91) we obtain: \displaystyle\mathcal{F}(\pi,\gamma)+\epsilon D_{KL}(\gamma\times\pi\parallel(\mu\otimes\nu)^{\otimes 2}) \displaystyle=\omega_{1}\langle d,\frac{\gamma+\pi}{2}\rangle+\omega_{2}\langle|d_{X}-d_{Y}|^{2},\gamma\otimes\pi\rangle+\lambda(D_{PTV}(\gamma_{1}\otimes\pi_{1}\parallel\mu^{\otimes 2})+D_{PTV}(\gamma_{2}\otimes\mu_{2}\parallel\nu^{\otimes 2})) \displaystyle\quad+\epsilon D_{KL}(\gamma\times\pi\parallel(\mu\otimes\nu)^{\otimes 2}) \displaystyle=\omega_{1}\langle d,\frac{\gamma+\pi}{2}\rangle+\omega_{2}\langle|d_{X}-d_{Y}|^{2},\gamma\otimes\pi\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma||\pi|)+\epsilon D_{KL}(\gamma\times\pi\parallel(\mu\otimes\nu)^{\otimes 2}) \displaystyle=\underbrace{\frac{1}{2}\omega_{1}\langle d,\pi\rangle+\lambda(|\mu|^{2}+|\nu|^{2})+\epsilon[(|\mu||\nu|)^{2}-|\pi||\mu||\nu|]}_{constant} \displaystyle\quad+\langle\frac{1}{2}\omega_{1}d+\omega_{2}|d_{X}-d_{Y}|^{2}\circ\pi+\epsilon\overline{D}_{KL}(\pi\parallel\mu\otimes\nu),\gamma\rangle-2\lambda|\pi||\gamma|)+\epsilon|\pi|D_{KL}(\gamma\parallel\mu\otimes\nu) where we use the fact ( 91 ) and \displaystyle|\gamma|\epsilon\overline{D}_{KL}(\pi\parallel\mu\otimes\nu)=\langle\epsilon\overline{D}_{KL}(\pi\parallel\mu\otimes\nu),\gamma\rangle. If we ignore the constant part, the remaining part is exactly the entropic partial OT (up to a constant \lambda|\pi|(|\mu|+|\nu|) ), and we complete the proof. ∎ Note, the partial OT problem ( 90 ) can be solved by the classical Sinkhorn algorithm. See e.g. [ 57 , 58 ] . Algorithm 4 Sinkhorn Partial OT Input: c,\epsilon,\lambda,\mathrm{p},\mathrm{q} Output: \gamma 1 Initialize u=1_{n},v=1_{m} , K=e^{-c/\epsilon}pq^{\top} 2 for l=1,2,\ldots do 3 u=\min(\frac{\mathrm{p}}{Kv},e^{\lambda/\epsilon}) 4 v=\min(\frac{\mathrm{q}}{K^{\top}u},e^{\lambda/\epsilon}) 5 If (u,v) converge , break 6 \gamma\leftarrow(u_{i}K_{ij}v_{j})_{ij} I.2 Sinkhorn for the fused Mass-constraint Gromov Wasserstein problem. Similar to the preious section, in the entropic regularziation setting, the fused mass-constraint Gromov Wasserstein problem is defined as: \displaystyle EFMPGW(\mathbb{X},\mathbb{Y}):=\inf_{\gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\omega_{1}\langle c,\gamma\rangle+\omega_{2}\langle|d_{X}-d_{Y}|,\gamma^{\otimes 2}\rangle+\epsilon D_{KL}(\gamma^{\otimes 2}\parallel(\mu\otimes\nu)^{\otimes 2}) (92) and it can be relaxed as \displaystyle LB-EFMPGW(\mathbb{X},\mathbb{Y}) \displaystyle:=\inf_{\gamma,\pi\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\underbrace{\omega_{1}\langle c,\frac{1}{2}(\gamma+\pi)\rangle+\omega_{2}\langle|d_{X}-d_{Y}|,\gamma^{\otimes 2}\rangle}_{\mathcal{F}(\gamma,\pi)} \displaystyle\qquad+\epsilon D_{KL}(\gamma\otimes\pi\parallel(\mu\otimes\nu)^{\otimes 2}) (93) Note, since \frac{1}{2}(\gamma+\pi)\in\Gamma_{\leq}^{\rho}(\mu,\nu) , and \mathcal{F}(\gamma,\gamma)=\mathcal{F}(\gamma) , thus, we have LB-EFMPGW(\mathbb{X},\mathbb{Y})\leq EFMPGW(\mathbb{X},\mathbb{Y}). Similar to the previous section, we have the following property: Proposition I.2 . Given a fixed \pi\in\Gamma_{\leq}^{\rho}(\mu,\nu) , considering the problem: \min_{\gamma\in\mathcal{M}_{+}(X\times Y)}\mathcal{F}(\pi,\gamma)+\epsilon D_{KL}(\pi\otimes\gamma\parallel(\mu\otimes\nu)^{\otimes 2}), it is equivalent to solve the following entropic optimal partial transport problem: \displaystyle\min_{\gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)}\int_{X\times Y}c_{\pi}(x,y)d\gamma+\epsilon D_{KL}(\gamma\parallel\mu\otimes\nu) (94) where c_{\pi} is defined in Proposition I.1 . Proof. Similar to the proof in Proposition I.1 , given \pi\in\Gamma^{\rho}_{\leq}(\mu,\nu) , we have \displaystyle\mathcal{F}(\pi,\gamma)+\epsilon D_{KL}(\gamma\times\pi\parallel(\mu\otimes\nu)^{\otimes 2}) \displaystyle=\omega_{1}\langle d,\frac{\gamma+\pi}{2}\rangle+\omega_{2}\langle|d_{X}-d_{Y}|^{2},\gamma\otimes\pi\rangle+\epsilon D_{KL}(\gamma\times\pi\parallel(\mu\otimes\nu)^{\otimes 2}) \displaystyle=\underbrace{\frac{1}{2}\omega_{1}\langle d,\pi\rangle+\epsilon[(|\mu||\nu|)^{2}-|\pi||\mu||\nu|]}_{constant} \displaystyle\quad+\langle\underbrace{\frac{1}{2}\omega_{1}d+\omega_{2}|d_{X}-d_{Y}|^{2}\circ\pi+\epsilon\overline{D}_{KL}(\pi\parallel\mu\otimes\nu)}_{c_{\pi}},\gamma+\epsilon\underbrace{|\pi|}_{=\rho}D_{KL}(\gamma\parallel\mu\otimes\nu) and we complete the proof. ∎ The Entropic partial OT problem ( 94 ) can be solved by the corresponded Sinkhorn algorithm [ 59 , 58 ] , thus we can derive the Sinkhorn algorithm problem for the relaxed fused-mass constraint Gromov Wasserstein problem: Algorithm 5 Sinkhorn Algorithm for FMPGW Input: C\in\mathbb{R}^{n\times m},C^{X}\in\mathbb{R}^{n\times n},C^{Y}\in\mathbb{R}^{m\times m},p\in\mathbb{R}^{n}_{+},q\in\mathbb{R}^{m}_{+} , \omega_{2}\in[0,1],\rho\in[0,\min(|p|,|q|)] . Output: \gamma for k=1,2,\ldots do \pi\leftarrow\gamma Solve the Sinkhorn partial OT problem ( 94 ) via algorithm ( 6 ): \gamma\leftarrow\min_{\gamma\in\Gamma^{\rho}_{\leq}(\mu,\nu)}\int_{X\times Y}c_{\pi}(x,y)d\gamma+\epsilon\rho D_{KL}(\gamma\parallel\mu\otimes\nu) 5 Fix \gamma and solve the similar Sinkhorn partial OT problem ( 94 ) via algorithm ( 6 ): \pi\leftarrow\min_{\gamma\in\Gamma^{\rho}_{\leq}(\mu,\nu)}\int_{X\times Y}c_{\gamma}(x,y)d\pi+\epsilon\rho D_{KL}(\pi\parallel\mu\otimes\nu) Break if \pi\approx\gamma end for Algorithm 6 Sinkhorn Mass-constraint Partial OT Input: p,q,\rho,c Output: \gamma 1 Initialization 2 K=e^{-c/\epsilon}pq^{\top} 3 for i=1,2,3 do 4 \xi^{i}\leftarrow 1_{n\times m} 5 \gamma^{(0)}\leftarrow K\frac{\rho}{\|K\|} 6 Main loop 7 k=0 for l=0,1,2,\ldots do 8 for i=1,2,3 do 9 k\leftarrow k+1 10 \gamma^{(k)}\leftarrow\text{Proj}_{\mathcal{C}_{i}}^{KL}(\gamma^{(k-1)}\odot\xi^{i}) 11 \xi^{i}\leftarrow\xi^{i}\odot\frac{\gamma^{(k-1)}}{\gamma^{(k)}} 12 Break if \gamma^{(k)} converges where \displaystyle\mathcal{C}_{1} \displaystyle=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\gamma_{2}\leq q\} \displaystyle\mathcal{C}_{2} \displaystyle=\{\gamma\in\mathbb{R}_{+}^{n\times m}:\gamma_{1}\leq p\} \displaystyle\mathcal{C}_{3} \displaystyle=\{\gamma\in\mathbb{R}_{+}^{n\times m}:|\gamma|=\rho\} \displaystyle\text{Proj}_{\mathcal{C}_{i}}^{KL}(\gamma) \displaystyle:=\min_{\gamma^{i}\in\mathcal{C}_{i}}KL(\gamma^{i}\parallel\gamma)=\begin{cases}\text{diag}(\min(\frac{p}{\gamma_{2}},1_{n}))\gamma\\ \gamma\text{diag}(\min(\frac{q}{\gamma^{\top}1_{n}},1_{m}))\\ \gamma\frac{\eta}{\|\gamma\|}\end{cases} Appendix J Fused Partial Gromov Wasserstein Barycenter In discrete setting, suppose we have K mm-spaces \mathbb{X}^{k}=(X^{k}\subset\mathbb{R}^{d},d_{X^{k}},\mu^{k}:=\sum_{i=1}^{n^{k}}p^{k}_{i}\delta_{x_{i}^{k}}) for k=1,\ldots,K and a fixed pmf function p\in\mathbb{R}_{+}^{n} where n\in\mathbb{N} . Note for each k\in[1:K] , let C^{k}=[d^{r}_{X^{k}}(x^{k}_{i},x^{k}_{i^{\prime}})]_{i,i^{\prime}\in[1:n^{k}]}\in\mathbb{R}^{n^{k}\times n^{k}} and let X^{k}=[x^{k}_{1},\ldots x^{k}_{n^{k}}]^{\top}\in\mathbb{R}^{n_{k}\times d} , we have (X^{k},\mathrm{p}^{k},C^{k}) can represent the space \mathbb{X}^{k} . Thus, for convenience, we use the convention \mathbb{X}^{k}=(X^{k},p^{k},C^{k}) to denote the corresponsded mm-space. Then, given pmf function \mathrm{p}\in\mathbb{R}_{+}^{n} where n\in\mathbb{N} , and \beta_{1},\ldots\beta_{K}\geq 0 with \sum_{k=1}^{K}\beta_{k}=1 , the fused-Gromov Wasserstein barycenter problem [ 30 ] is defined as: \displaystyle\min_{C\in\mathbb{R}^{n\times n},X\in\mathbb{R}^{n\times d}}\beta_{i}FGW_{L}(\mathbb{X},\mathbb{X}^{k}), \displaystyle\text{ where }\mathbb{X}=(X,\mathrm{p},C), (95) where we adapt notation FGW_{L}(\cdot,\cdot) to simplify the notation FGW_{r,L}(\cdot,\cdot) since r has been incorporated into matrix C^{k} . Inspired by this work, we present the following fused Partial GW barycenter problems. J.1 Fused-MPGW barycenter. Choose values \rho_{1},\rho_{2},\ldots,\rho_{K} where \rho_{k}\in[0,\min(|p|,|p^{k}|)] for each k . In addition, choose (\omega_{1}^{k},\omega_{2}^{k})\in[0,1] for k=1,2,\ldots K such that \omega_{1}^{k}+\omega_{2}^{k}=1,\forall k . The fused mass-constrained Partial GW barycenter problem is defined as: \displaystyle\min_{C\in\mathbb{R}^{n\times n},X\in\mathbb{R}^{n\times d}}\sum_{k=1}^{K}\beta_{k}FMPGW_{L,\rho_{k}}(\mathbb{X},\mathbb{X}^{k}), \displaystyle=\min_{\begin{subarray}{c}C\in\mathbb{R}^{n\times n}\\ X\in\mathbb{R}^{n\times d}\end{subarray}}\min_{\begin{subarray}{c}\gamma^{k}\in\Gamma^{\rho_{k}}_{\leq}(p,p^{k})\\ k\in[1:K]\end{subarray}}\sum_{k=1}^{K}\beta_{k}\left(\omega_{1}^{k}\langle D(X,X^{k}),\gamma^{k}\rangle+\omega_{2}^{k}\langle L(C,C^{k})(\gamma^{k})^{\otimes 2}\rangle\right), (96) where \mathbb{X}=(X,p,C) , \mathbb{X}^{k}=(X^{k},p^{k},C^{k}) , and D(X,X^{K})=[\|x_{i}-x^{k}_{j}\|^{2}]_{i\in[1:n],j\in[1:n^{k}]}\in\mathbb{R}^{n\times n_{k}} . Note that the above problem is convex with respect to (C,X) when \gamma^{k} is fixed for each k . However, it is not convex with respect to \gamma^{k} for each k . Similar to classical fused-GW, it can be solved iteratively by updating (C,X) and (\gamma^{k})_{k=1}^{K} alternatively in each iteration. Step 1. Given (C,X) , we update (\gamma^{k})_{k=1}^{K} . Note, when (C,X) is fixed, each optimal (\gamma^{k})^{*} is given by \displaystyle(\gamma^{k})^{*}=\arg\min_{\gamma^{k}\in\Gamma_{\leq}^{\rho_{k}}(p,p^{k})}\omega_{1}^{k}\langle D(X,X^{k}),\gamma^{k}\rangle+\omega_{2}^{k}\langle L(C,C^{k}),(\gamma^{k})^{\otimes 2}\rangle, which is a solution for the fused partial GW problem F-MPGW_{\rho^{k}}(\mathbb{X},\mathbb{X}^{k}) . Step 2. Given \gamma^{k} , update (C,X) . Suppose \gamma^{k} is given for each k , the objective function in ( 95 ) becomes: \displaystyle\min_{C\in\mathbb{R}^{n\times n},X\in\mathbb{R}^{n\times d}}\sum_{k=1}^{K}\beta_{k}\left(\omega_{1}\langle D(X,X^{k}),\gamma^{k}\rangle+\omega_{2}\langle L(C,C^{k}),(\gamma^{k})^{\otimes 2}\rangle\right) \displaystyle=\omega_{1}\underbrace{\min_{X\in\mathbb{R}^{n\times d}}\sum_{k=1}^{K}\beta_{k}\langle D(X,X^{k}),\gamma^{k}\rangle}_{A}+\omega_{2}\underbrace{\min_{C\in\mathbb{R}^{n\times n}}\sum_{k=1}^{K}\beta_{k}\langle L(C,C^{k}),(\gamma^{k})^{\otimes 2}\rangle}_{B}. Problem B admits the solution (we refer [ 28 ] Section M for details). In particular, if L satisfies ( 60 ), f_{1},h_{1} are differentiable, then \displaystyle C=\left(\frac{f_{1}^{\prime}}{h_{1}^{\prime}}\right)^{-1}\left(\frac{\sum_{k}\xi_{k}\gamma^{k}h_{2}(C^{k})(\gamma^{k})^{\top}}{\sum_{k}\xi_{k}\gamma_{1}^{k}(\gamma_{1}^{k})^{\top}}\right). (97) In particular, when L(\mathrm{r}_{1},\mathrm{r}_{2})=|\mathrm{r}_{1}-\mathrm{r}_{2}|^{2} , the above formula becomes: \displaystyle C=\frac{\sum_{k}\xi_{k}\gamma^{k}C^{k}(\gamma^{k})^{\top}}{\sum_{k}\xi_{k}\gamma_{1}^{k}(\gamma_{1}^{k})^{\top}}. J.2 Solving the subproblem A. We first introduce the barycentric projection: For each (X^{k},p^{k},\gamma^{k}) , the barycentric projection [ 12 ] is defined by \displaystyle\hat{x}^{k}_{i}=\begin{cases}\frac{1}{\gamma^{k}_{1}[i]}\sum_{j=1}^{n_{k}}\gamma^{k}_{i,j}x^{k}_{j}&\text{if }\gamma_{1}^{k}[i]=\sum_{j=1}^{n_{k}}\gamma_{i,j}^{k}>0,\\ x_{i}&\text{elsewhere}.\end{cases} (98) Note, if |\gamma^{k}|=|p|,\forall k , by [ 34 ] ( Eq 8), the optimal X is given by X=[x_{1},\ldots x_{n}]^{\top},x_{i}=\sum_{k=1}^{K}\beta_{k}\hat{x}_{i}^{k},\forall i\in[1:n]. In this subsection, we will extend the above result to the general case. Proposition J.1 . Any matric X satisfies the following is a solution for problem A . \displaystyle X=[x_{1},\ldots,x_{n}]^{\top},x_{i}=\frac{\sum_{k=1}^{K}\beta_{k}\hat{x}_{i}^{k}}{\sum_{k=1}^{K}\beta_{i}\gamma^{k}_{1}[i]}\qquad\text{if }\sum_{k=1}^{K}\beta_{i}\gamma_{1}^{k}[i]>0. (99) Note, for each i , we use convention \frac{0}{0}=0 if \sum_{k=1}^{K}\beta_{i}\gamma_{1}^{k}[i]=0 . Proof. Problem A can be written in terms of barycentric projection ( 98 ). In particular, let \mathcal{D}_{k}:=\{i:\sum_{i,j}\gamma^{k}_{i,j}>0\} and \mathcal{D}=\bigcup_{k=1}^{K}\mathcal{D}_{k} . We have: \displaystyle A \displaystyle=\min_{X\in\mathbb{R}^{n\times d}}\sum_{k=1}^{K}\beta_{k}\sum_{i=1}^{n}\gamma_{1}^{k}[i](\|x_{i}-\hat{x}_{i}^{k}\|^{2}) \displaystyle=\min_{X\in\mathbb{R}^{n\times d}}\sum_{i=1}^{n}\sum_{k=1}^{K}\beta_{k}\gamma_{1}^{k}[i](\|x_{i}-\hat{x}_{i}^{k}\|^{2}) \displaystyle=\sum_{i=1}^{n}\min_{x_{i}\in\mathbb{R}^{d}}\sum_{k=1}^{K}\beta_{k}\gamma_{1}^{k}[i](\|x_{i}-\hat{x}_{i}^{k}\|^{2}). For each i , we have two cases: Case 1: \sum_{k=1}^{K}\beta_{k}\gamma_{1}^{k}[i]>0 . Then optimal x_{i} is given by the weighted average vector: \frac{\sum_{k\in D_{i}}\beta_{k}\gamma_{1}^{k}[i]\hat{x}^{k}_{i}}{\sum_{i\in D_{k}}\beta_{k}\gamma^{k}_{1}[i]}. Case 2: \sum_{k=1}^{K}\beta_{k}\gamma_{1}^{k}[i]=0 . The problem becomes \min_{x_{i}\in\mathbb{R}^{d}}0, and there is no requirement for x_{i} . And we complete the proof. ∎ Remark J.2 . In practice, the above formulation can be described by matrices. In particular, let \hat{X}^{k}=[\hat{x}^{k}_{1},\ldots\hat{x}^{k}_{n}]^{\top} , we have \hat{X}^{k}=\frac{\gamma^{k}X^{k}}{\gamma^{k}_{1}},\gamma^{k}_{1}=\gamma^{k}1_{m}. Then we have ( 99 ) becomes X=\frac{\sum_{k=1}^{K}\beta_{k}\gamma_{1}^{k}1_{d}^{\top}\odot\hat{X}}{\sum_{k=1}^{K}\beta_{k}\gamma_{1}^{k}}, where \odot denotes the element-wise multiplication; the notation \frac{A}{B} where A\in\mathbb{R}^{n\times d},B\in\mathbb{R}^{n} denotes the following \frac{A}{B}=[A[:,1]/B_{1},\ldots,A[:,n]/B_{n}]^{\top}, and we use \frac{0}{0}=0 if any element in the denominator is 0. J.3 Fused-PGW barycenter Similar to the previous subsection, we define and derive the solution for the fused-Partial GW problem. Given \lambda_{1},\ldots\lambda_{K}\geq 0,p\in\mathbb{R}_{+}^{n} , the fused partial GW barycenter problem is defined as: \displaystyle\min_{C\in\mathbb{R}^{n\times n},X\in\mathbb{R}^{n\times d}}\sum_{k=1}^{K}\beta_{k}FPGW_{L,\lambda_{i}}(\mathbb{X},\mathbb{X}^{k}),\text{where }\mathbb{X}=(X,p,C) \displaystyle=\min_{C\in\mathbb{R}^{n\times n},X\in\mathbb{R}^{n\times d}}\min_{\gamma^{k}\in\Gamma_{\leq}(p,p^{k}):k\in[1:K]}\sum_{k=1}^{K}\omega_{1}^{k}\langle D(X,X^{k}),\gamma^{k}\rangle \displaystyle\qquad+\omega_{2}^{k}\langle L(C,C^{k}),(\gamma^{k})^{\otimes 2}\rangle+\lambda_{k}(|p^{k}|^{2}+|p|^{2}-2|\gamma^{k}|^{2}). (100) Similar to the fused MPGW barycenter problem, the above problem can be solved iteratively. In each iteration, we have two steps: Step 1. Given X,D , update \gamma^{k} . Note finding each \gamma^{k} is essentially solving the fused-PGW problem: \displaystyle\gamma^{k}=\arg\min_{\gamma\in\Gamma_{\leq}(p,p^{k})}\omega_{1}^{k}\langle D(X,X^{k}),\gamma\rangle+\omega_{2}^{k}\langle L(C,C^{k}),(\gamma^{\otimes 2})\rangle+\lambda_{k}(|p^{k}|^{2}+|p|^{2}-2|\gamma^{k}|^{2}) And it can be solved by algorithm 1 . Step 2. Given \gamma^{k}:k\in[1:K] , update C,X . In this case, ( 100 ) becomes \displaystyle\omega_{2}^{k}\underbrace{\min_{C\times\mathbb{R}^{n\times n}}\langle L(C,C^{k})-2\lambda_{k},(\gamma^{k})^{\otimes 2}\rangle}_{A}+\omega_{1}^{k}\underbrace{\min_{X\in\mathbb{R}^{n\times d}}\langle D(X,X^{k}),\gamma^{k}\rangle}_{B}. (101) Optimal C for subproblem A is ( 97 ) by [Proposition M.2 [ 28 ] ]. Optimal X for subproblem B is given by ( 99 ) by the Proposition J.1 . Appendix K Relation between FGW, FPGW and FMPGW. In this section, we briefly discuss the relation between FGW, Fused-PGW problem ( 11 ), and the fused-MPGW ( 10 ). First, we introduce the following “equivalent relation” between FPGW and FMPGW. It can be treated as the generalization of Proposition L.1. in [ 28 ] in the fused-PGW formulation. Proposition K.1 . Given mm-spaces \mathbb{X}=(X,d_{X},\mu),\mathbb{Y}=(Y,d_{Y},\nu) , r\geq 1,\lambda>0 . Suppose \gamma^{*} is a minimizer for FPGW problem FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) , then \gamma^{*} is also a minimizer for Fused-MPGW problem FPGW_{r,L,\rho}(\mathbb{X},\mathbb{Y}) where \rho=|\gamma^{*}| . Proof. Pick \gamma\in\Gamma_{\leq}^{\rho}(\mu,\nu)\subset\Gamma_{\leq}(\mu,\nu) . Since \gamma^{*} is optimal for FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) , we have: \displaystyle\omega_{1}\langle C,\gamma^{*}\rangle+\omega_{2}\langle L,(\gamma^{*})^{\otimes 2}\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma^{*}|^{2}) \displaystyle\leq\omega_{1}\langle C,\gamma\rangle+\omega_{2}\langle L,\gamma^{\otimes 2}\rangle+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}). Combine it with the fact |\gamma|=|\gamma^{*}|=\rho , we complete the proof. ∎ Next, we discuss the relation between FGW and FMPGW problems. Proposition K.2 . Under the setting of Proposition K.1 , suppose |\mu|=|\nu| , then FMPGW_{r,L,\rho}(\mathbb{X},\mathbb{Y})=FGW_{r,L,\rho}(\mathbb{X},\mathbb{Y}). Proof. In this case, \Gamma_{\leq}^{\rho}(\mu,\nu)=\Gamma(\mu,\nu) and we complete the proof. ∎ Similarly, in the extreme case, the FPGW problem can also recover the FGW problem. We first introduce the following lemma: Lemma K.3 . Suppose \mu,\nu are supported in compact set and |\mu|,|\nu|>0 . Let X=\text{supp}(\mu),Y=\text{supp}(\nu) , and \max L(d_{X}^{r},d_{Y}^{r}):=\max_{x,x^{\prime}\in X,y,y^{\prime}\in Y}L(d_{X}^{r}(x,x^{\prime}),d_{Y}^{r}(y,y^{\prime})),\max C:=\max_{x\in X,y\in Y}C(x,y) . Suppose \displaystyle 2\lambda\geq\omega_{1}\frac{1}{\min(|\mu|,|\nu|)}\max(C)+\omega_{2}\max L(d_{X}^{r},d_{Y}^{r}) (102) there exists a solution, denoted as \gamma^{*} , for FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) such that \displaystyle|\gamma^{*}|=\min(|\mu|,|\nu|). (103) If we replace “ \geq ” by “ > ” in the inequality (\ref{eq:big_lambda_cond}) , then every solution of FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{T}) satisfies (\ref{eq:big_lambda_res}) . Proof. For convenience, we suppose |\mu|\leq|\nu| . Suppose ( 102 ) holds. Choose an optimal \gamma\in\Gamma_{\leq}(\mu,\nu) . By lemma E.1. in [ 28 ] , there exists \gamma^{\prime}\in\Gamma_{\leq}(\mu,\nu) such that \gamma\leq\gamma^{\prime} with |\gamma^{\prime}|=|\mu| , i.e. \gamma^{\prime}_{1}=\mu . We have: \displaystyle\int_{X\times Y}\omega_{1}C(x,y)d\gamma^{\prime}+\int_{(X\times Y)^{2}}\omega_{2}L(d_{X}^{r},d_{Y}^{r})d\gamma^{\prime\otimes 2}+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma^{\prime}|^{2}) \displaystyle-\int_{X\times Y}\omega_{1}C(x,y)d\gamma+\int_{(X\times Y)^{2}}\omega_{2}L(d_{X}^{r},d_{Y}^{r})d\gamma^{\otimes 2}+\lambda(|\mu|^{2}+|\nu|^{2}-2|\gamma|^{2}) \displaystyle=\int_{X\times Y}\omega_{1}C(x,y)d(\gamma^{\prime}-\gamma)+\int_{(X\times Y)^{2}}\omega_{2}L(d_{X}^{r},d_{Y}^{r})-2\lambda d(\gamma^{\prime\otimes 2}-\gamma^{\otimes 2}) \displaystyle\leq\omega_{1}\max(C)|\gamma^{\prime}-\gamma|+\omega_{2}(\max(L(d_{X}^{r},d_{Y}^{r}))-2\lambda)|\gamma^{\prime\otimes 2}-\gamma^{\otimes 2}| \displaystyle=\underbrace{\left(\omega_{1}\frac{\max(C)}{|\gamma+\gamma^{\prime}|}+\omega_{2}\max(L(d_{X}^{r},d_{Y}^{r}))-2\lambda\right)}_{A}\underbrace{|\gamma^{\prime\otimes 2}-\gamma^{\otimes 2}|}_{B} \displaystyle\leq 0, (104) where ( 104 ) follows by the fact A\leq 0,B\geq 0 . Thus we have \gamma^{\prime} is optimal. Now we suppose 2\lambda>\omega_{1}\frac{1}{\min(|\mu|,|\nu|)}\max(C)+\omega_{2}\max L(d_{X}^{r},d_{Y}^{r}). We assume there exists an optimal \gamma such that |\gamma|<|\mu| . If we can find optimal \gamma with |\gamma|<|\mu| , then A<0 and B>0 and we have (\ref{pf:gamma'_optimal})<0 . That is, \gamma^{\prime} admits a smaller cost. It is a contradiction since \gamma is optimal, and we complete the proof. ∎ Remark K.4 . If \min(|\mu|,|\nu|)=0 , \Gamma_{\leq}(\mu,\nu)=\{\mathbf{0}\} where \{\mathbf{0}\} is the zero measure. In this case, ( 103 ) is automatically satisfied, and there is no requirement for \lambda . Based on this lemma, the FPGW can recover FGW in the extreme case: Proposition K.5 . Under the setting of Proposition K.2 , suppose \lambda satisfies ( 102 ), then FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y})=FGW_{r,L}(\mathbb{X},\mathbb{Y}). Proof. By Lemma K.3 , there exists optimal \gamma for FPGW_{r,L,\lambda}(\mathbb{X},\mathbb{Y}) with |\gamma|=|\mu|=|\nu| . By Proposition K.1 , we have \gamma is optimal for FMPGW_{r,L,\rho}(\mathbb{X},\mathbb{Y}) where \rho=|\mu|=|\nu| . By Proposition K.2 , we have \gamma is optimal for FGW_{r,L}(\mathbb{X},\mathbb{Y}) . Thus, \gamma and we complete the proof. ∎ Appendix L Measure graph similarity via Fused GW/PGW. In the following, we discuss how to model graphs as mm-spaces. Based on this modeling, fused-GW and fused-PGW can be adapted to measure graph similarity. Given graphs G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) , where V_{1},V_{2} are sets of vertices (nodes) and E_{1},E_{2} are sets of edges. First, consider G_{1} . Suppose V_{1}=\{v_{1}^{1},\ldots,v^{1}_{N_{1}}\} . We construct the mm-space \mathbb{X}_{1}=(V_{1},d_{V_{1}},\mu^{1}=\sum_{i=1}^{N_{1}}\mathrm{p}_{i}^{1}\delta_{v_{i}}) , where \mathrm{p}_{i}^{1}>0 for all i . Let \mathrm{p}^{1}=[p_{1}^{1},\ldots,p_{N_{1}}^{1}] . Note that when \sum(\mathrm{p}^{1})=1 , \mathrm{p}^{1} represents the probability mass function (pmf) of the measure \mu^{1} . For general cases, we refer to \mathrm{p}^{1} as the mass function (mf) of \mu^{1} . In this formulation, the function d_{V_{1}}:V_{1}^{2}\to\mathbb{R} can be defined as follows: – Adjacency indicator function: d_{V_{1}}(v_{1},v_{2})=1 if (v_{1},v_{2})\in E_{1} , and d_{V_{1}}(v_{1},v_{2})=0 otherwise. – Shortest distance function: d_{V_{1}}(v_{1},v_{2}) is the length of the shortest path connecting v_{1} and v_{2} if such a path exists, or \infty if v_{1} and v_{2} are not connected. Let \mathcal{F} denote the space of feature assignments for all nodes. We define a feature function f:V\to\mathcal{F} such that x_{i}=f(v_{i}) represents the feature of the vertex v_{i} . For convenience, when the graph has discrete features, \mathcal{F} is a discrete set; when the graph has continuous features, \mathcal{F}=\mathbb{R}^{d} , where d is the dimension of each feature. In both cases, we define a metric d_{\mathcal{F}} in the feature space. The feature similarity function d_{\mathcal{F}} is set as follows: – Continuous feature graph: Since \mathcal{F}=\mathbb{R}^{d} , we define d_{\mathcal{F}} as the (squared) Euclidean distance in \mathbb{R}^{d} . – Discrete feature graph: We first apply the Weisfeiler-Lehman kernel [ 47 ] , which encode elements in feature space as \text{wl}:\mathcal{F}\to S^{H} , where S is finite discrete set, H\in\mathbb{N} , typically set to 2 or 4 . We then use the Hamming distance in S^{\mathrm{h}} as d_{\mathcal{F}} . For details, refer to Section 4.2 of [ 24 ] . Appendix M Rapameter Setting in Graph Matching and Geometry Matching Experiments We present the detailed parameter settings for the graph and geometry matching experiments in this section. First, consider the graph node distribution settings \mu=\sum_{i=1}^{n}p_{i}\delta_{v_{i}^{q}},\quad\nu=\sum_{j=1}^{m}q_{j}\delta_{v_{j}^{o}}, where \mu denotes the node distribution of the query graph and \nu denotes the node distribution of the original graph. For unbalanced GW methods, SpecGW (Spectral Gromov–Wasserstein [ 40 ] ), eBPG (Entropic Bregman Projected Gradient [ 41 ] ), BPG (Bregman Projected Gradient [ 42 ] ), BAPG (Bregman Alternating Projected Gradient [ 43 ] ), and srGW (Semi-relaxed Gromov–Wasserstein [ 44 ] ), we follow their default settings \displaystyle p_{i}=\tfrac{1}{n},\quad q_{j}=\tfrac{1}{m}. (105) For PGW (Partial Gromov–Wasserstein [ 21 , 28 ] ), UGW (Unbalanced Gromov–Wasserstein [ 20 ] ), RGW (Outlier Robust Gromov–Wasserstein [ 23 ] ), FUGW (Fused Unbalanced Gromov–Wasserstein [ 26 ] ), and Sink-FUPGW (Sinkhorn Fused Partial Gromov–Wasserstein, ours), in addition to the above balanced setting, we alternatively consider the unbalanced setting: \displaystyle p_{i}=q_{j}=\tfrac{1}{\min(n,m)}=\tfrac{1}{n}. (106) And select the best option for each method. Other parameter settings are summarized in Tables 2 and 3 . In particular, in Spectral GW, time is the time limit of the heat kernel. In methods: eBPG, BPG, BAPG, srGW, UGW, FUGW, RGW, and sink-FPGW, \epsilon is the weight of the entropic regularization term. In BAPG, \rho is the weight of the Bregman divergence penalty. In PGW, “ mass ” is the mass constraint. In UGW, FUGW, sink-FPGW \rho is the weight of marginal regularization terms. In FPGW, \lambda is the weight of marginal regularization terms. In the fused methods (FGW, FUGW, sink-FPGW), \alpha denotes the balance among graph structure and node features. In RGW, \rho is the hard marginal constraint, \eta is the weight of the marginal constraint (soft constraint), t are the stepsizes in Bregman proximal alternating linearized minimization (BPALM). Other settings in geometry matching. In geometric matching, we only consider unbalanced GW methods (RGW, FUGW, FPGW), since UGW and PGW can be regarded as special cases of FUGW and FPGW and are therefore not included separately. We adopt the unbalanced mass function setting in ( 106 ). In this experiment, we further assume that a fixed pair of points from the ground-truth correspondence is known, denoted by (x_{0}^{q},x_{0}^{o}) , where the first point belongs to the query shape and the second to the original shape. For each point x in the query shape, its feature is defined as d(x,x_{0}^{q}) , where d is the Euclidean distance on the shape. Features of points in the original shape are defined analogously. Table 2 : The parameter settings in all the methods. Datasets with node attributes include Synthetic, Enzymes, Cuneiform, COX2, BZR, Protein and AIDS. parameter Dataset with node attributes Douban SpecGW time 10 10 eBPG \epsilon 0.1 0.01 BPG \epsilon 0.2 0.01 BAPG \rho 0.1 0.01 \epsilon 1e-6 1e-6 srGW \epsilon 2.0 10 PGW mass \min(|p|,|q|) \min(|p|,|q|) UGW \epsilon 0.01 1e-3 \rho 0.05 1.0 RGW \rho 0.05/0.1 0.1 \epsilon 0.05 1e-3 t 0.1 0.1 \tau 0.1 0.1 FGW \alpha 0.5 0.5 FUGW \alpha 0.5 0.5 \epsilon 0.01 2e-4 \rho 1.0 1.0 sink-FPGW(ours) \alpha 0.33 0.5 \epsilon 0.02 1e-4 \lambda 1.0 1.0 Table 3 : Parameter setting of all the methods in geometry matching. parameter Upper Body Lower Body RGW \rho 0.1 0.1 \epsilon 1e-3 1e-3 t 0.1 0.1 \tau 0.1 0.1 FUGW \alpha 0.5 0.5 \epsilon 0.005 0.1 \rho 1.0 1.0 sink-FPGW(ours) \alpha 0.5 0.5 \epsilon 1e-3 1e-4 \lambda 1.0 1.0 Appendix N Graph Classification Dataset Setup. We consider four widely used benchmark datasets, divided into two groups. The first group includes Mutag [ 60 ] and MSRC-9 [ 61 ] , which consist of graphs with discrete attributes. The second group consists of vector-attributed graphs, including Synthetic [ 35 ] , Cuneiform [ 37 ] , and Proteins [ 36 ] . For each dataset, we randomly select 50\% of the graphs and add outlier nodes. Specifically, for each selected graph, suppose N is the number of vertices. We manually add \eta N extra nodes, where \eta\in\{0,10\%,20\%,30\%\} represents the “level of outliers/noise”. For clarity, nodes that are not outliers are referred to as “regular nodes”. The outlier nodes are randomly connected to both the regular nodes and each other. The features of the outlier nodes are defined as follows: – For graphs with discrete features, each outlier node is assigned a label that does not occur among the regular nodes in the graph. – For graphs with continuous features, suppose all features lie within a compact set [x_{1},y_{1}]\times\ldots\times[x_{d},y_{d}]\subset\mathbb{R}^{d} , where d\in\mathbb{N} is the dimension of the feature space. We assign features to the outlier nodes by sampling vectors from [y_{1},y_{1}+2\text{sd}_{1}]\times\ldots\times[y_{d},y_{d}+2\text{sd}_{d}] , where \text{sd}_{i} is the standard deviation of all node features in dimension i . Furthermore, for each graph G , let N_{G} denote the number of regular nodes (i.e., nodes that are not outliers). We assume N_{G} is known. Figure 5 : We visualize the graph classification data in this plot. The parameter \eta\in\{0,10\%,20\%,30\%\} represents the proportion of outlier nodes. The blue nodes are the regular nodes in the graph, and the pink nodes are the outliers. Fused Gromov/Unbalanced Gromov/Partial Gromov Setting. We adapt the process in section L to model each graph G as a mm-space. In particular, in the FGW setting, we define the (probability) mass function \mathrm{p} as \mathrm{p}_{i}=\frac{1}{N} , where N is the number of nodes in graph G . In the FUGW/FPGW setting, we define the mass function \mathrm{p} as \mathrm{p}_{i}=\frac{1}{N_{G}} , where N_{G} is the number of regular nodes in G . For the distance functions d_{V_{1}} and d_{V_{2}} in graphs G_{1} and G_{2} , we use the “shortest path” metric in this experiment. We select FMPGW ( 10 ) and set the parameter \rho=1 . Baseline methods. We consider the fused Gromov Wasserstein [ 24 ] and the Unbalanced fused Gromov Wasserstein [ 26 ] as baselines for both discrete and continuous feature graph datasets. In addition, for discrete feature graph datasets, we add the Weisfeler Lehman kernel (WLK) [ 47 ] ,Graphlet count kernel (GK) [ 62 ] , random walk kernel (RWK) [ 63 ] , ODD-STh Kernel (ODD) [ 64 ] , vertex histogram (VH) [ 65 ] , Lovasz Theta (LT) [ 66 ] , SVM theta (ST) [ 67 ] as baselines methods. For the continuous feature graphs dataset, we also consider the HOPPER kernel [ 35 ] and the propagation kernel Neumann [ 68 ] . Classifier setup. We adapt the SVM classification model in this experiment. In particular, given a graph dataset, we first compute the pairwise distance via FGW/(other baselines)/FPGW. By using the approach given by [ 69 , 53 ] , we combine each distance with a support vector machine (SVM), applying stratified 10-fold cross-validation. In each iteration of cross-validation, we train an SVM using \exp(-\sigma D) as the kernel, where D is the matrix of pairwise distances (w.r.t. one of the considered distances) restricted to 9 folds, and compute the accuracy of the model on the remaining fold. We report the accuracy averaged over all 10 folds for each model. Table 4 : Kernel accuracy (%) with standard deviation under different noise levels (0%, 10%, 20%, 30%). Top: results for discrete node features. Bottom: results for continuous node features. MSRC-9 MUTAG 0\% 10\% 20\% 30\% 0\% 10\% 20\% 30\% WLK 85.5 ±5.9 86.5 ±5.2 86.9 ±4.7 86.0 ±3.7 75.0 ±6.3 73.4 ±6.7 72.4 ±7.0 73.5 ±7.8 GK 15.8 ±4.5 15.4 ±3.7 14.9 ±6.2 17.7 ±8.0 77.1 ±6.3 70.2 ±2.6 70.2 ±4.4 67.0 ±6.6 RWK 74.7 ±5.8 73.8 ±6.6 74.7 ±7.4 74.2 ±4.1 66.5 ±2.3 66.5 ±2.3 66.5 ±2.3 66.5 ±2.3 ODD 67.9 ±6.5 69.2 ±7.6 64.7 ±8.2 63.8 ±9.0 64.9 ±4.0 64.9 ±4.0 64.9 ±4.0 64.9 ±4.0 VH 86.4 ±4.0 86.9 ±4.2 87.8 ±4.5 87.8 ±4.0 66.5 ±2.3 66.5 ±2.3 66.5 ±2.3 66.5 ±2.3 LT 15.8 ±5.0 13.1 ±4.3 13.1 ±5.1 14.5 ±4.5 69.7 ±3.9 68.1 ±2.5 66.5 ±2.3 68.6 ±8.5 ST 13.6 ±0.2 13.6 ±0.2 13.6 ±0.2 13.6 ±0.2 75.0 ±2.7 72.9 ±3.7 72.3 ±3.9 72.3 ±3.9 RGW 79.7 ±0.1 76.1 ±0.1 59.8 ±0.1 60.2 ±0.1 81.8 ±0.1 80.3 ±0.1 77.7 ±0.1 76.1 ±0.0 FGW 87.4 ±4.4 86.9 ±4.7 63.8 ±5.8 62.0 ±5.0 85.6 ±5.6 83.5 ±5.7 79.8 ±6.5 76.6 ±6.8 FUGW 73.8 ±6.1 68.3 ±4.9 5.0 ±3.7 5.4 ±4.4 82.4 ±5.5 81.9 ±5.6 81.9 ±6.1 80.3 ±6.0 FPGW (ours) 87.0 ±4.7 88.3 ±4.1 87.3 ±4.4 86.9 ±4.7 85.6 ±5.6 85.1 ±5.9 84.6 ±5.6 82.5 ±6.3 PROTEINS SYNTHETIC 0\% 10\% 20\% 30\% 0\% 10\% 20\% 30\% Propagation 59.6 ±0.2 59.6 ±0.2 59.6 ±0.2 59.6 ±0.2 48.0 ±7.0 51.3 ±6.5 47.3 ±5.5 53.0 ±6.1 GraphHopper 69.7 ±3.8 68.2 ±4.8 67.3 ±3.5 67.2 ±4.7 86.0 ±5.3 78.7 ±9.5 70.3 ±7.1 70.7 ±10.7 RGW 59.6 ±0.0 47.3 ±0.1 44.7 ±0.1 51.4 ±0.1 46.0 ±0.1 50.0 ±0.0 50.0 ±0.0 49.7 ±0.0 FGW 72.0 ±3.7 68.5 ±3.1 65.3 ±4.4 65.8 ±4.4 97.7 ±4.0 95.7 ±2.9 48.7 ±1.6 49.3 ±0.7 FUGW 70.6 ±3.7 69.7 ±2.7 69.0 ±3.3 68.7 ±2.4 60.0 ±6.1 48.3 ±6.7 45.3 ±4.5 45.3 ±4.5 FPGW (ours) 72.0 ±3.7 71.6 ±4.0 71.2 ±4.9 69.2 ±5.5 97.7 ±4.0 96.3 ±3.1 97.7 ±4.0 94.3 ±4.5 Performance Analysis. The accuracy comparison is summarized in Table 4 . For discrete feature graph datasets, VH, FGW, and FPGW achieve the highest overall accuracy. However, as the noise level \eta increases, FGW’s performance noticeably deteriorates, while the other three methods remain robust against outlier corruption. In contrast, for continuous datasets such as Proteins and Synthetic , the baseline methods, including “Propagation,” “GraphHopper,” and “FGW,” experience a significant drop in performance. Notably, FPGW maintains strong performance across these datasets. Regarding FUGW, its performance on the Mutag/Proteins datasets is comparable to that of FPGW. However, on the SCRC/Synthetic datasets, FUGW’s accuracy is significantly lower than that of FGW and FPGW. We refer to Section N.1 for the parameter settings and wall-clock time comparison. In summary, focusing on the comparison between FGW, FUGW, and FPGW, FGW is slightly faster than FPGW, while both FGW and FPGW are significantly faster than FUGW. Table 5 : Kernel computation times (minutes) across different datasets and noise levels Method 0% 10% 20% 30% SYNTHETIC Propagation 0.01 0.02 0.01 0.02 GraphHopper 5.69 5.11 5.32 8.31 RGW 4.3 4.5 4.7 5.1 FGW 7.20 13.23 16.80 22.81 FUGW 41.00 40.53 35.32 37.88 FPGW 13.23 14.66 17.03 19.44 PROTEINS Propagation 0.02 0.02 0.02 0.03 GraphHopper 7.06 7.43 7.79 8.16 RGW 844.7 804.1 766.8 713.2 FGW 26.05 28.71 29.83 30.17 FUGW 96.78 186.93 204.20 220.96 FPGW 62.03 65.99 71.54 73.19 MSRC WLK (auto) 0.00 0.00 0.00 0.00 GK (k=3) 0.04 0.04 0.04 0.04 RWK 70.79 71.01 100.29 90.90 Odd Sth (k=3) 0.05 0.05 0.05 0.05 Vertex Histogram 0.00 0.00 0.00 0.00 Lovasz Theta 151.14 313.54 298.87 228.57 SVM Theta 0.00 0.00 0.00 0.00 RGW 3.0 3.2 3.4 3.6 FGW 4.03 4.31 4.63 5.05 FUGW 44.09 44.16 41.10 42.30 FPGW 4.54 4.95 5.17 5.77 MUTAG WLK (auto) 0.00 0.00 0.00 0.00 GK (k=3) 0.03 0.03 0.03 0.03 RWK 211.48 61.07 66.10 305.90 Odd Sth (k=3) 0.00 0.00 0.00 0.00 Vertex Histogram 0.00 0.00 0.00 0.00 Lovasz Theta 22.48 19.14 18.67 13.82 SVM Theta 0.00 0.00 0.00 0.00 RGW 32.6 31.2 30.2 27.5 FGW 0.79 0.83 0.87 0.91 FUGW 19.70 21.76 20.98 17.69 FPGW 1.09 1.54 3.62 9.21 N.1 Numerical details in graph classification Parameter and Numerical Settings. The parameter settings are provided in Table ( 6 ). For methods not explicitly listed, we use the default values from the GraKeL library . For the FUGW method, we adapt the solver from [ 70 ] . We test different marginal penalty parameters \rho to ensure that the transported mass in each sampled pair is approximately 1. Additionally, we choose the smallest entropy regularization term \epsilon that prevents NaN errors. Table 6 : Parameter setting of all methods in graph classification. We present the parameter setting in all the methods. \sigma is the weight parameter in the SVM classifier. In FGW and FPGW, \alpha parameter is the \omega_{2} in formulations of FGW ( 7 ) and FPGW ( 10 ). For WLK/FGW/FUGW/FPGW, the value H is the Weisfeiler-Lehman labeling parameter. \rho,\epsilon in FUGW is the weight parameter for the marginal penalty and entropy regularization. Parameter \kappa in the GK/ODD method is the graphlet size. “n-samples” in GK is the random draw sample size. Data set parameter Synthetic Proteins Mutag MSRC-9 SVM (Common) \sigma 1 15 2 1 RGW \rho 0.1 0.1 0.1 0.1 \epsilon 0.05 0.05 0.05 0.05 t 0.1 0.1 0.1 0.1 \tau 0.1 0.1 0.1 0.1 FGW \alpha 0.5 0.5 0.5 0.5 H - - 2 4 FPGW \alpha 0.5 0.5 0.5 0.5 H - - 2 4 FUGW \alpha 0.5 0.5 0.5 0.5 H - - 2 4 \rho 1 1 0.4 0.4 \epsilon 0.05 0.1 0.02 0.02 WLK H - - 5 5 GK \kappa - - 3 3 n-samples - - 100 100 Odd Sth \kappa - - 3 3 Wall-clock time analysis. The wall-clock times are reported in Table 5 . All graph data are formatted as NetworkX graphs using the NetworkX library . Continuous features are represented as 64-bit float NumPy vectors, while discrete features are stored as 64-bit integers. For discrete feature graphs, WLK, GK, and Vertex Histogram are the fastest methods, while FGW and FPGW have similar wall-clock times. In contrast, Lovász Theta and Random Walk Kernel are the slowest. For continuous feature graphs, “Propagation” and “GraphHopper” are significantly faster than FGW and FPGW. Among the three fused-GW-based methods, FGW is the fastest overall, while FUGW is the slowest. A potential reason for this difference is that FGW and FPGW leverage a C++ linear programming solver for the OT/POT solving step. In addition, FUGW adapts the Sinkhorn solver, leading to an accuracy-efficiency trade-off. Specifically, a smaller \epsilon can reduce the accuracy gap introduced by the entropic term; however, it increases the number of iterations required for convergence. All experiments presented in this paper are conducted on a computational machine with an AMD EPYC 7713 64-Core Processor, 8 \times 32GB DIMM DDR4, 3200 MHz, and an NVIDIA RTX A6000 GPU. Impact Statement This paper aims to advance the theoretical foundations and potential applications of Optimal Transport in the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.