Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: (Summary)

Unsupervised learning of vector representations for a graph is an important problem for various downstream applications. The authors propose an InstantEmbedding approach that learns d-dimensional embedding for each node in sublinear time. As the paper claims that this approach is a local embedding but globally consistent, users can quickly learn vector representations of nodes based on the local structure, being free from possibly growing the rest of the graph.

Two properties are first defined as qualifications to be a useful local embedding. Locality requires learning algorithms to use only local information. If an approach requires an access to the embeddings of every node in local neighbors or to the entire adjacency matrix, locality is not qualified. Global consistency means that the locally-computed embeddings remain identical even if we compute the embeddings of the entire nodes simultaneously.



(Originality and Contributions)

The proposed algorithm: InstantEmbedding is simple. Once we compute Personalized PageRank (PPR), the algorithm tries to decompose the dense similarity matrix log(PPR) + log(# of nodes) efficiently via two hash functions. The algorithm is designed in a way that global learning is equivalent to local update, automatically satisfying the global consistency. Thus most of the theoretical contributions are based on the idea of implicit factorization by Tsitsulin et al (2020) (which is essentially similar to Levy et al (2014)), the idea of hashing by Weinberger et al (2009), and the sparse computation of PPR by Andersen et al (2007). Instead, this paper conducts extensive study of empirical performance with increasing the error parameter $\epsilon$. The experimental results demonstrate that InstantEmbedding produces competitive embeddings with other methods with a few thousand times better in time and space complexity.



(Questions, Concerns, and Suggestions)

1) Global consistency was expected to be a theoretical property, as given in Section 2.3, such as distance/geodesic preservation between the graph space and the vector space. However, it ended up being chosen more as an algorithmic property, which the proposed algorithm is uniquely achievable by the design. Have you actually measured distortion in various datasets, being able to claim low-distortion?


2) As studied in GEMSEC by Rozemberczki et al (2018), quality embeddings should promote clustering of the nodes (i.e., underlying community structures) as well as preserving the proximities. Considering that one can easily acquire local clusters based only on the local structures of the graph, it will be useful for readers to know whether or not InstantEmbedding can also encode local community structures. And, that could be a significant part of the Locality.


3) Note that Graph Convolutional Convolutional networks can also be trained as an unsupervised fashion and sometimes achieve great generalization without node features. See how synthetic graph is generated featurelessly in GAP by Nazi et al (2019). More importantly, the message passing scheme in GCN is scalable to multi-graph or even hyper-graph, which is not readily clear in the proposed method. Learning hierarchical representation is also questionable.


4) Can you report the degree of scale-free and small-world for each of the graph in experiment? It is an important summary information for distinguishing individual graphs. Hope various graphs used in the experiment have explored a wide range of scale-free and small-world structures.


5) If we carefully read Andersen et al (2007), they did not adopt standard transition matrix given in the proposed model. Asymptotically it would not cause much difference, but it is less clear what’s the impact on the F1-performance given $\epsilon$ tolerance. Note again that InstantEmbedding becomes useful only if the tolerance parameter reaches at a certain level.


review_title: Review for InstantEmbedding

final_score: rating: 4: Ok but not good enough - rejection
review_content: ###### Summary ######

The paper proposes a node representation learning method for undirected networks based on the Personalized PageRank algorithm. The embedding vector for a node is obtained by applying a hashing algorithm on the approximated PageRank vector computed by using only the local region of the interested node. That way, the paper proposes a scalable algorithm that does not require the whole network while computing the embedding of a particular node. The performance of the algorithm is evaluated on the multi-label node classification and link prediction tasks.

###### Reasons for score ######

I vote for rejection. The structure and the main idea of the paper are good, but the experimental evaluation of the method is not sufficient and it should be enhanced. Although there are many recent scalable algorithms (as described below), the paper considers only FastRP and the classical models as baseline methods. 

###### Strengths ######

--- The algorithm computes the embedding vector of a particular node by using only the local subregion of the network, without requiring the embedding vectors of the remaining nodes.

--- The algorithm outperforms classical baseline methods on small training ratios in the classification task. 

###### Weaknesses ######

--- The experimental evaluation is weak and does not allow us to draw meaningful conclusions about the proposed algorithm. The paper does not use most of the recent scalable algorithms, except one, in the empirical analysis. 

--- The proposed algorithm does not show significant performance improvement on the link prediction task.

###### Detailed Comments ######

