Fused Gromov-Wasserstein Distance for Structured Objects

Abstract

Optimal transport theory has recently found many applications in machine learning thanks to its capacity to meaningfully compare various machine learning objects that are viewed as distributions. The Kantorovitch formulation, leading to the Wasserstein distance, focuses on the features of the elements of the objects, but treats them independently, whereas the Gromov–Wasserstein distance focuses on the relations between the elements, depicting the structure of the object, yet discarding its features. In this paper, we study the Fused Gromov-Wasserstein distance that extends the Wasserstein and Gromov–Wasserstein distances in order to encode simultaneously both the feature and structure information. We provide the mathematical framework for this distance in the continuous setting, prove its metric and interpolation properties, and provide a concentration result for the convergence of finite samples. We also illustrate and interpret its use in various applications, where structured objects are involved.

1. Introduction

We focus on the comparison of structured objects, i.e., objects defined by both a feature and a structure information. Abstractly, the feature information cover all the attributes of an object; for example, it can model the value of a signal when objects are time series, or the node labels over a graph. In shape analysis, the spatial positions of the nodes can be regarded as features, or, when objects are images, local color histograms can describe the image’s feature information. As for the structure information, it encodes the specific relationships that exist among the components of the object. In a graph context, nodes and edges are representative of this notion, so that each label of the graph may be linked to some others through the edges between the nodes. In a time series context, the values of the signal are related to each other through a temporal structure. This representation can be related with the concept of relational reasoning (see [1]), where some entities (or elements with attributes, such as the intensity of a signal) coexist with some relations or properties between them (or some structure, as described above). Including structural knowledge about objects in a machine learning context has often been valuable in order to build more generalizable models. As shown in many contexts, such as graphical models [2,3], relational reinforcement learning [4], or Bayesian nonparametrics [5], considering objects as a complex composition of entities together with their interactions is crucial in order to learn from small amounts of data.

Unlike recent deep learning end-to-end approaches [6,7] that attempt to avoid integration of prior knowledge or assumptions about the structure wherever possible, ad hoc methods, depending on the kind of structured objects involved, aim to build meaningful tools that include structure information in the machine learning process. In graph classification, the structure can be taken into account through dedicated graph kernels, in which the structure drives the combination of the feature information [8,9,10]. In a time series context, Dynamic Time Warping and related approaches are based on the similarity between the features while allowing limited temporal (i.e., structural) distortion in the time instants that are matched [11,12]. Closely related, an entire field has focused on predicting the structure as an output and it has been deployed on tasks, such as segmenting an image into meaningful components or predicting a natural language sentence [10,13,14].

All of these approaches rely on meaningful representations of the structured objects that are involved. In this context, distributions or probability measures can provide an interesting representation for machine learning data. This allows their comparison within the Optimal Transport (OT) framework that provides a meaningful way of comparing distributions by capturing the underlying geometric properties of the space through a cost function. When the distributions dwell in a common metric space $(\mathsf{\Omega },d)$, the Wasserstein distance defines a metric between these distributions under mild assumptions [15]. In contrast, the Gromov–Wasserstein distance [16,17] aims at comparing distributions that support live in different metric spaces through the intrinsic pair-to-pair distances in each space. Unifying both distances, the Fused Gromov–Wasserstein distance was proposed in a previous work in [18] and used in the discrete setting to encode, in a single OT formulation, both feature and structure information of structured objects. This approach considers structured objects as joint distributions over a common feature space associated with a structure space specific to each object. An OT formulation is derived by considering a tradeoff between the feature and the structure costs, respectively, defined with respect to the Wasserstein and the Gromov–Wasserstein standpoints.

This paper presents the theoretical foundations of this distance and states the mathematical properties of the $FGW$ metric in the general setting. We first introduce a representation of structured objects using distributions. We show that classical Wasserstein and Gromov–Wasserstein distance can be used in order to compare either the feature information or the structure information of the structured object but that they both fail at comparing the entire object. We then present the Fused Gromov–Wasserstein distance in its general formulation and derive some of its mathematical properties. Particularly, we show that it is a metric in a given case, we give a concentration result, and we study its interpolation and geodesic properties. We then provide a conditional-gradient algorithm to solve the quadratic problem resulting from $FGW$ in the discrete case and we conclude by illustrating and interpreting the distance in several applicative contexts.

Notations. Let $\mathcal{P}(\mathsf{\Omega })$ be the set of all probability measures on a space $\mathsf{\Omega }$ and $\mathcal{B}(A)$ the set of all Borel sets of a $\sigma$-algebra A. We note # the push-forward operator, such, that for a measurable function T, $B\in \mathcal{B}(A)$, $T\#\mu (B)=\mu (T^{-1}(B))$.

We note supp$(\mu )$ the support of $\mu \in \mathcal{P}(\mathsf{\Omega })$ is the minimal closed subset $A\subset \mathsf{\Omega }$ such that $\mu (\mathsf{\Omega }\backslash A)=0$. Informally, this is the set where the measure “is not zero”.

For two probability measures $\mu \in \mathcal{P}(A)$ and $\nu \in \mathcal{P}(B)$ we note $\mathsf{\Pi }(\mu ,\nu )$ the set of all couplings or matching measures of $\mu$ and $\nu$, i.e., the set $\{\pi \in P(\mathsf{\Omega }\times \mathsf{\Omega })|\forall (A_0,B_0)\in \mathcal{B}(A)\times \mathcal{B}(B),\pi (A_0\times B)=\mu (A_0),\pi (\mathsf{\Omega }\times {\mathsf{\Omega }}_0)=\nu (B_0)\}$.

For two metric spaces $(X,d_X)$ and $(Y,d_Y)$, we define the distance $d_X\oplus d_Y$ on $X\times Y$ such that, for $(x,y),(x^{\prime },y^{\prime })\in X\times Y,d_X\oplus d_Y((x,y),(x^{\prime },y^{\prime }))=d_X(x,x^{\prime })+d_Y(y,y^{\prime })$.

We note the simplex of N bins as ${\mathsf{\Sigma }}_N=\{a\in {({\mathbb{R}}_{+})}^N,{\sum }_i{a}_i=1\}$. For two histograms $a\in {\mathsf{\Sigma }}_n$ and $b\in {\mathsf{\Sigma }}_m$ we note with some abuses $\mathsf{\Pi }(a,b)$ the set of all couplings of a and b, i.e., the set $\mathsf{\Pi }(a,b)=\{\pi \in {\mathbb{R}}_{+}^{n\times m}|{\sum }_i{\pi }_{i,j}=b_j;{\sum }_j{\pi }_{i,j}=a_i\}$. Finally, for $x\in \mathsf{\Omega }$, ${\delta }_x$ denotes the dirac measure in x.

Assumption. In this paper, we assume that all metric spaces are non-trivial Polish metric spaces (i.e., separable and completely metrizable topological spaces) and that all measures are Borel.

2. Structured Objects as Distributions and Fused Gromov–Wasserstein Distance

The notion of structured objects used in this paper is inspired from the discrete point of view where one aims at comparing labeled graphs. More formally, we consider undirected labeled graphs as tuples of the form $\mathcal{G}=(\mathcal{V},\mathcal{E},{\ell }_f,{\ell }_s)$, where $(\mathcal{V},\mathcal{E})$ are the set of vertices and edges of the graph. ${\ell }_f:\mathcal{V}\to \mathsf{\Omega }$ is a labelling function that associates each vertex $v_i\in \mathcal{V}$ with a feature $a_i\stackrel{\mathrm{def}}{=}{\ell }_f(v_i)$ in some feature metric space $(\mathsf{\Omega },d)$. Similarly, ${\ell }_s:\mathcal{V}\to X$ maps a vertex $v_i$ from the graph to its structure representation $x_i\stackrel{\mathrm{def}}{=}{\ell }_s(v_i)$ in some structure space $(X,d_X)$ specific to each graph. $d_X:X\times X\to {\mathbb{R}}_{+}$ is a symmetric application which aims at measuring the similarity between the nodes in the graph. In the graph context, $d_X$ can either encode the neighborhood information of the nodes, the edge information of the graph or more generally it can model a distance between the nodes such as the shortest path distance or the harmonic distance [19]. When $d_X$ is a metric, such as the shortest-path distance, we naturally endow the structure with the metric space $(X,d_X)$.

In this paper, we propose enriching the previous definition of a structured object with a probability measure which serves the purpose of signaling the relative importance of the object’s elements. For example, we can add a probability (also denoted as weight) ${(h_i)}_i\in {\mathsf{\Sigma }}_n$ to each node in the graph. This way, we define a fully supported probability measure $\mu ={\sum }_i{h}_i{\delta }_{(x_i,a_i)}$, which includes all the structured object information (see Figure 1 for a graphical depiction).

This graph representation for objects with a finite number of points/vertices can be generalized to the continuous case and leads to a more general definition of structured objects:

Definition 1.

(Structured objects). A structured object over a metric space $(\mathsf{\Omega },d)$ is a triplet $(X\times \mathsf{\Omega },d_X,\mu )$, where $(X,d_X)$ is a metric space and μ is a probability measure over $X\times \mathsf{\Omega }$. $(\mathsf{\Omega },d)$ is denoted as the feature space, such that $d:\mathsf{\Omega }\times \mathsf{\Omega }\to {\mathbb{R}}_{+}$ is the distance in the feature space and $(X,d_X)$ the structure space, such that $d_X:X\times X\to {\mathbb{R}}_{+}$ is the distance in the structure space. We will note ${\mu }_X$ and ${\mu }_A$ the structure and feature marginals of μ.

Definition 2.

(Space of structured objects). We note $\mathbb{X}$ the set of all metric spaces. The space of all structured objects over $(\mathsf{\Omega },d)$ will be written as $\mathbb{S}(\mathsf{\Omega })$ and is defined by all the triplets $(X\times \mathsf{\Omega },d_X,\mu )$ where $(X,d_X)\in \mathbb{X}$ and $\mu \in \mathcal{P}(X\times \mathsf{\Omega })$. To avoid finiteness issues in the rest of the paper we define for $p\in {\mathbb{N}}^{*}$ the space ${\mathbb{S}}_p(\mathsf{\Omega })\subset \mathbb{S}(\mathsf{\Omega })$ such that if $(X\times \mathsf{\Omega },d_X,\mu )\in {\mathbb{S}}_p(\mathsf{\Omega })$ we have:

$${\int }_{\mathsf{\Omega }}d{(a,a_0)}^{p}d{\mu }_A(a)<+\infty$$

(1)

(the finiteness of this integral does not depend on the choice of $a_0$)

$${\int }_{X\times X}{d}_X{(x,x^{\prime })}^{p}d{\mu }_X(x)d{\mu }_X(x^{\prime })<+\infty .$$

(2)

For the sake of simplicity, and when it is clear from the context, we will sometimes denote only by $\mu$ the whole structured object. The marginals ${\mu }_X,{\mu }_A$ encode very partial information since they focus only on independent feature distributions or only on the structure. This definition encompasses the discrete setting discussed in above. More precisely, let us consider a labeled graph of n nodes with features $A={(a_i)}_{i=1}^n$ with $a_i\in \mathsf{\Omega }$ and $X={(x_i)}_{i=1}^n$ the structure representation of the nodes. Let ${(h_i)}_{i=1}^n$ be an histogram, then the probability measure $\mu ={\sum }_{i=1}^n{h}_i{\delta }_{(x_i,a_i)}$ defines structured object in the sense of Definition 1, since it lies in $\mathcal{P}(X\times \mathsf{\Omega })$. In this case, an example of $\mu$, ${\mu }_X$, and ${\mu }_A$ is provided in Figure 1.

Note that the set of structured objects is quite general and also allows considering discrete probability measures of the form $\mu ={\sum }_{i,j=1}^{p,q}{h}_{i,j}{\delta }_{(x_i,a_j)}$ with $p,q$ possibly different than n. We propose focusing on a particular type of structured objects, namely the generalized labeled graphs, as described in the following definition:

Definition 3.

(Generalized labeled graph). We call generalized labeled graph a structured object $(X\times \mathsf{\Omega },d_X,\mu )\in {\mathbb{S}}_p(\mathsf{\Omega })$ such that μ can be expressed as $\mu =(I\times {\ell }_f)\#{\mu }_X$ where ${\ell }_f:X\to \mathsf{\Omega }$ is surjective and pushes ${\mu }_X$ forward to ${\mu }_A$, i.e., ${\ell }_f\#{\mu }_X={\mu }_A$.

This definition implies that there exists a function ${\ell }_f$, which associates a feature $a=l_f(x)$ to a structure point $x\in X$ and, as such, one structure point can not have two different features. The labeled graph described by $\mu ={\sum }_{i=1}^n{h}_i{\delta }_{(x_i,a_i)}$ is a particular instance of a generalized labeled graph in which $l_f$ is defined by $l_f(x_i)=a_i$.

2.1. Comparing Structured Objects

We now aim to define a notion of equivalence between two structured objects $(X\times \mathsf{\Omega },d_X,\mu )$ and $(Y\times \mathsf{\Omega },d_Y,\nu )$. We note in the following ${\nu }_Y,{\nu }_B$ the marginals of $\nu$. Intuitively, two structured objects are the same if they share the same feature information, if their structure information are lookalike, and if the probability measures are corresponding in some sense. In this section, we present mathematical tools for individual comparison of the elements of structured objects. First, our formalism implies comparing metric spaces, which can be done via the notion of isometry.

Definition 4.

(Isometry). Let $(X,d_X)$ and $(Y,d_Y)$ be two metric spaces. An isometry is a surjective map $f:X\to Y$ that preserves the distances:

