Year: 2021

Abstract:
Graph representation learning has become important in order to understand and predict intrinsic structures in complex networks. A variety of embedding methods has in recent years been developed including the Latent Distance Modeling (LDM) approach. A major challenge is scaling network embedding approaches to very large networks and a drawback of LDM is the computational cost invoked evaluating the full likelihood having O(N2) complexity, making such analysis of large networks infeasible. We propose a novel multiscale hierarchical estimate of the full likelihood of LDMs providing high-details where the likelihood approximation is most important while scaling in complexity at O(N logN). The approach relies on a clustering procedure approximating the Euclidean norm of every node pair according to the multiscale hierarchical structure imposed. We demonstrate the accuracy of our approximation and for the first time embed very large networks in the order of a million nodes using LDM and contrast the predictive performance to prominent scalable graph embedding approaches. We find that our approach significantly outperforms these existing scalable approaches in the ability to perform link prediction, node clustering and classification utilizing a surprisingly low embedding dimensionality of two to three dimensions whereas the extracted hierarchical structure facilitates network visualization and interpretation. The developed scalable hierarchical embedding approach enables accurate low dimensional representations of very large networks providing detailed visualizations that can further our understanding of their properties and structure.

text: Graph representation learning has become important in order to understand and predict intrinsic structures in complex networks. A variety of embedding methods has in recent years been developed including the Latent Distance Modeling (LDM) approach. A major challenge is scaling network embedding approaches to very large networks and a drawback of LDM is the computational cost invoked evaluating the full likelihood having O(N2) complexity, making such analysis of large networks infeasible. We propose a novel multiscale hierarchical estimate of the full likelihood of LDMs providing high-details where the likelihood approximation is most important while scaling in complexity at O(N logN). The approach relies on a clustering procedure approximating the Euclidean norm of every node pair according to the multiscale hierarchical structure imposed. We demonstrate the accuracy of our approximation and for the first time embed very large networks in the order of a million nodes using LDM and contrast the predictive performance to prominent scalable graph embedding approaches. We find that our approach significantly outperforms these existing scalable approaches in the ability to perform link prediction, node clustering and classification utilizing a surprisingly low embedding dimensionality of two to three dimensions whereas the extracted hierarchical structure facilitates network visualization and interpretation. The developed scalable hierarchical embedding approach enables accurate low dimensional representations of very large networks providing detailed visualizations that can further our understanding of their properties and structure.

