A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization
复制标题
DOI：
10.1137/21m1467845
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Yifeng Fan;Y. Khoo;Zhizhen Zhao
中科院分区：
文献类型：
--
作者：
Yifeng Fan;Y. Khoo;Zhizhen Zhao
社区检测和正交群同步是科学和工程中具有重要应用的基本问题。在这项工作中，我们考虑的联合问题的社区检测和正交组同步，旨在恢复社区和同步的同时进行。为此，我们提出了一个简单的算法，包括一个频谱分解步骤，然后是一个块列枢轴QR分解（CPQR）。所提出的算法是有效的，并与图中的边的数量成线性比例。我们还利用最近开发的“留一出”技术，建立一个接近最佳的保证准确恢复的集群成员和稳定恢复的正交变换。数值实验表明，我们的算法的效率和有效性，并确认我们的理论表征。
Community detection and orthogonal group synchronization are both fundamental problems with a variety of important applications in science and engineering. In this work, we consider the joint problem of community detection and orthogonal group synchronization which aims to recover the communities and perform synchronization simultaneously. To this end, we propose a simple algorithm that consists of a spectral decomposition step followed by a blockwise column pivoted QR factorization (CPQR). The proposed algorithm is efficient and scales linearly with the number of edges in the graph. We also leverage the recently developed `leave-one-out' technique to establish a near-optimal guarantee for exact recovery of the cluster memberships and stable recovery of the orthogonal transforms. Numerical experiments demonstrate the efficiency and efficacy of our algorithm and confirm our theoretical characterization of it.