# Hierarchical and Unsupervised Graph Representation Learning with Loukas's Coarsening
## Appendix A Proofs  
Proof of Lemma 1.  
Proof.: We use Message Passing Neural Networks (MPNN) framework introduced in [43]. In order to demonstrate our theorem, we use the same notations as their paper. Let \(g=(V,A,Z)\in\mathbb{G}\). Let \(u\in V\) a node, and \(t\) the index of a layer. Then:  
\[h^{0}(u) =Z(u) \tag{1}\] \[m^{t+1}(u) =\sum_{v\in\mathcal{N}(u)}M_{t}(h^{t}(u),h^{t}(v),e_{uv})\] (2) \[h^{t+1}(u) =U_{t}(h^{t}(u),m^{t+1}(u)) \tag{3}\]  
Every GNN layer fall under MPNN framework. When the activation function used is continuous, the functions \(M_{t}\) and \(U_{t}\) are also continuous, because they involve matrix products (which are continuous operations). Moreover, the sum over \(\mathcal{N}(u)\) is finite because we consider finite graphs. Consequently, \(h^{t+1}(u)\) depend continuously of \(\{h^{t}(v),v\in\mathcal{N}(u)\}\) through \(S_{t}=U_{t}\circ M_{t}\). By composition, the result holds for any number of layers \(T\). Let \(F\) the resulting function on graph domain \(\mathbb{G}\), i.e., if \((V^{\prime},A^{\prime},Z^{\prime})=g^{\prime}=F(g)\) then \(A=A^{\prime}\) and \(V=V^{\prime}\) (GNNs do not modify topology), and for every node \(u\in V\) we have \(Z^{\prime}(u)=h^{T}(u)\).  
Figure 6: Six nearest neighbors of graphs in the learned latent space for four graphs from IMDB-b and MNIST. Column 0 corresponds to a randomly chosen graph, then the six nearest neighbors are drawn in increasing distance order from left to right (1 to 6).  
Let \((g_{n})_{n\in\mathbb{N}}\in\mathbb{G}^{\mathbb{N}}\) a sequence of attributed graphs such that \(\lim_{n\to\infty}g_{n}=g\) in the topological space induced by the metric \(d_{\mathbb{G}}\). Let \((\pi_{n}:V_{n}\times V)_{n\in\mathbb{N}}\) the corresponding set of transportation plans between \(g_{n}\) and \(g\). Let \(g_{n}^{\prime}=(V_{n}^{\prime},A_{n}^{\prime},Z_{n}^{\prime})=F(g_{n})\) and \(g^{\prime}=(V^{\prime},A^{\prime},Z^{\prime})=F(g)\). Then:  
\[\begin{split} d_{\mathbb{G}}(g_{n}^{\prime},g^{\prime})& \leq\sum_{u,u^{\prime},v^{\prime},v^{\prime}}\pi_{n}(u,v)\pi_{n}(u^{ \prime},v^{\prime})\left(|A_{n}^{\prime}(u,u^{\prime})-A^{\prime}(v,v^{\prime })|+|Z_{n}^{\prime}(u)-Z^{\prime}(v)|+|Z_{n}^{\prime}(u^{\prime})-Z^{\prime}( v^{\prime})|\right)\\ &=\sum_{u,u^{\prime},v^{\prime},v^{\prime}}\pi_{n}(u,v)\pi_{n}(u^ {\prime},v^{\prime})\left(|A_{n}(u,u^{\prime})-A(v,v^{\prime})|+|Z_{n}^{ \prime}(u)-Z^{\prime}(v)|+|Z_{n}^{\prime}(u^{\prime})-Z^{\prime}(v^{\prime})|\right) \end{split} \tag{10}\]  
Now, because \(\lim_{n\to\infty}g_{n}=g\) we have necessarily:  
\[\lim_{n\to\infty}\pi_{n}(u,v)\pi_{n}(u^{\prime},v^{\prime})|Z_{n}(u)-Z(u)|=0 \tag{11}\] \[\lim_{n\to\infty}\pi_{n}(u,v)\pi_{n}(u^{\prime},v^{\prime})|A_{n} (u,u^{\prime})-A(v,v^{\prime})|=0 \tag{12}\]  
The continuity of \(S_{t}\) allows to further conclude that:  
\[\lim_{n\to\infty}\pi_{n}(u,v)\pi_{n}(u^{\prime},v^{\prime})|Z_{n}^{\prime}(u)- Z^{\prime}(u)|=0 \tag{13}\]  
Finally, the right hand size of (10) must have limit \(0\), hence:  
\[\lim_{n\to\infty}g_{n}^{\prime}=g^{\prime} \tag{14}\]  
We just proved that \(\lim_{n\to\infty}g_{n}=g\) implies \(\lim_{n\to\infty}g_{n}^{\prime}=g^{\prime}\), which is precisely the definition of \(F\) being continuous w.r.t the topology induced by \(d_{\mathbb{G}}\).