$$\forall x,x^{\prime }\in X,d_Y(f(x),f(x^{\prime }))=d_X(x,x^{\prime }).$$

(3)

An isometry is bijective, since for $f(x)=f(x^{\prime })$ we have $d_Y(f(x),f(x^{\prime }))=0=d_X(x,x^{\prime })$ and hence $x=x^{\prime }$ (in the same way $f^{-1}$ is also a isometry). When it exists, X and Y share the same “size” and any statement about X, which can be expressed through its distance is transported to Y by the isometry f.

Example 1.

Let us consider the two following graphs whose discrete metric spaces are obtained as shortest path between the vertices (see corresponding graphs in Figure 2).

$$\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right),\underset{d_X(x_i,x_j)}{\underbrace{\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 2\\ 1& 1& 0& 2\\ 1& 2& 2& 0\end{array}\right)}}\mathit{and}\left(\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}\right),\underset{d_Y(y_i,y_j)}{\underbrace{\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 2& 2\\ 1& 2& 0& 1\\ 1& 2& 1& 0\end{array}\right)}}.$$

These spaces are isometric since the map f, such that $f(x_1)=y_1$, $f(x_2)=y_3$, $f(x_3)=y_4$, $f(x_4)=y_2$ verifies Equation (3).

The previous definition can be used in order to compare the structure information of two structured objects. Regarding the feature information, because they all lie in the same ambient space $\mathsf{\Omega }$, a natural way for comparing them is by the standard set equality $A=B$. Finally, in order to compare measures on different spaces, the notion of preserving map can be used.

Definition 5.

(Measure preserving map). Let ${\mathsf{\Omega }}_1,{\mu }_1\in \mathcal{P}({\mathsf{\Omega }}_1)$ and ${\mathsf{\Omega }}_2,{\mu }_2\in \mathcal{P}({\mathsf{\Omega }}_2)$ be two measurable spaces. A function (usually called a map) $f:{\mathsf{\Omega }}_1\to {\mathsf{\Omega }}_2$ is said to be measure preserving if it transports the measure ${\mu }_1$ on ${\mu }_2$ such that

$$f\#{\mu }_1={\mu }_2.$$

If there exists such a measure preserving map, the properties about measures of ${\mathsf{\Omega }}_1$ are transported via f to ${\mathsf{\Omega }}_2$.

Combining these two ideas together leads to the notion of measurable metric spaces (often called mm-spaces [17]), i.e., a metric space $(X,d_X)$ enriched with a probability measure and described by a triplet $(X,d_X,{\mu }_X\in \mathcal{P}(X))$. An interesting notion for comparing mm-spaces is the notion of isomorphism.

Definition 6.

(Isomorphism). Two mm-spaces $(X,d_X,{\mu }_X),(Y,d_Y,{\mu }_Y)$ are isomorphic if there exists a surjective measure preserving isometry $f:supp({\mu }_X)\to supp({\nu }_Y)$ between the support of the measures ${\mu }_X,{\nu }_Y$.

Example 2.

Let us consider two mm-spaces $(X=\{x_1,x_2\},d_X=\{1\},{\mu }_X=\{\frac{1}{2},\frac{1}{2}\})$ and $(Y=\{y_1,y_2\},d_Y=\{1\},{\mu }_Y=\{\frac{1}{4},\frac{3}{4}\})$, as depicted in Figure 3. These spaces are isometric, but not isomorphic, as there exists no measure preserving map between them.

All of this considered, we can now define a notion of equivalence between structured objects.

Definition 7.

(Strong isomorphism of structured objects).

Two structured objects are said to be strongly isomorphic if there exists an isomorphism I between the structures such that $f=(I,id)$ is bijective between $supp(\mu )$ and $supp(\nu )$ and measure preserving. More precisely, f satisfies the following properties:

P.1 

$f\#\mu =\nu$.

P.2 

The function f statisfies:

$$\forall (x,a)\in supp(\mu ),f(x,a)=(I(x),a).$$

(4)

P.3 

The function $I:supp({\mu }_X)\to supp({\nu }_Y)$ is surjective, satisfies $I\#{\mu }_X={\nu }_Y$ and:

$$\forall x,x^{\prime }\in {supp({\mu }_X)}^2,d_X(x,x^{\prime })=d_Y(I(x),I(x^{\prime })).$$

(5)

It is easy to check that the strong isomorphism defines an equivalence relation over ${\mathbb{S}}_p(\mathsf{\Omega })$.

Remark 1.

The function f described in this definition can be seen as a feature, structure, and measure preserving function. Indeed, fromP.1f is measure preserving. Moreover, $(X,d_X,{\mu }_X)$ and $(Y,d_Y,{\nu }_Y)$ are isomorphic through I. Finally usingP.1andP.2we have that ${\mu }_A={\nu }_B$, so that the feature information is also preserved.

Example 3.

To illustrate this definition, we consider a simple example of two discrete structured objects:

$$\underset{x_i,a_i}{\underbrace{\left(\begin{array}{c}(x_1,a_1)\\ (x_2,a_2)\\ (x_3,a_3)\\ (x_4,a_4)\end{array}\right)}},\underset{d_X(x_i,x_j)}{\underbrace{\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 2\\ 1& 1& 0& 2\\ 1& 2& 2& 0\end{array}\right)}},\underset{h_i}{\underbrace{\left(\begin{array}{c}1/4\\ 1/4\\ 1/4\\ 1/4\end{array}\right)}}\mathit{and}\underset{y_i,b_i}{\underbrace{\left(\begin{array}{c}(y_1,b_1)\\ (y_2,b_2)\\ (y_3,b_3)\\ (y_4,b_4)\end{array}\right)}},\underset{d_Y(y_i,y_j)}{\underbrace{\left(\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 2& 2\\ 1& 2& 0& 1\\ 1& 2& 1& 0\end{array}\right)}},\underset{h_i^{\prime }}{\underbrace{\left(\begin{array}{c}1/4\\ 1/4\\ 1/4\\ 1/4\end{array}\right)}}$$

with for i, $a_i=b_i$ and for $i\ne j$, $a_i\ne a_j$ (see Figure 4). The two structured objects have isometric structures and same features individually, but they are not strongly isomorphic. One possible map $f=(f_1,f_2)$, such that $f_1$ leads to an isometry is $f(x_1,a_1)=(y_1,b_1)$, $f(x_2,a_2)=(y_3,b_3)$, $f(x_3,a_3)=(y_4,b_4)$, $f(x_4,a_4)=(y_2,b_2)$. Yet, this map does not satisfy $f_2(x,.)=I_d$ for any x, since $f(x_2,a_2)=(y_3,b_3)$ and $a_2\ne b_3$. The other possible functions, such that $f_1$ leads to an isometry are simply permutations of this example, yet it is easy to check that none of them verifiesP.2(for example, with $f(x_2,a_2)=(y_4,b_4)$).

2.2. Background on OT Distances

The Optimal Transport (OT) framework defines distances between probability measures that describe either the feature or the structure information of structured objects.

Wasserstein distance. The classical OT theory aims at comparing probability measures ${\mu }_A\in \mathcal{P}(\mathsf{\Omega }),{\nu }_B\in \mathcal{P}(\mathsf{\Omega })$. In this context the quantity:

$$d_{W,p}({\mu }_A,{\nu }_B)={\left(\underset{\pi \in \mathsf{\Pi }({\mu }_A,{\nu }_B)}{\inf }\underset{\mathsf{\Omega }\times \mathsf{\Omega }}{\int }d{(a,b)}^{p}d\pi (a,b)\right)}^{\frac{1}{p}}$$

(6)

is usually called the p-Wasserstein distance (also known, for $p=1$, as Earth Mover’s distance [20] in the computer vision community) between distributions ${\mu }_A$ and ${\nu }_B$. It defines a distance on probability measures, especially $d_{W,p}({\mu }_A,{\nu }_B)=0$ iff ${\mu }_A={\nu }_B$. This distance also has a nice geometrical interpretation as it represents an optimal cost (w.r.t. d) to move the measure ${\mu }_A$ onto ${\nu }_B$ with $\pi (a,b)$ the amount of probability mass shifted from a to b (see Figure 5). To this extent, the Wasserstein distance quantifies how “far” ${\mu }_A$ is from ${\nu }_B$ by measuring how “difficult” it is to move all the mass from ${\mu }_A$ onto ${\nu }_B$. Optimal transport can deal with smooth and discrete measures and it has proved to be very useful for comparing distributions in a shared space, but with different (and even non-overlapping) supports.

Gromov–Wasserstein distance. In order to compare measures whose support are not necessarily in the same ambient space [16,17] define a new OT distance. By relaxing the classical Hausdorff distance [15,17], authors build a distance over the space of all mm-spaces. For two compact mm-spaces $(X,d_X,{\mu }_X\in \mathcal{P}(X))$ and $(Y,d_Y,{\nu }_Y\in \mathcal{P}(Y))$, the Gromov–Wasserstein distance is defined as:

$$d_{GW,p}({\mu }_X,{\nu }_Y)={\left(\underset{\pi \in \mathsf{\Pi }({\mu }_X,{\nu }_Y)}{\inf }\underset{X\times Y\times X\times Y}{\int }L{(x,y,x^{\prime },y^{\prime })}^{p}d\pi (x,y)d\pi (x^{\prime },y^{\prime })\right)}^{\frac{1}{p}}$$

(7)

where:

$$L(x,y,x^{\prime },y^{\prime })=|d_X(x,x^{\prime })-d_Y(y,y^{\prime })|$$

The Gromov–Wasserstein distance depends on the choice of the metrics $d_X$ and $d_Y$ and with some abuse of notation we denote the entire mm-space by its probability measure. When it is not clear from the context, we will specify using $d_{GW,p}(d_X,d_Y,{\mu }_X,{\nu }_Y)$. The resulting coupling tends to associate pairs of points with similar distances within each pair (see Figure 6). The Gromov–Wasserstein distance allows for the comparison of measures over different ground spaces and defines a metric over the space of all mm-spaces quotiented by the isomoprhisms (see Definitions 4 and 5). More precisely, it vanishes if the two mm-spaces are isomorphic. This distance has been used in the context of relational data e.g., in shape comparison  [17,22], deep metric alignment [23], generative modelling [24] or to align single-cell multi-omics datasets [25].

2.3. Fused Gromov–Wasserstein Distance

Building on both Gromov–Wasserstein and Wasserstein distances, we define the Fused Gromov–Wasserstein ($FGW$) distance on the space of structured objects:

Definition 8.

(Fused Gromov-Wasserstein distance). Let $\alpha \in [0,1]$ and $p,q\ge 1$. We consider $(X\times \mathsf{\Omega },d_X,\mu )\in {\mathbb{S}}_{pq}(\mathsf{\Omega })$ and $(Y\times \mathsf{\Omega },d_Y,\nu )\in {\mathbb{S}}_{pq}(\mathsf{\Omega })$. The Fused-Gromov–Wasserstein distance is defined as:

$$d_{FGW,\alpha ,p,q}(\mu ,\nu )={\left(\underset{\pi \in \mathsf{\Pi }(\mu ,\nu )}{inf}{E}_{p,q,\alpha }(\pi )\right)}^{\frac{1}{p}}$$

(8)

where

$$E_{p,q,\alpha }(\pi )=\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))$$

Figure 7 illustrates this definition. When it is clear from the context we will simply note $d_{FGW}$ instead for $d_{FGW,\alpha ,p,q}$ for brevity. $\alpha$ acts as a trade-off parameter between the cost of the structures represented by $L(x,y,x^{\prime },y^{\prime })$ and the feature cost $d(a,b)$. In this way, the convex combination of both terms leads to the use of both information in one formalism resulting on a single map $\pi$ that “moves” the mass from one joint probability measure to the other.

Many desirable properties arise from this definition. Among them, one can define a topology over the space of structured objects using the $FGW$ distance to compare structured objects, in the same philosophy as for Wasserstein and Gromov–Wasserstein distances. The definition also implies that $FGW$ acts as a generalization of both Wasserstein and Gromov-Wasserstein distances, with $FGW$ achieving an interpolation between these two distances. More remarkably, $FGW$ distance also realizes geodesic properties over the space of structured objects, allowing the definition of gradient flows. All of these properties are detailed in the next section. Before reviewing them, we first compare $FGW$ with $GW$ and W (by assuming for now that $FGW$ exists, which will be shown later in Theorem 1).

Proposition 1.

(Comparaison between $FGW$, $GW$ and W). We have the following results for two structured objects μ and ν:

• The following inequalities hold:

  $$d_{FGW,\alpha ,p,q}(\mu ,\nu )\ge (1-\alpha )d_{W,pq}{({\mu }_A,{\nu }_B)}^q$$

  (9)

  $$d_{FGW,\alpha ,p,q}(\mu ,\nu )\ge \alpha d_{GW,pq}{({\mu }_X,{\nu }_Y)}^q$$

  (10)
• Let us suppose that the structure spaces $(X,d_X)$,$(Y,d_Y)$ are part of a single ground space $(Z,d_Z)$ (i.e., $X,Y\subset Z$ and $d_X=d_Y=d_Z$). We consider the Wasserstein distance between μ and ν for the distance on $Z\times \mathsf{\Omega }$: $\tilde{d}((x,a),(y,b))=(1-\alpha )d(a,b)+\alpha d_Z(x,y)$. Then:

  $$d_{FGW,\alpha ,p,1}(\mu ,\nu )\le 2d_{W,p}(\mu ,\nu ).$$

  (11)

