Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models

Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:10852-10880, 2022.

Abstract

Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem, in which one seeks to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we 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 approximately reconstruct with high probability the latent clustering. We focus on the case where the hidden clusters have nearly 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. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-chierichetti22a, title = { Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models }, author = {Chierichetti, Flavio and Panconesi, Alessandro and Re, Giuseppe and Trevisan, Luca}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {10852--10880}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/chierichetti22a/chierichetti22a.pdf}, url = {https://proceedings.mlr.press/v151/chierichetti22a.html}, abstract = { Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem, in which one seeks to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we 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 approximately reconstruct with high probability the latent clustering. We focus on the case where the hidden clusters have nearly 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. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought. } }
Endnote
%0 Conference Paper %T Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models %A Flavio Chierichetti %A Alessandro Panconesi %A Giuseppe Re %A Luca Trevisan %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-chierichetti22a %I PMLR %P 10852--10880 %U https://proceedings.mlr.press/v151/chierichetti22a.html %V 151 %X Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem, in which one seeks to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we 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 approximately reconstruct with high probability the latent clustering. We focus on the case where the hidden clusters have nearly 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. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought.
APA
Chierichetti, F., Panconesi, A., Re, G. & Trevisan, L.. (2022). Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:10852-10880 Available from https://proceedings.mlr.press/v151/chierichetti22a.html.

Related Material