# Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models

arXiv: https://arxiv.org/abs/2108.04729 · HTML: https://mlsanity.com/paper/2108.04729/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 48 references that are in the map.
- First posted on arXiv 10 Aug 2021.

## Builds on (most cited first, 14 of 14)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1601.02658/) (2016)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian](https://mlsanity.com/paper/2006.06658/) (2020)
- [Learning Communities in the Presence of Errors](https://mlsanity.com/paper/1511.03229/) (2015)
- [Robustness of spectral methods for community detection](https://mlsanity.com/paper/1811.05808/) (2018)
- [Does robustness imply tractability? A lower bound for planted clique in the semi-random model](https://mlsanity.com/paper/1704.05120/) (2017)
- [Robustness of Community Detection to Random Geometric Perturbations](https://mlsanity.com/paper/2011.04298/) (2020)

## Built on by (most cited first, 2 of 2)

- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [Correlation Clustering with Random Partial Information](https://mlsanity.com/paper/2608.16315/) (2026)

## Abstract (arXiv)

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, 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 reconstruct almost perfectly and 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.