Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
In this work the authors propose a generative model for jointly learning a representation of nodes and communities in a joint framework.  The authors perform a wide variety of experiments on community (overlapping, non-overlapping) detection, and noed classification. This paper is potentially very interesting due to the large improvements it shows on some important tasks, but there are several non-trivial issues that I discuss in the following, and due to which I feel the paper is not above the bar in its current form. 

1. The authors should clarify early on, whether the focus is on undirected unweighted graphs, or general directed weighted graphs. 

2. The authors mention "In the literature these tasks are treated separately". The authors should discuss the problem more precisely. For instance if I have two connected components, each being a clique, most node embedding methods will capture this by placing nodes from each clique on the same point (or really close). If the two connected components are sparse, the nodes from each component will be embedded closer to each other compared to nodes from the other connected component.  So, standard graph embedding methods do capture basic connectivity, i.e., crude connectivity structure. This bring me also to the next point. 
3. How is the notion of a community defined here? Do you consider a community a set of low conductance? Or some set of nodes that share certain common attributes? I assume the former, i.e., some form of a well-connected set of nodes that is less well-connected to the rest of the graph.  
4. Can the authors comment on the improvements they observe using their method? Is it due to the fact that labels within the community are overwhelmingly similar?  The authors use as competitors methods that do not take into account features. If the difference lies in this, the authors should compare also against graph convolutional networks. In any case, a more detailed explanation of the improvements is required in my opinion. See also point 8 for an important reference to this work. 
5. In terms of competitors for overlapping community detection the authors should take a look at  the recent paper "SimClusters: Community-Based Representations for Heterogeneous Recommendations at Twitter" that describes some mechanics of Twitter's recommendation system, and that uses the objective, and a variation of the algorithm  proposed in "Provably fast inference of latent features from networks: With applications to learning social circles and multilabel classification" WWW 2015 for overlapping community detection. The algorithms in these two papers for instance outperform BigClam. 
6. Does the proposed method yield any concrete theoretical improvement? For example, have the authors tried to show that it achieves better than Cheeger's approximation guarantee? Perhaps some simulation results on synthetic dataset can provide at least some experimental evidence by looking inner products of nodes within and across communities. 
7. It would be helpful to explain the novelty of this work compared to the vGraph Neurips 2019 paper. 
8. Concerning the top 5 communities choice, the authors should also take a look at this paper  "The ground truth about metadata and community detection in networks" Science Advances  where the notion of ground-truth used in this work is questioned.  


review_title: Review 

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a generative model for community detection and node representation in a unified framework. The underlying assumption of the work is that connected nodes in a graph should have similar node embeddings and similar community assignments. Experimental evaluations show improvement both on node classification and community detection (both overlapping and non-overlapping).

The problem of integrating community detection and node representation in a unified framework is important and needs more attention from the researchers. The paper also motivates the problem well. The overall presentation is good and easy to follow. However, there are few concerns I have about the paper, as stated below.

1. The technical approach of the paper seems to be quite similar to the cited work vGraph (NeurIPS 2019). It would be good to point out the major differences between the two works.

2. Joint community detection and node representation learning - more discussion is needed for this subsection. Specifically, the existing works which integrate these two tasks and limitation of those works should be explained.

3. In Eq. 3, is it fair to assume that z_i 's are iid random variables? Embedding of a node should depend on the embeddings of neighbors at the least.

4. The GCN encoder aggregates the embeddings of the neighbors of a node while modeling q_{\phi}(z_i | I). Then what is the need of Equation 11 instead of Equation 10?

5. The last term of Equation 7 is a sum over all pairs of nodes, not only on the edges. Should not it lead to a computational complexity of O(N^2)?

6. DGI (ICLR 2019) should be used for both non-overlapping community detection and node classification, as it is a SOTA algorithm for unsupervised node representation learning. 

7. In Section 4.4, only results in Tables 2-4 are presented in words. I could not see any analysis and insight in this section. The reason of superior performance of VECODER compared to individual baselines is also missing.

8. Can authors also report classification accuracy on Cora and Citeseer, as that is a standard adopted by different SOTA network representation algorithms?


------------------------------------

Authors did answer some of my doubts through their response. However, I am still not very convinced if the paper has sufficient novelty to get accepted in ICLR. I increase my score from 4 to 5.
review_title: Interesting problem, but limited novelty

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

This paper aims to learn node representations of graph to jointly satisfy node embedding properties and community detection property. Node embedding must preserve proximities guaranteeing that adjacent nodes are closer than others. Community detection must promote more similar clustering assignments to adjacent nodes than others. These two problems have been tackled separately or simultaneously but with maintaining two different node representations. The authors claim that the proposed VECoDeR is capable of learning a single community-aware node representation per node, which is jointly effective in both scenarios.


(Originality and Contributions)

Their model assumes several conditional independences such as cluster assignments of different nodes given node representation, and adjacencies on different edges given the cluster assignments and node embeddings of each end. Then the rest of them creating ELBO and using reparametrization trick for training variational autoencoder follows the standard procedure. Posterior distribution of cluster assignment in the encoder adopt the weighted message passing (similar to graph convolution or Sun et al 2019). One possibly small novelty would be the parametrization of the edge decoder. In this sense, readers must find this paper’s contribution more in the practical side – superior performance -- than in the theoretical aspects.


