Scalable Hierarchical Embeddings of Complex Networks
Authors: Nikolaos Nakis
Abdulkadir CELIKKANAT
Sune Lehmann
Morten Mørup
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Representation Learning
Latent Space Model
Complex Networks
Scalable Network embeddings
Link prediction
Low dimension graph representations

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(N^2) 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(NlogN). 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.

Under review as a conference paper at ICLR 2022
SCALABLE HIERARCHICAL EMBEDDINGS OF COM- PLEX NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph representation learning has become important in order to understand and predict intrinsic structures in complex networks. A variety of embedding meth- ods has in recent years been developed including the Latent Distance Modeling (LDM) approach. A major challenge is scaling network embedding approaches very large networks and drawback of LDM is the computational cost invoked evaluating the full likelihood having O(N²) complexity, making such analysis of large networks infeasible. We propose novel multiscale hierarchical estimate of the full likelihood of LDMs providing high-details where the likelihood ap- proximation is most important while scaling in complexity at O(N log N). The approach relies 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 the order of a million nodes using LDM and contrast the pre- dictive performance to prominent scalable graph embedding approaches. We find that our approach significantly outperforms these existing scalable approaches the ability 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 interpre- tation. The developed scalable hierarchical embedding approach enables accurate low dimensional representations of very large networks providing detailed visual- izations that can further our understanding of their properties and structure.
INTRODUCTION
Networks naturally arise in plethora of scientific areas model the interactions between entities from physics to sociology and biology, with many instances such as collaboration, protein-protehi interaction, and brain connectivity networks (Newman 2003). In recent years Graph Representa- tion Learning (GRL) approaches have attracted great interest with their outstanding performance compared the classical techniques for the challenging network analysis problems such as link prediction (Libel-Nowell & Kleinberg] 2003 Backstrom & Leskoved 201T). node classification (Getoor Taskar 2007 Grover & Leskovee 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 (Per- ozzi et al. 2014 Grover & Leskoved, 2016) over the network or designing a matrix capturing the first and high order node proximities (Cao et al., 2015 Ou 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., (016) methods provide effective tools in learning the node representations by leveraging the side information such as node attribute features; never- theless, 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. |2200] CCen et al.) 2018), the performance of the methods in the downstream tasks significantly drops, and they require larger embedding sizes compensate for the loss.

---

Under review as a conference paper at ICLR 2022
K
K
K
K
Figure 1: Schematics of the distance matrix calculation for a hierarchical structure of tree height
L = 3 and number of observations N = 64.
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 charac- teristies. 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 al., 2002) with the Euclidean norm, in which nodes placed closer in the latent space 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 num- ber of nodes in the graph.
Many world networks can be expressed hierarchical structures of different scales (Ravasz & Barabá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 struc- tures (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 jet al. (220)) relying various measures of similarity. Learning the node representations preserv- ing 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 hier- archical 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 log N)) at the same time providing curate interpretable representation of structure at different scales. Using the SII-LDM we embed moderate sized and large-scale networks containing more than million nodes and establish the per- formance 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 rep- resentations providing favorable performance in all the considered GRL. tasks; link- fink-rreiction, 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 visualiza- tion and network compression utilizing ultra-low embedding dimensions and hierarchical represen- tations.
2 THE SCALABLE HIERARCHICALL-LTENN DISTANCE MODEL
We presently concentrate study on the case of undirected networks, but note that our approach generalizes to both directed and bipartite graphs as described the supplementary material. Let
(V. E) be graph where N = V is the number of nodes and YNx N [Vt.]] be the adjacency
matrix of the graph such that yi.j = 1 if there is an edge between the nodes U; and Uj and otherwise
it is equal for all < N.
2

---

Under review as a conference paper at ICLR 2022
A Latent Space Model (LSM) defines R??-dimensionl latent space in which every node of the graph is characterized through the unobserved but informative node-specific variables {z, E R²). These variables are considered sufficient to describe and explain the underlying relationships be- tween the nodes of the network, such as transitivity and homophily. The probability of an occurring edge hetween ordered pair of the graph is considered conditionally independent given the unob- served latent positions. Consequently, the total probability distribution of the network can be written as:
Z.Y|Z.0) II ply. y Zz 2ÿ).
A popular and convenient parameterization of equation 1 for binary data is through the logistic re- gression model (Hoff et al., 2002, Handcock et al. 2007; Krivitsky et al. 2009; Hoff 2005). In contrast, adopt the Poisson regression model as proposed in Hoff (2005) under generalized linear model framework for the LSM. The use of a Poisson likelihood for modelling binary rela- tionships in network does not decrease the predictive performance
the ability of the model to detect the network structure, as shown in |iidd & Mørup (2012) and also generalize the analysis to integer weighted graphs. In addition, the exchange of the logif to log link function when transi- tioning from a Berouulii 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 La- tent Distance Model (LDM) of the LSM family framework, the rate of an occurring edge depends on distance metric between the latent positions of the two nodes. We consider the LDM with node-specific biases or random-effeed (Hoff) 2005 Krivitsky et al. 2009) such that the expression for the Poisson rate becomes:
Xi = exp (1s + T a(z,,2))
where 7/ denotes the node-specific random-effects and di denotes any distance metric obeying
the triangle inequality { di. S d, + daj; }(i,j,)) Considering variables the latent charac- teristics, Eq. equation 2 shows that similar nodes will be placed closer in the latent space, yielding a high probability of occurring edge and thus modeling homophily and satisfies network transi- tivity and reciprocity through the triangle inequality whereas the node specific bias can account for degree heterogeneity. The conventional LDM utilizing a global bias, 79, corresponds the special case in which %/- 7 = 0.5y As in Hoff et al. (2002), we presently adopt the Euclidean distance as the choice for the distance metric day (:.).
2.1 SCALING THE LATENT DISTANCE MODEL
Optimizing the LDM requires the computation of the log-likelihood which is defined as the sum over each ordered pair of the network as:
log P(YI)) = Σ (n log(de)) -2i))
Σ i<jグE=1
log(Agg)
ΣNy. Xij SKJ
(3)
For brevity, we presently ignore the linear scaling of the above log-likelihood by dimensionality D. Large networks are highly sparse (Barabási & Pósfai 2016) with the number of edges for very sparse networks being proportional to the number of nodes the network. As a result, the computation of the link contribution Ey.,= log(As,)) is relatively cheap scaling linearithmic or sub-line lubllinearithmic (see also supplementary material). This is not the for the second term which still requires the computation of node pairs scaling as ( 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.c., akin to stochastic block models White et al.] (197)); Holland et al. (1983); Nowicki & Snijders) (200)), in which we when grouping the nodes into K clusters define the rate between block & and k in terms of their distance between centroids,
3

