2024-04-18-chen24e.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chen24e	0	Non-Convex Joint Community Detection and Group Synchronization via Generalized Power Method	2899	2907	2899-2907	2899	false	Chen, Sijin and Cheng, Xiwei and Man-Cho So, Anthony	given family Sijin Chen given family Xiwei Cheng given family Anthony Man-Cho So	2024-04-18		Proceedings of The 27th International Conference on Artificial Intelligence and Statistics	238	inproceedings	date-parts 2024 4 18	https://proceedings.mlr.press/v238/chen24e/chen24e.pdf