Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms

Sepehr Assadi, Sanjeev Khanna, Aaron Putterman

Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of be…