Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the task of learning latent community structure from two correlated Stochastic Block Models (SBM). They provide a information theoretic threshold above which there exists a estimator that learns the community structure with probability 1, and below which no estimator can recover the true correspondence with some probability away from 0.
main_review: This is a well written paper that not only is a precursor for using multiple correlated graphs to learn underlying latent communities, it demonstrates the advantages of using multiple graphs instead of a single graph (Theorem 3.6). The authors have shown robust and novel understanding of the subject as well as described conjectures on where future research work in this area could potentially head. I find that this adds to the significance of their results. Clear accept.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper revisits the community detection problem from a theoretical perspective. The community detection problem on the SBM is now well-understood, this paper looks at a case where 2 correlated SBMs are given instead of only one. The nodes of the 2 SBMs represent the same population but the mapping between the nodes of the 2 SBMs is not known. This is a natural extension of the mathematical problem of community detection on a single SBM motivated for example by de-anonymizing social networks.
The authors obtain partial results for exact recovery. A natural algorithm is to first align the 2 SBMs and then used the union of the 2 SBMs which is still a SBM to find the communities. The authors fully characterize when exact alignment is possible and then provide sufficient conditions for exact recovery. They also prove a partial converse result and provide conditions under which community recovery is information theoretically impossible.
main_review: The paper is very clear, well written and easy to read. I think that this line of work is a very natural extension for the SBM and will lead to subsequent works. As the authors claim, their work is a first step and I suspect that it will trigger interest in the crowd working on the theory of ML.
limitations_and_societal_impact: OK
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the exact graph matching problem in correlated stochastic block model. With the exact graph matching function, classical community detection algorithm can achieve exact community recovery.
main_review: The main contribution of the this paper is the analysis on phase transaction on the possibility on exact graph matching in correlated stochastic block model. Existing literature only solves the problem with correct community labels. The result is interesting and substantial in network analysis. 
The paper is well organized and reader-friendly.
limitations_and_societal_impact: The author has clearly indicated the limitation of this paper. The contribution to the community recovery problem is actually limited. The paper has not solved the community detection problem. Given the true matching function of the nodes, community recovery can be obtained by existing algorithms.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides necessary and sufficient conditions for exact recovery problems in a two-community correlated stochastic block model (SBMs). In this model, correlated SBMs are generated on the same set of vertices in a natural way and then the vertices of  one of the SBMs is randomly permuted. The paper gives necessary and sufficient conditions for 1) recovering the (unknown) permutation to recover the correspondence between the two SBMs and 2) recovering the underlying community memberships.  The extension to multiple correlated SBMs in also considered. 
main_review: This paper is clearly written. It provides a nice descriptions of the problem and the results are easy to follow. Overall, I enjoyed reading it. 

The key part of the proof requires a careful analysis of the conditions for finding the graph matching. While it seems the main approach builds upon previous work, there are a number of technical details which are well explained in the supplementary material. I think this analysis should also be viewed as a useful contribution of the paper. 

The significance and novelty are on par with related work in the literature. Also, similar to other work in the literature, the model is not very realistic so these results are more an exercise in mathematical analysis rather than shedding new insight into community detection problems in practice. Along these lines, one may question whether exact community recovery is a realistic objective, as opposed to approximate recovery. The authors do mention approximate recovery in the future work section.

limitations_and_societal_impact: The assumptions for the theoretical results are clearly stated.  Given the theoretical nature of this work I do not see the need for any more discussion on societal impact.
review_title: null

Meta-review: This paper presents a fine theoretical contribution showing how an initial step of graph matching of correlated graphs yields improved results to subsequently perform community detection, assuming graphs sampled from a correlated stochastic block model. The reviews are quite positive. Indeed joint consideration of multiple graphs to perform tasks such as community detection is a very natural strategy, and does not seem to have received much attention in the past. This makes the paper's contribution all the more valuable, hence the recommendation to accept. 
Decision: Accept (Spotlight)