Proof of this proposition can be found in Section 7.1. In particular, following this proposition, when the $FGW$ distance vanishes then both $GW$ and W distances vanish so that the structure and the feature of the structure object are individually “the same” (with respect to their corresponding equivalence relation). However, the converse is not necessarily true, as shown in the following example.

Example 4.

(Toy trees). We construct two trees as illustrated in Figure 8 where the 1D node features are shown with colors. The shortest path between the nodes is used to capture the structures of the two structured objects and the Euclidean distance is used for the features. We consider uniform weights on all nodes. Figure 8 illustrates the differences between $FGW$, $GW$, and W distances. The left part is the Wasserstein coupling between the features: red nodes are transported on red ones and the blue nodes on the blue ones but tree structures are completely discarded. In this case, the Wasserstein distance vanishes. In the right part, we compute the Gromov–Wasserstein distance between the structures: all couples of points are transported to another couple of points, which enforces the matching of tree structures without taking into account the features. Because structures are isometric, the Gromov–Wasserstein distance is null. Finally, we compute the $FGW$ using intermediate α (center), the bottom and first level structure is preserved as well as the feature matching (red on red and blue on blue) and $FGW$ discriminates the two structured objects.

3. Mathematical Properties of $\mathbf{FGW}$

In this section, we establish some mathematical properties of the $FGW$ distance. The first result relates to the existence of the $FGW$ distance and the topology of the space of structured objects. We then prove that the $FGW$ distance is indeed a distance regarding the equivalence relation between structured objects, as defined in Defintion 7, allowing us to derive a topology on $\mathbb{S}(\mathsf{\Omega })$.

3.1. Topology of the Structured Object Space

The $FGW$ distance has the following properties:

Theorem 1.

(Metric properties). Let $p,q\ge 1$, $\alpha \in ]0,1[$ and $\mu ,\nu \in {\mathbb{S}}_{pq}(\mathsf{\Omega })$. The functional $\pi \to E_{p,q,\alpha }(\pi )$ always achieves an infimum ${\pi }^{*}$ in $\mathsf{\Pi }(\mu ,\nu )$ s.t. $d_{FGW,\alpha ,p,q}(\mu ,\nu )=E_{p,q,\alpha }({\pi }^{*})<+\infty$. Moreover:

•

$d_{FGW,\alpha ,p,q}$ is symmetric and, for $q=1$, satisfies the triangle inequality. For $q\ge 2$, the triangular inequality is relaxed by a factor $2^{q-1}$.

•

For $\alpha \in ]0,1[$, $d_{FGW,\alpha ,p,q}(\mu ,\nu )=0$ if an only if there exists a bijective function $f=(f_1,f_2):supp(\mu )\to supp(\nu )$ such that:

$$f\#\mu =\nu$$

(12)

$$\forall (x,a)\in supp(\mu ),f_2(x,a)=a$$

(13)

$$\forall (x,a),(x^{\prime },a^{\prime })\in supp{(\mu )}^2,d_X(x,x^{\prime })=d_Y(f_1(x,a),f_1(x^{\prime },a^{\prime }))$$

(14)

•

If $(\mu ,\nu )$ are generalized labeled graphs then $d_{FGW,\alpha ,p,q}(\mu ,\nu )=0$ if and only if $(X\times \mathsf{\Omega },d_X,\mu )$ and $(Y\times \mathsf{\Omega },d_Y,\nu )$ are strongly isomorphic.

Proof of this theorem can be found in Section 7.2. The identity of indiscernibles is the most delicate part to prove and it is based on using the Gromov–Wasserstein distance between the spaces $X\times \mathsf{\Omega }$ and $Y\times \mathsf{\Omega }$. The previous theorem states that $FGW$ is a distance over the space of generalized labeled graphs endowed with the strong isomorphism as equivalence relation defined in Definition 7. More generally, for any structured objects the equivalence relation is given by (12)–(14). Informally, invariants of the $FGW$ are structured objects that have both the same structure and the same features in the same place. Despite the fact that $q=1$ leads to a proper metric, we will further see in Section 4.1 that the case $q=2$ can be computed more efficiently using a separability trick from [26].

Theorem 1 allows a wide set of applications for $FGW$, such as k-nearest-neighbors, distance-substitution kernels, pseudo-Euclidean embeddings, or representative-set methods [27,28,29]. Arguably, such a distance allows for a better interpretation than to end-to-end learning machines, such as neural networks, because the $\pi$ matrix exhibits the relationships between the elements of the objects in a pairwise comparison.

3.2. Can We Adapt W and GW for Structured Objects?

Despite the appealing properties of both Wasserstein and Gromov–Wasserstein distances, they fail at comparing structured objects by focusing only on the feature and structure marginals, respectively. However, with some hypotheses, one could adapt these distances for structured objects.

Adapting Wasserstein. If the structure spaces $(X,d_X)$ and $(Y,d_Y)$ are part of a same ground space $(Z,d_Z)$, i.e., ($X,Y\subset Z$ and $d_X=d_Y=d_Z$), one can build a distance $\widehat{d}=d_Z\oplus d$ between couples $(x,a)$ and $(y,b)$ and apply the Wasserstein distance, so as to compare the two structured objects. In this case, when the Wasserstein distance vanishes it implies that the structured objects are equal in the sense $\mu =\nu$. This approach is very related with the one discussed in [30], where the authors define the Transportation $L^p$ distance for signal analysis purposes. Their approach can be viewed as a transport between two joint measures $\mu (X\times \mathsf{\Omega })=\lambda (\{(x,f(x))|x\in X\subset Z={\mathbb{R}}^d;f(x)\in A\subset {\mathbb{R}}^m\})$, $\nu (Y\times \mathsf{\Omega })=\lambda (\{(y,g(y))|y\in Y\subset Z={\mathbb{R}}^d;g(y)\in B\subset {\mathbb{R}}^m\})$ for function $f,g:Z\to {\mathbb{R}}^m$ representative of the signal values and $\lambda$ the Lebesgue measure. The distance for the transport is defined as $\widehat{d}((x,f(x)),(y,g(y)))=\frac{1}{\alpha }{\parallel x-y\parallel }_p^p+{\parallel f(x)-g(y)\parallel }_p^p$ for $\alpha >0$ and ${\parallel ·\parallel }_p$ the $l_p$ norm. In this case, $f(x)$ and $g(y)$ can be interpreted as encoding the feature information of the signal, while $x,y$ encode its structure information. This approach is very interesting, but cannot be used on structured objects, such as graphs that will not share a common structure embedding space.

Adapting Gromov-Wasserstein. The Gromov–Wasserstein distance can also be adapted to structured objects by considering the distances $(1-\beta )d_X\oplus \beta d$ and $(1-\beta )d_Y\oplus \beta d$ within each space $X\times \mathsf{\Omega }$ and $Y\times \mathsf{\Omega }$, respectively, and $\beta \in ]0,1[$. When the resulting $GW$ distance vanishes, structured objects are isomorphic with respect to $(1-\beta )d_X\oplus \beta d$ and $(1-\beta )d_Y\oplus \beta d$. However, the strong isomorphism is stronger than this notion, since the isomorphism allows for “permuting the labels”, but not the strong isomorphism. More precisely, we have the following lemma:

Lemma 1.

Let $(X\times \mathsf{\Omega },d_X,\mu ),(Y\times \mathsf{\Omega },d_Y,\nu )$ be two structured objects and $\beta \in ]0,1[$.

If $(X\times \mathsf{\Omega },d_X,\mu )$ and $(Y\times \mathsf{\Omega },d_Y,\nu )$ are strongly isomorphic then $(X\times \mathsf{\Omega },(1-\beta )d_X\oplus \beta d,\mu )$ and $(Y\times \mathsf{\Omega },(1-\beta )d_Y\oplus \beta d,\nu )$ are isomorphic. However the converse is not true in general.

Proof. 

To see this, if we consider f as defined in Theorem 1, then, for $(x,a),(x^{\prime },b)\in {(\mathrm{supp}(\mu ))}^2$, we have $d_X(x,x^{\prime })=d_Y(I(x),I(x^{\prime }))$. In this way:

$$(1-\beta )d_X(x,x^{\prime })+\beta d(a,b)=(1-\beta )d_Y(I(x),I(x^{\prime }))+\beta d(a,b)$$

(15)

which can be rewritten as:

$$(1-\beta )d\oplus \beta d_X((x,a),(x^{\prime },b))=(1-\beta )d\oplus \beta d_Y(f(x,a),f(x^{\prime },b))$$

(16)

and so f is an isometry with respect to $(1-\beta )d\oplus \beta d_X$ and $(1-\beta )d\oplus \beta d_Y$. Because f is also measure preserving and surjective $(X\times \mathsf{\Omega },(1-\beta )d_X\oplus \beta d,\mu )$ and $(Y\times \mathsf{\Omega },(1-\beta )d_Y\oplus \beta d,\nu )$ are isomorphic. □

However, the converse is not necessarily true, as it is easy to cook up an example with the same structure but with permuted labels, so that objects are isomorphic but not strongly isomorphic. For example, in the tree example Figure 4, the structures are isomorphic and the distances between the features within each space are the same between each structured objects, so that $(X\times \mathsf{\Omega },(1-\beta )d_X\oplus \beta d,\mu )$ and $(Y\times \mathsf{\Omega },(1-\beta )d_Y\oplus \beta d,\nu )$ are isomorphic, yet not strongly isomorphic, as shown in the example since $FGW>0$.

3.3. Convergence of Structured Objects

The metric property naturally endows the structured object space with a notion of convergence, as described in the next definition:

Definition 9.

Convergence of structured objects.

Let ${\left((X_n\times A_n,d_{X_n},{\mu }_n)\right)}_{n\in \mathbb{N}}$ be a sequence of structured objects. It converges to $(X\times \mathsf{\Omega },d_X,\mu )$ in the Fused Gromov–Wasserstein sense if:

$$\underset{n\to \infty }{lim}{d}_{FGW,\alpha ,p,1}({\mu }_n,\mu )=0$$

(17)

Using Proposition 1, it is straightforward to see that if the sequence converges in the $FGW$ sense, both the features and the structure converge respectively in the Wasserstein and Gromov–Wasserstein sense (see [17] for the definition of convergence in the Gromov–Wasserstein sense).

An interesting question arises from this definition. Let us consider a structured object $(X\times \mathsf{\Omega },d_X,\mu )$ and let us sample the joint distribution so as to consider ${({\{(x_i,a_i)\}}_{i\in \{1,\dots ,n\}},d_X,{\mu }_n)}_{n\in \mathbb{N}}$ with ${\mu }_n=\frac{1}{n}{\displaystyle \sum _{i=1}^n}{\delta }_{x_i,a_i}$ where $(x_i,a_i)\in X\times \mathsf{\Omega }$ are sampled from $\mu$. Does this sequence converges to $(X\times \mathsf{\Omega },d_X,\mu )$ in the $FGW$ sense and how fast is the convergence?

This question can be answered thanks to a notion of “size” of a probability measure. For the sake of conciseness, we will not exhaustively present the theory, but the reader can refer to [31] for more details. Given a measure $\mu$ on $\mathsf{\Omega }$, we denote as $di{m}_p^{*}(\mu )$ its upper Wasserstein dimension. It coincides with the intuitive notion of “dimension” when the measure is sufficiently well behaved. For example, for any absolutely continuous measure $\mu$ with respect to the Lebesgue measure on ${[0,1]}^d$, we have $di{m}_p^{*}(\mu )=d$ for any $p\in [1,\frac{d}{2}]$. Using this definition and the results presented in [31], we answer the question of convergence of finite sample in the following theorem (proof can be found in Section 7.3):

Theorem 2.

Convergence of finite samples and a concentration inequality

Let $p\ge 1$. We have:

$$\underset{n\to \infty }{lim}{d}_{FGW,\alpha ,p,1}({\mu }_n,\mu )=0.$$

Moreover, suppose that $s>d_p^{*}(\mu )$. Then there exists a constant C that does not depend on n such that:

$$\mathbb{E}[d_{FGW,\alpha ,p,1}({\mu }_n,\mu )]\le C{n}^{-\frac{1}{s}}.$$

(18)

The expectation is taken over the i.i.d samples $(x_i,a_i)$. A particular case of this inequality is when $\alpha =1$ so that we can use the result above to derive a concentration result for the Gromov-Wasserstein distance. More precisely, if ${\nu }_n=\frac{1}{n}{\sum }_i{\delta }_{x_i}$ denotes the empirical measure of $\nu \in \mathcal{P}(X)$ and if $s^{\prime }>d_p^{*}(\nu )$, we have:

$$\mathbb{E}[d_{GW,p}({\nu }_n,\nu )]\le C^{\prime }{n}^{-\frac{1}{s^{\prime }}}.$$

(19)

This result is a simple application of the convergence of finite sample properties of the Wasserstein distance, since in this case ${\mu }_n$ and $\mu$ are part of the same ground space so that (18) derive naturally from (11) and the properties of Wasserstein. In contrast to the Wasserstein distance case, this inequality is not necessarily sharp and future work will be dedicated to the study of its tightness.

3.4. Interpolation Properties between Wasserstein and Gromov-Wasserstein Distances

$FGW$ distance is a generalization of both Wasserstein and Gromov–Wasserstein distances in the sense that it achieves an interpolation between them. More precisely, we have the following theorem:

Theorem 3.

Interpolation properties.

As α tends to zero, one recovers the Wasserstein distance between the features information and as α goes to one, one recovers the Gromov–Wasserstein distance between the structure information:

$$\underset{\alpha \to 0}{lim}{d}_{FGW,\alpha ,p,q}(\mu ,\nu )={(d_{W,qp}({\mu }_A,{\nu }_B))}^q$$

(20)

$$\underset{\alpha \to 1}{lim}{d}_{FGW,\alpha ,p,q}(\mu ,\nu )={(d_{GW,qp}({\mu }_X,{\nu }_Y))}^q$$

(21)

Proof of this theorem can be found in Section 7.4.

This result shows that $FGW$ can revert to one of the other distances. In machine learning, this allows for a validation of the $\alpha$ parameter to better fit the data properties (i.e., by tuning the relative importance of the feature vs. structure information). One can also see the choice of $\alpha$ as a representation learning problem and its value can be found by optimizing a given criterion.

3.5. Geodesic Properties

One desirable property in OT is the underlying geodesics defined by the mass transfer between two probability distributions. These properties are useful in order to define the dynamic formulation of OT problems. This dynamic point of view is inspired by fluid dynamics and found its origin in the Wasserstein context with [32]. Various applications in machine learning can be derived from this formulation: interpolation along geodesic paths were used in computer graphics for color or illumination interpolations [33]. More recently, Ref. [34] used Wasserstein gradient flows in an optimization context, deriving global minima results for non-convex particles gradient descent. In [35], the authors used Wasserstein gradient flows in the context of reinforcement learning for policy optimization.

The main idea of this dynamic formulation is to describe the optimal transport problem between two measures as a curve in the space of measures minimizing its total length. We first describe some generality about geodesic spaces and recall classical results for dynamic formulation in both Wasserstein and Gromov–Wasserstein contexts. In a second part, we derive new geodesic properties in the $FGW$ context.

Geodesic spaces. Let $(X,d)$ be a metric space and $x,y$ two points in X. We say that a curve $w:[0,1]\to X$ joining the endpointsx and y (i.e., with $w(0)=x$ and $w(1)=y$) is a constant speed geodesic if it satisfies $d(w(t),w(s))\le |t-s|d(w(0),w(1))=|t-s|d(x,y)$ for $t,s\in [0,1]$. Moreover, if $(X,d)$ is a length space (i.e., if the distance between two points of X is equal to the infimum of the lengths of the curves connecting these two points) then the converse is also true and a constant speed geodesic satisfies $d(w(t),w(s))=|t-s|d(x,y)$. It is easy to compute distances along such curves, as they are directly embedded into $\mathbb{R}$.

In the Wasserstein context, if the ground space is a complete separable, locally compact length space, and if the endpoints of the geodesic are given, then there exists a geodesic curve. Moreover, if the transport between the endpoints is unique, then there is a unique displacement interpolation between the endpoints (see Corollary 7.22 and 7.23 in [15]). For example, if the ground space is ${\mathbb{R}}^d$ and the distance between the points is measured via the ${\ell }_2$ norm, then geodesics exist and are uniquely determined (this can be generalized to strictly convex costs). In the Gromov–Wasserstein context, there always exists constant speed geodesics as long as the endpoints are given. These geodesics are unique modulo the isomorphism equivalence relation (see [16]).

The $FGW$ case. In this paragraph, we suppose that $\mathsf{\Omega }={\mathbb{R}}^d$. We are interested in finding a geodesic curve in the space of structured objects i.e., a constant speed curve of structured objects joining two structured objects. As for Wasserstein and Gromov–Wasserstein, the structured object space endowed with the Fused Gromov–Wasserstein distance maintains some geodesic properties. The following result proves the existence of such a geodesic and characterizes it:

Theorem 4.

Constant speed geodesic.

Let $p\ge 1$ and $(X\times \mathsf{\Omega },d_X,{\mu }_0)$ and $(Y\times \mathsf{\Omega },d_Y,{\mu }_1)$ in ${\mathbb{S}}_p({\mathbb{R}}^d)$. Let ${\pi }^{*}$ be an optimal coupling for the Fused Gromov–Wasserstein distance between ${\mu }_0,{\mu }_1$, and $t\in [0,1]$. We equip ${\mathbb{R}}^d$ with the ${\ell }_m$ norm for $m\ge 1$.

We define ${\eta }_t:X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }\to X\times Y\times \mathsf{\Omega }$ such that:

