# Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening
## 4 Contribution: Hierarchical Graph2 Vec (HG2V)  
Our motivations for this work can be summarized as follows:  
* we first show that **WL** fails to capture global scale information, which is hurtful for many tasks;
* we then show that such flaw can be corrected by the use of graph coarsening. In particular, [PERSON]'s coarsening exhibits good properties in this regard;
* we finally show that the advantage of GNN over **WL** is to be continuous functions in node features. They are robust to small perturbations.  
Based on those observations, we propose a new algorithm building on graph coarsening and mutual information maximization, which we term Hierarchical Graph2 Vec (HG2V). It has the following properties:  
* The training is unsupervised. No label is required. The representation can be used for different tasks.
* The model is inductive, trained once for all with the graphs of the dataset in linear time. The training dataset is used as a prior to embed new graphs, whatever their underlying distribution.
* It handles continuous nodes attributes by replacing the hash function in **WL** procedure by a Convolutional Graph NN. It can be combined with other learning layers, serving as pre-processing step for feature extraction.
* The model is end-to-end differentiable. Its input and its output can be connected to other deep neural networks to be used as building block in a full pipeline. The signal of the loss can be back-propagated through the model to train feature extractors, or to retrain the model in transfer learning. For example, if the node features are rich and complex (images, audio), a CNN can be connected to the input to improve the quality of representation.
* The structures of the graph at all scales are summarized using Loukas coarsening. The embedding combines **local view and global view** of the graph.  
The resulting algorithm shares a similar spirit with Graph2 Vec (MI maximization between node and graph descriptors), but it corrects some of its above-mentioned flaws. A high level overview of the method is provided in Algorithm 1. Table 1 summarizes key properties of the method, against the other ones found in literature.  
In the following, we introduce in Section 4.1 the [PERSON]'s coarsening method of [3], and detail how we use it in Section 4.2. Then, Section 4.3 deals with the continuity property achieved by GNN, while Section 4.4 explains how to train our proposed model **HG2V**.  
```
Result: Graph embedding \(\mathcal{E}(g)\) for each graph \(g\) Input: A training set of attributed graphs \(g\), subset of \(\mathbb{G}\) and the number of stages \(L\) ; GNNs \(F^{l}_{\theta}\) and \(H^{l}_{\theta}\) with randomly initialized \(\theta\), \(1\leq l\leq L\)foreach batch of attributed graphsdoforeach graph \(g\) in the batchdo  See Section 4.1: run [PERSON]'s algorithm on \(g\) to produce a sequence of coarsened graphs \(g^{l}\), \(1\leq l\leq L\);  end foreach level \(1\leq l\leq L\)doforeach graph \(g^{l}\) in the batchdo foreach node \(u\) in \(g^{l}\)do  See Section 4.2: Generate local neighborhood embedding \(x^{l}(u)\) using \(H^{l}_{\theta}\);  Let \(\mathcal{P}(u)\in g^{l+1}\) the image of \(u\) after pooling a node of the coarsened graph;  Generate node embedding \(g^{l+1}(\mathcal{P}(u))\) using \(F^{l}_{\theta}\);  Create positive example \((x^{l}(u),g^{l+1}(\mathcal{P}(u))\);  end foreach foreach pair of graphs \((g,g^{\prime})\)doforeach pair of nodes \((u,v)\in(g,\hat{g})\)do  Create negative examples \((x^{l}(u),\hat{g}^{l+1}(\mathcal{P}(v))\);  end foreach  end foreach  Minimize the cross entropy in Equation (3) between positive and negative examples with discriminator \(T(x,y)=x\cdot y\) and using Section 4.4.  end foreach  end foreach
```  
**Algorithm 1**High-level version of the Hierarchical Graph2 Vec (HG2V) algorithm