# Fused Gromov-Wasserstein Distance for Structured Objects
## 2 Structured Objects as Distributions and Fused Gromov-Wasserstein Distance
### 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\geq 1\). We consider \((X\times\Omega,d_{X},\mu)\in\mathbb{S}_{pq}(\Omega)\) and \((Y\times\Omega,d_{Y},\
u)\in\mathbb{S}_{pq}(\Omega)\). The Fused-Gromov-Wasserstein distance is defined as:_  
\[d_{FGW,\alpha,p,q}(\mu,\
u)=\left(\inf_{\pi\in\Pi(\mu,\
u)}E_{p,q,\alpha}(\pi) \right)^{\frac{1}{p}} \tag{8}\]  
_where_  
\[E_{p,q,\alpha}(\pi)\!=\!\!\!  
**Proposition 1** (Comparaison between \(FGW\), \(GW\) and \(W\)).: _We have the following results for two structured objects \(\mu\) and \(\
u\):_  
* _The following inequalities hold:_ \[d_{FGW,\alpha,p,q}(\mu,\
u)\geq(1-\alpha)d_{W,pq}(\mu_{A},\
u_{B})^{q}\] (9) \[d_{FGW,\alpha,p,q}(\mu,\
u)\geq\alpha d_{GW,pq}(\mu_{X},\
u_{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_ \(\mu\) _and_ \(\
u\) _for the distance on_ \(Z\times\Omega\)_:_ \(d((x,a),(y,b))=(1-\alpha)d(a,b)+\alpha d_{Z}(x,y)\)_. Then:_ \[d_{FGW,\alpha,p,1}(\mu,\
u)\leq 2d_{W,p}(\mu,\
u).\] (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 a (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._  
Figure 7: Illustration of Definition 8. The figure shows two structured objects \((X\times\Omega,d_{X},\mu)\) and \((Y\times\Omega,d_{Y},\mu)\). The feature space \(\Omega\) is the common space for all features. The two metric spaces \((X,d_{X})\) and \((Y,d_{Y})\) represent the structures of the two structured objects, the similarity between all pair-to-pair distances of the structure points is measured by \(L(x,y,x^{\prime},y^{\prime})\). \(\mu\) and \(\
u\) are the joint measures on the structure space and the feature space.