---

Under review as a conference paper at ICLR 2022
K
Σ
Nis RJ
eloctrs 10-7ss-llxx- (lox--
1.EEC
iER.jECk
(4)
Σ
--llm 1-lllu--ue -x
Σ
L.JEC
k>kk'
VEE
JEC22
where (4 denotes the k'th cluster centroid of the set C = -CI,,.., .....,,C), 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 cluster- ing procedure that obeys "cluster-homophily and "aassterrtansttivitt" 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 ac- curate approximation schema. Assuming equally sized clusters having N/K nodes the first part scales O / K) whereas the second part scales O(K²). 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 as ONN log N) but at the cost of the second term scaling O(N2 (log(N)) which for large networks is still prohibitive.
2.1.1 HIERARCHICAL APPROXIMATION OF THE LATENT DISTANCE MODEL
For the second term to be scalable, we need for K N (N)) the contribution for the second term to scale also at ON log N). To achieve this, we adopt a multiresolution KD tree (mrkd-tree) structure similar to Moore (999) 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 specific level are considered of a non-leaf node is performed only on the set of points allocated to the parent tree- tree-node (cluster). A node is considered datapoints which for = N/log(N N) is set to be approximately equal to N/K = log N. For every level of the tree, we consider the pairwise distances of datapoints belonging different tree- nodes as the distance between the corresponding cluster centroids, as illustrated by Figures [b] Ic and ld] 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 tree- nodes are considered as leafs) we calculate analytically the inner cluster pairwise distances for the corresponding likelihood contribution of analytical blocks, as shown by Figure Te
the clusters for that specific tree height. Every novel partition
leaf if the corresponding cluster contains less than specific amount of
We can thereby define a Scalable Hierarchical-L Distance Model with Random Effects (SH- LDM-RE) as:
log P(YI)) = =Em, =m
71 7/ - -1|z - -2]ll2
Eki Ensecho eltut7s-11e (2)
(5)
-E' Emnzee -llue, -Mglla Eieco ex ( ers ))
lluee
(66
where / = [1.... T.] denotes the I'th mrkd-tree level, ky is the index representing the cluster id for the different tree levels and μıs, the corresponding centroid. We also consider a Scalable Hierarchical- Latent Distance Model (SH-LDM) without the random effects setting % 0.5-7. For multi- furcating tree splitting in C clusters and having N/log(N) terminal nodes (clusters) the number of internal nodes are (N/((C log N)) and each node needs to evaluate O (C2)) pairs providing over- all complexity of ONC/ log N). thus C' < log 2 to achieve O(N log N) scaling (Epp) 2010).
2.1.2 DIVISIVE PARTITIONING USING K- M-MANSS WITH EUCLIDEAN DISTANCE METRIC
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/ log N).
4

---