(Strength and weakness)
- Strength is the performance that beats all other famous models. 
- Weakness is the lack of analysis that provide intuitions why and how VECoDeR outperforms other models by a big margin.


(Concerns, Questions, and Suggestions)

1) In the equation (12), the query random variable must be $a_{ij}$ rather than $e_{ij}$. 

2) It would be also great to double clarify what types of and how many parameters belong to the encoder (in $\phi$) and the decoder (in $\theta$). 

3) Using Gumbel-softmax trick allows you to efficiently sample one-hot vector of clustering assignment for non-overlapping community detection. For overlapping community detection, in contrast, clustering assignment matrix would be dense by assigning possibly negligible probability mass to all existing clusters. In the inference time, you are able to threshold it to reduce the dense connection by increasing $\epsilon$, but how to scale the algorithm for learning large number of clusters?
 
4) Related to the previous point, the number of clusters $K$ in all datasets seem to be orders of magnitudes smaller comparing to the number of nodes. This is often not satisfied in real data and some scenarios could ask overcomplete community detection (see Ananakumar et al 2012). Is the proposed model capable of detecting fine-grained community structures?

5) Similarly, the model seems to be too independent from different hyperparameter settings of $\alpha$ and $\epsilon$ than expected. At least one or two datasets where the ground-truth overlapping communities are approximately known must be tested with much larger $K$ for robustness check.

6) Assuming the reported performance are all correct, VECoDeR outperforms a variety of famous models for graph representation learning. Having some qualitative examples (than abstract explanation in high-level about structure preservation) would be beneficial. In particular, some part of the graph that does not performed well in all other models but correctly done by VECoDeR. Current draft rarely provides such intuitions to potential readers and users.

review_title: Review for VECoDeR

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper deals with the problem of simultaneously learning node embeddings and detecting communities on graphs. Although both tasks are particularly important while analyzing networks, most of the proposed approaches address them independently. The paper proposes a generative model, called VECODER, that aims to jointly learn overlapping communities and node representations. The proposed model follows a variational formulation which assumes that the node embeddings are generated from a prior distribution; this can be used to control how community embeddings are sampled. This leads to an encoder-decoder architecture, where the decoder ensures that similar (i.e., connected) nodes will obtain similar embeddings. The proposed model has been empirically evaluated on three tasks (overlapping and non-overlapping community detection, and node classification), and the performance has been compared against various baseline models.

Strong points:

-- The paper addresses two important problems in network analysis, namely community detection and representation learning.  

-- The paper is well-structured and well-written. In particular, the part of the proposed methodology is clearly presented and overall seems to be very interesting.

-- In the experimental evaluation of the proposed model, the performance of VECODER is examined over multiple networks on three different tasks.

Weak points:

-- The main concern about the paper is related to the experimental evaluation. In particular, some important baselines methods are missing. Since the paper examines community-based embeddings, I would expect to consider M-NMF as a baseline. The authors mention M-NMF in the related work but do not consider it in the evaluation mainly due to its scalability issues. In any case, most of the datasets used in the experiments are relatively small, so I expect that M-NMF would be able to scale.

-- Besides, a few other quite important baselines are missing from both the empirical evaluation and the related work. Below, I mention three papers that are highly relevant:

- A unified framework for community detection and network representation learning, TKDD 2018
- Graph Embedding with Self-Clustering, ASONAM 2019
- CommunityGAN: Community Detection with Generative Adversarial Nets, CIKM 2019

Is there any particular reason why these models have not been considered?

-- Another point is related to the fact that the proposed model is based on an encoder-decoder framework that leverages features while learning embeddings. On the contrary, most of the used baseline models (e.g., ComE) do not take into account features while learning representations. Although node features are used while training a logistic regression classifier for node classification, to my view this is not a very fair comparison. So, my question is why the paper did not consider variants of GNN models (with unsupervised training) or Graph Autoencoders as baselines?

-- Is there any particular reason why the task of link prediction has not been considered?

-- In Table 3, in both CiteSeer networks, there is a huge gap in the performance of the proposed model compared to the baselines. Why is this happening?

-- The parameter sensitivity experiments are very interesting. Nevertheless, I would expect to also have some experiments that would demonstrate how the design choices have affected the performance of the model. For instance, as mentioned in Sec. 3.3, would there be any impact on the performance on downstream tasks if different GNN architectures are used as encoders?


Minor comments/typos:

-- In the Related work section (page 2), it is mentioned that spectral clustering is applied to the adjacency matrix for extracting communities. I would propose the authors to mention the Laplacian matrix instead.

-- Related work (page 3): some spaces are missing before references, and some others should be removed.

review_title: Interesting methodology, but the experimental evaluation should be enhanced.

Meta-review: The paper proposes a new method to learn representation and community structure of a network jointly. The reviewers agree that the paper contains some interesting ideas but they raise also some important concerns. For example:

- even after considering the authors' rebuttal, the paper seems not too novel. In particular the results seem a bit incremental over vGraph.

- the notion of community is not formalized by the authors neither in the paper or in the rebuttal. The paper would benefit greatly by having such formal definition 

Overall, the paper is interesting but it does not meet the high acceptance bar of ICLR
Decision: Reject