# Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening
## 4 Contribution: Hierarchical Graph2 Vec (HG2V)
### Loukas's Coarsening
#### 4.1.1 Wesfeiler-Lehman Sensibility to Structural Noise  
The ability of **WL** to discriminate all graph patterns comes with the incapacity to recognize as similar a graph and its noisy counterpart. Each edge added or removed can strongly perturb the histogram of labels produced by **WL**. Said otherwise, **WL** is not a good solution to inexact graph matching problem.  
We perform experiments to evaluate the effect of adding or removing edges on different graphs. We randomly generate 100 graphs of 500 nodes each, that belong to four categories (cycle, tree, wheel and ladder), using the routines of NetworkX [33] library. For each generated graph \(g\), we randomly remove from 1 to 10 edges, sampled with independent and uniform probability, to create the graph \(g^{\prime}\). One may hope that such little modification over this huge edge set would not perturb excessively the labels of **WL** procedure.  
To evaluate the consequences of edge removal we propose to use as similarity score the intersection over union of histogram of labels of \(g\) and \(g^{\prime}\) at each stage \(1\leq l\leq 5\):  
\[\mathcal{S}^{l}(g,g^{\prime})=100\times\frac{|\text{histo}(\textbf{WL}^{l}(g) )\cap\text{histo}(\textbf{WL}^{l}(g^{\prime}))|}{|\text{histo}(\textbf{WL}^{l }(g))\cup\text{histo}(\textbf{WL}^{l}(g^{\prime}))|} \tag{5}\]  
The average similarity score \(\mathcal{S}^{l}(g,g^{\prime})\) over the 100 graphs is reported in Figure 2.  
The similarity decreases monotonically with the number of edges removed, even when restricting the procedure to the first stage (neighborhood of width 1). On higher stages (wider neighborhood) the effect is even worse. On graphs with small diameter (such as _wheel_ graph or 3-regular tree) a significant drop in similarity can be noticed. On ladder graph and cycle, sparse graphs with huge diameter, the effect of edge removal remains significant.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & **Continuous** & **Complexity** & **Complexity** & **End-to-End** & \multirow{2}{*}{**Supervised**} \\  & **Attributes** & **(Training)** & **(Inference)** & **Differentiable** & \\ \hline Kernel methods, e.g., & & & & & \\
**WL**-OA [27], **WWL**[4] & & ✓ & \(\mathcal{O}(N^{2})^{*}\) & \(\mathcal{O}(N)^{*}\) & ✗ & ✗ \\ \hline Graph2 Vec [2] & ✗ & \(\mathcal{O}(N)\) & ✗ & ✗ & ✗ \\ \hline GIN [32], DiffPool [17], & & & & & \\ MinCutPool [18] & ✓ & \(\mathcal{O}(N)\) & \(\mathcal{O}(1)\) & ✓ & ✓ \\ \hline
**HG2V** (Section 4), & & & & & \\ Infograph [13] & ✓ & \(\mathcal{O}(N)\) & \(\mathcal{O}(1)\) & ✓ & ✗ \\ \hline \hline \end{tabular}  
* Can be improved with Nystrom approximation or Random Fourier Features.  
\end{table}
Table 1: Key properties of methods (related or proposed) for graph embedding. \(N\) is the number of graphs. Symbol ✗ for complexity (inference) means the method is transductive (and not inductive) and one needs to use the same time as for training. Symbol ✓ for supervised means labels are required to learn a representation (by back-propagating classification loss).