1979) where T is the number of Under review as a conference paper at ICLR 2022
To reduce this scaling we use more efficient divisive partitioning procedure. For efficiency instead of considering minimizing the full expression in equation we consider minimizing the Euclidean norm || Mzll2. The divisive clustering procedure thus relies the following Euclidean norm objective
N K
Jr, 11) = -E>
Tae - 14
(7)
where & denotes the cluster id, 2, is the i'th data observation, Vik the cluster responsibil- ity/assignment, and μt 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 Ts & Morikawa (2012) developed in the context of compressed sensing. We define an auxiliary function for Eq. equation as:
J (6.
Σ
K
Tike
12:
1 + 2 0ikk
(8)
201
where Φ are the auxiliary variables. Thereby, minimizing Eq. equation X with respect to Φnk yields
6i ||z Hell2 and by plugging & back to Eq. equation 7 we obtain ( .I, [r. μ)
verifying that Eq. equation is indeed a valid auxiliary function for Eq. equation 7 The algorithm
proceeds by optimizing cluster centroids as pak
EiER
XL Pua
/ _1) and assigning points to dic
centroids as arg ming Ek=n Ezec,
11=-4-11 +/00 upon which Φb. is updated. The overall 20v
complexity of this procedure is O(TKND) (Hartigan & Wong
iterations required to converge.
A simple approach to construct the structure would be the above Euclidean k-means pro- cedure to split the nodes into K = N/ log( clusters and construct the tree according to agglomer- ation as hierarchical clustering. Unfortunately, such strategy is prohibitive for K = N/ log N, and maximally K log N clusters can be obtained for scaling of O log N). It would be tempting to continue splitting into log N clusters, however, for balanced multifurcating tree with N/ log N leaf clusters this will result in a height scaling Olog N/ log log N) and thus an overall com- plexity of (N log N²/ log log N) (Epp) 2010). Whereas using a balanced binary tree at all levels below the root results in height scaling as Ollog N) providing of O(DN log N) for the SH-LDM. Figure Ia illustrates the resulting tree for small problem of N 64 nodes in which first split into 4 (z log(64)) clusters and subsequently create binary splits until each cluster contains (zs log(64)) nodes.
overall complexity when includ-
ing the lincar scaling by dimensionality
2.2 RELATED WORK
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 al. 2014 Grover & Leskovec) 2016 Tang et al. 2015 Nguyen & Malliaros 2018), which generate leneh-length node sequences by following& 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-basel algo- rithms (Cao al. 2015; Ou et al.) 2016; Zhang et al. (0200). They extract the embedding vectors by decomposing a designed feature matrix. The neural networks are undoubtedly one of the most out- standing models, and many models (Hamilton al.
2017b; Waag 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 computa- tional challenges emerging for large networks by either incorporating fast approximation techniques with the existing models QQu et al.) 2019) or developing novel approaches relying fast hashing schemes Yang et al. | Zhang et al.; 2018). Our approach is related to current efforts in scaling graph embedding approaches for the analysis of very large networks.
5

---

