Scalable Algorithms for Uniform Max Size-Constrained Correlation Clustering
Nathan Cordner, George Kollios · 2025
Correlation clustering (CC) groups objects together based on pairwise relationships (either positive or negative). The CC objective is to minimize the number of negative relationships between objects clustered together, and positive relationships between objects in different clusters. This clustering approach is used in numerous applications, including machine learning classification, database deduplication, and community detection.Most state-of-the-art algorithms for CC, including with cluster size constraints, rely on solving time-consuming linear programs (LPs). Recent research efforts have been trying to bridge the gap between quality approximation results and time-efficient algorithms that run in nearly-linear time or better.In this paper we focus on CC with uniform hard max cluster size constraints. We revisit and adapt popular methods like Pivot and Vote as practical alternatives to existing methods. We provide the first direct comparison between these methods and the state-of-the-art LP rounding algorithms, and show experimentally that we can obtain quality clustering results without the overhead cost of running LP solvers.