Correlation Clustering with Random Partial Information
2026-08-17 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors study a clustering problem where the goal is to group items based on positive and negative connections. While good approximate solutions exist when every item is connected to every other (complete graphs), these solutions perform poorly on less connected graphs. They focus on graphs made by randomly removing connections from a complete graph and show that for these, the problem can be solved with better approximations than in general incomplete graphs. Their experiments also indicate these results are close to those possible on fully connected graphs.
correlation clusteringapproximation algorithmscomplete graphsincomplete graphsmin-disagreementmin-max objectiverandom subsamplingconstant-factor approximationgraph theoryunsupervised learning
Authors
Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
Abstract
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.