Correlation Clustering with Random Partial Information

Rajath Rao K. N.; Jens Schlöter; Sami Davies; Amira Ouchene; Yasamin Nazari

cs.DSAug 17, 2026

Correlation Clustering with Random Partial Information

Authors: Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari

Organizations: Vrije Universiteit Amsterdam, The Netherlands · CWI Amsterdam, The Netherlands · Department of EECS, UC Berkeley

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.

Figures & tables

Panel of Figure 1 — Figure 1: Performance of Algorithm 2 on the Facebook ego-graphs under random edge deletion, as means over $30$ seeds. Left: the six largest ego-graphs, showing the cost on $G^{\prime}$ relative to $(1-q)$ times the cost reported by Davies, Moseley, and Newman (2023) on the undeleted graph; one line per deletion probability $q$ , with $\log_{2}n$ dotted for reference. Right: the four smallest ego-graphs, where the min-max LP is solved on $G^{\prime}$ , so the ratio is an upper bound on the true approximation ratio.

Panel of Figure 2 — Figure 2: Approximation ratio of Pivot against the LP optimum, as a function of the deletion probability $q$ . Dotted lines show the mean ratio and the shaded region spans the best ratio observed to the mean. Left: planted-clique instances, over $50$ independent seeds per instance ( $20$ seeds for $n=100$ ). Right: the four smallest Facebook ego-graphs, over $30$ seeds.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Graph	#vertices	#edges	max. pos. degree
FB 3980	52	292	19
FB 698	61	540	30
FB 414	150	3,386	58
FB 686	168	3,312	78
FB 348	224	6,384	100
FB 0	333	5,038	78

Appendix

Table 1: Graph statistics for the Facebook ego-networks. The four graphs above the rule are those on which the LP relaxation was solved exactly; on the six below it the LP was not solved.

Figure 3: Average running time (log scale) of our combinatorial Algorithm 2 and of LP on the Facebook ego-networks, as a function of the number of vertices $n$ .

Figure 4: Cost of our Min-Max Algorithm ( Algorithm 2 ) on $G^{\prime}$ relative to $(1-q)$ times the cost of Davies, Moseley, and Newman (2023) on the original graph, over the six biggest ego-graphs where the min-max LP is infeasible. We ran it with $30$ seeds.

Figure 5: Approximation ratio of our Min-Max Algorithm ( Algorithm 2 ) against the min-max LP Equation 5 optimum on the four smallest Facebook ego-graphs, plotted against graph size; one line per deletion probability $q$

	$q$
Graph	0.05	0.15	0.25	0.40
FB 348	1.550 (0.043)	1.453 (0.056)	1.306 (0.088)	0.998 (0.068)
	$\pm.016$	$\pm.021$	$\pm.033$	$\pm.025$
FB 0	1.240 (0.038)	1.170 (0.075)	1.124 (0.073)	1.358 (0.118)
	$\pm.014$	$\pm.028$	$\pm.027$	$\pm.044$
FB 3437	0.747 (0.029)	0.685 (0.031)	0.717 (0.041)	0.904 (0.080)

Appendix

Table 2: Min-max cost of Algorithm 2 relative to

(1-q)

times the min-max cost of Davies, Moseley, and Newman (2023) on the undeleted graph, for Facebook ego-networks under deletion probability

q

; graphs are ordered by size. Each cell aggregates 30 seeds and gives the mean, the standard deviation in parentheses, and below it the

95\%

confidence interval as

\pm

a margin. Values below

1

indicate that our algorithm on

G^{\prime}

is cheaper than the scaled baseline.

	$q$
Graph	0.05	0.15	0.25	0.40
FB 3980	2.483 (0.061)	2.609 (0.118)	2.692 (0.175)	2.931 (0.225)
	$\pm.023$	$\pm.044$	$\pm.066$	$\pm.084$
FB 698	2.747 (0.041)	2.811 (0.083)	2.930 (0.122)	3.145 (0.158)
	$\pm.015$	$\pm.031$	$\pm.046$	$\pm.059$
FB 414	2.047 (0.052)	2.099 (0.087)	2.196 (0.228)	2.941 (0.204)

Appendix

Table 3: Min-Max approximation ratio against the min-max LP ( Equation 5 ) optimum ( Algorithm 2 / MinMaxLP) for Facebook ego-networks under deletion probability

q

. Each cell aggregates 30 seeds and gives the mean, the standard deviation in parentheses, and below it the

95\%

confidence interval as

\pm

a margin.

$n$	Clique decompositions
10	$2\times 5,\ (4,3,3),\ (5,3,2)$
15	$3\times 5,\ (5,5,3,2),\ (8,7)$
20	$2\times 10,\ 4\times 5,\ (7,7,6)$
25	$(10,10,5),\ (12,7,6),\ (13,12),\ (9,8,8)$
30	$(15,10,5),\ (20,5,5),\ 2\times 15,\ 3\times 10$
100	$10\times 10,\ 4\times 25,\ (60,25,10,5)$