heading: 1 INTRODUCTION
text: Networks naturally arise in a plethora of scientific areas to model the interactions between entities from physics to sociology and biology, with many instances such as collaboration, protein-protein interaction, and brain connectivity networks (Newman, 2003). In recent years Graph Representation Learning (GRL) approaches have attracted great interest with their outstanding performance compared to the classical techniques for the challenging network analysis problems such as link prediction (Liben-Nowell & Kleinberg, 2003; Backstrom & Leskovec, 2011), node classification (Getoor & Taskar, 2007; Grover & Leskovec, 2016), and community detection (Fortunato, 2010).
Many existing GRL methods (Hamilton et al., 2017b; Zhang et al., 2020) mainly aim to capture the underlying intrinsic relationships among the nodes by either performing random walks (Perozzi et al., 2014; Grover & Leskovec, 2016) over the network or designing a matrix capturing the first and high order node proximities (Cao et al., 2015; Ou et al., 2016). However, they require high computational and space costs because of the exact node sampling procedures or the expensive factorization of dense proximity matrices. The recent Graph Neural Networks (GNNs) (Hamilton et al., 2017b; Zhang et al., 2020; Wang et al., 2016) methods provide effective tools in learning the node representations by leveraging the side information such as node attribute features; nevertheless, they also face computational difficulties, especially for large-scale networks consisting of millions of nodes and edges. Although the recent studies aim to alleviate the computational burden of the algorithms through matrix sparsification tools (Qiu et al., 2019) or hierarchical representations (Bhowmick et al., 2020; Chen et al., 2018), the performance of the methods in the downstream tasks significantly drops, and they require larger embedding sizes to compensate for the loss.
Latent Space Models (LSMs) for the representation of graphs have been quite popular over the past years, especially for social networks analysis (Hoff et al., 2002). LSMs utilize the generalized linear model framework to obtain informative latent node embeddings while preserving network characteristics. The choice of latent effects in modeling the link probabilities between the nodes leads to different expressive capabilities characterizing network structure. We consider the Latent Distance Model (LDM) (Hoff et al., 2002) with the Euclidean norm, in which nodes are placed closer in the latent space if they are similar or vice-versa. LDM obeys the triangle inequality and thus naturally represents transitivity and network homophily. These methods are attractive due to their simplicity, as they define well-structured inference problems and are characterized by high explanatory power. The time and space complexities are their main drawbacks, which scale quadratically with the number of nodes in the graph.
Many real-world networks can be expressed as hierarchical structures of different scales (Ravasz & Barabási, 2003). For this purpose, several hierarchical network modeling tools have been proposed, such as the extensions of the stochastic block model to binary and multifurcating hierarchical structures (Clauset et al., 2008; Roy et al., 2007; Blundell et al., 2012; Herlau et al., 2012; 2013) as well as agglomerative (Blondel et al., 2008; Ahn et al., 2010) and recursive partitioning procedures (Li et al., 2020) relying on various measures of similarity. Learning the node representations preserving the hierarchical structure of the network is also a very promising task, and it can facilitate the visualization and the understanding of the inner dynamics of the network.
In this work, we propose the Scalable Hierarchical Latent Distance Model (SH-LDM) combining embedding and hierarchical representations for graph representation learning. Importantly, the hierarchical structure imposed in (SH-LDM) reduces the total time and space complexity of the LDM to linearithmic in terms of the number of nodes (i.e., O(N logN)) at the same time providing accurate interpretable representation of structure at different scales. Using the SH-LDM we embed moderate sized and large-scale networks containing more than a million nodes and establish the performance of LDM in terms of link prediction and node classification to existing prominent scalable graph embedding approaches. We further highlight how the inferred hierarchical organization can facilitate accurate visualization of network structure even when using only D = 2 dimensional representations providing favorable performance in all the considered GRL tasks; link-prediction, node classification, node clustering, and network reconstruction.
In summary, our contributions are to reconcile embedding and hierarchical representations providing accurate linearithmic approximation of the full likelihood, efficient inference, enhanced visualization and network compression utilizing ultra-low embedding dimensions and hierarchical representations.

heading: 2 THE SCALABLE HIERARCHICAL-LATENT DISTANCE MODEL
text: We presently concentrate our study on the case of undirected networks, but we note that our approach generalizes to both directed and bipartite graphs as described in the supplementary material. Let G = (V,E) be a graph where N := |V | is the number of nodes and YN×N = [yi,j ] be the adjacency matrix of the graph such that yi,j = 1 if there is an edge between the nodes vi and vj and otherwise it is equal 0 for all 1 ≤ i < j ≤ N .
A Latent Space Model (LSM) defines a RD-dimensional latent space in which every node of the graph is characterized through the unobserved but informative node-specific variables {zi ∈ RD}. These variables are considered sufficient to describe and explain the underlying relationships between the nodes of the network, such as transitivity and homophily. The probability of an occurring edge between an ordered pair of the graph is considered conditionally independent given the unobserved latent positions. Consequently, the total probability distribution of the network can be written as:
P (Y |Z,θ) = N∏ i<j p(yi,j |zi, zj), (1)
A popular and convenient parameterization of equation 1 for binary data is through the logistic regression model (Hoff et al., 2002; Handcock et al., 2007; Krivitsky et al., 2009; Hoff, 2005). In contrast, we adopt the Poisson regression model as proposed in Hoff (2005) under a generalized linear model framework for the LSM. The use of a Poisson likelihood for modelling binary relationships in a network does not decrease the predictive performance nor the ability of the model to detect the network structure, as shown in Wind & Mørup (2012) and also generalize the analysis to integer weighted graphs. In addition, the exchange of the logit to a log link function when transitioning from a Bernoulli to a Poisson model defines nice decoupling properties over the predictor variables in the likelihood (Karrer & Newman, 2011; Herlau et al., 2014). Utilizing the Poisson Latent Distance Model (LDM) of the LSM family framework, the rate of an occurring edge depends on a distance metric between the latent positions of the two nodes. We consider the LDM with node-specific biases or random-effects (Hoff, 2005; Krivitsky et al., 2009) such that the expression for the Poisson rate becomes:
λij = exp ( γi + γj − d ( zi, zj )) . (2)
where γi denotes the node-specific random-effects and dij(·, ·) denotes any distance metric obeying the triangle inequality { dij ≤ dik + dkj , ∀(i, j, k) } . Considering variables z as the latent charac-
teristics, Eq. equation 2 shows that similar nodes will be placed closer in the latent space, yielding a high probability of an occurring edge and thus modeling homophily and satisfies network transitivity and reciprocity through the triangle inequality whereas the node specific bias can account for degree heterogeneity. The conventional LDM utilizing a global bias, γg , corresponds to the special case in which γi = γj = 0.5γg . As in Hoff et al. (2002), we presently adopt the Euclidean distance as the choice for the distance metric dij(·, ·).

