# Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening
## 4 Contribution: Hierarchical Graph2 Vec (HG2V)
### Hierarchical Negative Sampling  
Following the principles of Graph2 Vec we aim to maximize mutual information between node embeddings and local neighborhood embeddings at each level. We achieve this by training a classifier to distinguish between positive and negative examples of such pairs of embeddings. Positive pairs are defined as node \(v\) in level \(l\) and its \"super node\" \(\mathcal{P}(v)\) in level \(l+1\).  
More precisely, consider the \(l\)-th level of the hierarchical pyramid. The probability \(P_{\mathcal{V}^{l}}\) is built by sampling a graph \(g\) from the dataset, then by sampling a node \(u\) with uniform probability from this graph. \(P_{X^{l}|\mathcal{V}^{l}}\) is obtained by sampling a node from \(\mathcal{P}^{-1}(u)\). It gives a pair \((x^{l}(\mathcal{P}^{-1}(u)),g^{l+1}(u))\) sampled according to \(P_{X^{l}|\mathcal{V}^{l}}=P_{\mathcal{V}^{l}}P_{X^{l}|\mathcal{V}^{l}}\). The negative pairs are built as usual from the independent probability \(P_{X^{l}}\otimes P_{\mathcal{V}^{l}}\). The corresponding loss function takes the form:  
\[\mathcal{L}^{l}=\mathbb{E}_{(x^{l}_{j}(u),g^{l}(\mathcal{P}(u)))\sim P_{X^{l} \mathcal{V}^{l}}}\log\sigma(x^{l}(u)\cdot g^{l}(\mathcal{P}(u)))+\mathbb{E}_{ (x^{l}(u),g^{l}(v))\sim P_{X^{l}}\otimes P_{\mathcal{V}^{l}}}\log\sigma(-x^{l }(u)\cdot g^{l}(v)) \tag{13}\]  
The overall method is described in Algorithm 1.  
A descriptor \(\mathcal{E}_{l}(g)\) for each level \(l\) of the graph \(g\) is computed by global pooling over node embeddings. The final graph embedding is obtained by concatenating those descriptors. The sum aggregator is always preferred over mean aggregator, because of its better ability to distinguish between multisets instead of distributions, as argued in [32]. Hence, the learned representation is:  
\[\mathcal{E}_{l}(g) =\left[\sum_{u\in V}g^{l}(u),\max_{u\in V}g^{l}(u)\right] \tag{14}\] \[\mathcal{E}(g) =\text{CONCATENATE}\left(\mathcal{E}_{1}(g),\mathcal{E}_{2}(g),...,\mathcal{E}_{L}(g)\right) \tag{15}\]In the [PERSON]'s method, the number of stages is not pre-determined in advance: only the final coarsened graph size can be chosen. When the number of stages produced by the [PERSON] method is not aligned with the depth of the neural network, the pooling is either cropped (too much stages) or completed with identity poolings (not enough stages). The resulting vector can be used for visualization purposes (PCA, t-SNE) or directly plug into a classifier with labels on graphs.  
Complexity  
Time. The coarsening of each graph can be pre-computed once for all, in linear time in the number of nodes and edges [3]. Hence, the main bottleneck is the maximization of mutual information. Let \(|V|\) the maximum number of nodes in a graph. Let \(B\) be the batch size. Let \(L\) be the number of stages. Let \(a\) the order of Truncated Krylov. Let \(d\) the dimension of node embedding. The complexity of the algorithm per batch is \(\mathcal{O}(BLa|V|^{3}+BLa|V|^{2}d+BLa|V|d^{2}+B^{2}Ld)\). The first term is due to exponentiation of adjacency matrix, the second one to diffusion along edges, the third one to forward pass in network layers, and the last one to the Cartesian product to create positive and negative examples. The average complexity per graph is hence: \(\mathcal{O}(La|V|(|V|+d)^{2}+BLd)\). The most sensitive factor is the number of nodes, followed by the the number of features and the batch size. The magnitude of those matrices allows to handle graphs with hundred of nodes efficiently on modern GPUs, with embedding as big as 512 and up to 8 graphs per batch and 5 stages of coarsening. In practice, the bottleneck turn out to be the pre-computation of coarsening, which does not benefit the GPU speed.  
Space. Note that for datasets with small graphs we have \(\dim(\mathcal{E}_{i})=2 Ld>\dim(X_{i})+\dim(A_{i})=n|V|+|V|^{2}\). However, when the number of nodes exceeds 50, the embedding size is always smaller than the adjacency matrix. Hence, this method is more suitable for big graphs with hundreds of nodes.