Appendix

Table 4: Clique decompositions used to generate the planted-clique instances. Here,

k\times s

denotes

k

planted cliques of size

s

		$q$
$n$	Runs	0.00	0.05	0.15	0.25	0.40
10	150 †	1.731 (0.65)	1.825 (0.74)	2.005 (0.87)	2.189 (1.06)	2.255 (1.03)
		$\pm.105$	$\pm.120$	$\pm.141$	$\pm.173$	$\pm.176$
15	150	1.871 (0.22)	1.960 (0.29)	2.100 (0.43)	2.258 (0.64)	2.575 (1.36)
		$\pm.036$	$\pm.048$	$\pm.069$	$\pm.104$	$\pm.219$
20	150	1.972 (0.18)	2.064 (0.26)	2.253 (0.44)	2.388 (0.65)	2.527 (0.83)

Appendix

Table 5: Ratio of average Pivot cost on

G^{\prime}

to the min-disagreement LP ( Equation 2 ) on the planted-clique instances. Each instance of Table 4 is run with 50 independent seeds (20 for

n=100

). Cells give the mean, the standard deviation in parentheses, and below it the

95\%

confidence interval as

\pm

a margin. † At

n=10

, realisations with LP optimum

0

are omitted, leaving 149, 148 and 133 runs at

q=0.15

0.25

and

0.40

	$q$
Graph	0.05	0.15	0.25	0.40
FB 3980	1.709 (0.030)	1.692 (0.040)	1.693 (0.038)	1.709 (0.048)
	$\pm.011$	$\pm.015$	$\pm.014$	$\pm.018$
FB 698	1.643 (0.025)	1.750 (0.042)	1.839 (0.077)	1.961 (0.128)
	$\pm.009$	$\pm.016$	$\pm.029$	$\pm.048$
FB 414	1.670 (0.013)	1.739 (0.016)	1.801 (0.023)	1.880 (0.030)

Appendix

Table 6: Ratio of average Pivot cost on the subsampled graph to the min-disagreement LP ( Equation 6 ), for Facebook ego-networks under deletion probability

q

. Each cell aggregates 30 independent runs and gives the mean, the standard deviation in parentheses, and below it below it the

95\%

confidence interval as

\pm

a margin

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering
Apr 17, 2026Ibne Farabi Shihab, Sanjeda Akter, Anuj SharmaClustering Approximation Algorithms
Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University
Quality control in sublinear time: a case study via random graphs
Aug 22, 2025Cassandra Marcussen, Ronitt Rubinfeld, Madhu SudanQuery Complexity
School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts, USA. · Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, Massachusetts, USA.
Inductive Correlation Clustering with Graph Neural Networks
Aug 27, 2026Francesco Paolo Nerini, Francesco Bonchi, Arijit Khan +1Clustering Graph Clustering
Sapienza University of Rome, Italy · Intesa Sanpaolo AI Research, Italy · Bowling Green State University, OH, USA

Apr 17, 2026J/K move · Enter open · S save

Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering

Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University

Clustering Approximation Algorithms

Open paper AskPDF arXiv

Chromatic Correlation Clustering (CCC) extends Correlation Clustering by assigning semantic colors to edges and requiring each cluster to receive a single color label. Unlike standard CC, whose LP relaxation has integrality gap 2 on complete graphs and admits a 2.06-approximation, the analogous LP for CCC has a strict lower bound of 2.11, and the best known LP-rounding algorithm achieves 2.15. We explain this gap by isolating the source of difficulty: cross-edge chromatic interference. Neutral edges, whose color does not match the candidate cluster color, create an irreducible cost absent from standard CC and force any color-independent rounding scheme to pay an additional mismatch penalty. We make four contributions. First, we prove a Global Integrality Gap Decomposition Theorem showing that the gap of any color-independent CCC rounding algorithm equals the standard CC gap plus an irreducible chromatic penalty Delta(L) > 0. Second, we solve the associated min-max problem and derive the staircase formula Delta(L) = ((L-1)/L) Delta_infinity, where Delta_infinity is approximately 0.0734. In particular, the two-color gap is 2.0967, separating CCC from standard CC already at L = 2. Third, we introduce Color-Coupled Correlation Clustering (C4). Adding the valid global constraint sum_c x_uv^c >= L-1 and a correlated interval-packing rounding scheme makes neutral edges behave like classical negative edges, recovering the optimal 2.06 approximation and bypassing the 2.11 lower bound for the uncoupled LP. Fourth, experiments on extremal instances, real multi-relational networks, and fairness benchmarks validate the theory: empirical LP gaps follow the predicted staircase, and C4 matches the unconstrained approximation ratio under fairness constraints.

Abstract

Clustering

Explore similar work

Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering

Quality control in sublinear time: a case study via random graphs

Inductive Correlation Clustering with Graph Neural Networks