heading: 2.1 SCALING THE LATENT DISTANCE MODEL
text: Optimizing the LDM requires the computation of the log-likelihood which is defined as the sum over each ordered pair of the network as:
logP (Y |λ) = ∑ i<j ( yij log(λij)− λij ) = ∑ i<j:yij=1 log(λij) − ∑ i<j λij , (3)
For brevity, we presently ignore the linear scaling of the above log-likelihood by dimensionality D. Large networks are highly sparse (Barabási & Pósfai, 2016) with the number of edges for very sparse networks being proportional to the number of nodes in the network. As a result, the computation of the link contribution ∑ yi,j=1
log(λi,j) is relatively cheap scaling linearithmic or sub-linearithmic (see also supplementary material). This is not the case for the second term which still requires the computation of all node pairs scaling as O(N2) making the evaluation of the above likelihood infeasible for large networks.
To reduce the complexity, we propose to approximate the non-link term O(N2) using blocks, i.e., akin to stochastic block models White et al. (1976); Holland et al. (1983); Nowicki & Snijders (2001), in which we when grouping the nodes into K clusters define the rate between block k and k′ in terms of their distance between centroids,
∑ i<j λij ≈ K∑ k ( ∑ i,j∈Ck e(γi+γj−||zi−zj ||2) + ∑ i∈k,j /∈Ck e(γi+γj−||µk−µk′ ||2) )
= ( K∑ k ∑ i,j∈Ck e(γi+γj−||zi−zj ||2) ) + ∑ k>k′ e−||µk−µk′ ||2 (∑ i∈Ck eγi )( ∑ j∈Ck′ eγj ) , (4)
where µk denotes the k’th cluster centroid of the set C = {C1, . . . , CK}, and has absorbed the dependency over the variables Z.
Overall, considering the main principle of the LDM that connected and homophilic nodes will be placed closer in the latent space, this approximation generalizes this principle introducing a clustering procedure that obeys ”cluster-homophily” and ”cluster-transitivity” over the latent space. More specifically, we can assume that closely related nodes will be positioned in the same cluster while related or interconnected clusters will also be positioned close in the latent space, providing an accurate approximation schema. Assuming equally sized clusters having N/K nodes the first part scales O(N2/K) whereas the second part scales O(K2). As such, there is an undesirable inherent trade-off in which the first term reduces by K but the second term increases quadratically. Thus, by setting K = N/log(N) we reduce the first part to scale asO(N logN) but at the cost of the second term scaling O(N2/log(N)2) which for large networks is still prohibitive.

heading: 2.1.1 HIERARCHICAL APPROXIMATION OF THE LATENT DISTANCE MODEL
text: For the second term to be scalable, we need for K = N/log(N) the contribution for the second term to scale also at O(N logN). To achieve this, we adopt a multiresolution KD tree (mrkd-tree) structure similar to Moore (1999) which endorses a hierarchical divisive clustering architecture. The root of the tree contains the total amount of latent variables Z. At every level of the tree, we perform partitioning of the tree-nodes which are not considered as leafs. The tree-nodes belonging to a specific level are considered as the clusters for that specific tree height. Every novel partition of a non-leaf node is performed only on the set of points allocated to the parent tree-node (cluster). A node is considered as a leaf if the corresponding cluster contains less than a specific amount of datapoints which for K = N/log(N) is set to be approximately equal to N/K = logN . For every level of the tree, we consider the pairwise distances of datapoints belonging to different treenodes as the distance between the corresponding cluster centroids, as illustrated by Figures 1b, 1c and 1d. Based on these distances, we calculate the likelihood contribution of these approximation blocks and continue down the tree for the non-leaf tree-nodes. In the last level (or when all treenodes are considered as leafs) we calculate analytically the inner cluster pairwise distances for the corresponding likelihood contribution of analytical blocks, as shown by Figure 1e.
We can thereby define a Scalable Hierarchical-Latent Distance Model with Random Effects (SHLDM-RE) as:
logP (Y |λ) =∑yi,j=1 ( γi + γj − ||zi − zj ||2 ) −∑KLkL (∑ i,j∈CkL e(γi+γj−||zi−zj ||2) ) (5)
−∑Ll (∑ kl>k′l e −||µkl−µk′l ||2 (∑ i∈Ckl eγi )(∑ j∈Ck′
l
eγj )) ,(6)
where l = [1, · · ·L] denotes the l’th mrkd-tree level, kl is the index representing the cluster id for the different tree levels and µkl the corresponding centroid. We also consider a Scalable HierarchicalLatent Distance Model (SH-LDM) without the random effects setting γi = 0.5γg . For a multifurcating tree splitting in C clusters and having N/log(N) terminal nodes (clusters) the number of internal nodes areO(N/(C logN)) and each node needs to evaluateO(C2) pairs providing an overall complexity of O(NC/ logN), thus C ≤ logN2 to achieve O(N logN) scaling (Epp, 2010).

