# Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening
## 4 Contribution: Hierarchical Graph2 Vec (HG2V)
### Handling Continuous Node Attributes with Truncated Krylov  
The **WL** algorithm uses a discrete hash function in Equation (2), with the issue that nodes sharing similar but not quite identical neighborhoods are considered different. If the differences are caused by noise in computations or measures, they should not result in much differences in the labels. For that, we relax the injectivity property of **WL** by replacing it by a function with a continuity property. It is known that Graph Neural Networks (GNN) have a discriminative power at least equivalent to **WL**[32, 34, 35]. We require the opposite, and we emphasize the importance of not having a too strong discriminator. We use the extension of the Gromov-Wasserstein distance to attributed graphs, that requires the mapping to preserve both edge weights and node attributes. The resulting distance is a special case of the Fused Gromov-Wasserstein distance [36]. **Definition 5** (Fused Gromov-Wasserstein distance.). : _Let \(g_{1}=(V_{1},A_{1},Z_{1})\) and \(g_{2}=(V_{2},A_{2},Z_{2})\) be two attributed graphs in \(\mathbb{G}\)._  
\[d_{\mathbb{G}}(g_{1},g_{2})=\min_{\pi\in\Pi}\sum_{u,u^{\prime},x,v^{\prime}}\pi (u,v)\pi(u^{\prime},v^{\prime})(|A_{1}(u,u^{\prime})-A_{2}(v,v^{\prime})|+|Z_{ 1}(u)-Z_{2}(v)|+|Z_{1}(u^{\prime})-Z_{2}(v^{\prime})|) \tag{11}\]  
_where \(\Pi\) is the collection of measures over \(V_{1}\times V_{2}\) whose marginals are discrete uniform distributions over \(V_{1}\) and \(V_{2}\)._  
This definition allows us to state the continuity of GNN under this metric. **Lemma 1** (GNN continuity.). : _GNNs with continuous activation function are continuous on the topological space induced by the metric \(d_{\mathbb{G}}\)._  
Proof in Appendix A.  
GNNs are usually parameterized functions learnable with stochastic gradient descent, and hence fulfill this continuity constraint. Moreover, some attributes may be irrelevant, and should be discarded,  
Figure 5: Single level of the pyramid. Local information \(x^{l}(u)\) centered around node \(u\) is extracted from graph \(g^{l}\). The graph is coarsened to form a new graph \(g^{l+1}\). There, \(g^{l+1}(\mathcal{P}(u))\) captures information at a larger scale, centered on node \(\mathcal{P}(u)\). The pair \((x^{l}(u),g^{l+1}(\mathcal{P}(u)))\) is used as positive example in the negative sampling algorithm, and it helps to maximize mutual information between global and local view. or sometimes the graph is only characterized by some function (for example a linear combination) of the attributes. Such a function can be inferred directly from the dataset itself, simply by looking by the co-occurrences of some similar sub-graphs. Hence, the ability of GNN to learn features relevant for some specific task is an other advantage over **WL**. GCN [21] is as a baseline among this family of networks (see Section 2 for a brief survey). Unfortunately, [23] have shown that they behave badly when stacked. They propose Truncated Krylov GNN in replacement of GCN, correcting its flaws, with better theoretical guarantees and empirical evidence of their superiority over GCN. We chose it, encouraged by the promising results of early experiments. It amounts to consider, for a given node, a receptive field extended to the neighborhood of nodes at most at given distance \(a\). The resulting layer uses the normalized adjacency matrix \(\tilde{A}=D^{-\
icefrac{{1}}{{2}}}(A+I)D^{-\
icefrac{{1}}{{2}}}\) (like in GCN) of the graph \(g^{l}\):  
\[ \begin{split} g^{l+1}&=\text{Pool}(\tanh\left([g^{ l},\tilde{A}g^{l},\tilde{A}^{2}g^{l},\dots,\tilde{A}^{a}g^{l}]\theta^{l}_{1} \right))\theta^{l}_{2}+\theta^{l}_{3}\\ x^{l}&=\tanh\left([g^{l},\tilde{A}g^{l},\tilde{A}^{ 2}g^{l},\dots,\tilde{A}^{a}g^{l}]\theta^{l}_{4}\right).\end{split}  \tag{12}\]  
The vector \(\theta\) is made of the trainable parameters, and \([\dots]\) denotes the concatenation operation. We abused the notations, using \(x\) and \(g\) as real-valued vectors indexed by node set \(V\).