Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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.
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).
In the rather rough analysis of the runtime the authors make the following assumptions:
i) 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
ii) The embedding dimensions is a constant -- which  follows clearly by setting it to a really small value, like 2.
iii) The cluster sizes are equal.
I have a two-fold objection with the last assumption:
1. 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.
2. 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].

Also, 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? 

In other minor remarks:
1. Defining in the abstract that N is the number of nodes could help exposition for those not familiar with network terminology.
2. In page 3, $\theta$ is not defined.
3. As part of the LL function is evaluated between cluster centroids, is the model having some relationship with the SBM models?
4. Figure 1 does not have indexing.
5. The same Eq. is labeled as (5) & (6).
[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.

[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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose Scalable Hierarchical Latent Distance Model which scales at O(NlogN) rather than O(N^2).
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. 

My main concerns regarding this paper is: 

1. 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. 

Another 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. 

A 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. 

2. 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_review: Interesting paper, but lots of decisions/choices that appear arbitrary, insufficiently motivated/justified, and over-engineered.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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:
-	__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.

main_review: Overall, it seems that the contribution of this paper does not necessarily warrant its publication at CVPR.

Pros:
- The authors develop an unsupervised embedding technique that is scalable.
- 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.


Cons:
- 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.
- 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.
- The main concern with this submission is the method of evaluation:
   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.
   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
data density or variance, and cluster sizes and large-scale distances
are 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.


[1] Martin Wattenberg, Fernanda Viégas, and Ian Johnson. How to use t-sne effectively. Distill, 2016.
[2] Nguyen, Lan Huong, and Susan Holmes. "Diffusion t-SNE for multiscale data visualization"

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strengths:
1. It is novel to use LDM for hierarchical node structure representation.
2. Using blocks to approximate O(N^2) and reduce the complexity is reasonable and works well.
3. The proposed method performs well with low embedding dimensions on different datasets.

Weaknesses: 
1. 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.
2. Why the proposed method does not perform well with higher dimensions (e.g., 128D on Cora and DBLP)? More analysis/discussions are expected.
3. Any theory that can explain why SH-LDM performs better with random effects?
4. How does the height L of the hierarchical structure influence the performance of the proposed method?
5. Some important hierarchical embedding approaches are missing as baseline models in the experiments (e.g., HARP and MILE).

Some presentation issues:
1. There is no a, b, c label in Fig. 1.
2. Delete equation label (5). 

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.
review_title: null

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