Overall, the paper is well-written and has a well-organized structure. The proposed methodology is interesting, but I have concerns related to various parts of the paper. 

In Section 3, the paper starts describing the methodology by firstly introducing the objective function of VERSE and then indicating that it implicitly performs a matrix factorization of the matrix M defined as “log(PPR) + log(n) + log(b)”. In Section 3.1.1, the paper describes the proposed approach as an efficient alternative to factorizing matrix M, preserving the similarities of PPR. Nevertheless, the hashing algorithm is applied to the rows of matrix M, so the approach mainly targets to preserve the similarities in MM^T instead of M as stated in Lemma 3.2. That’s why it seems that Lemma 3.1 does not contribute much to the presentation of the method. The paper also provides the proof of Lemma 3.1 in the Appendix, although this is somehow not relevant to the scope of the paper. 

# Theoretical background

--- Lemma 3.2 is very similar to the first part of Lemma 2 in [Weinberger et al., 2009] and Lemma 3.3 relies highly on Theorem 3.2 of the paper [Andersen et al. (2007)]. Thus, it is preferable to provide references for these papers while presenting the lemmas. Similarly, for the proof of Theorem A.5 (ref Theorem 3.4) in the Appendix, the paper should give reference to Theorem 3.2 of Andersen et al. (2007).

--- In the proof of Lemma A.4 (ref Lemma 3.3), I think the expression “... and only if a neighbor of w has positive score” should be replaced with “... and only if there is a node w in the graph such that r[w] greater than \epsilon \times deg(w).” In the proof, the “push” operation is also not defined.

--- In the proof of Theorem 3.5, the symbol \epsilon is used for the InstantEmbedding algorithm corresponding to the term defined for \epsilon-approximate Pagerank vector. However, the \epsilon used for GraphEmbedding indicates the desired precision of the approximation. I think it is not clear that the resulting vectors obtained by these two algorithms with the same epsilon value produce the same vectors. The authors should elaborate more on it in the proof of the theorem. For instance, [Andersen et al. (2007)] demonstrates that the total difference between the PageRank vector and the \epsilon-approximate PageRank vector can be bounded in terms of \epsilon and vol(S) for a given set S.

--- Although the paper mentions that it applies the classic random walk settings in the paper, it actually uses the same updated rules (Algorithm 3 in Appendix) as in Andersen et al. (2007). Thus, the paper works on the PageRank vectors corresponding to the alpha values in the lazy random walk strategy. As the paper states in Section A.7, the alpha for the formulation given in Eq. 1 is different for the same vectors, so Eq. 1 needs to be reformulated.

--- The authors remove the constant “b” but not “n” from the target objective matrix. Is there a particular reason for this choice? 

--- In Table 1, the complexity of the proposed approach is provided for learning the representation of a specific node, while the complexities of the baseline methods are given for the whole network structure. I believe that it might be better to introduce an additional parameter for the proposed approach to indicate the desired number of nodes to learn embeddings. For the complexities of the baseline methods, the paper should also provide references for them.


# Experiments

--- For the experiments shown in Figure 1, it seems that the scores for the baseline methods are given for the whole network, while for the proposed method they are stated for only one node. I think it might be better to follow the same strategy for the InstantEmbedding, in order to have a fair comparison -- since we need embeddings for the whole network structure, for instance, for the link prediction experiment in Table 4. The chosen \epsilon values are not also described in the experiments in Figure 1, although \epsilon has a significant influence on the running time.

--- For the link prediction experiment, the paper should use all networks listed in Table 2 in order to have a more complete view of the experimental evaluation of the method.

--- For the classification experiments, although the paper uses 1%, 5%, and 9% training ratios for all networks, it considers 10%, 50%, and 90% training ratios for the Blogcatalog dataset. Is there any particular reason for that? Besides, the VERSE algorithm mostly shows better performance for the link prediction task. How is this behavior explained? 

--- In Table 3, the performance of node2vec is better than InstantEmbedding on Blogcatalog network, so its score should be in bold. For the Flickr network, the score of Deepwalk should also be in bold.

--- Another very important aspect has to do with the baselines used in the paper. In the related literature, there are many recently proposed scalable representation learning models that are not used in the experimental evaluation.  Although the paper provides references for some recent scalable algorithms such as RandNE [Zhang et al., 2018] and FREDE [Tsitsulin et al. (2020)], it does not consider them as baseline methods in the experiments. The paper uses solely FastRP [Chen et al., 2019] and the classical node embedding methods to compare the performance of the method, while other recent models are known to perform better than FastRP.  Why recent scalable methods such as NodeSketch [1] and LouvainNE [2], are not considered in the experiments? Besides, why is FREDE (matrix factorization formulation of VERSE)  not used as a baseline?

