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