Under review as a conference paper at ICLR 2022
Table 1: Statistics of networks. N: number of nodes, M: number of edges.
Cora
Dblp
AstroPh
GrQe
Facebook
HepTTh
Amazon
YouTube
Flickr
Plixster
N
2,708
27.199
17,903
5.242
4,039
8,638
334,868
1.138,499 2,990,443
1,715,255 15,555,042
2,523.386
M
5,278
66,832
197,031
14,496
88,234
24,827
925,876
7,918,801
Table Area Under Curve scores for representation sizes of 2 and over moderate-sizee networks.
AstroPh
GrQe
Facebook
HepTh
Cora
DBLP
Dimension (D)
2
8
2
8
DEEPWALK
.831
.945
845
.19
.958
.86
.773
.874
.684
.782
.803
.939
VEC
.825
.950
.809
.884
.914
.988
.780
.881
.640
.776
.803
.945
LINE
.632
.910
.688
.920
.751
.800
.659
.874
.634
.521
.625
.503
N
800
.814
.800
860
.872
.955
.757
.792
.629
.739
.838
.858
NETSMF
.288
.891
.756
.805
.907
.976
.705
.810
.605
.737
.766
.857
RANDNE
.524
.554
.534
.560
.614
.657
.519
.509
.508
.556
.508
.517
LOUVAINNE
.798
.813
.861
868
.957
.958
.774
.874
.767
.747
.900
.904
PRONE
.768
.907
.818
.883
.900
.971
.678
.823
.675
.764
.813
.924
SH-LDM
.17
.960
.898
.944
.980
.986
.847
.912
.786
.792
.919
.956
SH-LDM-RE
.931
.962
.910
.953
.986
.988
.869
.923
.759
.795
.930
.963
The most related scalable study to our method is the work for the LDM Raftery et al. (2012) where the ( complexity is lowered (cFF) with N via case-control approach motivated by epidemiology studies. While the overall complexity of the case-control model can scale the analysis of LDMs 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 scalable version of the case-control approach. as presently considered we exchanged the stratified sampling with uniform sampling procedure which as argued by the authors may not be the best estimator. We conclude that also the case- control approach does not yield a hicrarchical representation of network structure as the presently developed SH- LDM. However, the developed hierarchical clustering procedure can be used post-processing step to extract hierarchical representations from the learned embeddings.
order scale the case-control model to the order of millions of nodes
be used to successfully scale the LDMs. Notably, the casc-control approach
3 EXPERIMENTS
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 un- weighted for the consistency of the experiments, and the detailed statistics of the networks given in Table T We have conducted all the experiments regarding the SH-LDM and SH-LDM- on 32 GB Tesla V100 GPU machine. For the SH-LDM and SH--DDMREE models, we optimize the negative log-like ligllikeldoood via the Adam (Kingma & Ba 2017) optimizer while setting the learning rate to Ir 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 scalable spectral clustering initialization scheme for SH-LDM are provided supplementary ma- terials. 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 characteris- tic (AUC) whereas we defer the corresponding Precision- Reecallon-Recall AUC to the supplementary material. For the experimental setup, we follow the commonly applied strategy (Perozzi et al. 2014: Grover & Leskovee| 2016), and we remove half of the edges of given network by keeping the residual network connected. For the targe-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

---

Under review as a conference paper at ICLR 2022
Table 3: Area Under Curve scores for varying representation sizes over the large-scale networks. The symbol "-" indicates that the running time of the corresponding model takes more than 20 hours and "x" shows that the method is not able to run due to insufficient memory space.
Amazon
Tobeube
Flickr
Flixster
Dimension (D)
2
3
8
2
3
8
DEEPWALK
.839
.932
.922
.822
.891
.911
.889
.937
.972
.820
.866
.911
NODE2VEC
.813
.880
.968
LINE
.626
.501
.500
.660
.832
.878
.685
.889
.921
.523
.868
.936
NETMF
.829
.831
.858
NETSMF
.768
.786
.835
.939
.940
.949
.974
.977
.980
.987
.987
.987
RANDNE
.507
.511
.514
.672
.700
.762
.833
.869
.903
.700
.739
.835
LOUVAINNE
.955
.954
.954
.820
.819
.815
.898
.899
.909
.735
.718
.746
PRONE
847
.901
.944
.691
.761
.861
.623
.819
.908
.756
.803
.846
SH-LDM
974
.980
.988
.899
.920
.935
.972
.799
.986
.897
.916
.932
SH-LDM-RE
976
.981
.988
.940
.947
.957
.980
.985
.988
.962
,969
.971
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 Iearn the node embeddings and report the best performing binary operator (Grover & Leskovee 2016) used for logistic regression with La regularization (detailed list of the operators are given in the supplementary material). For SH-LDM and SH-LDM-R RE the predictions are made directly based on the learned Poisson rates of the test set pairs {ij), i.e. Xij exp (1/ + || 2/ (l2)). Error bars for the following AUC scores were found to be in the scale of 10 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-RA RE perform significantly better or on par with the performance of the considered baseline approaches. In particular, the SH-LDM and SHI-LDM-RE perform better than all base- lines 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-RR consistently outperforms the SH-LDM. In Figure i in the first and second panel we provide the underlying hierarchical structure, as well as an analysis of the accuracy of the SH- LDM 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 system- atically slightly lower likelihood estimates which we attribute to the SH-LDM inference minimizing the hierarchical approximation. In Figure third panel we observe the predictive performance function of latent dimension D and here in general observe that modest improvements in the pre- dictive 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 SH- LDM and SH-I-DM-RF utilize very low-dimensional representations. Results for the large-scale networks are given in Table 3. Again we observe that SH-LDMM -FE outperforms the baselines only being surpassed performance by NETSMF for the Flixster dataset. Notably, we again observe very good performance for the SH--LDMREE, but also NETSMF when utilizing the very low em- bedding dimension of D 2. In Figure 2 the fourth panel investigate the convergence of the best performing SH-LDM-RE for the large networks and here observe that the model rapidly con- verges such that we already after 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-lahel/mmulti-allee classification task and provide the Micro-F, scores (Macro-F, scores are reported in the supple- mentary). For the experimental setup, we randomly pick 50% of nodes as the training set and use the rest the testing set. For an accurate comparison across different methods we used two sim- ple 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 = 10 (similar results were obtained with higher choices for k well). Lastly, report the average Micro-F, scores across 10 repeated trials. Results
7

---

Under review as a conference paper at ICLR 2022
3.6
Nogatee Log Medhoed
EDM
S11-D00
0.030
ADC BOC
38-
YorTube
0,025
0.015
Hiek
20x 10
25.x0 10
Flocker
66-
Amazo
6 13P
20 UP
35
64
2x107
10c07
(0)
iiii)
(iv)
Figure 2: (i) Facebook ordered adjacency matrix for the learned D embeddings of SH-LDM- RE for a hierarchical structure of L 3. (ii) NLL comparison between SH-LDM and LDM for various networks for varying embedding sizes. (iv) AUC scores SH-I.DM-RE in terms of iterations for large-scale networks.
Facebook with D 2. (iii) AUC performance
Table 4: Micro-F, scores varying embedding dimensions for two moderate and large-scale networks.
Cora
DBLP
Amazon
YouTube
Dimension (D)
2
3
128
2
3
128
2
3
8
2
3
8
DEEPWALK
.502
.712
.838
.599
.605
.822
.231
.596
.929
.293
.351
.413
NODE2VEC
.419
.658
.835
.448
.540
.815
.096
.305
.895
LINE
.197
.191
.794
.328
.994
.771
.005
.003
.003
.185
.134
.177
NETMF
.389
.653
.835
.654
.707
.742
X
X
X
X
NETSMF
.554
.705
.842
.622
.732
.829
.387
.649
.845
.317
.361
.397
RANDNE
.271
.337
.731
.406
.473
.718
.223
.411
.787
.211
.226
.277
LOUVAINNE
.804
.811
.801
.780
.812
.825
.970
.971
.974
.362
.360
.359
PRONE
.450
.611
.830
.574
.634
.825
.420
.750
.933
.218
.274
.379
SH-LDM
.789
.807
.816
.812
.814
.772
.970
.971
.931
.320
.366
.414
SH-LDM-RE
.805
.809
.818
.805
.822
.808
.956
.955
.931
.326
.367
.414
for the uni-labeled Cora and DBLP networks reported in the two leftmost columns of Table We observe that SH-LDM-RE and SH-LDM significantly outperform the baselines for the regimes of D 2.3 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 transi- tivity can express accurately the underlying node class structure.
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 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 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-F, scores. Our proposed SH--DMM and Sn1- LDM-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-I.DM 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 + This is not the case for NODE2 and LOUVAINNE as their Micro-F, scores dramatically drop. For most methods NMI benefits when transitioning to t-SNES with SH-LDM giving par performance for Cora while SH-LDM-R RE has the highest overall NMI for DBLP (D=128+t-SNE). We attribute the increase in clustering performance while using high- high-dimensions and t-SNE (especially for DBLP) 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 the
Network visualization:
and D = 128
8

