# Fused Gromov-Wasserstein Distance for Structured Objects  
[PERSON]  
1 CNRS, IRISA, Universite Bretagne-Sud, F-56000 Vannes, France; [EMAIL_ADDRESS] (L.C. ); [EMAIL_ADDRESS] (N.C.)  
1 CNRS, OCA Lagrange, Universite Cote d'Azur, F-06000 Nice, France; remi. 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 \((\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}(\Omega)\) be the set of all probability measures on a space \(\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 \(\operatorname{supp}(\mu)\) the support of \(\mu\in\mathcal{P}(\Omega)\) is the minimal closed subset \(A\subset\Omega\) such that \(\mu(\Omega\backslash A)=0\). Informally, this is the set where the measure \"is not zero\".