$$\forall (x,a),(y,b)\in X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega },{\eta }_t(x,a,y,b)=(x,y,(1-t)a+tb)$$

(22)

Then:

$${\left(X\times Y\times \mathsf{\Omega },(1-t)d_X\oplus t{d}_Y,{\mu }_t={\eta }_t\#{\pi }^{*}\right)}_{t\in [0,1]}$$

(23)

is a constant speed geodesic connecting $(X\times \mathsf{\Omega },d_X,{\mu }_0)$ and $(Y\times \mathsf{\Omega },d_Y,{\mu }_1)$ in the metric space $\left({\mathbb{S}}_p({\mathbb{R}}^d),d_{FGW,\alpha ,p,1}\right)$.

Proof of the previous theorem can be found in Section 7.5. In a sense, this result combines the geodesics in the Wasserstein space and in the space of all mm-spaces, since it suffices to interpolate the distances in the structure space and the features to construct a geodesic. The main interest is that it defines the minimum path between two structured objects. For example, when considering two discrete structured objects represented by the measures $\mu ={\sum }_{i=1}^n{h}_i{\delta }_{(x_i,a_i)}$ and $\nu ={\sum }_{j=1}^m{g}_j{\delta }_{(y_j,b_j)}$, the interpolation path is given for $t\in [0,1]$ by the measure ${\mu }_t={\sum }_{i=1}^n{\sum }_{j=1}^m{\pi }^{*}(i,j){\delta }_{(x_i,y_j,(1-t)a_i+t{b}_j)}$ where ${\pi }^{*}$ is an optimal coupling for the $FGW$ distance. However this geodesic is difficult to handle in practice, since it requires the computation of the cartesian product $X\times Y$. To overcome this obstacle, an extension using theFréchet mean is defined in Section 4.2. The proper definition and properties of velocity fields associated to this geodesic is postponed to further works.

4. $\mathbf{FGW}$ in the Discrete Case

In practice, structured objects are often discrete and can be defined using the labeled graph formalism described previously. In this section, we discuss how to compute $FGW$ efficiently. We also provide an algorithm for the computation of Fréchet means.

4.1. FGW in the Discrete Case

We consider two structured objects $\mu ={\sum }_{i=1}^n{h}_i{\delta }_{(x_i,a_i)}$ and $\nu ={\sum }_{j=1}^m{g}_j{\delta }_{(y_j,b_j)}$, as described previously. We note $M_{AB}$ the matrix $M_{AB}(i,j)=d(a_i,b_j)$ and $C_1,C_2$ the matrices $C_1(i,k)=d_X(x_i,x_k)$, $C_2(j,l)=d_Y(y_j,y_l)$ (see Figure 9). The Fused Gromov–Wasserstein distance is defined as

$$d_{FGW,\alpha ,p,q}(\mu ,\nu )={\left(\underset{\pi \in \mathsf{\Pi }(h,g)}{min}{E}_{p,q,\alpha }(\pi )\right)}^{\frac{1}{p}}$$

(24)

where:

$$E_{p,q,\alpha }(\pi )=\sum _{i,j,k,l}{\left((1-\alpha )M_{AB}{(i,j)}^q+\alpha {|C_1(i,k)-C_2(j,l)|}^q\right)}^p{\pi }_{i,j}{\pi }_{k,l}.$$

Solving the related Quadratic Optimization problem. Equation (24) is clearly a quadratic problem w.r.t. $\pi$. Note that, despite the apparent $\mathcal{O}(m^2{n}^2)$ complexity of computing the tensor product, one can simplify the sum to complexity $\mathcal{O}(m{n}^2+m^{2}n)$ [26] when considering $p=1,q=2$. In this case, the $FGW$ computation problem can be re-written as finding ${\pi }^{*}$, such that:

$${\pi }^{*}=\underset{\pi \in \mathsf{\Pi }(h,g)}{argmin}\mathrm{vec}{(\pi )}^{T}Q(\alpha )\mathrm{vec}(\pi )+\mathrm{vec}{(D(\alpha ))}^T\mathrm{vec}(\pi )$$

(25)

where $Q=-2\alpha C_2{\otimes }_K{C}_1$ and $D(\alpha )=(1-\alpha )M_{AB}$. ${\otimes }_K$ denote the Kronecker product of two matrices, vec the column-stacking operator. With such form, the resulting optimal map can be seen as a quadratic regularized map from initial Wasserstein [36,37]. However, unlike these approaches, we have a quadratic but probably non-convex term. The gradient G that arises from Equation (24) can be expressed with the following partial derivative w.r.t.$\pi$:

$$G=(1-\alpha )M_{AB}^q+2\alpha {\left(\sum _{k,l}{|C_1(i,k)-C_2(j,l)|}^q{\pi }_{k,l}\right)}_{i,j}$$

(26)

Solving a large scale QP with a classical solver can be computationally expensive. In [36], the authors propose a solver for a graph regularized optimal transport problem whose resulting optimization problem is also a QP. We can then directly use their conditional gradient defined in Algorithm 1 to solve our optimization problem. It only needs at each iteration to compute the gradient in Equation (26) and solve a classical OT problem for instance with a network flow algorithm. The line-search part is a constrained minimization of a second degree polynomial function that is adapted to the non convex loss in Algorithm 2. While the problem is non convex, conditional gradient is known to converge to a local stationary point [38]. When $C_1,C_2$ are squared Euclidean distance matrices the problem reduces to a concave graph matching so that the line-search of the conditional gradient Algorithm 1 always leads to 1 [39,40].

Algorithm 1. Conditional Gradient (CG) for $FGW$.

1: ${\pi }^{(0)}\leftarrow {\mu }_X{\mu }_Y^{\top }$ 2: for$i=1,\dots ,$do 3:     $G\leftarrow$ Gradient from Equation (26) w.r.t.${\pi }^{(i-1)}$ 4:     ${\tilde{\pi }}^{(i)}\leftarrow$ Solve OT with ground loss G 5:     ${\tau }^{(i)}\leftarrow$ Line-search for loss (24) with $\tau \in (0,1)$ using Algorithm 2 6:     ${\pi }^{(i)}\leftarrow (1-{\tau }^{(i)}){\pi }^{(i-1)}+{\tau }^{(i)}{\tilde{\pi }}^{(i)}$ 7: end for

Algorithm 2. Line-search for CG ($q=2$).

1: $c_{C_1,C_2}$ from Equation (6) in [26] 2: $a=-2\alpha \langle C_1{\tilde{\pi }}^{(i)}{C}_2,{\tilde{\pi }}^{(i)}\rangle$ 3: $b=\langle (1-\alpha )M_{AB}+\alpha c_{C_1,C_2},{\tilde{\pi }}^{(i)}\rangle$$-2\alpha \left(\langle C_1{\tilde{\pi }}^{(i)}{C}_2,{\pi }^{(i-1)}\rangle +\langle C_1{\pi }^{(i-1)}{C}_2,{\tilde{\pi }}^{(i)}\rangle \right)$ 4: if$a>0$then 5:     ${\tau }^{(i)}\leftarrow \min (1,\max (0,\frac{-b}{2a}))$ 6: else 7:     ${\tau }^{(i)}\leftarrow 1$ if $a+b<0$ else ${\tau }^{(i)}\leftarrow 0$ 8: end if

4.2. Structured Optimal Transport Barycenter

An interesting use of the $FGW$ distance is to define a barycenter of a set of structured data as a Fréchet mean. In that context, one seeks the structured object that minimizes the sum of the (weighted) $FGW$ distances with a given set of objects. OT barycenters have many desirable properties and applications [26,41], yet no formulation can leverage both structural and feature information in the barycenter computation. Here, we propose to use the $FGW$ distance to compute the barycenter of a set of K structured objects ${({\mu }_k)}_k\in \mathbb{S}{(\mathsf{\Omega })}^K$ associated with structures ${(C_k)}_k$, features ${(B_k)}_k$ and base histograms ${(h_k)}_k$.

We suppose that the feature space is $\mathsf{\Omega }=({\mathbb{R}}^d,{\ell }_2)$ and $p=1$. For simplicity, we assume that the base histograms and the histogram h associated to the barycenter are known and fixed. Note that it could be also included in the optimization process, as suggested in [26].

In this context, for a fixed $N\in \mathbb{N}$ and ${({\lambda }_k)}_k$, such that ${\sum }_k{\lambda }_k=1$, we aim to find:

$$\underset{\mu }{\min }\sum _k{\lambda }_k{d}_{FGW,\alpha ,1,q}(\mu ,{\mu }_k)=\underset{C,A\in {\mathbb{R}}^{N\times d},{({\pi }_k)}_k}{\min }\sum _k{\lambda }_k{E}_{1,q,\alpha }(M_{A{B}_k},C,C_k,{\pi }_k)$$

(27)

Note that this problem is convex w.r.t. C and A, but not w.r.t.${\pi }_k$. Intuitively, looking for a barycenter means finding feature values supported on a fixed size support, and the structure that relates them. Interestingly enough, there are several variants of this problem, where features or structure can be fixed for the barycenter. Solving the related simpler optimization problems extend straightforwardly.

Solving the barycenter problem with Block Coordinate Descent (BCD). We propose minimizing Equation (27) using a BCD algorithm, i.e., iteratively minimizing with respect to the couplings ${\pi }_k$, the structure metric C and the feature vector A.The minimization of this problem w.r.t.${({\pi }_k)}_k$ is equivalent to computing K independent Fused Gromov–Wasserstein distances using the algorithm presented above. We suppose that the feature space is $\mathsf{\Omega }=({\mathbb{R}}^d,{\ell }_2)$ and we consider $q=2$. Minimization w.r.t. C in this case has a closed form (see Prop. 4 in [26]):

$$C\leftarrow \frac{1}{h{h}^T}{\sum }_k{\lambda }_k{\pi }_k^T{C}_k{\pi }_k$$

(28)

where h is the histogram of the barycenter and the division is computed pointwise. Minimization w.r.t. A can be computed with (Equation (8) in [42]):

$$A\leftarrow \sum _k{\lambda }_k{B}_k{\pi }_k^T\mathrm{diag}\left(\frac{1}{h}\right).$$

(29)

5. Examples and Applications

In this section we derive some applications of $FGW$ in graph contexts such as classification, clustering and coarsening of graphs.

5.1. Illustrations of FGW

In this section, we present several applications of $FGW$ as a distance between structured objects and provide an interpretation of the OT matrix.

Example with one-dimensional (1D) features and structure spaces.Figure 10 illustrates the differences between Wasserstein, Gromov–Wasserstein, and Fused Gromov–Wasserstein couplings ${\pi }^{*}$. In this example, both the feature and structure space are one-dimensional (Figure 10 left). The feature space (vertical axis) denotes two clusters among the elements of both objects illustrated in the OT matrix $M_{AB}$, the structure space (horizontal axis) denotes a noisy temporal sequence along the indexes illustrated in the matrices $C_1$ and $C_2$ (Figure 10 center). Wasserstein respects the clustering, but forgets the temporal structure, Gromov–Wasserstein respects the structure, but do not take the clustering into account. Only FGW retrieves a transport matrix respecting both feature and structure.

Example on two simple images. We extract a $28\times 28$ image from the MNIST dataset and generate a second one through translation or mirroring of the digit in the original image. We use pixel gray levels of the pixels as the features, and the structure is defined as the city-block distance on the pixel coordinate grid. We use equal weights for all of the pixels in the image. Figure 11 shows the different couplings obtained when only considering either the features, the structure only or both information. $FGW$ aligns the pixels of the digits, recovering the correct order of the pixels, while both Wassertein and Gromov–Wasserstein distances fail at providing a meaningful transportation map. Note that in the Wasserstein and Gromov-Wasserstein case, the distances are equal to 0, whereas $FGW$ manages to spot that the two images are different. Additionally, note that, in the $FGW$ sense, the original digit and its mirrored version are also equivalent as there exists an isometry between their structure spaces, making $FGW$ invariant to rotations or flips in the structure space in this case.

Example on time series data. One of the main assets of $FGW$ is that it can be used on a wide class of objects and time series are one more example of this. We consider here 25 monodimensional time series composed of two humps in $[0,1]$ with random uniform height between 0 and 1. The signals are distributed according to two classes translated from each other with a fixed gap. The $FGW$ distance is computed by considering d as the euclidean distance between the features of the signals (here the value of the signal in each point) and $d_X$ and $d_Y$ as the euclidean distance between timestamps.

A two-dimensional (2D) embedding is computed from a $FGW$ distance matrix between a number of examples in this dataset with multidimensional scaling (MDS) [43] in Figure 12 (top). One can clearly see that the representation with a reasonable $\alpha$ value in the center is the most discriminant one. This can be better understood by looking as the OT matrices between the classes. Figure 12 (bottom) illustrates the behavior of $FGW$ on one pair of examples when going from Wasserstein to Gromov–Wasserstein. The black line depicts the matching provided by the transport matrix and one can clearly see that while Wasserstein on the left assigns samples completely independently to their temporal position, the Gromov-Wasserstein on the right tends to align perfectly the samples (note that it could have reversed exactly the alignment with the same loss), but discards the values in the signal. Only the true $FGW$ in the center finds a transport matrix that both respects the time sequences and aligns similar values in the signals.

5.2. Graph-Structured Data Classification

In this section, we adress the question of training a classifier for graph data and evaluate the FGW distance used in a kernel with SVM.

Learning problem and datasets. We consider 12 widely used benchmark datasets divided into 3 groups. BZR, COX2 [44], PROTEINS, ENZYMES [45], CUNEIFORM [46] and SYNTHETIC [47] are vector attributed graphs. MUTAG [48], PTC-MR [49], and NCI1 [50] contain graphs with discrete attributes derived from small molecules. IMDB-B, IMDB-M [51] contain unlabeled graphs derived from social networks. All of the datasets are available in [52].

Experimental setup. Regarding the feature distance matrix $M_{AB}$ between node features, when dealing with real valued vector attributed graphs, we consider the ${\ell }_2$ distance between the labels of the vertices. In the case of graphs with discrete attributes, we consider two settings: in the first one, we keep the original labels (denoted as raw); we also consider a Weisfeiler-Lehman labeling (denoted as wl) by concatenating the labels of the neighbors. A vector of size h is created by repeating this procedure h times [49,53]. In both cases, we compute the feature distance matrix by using $d(a_i,b_j)={\sum }_{k=0}^H\delta (\tau (a_i^k),\tau (b_j^k))$ where $\delta (x,y)=1$ if $x\ne y$ else $\delta (x,y)=0$ and $\tau (a_i^k)$ denotes the concatenated label at iteration k (for $k=0$ original labels are used). Regarding the structure distances C, they are computed by considering a shortest path distance between the vertices.

For the classification task, we run a SVM using the indefinite kernel matrix $e^{-\gamma FGW}$, which is seen as a noisy observation of the true positive semidefinite kernel [54]. We compare classification accuracies with the following state-of-the-art graph kernel methods: (SPK) denotes the shortest path kernel [45], (RWK) the random walk kernel [55], (WLK) the Weisfeler Lehman kernel [53], and (GK) the graphlet count kernel [56]. For real valued vector attributes, we consider the HOPPER kernel (HOPPERK) [47] and the propagation kernel (PROPAK) [57]. We build upon the GraKel library [58] to construct the kernels and C-SVM to perform the classification. We also compare $FGW$ with the PATCHY-SAN framework for CNN on graphs (PSCN) [9] building on our own implementation of the method.

To provide a comparison between the methods, most of the papers about graph classification usually perform a nested cross validation (using nine-fold for training, one for testing, and reporting the average accuracy of this experiment repeated 10 times), and report accuracies of the other methods taken from the original papers. However, these comparisons are not fair because of the high variance (on most datasets) w.r.t. the folds chosen for training and testing. This is why, in our experiments, the nested cross validation is performed on the same folds for training and testing for all methods [59]. In the result,

Table 1. Average classification accuracy on the graph datasets with vector attributes.

Vector Attributes	BZR	COX2	CUNEIFORM	ENZYMES	PROTEIN	SYNTHETIC
FGW sp	85.12 ± 4.15 *	77.23 ± 4.86	76.67 ± 7.04	71.00 ± 6.76	74.55 ± 2.74	100.00 ± 0.00
HOPPERK	84.15 ± 5.26	79.57 ± 3.46	32.59 ± 8.73	45.33 ± 4.00	71.96 ± 3.22	90.67 ± 4.67
PROPAK	79.51 ± 5.02	77.66 ± 3.95	12.59 ± 6.67	71.67 ± 5.63 *	61.34 ± 4.38	64.67 ± 6.70
PSCN k = 10	80.00 ± 4.47	71.70 ± 3.57	25.19 ± 7.73	26.67 ± 4.77	67.95 ± 11.28	100.00 ± 0.00
PSCN k = 5	82.20 ± 4.23	71.91 ± 3.40	24.81 ± 7.23	27.33 ± 4.16	71.79 ± 3.39	100.00 ± 0.00

,

Table 2. Average classification accuracy on the graph datasets with discrete attributes.

Discrete Attr.	MUTAG	NCI1	PTC-MR
FGW raw sp	83.26 ± 10.30	72.82 ± 1.46	55.71 ± 6.74
FGW wl h = 2 sp	86.42 ± 7.81	85.82 ± 1.16	63.20 ± 7.68
FGW wl h = 4 sp	88.42 ± 5.67	86.42 ± 1.63	65.31 ± 7.90
GK k = 3	82.42 ± 8.40	60.78 ± 2.48	56.46 ± 8.03
RWK	79.47 ± 8.17	58.63 ± 2.44	55.09 ± 7.34
SPK	82.95 ± 8.19	74.26 ± 1.53	60.05 ± 7.39
WLK	86.21 ± 8.48	85.77 ± 1.07	62.86 ± 7.23
WLK h=2	86.21 ± 8.15	81.85 ± 2.28	61.60 ± 8.14
WLK h = 4	83.68 ± 9.13	85.13 ± 1.61	62.17 ± 7.80
PSCN k = 10	83.47 ± 10.26	70.65 ± 2.58	58.34 ± 7.71
PSCN k = 5	83.05 ± 10.80	69.85 ± 1.79	55.37 ± 8.28

and

Table 3. Average classification accuracy on the graph datasets with no attributes.

Without Attribute	IMDB-B	IMDB-M
GW sp	63.80 ± 3.49	48.00 ± 3.22
GK k = 3	56.00 ± 3.61	41.13 ± 4.68
SPK	55.80 ± 2.93	38.93 ± 5.12

, we write in bold the best score for each dataset and we add a (*) when the best score does not yield to a significative improvement (based on a Wilcoxon signed rank test on the test scores) compared to the second best one. Note that, because of their small sizes, we repeat the experiments 50 times for MUTAG and PTC-MR datasets. For all methods using SVM, we cross validate the parameter $C\in \{{10}^{-7},{10}^{-6},\dots ,{10}^7\}$. The range of the WL parameter h is $\{0,1\dots ,10\}$, and we also compute this kernel with h fixed at $2,4$. The decay factor $\lambda$ for RWK $\{{10}^{-6},{10}^{-5}\dots ,{10}^{-2}\}$, for the GK kernel we set the graphlet size $\kappa =3$ and cross validate the precision level $ϵ$ and the confidence $\delta$ as in the original paper [56]. The $t_{\max }$ parameter for PROPAK is chosen within $\{1,3,5,8,10,15,20\}$. For PSCN, we choose the normalized betweenness centrality as labeling procedure and cross validate the batch size in $\{10,15,\dots ,35\}$ and number of epochs in $\{10,20,\dots ,100\}$. Finally, for $FGW$, $\gamma$ is cross validated within $\{2^{-10},2^{-9},\dots ,2^{10}\}$ and $\alpha$ is cross validated via a logspace search in $[0,0.5]$ and symmetrically $[0.5,1]$ (15 values are drawn).

Vector attributed graphs. The average accuracies reported in Table 1 show that FGW is a clear state-of-the-art method and performs best on four out of six datasets with performances in the error bars of the best methods on the other two datasets. The results for CUNEIFORM are significantly below those from the original paper [46], which can be explained by the fact that the method in this paper uses a graph convolutional approach specially designed for this dataset and that experiment settings are different. In comparison, the other competitive methods are less consistent, as they exhibit some good performances on some datasets only.

Discrete labeled graphs. We first note in Table 2 that $FGW$ using WL attributes outperforms all competitive methods, including $FGW$ with raw features. Indeed, the WL attributes allow for more finely encoding the neighborood of the vertices by stacking their attributes, whereas FGW with raw features only consider the shortest path distance between vertices, not their sequence of labels. This result calls for using meaningful feature and/or structure matrices in the FGW definition, which can be dataset-dependant, in order to enhance the performances. We also note that $FGW$ with WL attributes outperforms the WL kernel method, highlighting the benefit of an optimal transport-based distance over a kernel-based similarity. Surprisingly, the results of PSCN are significantly lower than those from the original paper. We believe that it comes from the difference between the fold assignment for training and testing, which suggests that PSCN is difficult to tune.

Non-attributed graphs. The particular case of the GW distance for graph classification is also illustrated on social datasets, which contain no labels on the vertices. Note that no artificial features were added to these datasets. Accuracies reported in Table 3 show that it greatly outperforms the SPK and GK graph kernel methods. This is, to the best of our knowledge, the first application of the Gromov–Wasserstein distance for social graph classification and it highlights the fact that $GW$ is a good metric for comparing the graph structures.

Comparison between $FGW$, W and $GW$. During the validation step, the optimal value of $\alpha$ was consistently selected inside the $]0,1[$ interval, i.e., excluding 0 and 1, suggesting that both structure and feature information are necessary.

5.3. Graph Barycenter and Compression

In this experiment, we use $FGW$ to compute barycenters and approximations of toy graphs. In the first example, we generate graphs following either a circle or 8 symbol with 1D features following a sine and linear variation, respectively. For each example, the number of nodes is drawn randomly between 10 and 25, Gaussian noise is added to the features and a small noise is applied to the structure (some connections are randomly added). An example graph with no noise is provided for each class in the first column of Figure 13. One can see from there that the circle class has a feature varying smoothly (sine) along the graph, but the 8 has a sharp feature change at its center (so that low pass filtering would loose some information). Some examples of the generated graphs are provided in the 2nd-to-7th columns of Figure 13. We compute the $FGW$ barycenter containing 10 samples while using the shortest path distance between the nodes as the structural information and the ${\ell }_2$ distance for the features. We recover an adjacency matrix by thresholding the similarity matrix C given by the barycenter. The threshold is tuned, so as to minimize the Frobenius norm between the original C matrix and the shortest path matrix constructed after thresholding C. Resulting barycenters are showed in Figure 13 for $n=15$ and $n=7$ nodes. First, one can see that the barycenters are denoised in both the feature space and structure space. Also note that the sharp change at the center of the 8 class is conserved in the barycenters, which is a nice result when compared to other divergences that tend to smooth-out their barycenters (${\ell }_2$, for instance). Finally, note that, by selecting the number of nodes in the barycenter, one can compress the graph or estimate a “high resolution” representation from all the samples. To the best of our knowledge, no other method can compute such graph barycenters. Finally, note that $FGW$ is interpretable, because the resulting OT matrix provides correspondence between the nodes from the samples and those from the barycenter.

In the second experiment, we evaluate the ability of FGW to perform graph approximation and compression on a Stochastic Block Model graph [60,61]. The question is to see whether estimating an approximated graph can recover the relation between the blocks and perform simultaneously a community clustering on the original graph (using the OT matrix). We generate two community graphs illustrated in the left column of Figure 14. We can see that the relation between the blocks is sparse and has a “linear” structure, the example in the first line has features that follow the blocks (noisy but similar in each block) whereas the example in the second line has two modes per block. The first graph approximation (top line) is done with four nodes and we can recover both the blocks in the graph and the average feature on each blocks (colors on the nodes). The second problem is more complex due to the two modes per block but one can see that when approximating the graph with eight nodes we recover both the structure between the blocks and the sub-clusters in each block, which illustrates the strength of $FGW$ that encodes both features and structures.

5.4. Unsupervised Learning: Graphs Clustering

In the last experiment, we evaluate the ability of $FGW$ to perform a clustering of multiple graphs and to retrieve meaningful barycenters of such clusters. To do so, we generate a dataset of four groups of community graphs. Each graph follows a simple Stochastic Block Model [60,61] and the groups are defined w.r.t. the number of communities inside each graph and the distribution of their labels. More precisely, labels are drawn from a 1D gaussian distribution specific to each community: each feature of a node is drawn from a law $\mathcal{N}(n_{c_1}+n_{c_2},\sigma )$, where $n_{c_1}$ is the index of the community and $n_{c_2}\in \{0,1\}$ to create two modes per community. The dataset is composed of 40 graphs (10 graphs per group) and the number of nodes of each graph is drawn randomly from $\{20,30,\dots ,50\}$, as illustrated in Figure 15. We perform a k-means clustering using the $FGW$ barycenter defined in Equation (27) as the centroid of the groups and the $FGW$ distance for the cluster assignment. We set the number of nodes of each centroid to 30. We perform a thresholding on the pairwise similarity matrix C of the centroid at the end in order to obtain an adjacency matrix for visualization purposes. The threshold value is chosen, so as to minimize the distance that is induced by the Frobenius norm between the original matrix C and the shortest path matrix obtained from the adjacency matrix. The evolution of the barycenters along the iterations is reported in Figure 15. We can see that these centroids recover community structures and feature distributions that are representative of their cluster content. On this example, note that the clustering perfectly recovers the known groups in the dataset. To the best of our knowledge, there exists no other method that is able to perform a clustering of graphs of arbitrary size and to retrieve the average graph in each cluster without having to solve a pre-image problem.

6. Conclusions

This paper presents the Fused Gromov–Wasserstein ($FGW$) distance. Inspired by both Wasserstein and Gromov–Wasserstein distances, $FGW$ can compare structured objects by including the inherent relations that exist between the elements of the objects, constituting their structure information, and their feature information, part of a common ground space between each structured objects. We have stated mathematical results about this new distance, such as metric, interpolation, and geodesic properties. We have also provided a concentration result for the convergence of finite samples. In the discrete case, algorithms to compute $FGW$ itself and related Fréchet means are provided. The use of this new distance is illustrated on problems involving structured objects, such as time series embedding, graph classification, graph barycenter computation, and graph clustering. Several questions are raised by this work. From a practical side, the FGW method is quite expensive to compute and further works will try to lower the computational complexity of the underlying optimization problem to ensure better scalability to very large graphs. Moreover, while we mostly consider in this work structure of graphs described by the shortest path, other choices could be made, such as the distances based on the Laplacian of the graph. Finally, from a theoretical point of view, it is often valuable that the geodesic path be unique, so as to defined properly objects, such as gradient flows. One interesting result would be, for example, to see if the geodesic is unique with respect to the strong isomorphism relation.

7. Proofs of the Mathematical Properties

This section presents all of the proofs of previous theorems and results. We note $P_i\#\mu$ the projection on the i-th marginal of $\mu$. We will frequently use the following lemma:

Lemma 2.

Let $q\ge 1$. We have:

$$\forall x,y\in {\mathbb{R}}_{+},{(x+y)}^q\le 2^{q-1}(x^q+y^q).$$

(30)

Proof. 

Indeed, if $q>1$

${(x+y)}^q={\left({(\frac{1}{2^{q-1}})}^{\frac{1}{q}}\frac{x}{{(\frac{1}{2^{q-1}})}^{\frac{1}{q}}}+{(\frac{1}{2^{q-1}})}^{\frac{1}{q}}\frac{y}{{(\frac{1}{2^{q-1}})}^{\frac{1}{q}}}\right)}^q\le {\left[{(\frac{1}{2^{q-1}})}^{\frac{1}{q-1}}+{(\frac{1}{2^{q-1}})}^{\frac{1}{q-1}}\right]}^{q-1}\left(\frac{x^q}{\frac{1}{2^{q-1}}}+\frac{y^q}{\frac{1}{2^{q-1}}}\right)=\frac{x^q}{\frac{1}{2^{q-1}}}+\frac{y^q}{\frac{1}{2^{q-1}}}.$

Last inequality is a consequence of HÃlder inequality. The result remains valid for $q=1$. □

7.1. Proof of Proposition 1—Comparison between FGW, GW and W

Proof. 

Of the Proposition.

For the two inequalities (9) and (10), let $\pi$ be an optimal coupling for the Fused Gromov-Wasserstein distance between $\mu$ and $\nu$ (assuming its existence for now). Clearly:

$$\begin{array}{cc}\hfill d_{FGW,\alpha ,p,q}(\mu ,\nu )& ={\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & \ge {\left(\underset{X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }}{\int }{(1-\alpha )}^{p}d{(a,b)}^{pq}d\pi ((x,a),(y,b))\right)}^{\frac{1}{p}}=(1-\alpha ){\left(\underset{\mathsf{\Omega }\times \mathsf{\Omega }}{\int }d{(a,b)}^{pq}d{P}_{2,4}\#\pi (a,b)\right)}^{\frac{1}{p}}\hfill \end{array}$$

Becasue $\pi \in \mathsf{\Pi }(\mu ,\nu )$ the coupling $P_{2,4}\#\pi$ is in $\mathsf{\Pi }({\mu }_A,{\nu }_B)$. So by suboptimality:

$$d_{FGW,\alpha ,p,q}(\mu ,\nu )\ge (1-\alpha ){(d_{W,pq}({\mu }_A,{\nu }_B))}^q$$

which proves Equation (9). Same reasoning is used for Equation (10).

For the last inequality (11), let $\pi \in \mathsf{\Pi }(\mu ,\nu )$ be any admissible coupling. By suboptimality:

$$\begin{array}{cc}& d_{FGW,\alpha ,p,1}(\mu ,\nu )\le {\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d(a,b)+\alpha |d_Z(x,x^{\prime })-d_Z(y,y^{\prime })|\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & \stackrel{(*)}{\le }{\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d(a,b)+\alpha d_Z(x,y)+\alpha d_Z(x^{\prime },y^{\prime })\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & \le {\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d(a,b)+\alpha d_Z(x,y)+(1-\alpha )d(a^{\prime },b^{\prime })+\alpha d_Z(x^{\prime },y^{\prime })\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & \stackrel{(**)}{\le }2{\left(\underset{X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }}{\int }{\left((1-\alpha )d(a,b)+\alpha d_Z(x,y)\right)}^{p}d\pi ((x,a),(y,b))\right)}^{\frac{1}{p}}\hfill \end{array}$$

(*) is the triangle inequality of $d_Z$ and (**) Minkowski inequality. Since this inequality is true for any admissible coupling $\pi$ we can apply it with the optimal coupling for the Wasserstein distance defined in the proposition and the claim follows. □

7.2. Proof of Theorem 1—Metric Properties of FGW

We prove the theorem point by point: first the existence, then the equality relation and finally the triangle inequality statement. We first recall the definition of weak convergence of probability measure in a metric space [62]:

Definition 10.

(Weak-convergence on a metric space). Let ${({\mu }_n)}_{n\in \mathbb{N}}$ be a sequence of probability measures on $(X,\mathcal{B}(d))$ where $(X,d)$ is a completely metrizable topological space (Polish space) and $\mathcal{B}(d)$ is the Borel σ algebra. We say that ${({\mu }_n)}_{n\in \mathbb{N}}$ converges weakly to μ in $(X,\mathcal{B}(d))$ if for all continuous and bounded functions $f:X\to R$:

$${\int }_{X}fd{\mu }_n\to {\int }_{X}fd\mu$$

(31)

We also recall the definition of semi continuity in a metric space:

Definition 11.

(Lower-semi continuity). On a metric space $(X,d)$ a function $f:X\to \mathbb{R}\cup \{+\infty \}$ is said to be lower semi-continuous (l.s.c.) if for every sequence $x_n\to x$ we have $f(x)\le liminff(x_n)$.

To state the existence of a minimizer, we will rely on the following lemma:

Lemma 3.

Let W be a Polish space. If $f:W\times W\to {\mathbb{R}}_{+}\cup +\infty$ is lower semi-continuous, then the functional $J:\mathcal{P}(W)\to \mathbb{R}\cup +\infty$ with $J(\mu )=\int \int f(w,w^{\prime })d\mu (w)d\mu (w^{\prime })$ is l.s.c. for the weak convergence of measures.

Proof. 

f is l.s.c. and bounded from below by 0. We can consider ${(f_k)}_k$ a sequence of continuous and bounded functions converging increasingly to f (see e.g., [63]). By the monotone convergence theorem $J_k(\mu )\to J(\mu )\stackrel{def}{=}{sup}_k{J}_k(\mu )={sup}_k\int \int f_{k}d\mu d\mu$.

Moreover every $J_k$ is continuous for the weak convergence. Using Theorem 2.8 [62] on the Polish space $W\times W$ we know that if ${\mu }_n$ converges weakly to $\mu$ then the product measure ${\mu }_n\otimes {\mu }_n$ converges weakly to $\mu \otimes \mu$. In this way ${lim}_{n\to \infty }{J}_k({\mu }_n)=J_k(\mu )$ since $f_k$ are continuous and bounded. In particular every $J_k$ is l.s.c.

We can conclude that J is l.s.c. as the supremum of l.s.c. functionals on the metric space of $(\mathcal{P}(W),\delta )$ (see e.g., [63]). Here we equipped $\mathcal{P}(W)$ with a metric $\delta$ as e.g., $\delta (\mu ,\nu )={\sum }_{k=1}^{\infty }{2}^{-k}|{\int }_W{f}_{k}d\mu -{\int }_W{f}_{k}d\nu |$ (see Remark 5.11 in [64]). □

Proposition 2.

Existence of an optimal coupling for the $FGW$ distance. For $p,q\ge 1$, $\pi \to E_{p,q,\alpha }(\pi )$ always achieves a infimum ${\pi }^{*}$ in $\mathsf{\Pi }(\mu ,\nu )$ such that $d_{FGW,\alpha ,p,q}(\mu ,\nu )=E_{p,q,\alpha }({\pi }^{*})<+\infty$.

Proof. 

Since $X\times \mathsf{\Omega }$ and $Y\times \mathsf{\Omega }$ are Polish spaces we known that $\mathsf{\Pi }(\mu ,\nu )\subset \mathcal{P}(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })$ is compact (Theorem 1.7 in [63]), so by applying Weierstrass theorem we can conclude that the infimum is attained at some ${\pi }^{*}\in \mathsf{\Pi }(\mu ,\nu )$ if $\pi \to E_{p,q,\alpha }(\pi )$ is l.s.c.

We will use Lemma 3 to prove that the functionnal is l.s.c. on $\mathsf{\Pi }(\mu ,\nu )$. If we consider $W=X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }$ which is a a metric space endowed with the distance $d_X\oplus d\oplus d_Y\oplus d$ and $f((w=(x,a,y,b),w^{\prime }=(x^{\prime },a^{\prime },y^{\prime },b^{\prime }))={((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q)}^p$ then f is l.s.c. by continuity of d, $d_X$ and $d_Y$. With the previous reasoning we can conclude that the infimum is attained. Finally finiteness come from:

$$\begin{array}{cc}\hfill & \underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \\ \hfill & \stackrel{*}{\le }\int 2^{p-1}(1-\alpha )d{(a,b)}^{qp}d{\mu }_A(a)d\nu (b)+\int 2^{p-1}\alpha L{(x,y,x^{\prime },y^{\prime })}^{qp}d{\mu }_X(x)d{\mu }_X(x^{\prime })d{\nu }_Y(y^{\prime })d{\nu }_Y(y^{\prime })\hfill \\ \hfill & \stackrel{**}{<}+\infty \hfill \end{array}$$

(32)

where in (*) we used Lemma 30 and in (**) that $\mu ,\nu$ are in ${\mathbb{S}}_{pq}(\mathsf{\Omega })$. □

Proposition 3.

Equality relation. For $\alpha \in ]0,1[$, $d_{FGW,\alpha ,p,q}(\mu ,\nu )=0$ if an only if there exists a bijective function $f=(f_1,f_2):supp(\mu )\to supp(\nu )$ such that:

$$f\#\mu =\nu$$

(33)

$$\forall (x,a)\in supp(\mu ),f_2(x,a)=a$$

(34)

$$\forall (x,a),(x^{\prime },a^{\prime })\in supp{(\mu )}^2,d_X(x,x^{\prime })=d_Y(f_1(x,a),f_1(x^{\prime },a^{\prime }))$$

(35)

Moreover if $(\mu ,\nu )$ are generalized labeled graphs then $d_{FGW,\alpha ,p,q}(\mu ,\nu )=0$ if and only if $(X,d_X,\mu )$ and $(Y,d_Y,\nu )$ are strongly isomorphic.

Proof. 

For the first point, let us assume that there exists a function f verifying (33)–(35). We consider the map $\pi =(I_d\times f)\#\mu \in \mathsf{\Pi }(\mu ,\nu )$. We note $f=(f_1,f_2)$. Then:

$$\begin{array}{cc}\hfill E_{p,q,\alpha }(\pi )& =\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L({(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \\ & =\underset{{(X\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,f_2(x,a))}^q+\alpha L{\left((x,f_1(x,a),x^{\prime },f_1(x^{\prime },a^{\prime })\right)}^q\right)}^{p}d\mu (x,a)d\mu (x^{\prime },a^{\prime })\hfill \\ & =\underset{{(X\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,f_2(x,a))}^q+\alpha {|d_X(x,x^{\prime })-d_Y(f_1(x,a),f_1(x^{\prime },a^{\prime }))|}^q\right)}^{p}d\mu (x,a)d\mu (x^{\prime },a^{\prime })\hfill \\ & =0\hfill \end{array}$$

(36)

Conversely, suppose that $d_{FGW,\alpha ,p,q}(\mu ,\nu )=0$. To prove the existence of a map $f:\mathrm{supp}(\mu )\to \mathrm{supp}(\nu )$ verifying (33)–(35) we will use the Gromov-Wasserstein properties. We are looking for a vanishing Gromov-Wassersein distance between the spaces $X\times \mathsf{\Omega }$ and $Y\times \mathsf{\Omega }$ equipped with our two measures $\mu$ and $\nu$.

More precisely, we define for $\left((x,a),(y,b),(x^{\prime },a^{\prime }),(y^{\prime },b^{\prime })\right)\in {(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2$ and $\beta \in ]0,1[$:

$$d_{X\times \mathsf{\Omega }}\left((x,a),(x^{\prime },a^{\prime })\right)=(1-\beta )d_X(x,x^{\prime })+\beta d(a,a^{\prime })$$

and

$$d_{Y\times \mathsf{\Omega }}\left((y,b),(y^{\prime },b^{\prime })\right)=(1-\beta )d_Y(y,y^{\prime })+\beta d(b,b^{\prime })$$

We will prove that $d_{GW,p}(d_{X\times \mathsf{\Omega }},d_{Y\times \mathsf{\Omega }},\mu ,\nu )=0$. To show that we will bound the Gromov cost with the metrics $d_{X\times \mathsf{\Omega }},d_{Y\times \mathsf{\Omega }}$ by the Gromov cost with the metrics $d_X,d_Y$ and a Wasserstein cost.

Let $\pi \in \mathsf{\Pi }(\mu ,\nu )$ be any admissible transportation plan. Subsequently, for $n\ge 1$:

$$\begin{array}{cc}\hfill & J_n(d_{X\times \mathsf{\Omega }},d_{Y\times \mathsf{\Omega }},\pi )\stackrel{def}{=}\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }L{(x,y,x^{\prime },y^{\prime })}^{n}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \\ \hfill & =\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{|(1-\beta )(d_X(x,x^{\prime })-d_Y(y,y^{\prime }))+\beta (d(a,a^{\prime })-d(b,b^{\prime }))|}^{n}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \\ \hfill & \le \underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }(1-\beta ){|d_X(x,x^{\prime })-d_Y(y,y^{\prime })|}^{n}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \\ \hfill & +\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }\beta {|d(a,a^{\prime })-d(b,b^{\prime })|}^{n}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \end{array}$$

using Jensen inequality with convexity of $t\to t^n$ and subadditivity of |.|. We note $(*)$ the first term above and $(**)$ the second term above. By the triangle inequality property of d we have:

(**) $\le \beta \underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }(d(a,b)+d(a^{\prime },b^{\prime }){)}^{n}d\pi ((x,a),(y,b))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\stackrel{def}{=}\beta M_n(\pi )$ such that we have shown:

$$\forall \pi \in \mathsf{\Pi }(\mu ,\nu ),\forall n\ge 1,J_n(d_{X\times \mathsf{\Omega }},d_{Y\times \mathsf{\Omega }},\pi )\le (1-\beta )J_n(d_X,d_Y,\pi )+\beta M_n(\pi )$$

(37)

Now let ${\pi }_{*}$ be an optimal coupling for $d_{FGW,\alpha ,p,q}$ between $\mu$ and $\nu$. By hypothesis $d_{FGW,\alpha ,p,q}(\mu ,\nu )=0$ so that:

$$J_{qp}(d_X,d_Y,\pi *)=0$$

(38)

and:

$$H_{qp}({\pi }^{*})=0.$$

(39)

Subsequently, $\underset{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}{\int }d{(a,b)}^{qp}d{\pi }^{*}((x,a),(y,b))=0$ which implies that d is zero ${\pi }^{*}$a.e. so that $\underset{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}{\int }d{(a,b)}^{m}d{\pi }^{*}((x,a),(y,b))=0$ for any $m\in {\mathbb{N}}^{*}$. In this way:

$$\begin{array}{cc}& M_{qp}({\pi }^{*})=\beta \underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }\sum _h\left(\genfrac{}{}{0pt}{}{qp}{h}\right)d{(a,b)}^{h}d{(a^{\prime },b^{\prime })}^{qp-h}d{\pi }^{*}((x,a),(y,b))d{\pi }^{*}((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\hfill \\ & =\beta \sum _h\left(\genfrac{}{}{0pt}{}{qp}{h}\right)\left(\underset{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}{\int }d{(a,b)}^{h}d{\pi }^{*}((x,a),(y,b))\right)\left(\underset{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}{\int }d{(a^{\prime },b^{\prime })}^{qp-h}d{\pi }^{*}((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\right)=0\hfill \end{array}$$

Using Equation (37), we have shown

$$J_{qp}(d_{X\times \mathsf{\Omega }},d_{Y\times \mathsf{\Omega }},{\pi }_{*})=0$$

which implies that $d_{GW,p}(d_{X\times \mathsf{\Omega }},d_{Y\times \mathsf{\Omega }},\mu ,\nu )=0$ for the coupling ${\pi }^{*}$.

Thanks to the Gromov–Wasserstein properties (see [17]) this states the existence of an isometry between $\mathrm{supp}(\mu )$ and $\mathrm{supp}(\nu )$. So there exists a surjective function $f=(f_1,f_2):\mathrm{supp}(\mu )\to \mathrm{supp}(\nu )$, which verifies P.1 and:

$$\forall ((x,a),(x^{\prime },a^{\prime }))\in {(\mathrm{supp}(\mu ))}^2,d_{X\times \mathsf{\Omega }}((x,a),(x^{\prime },a^{\prime }))=d_{Y\times \mathsf{\Omega }}(f(x,a),f(x^{\prime },a^{\prime }))$$

(40)

or equivalently:

$$\forall ((x,a),(x^{\prime },a^{\prime }))\in {(\mathrm{supp}(\mu ))}^2,(1-\beta )d_X(x,x^{\prime })+\beta d(a,a^{\prime })=(1-\beta )d_Y(f_1(x,a),f_1(x^{\prime },a^{\prime }))+\beta d(f_2(x,a),f_2(x^{\prime },a^{\prime }))$$

(41)

In particular, ${\pi }^{*}$ is concentrated on $\{(x,y)=f(x,y)\}$ or equivalently ${\pi }^{*}=(I_d\times f)\#\mu$. Injecting ${\pi }^{*}$ in (39) leads to:

$$\begin{array}{cc}\hfill H_{qp}({\pi }^{*})& =\underset{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}{\int }d{(a,b)}^{qp}d{\pi }^{*}((x,a),(y,b))=\underset{X\times \mathsf{\Omega }}{\int }d{(a,f_2(x,a))}^{qp}d\mu (x,a)=0\hfill \end{array}$$

(42)

Which implies:

$$\forall (x,a)\in \mathrm{supp}(\mu ),f_2(x,a)=a$$

(43)

Moreover, using the equality (41), we can conclude that:

$$\forall (x,a)(x^{\prime },a^{\prime })\in \mathrm{supp}{(\mu )}^2,d_X(x,x^{\prime })=d_Y(f_1(x,a),f_1(x^{\prime },a^{\prime }))$$

(44)

In this way, f verifies all of the properties (33)–(35).

Moreover, suppose that $\mu$ and $\nu$ are generalized labeled graphs. In this case there exists ${\ell }_f:X\to A$ surjective such that $\mu =(I\times {\ell }_f)\#{\mu }_X$. Afterwards, (44) implies that:

$$\forall (x,x^{\prime })\in \mathrm{supp}{({\mu }_X)}^2,d_X(x,x^{\prime })=d_Y(f_1(x,{\ell }_f(x)),f_1(x^{\prime },{\ell }_f(x^{\prime })))$$

(45)

We define $I:\mathrm{supp}({\mu }_X)\to \mathrm{supp}({\mu }_Y)$ such that $I(x)=f_1(x,{\ell }_f(x))$. Then we have by (45) $d_X(x,x^{\prime })=d_Y(I(x),I(x^{\prime }))$ for $(x,x^{\prime })\in {\mathrm{supp}({\mu }_X)}^2$. Overall we have $f(x,a)=(I(x),a)$ for all $(x,a)\in \mathrm{supp}(\mu )$. Also since $f\#\mu =\nu$ we have $I\#{\mu }_X={\nu }_Y$.

Moreover, I is a surjective function. Indeed let $y\in \mathrm{supp}({\nu }_Y)$. Let $b\in \mathrm{supp}({\nu }_B)$ such that $(y,b)\in \mathrm{supp}(\nu )$. By surjectivity of f there exists $(x,a)\in \mathrm{supp}(\mu )$ such that $(y,b)=f(x,a)=(I(x),a)$ so that $y=I(x)$.

Overall, f satisfies all P.1, P.2 and P.3 if $\mu$ and $\nu$ are generalized labeled graphs. The converse is also true using the reasoning in (36). □

Proposition 4.

Symmetry and triangle inequality.

$d_{FGW,\alpha ,p,q}$ is symmetric and for $q=1$ satisfies the triangle inequality. For $q\ge 2$ the triangle inequality is relaxed by a factor $2^{q-1}$.

To prove this result we will use the following lemma:

Lemma 4.

Let $(X\times \mathsf{\Omega },d_X,\mu ),(Y\times \mathsf{\Omega },d_Y,\beta ),(Z\times \mathsf{\Omega },d_Z,\nu )\in \mathbb{S}{(\mathsf{\Omega })}^3$. For $(x,a),(x^{\prime },a^{\prime })\in {(X\times \mathsf{\Omega })}^2$, $(y,b),(y^{\prime },b^{\prime })\in {(Y\times \mathsf{\Omega })}^2$ and $(z,c),(z^{\prime },c^{\prime })\in {(Z\times \mathsf{\Omega })}^2$ we have:

$$L{(x,z,x^{\prime },z^{\prime })}^q\le 2^{q-1}(L{(x,y,x^{\prime },y^{\prime })}^q+L{(y,z,y^{\prime },z^{\prime })}^q)$$

(46)

$$d{(a,c)}^q\le 2^{q-1}(d{(a,b)}^q+d{(b,c)}^q)$$

(47)

Proof. 

Direct consequence of (30) and triangle inequalities of $d,d_X,d_Y,d_Z$. □

Proof of Proposition 4. 

To prove the triangle inequality of $d_{FGW,\alpha ,p,q}$ distance for arbitrary measures we will use the Gluing lemma which stresses the existence of couplings with a prescribed structure. Let $(X\times \mathsf{\Omega },d_X,\mu ),(Y\times \mathsf{\Omega },d_Y,\beta ),(Z\times \mathsf{\Omega },d_Z,\nu )\in \mathbb{S}{(\mathsf{\Omega })}^3$.

Let ${\pi }_1\in \mathsf{\Pi }(\mu ,\beta )$ and ${\pi }_2\in \mathsf{\Pi }(\beta ,\nu )$ be optimal transportation plans for the Fused Gromov-Wasserstein distance between $\mu$, $\beta$ and $\beta$, $\nu$ respectively. By the Gluing Lemma (see [15] and Lemma 5.3.2 in [65]) there exists a probability measure $\pi \in P\left((X\times \mathsf{\Omega })\times (Y\times \mathsf{\Omega })\times (Z\times \mathsf{\Omega })\right)$ with marginals ${\pi }_1$ on $(X\times \mathsf{\Omega })\times (Y\times \mathsf{\Omega })$ and ${\pi }_2$ on $(Y\times \mathsf{\Omega })\times (Z\times \mathsf{\Omega })$. Let ${\pi }_3$ be the marginal of $\pi$ on $(X\times \mathsf{\Omega })\times (Z\times \mathsf{\Omega })$. By construction ${\pi }_3\in \mathsf{\Pi }(\mu ,\nu )$. So by suboptimality of ${\pi }_3$:

$$\begin{array}{cc}& d_{FGW,\alpha ,p,q}(d_X,d_Z,\mu ,\nu )\le {\left(\underset{{(X\times \mathsf{\Omega }\times Z\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,c)}^q+\alpha L{(x,z,x^{\prime },z^{\prime })}^q\right)}^{p}d{\pi }_3((x,a),(z,c))d{\pi }_3((x^{\prime },a^{\prime }),(z^{\prime },c^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & ={\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }\times Z\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,c)}^q+\alpha L{(x,z,x^{\prime },z^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b),(z,c))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }),(z^{\prime },c^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & \stackrel{(*)}{\le }{2}^{q-1}(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }\times Z\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+(1-\alpha )d{(b,c)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q+\alpha L{(y,z,y^{\prime },z^{\prime })}^q\right)}^p\hfill \\ & d\pi ((x,a),(y,b),(z,c))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }),(z^{\prime },c^{\prime })){)}^{\frac{1}{p}}\hfill \\ & \stackrel{(**)}{\le }{2}^{q-1}({\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }\times Z\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b),(z,c))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }),(z^{\prime },c^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & +{\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }\times Z\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(b,c)}^q+\alpha L{(y,z,y^{\prime },z^{\prime })}^q\right)}^{p}d\pi ((x,a),(y,b),(z,c))d\pi ((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }),(z^{\prime },c^{\prime }))\right)}^{\frac{1}{p}})\hfill \\ & =2^{q-1}({\left(\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d{\pi }_1((x,a),(y,b))d{\pi }_1((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))\right)}^{\frac{1}{p}}\hfill \\ & +{\left(\underset{{(Y\times \mathsf{\Omega }\times Z\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(b,c)}^q+\alpha L{(y,z,y^{\prime },z^{\prime })}^q\right)}^{p}d{\pi }_2((y,b),(z,c))d{\pi }_2((y^{\prime },b^{\prime }),(z^{\prime },c^{\prime }))\right)}^{\frac{1}{p}})\hfill \\ & =2^{q-1}(d_{FGW,\alpha ,p,q}(\mu ,\beta )+d_{FGW,\alpha ,p,q}(\beta ,\nu ))\hfill \end{array}$$