---

Under review as a conference paper at ICLR 2022
silver lining between consistent performance across all GRL downstream tasks well network visualizations. All baseline results are available in the supplementary.
Cora
DBLP
((TES)
(t-SNES)
128 (-SNES)
(TES)
(t-NNS)
(tSNES)
NODE2VEC
6.175,.415 .419,.863))
(.147, 22.2226,,880 .841).
(3378, 204,
(0022, 1072,.448,.8 .900)
(.004, .36,, 820)
(.117, 298, 974)
NETSME
(.268,.538 .5544.4466000 .860) (,265, 560, .873)
(,397, 836, 970)
(113, 622, .40)
(,03, 624, .511)
(,114,882) 9755)
LOUVAINNE
(,253,.800 .804, .44)
2217,2266,00
(.268, .212,941)
(.012, 780, .90))
(.005, 295, 944)
(.008, 290, .951)
SHLLDM
(,212,789,, 789,,999995 1975)
(,235, 770, .67))
(3883, .97,
(047,-793) 985)
(.028, 796, .953)
(.076, .955
SEL LDMBRE
(.283, .805, .75)
791,,999) (.367, .824, .966)
(.036, .985
(027,880,, .988 (.118, .824, .975)
Figure 3: The first two columns for each dataset represent the node embeddings learned in two- dimensional space and 1-SNE algorithm applied for the second and the third columns reduce the dimension size for the visualization task and to demonstrate the influence of t-SNE algorithm on the embeddings. For each network, NMI (node clustering), Micro-F, (node classification) and AUC scores (network reconstruction) are reported, respectively.
CONCLUSION AND LIMITATIONS
We proposed the Scalable Hierarchical Latent Distance Model (SII-LDM), a scalable approach em- bedding networks using the latent distance model (LDM) enabling characterization of structure multiple scales. Notably, the approximation provides high accuracy where the likelihood approxi- mation is most important while scaling complexity by O(DN N). 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 very low embedding dimension of D = 2 providing favorable network visualizations and characterization of structure at multiple scales. The SII-DDM is based on the latent distance model (LDM) and thus good at characterizing transitivity and ho- mophily 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 equiv- alence (Hoff 2007). Future work should thus investigate how the proposed hierarchical embedding structure be imposed on more flexible embedding procedures such as the eigenmodel.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yong-Year Yeol Ahn, James Bagrow, and Sune Lehmann. Link communities reveal multiscale com- plexity in networks. nature, 466(7300):761-766) 2010.
Lars Backstrom and Jure Leskovec. Supervised random walks: Predicting and recommending links in social networks. In Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, WSDM 11, pp. 635-644, New York, NY, USA, 2011. Association for Com- puting Machinery.
Albert-László Barabási and Márton Pósfai. Network science. Cambridge University Press, 2016.
Ayan Kumar Bhowmick. Koushik Meneni, Maximilien Danisch, Jean-Loup Guillaume, and Bivas Mitra. LouvainNE: Hierarchical louvain method for high quality and scalable network embed- ding. In WSDM, pp. 43-51, 2020.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10):P00008, 2008.
Charles Blundell, Yee Whye Teh, and Katherine Heller. Bayesian rose trees. arXiv preprint arXiv:1203.3468, 2012.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. GraRep: Learning graph representations with global structural information. In CIKM, pp. 891-900, 2015.
Shaosheng Cao. Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In AAAI, 2016.
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. HARP: hierarchical representation learning for networks. AAAL, pp- 2127-2134, 2018.
Aaron Clauset, Cristopher Moore, and Mark EJ Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98-101, 2008.
Susanna S. Epp. Discrete Mathematics with Applications. Brooks/Cole Publishing Co., USA, 4th edition, 2010. ISBN 0495391328.
Santo Fortunato. Community detection in graphs. Physics Reports, 486(3):75-174,2)
Lise Getoor and Ben Taskar. Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning). The MIT Press, 2007. ISBN 0262072882.
Aditya Grover and Jure Leskovec. Node2Vec: Scalable feature learning for networks. In KDD, pp- 855-864, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. NIPS, 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017b.
Mark Handcock, Adrian Raftery, and Jeremy Tantrum. Model-based clustering for social networks. Journal of the Royal Statistical Society: Seriey A (Statistics Society), 170:301 354, 03 2007. doi: 10.111111 200666988022077.... .00070000.1.....
A. Hartigan and M. A. Wong. Algorithm AS 136: A K-Means clustering algorithm. Applied Statistics, 28(1): 100-188 1979. ISSN 00359254.
Tue Herlau, Morten Mørup, Mikkel N Schmidt, and Lars Kai Hansen. Detecting hierarchical struc- ture networks. In 2012 3rd International Workshop on Cognitive Information Processing (CIP), pp. 1-6. IEEE, 2012.
Tue Herlau, Morten Mørup, and Mikkel Schmidt. Modeling temporal evolution and multiscale structure in networks. In International Conference on Machine Learning, pp. 960-968. PMLR, 2013.
10

