标题： 高斯加权随机块模型和植入密集子图中的精确恢复：统计和算法阈值 显示英文标题

标题： Exact recovery in Gaussian weighted stochastic block model and planted dense subgraphs: Statistical and algorithmic thresholds

摘要： 在本文中，我们研究了具有两个对称社区的随机块模型的高斯加权版本中的精确恢复问题。我们以模型的信噪比（SNR）为基准提供了信息理论阈值，并证明当SNR$<1$时，没有任何统计估计器可以在概率远离零的情况下精确恢复社区结构。另一方面，我们表明当SNR$>1$时，最大似然估计器本身可以以接近一的概率精确恢复社区结构。然后，我们提供了两种算法来实现精确恢复。最大似然估计器的半定松弛以及谱松弛可以将社区结构恢复到阈值值1，从而确立了该模型不存在信息-计算差距。接下来，我们将社区检测问题与在图中恢复一个密集加权的植入社区的问题进行比较，并证明在相同SNR$< 3/2$的情况下，没有任何统计估计器可以在概率远离零的情况下精确恢复植入社区，从而证明了两个对称社区的精确恢复问题比恢复大小为总节点数一半的密集子图的问题要严格容易。更准确地说，当$1 <$SNR$< 3/2$时，社区检测的精确恢复在统计上和算法上都是可能的，但在高斯加权模型中，即使在统计上也无法精确恢复植入社区。最后，我们证明当SNR$>2$时，最大似然估计器本身可以以接近一的概率精确恢复植入社区。我们还证明了最大似然估计器的半定松弛可以将植入社区结构恢复到阈值值2。 显示英文摘要

摘要： In this paper, we study the exact recovery problem in the Gaussian weighted version of the Stochastic block model with two symmetric communities. We provide the information-theoretic threshold in terms of the signal-to-noise ratio (SNR) of the model and prove that when SNR $<1$, no statistical estimator can exactly recover the community structure with probability bounded away from zero. On the other hand, we show that when SNR $>1$, the Maximum likelihood estimator itself succeeds in exactly recovering the community structure with probability approaching one. Then, we provide two algorithms for achieving exact recovery. The Semi-definite relaxation as well as the spectral relaxation of the Maximum likelihood estimator can recover the community structure down to the threshold value of 1, establishing the absence of an information-computation gap for this model. Next, we compare the problem of community detection with the problem of recovering a planted densely weighted community within a graph and prove that the exact recovery of two symmetric communities is a strictly easier problem than recovering a planted dense subgraph of size half the total number of nodes, by establishing that when the same SNR$< 3/2$, no statistical estimator can exactly recover the planted community with probability bounded away from zero. More precisely, when $1 <$ SNR $< 3/2$ exact recovery of community detection is possible, both statistically and algorithmically, but it is impossible to exactly recover the planted community, even statistically, in the Gaussian weighted model. Finally, we show that when SNR $>2$, the Maximum likelihood estimator itself succeeds in exactly recovering the planted community with probability approaching one. We also prove that the Semi-definite relaxation of the Maximum likelihood estimator can recover the planted community structure down to the threshold value of 2.