Semidefinite Programming for Community Detection With Side Information
Semidefinite Programming for Community Detection With Side Information
复制标题
DOI：
10.1109/tnse.2021.3078612
复制
发表时间：
2021-04
影响因子：
6.6
通讯作者：
Mohammadjafar Esmaeili;H. Saad;Aria Nosratinia
中科院分区：
文献类型：
--
作者：
Mohammadjafar Esmaeili;H. Saad;Aria Nosratinia
本文生成了一个有效的半决赛编程（SDP）解决方案，用于社区检测，其中包含了非编号数据，在这种情况下，该解决方案称为侧面信息。 SDP是用于图形上标准社区检测的有效解决方案。我们制定了半明确的放松，以观察图和非图形数据的最大似然估计。该公式与标准社区检测的SDP解决方案不同，但保持其理想的特性。我们计算了三种非图形信息的精确恢复阈值，在本文中称为侧面信息：部分显示标签，嘈杂的标签以及每个节点的多个观察值（功能），具有任意但有限的基数。我们发现，在存在侧面信息的情况下，SDP具有与最大可能性相同的恢复阈值。因此，本文开发的方法在计算上是有效的，并且在存在侧面信息的情况下求解社区检测方面具有准确性。模拟表明，本文的渐近结果还可以阐明SDP的性能，以显示适度的大小。
This paper produces an efficient semidefinite programming (SDP) solution for community detection that incorporates non-graph data, which in this context is known as side information. SDP is an efficient solution for standard community detection on graphs. We formulate a semi-definite relaxation for the maximum likelihood estimation of node labels, subject to observing both graph and non-graph data. This formulation is distinct from the SDP solution of standard community detection, but maintains its desirable properties. We calculate the exact recovery threshold for three types of non-graph information, which in this paper are called side information: partially revealed labels, noisy labels, as well as multiple observations (features) per node with arbitrary but finite cardinality. We find that SDP has the same exact recovery threshold in the presence of side information as maximum likelihood with side information. Thus, the methods developed herein are computationally efficient as well as asymptotically accurate for the solution of community detection in the presence of side information. Simulations show that the asymptotic results of this paper can also shed light on the performance of SDP for graphs of modest size.