# Fused Gromov-Wasserstein Distance for Structured Objects
## 4 \(Fgw\) in the Discrete Case
### \(Fgw\) in the Discrete Case  
We consider two structured objects \(\mu=\sum_{i=1}^{n}h_{i}\delta_{(x_{i},\mu_{i})}\) and \(\
u=\sum_{j=1}^{m}g_{j}\delta_{(y_{j},b_{j})}\), as described previously. We note \(M_{AB}\) the matrix \(M_{AB}(i,j)=d(a_{i},b_{j})\) and \(C_{1},C_{2}\) the matrices \(C_{1}(i,k)=d_{X}(x_{i},x_{k})\), \(C_{2}(j,l)=d_{Y}(y_{j},y_{l})\) (see Figure 9). The Fused Gromov-Wasserstein distance is defined as  
\[d_{FGW,\alpha,p,q}(\mu,\
u)=\left(\min_{\pi\in\Pi(h,g)}E_{p,q,\alpha}(\pi) \right)^{\frac{1}{p}} \tag{24}\]  
where:  
\[E_{p,q,\alpha}(\pi)=\sum_{i,j,k,l}\left((1-\alpha)M_{AB}(i,j)^{q}+\alpha|C_{1 }(i,k)-C_{2}(j,l)|^{q}\right)^{p}\pi_{i,j}\,\pi_{k,l}.\]  
**Solving the related Quadratic Optimization problem.** Equation (24) is clearly a quadratic problem _w.r.t._\(\pi\). Note that, despite the apparent \(\mathcal{O}(m^{2}n^{2})\) complexity of computing the tensor product, one can simplify the sum to complexity \(\mathcal{O}(mn^{2}+m^{2}n)\)[26] when considering \(p=1,q=2\). In this case, the \(FGW\) computation problem can be re-written as finding \(\pi^{*}\), such that:  
\[\pi^{*}=\operatorname*{arg\,min}_{\pi\in\Pi(h,g)}\quad\operatorname{vec}(\pi) ^{T}Q(\alpha)\operatorname{vec}(\pi)+\operatorname{vec}(D(\alpha))^{T} \operatorname{vec}(\pi) \tag{25}\]  
where \(Q=-2\alpha C_{2}\otimes_{K}C_{1}\) and \(D(\alpha)=(1-\alpha)M_{AB}\). \(\otimes_{K}\) denote the Kronecker product of two matrices, vec the column-stacking operator. With such form, the resulting optimal map can be seen as a quadratic regularized map from initial Wasserstein [36; 37]. However, unlike these approaches, we have a quadratic but probably non-convex term. The gradient \(G\) that arises from Equation (24) can be expressed with the following partial derivative _w.r.t._\(\pi\):  
\[G=(1-\alpha)M_{AB}^{q}+2\alpha\left(\sum_{k,l}|C_{1}(i,k)-C_{2}(j,l)|^{q}\pi_{k, l}\right)_{i,j} \tag{26}\]  
Solving a large scale QP with a classical solver can be computationally expensive. In [36], the authors propose a solver for a graph regularized optimal transport problem whose resulting optimization problem is also a QP. We can then directly use their conditional gradient defined in Algorithmic 1 to solve our optimization problem. It only needs at each iteration to compute the gradient in Equation (26) and solve a classical OT problem for instance with a network flow algorithm. The line-search part is a constrained minimization of a second degree polynomial function that is adapted to the non convex loss in Algorithmic 2. While the problem is non convex, conditional gradient is known to converge to a local stationary point [38]. When \(C_{1},C_{2}\) are squared Euclidean distance matrices the problem reduces to a concave graph matching so that the line-search of the conditional gradient Algorithm 1 always leads to 1 [39; 40].  
```
1:\(\pi^{(0)}\leftarrow\mu_{X}\mu_{Y}^{\top}\)
2:for\(i=1,\dots,\)do
3:\(G\leftarrow\) Gradient from Equation (26) w.r.t. \(\pi^{(i-1)}\)
4:\(\tilde{\pi}^{(i)}\leftarrow\) Solve OT with ground loss \(G\)
5:\(\tau^{(i)}\leftarrow\) Line-search for loss (24) with \(\tau\in(0,1)\) using Algorithm 2
6:\(\pi^{(i)}\leftarrow(1-\tau^{(i)})\pi^{(i-1)}+\tau^{(i)}\pi^{(i)}\)
7:endfor
```  
**Algorithm 1** Conditional Gradient (CG) for \(FGW\)  
Figure 9: \(FGW\) loss for a coupling \(\pi\) depends on both a similarity between each feature of each node of each graph \((d(a_{i},b_{j}))_{i,j}\) and between all intra-graph structure similarities \((|C_{1}(i,k)-C_{2}(j,l)|)_{i,j,k,l}\).