---

Under review as a conference paper at ICLR 2022
Tue Herlau, Mikkel N Schmidt, and Morten Mørup. Infinitedegree--orreee stochastic block
model. Physical review E, 903)):33819, 2014.
Peter D Hoff. Bilinear mixed-effects models for dyadic data. Journal of the American Statistical Association, 100(469):286-255, 2005.
Peter D. Hoff. Modeling homophily and stochastic equivalence in symmetric relational data, 2007.
Peter D Hoff, Adrian Raftery, and Mark S Handcock. Latent space approaches social network analysis. Journal of the American Statistical Association, 979460): 2002. doi: 10.
1198001621502238611 8906.
Paul Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 1983.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107,20) 2011.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Pavel N. Krivitsky, Mark S. Handcock, Adrian E. Raftery, and Peter D. Hoff. Representing degree distributions, clustering, and homophily in social networks with latent cluster random effects models. Social Networks, 31(3):204 213, 2009.
Tianxi Li, Lihua Lei, Sharmodeep Bhattacharyya, Koen Van den Berge, Purnamrita Sarkar, Peter Bickel, and Elizaveta Levina. Hierarchical community detection by recursive partitioning. Jour- nal of the American Statistical Association, pp. 1-18, 2020.
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. CIKM, pp. 556-559, 2003.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representa- tions of words and phrases and their compositionality. In NIPS, pp. 3111-3119, 2013.
Andrew W. Moore. Very fast em-based mixture model clustering using multiresolution kd-trees. In Proceedings of the 1998 Conference on Advances in Neural Information Processing Systems II, pp. 543-549, Cambridge, MA, USA, 1999. MIT Press. ISBN 02621 12450.
M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167-256, 2003.
Duong Nguyen and Fragkiskos D. Malliaros. WalsedWalk: Biased sampling for representation learn- ing graphs. In Big Data, pp. 4045-4053, 2018.
Krzysztof Nowicki and Tom A. B Snijders. Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96(455): 2001.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In KDD, pp. 1105-1114, 2016.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. DeepWalk: Online learning of social representa- tions. CoRR, abs//403. http//10366666 (6000,666622220 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Chi Wang, Kuansan Wang, and Jie Tang. NetSMF: Large-scale network embedding as sparse matrix factorization. In wWW, pp. 1509-1520, 2019.
Adrian F. Raftery, Xiaoyue Niu, Peter D. Hoff, and Ka Yee Yeung. Fast inference for the latent space network model using case-control approximate likelihood. Journal of Computational and Graphical Statistics, 21(4):901-919, 2012.
Erzsébet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks. Phys. Rev. E, 67:026112, 2003.
11

---

Under review as a conference paper at ICLR 2022
Daniel M Roy, Charles Kemp, Vikash Mansinghka, and Joshua Tenenbaum. Learning annotated hierarchies from relational data. In B. Schölkopf. Platt, and T. Hoffman (eds.), Advances in Neural Information Processing Systems, volume 19. MIT Press, 2007.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: Large-scale information network embedding. In WWW, pp. 1067-1077, 2015.
Hiroshi Tsutsu and Y. Morikawa. An lp norm minimization using auxiliary function for compressed sensing. In Proceedings of The International MultiConference of Engineers and Computer Sci- enlists, 2012.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(86))2579-2605 2008.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoencoders: Learning useful representations in a deep network with local denoising criterion. J. Mach. Learn. Res., 11:3371-3408, 2010.
Daixin Wang, Peng Cui, and Wenwu Zhu, Structural deep network embedding. In KDD, pp. 1225- 1234, 2016.
Harrison White, Scott A Boorman, and Ronald Breiger. Social structure from multiple networks. i. blockmodels of roles and positions. American journal of sociology. 81(4):33--780 1976.
David Kofoed Wind and Morten Mørup. Link prediction in weighted networks, In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pp. 1-6, 2012. doi: 10. 1109MMLSSP22122.34477455
Dingqi Yang, Paolo Rosso, Bin Li, and Philippe Cudre-Mauroux. Nodesketch: Highly-efficient graph embeddings via recursive sketching. In KDD, pp. 1162-1172, 2019.
D. Zhang, J. Yin, X. Zhu, and C. Zhang. Network representation learning: A survey. IEEE Trans- actions on Big Data, 6(1):3-28, 2020.
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding, Prone: Fast and scalable network representation learning. IJCAI-19, pp.
7 2019.
Zhang, Cui, H. Li, X. Wang, and W. Zhu. Billion-scale network embedding with iterative random projection. In ICDM, pp. 787-796, 2018.
12


