# Fused Gromov-Wasserstein Distance for Structured Objects
## 3 Mathematical Properties of \(Fgw\)
### 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 _endpoints_\(x\) 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))\leq|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 \(\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\geq 1\) and \((X\times\Omega,d_{X},\mu_{0})\) and \((Y\times\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]\).