with (*) comes from (46) and (47) and (**) is Minkowski inequality. So when $q=1$, $d_{FGW,\alpha ,p,q}$ satisfies the triangle inequality and when $q>1$, $d_{FGW,\alpha ,p,q}$ satisfies a relaxed triangle inequality so that it defines a semi-metric as described previously. □

7.3. Proof of Theorem 2—Convergence and Concentration Inequality

Proof. 

The proof of the convergence in $FGW$ directly stems from the weak convergence of the empirical measure and Lemma 3. Moreover, since ${\mu }_n$ and $\mu$ are both in the same ground space, we have:

$$d_{FGW,\alpha ,p,1}({\mu }_n,\mu )\le 2d_{W,p}({\mu }_n,\mu )\Rightarrow \mathbb{E}[d_{FGW,\alpha ,p,1}({\mu }_n,\mu )]\le 2\mathbb{E}[d_{W,p}({\mu }_n,\mu )].$$

We can directly apply Theorem 1 in [31] to state the inequality. □

7.4. Proof of Theorem 3—Interpolation Properties between GW and W

Proof. 

Let ${\pi }_{OT}\in \mathsf{\Pi }({\mu }_A,{\nu }_B)$ be an optimal coupling for the $pq$-Wasserstein distance between ${\mu }_A$ and ${\nu }_B$. We can use the same Gluing lemma (Lemma 5.3.2 in [65]) to construct:

$$\rho \in P(\underset{{\pi }_{OT}}{\underbrace{\stackrel{\mu }{\overbrace{X\times \mathsf{\Omega }}}\times \stackrel{\nu }{\overbrace{\mathsf{\Omega }\times Y}})}}$$

such that $\rho \in \mathsf{\Pi }(\mu ,\nu )$ and $P_{2,3}\#\rho ={\pi }_{OT}$.

Moreover we have:

$$\underset{\mathsf{\Omega }\times \mathsf{\Omega }}{\int }d{(a,b)}^{pq}d{\pi }_{OT}(a,b)=\underset{X\times \mathsf{\Omega }\times \mathsf{\Omega }\times Y}{\int }d{(a,b)}^{pq}d\rho (x,a,b,y)$$

(48)

Let $\alpha \ge 0$ and ${\pi }_{\alpha }$ optimal plan for the Fused Gromov-Wasserstein distance between $\mu$ and $\nu$.

We can deduce that:

$$\begin{array}{cc}& d_{FGW,\alpha ,p,q}{(\mu ,\nu )}^p-{(1-\alpha )}^p{d}_{W,pq}{({\mu }_A,{\nu }_B)}^{pq}\hfill \\ & =\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d{\pi }_{\alpha }((x,a),(y,b))d{\pi }_{\alpha }((x^{\prime },a^{\prime }),(y^{\prime },b^{\prime }))-\underset{\mathsf{\Omega }\times \mathsf{\Omega }}{\int }{(1-\alpha )}^{p}d{(a,b)}^{pq}d{\pi }_{OT}(a,b)\hfill \\ & \stackrel{(*)}{\le }\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d{(a,b)}^q+\alpha L{(x,y,x^{\prime },y^{\prime })}^q\right)}^{p}d\rho (x,a,b,y)d\rho (x^{\prime },a^{\prime },b^{\prime },y^{\prime })-\underset{X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }}{\int }{(1-\alpha )}^{p}d{(a,b)}^{pq}d\rho (x,a,b,y)\hfill \\ & ={(1-\alpha )}^p\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }d{(a,b)}^{pq}d\rho (x,a,b,y)d\rho (x^{\prime },a^{\prime },b^{\prime },y^{\prime })-{(1-\alpha )}^p\underset{X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega }}{\int }d{(a,b)}^{pq}d\rho (x,a,b,y)\hfill \\ & +\sum _{k=0}^{p-1}\left(\genfrac{}{}{0pt}{}{p}{k}\right){(1-\alpha )}^k{\alpha }^{p-k}\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }d{(a,b)}^{qk}L{(x,y,x^{\prime },y^{\prime })}^{q(p-k)}d\rho (x,a,b,y)d\rho (x^{\prime },a^{\prime },b^{\prime },y^{\prime })\hfill \\ & =\sum _{k=0}^{p-1}\left(\genfrac{}{}{0pt}{}{p}{k}\right){(1-\alpha )}^k{\alpha }^{p-k}\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }d{(a,b)}^{qk}L{(x,y,x^{\prime },y^{\prime })}^{q(p-k)}d\rho (x,a,b,y)d\rho (x^{\prime },a^{\prime },b^{\prime },y^{\prime }).\hfill \end{array}$$