[1] Dingqi Yang, Paolo Rosso, Bin Li and Philippe Cudre-Mauroux, NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching, KDD 2019
[2] Ayan Kumar Bhowmick, Koushik Meneni, Jean-Loup Guillaume, Maximilien Danisch, Bivas Mitra, LouvainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding WSDM 2020

# Typos
In Subsection 2.1, “v \in G” should be “v \in V”
In the second paragraph of Subsection B.4.1, “For each methods” should be “For each method”

review_title: Interesting scalable model for computing node embeddings. The experimental evaluation though should be enhanced.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

Contributions of this paper are twofold. First, it introduces the problem of Local Node Embedding, which means node embedding by using local information only while garanteeing global consistency. Second, it presents InstantEmbedding, an efficient implementation based on PPR and random projections. Extensive experiments on 10 datasets show that this new algorithm saves computer memory and is much faster than existing baselines.


##########################################################################

Reasons for score: 

I vote for accepting the paper for I think we need such efficient approaches that are able to deal with huge graph (for industrial applications), or juste help when one uses a simple computer with limited capacities. I don't give a higher grade for I think it's a rather incremental proposal that is build on a pipeline combining two previous papers.

 
##########################################################################

Pros: 
 
1. very well written paper
2. approach well grounded on two previous interesting works
3. new approach is proven to be more efficient, in term of runtime and memory usage

 
##########################################################################

Cons: 

1. quite incremental, seems more like an application of existing methods
2. way of comparing to previous work is not perfectly clear (see below)
3. no discussion on the better performances in node classification (see below)
 
##########################################################################

Questions during rebuttal period: 

- The way runtime is calculated in Section 4.2 is not perfectly clear. Is it calculated on the whole graph, and then divided by n (number of nodes), or is it directly at the node level? If this is the latter, how do you calculate the values for the competitors? For DeepWalk, in particular, complexity is proportional to the parameters defining the random walk, not n as shown in Table 1.

- Can you explain why DeepWalk cannot be described as a local method since it is based on truncated random walks?

- Do you have any explanation for the very good results in node classification? There is no clear reason why the proposed approach will be good for solving this task. The quick mention of regularization is not fully satisfying and further insight would be much welcome.

#########################################################################

Some typos: 

"for its adaption"
"should posses"
"can choose and universal"

review_title: Node embedding in sublinear time

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes an efficient algorithm to obtain a given node's embedding based on its local PageRank scores. The proposed approach uses a hashing technique to hold similarities between nodes effectively. Besides, it exploits a local partition approach to compute PageRank scores. This paper performs the experiments by using several real datasets to show the approach’s efficiency and effectiveness. 

In my opinion, the proposed approach lacks the originality; it is a combination of the existing hashing technique by Weinberger et al., and the PageRank computation approach by Andersen et al. Unlike the previous approaches such as DeepWalk, it exploits PageRank score to obtain similarities. However, this is the same idea proposed by Tsitsulin et al.

I doubt the paper performed a fair comparison to the existing approaches in terms of running time. As shown in Algorithm 2, the proposed approach computes an embedding of a single node. On the other hand, the existing embedding approaches compute embeddings of all the nodes. Therefore, the proposed approach should be evaluated in computing embeddings of all the nodes. I do not think it takes only 80ms to compute embeddings of all the nodes for Friendster dataset of 66M nodes. The downstream applications, such as visualization, need embeddings of all the nodes, not a single node. Could you tell me whether the proposed approach is faster than the previous approaches if it computes all the nodes' embeddings?

In terms of running time, it is good to compare the proposed approach to the state-of-the-art approaches such as FastRP.

Since the proposed approach removes non-significant PPR scores by using log b, it would impact the proposed approach’s running time and accuracy. Could you tell me the effects of log b?

review_title: Need fair comparisons

Meta-review: This paper proposes an efficient algorithm to obtain a node embedding based on its local PageRank scores. The proposed approach uses a hashing technique and a local partition approach to make the method more efficient and effective. However, the paper has significant drawback and can be further improved in the following aspects: 
1. The experimental evaluation is weak and does not allow us to draw meaningful conclusions about the proposed algorithm. 
2. The proposed algorithm does not show significant performance improvement on the link prediction task.
Decision: Reject