Reviews:
[{"review_id": "lvCBcWaBzQ7", "reviewer": "Reviewer_BVVN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main strength of the paper is that it is faster/more scalable than the traditional LSM and that the method appears to perform quite well in experiment. \n\nMy main concerns regarding this paper is: \n\n1. The authors introduced several heuristics to approximate things/speed things up: a) approximating the non-link term using blocks b) using a multiresolution KD tree c) minimizing with a Euclidean norm instead of the exact expression, which they propose an auxiliary function optimization procedure for. The main motivation for these heuristics is to reduce run time so that the procedure is scalable. But what the authors did not sufficiently address/rigorously justify is a) how accurate are these approximations? are there any bounds on the approximation error? b) how does the resulting model after applying these changes relate to the original model? are desirable properties that make the LDM useful in the first place retained? Without addressing the above questions, it is very unclear what exactly this new model is capturing and whether it is still an LDM model. \n\nAnother way to phrase the above is that the authors proposed modifications to the LDM that are *sufficient* to make it scalable. What the authors did not address is 1) what are the quantifiable tradeoffs that come with this scalability? 2) are these changes to the LDM *necessary* and *unique*? For example, why the multiresolution KD tree? That seemed to have come out of nowhere. Does there exist some other data structure or algorithm that can achieve similar results? If there are alternatives, then the authors should state the alternatives and give reasons for why the choice that they made is the most appropriate given all the alternatives. \n\nA lot of the decisions/choices made in this paper are not sufficiently motivated/justified. Without further justification (especially addressing the uniqueness point above), I find a lot of the decisions (e.g. Using the Euclidean norm as a replacement for the exact expression, and then developing some auxilary function optimization procedure) arbitrary and overengineered. \n\n2. I find it weird that in the experimental section the authors did not compare the SH-LDM with the full LDM. If the SH-LDM is doing so much better than the other competitors, then perhaps the full LDM would be even better, computational costs aside? But I don't recall seeing such results in the literature. If that is the case, then where is the gain of SH-LDM coming from? Is it from the approximations? In any case, I think it is very important for the authors to provide a comparison between their new method and the original method that they modified, even if this means they need to compare them on smaller networks/datasets. ", "summary_of_the_paper": "The authors propose Scalable Hierarchical Latent Distance Model which scales at O(NlogN) rather than O(N^2).", "summary_of_the_review": "Interesting paper, but lots of decisions/choices that appear arbitrary, insufficiently motivated/justified, and over-engineered. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jo71WiAFWZk", "reviewer": "Reviewer_ApfC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. It is novel to use LDM for hierarchical node structure representation.\n2. Using blocks to approximate O(N^2) and reduce the complexity is reasonable and works well.\n3. The proposed method performs well with low embedding dimensions on different datasets.\n\nWeaknesses: \n1. It is hard to understand why an auxiliary function is needed for Eq.7 and how it is designed. Motivations and intuitions should be provided.\n2. Why the proposed method does not perform well with higher dimensions (e.g., 128D on Cora and DBLP)? More analysis/discussions are expected.\n3. Any theory that can explain why SH-LDM performs better with random effects?\n4. How does the height L of the hierarchical structure influence the performance of the proposed method?\n5. Some important hierarchical embedding approaches are missing as baseline models in the experiments (e.g., HARP and MILE).\n\nSome presentation issues:\n1. There is no a, b, c label in Fig. 1.\n2. Delete equation label (5). \n", "summary_of_the_paper": "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.", "summary_of_the_review": "Although the proposed method performs well in experiments under the low embedding dimension setting, more explorations on different settings are expected to understand this model comprehensively. Other concerns are listed above in weaknesses.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HW6NSmLYxcP", "reviewer": "Reviewer_2m7B", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, it seems that the contribution of this paper does not necessarily warrant its publication at CVPR.\n\nPros:\n- The authors develop an unsupervised embedding technique that is scalable.\n- Interesting trick: in their model, the probability of the network decomposes over the product of the probability of the individual edges. The main take-away here is that they use a Poisson regression model rather than logistic regression framework. Not sure how this could be applicable to \"weighted\" graphs, as the authors imply however, but it would have been interesting to delve deeper into the properties of the model as a result of this choice --- it is an interesting choice, that was not sufficiently well motivated.\n\n\nCons:\n- This is more of a new pipeline rather than a new method --- the authors stitch together existing methods, and while the scalability issue in node embeddings is an interesting aspect, the body of work here is not really novel.\n- The method is perhaps not appropriately described --- it should be emphasized that the method for learning structure here is unsupervised (they do not use class labels), which is a big difference with GNNs. Somehow, I thought that the scalability argument was emphasized everywhere, but perhaps not convincing to explain why the method should not be compared with GNNs.\n- The main concern with this submission is the method of evaluation:\n   1.  The comparison table should list running times and complexities for all of the algorithms, instead of simply the performance.  Currently, we fail to see how \"scalable\" these truly are, and the performance is only midly impressive.\n   2.  The t-sne  evaluation method was not convincing at all, in my opinion. This is (a) a stochastic method, and unless the PCA initialization is used, the results typically vastly vary, and its output is sometimes unpredictable and often sensitive to the choice of perplexity parameter --- I am therefore not quite sure what value to put on the micro-F1 scores, NMI etc.  As a reminder, t-SNE is a visualization method at best, but not a way to do quantitative work. t-SNE is indeed unable to correctly represent local differences in\ndata density or variance, and cluster sizes and large-scale distances\nare not interpretable in t-SNE output embeddings ---- so again, using tsne based distances to assess quality seem inadequate. See [1] and[2] for references on the topic. Instead, statisticians usually prefer using techniques such UMAP rather than t-SNE.\n\n\n[1] Martin Wattenberg, Fernanda Viégas, and Ian Johnson. How to use t-sne effectively. Distill, 2016.\n[2] Nguyen, Lan Huong, and Susan Holmes. \"Diffusion t-SNE for multiscale data visualization\"\n", "summary_of_the_paper": "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:\n-\t__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}$:\n$$ \\lambda_{ij} = \\gamma_i + \\gamma_j - || z_i -z_j||_2 $$\nFinding a solution in terms of $z_i$ s of this model --- which is not new --- is the object of this paper.\n\n- __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$.\n\n- __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\nfor k-means clustering with Euclidean norm utilizing the auxiliary function framework of Tsutsu & Morikawa to perform optimization scalably.\nThis allows the partition of the data into $K = \\log(N)$ clusters.\n\nThis results in a reduction of  the total time and space complexity of the LDM to O(N logN)).\nThe authors then proceed to validate their method using a set of experiments:\n\n 1. node classification\n\n 2. edge prediction\n\n 3. clustering and hierarchical structure recovered in the latent space.\n\nwith reasonable performance on a subset of the dataset.\n", "summary_of_the_review": "Overall, this paper seems unfit for publication. The novelty is limited, and the methods of validation/ experiments do not make a strong case for the usefulness of such a data processing piepline.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ELtLZYZT8jL", "reviewer": "Reviewer_MkFe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The LDM approach is a relatively old approach to learning latent representations for networks. The innovation of this paper is instead of evaluating the exact likelihood function that involves computing pairwise distances among nodes to resort into a clustering technique: Group nodes based on their respective embeddings and only compute the pairwise distances between the centroids of each cluster. This allows for the term that contributes to O(N^2) in the evaluation to reduce to O(K^2).\nIn the rather rough analysis of the runtime the authors make the following assumptions:\ni) The network is sparse -- this is a valid assumption however it should be made clear that the claimed running time of O(nlong) is made based on this assumption\nii) The embedding dimensions is a constant -- which  follows clearly by setting it to a really small value, like 2.\niii) The cluster sizes are equal.\nI have a two-fold objection with the last assumption:\n1. If we think of networks as collections of clusters, then it is usually the case that these are highly imbalanced. E.g., in several empirical studies as in [1], we see that usually there is a collection of small large clusters and an abundance of smaller clusters (called whiskers) that are connected through the core clusters. I am surprised therefore that this approach can lead to good performance.\n2. Another objection is that the authors do not make clear how they get this clustering. Initially, the use of a multiresolutional KD-tree is proposed. However, if we stop splitting nodes, when we reach K nodes in the tree, then there is no guarantee that the resulting clusters will be of equal size. The splitting criterion can be arbitrary (is not defined here), while a good empirical practice is to split along the dimension of higher variance -- a balanced partitioning is guaranteed only for the first split, then it depends. As this approach also fails in terms of reducing the computational burden, the authors try to propose other approaches, like a modified k-means or a balanced binary. The latter of course could work, but there is no information at all on how this is created: How de we choose which points (nodes) to fall under the  left or right child of a split. The paragraph above 2.2 that tries to describe this procedure is rather confusing with limited information. As a reference, a method that tries to achieve balanced partitioning of nodes is described in [2].\n\nAlso, while the evaluation of the  likelihood function is discussed in detail, the same is not true for the convergence of the model. How many iterations do we need and how much time does it take to train the model? \n\nIn other minor remarks:\n1. Defining in the abstract that N is the number of nodes could help exposition for those not familiar with network terminology.\n2. In page 3, $\\theta$ is not defined.\n3. As part of the LL function is evaluated between cluster centroids, is the model having some relationship with the SBM models?\n4. Figure 1 does not have indexing.\n5. The same Eq. is labeled as (5) & (6).\n[1] Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009). Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1), 29-123.\n\n[2] Karypis, G., & Kumar, V. (1997). METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices.", "summary_of_the_paper": "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.\nTo 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.", "summary_of_the_review": "The paper proposes a centroid-based approximation to evaluating the likelihood function of latent models -- a rather incremental approach. The main problem is that the final choice of the clustering procedure -- which is the crux of this paper -- is not clearly described. The authors describe more in detail other appoaches -- like KD-trees -- that fail, whereas for the actual choice -- balanced binary tree?-- we know little to nothing. Moreover, the clustering approach itself, and the need for the clusters to be balanced, is one that I have objections based on reasons described before. Under the assumptions that we use O(long) balanced clusters, then (n/logn) nodes will fall under the same cluster. Hence, almost all nodes! Maybe then the relevant term that gives this O(N^2) burden is not relevant to optimize? For these reasons, and despite the claimed superior performance in downstream tasks, I am not in favor of recommending this paper for acceptance in its current form.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes SH-LDM, which approximates the LDM model with a hierarchy of clusters. The authors should discuss the details about clustering and how this algorithm can benefit from sparsity in a more rigorous language.  

The authors should review the rich literature on scaling up distance-based methods such as kNN and kernel methods, which this paper belongs to. The title is also misleading; the paper mainly discusses scalable link prediction rather than learning new embeddings.

The reviewers have raised several questions about the experiments. For example, the main results should be a table for comparing the speed rather than the accuracy of the algorithms. Also, the original LDM should be included in the accuracy tables. The settings in the experiments, such as embedding dimensions, are not appropriate for large graphs.
Decision: Reject