A Parallel Algorithm for $(3 + \varepsilon)$-Approximate Correlation Clustering

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study parallel algorithms for correlation clustering, where each pair of items is labeled either similar or dissimilar. The task is to partition the elements and the objective is to minimize disagreements, that is, the number of dissimilar elements grouped together and similar elements grouped separately. Our main contribution is a parallel algorithm that achieves a $(3 + \varepsilon)$-approximation to the minimum number of disagreements. Our algorithm builds on the analysis of the PIVOT algorithm by Ailon, Charikar, and Newman [JACM'08] that obtains a $3$-approximation in the centralized setting. Our design allows us to sparsify the input graph by ignoring a large portion of the nodes and edges without a large extra cost as compared to the analysis of PIVOT. This sparsification makes our technique applicable on several models of massive graph processing, such as Massively Parallel Computing (MPC) and graph streaming, where sparse graphs can typically be handled much more efficiently. For linear memory models, such as the linear memory MPC and streaming, our approach yields $O(1)$ time algorithms, where the runtime is independent of $\varepsilon$, which only appears in the memory demand.