Local Statistics, Semidefinite Programming, and Community Detection*
Local Statistics, Semidefinite Programming, and Community Detection*
复制标题
局部统计、半定规划和社区检测*
DOI：
10.1137/1.9781611976465.79
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Jess Banks, Sidhanth Mohanty
中科院分区：
文献类型：
--
作者：
Jess Banks, Sidhanth Mohanty
针对推理问题，提出了一种新的、可有效求解的半定规划松弛层次。作为测试用例，我们考虑了块模型中的社区检测问题。这些顶点被划分为社区，并在规定数量的社区间和社区内边的条件下对图进行采样。在检测问题中，我们要以高概率决定一个图是从这个模型中绘制的还是从正则图上的均匀分布中绘制的，我们推测在一个称为Kesten-Stigum （KS）阈值的点上要经历一个计算相变。在这项工作中，我们考虑了随机图的两种模型，即研究得很好的（不规则的）随机块模型和随机正则图的分布，我们称之为程度正则块模型。对于这两个模型，我们表明，足够高的层次结构常数水平可以执行任意接近KS阈值的检测，并且我们的算法对高达线性数量的对抗性边缘扰动具有鲁棒性。此外，在度规则块模型的情况下，我们表明，在Kesten-Stigum阈值以下，没有常数水平可以这样做。在（不规则）随机块模型的情况下，已知存在有效的算法一直到这个阈值，尽管没有一个算法对线性边数的对抗性扰动具有鲁棒性。更重要的是，几乎没有复杂性理论证据表明在阈值以下检测是困难的。在超过两个组的DRBM中，据我们所知，还没有证明任何算法能够成功地降低到KS阈值，更不用说可以做到这一点了，并且硬度低于这一点的证据也同样缺乏。我们的SDP层次结构是高度通用的，适用于广泛的假设检验问题。
We propose a new, efficiently solvable hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertices are partitioned intokcommunities, and a graph is sampled conditional on a prescribed number of inter- and intra-community edges. The problem ofdetection, where we are to decide with high probability whether a graph was drawn from this model or the uniform distribution on regular graphs, is conjectured to undergo a computational phase transition at a point called the Kesten-Stigum (KS) threshold.In this work, we consider two models of random graphs namely the well-studied (irregular) Stochastic Block Model and a distribution over random regular graphs we'll call the Degree Regular Block Model. For both these models, we show that sufficiently high constant levels of our hierarchy can perform detection arbitrarily close to the KS threshold and that our algorithm is robust to up to a linear number of adversarial edge perturbations. Furthermore, in the case of Degree Regular Block Model, we show that below the Kesten-Stigum threshold no constant level can do so.In the case of the (irregular) Stochastic Block Model, it is known that efficient algorithms exist all the way down to this threshold, although none are robust to adversarial perturbation of alinearnumber of edges. More importantly, there is little complexity-theoretic evidence that detection is hard below the threshold. In the DRBM with more than two groups, it has not to our knowledge been proven that any algorithm succeeds down to the KS threshold, let alone that one can do so robustly, and there is a similar dearth of evidence for hardness below this point.Our SDP hierarchy is highly general and applicable to a wide range of hypothesis testing problems.