heading: 2.1.2 DIVISIVE PARTITIONING USING K-MEANS WITH A EUCLIDEAN DISTANCE METRIC
text: Whereas the likelihood in equation 6 can be directly minimized by assigning nodes to the clusters given by the tree structure this evaluation for all N nodes scales prohibitively as O(N2/ logN).
To reduce this scaling we use a more efficient divisive partitioning procedure. For efficiency instead of considering minimizing the full expression in equation 6 we consider minimizing the Euclidean norm ||µkl − µk′l ||2. The divisive clustering procedure thus relies on the following Euclidean norm objective
J(r,µ) = N∑ i=1 K∑ k=1 rik||zi − µk||2, (7)
where k denotes the cluster id, zi is the i’th data observation, rik the cluster responsibility/assignment, and µk the cluster centroid.
This objective function is unfortunately not accounted for by existing k-means clustering algorithms relying on the squared Euclidean norm. We therefore presently derive an optimization procedure for k-means clustering with Euclidean norm utilizing the auxiliary function framework of Tsutsu & Morikawa (2012) developed in the context of compressed sensing. We define an auxiliary function for Eq. equation 7 as:
J+(φ, r,µ) = N∑ i=1 K∑ k=1 rik ( ||zi − µk||22 2φik + 1 2 φik ) , (8)
where φ are the auxiliary variables. Thereby, minimizing Eq. equation 8 with respect to φnk yields φ∗ik = ||zi − µk||2 and by plugging φ∗ik back to Eq. equation 7 we obtain J+(φ∗, r,µ) = J(r,µ) verifying that Eq. equation 8 is indeed a valid auxiliary function for Eq. equation 7. The algorithm proceeds by optimizing cluster centroids as µk = (∑ i∈k xi φik / ∑ i∈k 1 φik ) and assigning points to
centroids as argminC = ∑K k=1 ∑ z∈Ck ( ||z−µk||22 2φk + 12φk ) upon which φk is updated. The overall complexity of this procedure is O(TKND) (Hartigan & Wong, 1979) where T is the number of iterations required to converge.
A simple approach to construct the tree structure would be to use the above Euclidean k-means procedure to split the nodes intoK = N/ log(N) clusters and construct the tree according to agglomeration as in hierarchical clustering. Unfortunately, such a strategy is prohibitive for K = N/ logN , and maximallyK = logN clusters can be obtained for scaling ofO(N logN). It would be tempting to continue splitting into logN clusters, however, for a balanced multifurcating tree with N/ logN leaf clusters this will result in a height scaling as O(logN/ log logN) and thus an overall complexity of O(N logN2/ log logN) (Epp, 2010). Whereas using a balanced binary tree at all levels below the root results in a height scaling asO(logN) providing an overall complexity when including the linear scaling by dimensionality D of O(DN logN) for the SH-LDM. Figure 1a illustrates the resulting tree for a small problem of N = 64 nodes in which we first split into 4 (≈ log(64)) clusters and subsequently create binary splits until each cluster contains 4 (≈ log(64)) nodes.

