Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method

Sijin Chen; Xiwei Cheng; Anthony Man-Cho So

Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method

Sijin Chen, Xiwei Cheng, Anthony Man-Cho So

Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:2899-2907, 2024.

Abstract

This paper proposes a Generalized Power Method (GPM) to simultaneously solve the joint problem of community detection and group synchronization in a direct non-convex manner, in contrast to the existing method of semidefinite programming (SDP). Under a natural extension of stochastic block model (SBM), our theoretical analysis proves that the proposed algorithm is able to exactly recover the ground truth in

$O(n\log^2 n)$ time for problems of size

$n$ , sharply outperforming the

$O(n^{3.5})$ runtime of SDP. Moreover, we give a lower bound of model parameters as a sufficient condition for the exact recovery of GPM. The new bound breaches the information-theoretic limit for pure community detection under SBM, thus demonstrating the superiority of our simultaneous optimization algorithm over any two-stage method that performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to corroborate our theoretical analysis.

Cite this Paper

BibTeX

@InProceedings{pmlr-v238-chen24e,
  title = 	 {Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method},
  author =       {Chen, Sijin and Cheng, Xiwei and Man-Cho So, Anthony},
  booktitle = 	 {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
  pages = 	 {2899--2907},
  year = 	 {2024},
  editor = 	 {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
  volume = 	 {238},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {02--04 May},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v238/chen24e/chen24e.pdf},
  url = 	 {https://proceedings.mlr.press/v238/chen24e.html},
  abstract = 	 {This paper proposes a Generalized Power Method (GPM) to simultaneously solve the joint problem of community detection and group synchronization in a direct non-convex manner, in contrast to the existing method of semidefinite programming (SDP). Under a natural extension of stochastic block model (SBM), our theoretical analysis proves that the proposed algorithm is able to exactly recover the ground truth in $O(n\log^2 n)$ time for problems of size $n$, sharply outperforming the $O(n^{3.5})$ runtime of SDP. Moreover, we give a lower bound of model parameters as a sufficient condition for the exact recovery of GPM. The new bound breaches the information-theoretic limit for pure community detection under SBM, thus demonstrating the superiority of our simultaneous optimization algorithm over any two-stage method that performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to corroborate our theoretical analysis.}
}

Endnote

%0 Conference Paper
%T Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method
%A Sijin Chen
%A Xiwei Cheng
%A Anthony Man-Cho So
%B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics
%C Proceedings of Machine Learning Research
%D 2024
%E Sanjoy Dasgupta
%E Stephan Mandt
%E Yingzhen Li	
%F pmlr-v238-chen24e
%I PMLR
%P 2899--2907
%U https://proceedings.mlr.press/v238/chen24e.html
%V 238
%X This paper proposes a Generalized Power Method (GPM) to simultaneously solve the joint problem of community detection and group synchronization in a direct non-convex manner, in contrast to the existing method of semidefinite programming (SDP). Under a natural extension of stochastic block model (SBM), our theoretical analysis proves that the proposed algorithm is able to exactly recover the ground truth in $O(n\log^2 n)$ time for problems of size $n$, sharply outperforming the $O(n^{3.5})$ runtime of SDP. Moreover, we give a lower bound of model parameters as a sufficient condition for the exact recovery of GPM. The new bound breaches the information-theoretic limit for pure community detection under SBM, thus demonstrating the superiority of our simultaneous optimization algorithm over any two-stage method that performs the two tasks in succession. We also conduct numerical experiments on GPM and SDP to corroborate our theoretical analysis.

APA

Chen, S., Cheng, X. & Man-Cho So, A.. (2024). Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:2899-2907 Available from https://proceedings.mlr.press/v238/chen24e.html.

Related Material

Download PDF