# Fused Gromov-Wasserstein Distance for Structured Objects
## 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\Omega\) is a labelling function that associates each vertex \(v_{i}\in\mathcal{V}\) with a feature \(a_{i}\stackrel{{\text{def}}}{{=}}\ell_{f}(v_{i})\) in some feature metric space \((\Omega,d)\). Similarly, \(\ell_{s}:\mathcal{V}\to X\) maps a vertex \(v_{i}\) from the graph to its structure representation \(x_{i}\stackrel{{\text{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\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 \((\Omega,d)\) is a triplet \((X\times\Omega,d_{X},\mu)\), where \((X,d_{X})\) is a metric space and \(\mu\) is a probability measure over \(X\times\Omega\). \((\Omega,d)\) is denoted as the _feature space_, such that \(d:\Omega\times\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 \(\mu\). Definition 2 (Space of structured objects): We note \(\mathbb{X}\) the set of all metric spaces. The space of all structured objects over \((\Omega,d)\) will be written as \(\mathbb{S}(\Omega)\) and is defined by all the triplets \((X\times\Omega,d_{X},\mu)\) where \((X,d_{X})\in\mathbb{X}\) and \(\mu\in\mathcal{P}(X\times\Omega)\). To avoid finiteness issues in the rest of the paper we define for \(p\in\mathbb{N}^{*}\) the space \(\mathbb{S}_{p}(\Omega)\subset\mathbb{S}(\Omega)\) such that if \((X\times\Omega,d_{X},\mu)\in\mathbb{S}_{p}(\Omega)\) we have:  
\[\int_{\Omega}d(a,a_{0})^{p}d\mu_{A}(a)<+\infty \tag{1}\]  
Figure 1: Discrete structured object (**left**) can be described by a labeled graph with \((a_{i})_{i}\) the feature information of the object and \((x_{i})_{i}\) the structure information. If we enrich this object with a histogram \((h_{i})_{i}\) aiming at measuring the relative importance of the nodes, we can represent the structured object as a fully supported probability measure \(\mu\) over the couple space of feature and structure with marginals \(\mu_{X}\) and \(\mu_{A}\) on the structure and the features respectively (**right**).