English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Correlation Clustering is an important clustering problem with manyapplications. We study the reconstruction version of this problem in which oneis seeking to reconstruct a latent clustering that has been corrupted by randomnoise and adversarial modifications. Concerning the latter, there is a standard"post-adversarial" model in the literature, in which adversarial modificationscome after the noise. Here, we introduce and analyse a "pre-adversarial" modelin which adversarial modifications come before the noise. Given an input comingfrom such a semi-adversarial generative model, the goal is to reconstructalmost perfectly and with high probability the latent clustering. We focus onthe case where the hidden clusters have nearly equal size and show thefollowing. In the pre-adversarial setting, spectral algorithms are optimal, inthe sense that they reconstruct all the way to the information-theoreticthreshold beyond which no reconstruction is possible. This is in contrast tothe post-adversarial setting, in which their ability to restore the hiddenclusters stops before the threshold, but the gap is optimally filled bySDP-based algorithms. These results highlight a heretofore unknown robustnessof spectral algorithms, showing them less brittle than previously thought.

Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models