# Fused Gromov-Wasserstein Distance for Structured Objects
## 3 Mathematical Properties of \(Fgw\)
### 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 \(\big{(}(X_{n}\times A_{n},d_{X_{n}},\mu_{n})\big{)}_{n\in\mathbb{N}}\) be a sequence of structured objects. It converges to \((X\times\Omega,d_{X},\mu)\) in the Fused Gromov-Wasserstein sense if:_  
\[\lim_{n\to\infty}d_{FGW,\mu,p,1}\big{(}\mu_{n},\mu\big{)}=0 \tag{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\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}\sum\limits_{i=1}^{n}\delta_{x_{i},a_{i}}\) where \((x_{i},a_{i})\in X\times\Omega\) are sampled from \(\mu\). Does this sequence converges to \((X\times\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 \(\Omega\), we denote as \(dim^{*}_{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 \(dim^{*}_{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\geq 1\). We have:_  
\[\lim_{n\to\infty}d_{FGW,\alpha,p,1}\big{(}\mu_{n},\mu\big{)}=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)]\leq Cn^{-\frac{1}{s}}. \tag{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 \(\
u_{n}=\frac{1}{n}\sum_{i}\delta_{x_{i}}\) denotes the empirical measure of \(\
u\in\mathcal{P}(X)\) and if \(s^{\prime}>d^{*}_{p}(\
u)\), we have:_  
\[\mathbb{E}[d_{GW,p}(\
u_{n},\
u)]\leq C^{\prime}n^{-\frac{1}{s^{\prime}}}. \tag{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.