# Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening
## 4 Contribution: Hierarchical Graph2 Vec (HG2V)
### Loukas's Coarsening
#### 4.1.2 Robustness to Structural Noise with [PERSON]'s Coarsening  
**WL** procedure characterizes a graph as a sequence of rooted subtrees with increasing width. While this description is suitable for small patterns and inexact graph matching at local scale, it is very sensitive to structural noise. Adding or removing few edges (without hurting the global shape) changes the labels completely for subtrees of higher width. So as to characterize global features (e.g., communities, bridges, sparsest cuts...), we rely on a sequence of coarsened graphs based on the Loukas's procedure, that replaces the different iterations of neighborhoods of **WL**. **Definition 3** (Graph Coarsening). : _Graph coarsening is an operation mapping a graph \((V_{1},E_{1})\) to a new graph \((V_{2},E_{2})\) verifying \(|V_{2}|<|V_{1}|\), using a surjective graph homomorphism \(\mathcal{P}:V_{1}\to V_{2}\) called **pooling function**:_  
\[ \begin{split}(u,v)\in E_{1}&\implies(\mathcal{P} (u),\mathcal{P}(v))\in E_{2}\text{ or }\mathcal{P}(u)=\mathcal{P}(v)\\ (\mathcal{P}(u),\mathcal{P}(v))\
otin E_{2}&\implies(u,v)\
otin E_{1}\end{split}  \tag{6}\]  
[PERSON]'s method [3] is a graph coarsening operation. This spectral reduction of attributed graphs offers the guarantee, in the spectral domain, that a coarsened graph approximates well its larger version. The idea is that the graph spectrum (eigenspaces and eigenvalues of their Laplacian) describes global and local structures of graphs. Structural noise may have very little consequences on the spectrum, depending of the nature of the intervention. Hence [PERSON]'s coarsening, which preserves  
Figure 2: Similarity score as a function of edges removed for different stages of **WL** iterations. The similarity score reaches 100% for identical sets of labels, and 0% for disjoint sets of labels. **(a)** Cycle: the 2-regular graph with one giant connected component. **(b)** Tree: three children per node, except the ones at the last level. **(c)** Wheel: like cycle graph, with an additional node connected to all the others. **(d)** Ladder: two paths of 250 nodes each, where each pair of nodes is joined by an edge. components associated with a low frequency in the graph spectrum, will produce a smaller graph with the same global shape as the input one, as demonstrated in Figure 3.  
In a nutshell, the method computes a sequence of projection matrices \((P_{l})_{1\leq l\leq L}\) such that the Laplacian of the coarsened graph can be written as \(L_{l+1}=P_{l}^{\mp}L_{l}P_{l}\) (where \(\mp\) denotes the transposed pseudo-inverse). Since the algorithm is quite evolved and its explanation beyond the scope of our work, we refer to the original paper [3] for an explicit description of [PERSON]'s method and an extensive list of properties and guarantees. The interest of this coarsening method is that, if two graphs \(g^{l-1}\) and \(h^{l-1}\) are close enough, the coarsened graphs \(g^{l}\) is itself a satisfying coarsening for \(h^{l-1}\). By symmetry, the same result follows for \(h^{l}\) and \(g^{l-1}\). Hence, one may hope that \(g^{l}\) and \(h^{l}\) share similar patterns (Figure 4), and it will be advantageous for the **WL** procedure. Such intuition can be confirmed experimentally. On four datasets (see Section 5 for their description), we sample two graphs \(g^{0}\) and \(h^{0}\) with independent and uniform probability. We measure their similarity using the Wasserstein distance between their spectra. Such choice is motivated by the fact that two graphs with different number of nodes have spectrum of different sizes. Wasserstein provides an elegant way to measure distance between sets of different size, in addition to be fast and easy to compute. **Definition 4** (Wasserstein Distance between Graph Spectra). : _Let \(\mathbf{\lambda}=\{\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\}\) and \(\mathbf{\mu}=\{\mu_{1},\mu_{2},\ldots,\mu_{m}\}\) the spectra of two graphs.