We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige-Kilian or monotone errors, and edge outlier errors. Our work answers affirmatively an open question posed by Mossel, Neeman and Sly (STOC 2015), that asked whether an almost exact recovery is possible when the adversary is allowed to add $o(n)$ edges. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is $\epsilon m$ close to SBM in the Kullback-Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.

本文研究了学习社区并提供了鲁棒性恢复算法来解决SBM中建模误差的问题，SBM广泛用于各个领域中的社区检测和图划分。我们考虑了两种adversarial error，并回答了一个开放性问题，证明了我们的算法即使在k>2的情况下也可以实现几乎精确的恢复，并证明了我们的算法不仅适用于SBM生成的图，还应用于与SBM在Kullback-Leibler散度上相似的任何图分布。

存在误差下的学习社区