  This paper studies the joint community detection and phase synchronization
problem on the \textit{stochastic block model with relative phase}, where each
node is associated with an unknown phase angle. This problem, with a variety of
real-world applications, aims to recover the cluster structure and associated
phase angles simultaneously. We show this problem exhibits a
\textit{``multi-frequency''} structure by closely examining its maximum
likelihood estimation (MLE) formulation, whereas existing methods are not
originated from this perspective. To this end, two simple yet efficient
algorithms that leverage the MLE formulation and benefit from the information
across multiple frequencies are proposed. The former is a spectral method based
on the novel multi-frequency column-pivoted QR factorization. The factorization
applied to the top eigenvectors of the observation matrix provides key
information about the cluster structure and associated phase angles. The second
approach is an iterative multi-frequency generalized power method, where each
iteration updates the estimation in a matrix-multiplication-then-projection
manner. Numerical experiments show that our proposed algorithms significantly
improve the ability of exactly recovering the cluster structure and the
accuracy of the estimated phase angles, compared to state-of-the-art
algorithms.