We note $H_k=\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }d{(a,b)}^{qk}L{(x,y,x^{\prime },y^{\prime })}^{q(p-k)}d\rho (x,a,b,y)d\rho (x^{\prime },a^{\prime },b^{\prime },y^{\prime })$.

Using (9) we have shown that:

$$(1-\alpha ){(d_{W,pq}({\mu }_A,{\nu }_B))}^q\le d_{FGW,\alpha ,p,q}(\mu ,\nu )\le {\left({(1-\alpha )}^p{(d_{W,pq}({\mu }_A,{\nu }_B))}^{pq}+{\sum }_{k=0}^{p-1}\left(\genfrac{}{}{0pt}{}{p}{k}\right){(1-\alpha )}^k{\alpha }^{p-k}{H}_k\right)}^{\frac{1}{p}}$$

Accordingly, $\underset{\alpha \to 0}{lim}{d}_{FGW,\alpha ,p,q}(\mu ,\nu )={(d_{W,pq}({\mu }_A,{\nu }_B))}^q$.

For the case $\alpha \to 1$ we rather consider ${\pi }_{GW}\in \mathsf{\Pi }({\mu }_X,{\nu }_Y)$ an optimal coupling for the $pq$-Gromov–Wasserstein distance between ${\mu }_X$ and ${\nu }_Y$ and we construct