heading: 2.2 RELATED WORK
text: In recent years, we have witnessed a tremendous increase in the number of GRL methods. The leading initial works are the random walk-based methods (Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015; Nguyen & Malliaros, 2018), which generate fixed-length node sequences by following a strategy and leverages the Skip-Gram algorithm (Mikolov et al., 2013) to learn the node representations. Another prominent class of techniques is the matrix factorization-based algorithms (Cao et al., 2015; Ou et al., 2016; Zhang et al., 2020). They extract the embedding vectors by decomposing a designed feature matrix. The neural networks are undoubtedly one of the most outstanding models, and many models (Hamilton et al., 2017b; Wang et al., 2016; Zhang et al., 2020; Cao et al., 2016; Vincent et al., 2010; Kipf & Welling, 2017; Hamilton et al., 2017a) allowing to incorporate the node attributes with the network structure when learning the embeddings have been proposed for graph-structured data. Although these approaches are quite effective in downstream tasks, they require a high computational burden, making them inapplicable for large-scale networks. Therefore, the recent works (Bhowmick et al., 2020; Zhang et al., 2019) capitalize on the computational challenges emerging for large networks by either incorporating fast approximation techniques with the existing models (Qiu et al., 2019) or developing novel approaches relying on fast hashing schemes (Yang et al., 2019; Zhang et al., 2018). Our approach is related to current efforts in scaling graph embedding approaches for the analysis of very large networks.
The most related scalable study to our method is the work for the LDM Raftery et al. (2012) where the O(N2) complexity is lowered to O(cE) with c N via a case-control approach motivated by epidemiology studies. While the overall complexity of the case-control model can scale the analysis of LDMs to massive networks creating the All-Pairs Shortest Paths matrix that is required to perform the proposed stratified sampling over non-links, is not possible for large networks, both in terms of time and space complexity (> O(N2)) and the authors did not consider networks larger than N = 2716 nodes. In the supplementary material, we therefore examine a scalable version of the case-control approach. In order to scale the case-control model to the order of millions of nodes as presently considered we exchanged the stratified sampling with a uniform sampling procedure which as argued by the authors may not be the best estimator. We conclude that also the casecontrol approach can be used to successfully scale the LDMs. Notably, the case-control approach does not yield a hierarchical representation of network structure as the presently developed SHLDM. However, the developed hierarchical clustering procedure can be used as a post-processing step to extract hierarchical representations from the learned embeddings.

