论文标题
最小值的社区检测率
Minimax Rates for Robust Community Detection
论文作者
论文摘要
在这项工作中，我们研究了具有对抗性节点损坏的随机块模型中社区发现的问题。我们的主要结果是一种有效的算法，该算法可以忍受损坏的$ε$分数并达到错误$ o（ε） + e^{ - \ frac {c} {2} {2} {2}（1 \ pm o（1）} $ $ c =（$ c =）和$ b/n $分别是社区间和社区内连接概率。这些界限基本上与无损坏的SBM的最小值相匹配。我们还为$ \ mathbb {z} _2 $ -Synchronization提供了强大的算法。我们算法的核心是一个新的半决赛程序，它使用全局信息来鲁棒提高粗糙聚类的准确性。此外，我们表明我们的算法是双重的，因为它们在更具挑战性的噪声模型中起作用，该模型将对抗性腐败与无限的单调变化混合在一起，从半随机模型中。
In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an $ε$-fraction of corruptions and achieves error $O(ε) + e^{-\frac{C}{2} (1 \pm o(1))}$ where $C = (\sqrt{a} - \sqrt{b})^2$ is the signal-to-noise ratio and $a/n$ and $b/n$ are the inter-community and intra-community connection probabilities respectively. These bounds essentially match the minimax rates for the SBM without corruptions. We also give robust algorithms for $\mathbb{Z}_2$-synchronization. At the heart of our algorithm is a new semidefinite program that uses global information to robustly boost the accuracy of a rough clustering. Moreover, we show that our algorithms are doubly-robust in the sense that they work in an even more challenging noise model that mixes adversarial corruptions with unbounded monotone changes, from the semi-random model.
