Search papers, labs, and topics across Lattice.
This paper investigates correlation clustering on randomly subsampled signed graphs, addressing the significant performance gap in approximation guarantees between complete and general graphs. By analyzing the min-max and min-disagreement objectives, the authors establish that certain incomplete graphs can achieve approximation guarantees that approach those of complete graphs, depending on the edge deletion probability \( q \). Empirical results further support the theoretical findings, demonstrating that the proposed method yields approximation ratios superior to those of general graphs while being comparable to complete graphs.
Randomly subsampling edges can yield correlation clustering approximations that rival those of complete graphs, challenging existing lower bounds for general graphs.
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.
BAIR