Correlation Clustering Reconstruction in Semi-Adversarial Models
Correlation Clustering Reconstruction in Semi-Adversarial Models
复制标题
半对抗模型中的相关聚类重建
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
Flavio Chierichetti;A. Panconesi;G. Re;L. Trevisan
相关聚类是许多应用中的一个重要聚类问题。我们研究这个问题的重建版本，其中人们试图重建一个被随机噪声和对抗性修改破坏的潜在聚类。关于后者，我们研究了一个标准的“后对抗性”模型，其中对抗性修改发生在噪声之后，并且还介绍并分析了一种“前对抗性”模型，其中对抗性修改发生在噪声之前。给定来自这种半对抗性生成模型的输入，目标是几乎完美地且高概率地重建潜在聚类。我们重点关注隐藏簇具有相同大小的情况，并显示以下内容。在预对抗环境中，谱算法是最优的，因为它们一直重建到信息论阈值，超过该阈值就不可能进行重建。相比之下，在后对抗环境中，他们恢复隐藏簇的能力在阈值之前停止，但基于 SDP 的算法可以最佳地填补这一空白。
Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, we study a standard “post-adversarial” model, in which adversarial modifica-tions come after the noise, and also introduce and analyse a “pre-adversarial” model in which adversarial modifications come before the noise. Given an input coming from such a semi-adversarial generative model, the goal is to reconstruct almost perfectly and with high probability the latent clustering. We focus on the case where the hidden clusters have equal size and show the following. In the pre-adversarial setting, spectral algorithms are optimal, in the sense that they reconstruct all the way to the information-theoretic threshold beyond which no reconstruction is possible. In contrast, in the post-adversarial setting their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms.
影响因子：
1.1
作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking
通讯作者：
Matthias Englert;Heiko Röglin;Berthold Vöcking