Summary
The paper under revision addresses the problem of graph matching and community recovery in correlated stochastic block models (SBM) with two balanced communities. In particular, it studies the regime where the vertices of the parent graph have a logarithmic average degree, considering the within-community edge probability to be $a\frac{\log n}{n}$ and between-community edge probability to be $b\frac{\log n}{n}$. The edge correlation parameter is equal to $s$.
Regarding graph matching, they proved in Theorem 1 the existence of a polynomial-time algorithm that can achieve both almost exact and exact matching. Almost exact matching is achieved when the square of the edge correlation is greater than Otter’s tree counting constant ($s^2 > \alpha$). To obtain exact matching, an additional condition is necessary, namely $s^2(a+b)/2 > 1$. This result extends known results on almost exact and exact matching for correlated Erd\H{o}s--Rényi graphs obtained in Mao et al. (2023). It corroborates the previous work by Racz & Sridhar (2021), which determined that exact matching in correlated SBM is only achieved when $s^2(a+b)/2 > 1$.
In the context of community detection, Theorem 2 of the manuscript states that exact community recovery in correlated SBM is achieved by a polynomial-time algorithm when \( s^2 > \alpha \), and it satisfies the information-theoretic threshold for community recovery in correlated SBM established by Racz & Sridhar (2021). The authors provide a brief description of the polynomial-time algorithm in Section 5 and a more detailed explanation in Appendix C. In this way, one of the main contributions of this work is to propose an efficient algorithm for graph matching for correlated SBM.
In terms of the algorithm itself, it is structured by first applying a community detection algorithm proposed by Mossel et al. (2015) to each of the graphs to ensure exact recovery of the communities. Then, an adaptation of the algorithm proposed by Mao et al. (2023) for correlated Erdős–Rényi graphs, based on rooted trees known as chandeliers, is applied.
The manuscript combines established ideas from previous works, specifically integrating the concepts from Racz & Sridhar (2021) and Mao et al. (2023) to develop a polynomial-time algorithm for graph matching in correlated SBM. The manuscript is well-structured and provides detailed explanations of the algorithms, results and their connections to related works.
References:
Mao, Cheng, Wu, Yihong, Xu, Jiaming, & Yu, Sophie H. 2023. Random graph matching
at Otter’s threshold via counting chandeliers. Pages 1345–1356 of: Proceedings of the
55th Annual ACM Symposium on Theory of Computing.
Mossel, Elchanan, Neeman, Joe, & Sly, Allan. 2015. Consistency thresholds for the planted
bisection model. Pages 69–75 of: Proceedings of the forty-seventh annual ACM
symposium on Theory of computing.
Racz, Miklos, & Sridhar, Anirudh. 2021. Correlated stochastic block models: Exact graph
matching with applications to recovering communities. Advances in Neural Information
Processing Systems, 34, 22259–22273.
Strengths
The manuscript combines established ideas from previous works, specifically integrating the concepts from Racz & Sridhar (2021) and Mao et al. (2023) to develop a polynomial-time algorithm for graph matching in correlated SBM. The manuscript is well-structured and provides detailed explanations of the algorithms, results, and their connections to related works.