heading: 3 EXPERIMENTS
text: We extensively evaluate the performance of our approach compared to other baseline approaches on ten networks of various sizes and structures. We consider each network as undirected and unweighted for the consistency of the experiments, and the detailed statistics of the networks are given in Table 1. We have conducted all the experiments regarding the SH-LDM and SH-LDM-RE on a 32 GB Tesla V100 GPU machine. For the SH-LDM and SH-LDM-RE models, we optimize the negative log-likelihood via the Adam (Kingma & Ba, 2017) optimizer while setting the learning rate to lr = 0.1 for all networks. The parameters of the baseline approaches have been tuned. Because of the limitation in the number of pages, the details of the parameter settings, the datasets as well as a scalable spectral clustering initialization scheme for SH-LDM are provided as supplementary materials. In the following we report results on the prominent graph representation learning tasks; link prediction, node classification, and network visualization. For the network visualization we further include quantitative evaluations in terms of network reconstruction and node clustering quality.
Link Prediction: We report results for the area under the curve of the receiver operator characteristic (AUC) whereas we defer the corresponding Precision-Recall AUC to the supplementary material. For the experimental setup, we follow the commonly applied strategy (Perozzi et al., 2014; Grover & Leskovec, 2016), and we remove half of the edges of a given network by keeping the residual network connected. For the large-scale networks , this approach is infeasible, so we apply a scalable evaluation technique (Bhowmick et al., 2020; Zhang et al., 2018). We hide 30% of the edges of a
given initial network and consider the greatest connected component (GCC) of the residual network to learn the node representations. We utilize the residual network to learn the node embeddings and report the best performing binary operator (Grover & Leskovec, 2016) used for logistic regression with L2 regularization (detailed list of the operators are given in the supplementary material). For SH-LDM and SH-LDM-RE the predictions are made directly based on the learned Poisson rates of the test set pairs {ij}, i.e. λij = exp (γi + γj − ||zi − zj ||2). Error bars for the following AUC scores were found to be in the scale of 10−3 and thus provided in the supplementary material.
Results for the moderate-sized networks are given in Table 2. We here observe that the SH-LDM and SH-LDM-RE perform significantly better or on par with the performance of the considered baseline approaches. In particular, the SH-LDM and SH-LDM-RE perform better than all baselines when D = 2 which highlights the superiority of LDMs in learning very low-dimensional network representations that accurately accounts for the network structure. We further observe that representing degree heterogeneity with random effects provides extended representational power as the SH-LDM-RE consistently outperforms the SH-LDM. In Figure 2 in the first and second panel we provide the underlying hierarchical structure, as well as an analysis of the accuracy of the SHLDM when contrasted with the full likelihood evaluated on the moderate-sized network Facebook (results for more networks are provided in the supplementary material). We here observe that the SH-LDM likelihood approximation corresponds well with the true full likelihood providing systematically slightly lower likelihood estimates which we attribute to the SH-LDM inference minimizing the hierarchical approximation. In Figure 2 third panel we observe the predictive performance as a function of latent dimension D and here in general observe that modest improvements in the predictive performance are attained when increasing the embedding dimensions from D = 2 to D = 8 with no further improvements increasing to D = 128 highlighting the efficiency in which SHLDM and SH-LDM-RE utilize very low-dimensional representations. Results for the large-scale networks are given in Table 3. Again we observe that SH-LDM-RE outperforms the baselines only being surpassed in performance by NETSMF for the Flixster dataset. Notably, we again observe very good performance for the SH-LDM-RE, but also NETSMF when utilizing the very low embedding dimension of D = 2. In Figure 2, the fourth panel we investigate the convergence of the best performing SH-LDM-RE for the large networks and here observe that the model rapidly converges such that we already after a couple of thousand iterations (scalable regime) obtain competitive performance for link prediction which then gently increases until convergence.
Node classification: We assess the success of the proposed framework in the uni-label/multi-label classification task and provide the Micro-F1 scores (Macro-F1 scores are reported in the supplementary). For the experimental setup, we randomly pick 50% of nodes as the training set and use the rest as the testing set. For an accurate comparison across different methods we used two simple classifiers, one linear (logistic regression) and one non-linear (linearithmic k-nearest neighbors classifier (kNN )) and reported the highest scores. We found that all methods benefit from using kNN. The number of neighbors was set to k = 10 (similar results were obtained with higher choices for k as well). Lastly, we report the average Micro-F1 scores across 10 repeated trials. Results
for the uni-labeled Cora and DBLP networks are reported in the two leftmost columns of Table 4. We observe that SH-LDM-RE and SH-LDM significantly outperform the baselines for the regimes of D = 2, 3 with only LOUVAINNE being competitive. Results for large-scale and multi-labeled networks Amazon and YouTube are provided by the two rightmost columns in Table 4. Again, the proposed framework outperforms the baselines for the low-dimensional regime with LOUVAINNE being on par. The superiority of SH-LDM for low-dimensions verifies that homophily and transitivity can express accurately the underlying node class structure.
Network visualization: The existing graph representation learning literature mainly focuses on embeddings with dimensionality greater than D = 2 and 3. As a direct consequence explanatory analysis and network visualizations rely on dimensionality reduction frameworks, typically using the t-distributed Stochastic Neighbor Embedding (t-SNE) van der Maaten & Hinton (2008). In order to verify the validity of the t-SNE constructed Space (t-SNES), in Figure 3 we provide the labeled-colored True Embedding Space (TES) for D = 2, as well as for D = 2 and D = 128 mapped to D = 2 via the use of t-SNE for Cora and DBLP. We report the performance over the tasks of network reconstruction, clustering and classification respectively reporting the AUC, the Normalized Mutual Information (NMI) and Micro-F1 scores. Our proposed SH-LDM and SHLDM-RE have the most consistent and reliable scores across both the TES and the t-SNES. For the network reconstruction task we see relatively small decrease in AUC-ROC when transitioning from TES to t-SNES, meaning that the network structure is preserved. For the classification task we observe that SH-LDM SH-LDM-RE benefit from transitioning to t-SNES as the scores for both D = 2 and D = 128 increase, as summarized in Figure 3 and Table 4. This is not the case for NODE2VEC and LOUVAINNE as their Micro-F1 scores dramatically drop. For most methods NMI benefits when transitioning to t-SNES with SH-LDM giving on par performance for Cora while SH-LDM-RE has the highest overall NMI for DBLP (D=128+t-SNE). We attribute the increase in clustering performance while using high-dimensions and t-SNE (especially for DBLP ) to the fact that peripheral nodes which act as noise are grouped in a unique cluster, as it is evident from the third and sixth columns in Figure 3. The visualization experiments positions our proposed models as the
silver lining between consistent performance across all GRL downstream tasks as well as network visualizations. All baseline results are available in the supplementary.