$$\gamma \in P(\underset{{\pi }_{GW}}{\underbrace{\stackrel{\mu }{\overbrace{X\times \mathsf{\Omega }}}\times \stackrel{\nu }{\overbrace{\mathsf{\Omega }\times Y}})}}$$

such that $\gamma \in \mathsf{\Pi }(\mu ,\nu )$ and $P_{2,3}\#\rho ={\pi }_{GW}$. In the same way as previous reasoning we can derive:

$$\alpha {(d_{GW,pq}({\mu }_X,{\nu }_Y))}^q\le d_{FGW,\alpha ,p,q}(\mu ,\nu )\le ({\alpha }^p{(d_{GW,pq}({\mu }_X,{\nu }_Y))}^{pq}+\sum _{k=0}^{p-1}\left(\genfrac{}{}{0pt}{}{p}{k}\right){(1-\alpha )}^{p-k}{\alpha }^k{J}_k{)}^{\frac{1}{p}}$$

(49)

with $J_k=\int d{(a,b)}^{q(p-k)}L{(x,y,x^{\prime },y^{\prime })}^{qk}d\rho (x,a,b,y)d\rho (x^{\prime },a^{\prime },b^{\prime },y^{\prime })$. In this way $\underset{\alpha \to 1}{lim}{d}_{FGW,\alpha ,p,q}(\mu ,\nu )={(d_{GW,pq}({\mu }_X,{\nu }_Y))}^q$. □

7.5. Proof of Theorem 4—Constant Speed Geodesic

Proof. 

Let $t,s\in [0,1]$. Recalling:

$$\forall (x,a),(y,b)\in X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega },{\eta }_t(x,a,y,b)=(x,y,(1-t)a+tb)$$

(50)

We note ${\mathbb{S}}_t={\left(X\times Y\times \mathsf{\Omega },(1-t)d_X\oplus t{d}_Y,{\mu }_t={\eta }_t\#{\pi }^{*}\right)}_{t\in [0,1]}$ and $d_t=(1-t)d_X\oplus t{d}_Y$. Let $\parallel .\parallel$ be any ${\ell }_m$ norm for $m\ge 1$. It suffices to prove:

$$d_{FGW,\alpha ,p,1}({\mu }_t,{\mu }_s)\le |t-s|d_{FGW,\alpha ,p,1}({\mu }_0,{\mu }_1)$$

(51)

To do so, we consider ${\Delta }_s^t\in P(X\times Y\times \mathsf{\Omega }\times X\times Y\times \mathsf{\Omega })$ defined by ${\Delta }_s^t=({\eta }_t\times {\eta }_s)\#{\pi }^{*}\in \mathsf{\Pi }({\mu }_t,{\mu }_s)$ and the following “diagonal” coupling:

$$d{\gamma }_s^t((x,y),a,(x^{″},y^{″}),b)=d{\Delta }_s^t((x,y),a,(x^{″},y^{″}),b)d{\delta }_{(x_0,x_1)}(x_0^{″},x_1^{″})$$

(52)

Subsquently, ${\gamma }_s^t\in P(X\times Y\times \mathsf{\Omega }\times X\times Y\times \mathsf{\Omega })$ and since ${\Delta }_s^t\in \mathsf{\Pi }({\mu }_t,{\mu }_s)$ then ${\gamma }_s^t\in \mathsf{\Pi }({\mu }_t,{\mu }_s)$ So by suboptimality:

$$\begin{array}{cc}& d_{FGW,\alpha ,p,1}{({\mu }_t,{\mu }_s)}^p\le \underset{{(X\times Y\times \mathsf{\Omega }\times X\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d(a,b)+\alpha |d_t[(x,y),(x^{\prime },y^{\prime })]-d_s[(x^{″},y^{″}),(x^{″\prime },y^{″\prime })]|\right)}^p\hfill \\ & d{\gamma }_s^t(x,y,a,x^{\prime \prime },y^{\prime \prime },b)d{\gamma }_s^t(x^{\prime },y^{\prime },a^{\prime },x^{\prime \prime \prime },y^{\prime \prime \prime },b^{\prime })\hfill \\ & =\underset{{(X\times Y\times \mathsf{\Omega }\times X\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )d(a,b)+\alpha |d_t[(x,y),(x^{\prime },y^{\prime })]-d_s[(x,y),(x^{\prime },y^{\prime })]|\right)}^p\hfill \\ & d{\Delta }_s^t(x,y,a,x,y,b)d{\Delta }_s^t(x^{\prime },y^{\prime },a^{\prime },x^{\prime },y^{\prime },b^{\prime })\hfill \\ & =\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )\parallel (1-t)a+tb-(1-s)a-sb\parallel +\alpha |(1-t)d_X(x,x^{\prime })+t{d}_Y(y,y^{\prime })-(1-s)d_X(x,x^{\prime })+s{d}_Y(y,y^{\prime })|\right)}^p\hfill \\ & d{\pi }^{*}(x,a,y,b)d{\pi }^{*}(x^{\prime },a^{\prime },y^{\prime },b^{\prime })\hfill \\ & ={|t-s|}^p\underset{{(X\times \mathsf{\Omega }\times Y\times \mathsf{\Omega })}^2}{\int }{\left((1-\alpha )\parallel a-b\parallel +\alpha |d_X(x,x^{\prime })-d_Y(y,y^{\prime })|\right)}^{p}d{\pi }^{*}(x,a,y,b)d{\pi }^{*}(x^{\prime },a^{\prime },y^{\prime },b^{\prime })\hfill \end{array}$$

So $d_{FGW,\alpha ,p,1}({\mu }_t,{\mu }_s)\le |t-s|d_{FGW,\alpha ,p,1}(d_0,d_1,{\mu }_0,{\mu }_1)$. □