heading: 4 CONCLUSION AND LIMITATIONS
text: We proposed the Scalable Hierarchical Latent Distance Model (SH-LDM), a scalable approach embedding networks using the latent distance model (LDM) enabling characterization of structure at multiple scales. Notably, the approximation provides high accuracy where the likelihood approximation is most important while scaling in complexity by O(DN logN). We analyzed ten networks from moderate sizes to large-scale and found that the SH-LDM had favorable performance when compared to existing scalable embedding procedures. In particular, we observed that the SH-LDM well predicts links and node classes utilizing a very low embedding dimension of D = 2 providing favorable network visualizations and characterization of structure at multiple scales. The SH-LDM is based on the latent distance model (LDM) and thus good at characterizing transitivity and homophily whereas the random effects enable to take degree heterogeneity into account. Notably, the SH-LDM suffers from the limitations of the LDM and is thus unable to account for stochastic equivalence (Hoff, 2007). Future work should thus investigate how the proposed hierarchical embedding structure can be imposed on more flexible embedding procedures such as the eigenmodel.

Review summaries:
The authors of this paper propose using Latent Distance Modeling (LDM) for embedding networks. LDM is an old model and simply relies on estimating the probability of an edge based on the distance of the respective embeddings of the two endpoints (+ some fixed-effect terms that capture the degree nonhomogeneity. The problem with this approach is that evaluating the likelihood function to maximize requires computing all pairwise distances between nodes in the graph -- thus scales quadratically with the size of the graph. To tackle this problem the authors propose grouping nodes (based on their embeddings in each iteration) into clusters and only evaluating the pairwise distance between the centroids of the clusters. This allows for faster evaluation of the likelihood function. Also, according to the authors, the LDM model (with and without fixed effects terms for each node), is able to achieve higher performance in different tasks (classification and link prediction) than other popular embedding methods (like DeepWalk or Node2Vec) using just 2 to 3 dimensions for the node embeddings. As a reference, the SoA approaches usually use 128 dimensions to achieve good performance.

The focus of the paper is in suggesting a node embedding method that uses hierarchy to ensure scalability. The proposed method, “Scalable Hierarchical Latent Distance Model” ( SH-LDM), aims to reconcile embedding and hierarchical network representations. This method is based on the following components: -	__Foundational component:__ a Latent Distance Model. Latent Space Models are a special type of node embedding method that uses  the generalized linear model framework to obtain latent node embeddings while preserving network characteristics. In the case of the Latent Distance Models, this means that nodes are placed closer in the latent space if they are closer together. In particular, here, __representing the edges as sampled from a Poisson distribution__ with parameter $\lambda_{ij}$: $$ \lambda_{ij} = \gamma_i + \gamma_j - || z_i -z_j||_2 $$ Finding a solution in terms of $z_i$ s of this model --- which is not new --- is the object of this paper.  - __Component 2:  Hierarchy:__ To make the fitting of this model more scalable, the authors approximate the distance r $ d(z_, z_j) = || z_i  - z_j|| $ by the distance between centroids $|| \mu_{C_i} -\mu_{C_j}||, \quad \forall C_i\neq C_j$.  - __Component 3: Scalable division of the data in clusters__ The clusters are not known. So the authors use a multiresoluiton KD tree to split the data into K clusters of equal sizes. It further relies on an optimization procedure for k-means clustering with Euclidean norm utilizing the auxiliary function framework of Tsutsu & Morikawa to perform optimization scalably. This allows the partition of the data into $K = \log(N)$ clusters.  This results in a reduction of  the total time and space complexity of the LDM to O(N logN)). The authors then proceed to validate their method using a set of experiments:   1. node classification   2. edge prediction   3. clustering and hierarchical structure recovered in the latent space.  with reasonable performance on a subset of the dataset. 

The paper studies the node-level representation learning problem. It proposes SH-LDM, which combines the embedding and hierarchical representations for scalable graph representation learning. The hierarchical structure in SH-LDM reduces the time and space complexity of the LDM to linearithmic in terms of the number of nodes. The proposed model works well on link prediction and node classification with low embedding dimensions.