Towards Better-than-2 Approximation for Constrained Correlation Clustering
Authors: Andreas Kalavas
Evangelos Kipouridis
Nithin Varma
Venue: ICML 2025 spotlightposter (2025)
Keywords: Clustering
Constrained Correlation Clustering
Approximation
Primary area: theory
TL;DR: In this work, we show that in order to obtain a better-than-2 approximation for Constrained Correlation Clustering, solving the (exponentially large) Constrained Cluster LP would be sufficient.

Abstract: In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the sum of the number of edges across different clusters and the number of non-edges within clusters. In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. Constrained Correlation Clustering is APX-Hard, and the best known approximation factor is 3 (van Zuylen et al. [SODA '07]). In this work, we show that in order to obtain a better-than-2 approximation, solving the (exponentially large) Constrained Cluster LP would be sufficient.

[The peer-reviewed version of this article claimed an efficient algorithm for solving the Constrained Cluster LP. An error in the proof, that the authors discovered after the review process, led them to revise the results to be conditional on the existence of a valid LP solution.]

Towards Better-than-2 Approximation for Constrained Correlation Clustering
Andreas Kalavas" 12 Evangelos Kipouridis
Nithin Varma
Abstract
et al.
2009
Chakrabarti et al. 2008), clustering ensem-
bles
Bonchi et al. 2013). community detection (Chen et al.
In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the sum of the number of edges across different clusters and the number of non- edges within clusters. In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandat- ing certain pairs to be in the same cluster and cer- tain pairs to be in different clusters. Constrained Correlation Clustering is APX-Hard, and the best known approximation factor is 3 (van Zuylen el al. [SODA '07)). In this work, we show that in order to obtain a better-than-2 approximation, solving the (exponentially large) Constrained Cluster I.P would be sufficien!!
2012
Veldt et al. 2018). disambiguation tasks (Kalashnikov
ct al.
2008). duplicate detection (Arasu et al.
2009) and
image segmentation (Kim et al. 2011 Yarkony et al. 2012)
Given a complete unweighted undirected graph (V, E E), whose edges are labeled either "plus" or "minus", the Correlation Clustering problem is to output a partition (clustering) C [Ci..... C of the vertex set V. The sets C: of C are called clusters. The objective is to minimize the sum of the number of plus edges across different clusters and the number of minus edges within clusters.
One can view the edges in the input graph as modeling pairwise relationships between entities corresponding the nodes. Specifically, a plus edge denotes the preference of its endpoints to be clustered together and minus edge denotes their preference to be separated. The cost of clustering is then the number of preferences violated by the clustering and the goal of Correlation Clustering translates to finding a clustering that satisfies the preferences of the maximum number of pairs.
1. Introduction
Clustering is a fundamental unsupervised learning task and has many applications in machine learning and data mining. The high-level goal is to partition set of elements into clusters such that similar elements are in the same cluster and dissimilar elements are in different clusters. Over the years, several definitions of clustering have been considered, each with a different objective.
The real-world applications that motivate clustering as above often necessitate incorporating additional hard constraints that result from prior knowledge. In such semi-supervised setting, it is imperative to study the more general problem of constrained clustering. There are several variants of con- strained clustering including, but not limited to constrained k-means (Wagstaff al. 2001), spectral clustering with constraints (Wang & Davidson 2010), constrained rank- ing and clustering (van Zuylen & Williamson 2009), and constrained fuzzy clustering (Pham 2002). Constrained clustering is particularly valuable as it improves the quality of clusters, aligns outcomes with domain-specifee knowl- edge, and reduces sensitivity to noisy data.
Correlation Clustering, proposed by Bansal, Blum, and Chawla (Bansal et al., 2004). is one such clustering for- mulation, which was widely studied since its introduction. The appeal of Correlation Clustering stems from its sim- ple and natural definition and from the absence of require- ment to specify the number of clusters as part of the input. The problem has found success in many applications in- cluding, but not limited to, automated labeling (Agrawal
In this work, we study Constrained Correlation Clustering, variant of Correlation Clustering capturing the idea of crit- ical pairs of nodes, which was first studied by van Zuylen and Williamson (van Zuylen & Williamson, 2009). Con-
'Equal contribution MMax Planck Institute for Informat- ics & Saarland Informatics Campus, Saarbrücken, Germany "Archimedes, Athena Research Center, Athens, Greece UUniversity of Cologne, Germany. Correspondence to: Andreas Kalavas
'The peer-reviewed version of this articlc claimed an efficient algorithm for solving the Constrained Cluster LP. An error in the proof, that the authors discovered after the review process, led them to revise the results to be conditional on the existence of a valid LP solution.
<mathm24008 math. hwwp:///000emaaaaaagaaa....... aegean.gr>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLK 267, 2025. Copyright 2025 by the author(s).

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
strained Correlation Clustering introduces hard constraints in addition to the pairwise preferences, where one could have must-link (requiring nodes to be in the same cluster) or cannot-link (requiring nodes to be separate) constraints. A clustering is valid if it satisfies all hard constraints, and the goal is to find a valid clustering of minimum cost.
signed a deterministic 3-approximation. We note here that algorithms with better-than-3 approximation for Correlation Clustering existed for a long time after the 3-approximation by (van Zuylen & Williamson 2009), but they do not seem to extend to the case of Constrained Correlation Clustering. Due to the significance of the problem, a follow-up work by Fischer, Klausen, Kipouridis and Thorup (Fischer et al., 2024) focused on faster algorithms for Constrained Correla- tion Clustering, even at the expense of worse approximation.
Constrained Correlation Clustering with must-link and cannot-link constraints is well-motivated in both theory and practice. For instance, it has been used to cluster news arti- cles about the same event across different languages (Gael & Zhu 2007). The hard constraints here ensure that news articles about different events from the same language do not end up in the same cluster.
It is worth noting that it is not possible, in general, to handle the must-link constraints by simply merging the nodes in connected components induced by these constraints into supernodes, as such an aggregation results in a weighted instance outside the problem.
1.1. Previous Results
1.2. Related Work
Correlation Clustering was defined by Bansal, Blum, and Chawla (Bansal et al. 2004), who, in addition to prov- ing its NP-Hardness, provided a deterministic constant- factor approximation, the constant being larger than 15,000. Subsequent results improved the approximation guaran- tee by relying LP-rounding techniques: Charikar, Gu- ruswami and Wirth showed that the problem is APX-Hard and also gave a deterministic 4-approximation (Charikar jet al. (000)) Ailon, Charikar and Newman gave a random- ized 2.5-approximation (Ailon et al. 2008]. and Chawla, Makarychev, Schramm and Yaroslavtsev gave determinis- tic 2.66-aprrxxmmttion (Chawla et al. 2015). The last result is nearly optimal among algorithms that round the natural LP formulation, since its integrality gap is at least 2. In a breakthrough result by Cohen-Addad, Lee and Newman, a (1.994 + appprooximtioo using the Sherali-Adan Adams relax- ation broke the 2 barrier (Cohen-Addad et al. 2022). The approximation guarantee was later improved to 1.73 + (Cohen-Addad et al. 2023) by Cohen-Addad, Lee, Li and Newman, and even to 1.437 by (Cao et al. 2024a)). There is also a combinatorial 1 1847-approximatioo by (Cohen- Addad et al.) 2024b) for the problem. The current-state of the art is an adaptation of the 1.437 approximation that runs in linear (Cao et al. 2025b), and even sublinear (Cao et al.]
Closely related to the problems considered by us are hi- erarchical clustering problems under similar constrained settings. In particular, for each pair {u, 0} we are given an upper and lower bound regarding the distance of and in the output (Farach, Kannan, and Warnow (Farach et al., 1995).. Ailon and Charikar, in (Ailon & Charikar 2011). make progress on constrained hierarchical clustering, but op- timal algorithms are still elusive. We note that Constrained Correlation Clustering is a special case of constrained hier- archical clustering (where the hierarchy is trivial).
1.3. Our Contribution and Techniques
Our main result is a proof that, to achieve a better-than-2 approximation for Constrained Correlation Clustering, suffices to design efficient solution to the Constrained Cluster LP (Figure IT.
Theorem 1.1 (Informal). If there exists polynomial-tie algorithm to solve the Constrained Cluster I.P, then there exists a potynomial time algorithm for Constrained Corre- lation Clustering whose spproximation is 1.92.
Once again, we note that we do not claim a solution to the Constrained Cluster LP. We consider plausible because the corresponding unconstrained Cluster LP has been solved in polynomial (Cao al. 2024a), linear (Cao al. 2025b). and even sublinear time (Cao et al. 2025a).
2025a) time.
Correlation Clustering has also been studied in different settings such as dynamic algorithms -lohen-Addad et al.
2024a) parameterized algorithms (Fomin et al. 2014). sub-
linear and streaming algorithms (Assadi & Wang
2022
There are two main techniques for (unconstrained) Cor- relation Clustering to achieve a better-than-2 approxima- tion. One (Cao et al. 2024a) is based on the Cluster IP, an LP stronger than the natural one while the other (Cohen- Addad et al. 2024b) is based on a local search technique.
Cambus et al.] 2024; Behnezhad et al. 2022: 2023 Cam
bus et al. 2024, Makarychev & Chakrabarty 2023), mas-
sively parallel computation (MPC) algorithms (Cohen-
Addad al. 2021 Cao et al. 2024b), and differentially
private algorithms (Bun et al. 2021).
The problem in extending the LP based approach is that, even given valid solution to the Constrained Cluster LP,
Regarding Constrained Correlation Clustering, the state-of- the-art approximation is given in the work of van Zuylen and Williamson (van Zuylen& & Williamson, 2009) who de-
IIn fact it has exponential size, but one can, in polynomial time, compute a (1 + s) approximate solution of polynomial size.
2

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
its rounding involves creating clusters based on independent sampling of nodes (based some probability distributions dictated by the LP solution). However, when hard con- straints are enforced, we can no longer use independent sampling since, for example, placing a node u in a cluster implics that all nodes with a cannot-link constraint with u cannot be in the same cluster.
straightforward approach would be to first round the frac- tional clustering, obtain clustering C that is close to opti- mal, and then mix the two solutions and C. The problem with this approach is that it would normally only show that we can get a better clustering than C, not better than the optimal, which is no longer a contradiction.
Still, we show that there exists one particular way to round the fractional clustering, so that the mixing is guaranteed to be below the optimal, not just C. In fact, this particular rounding simply samples clusters with probabilities propor- tional to the values of the LP solution. Its properties were analysed already in (Cao et al. 2024a), as one part of their overall algorithm.
The local-search approach, on the other hand, is based on a simple principle: if we have clustering whose cost is more than 2 times the optimal cost, there exists a cluster in the optimal solution that we can "force" into our clustering [ and get a clustering with smaller cost. The proof is based on a simple counting argument, and the technique would directly lend itself to a 2 approximation, if we could spend exponen- tial time find such a cluster. The novelty of (Cohen-Addad et al. 2024b) is that they manage to (nearly) simulate this in polynomial time, and their approximation is 2 + E. As one would expect, achieving this is the most technically challenging part of their paper. It is possible that these tech- niques could be extended to the Constrained Correlation Clustering setting, but even if true, the resulting algorithm and analysis would be highly non-trivial.
Finally, we note that in our case we can algorithmically compute and use C, given access to the fractional optimal (unlike in (Cohen-Addar et al., (024b) where they do not have access to the optimal clustering, and therefore C is only part of the analysis).
1.4. Organization
The rest of the paper has the following structure. In Sec- tion 2 we formally define the problem, and give some basic notation. In Section 3 we describe the LP that models Constrained Correlation Clustering. Finally, in Section we give a full analysis for our main algorithm and how achieves its approximation factor of (1.92+e)
Instead, in this work. we propose a simple approach for Con- strained Correlation Clustering that combines the strengths of both aforementioned techniques.
Perhaps the most critical observation in our paper is that even though we do not have access to the optimal clustering, an optimal fractional clustering (that is, a solution to the LP) would suffice to guide the local search, and thus bypass the need for the heavy machinery introduced in (Cohen- Addad et al., 2024b). In particular, one could embed the hard constraints in the LP, and guarantee that the output of the local search is a valid clustering.
2. Preliminaries
The graphs (V,E+ E A E-) we consider in this paper are complete, unweighted, undirected, and every edge is labeled plus or minus (it belongs to one of E+ or E respectively). We typically set n = [V]. Let (2) denote the set of all size- subsets of a set A. We often abbreviate the (unordered) set { u, by uv. Before introducing our problem, we first define the cost of clustering:
Despite the success of using the optimal fractional cluster- ing to get 2-approximation, does not come without its own shortcomings. In particular, the problem occurs when trying to break the 2 barrier. In (Cohen-Addad et al.) 2024b), they show that normally the output of the local search is already a tetter-than-2 approximation, except for some very specific cases. Then, they run a second local search, which incentivised to give very different solution than the first (thus, intuitively, avoiding the specific bad cases). To argue that one of the two solutions achieves better-than-2 approx- imation, they show that if both approximations were at least 2, then it would be possible to "mix" 3 different clusterings (the two solutions and the optimal one) in order to obtain a clustering that is better than optimal (a contradiction).
Definition 2.1. Let E+ (C) and & (C) be the sets of plus and minus edges that are not satisfied in a clustering C. That
is E (C) = { uw E E+ 1C E C with (u.v) C C) } and E (C) = wv E 3C e C with {u,0] v) C C). The
cost of C is defined cost(C) = |8 + (C) + (C)).
We now formally define Constrained Correlation Clustering.
Definition 2.2 (Constrained Correlation Clustering). Given an instance (V, E+ l E F,, H),, where (V, E e E-) is an edge-labeled graph, C (K) is a set of friendly pairs, and H C (K) is a set of hostile pairs, compute minimum cost clustering C = [C,.... C2 } of V such that no pair wv E F has u, e in different clusters and no pair ue E H has u, e in the same cluster.
In our case however, is not even clear what mixing two clusterings and a fractional clustering would mean. A
$ More formally, given a clustering { (C1, C2,..., Cx and a cluster C, the new clustering is {C, C1 (C,, CC Ck C...
3

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
3. LP with constraints
From this point on, we always assume that we have access particular solution to the L., with the properties described in Assumption 3.1
In this section, we describe the linear program used to model the problem. We will use its solution to guide the local searches for the algorithm later.
4. Local Search Algorithm
Given an instance (V, Et t E F. H) of Constrained Cor- relation Clustering, we can define the following linear pro- gram, which we call the Constrained Cluster LP. It has two types of variables: Tue for every uu E (2) and 2c for every C S V. The variable Jun describes the desirability of nodes and to be in different clusters (one can view it as a dis- tance between the two nodes) and the variable ac captures the probability of cluster C' to be in the final clustering.
In this section, we describe our algorithm and give a full proof for its approximation factor.
At high level, the algorithm solves the Constrained Cluster LP (Assumption 3.1 whose solution we view as a (frac- tional) optimal clustering we then perform a simple lo- cal search procedure (guided by this optimal) that gives a 2-approximation. In fact, this solution already gives a better- than-2 approximation, unless some really specific conditions occur. It turns out that suffices to run local search once again, but this time we discourage the new clustering from looking similar the previous one (by adding a penalty in the objective function, when the two clusterings are similar).
[
Figure I. Constrained Cluster LP.
min
Σ
Luv +
Σ
(1- - Tun)
E
W F
In (Cohen-Addad et al. 2024b), they prove that one of the two clusterings gives a better-than-2 approximation as follows: assuming this is not true, they show how to obtain new clustering that has approximation better than the optimal (a contradiction). To obtain this clustering, they "mix" the optimal with the two local search solutions. We perform the same steps, but in our case we can actually perform these steps as part of the algorithm, not just in the analysis, exactly because in our case we assume we have obtained a (fractional) optimal solution.
s.t.
Σ 2s 1
Vu V,
Szu
28 1 - Fuv
Vuu (2)
(2(u,))
20 0
AS C V + 0,
Zuv = 0
Vuu E F,
Lu = 1
Yuu E H
4.1. Local Search Algorithm
The Esau 2q constraints ensure that all vertices belong to some cluster in the final clustering. The Es> (s.2)..) Es 1 1- 1-xu constraints state that the closeness of two nodes is proportional to the total weight of clusters containing both of them. Finally, the Zue = 0 and Zuv = 1 constraints model the hard constraints of the instance. We note that without the last two types of constraints, the above LP is identical to the Cluster I.P for (unconstrained) Correlation Clustering, solved in (Cao et al., 2024a 2025b a).
We first define an operation (which we call local move) that transforms a clustering C. Intuitively, the operation takes a new cluster C' and swaps in the clustering; the resulting clustering is defined as Cc {S \ C: : S E C) U (C). We call local move legal, if the cluster C' that we introduce to the clustering C does not violate any constraints in F or H. In other words, C does not contain both endpoints of a hostile edge nor does it contain only one endpoint of a friendly edge.
Assumption 3.1. Let OPT be the value of the optimal solution for a Constrained Correlation Clustering instance (V, E E F, H).. We assume that for any constants 0, 0 there exists algorithm that runs in time poly(1//e and with probability 1 1-n -x returns solution to the Constrained Cluster LP such that:
Lemma 4.1. Starting from a feasible clustering C, applying any number of legal local moves results in a clustering that does not violate any constraints in F or H.
Proof. We consider a single legal local move, as by induc- tion on the number of legal local moves we directly get the lemma.
its value is at most (1 + =)OPT.
it has at most poly(n, !) subsets S with 25 > 0,
For a friendly pair be violated, there must exist cluster containing exactly one of its endpoints. By the definition of legal move, this cannot happen in the introduced cluster
for every uv E F there is no subset S with zz >> 0 and I { u, = 1,
for every wv E H there is no subset S with 2g > and 2 { (u, 0,
'From this point on, we refer to solution to the Constrained Cluster LP as a fractional clustering.
4

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
C. (which either contains both or none of the endpoints). Additionally, this cannot happen in other clusters well; if it did, then the other endpoint would be in C, which we already proved cannot happen. Similarly, for a hostile pair to be violated, the two endpoints must end up in the same cluster. The only cluster that can contain nodes that were in different clusters in C is cluster C, which by definition does not contain both endpoints of a hostile pairs.
Lemma 4.4. Let L be as in Algorithm 7 Then,
cost(C) - 2LP 2LP-LP -P LP--
E
Luvs
(OVEE-L))E-CC
where LP denotes the value of the fractional LP solution.
Proof. Let C. be a cluster such that 2ç 0 in the LP so- lution returned (C' E M). Recall that, Le denotes the clustering obtained by applying a local move with cluster C on clustering L. This local move can affect an edge (i.e. make it satisfied or unsatisfied) only if the edge has at least one endpoint in cluster C' (if not, then the endpoints of the edge do not change cluster, which means that they remain as they are satisfied or unsatisfied). We say that these edges are covered by C. By the local optimality of L, we have cost(C) cost(Cc). Informally, this means that after swapping cluster C' in, more edges covered by C are unsatisfied than before. Let C++ denote the set of plus-edges that have exactly one endpoint in C. Similarly, let C denote the set of minus edges that have both end- points in C. The set C+ UC- is the set of edges unsat- isfied by the cluster C. Next, let & (C) S 3. (C) be the set of plus edges we E EC) that covered by C, i.e., Ku, o) n C1 > 1. Let (C) S (C) be the set of minus edges uv E EC) such that Ku, naI 2 1. From the above discussion, for each cluster C with 2c > O, we have, |C+ |C-| 2 (C) + 235 (C)) This further implies that
Observation 4.2. We note that it is direct algorithmi- cally obtain a feasible clustering C, by creating cluster for each connected component of (V, F). Informally, this gives minimal clusters satisfying F. If any hard constraint in H was not satisfied, then the instance itself would be infeasible (two nodes are forced to be together, by F, and to be separated, by H).
We now define the local search procedure. Let M be the collection of clusters C' with 2c > 0 in the LP solution. By Assumption 3.1 there are poly(n, 2) clusters in M. Furthermore, they do not violate the hard constraints, and can thus be used for legal local moves.
Algorithm 1: Local Search
LECALSEARCH()
+ arbitrary feasible clustering
while 3C E M such that cost(Lc) < cost(L) do L CC
return L
Σ =c . (1C*|+
Σ =c (1E +1)
The running time of Algorithm is polynomial, as [M poly 1) and the cost can take only non non-negative integer values bounded by (2)-
We simplify the left-hand side of the above inequality by separately accounting for the contributions of plus and mi- nus edges to the summation. The contribution of a plus- edge ue to the left-hand side of the above sum simply Eo:l(ueencc==1 2C. Recall, from the LP in Figure 1 that Ecwec 2C Ec.vec =C
4.2. Analysis of Local Search: 2-approximation
Recall that we view the LP solution as fractional clustering. Here, we introduce notation to separately capture the cost incurred by plus edges that go across clusters and the cost incurred by minus edges within clusters.
and Ec. =C Inv. From this, it follows that Ec: [c:((u.))C))) 2c = 2. Similarly, one can see that the contribution of minus- edge we to the left-hand side of the sum 1 wwe- Summing over the plus and minus edges separately,
Definition 4.3. Let LP+ and LP denote the costs of the plus and minus edges incurred by the fractional clustering given by the I.P solution. That is LP =I -EwEB Tue and LP EuvEE-
Σ 20 -e--((t1 + (CT = 2LP +LP 2LP LP-
J.
We slightly abuse notation and use LP to refer both to the linear program, and the cost of its acquired solution (LP = LP+ L
We similarly transform the right-hand side Ee 2c (C)) + (C)) of the above inequality. Each plus edge we that contributes to Ec =c (1Et(2) (E) belongs to 8 (C().. A plus edge in (C(() contributes an amount of 20 to the sum if either u or u is contained in C. Thus, its total contribution is Σcien(u. &C. which is equal to + Fue- Using a similar argument, the contribution
We say clustering C' is a-approximate if cost(C) < aLP. We first show that L is 2-approximate. In fact, we prove something even stronger, that we later use to get an algo- rithm that is better than 2-approximate.
5

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
of minus edge ue in & (4)) the sum also be seen
Following from the above, if L. is not (2 8) approximmate then its cost is dominated by the plus edges. The idea here is that we try to run a local search that produces clustering that looks very different from L (and thus ideally does not satisfy the aforementioned conditions). To do that, we simply penalize the plus edges paid by L the cost note that this part is exactly as function (Algorithm 2 2024b).
be 1 + Tue- Thus, the summation simplifies to
Σ 20 (((((()))))((( = c
Σ
Eue-
WHET (C)UE" (4)
Substituting these rewritten terms in the inequality, get the desired statement.
in Cohen-Addad
Definition 4.7. For a clustering the new cost function is:
The last lemma directly gives approximation ratio of 2, which we reduce further on. Corollary 4.5. Let L be in Algorithm 7 Then,
cost (C) cost(C) (C)
Algorithm 2: Local Search with penalties
cost(4) < 2LP LP-
Σ
Fuv
(C')
W (C)
return cost((") + (E+( (E+()))))))))
cCst(C) - (EE
Σ
LOCALSEARCUU-TTIHPPPAANT
Eav
L C LOCALSEARCHO)
WVEE+(() (C)
L' <- arbitrary feasible clustering
while EC E M such that costz co')
Proof. The first inequality is just Lemma 4.4 with the term E Ewves- (C) Tuv dropped. The second inequality starts
do
L C' - C'c
from Lemma 4.4 and uses the fact that:
7
8
return L
LP
Σ
(1
Tuo + Fun)
NIEE-
UUEE (PEE-(C) (C)
Working exactly as for Corollary 4.6 but using cost in- stead of cost, we get similar conditions for when L' is not better than 2-approximate:
where the right-hand side is equal to (C).
4.3. Local Search with Penalties
Lemma 4.8. If L' is not (2 8) apprroxiieete, then:
2 For the rest of the proof, it is instructive to Let 8 = 25 think about 8 as very small constant.
Directly from Corollary 4.5 we observe that either C is already better than 2-approximate, or some very particular conditions happen:
18 (c')++
Σ
Iuo + (
(WE)
öLP +2
Fuv
uVEE+(C)
Regarding minus-edges, the cost of both L. and the LP is negligible.
Proof. Proved in Appendix A
Regarding plus-edges paid by L, the corresponding cost of the LP is negligible.
Directly by Corollary 4.6 and Lemma 4.8 we note that if
neither L nor L' are - -2- -0apppoxximmtee, then the following
We formalize this intuition in the following corollary. Corollary 4.6. If L is not (2 8) -)ppproxiee then:
conditions occur:
Regarding minus edges, the cost of LP, the cost of L, and the cost of L' are all negligible.
LP + Σ
Fav < 8LP,
(C)
Regarding plus edges, not too many of them can con- tribute to both L and L', and, moreover, the ones that contribute to L. or L cannot contribute much to the cost of the LP.
3 (C) +
Σ
Tav < 8LP
(C)
Proof. Immediately from Corollary 4.5
The following corollary formalizes the above.
6

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
Corollary 4.9. nneitherr L and L' are (2 - (2-8)-auproanee -aprroximate,
cluster containing only one of them, conditioned the fact that select cluster containing least of them. This is
then:
Σ Linnt w. 11-1
Esau.8au Sst
By the LP in Figure 1 we have Essu 28 1 and LSa0, 28 3 S3w Es2(u.u) 2s = =1 -1 Tuw) = Daw, which
LP +18 (f')
- jsnt 121 #8
Esy #8t2
Σ
Σ
Luo + (18
Tue
W
(C)
(VE)((2")
proves the claim.
46LP.
Corollary 4.11. It holds that
Proof. Follows from the inequalities of Corollary 4.6 and Lemma
+
LP-+2
Σ
Tue +
Σ
Buw
4.4. Final Algorithm and Analysis
WPEE (C)
WCEE+(C)
The structure of the rest of the proof in Addad et al. 2024b) as follows: assuming that none among L, L' are (2 - -approoxx,, the authors construct a clustering that better than 1-approximate contradiction). To construct this clustering, they propose way to "mix" (in the anal- ysis) f. L', and the optimal clustering. For this to work in our case, we are required to use the fractional optimal clustering. This is so because the guarantees for our two clusterings C, L' are with respect to the fractional optimal instead of the actual optimal, as was done in the paper that introduced the local search approach for Correlation Clus- tering (Cohen-Addee procedure cannot be straightforwardly extended to fractional clusterings. Instead, we first round the fractional clustering C to an integral one, whose properties are crucially very close to that of C*
where the expectation is over the randommess of Algo-
rithm 3
Proof. Notice that for a minus edge uc, LP pays 1 - Favs while the expected cost of I is 1
20 1++r
1 (1
Fuo) S 1 Tun- Similarly, for the other two inequalities: for a plus edge uv the cost LP solution is Zao while the expected cost of I is 2
2x
1+
Corollary 4.12. For any constants e > 0, 0, we can run Algorithum such that
3 for Ollogn) times, get clustering I
al. (2024b). However, the mixing
18
(1P +2
Σ
Fao +
Σ
Foe)
BUEE (C)
WUEE (C')
This rounding (see (Cao et al. 2024a)) gives a 2- approximate clustering that samples clusters from M.
with probability at least n
Proof. By Markov Inequality and Corollary 4.11 we have probability at most 1/(1 + = I+s Itc to get clustering I that does not satisfy the claim execution of Algorithm
Algorithm 3: Simple sampling-base 2-approximation
particular Therefore the probability of
SAMPLING()
I+0,S++ while S + 1 do
failure in 1+s cln repetitions is S -eluun =
Sample cluster C' with probability
Finally, we show that I is clustering satisfying the hard constraints.
proportional to 2c I-IU(Cns] S
Lemma 4.13. Clustering I returned by Algorithm 3 fies all hard constraints.
satis-
return
Proof. By Assumption 3.1 if an endpoint of a friendly pair wv E F contained in a cluster C with 2c > O, then the other endpoint will also be contained in that cluster. Thus, a sampled cluster will always have both endpoints of friendly pair. This means that endpoints of friendly pairs are removed from S simultaneously. Therefore, when introducing C' S, it either contains both u and or neither of them. Analogously, by Assumption 3.J endpoints of hostile pairs are never in the same cluster with &c > O. Hence, they cannot end up in the same cluster in clustering I.
Algorithm 3 cen trivially run in polynomial time by avoiding sampling clusters C' with C c = 0. Proving that it is a 2-approximation follows directly from Lemma 4.10
Lemma 4.10 (Generalization of Lemma 6 of (Cao et al. 2024al). For every wo E (2) the probability that u, v are separated in I returned by Algorithm 3 is I-22xs
25nv
Proof. Directly from the algorithm, the probability that u, v are separated is equal to the probability that we select
7

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
We now ready show that if Algorithms I [and return
If P pays for minus edge, then least one of L, L'
clusterings that not (2 approxxiimee, then create new clustering that is 24d-approximate, which is better-than-2 approximate clustering for our setting of 6.
and I pays for this edge.
If P pays for plus edge, then at least two of L, C' and I pays for this edge.
To do that, we first observe that if neither L nor L' are (2 - appproxxiet,,, then the following conditions occur:
Therefore, by Corollary 4.14 the total cost of small,
Regarding minus edges, the cost of I, the cost of L, and the cost of L' are all negligible.
We now describe how construct P (Algorithm First, assign to each node label (X, Y, Z), such that belongs to clusters X E L, Y. E L', and Z E Z.
Regarding plus edges, most of them only contribute to the cost of at most one among L, I.
Definition 4.15. An equivalence class QXYz the set of all nodes that have label equal to (X,Y, 2) Z)
This is similar to Corollary 4.9 and uses the fact that by Corollary 4. clusttrng behaves very similar to the I.P. Corollary 4.14, For any constants c > 0, > 0, if neither of C and L' are (2 8) apprroxxieee, and we obtain I by using Corollary 4.12 then with probability at least n
The construction of the new clustering P is shown Algo- rithm
Algorithm 4: Pivoting Procedure
PIVOT(C, L')
Obtain I by Corollary 4.12
Assign labels (X, 2 nodes E V
V' +- V.P
(I) (())))((())))((+)))(())+)) (()++ (C)) < OLL
while V * do do
S f an arbitrary equivalence class QXYZ with all its nodes in V and maximum cardinality *+Su {u V the label of u differs in exactly one label variable from XX,Y P - PU (C), V + V
Proof. Beginning from the left hand side and using Corol- 7 lary 4.12 we get that with probability at least
return P
18 (00))
< (=72001())--((1000()))++11000000
Lemma 4.16. For any constants > 0, >> 0, if neither and L' are (2 - 8)-approximate, then P is (24 + 3=) approximate with probability at least 1
(I (1+ +2
Σ
Luv + 2-
Σ
Iwe)
(CE
(C))+(CC)
Proof. Notice that directly from the algorithm, if two nodes are in the same equivalence class, then they end up in the same cluster of P; therefore P does not pay for plus edges with endpoints in the same equivalence class (that is, end- points that do not differ in any label variable). Furthermore, if u, are in the same cluster in P, it is because they share at least two label variables with some equivalence class QXYZ z. Therefore, by pigeonhole principle, u, share at least one label variable, meaning that P does not pay for minus edges with their endpoints differing in all label variables.
Now, we further manipulate the right hand side, by factoring out the constants:
[C)(2) 18 (8 (C') + +(+)))++())))
(1 (1P +2. Σ
Fun +
E
Fao)
unEEl (C)
weEE! (C")
< <2(1+s)
Σ
Luv
Σ
Duot
(CE
(CE
We conclude that there are 3 categories of edges that we contribute towards the cost of P:
By Corollary 4.9 this is less than (8)8L) which proves the claim by scaling e.
1. minus edges whose endpoints differ in at most two label variables.
We will now use clusterings C, L' and I to create a new clustering P such that:
plus edges whose endpoints differ in exactly one label variable.
8

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
3. plus edges whose endpoints differ in at least two label variables.
Algorithm 5: Main Algorithm
L + LOCALSEARCHIO
L <- LOCALSEARCH-WITTIIEEE
In Case 1, minus edges are bounded by Corollary 4.14 as
3 P + PIVOT((C,
at least one of the clusterings L, L' and I pay for them
4 C < arg (CC.) cost(S)
(at least one variable in the labels of their endpoints is the same, meaning that there is a cluster in one of L. L or I that contains both). Similarly, in Case 3. plus edges are also bounded by Corollary 4.14 as least two of the clusterings L. L' and I pay for them (at least two variables in the labels of their endpoints are different, therefore they are in different clusters in at least two of the clusterings).
5 return C
Furthermore, with probability 1 n-n we successfully solve
the LP in Figure I (Assumption 3.1 and get that either
min cost(C), cost [C} < 1.92LP cost(P) - (1.92 + e) (by Lemma 4.16 and 8 = 25 ). As LP S (1 + O)PT
For every edge uu in Case 2, we show that it can be charged to some edge of the previous cases, and each edge from the previous cases charged by at most two edges of Case 2.
(Assumption 3.1 Algorithm 5 satisfies the claim by scaling e.
This results in cost 3 (8 + =)8LP. by Corollary 4.14
5. Concluding Remarks
Consider an iteration of Algorithm 4 that creates cluster C' in P by selecting an equivalence class 5 = QXY 2- For a plus edge wv in Case 2 that we pay for, it must be that one of its endpoints differs in one label variable from (X, Y, Z) (therefore it in C), and the other differs in two (so that it not in C, because we pay for un, but still only differs in one label variable from u). W.l.o.g. assume V E Q and QXY'Z
In this paper, we present a better-than-2 approximation algo- rithm for Constrained Correlation Clustering, conditioned on efficient solution to the Constrained Cluster LP. We obtain our algorithm by combining the assumed Cluster LP solution with a local search technique. Our algorithm is conceptually simpler to analyze and gives a better-than-2 approximation for the special case of Correlation Clustering,
E QXYZ' meaning that can be associated with at most 1Qxr +|xxx edges in Case 2 that we pay for.
The main open direction is to determine whether there exists an efficient solution for the Constrained Cluster LP. It would also be interesting to explore whether our approach of com- bining the LP and local search has broader applications. An- other open direction is with respect to the inapproximability of Constrained Correlation Clustering. Finally, it intrigu- ing to know whether inapproximability results stronger than the ones directly implied by those for Correlation Clustering exist for the constrained setting.
By maximality of S we have Qxy' S S, and therefore we can find an injective function f : QxY'z + S. If { {v, f(u) } is a plus edge, then it is a Case 3 edge and if {u, (()) } is minus edge, then it is a Case edge. Simi- larly for QXYZ' which proves our claim.
Lemma 4.17. P does not violate any hard constraints.
Proof. A friendly pair wo will be in the same cluster in all 3 clusterings L, L' I (as they are feasible clusterings), thus u and v will be in the same equivalence class Q By the construction of P. all nodes of an equivalence class end up in the same cluster. Similarly, a hostile pair ue will have its endpoints and in different clusters all 3 clusterings C. f', I, which means that their labels will differ in all three variables. Again, by construction, no two nodes that differ in all the label variables end up in the same group in P. D
Acknowledgments. We thank Vincent Cohen-Addad and David Rasmussen Lolck for helpful discussions. We also thank the anonymous reviewers for their feedback that sig- nificantly improved the presentation of our paper.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Our final algorithm returns the best out of all clusterings.
Theorem 4.18. Under Assumption 3.1 for any constants e > 0, > O, there exists a polynomial time algorithm for Constrained Correlation Clustering whose approximation factor is (1.92 + E) with probability 1 1-n"" =
References
Agrawal, R., Halverson, A., Kenthapadi, K., Mishra, N., and Tsaparas, P. Generating labels from clicks. In Baeza- Baeza-Yates, R., Boldi, P., Ribeiro- Neto, B. A., and Cambazoglu, B. B. (eds.). Proceedings of the Sec- ond International Conference on Web Search and Web
Proof. L, L' and P all satisfy the hard constraints (Lem- mas 4.1 4.17p and can be computed in polynomial time.

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
Data Mining, WSDM 2009, Barcelona, Spain, Febru- ary 9-11, 2009, pp. 172-181. ACM, 2009. doi: 10.
10. 1.97816119775544CHH33. URL htttp::///ooi.... /ttp://oo..oooo
.ch33
(145/14987591149888 URL
Bonchi, F., Gionis, A., and Ukkonen, A. Overlapping correlation clustering. Knowl. Inf. Syst., 35(1):1-32. 2013. doi: 10.
Ailon, N. and Charikar, M. Fitting tree metrics: Hierarchical clustering and phylogeny. SIAM J. Comput., 40(5): 275- 1291, 2011. doi: 10.1137/100006888. URL hps
URL https
7/doi. orddi.org/0..o 1007/ 001000//1111111 012-
Announced at
Bun, M., Eliás, M., and Kulkarni, J. Differentially pri- vate correlation clustering. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Con- ference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Ma-
05.
Ailon, N., Charikar, M., and Newman, A. Aggre- gating inconsistent information: Ranking and cluster- ing. J. ACM. 55(5):23:1-33:27 2008. doi: 10. 1145/1411509.1411555 URL httpp://dot......... org/
chine Learning Research, pp. 1136-1 146. PMLR, 2021. URL httt:://ccrcceeingg , www. press/v139/
10. D0..145/1441559..0 2005.
Announced in STOC
bun2 1a a html
Cambus, M., Kuhn, F., Lindy, E., Pai, S., and Uitto, J. A (3 + apppproxmmate correlation clustering algorithm in dynamic streams. In Woodruff, D. P. (ed.), Pro- ceedings of the 2024 ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2024, Alexandria, VA, USA, SIAM, 2024. doi: URL https:://oo/ org/10.1137 /ttp://.999111111
Arasu, A., Ré, C., and Suciu, D. Large-scale deduplication with constraints using dedupalog. In Ioannidis, Y. E., Lee, D. L., and Ng, R. T. (eds.), Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 April 2 2009, Shanghai, China, pp. 952-963. IEEE Computer Society, 2009. doi: 10. 1109/CCD..2009443 URL #109/CCD..2099..
January 7-10, 2024, pp. 2861-228882222 -2800.
0011133/19781111197797
Cao, N., Cohen-Addad, V., Lee, E., Li, S., Newman, A., and Vogl, I.. Understanding the cluster linear program for correlation clustering, In Mohar, B., Shinkar, I., and O' D'Doneell, R. (eds.), Proceedings of the 56th Annual ACM Symposium on Theory of Com- puting, STOC 2024, Vancouver, BC, Canada, June 24- 28, 2024, pp. 1605-1616. ACM, 2024a. doi: 10. 11 1145/361826003649744 URL https:://oo..oo 10. 09.1145/3618255 3649749
Assadi, S. and Wang. C. Sublinear time and space al- gorithms for correlation clustering via sparse-dense de- compositions. In Braverman, M. (ed.), 13th Innova- tions in Theoretical Computer Science Conference, ITCS 2022, January 31- -eebuuar 3, 2022, Berkeley, CA, USA, volume 215 of LIPlcs, pp. 10:1-10:20. Schloss Dagstuhl- - Leibniz-Zentrum für Informatik, 2022. doi: 10.4230/LPICC..TCS..00
URL httpps//doo: org/10 /00./1...0 4000.2220/1PPPPP ITC.S 2T1.:I22..TTS.2222111111 2022.10
Bansal, N., Blum, A., and Chawla, S. Corre- lation clustering. Mach. Learn., 56(1-3):89-113, 2004. doi: 00.02//..AAHH.000331166553
Cao, N., Huang, S., and Su, H. Breaking 3-factor ap- proximation for correlation clustering in polylogarith- mie rounds. In Woodruff, D. P. (ed.), Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algo- rithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pp. 9781611977912.1433 URL https: / /oo. www.ioooo...... 0rg/10 1137 911.11997811119977
95. URL htt.tts::/....rg////// 1ttp.//0/////111102//////0. 00000331 6.55574..5.
SIAM, 2024b. doi: 10.1137/1.
Behnezhad, S., Charikar, M., Ma, W., and Tan, I.. Al- most 3-approximate correlation clustering in constant rounds. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, Oc- tober 31- November 3, 2022, pp. 720-731. IEEE, 2022. doi: 00.11009FFOCS5444522222000 20040 URL ht 202222224444222444 000 00074
143
Cao, N., Cohen-Addad, V., Li, S., Lee, E., Lolck, D. R.,
Newman, A., Thorup. M., Vogl, L., Yan, S., and Zhang, H. Solving the correlation cluster LP in sublinear time.
CoRR, abs/2503. 250/22203.2888,,,.. 2025a. doi: 10.48550/ARXIV. 2503.20888 https:ttts:/// /wt./iiiioo/// http://::///iii.o//.00....0 a arXiv TrXiv.2503.0 20803.0.883.
Behnezhad, S., Charikar, M., Ma, W., and Tan, L. Single- pass streaming algorithms for correlation clustering. In Bansal, N. and Nagarajan, V. (eds.), Proceedings of the 2023 ACM-SIAM Symposium on Discrete Al- gorithuns, SODA 2023. Florence, Italy, January 22- 25, 2023, pp. 819 849. SIAM, 2023. doi: 10.1137/
Cao, N., Cohen-Addad, V., Li, S., Lee, E., Lolck, D. R., Newman, A., Thorup, M., Vogl, L., Yan, S., and Zhang, H. Solving the correlation cluster Ip in nearly linear time. 2025b. Accepted at STOC 2025 (not published yet).
10

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
Chakrabarti, D., Kumar, R., and Punera, K. A graph- theoretic approach webpage segmentation. In Huai, J., Chen, R., Hon, H., Liu, Y., Ma, W. Tomkins, A., and Zhang, X. (eds.), Proceedings of the 17th Inter- national Conference on World Wide Web, WWW 2008, Beijing, China, April 21-25, 2008, pp. 377-386. ACM, 2008. doi: 10.1 14411446774997736775444 URL https: //doi.org/11 Ttt../...111111177..1
approximation for correlation clustering. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, PP. 1082-1 1004. IEEE, 2023, doi: 10.1109/F0C555990. 2023.00065. URI
FOCS57990 2023300.22...0 00065
Cohen-Addad, V., Lattanzi, S., Maggiori, A., and Parot- sidis, N. Dynamic correlation clustering in sublinear update time. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024a. URL https 7 woopeneevew.nntt.. 3 3YG55LLbG
Charikar, M., Guruswami, V., and Wirth, A. Clus- tering with qualitarive information. J. Comput. Syst. Sci., 71(3):360- 383, 2005. doi: 10.1016/1.jsss.0004 2004.1.. 012. URL WwR.tttpss. https: stttps://doi... http////oo..rg.l.///// 100 1016/j. jcss 2004. 11.1111111 012
Announced in FOCS 2003.
Cohen-Addad, V., Lolck, D. R., Pilipczuk, M., Thorup, M., Yan, S., and Zhang, H. Combinatorial correlation clustering. In Mohar, B., Shinkar, I., and O' Donnell, R. (eds.), Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24- 2024, pp. 1617-1628. ACM, 2024b. doi: 10. 10..1145/366 02..22263333977 org /C. 1ew.i1115//3 3618260.66.. 3649712
Chawla, S., Makarychev, K., Schramm, T., and Yaroslavt- sev, G. Near optimal LP rounding algorithm for cor- relation clustering on complete and complete k-partite graphs. In Servedio, R. A. and Rubinfeld, R. (eds.), Proceedings of the Forty-Seventh Annual ACM on Sym- posium on Theory of Computing, STOC 2015, Port- land, OR, USA, June 14-17, 2015, pp. 219-228. ACM, URL https: 0TA1446666...746644
httt.htts::////. //oii
2015. doi: 10. 10.114452746639927466600 //doi.org/// 10.
Farach, M., Kannan, S., and Warnow, T. J. A robust model for finding optimal evolutionary trees. Algorithmica, 13 (1/2):155-179) 1995. Announced at STOC 1993.
Chen, Y., Sanghavi, S., and Xu, H. Clustering sparse graphs. In Bartlett, P. L., Pereira, F. C. N., Burges, C. C., Bottou, L.,, and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pp. 2213- 2221, 2012.
Fischer, N., Klausen, J., Kipouridis, E., and Thorup, M. A faster algorithm for constrained correlation clustering. CoRR, abs/2501. 100114,, 2024. doi: 10.48550/ARXIV. 2501.03154. URL http:::tt///oo //doii////oo///// wtt//0/10000. 48550/ SzXiv.250.. 03154
To appear at STACS 2025.
URL https:://rrceeddig
neur /c/ http:/sccccaapppe///////aaaa/ (06e0000220050355776662226663333
Fomin, F. V., Kratsch, S., Pilipczuk, M., Pilipczuk, M., and Villanger, Y. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. J. Comput. Syst. Sci., 80(7): 1430) 1447, 2014. doi: 10. N016/:jess.2011.44.00 URL 10. 10.1016/11 jca.:/...c...... 2014. 04. 015
html
Cohen-Addad, V., Lattanzi, S., Mitrovic, S., Norouzi-Fard A., Parotsidis, N., and Tarnawski, J. Correlation cluster- ing in constant many parallel rounds. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2069-2078. PMLR, w.l..press/ v1 v139/cohen www.:oohhnnaccccll........ html
orr/
Gael, J. V. and Zhu, X. Correlation clustering for crosslin- gual link detection. In Veloso, M. M. (ed.), IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-
2021.
12, 2007, pp. 1744-1749, 2007. URL http::/tt/// //jjcai org http://ooedd..ggsg//////////////
Cohen-Addad, V., Lee, E., and Newman, A. Correlation clustering with Sherali-Adams. In 63rd IEEE Annual Symposium Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31- November 3, 2022, doi: 10. 10.1109/70C554457.
Kalashnikov, D. V., Chen, Z., Mchrotra, S., and Nuray- Turan, R. Web people search via connection analy- sis. IEEE Trans. Knowl. Data Eng. 10500:1550- 2008. doi: 10.1 10.1109/TKDF.2008.1 78. URI. https 2008. 78
pp. 651 1661. IEEE, 2022.
2022.00068. URL FOCS54457.200 201557200220000 00068
//doi. 10. 1
Kim, S., Nowozin, S., Kohli, P., and Yoo, C. Higher- order correlation clustering for image segmentation. In Shawe-Taylor, J., Zemel, R. S., Bartlett, P. L.,
Cohen-Addad, V., Lee, E., Li, S., and Newman, A. Han- dling correlated rounding error via preclustering: A 1.73-

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
Pereira, F. C. N., and Weinberger, K. Q. (eds.), Ad- vances in Neural Information Processing Systems 24: 25th Annual Conference Neural Information Processing Systems 2011. Proceedings of meeting held 12-14 December 201 Granada, Spain, pp. 1530- 1538. 2011.
Notes in Computer Science, pp. 568-581. Springer, 2012.
doi: 10.10779788-3144233788333 41. https:/ /
doi. 1o1.org/10.1007/9978 3-913388--3-38-888------33------
URL
B865500000aaDD660000001111111110 Abstta html
Makarychev, and Chakrabarty, S. Single-pass pivot algorithm for correlation clustering, keep simple! In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, Decem- ber 10 16, 2023, 2023. URL
nips. catpsccc/paper_ffae_1 http://ppe....eaeeeeeeee//////aa 159ad632200377abbccc1111777776
ract wwwaataoocfeeeeeee Conference.
html
Pham, D. L. Fuzzy clustering with spatial constraints. In Proceedings. International Conference on Image Process- ing, volume 2. pp. II-II. IEEE, 2002.
van Zuylen, A. and Williamson, D. Deterministic piv- oting algorithms for constrained ranking and clustering problems. Math. Oper. Res., 34(3):594 620, 2009. doi: 10. 10228//moor,1000000330 URL BtL.ttts::/ /tttps://doi.oo http://ooooorooooooo/////.oo/oo 10.1287/mocrz 1090. 0385. Announced in SODA 2007.
Veldt, N., Gleich, D. F., and Wirth, A. A correlation clustering framework for community detection. In Champin, P., Gandon, F., Lalmas, M., and Ipeirotis, P. G. (eds.), Proceedings of the 2018 World Wide Web Conference on World Wide Web. WWW 2018, Lyon, France, April 23-27, 2018, pp. 439-448. ACM, 2018. doi: 10. 10.111553178887.311661000 URL URLhttps::/det 3rrr/00.1145/33188666333333
Wagstaff, K., Cardie, C., Rogers, S., Schrödl, S., et al. Con- strained k-means clustering with background knowledge. In leml, volume 1, pp. 577-584, 2001.
Wang, X. and Davidson, I. Flexible constrained spectral clustering. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 563-572, 2010.
Yarkony, J., Ihler, A. T., and Fowlkes, C. C. Fast planar cor- relation clustering for image segmentation. In Fitzgibbon, A. W., Lazebnik, S., Perona, P., Sato, Y., and Schmid, C. (eds.), Computer Vision ECCV 2012 - 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012, Proceedings, Part VI, volume 7577 of Lecture
12

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
A. Analysis of Local Search with Penalty In this section, we present the analysis of Algorithm 2
which very closely follows the analysis of Algorithm
Lemma 4.8. If C' is not (2 a)-pproxiee then:
18 (f')++
Σ
Fun +(*+((")
(CE)+(CC)
< öLP +2
Tuv
WUEE+ (C)
Proof. Let C' be cluster such that =c 0 in the LP solution returned (C' E M). Recall that, L' denotes the clustering obtained by applying local move with cluster C' on clustering L'. This local move can affect an edge (i.e. make it satisfied or unsatisfied) only if the edge has at least one endpoint in cluster C' (if not, then the endpoints of the edge do not change cluster, which means that they remain as they are satisfied or unsatisfied). We say that these edges are covered by C. By the local optimality of L', we have cost' (C') v cost'(C'c) This means that after swapping cluster C' in, more edges covered by C' are unsatisfied than before. Let C+ denote the set of plus-edges that have exactly one endpoint in C. Similarly, let C' denote the set of minus edges that have both endpoints in C. The C* U C- is the set of edges unsatisfied by the cluster C. Next, let E (C') S (+(') be the set of plus edges wy Ex (CC) that are covered by C, i.e., [u,, v} n CI 2 1. Let EC C (L') be the set of minus edges E 8- (CC)) such that Hu, w) n CI 2 1. From the above discussion, for each cluster C with 2c > O, we have, |C+1 + |C+ n + |C- > 31 (2') + (E') (C))()CC)))))))) + 1 (C') This further implies that
Σ = (o-((C+++10+++
Σ 0 |C (Ct
Σ 2c + + z (C')
We simplify the first term of every side of the inequality in the same manner in Lemma 4.4 which gives us:
2LP LP + Σ cc ICt (E)(C)) 2 cost(f")=
Σ
Σ> 20 (C))
Two +
WeEE+
(C")UE-CE (C')
We simplify the term Ee 2o |C+ n (C) of the left-hand side by accounting the contributions of plus edges to the summation.
plus edge in g+ (C) contributes an amount of ac to the sum either u or e is contained in C. Thus, its total contribution is Σ Eo:jon(w)))2 =C, which is equal to 1 + Zuv.
For an edge to contribute to the term it must be in E+ and only have one of its endpoints in cluster C. This means that every edge in (C) contributes exactly Ec: (u.o)nol-1 =c = 2xa Thus, we get:
Σ 10 (ootnet(CC) =2
Σ (CE
Fav
We similarly transform the term Ec (Et((') n (C)) of the right-hand side. For an edge to contribute to the term it must be in both E- (C) and & (L') and least one of its endpoints in cluster C. This means that every edge in E (C)nn+t())) contributes exactly EoHHw 2c = 1 + Fuv- Thus, get:
Σ 2c (0))))++())
Σ
(1 + Faw) xav)= = 18 (1
Σ
Fae
WEEE + (C)NE (Cr)
aPEE + (C)NE+ (C')
By substituting these rewritten terms in the inequality, we get the following:
13

---

Towards Better-than-2 Approximation for Constrained Correlation Clustering
cost(L") -LP LP-
Σ
Fur -1 +2 WPEE+(C) (C)
Σ
Tue
Σ
Fuv
uPEE (C")UE(CC)
(VEE+())
2LP LP
Σ
Fuv (8
+2
Σ
uDEE+ (C")UE-(E)
uDEE+ (C)
< 2LP (1-)11 -
Σ
Tue (C()))
E
Tuv
U2)
UVEE+(L)
For the second inequality we used the fact Envegt (E)NEt(E") Tuo 2 0 and for the third inequality the fact LP + EnvEE (0') Tun 2 EuvEE (cy(1 Tun + Tuv). Finally, if L' is not (2 -)-aprooximate, then:
+C))+
E
Iun + ((())=) +LP
Σ
Eue
WEEE (29)
WVEET(A)
which is the desired statement.
14


Reviews:
[{"review_id": "FRI5U57jpB", "reviewer": "Reviewer_hg9m", "summary": "The authors consider the classic Correlation Clustering problem which, given a complete graph with edges labeled either + or -, the goal is to find a partition of the vertices so as to minimize the number of + edges across parts plus the number of - edges within parts. The has received a lot of attention since its introduction in the early 2000s.\n\nThe authors study the hard-constrained version of Correlation Clustering which goes as follows. In addition to the graph, some pairs of vertices may be labeled as hard positive or hard negative. The solution then must not separate any hard positive pair and not join any hard negative pair. \n\nThe problem is harder than the standard Correlation Clustering for which a 1.43 approximation is known and for which a 2.5-approximation has been known for 20 years. Only a 3-approximation was known for the hard-constrained version of the problem.\n\nThe authors combine two state-of-the-art methods to obtain this results: the Cluster Linear Program (LP) introduced at FOCS'23 and further analyzed at STOC'24, and the local search techniques presented at STOC'24. It is remarkable that these two techniques could be (1) extended to handle the hard-constrained version of the problem (albeit at the expense of worse approximation) and (2) combined to obtain better approximation bounds. The idea of using the clusters output by the Cluster LP as input clusters for local search is neat and a clever way to handle the hard constraints.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestion. We inherited the \"competitive\" terminology from the local search paper [Combinatorial Correlation Clustering; Cohen-Addad et al.; STOC 2024], but we understand now that mixing the two can be confusing. We will stick to \"approximate\".", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I went over the proofs. I haven't checked the proofs in the appendix in details though.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "Nothing missing.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "I like the paper. It cleverly combines state-of-the-art techniques to solve a more general problem.", "other_comments_or_suggestions": "I would suggest to remove \"competitive\" and use \"approximation\" in, e.g., 2-competitive. Usually competitive refers to the online algorithm setting, and it is a bit confusing to have both competitive and approximation at the same time in the paper.", "questions_for_authors": "No specific question at this stage.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NftYdrQ2DL", "reviewer": "Reviewer_W4nh", "summary": "The main contribution of this paper is the development of a 1.94-approximation algorithm for the constrained correlation clustering problem. In this context, the input is a graph consisting of edges labeled as {+1, -1}. The objective of correlation clustering is to find a partition (clustering) of the nodes that minimizes the total number of negative edges inside clusters plus positive edges between clusters. A natural extension of this problem is imposing constraint that dictates whether certain selected edges must belong to the same cluster or to different clusters.\n\nFor vanilla correlation clustering, there are two primary techniques LP and LS that achieve good approximation. Both struggle to be directed applied to the constrained version. However, the authors point out that the fractional solution is sufficient to help find a satisfactory integer solution. Roughly speaking, they initially form a collection of clusters by selecting all subsets with a positive indicator from the LP solution, and then compute a clustering L by running local search. Next, they compute L’ by running local search with penalty based on L. Finally, they implement the pivot algorithm, which “mixes” L and L’ and outputs a clustering P (with high prob). At least one solution out of {L, L’, P} achieves a 2-2/31 approximation. The authors demonstrate this by assuming that both L and L’ are inadequate, leading to the conclusion that P would be a sufficiently good solution.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions, we will apply them all in the final version.\n\nIn particular, regarding APX-Hardness of Correlation Clustering:\n- It was shown that Correlation Clustering is APX-Hard, but without an explicit constant, in [Clustering with qualitative information; Charikar, Guruswami, Wirth; FOCS 2003].\n- An explicit constant 24/23 > 1.043 was given in [Understanding the Cluster LP for Correlation Clustering; Cao et al.; STOC 2024], under the assumption that $P \\ne BPP$. In the same paper they proved a 4/3 integrality gap for the cluster LP.\n\nWe are not aware of any studies or results that discuss lower bounds on the approximation ratio of Constrained Correlation Clustering. In fact, when we first started this work, we were considering whether 2 is an actual lower bound, but we did not have any insight on how to leverage the hard constraints in order to improve the lower bound.\n\nIt is worth mentioning here that Constrained Correlation Clustering is not the only problem generalizing Correlation Clustering for which the only known lower bound is the APX Hardness of (unconstrained) Correlation Clustering. Ultrametric Violation Distance and $L_1$ Best-Fit Ultrametrics (from the tree-reconstruction world) also generalize Correlation Clustering, but their hierarchical nature has not been successfully leveraged to provide any better lower bound.\n\nOnce again, we thank the reviewer and will incorporate the above discussion in the final version of our paper.", "claims_and_evidence": "All claims are supported by proofs.", "methods_and_evaluation_criteria": "This is a totally theoretical paper without experiments.", "theoretical_claims": "Yes. I checked all proofs except those in the supplement.", "experimental_designs_or_analyses": "There is no experiments in this paper", "relation_to_broader_scientific_literature": "the method the author proposed has the potential to handle more constrained problems.", "essential_references_not_discussed": "I have not found so far.", "other_strengths_and_weaknesses": "The contribution of this paper is straightforward. The study provides an innovative approximation ratio for the constrained correlation clustering problem. Moreover, the overall idea of the proof is concise and easy to follow. The algorithm is very simple to implement.", "other_comments_or_suggestions": "typos\n\n- Line 214, a feasible clustering $C$ should be $\\mathcal{C}$\n- In corollary 4.5, some $\\mathcal{E}$ are misspelled as $E$", "questions_for_authors": "More discussions on the hardness are needed.\n1. As the constrained correlation clustering is APX-Hard, are there any studies or results that discuss the lower bound of its approximation ratio?\n2. Correlation clustering w/o constraints are APX-Hard. Are there more nuanced differences in computing complexity between the two? Maybe constrained correlation clustering is much harder.\n\nAlthough responses to these questions will not affect my score, I believe it is beneficial to include this content in the paper for a more comprehensive discussion.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "APvPREZvLb", "reviewer": "Reviewer_Rox7", "summary": "This paper proves a better-than-2 approximation for constrained correlation clustering (correlation clustering where certain \"friendly\" pairs are required to be in the same cluster and other \"hostile\" pairs are required to be separated). The approach combines two recent techniques for standard correlation clustering that led to better-than-2 approximations for the unconstrained case: rounding the cluster LP relaxation and the local search method. In more detail, this paper approximately solves the cluster LP relaxation (with new constraints for friendly and hostile pairs), runs local search, then runs another local search with a new type of penalty to get a qualitatively different clustering, and then rounds the LP relaxation to get another clustering. If the first two clusterings are no better than 2 approximations, a new procedure is used to \"mix\" them with the rounded LP solution to get another clustering that is a better-than-2 approx.\n\n## Update post rebuttal\n\nThanks for the responses. I continue to have a very high view of the paper.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions, we will apply them all in the final version.\n\nRegarding the proof-by-contradiction: Indeed, this claim of ours is inaccurate; this is how it was treated in the original local search paper [Combinatorial Correlation Clustering; Cohen-Addad et al.; STOC 2024], because the clustering obtained from \"mixing\" was only part of the analysis (as it requires knowledge of the optimal). As the reviewer correctly understood, in our case we have access to a (fractional) optimal, and therefore also have access to the clustering obtained by \"mixing\". Therefore, there is no need for proof-by-contradiction. We shall rectify that in the final version of the paper.\n\nWe also thank the reviewer for their suggestion to highlight that our work conceptually simplifies better-than-2 approximations of (unconstrained) Correlation Clustering.", "claims_and_evidence": "None of the claims are problematic, the paper provides proofs for all aspects of the paper.", "methods_and_evaluation_criteria": "The methodology is sound and is based on a combination of existing techniques for getting better than two approximations for standard correlation clustering.", "theoretical_claims": "I checked the first couple proofs in more detail (finding no problems), and skimmed more quickly through the rest of the proofs. I did not encounter any issues. The logical layout of the Lemmas and corollaries is very clear and does a good job guiding the reader.", "experimental_designs_or_analyses": "There are no experimental results.", "relation_to_broader_scientific_literature": "There has been a flurry of recent work on better-than-2 approximations for standard correlation clustering (which the paper has reviewed in detail), but very little for constrained correlation clustering. This paper shows how these recent methodologies (with some extra work) can be made to work for constrained correlation clustering.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "This paper is overall very strong and fills a large gap in the literature. There has been a lot of work on unconstrained correlation clustering recently, with very little work focused on understanding how these recent advances can apply to other variants of correlation clustering. The paper outlines prior work and provides important background very clearly, and then provides a detailed proof for better-than-2 approximations for constrained correlation clustering. This builds on prior techniques for unconstrained correlation clustering, but the theoretical contribution is still very non-trivial. It needs to combine two previous techniques from the literature, and includes several other new tricks and results in order to make everything work for the constrained case. I found the manuscript very easy to read and the proof (while detailed and non trivial) is laid out very carefully and logically for the reader.", "other_comments_or_suggestions": "On the right column at the top of page 5, I think you are missing a \"z_C\" in one of your summations; you have \\sum_{c : v \\in C} = 1 instead of \\sum_{c: v \\in C} z_C = 1.\n\nIn the statement and proof for Corollary 4.5, you used E several places instead of \\mathcal{E}", "questions_for_authors": "On page 7 you mention that creating a new clustering that is 30\\delta-competitive is a \"contradiction\" for small enough \\delta. However, when I read this I had not forgotten that you previously set \\delta to be 2/31, meaning that you get a slightly better than 2-competitive result, and unless I'm missing something there's no contradiction here. My understanding is that the idea is just that if your first 2 clusterings are not $2-\\delta$ competitive, you then can construct a 3rd clustering via \"mixing\" that is a better than 2 approx. My question is: am I missing something or is this really not a proof by contradiction but just rather a proof that at least one of three clusterings is guaranteed to get you the desired result? I wonder if it'd be cleaner and more direct to not try to argue there is some sort of contradiction here. This is of course very minor.\n\nThis entire approach also applies when F = H = \\emptyset, right? So can we not also view this as a new approach for getting a better-than-2 approximation for unconstrained correlation clustering that mixes a couple prior approaches? This would not be groundbreaking given the other existing better approximation factors, but could there be a benefit of your approach even just for unconstrained correlation clustering (e.g., in terms of simplicity of arguments?).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6CI1ZFIV7k", "reviewer": "Reviewer_h3bn", "summary": "In this paper, the authors study Constrained Correlation Clustering, introduced by van Zuylen and Williamson (2009). The problem is a generalization of the well-known Correlation Clustering, where we are additionally given the set of friendly pairs and the set of hostile pairs and the goal is to find an optimal clustering (in terms of Correlation Clustering) satisfying the additional constraint that every friendly pair is placed within a cluster and every hostile pair is placed across clusters. In the context of machine learning, this problem can be seen as a semi-supervised variant of Correlation Clustering. For the problem, the state-of-the-art polynomial-time approximation ratio is 3, which was also given by van Zuylen and Williamson (2009). In the present paper, the authors propose a polynomial-time better-than-2 (< 1.94) approximation algorithm. To this end, the authors combine two techniques that have recently been developed to achieve better-than-2 approximations for Correlation Clustering: one is the cluster LP (Cao et al., 2024) and the other is a local search algorithm based on an optimal clustering (Cohen-Addad et al., 2024).\n\n## update after rebuttal\nMy initial recommendation was conditional due to an issue in the proof. The authors have now rectified this in their rebuttal, and I maintain my original recommendation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review and comments.\n\nFirst we reply to their two main concerns, that is, the practicality of our algorithm and Lemma 4.4.\n\n--- \n\nRegarding the practicality of our algorithm, as the reviewer noted, the bottleneck is in solving the Constrained Cluster LP. We are happy to share that after our submission, a paper titled “Solving the Correlation Cluster LP in Nearly Linear Time” was published at STOC 2025. This makes us optimistic that our overall algorithm can be practical.\n\nIt is worth noting that to feasibly use this particular approach, one should compromise for worse theoretical guarantees. Furthermore, the paper is 57 pages long, so it would require a whole new work to study how to adapt it to the constrained setting.\n\nWe view our algorithm as a flexible framework to which one can incorporate any solution to the Constrained Cluster LP (whether it is a variation of the STOC paper or some totally new algorithm), and get a solution for Constrained Correlation Clustering. Under this light, future work can focus on implementing practical solvers for the Constrained Cluster LP (even with weaker guarantees, as long as they are efficient) and get solutions for Constrained Correlation Clustering.\n\n---\n\nRegarding Lemma 4.4, thank you very much for spotting the issue. There is indeed a mistake in the proof the way it is written in the submission. Specifically, we should have used a stronger inequality resulting from the local optimality of the clustering L. However, the following is a simple fix. \n\nWe say that an edge is crucial if it has at least one endpoint in C. Since the cost of L is at most the cost of $L_C$, it must be the case that the number of crucial edges unsatisfied by $L_C$ is more than the number of crucial edges unsatisfied by L. We redefine $E_C^+(L)$ to be the set of crucial edges in $E^+(L)$, and $E_C^-(L)$ to be the set of crucial edges in $E^-(L)$. \n\nThe proof, as was written in the submission, holds once the aforementioned changes are made.\n\n---\n\nWe also briefly reply to some of the other comments of the reviewer. For the ones we do not give a reply, we agree with the reviewer and will incorporate the suggestions on the paper.\n\n* \"The reason why we are required to use the fractional clustering, as stated on Page 6, is not quite clear. Is it to simplify the analysis?\":\nIndeed, we will make this more clear. This is not just to simplify the analysis. It is because the guarantees for our two clusterings are with respect to the fractional optimal (instead of the actual optimal, as was done in the paper that introduced the local search approach for correlation clustering [Combinatorial Correlation Clustering; Cohen-Addad et al.; STOC 2024]).\n\n* \"On Page 5, we do not need to mention the range of the cost to see the polynomial time complexity of Algorithm 1.\":\nOur understanding is that it takes polynomial time to improve the cost by at least 1, and as the maximum cost is polynomial, this improvement cannot happen many times. However this would not be the case if the maximum cost is exponential and every time we only improve by 1.\n\n* \"What the \"fractional clustering\" refers to should be explained.\":\nWe will make this more clear; with \"fractional clustering\" we refer to a solution of the Constrained Cluster LP.\n\n* \"The first sentence of the last paragraph of the proof of Lemma 4.16 is not clear.\"\nIndeed, we will rephrase that to \"By maximality of S we have $Q_{XY'Z} \\le S$, and therefore we can find an injective function $f: Q_{XY'Z} \\rightarrow S$\". If $\\{u,f(u)\\}$ is a plus edge [...]\" so that we are more precise.\n\n* Conclusion section: Thanks for the suggestion. We will add a concluding section summarizing our contributions and discussing the research directions left open by our work.", "claims_and_evidence": "Generally speaking, the claims are supported by clear and convincing evidence. In particular, the intuitive explanations provided throughout the paper make it easy to follow.", "methods_and_evaluation_criteria": "The proposed algorithm makes sense.", "theoretical_claims": "I have checked the correctness of all contents in the main body. My recommendation, Weak Accept, is conditional, based on the following concern about the correctness. Let's look at the last paragraph of the proof of Lemma 4.4 (starting with \"We similarly transform the right-hand side...\"). The authors state that a plus edge in $\\mathcal{E}^+(\\mathcal{L})$ contributes an amount of $z_C$ to the sum if either $u$ or $v$ is contained in $C$. However, in my understanding, it is wrong. Indeed, a plus edge in $\\mathcal{E}^+(\\mathcal{L})$ contributes an amount of $z_C$ to the sum if both $u,v$ are contained in $C$. Note that the right-hand side computes the cost decremented by $C$ rather than that incremented by $C$. This leads to the contribution $1-x_{uv}$ rather than $1+x_{uv}$. Similarly, for a minus edge, it seems we have the contribution $1-x_{uv}$ rather than $1+x_{uv}$. Based on the above, it is not clear if we can still have the simplification stated in Lemma 4.4.", "experimental_designs_or_analyses": "No experiments performed.", "relation_to_broader_scientific_literature": "Correlation Clustering is one of the most actively-studied clustering problems in machine learning.", "essential_references_not_discussed": "No essential references missing.", "other_strengths_and_weaknesses": "- I enjoyed reading the paper and was a bit surprised that a better-than-2 approximation for (Constrained) Correlation Clustering can be achieved through such a simple and reader-friendly analysis.\n- Although it is acknowledged that the paper improves the state-of-the-art result of the SODA 2009 paper, the contribution might be not quite significant in the machine learning community. Indeed, the proposed algorithm is, unfortunately, not practical due to solving the variant of the cluster LP and the authors do not test the algorithm empirically.", "other_comments_or_suggestions": "Comments: \n- Regarding Constrained Correlation Clustering, unfamiliar readers could think that handling the set of friendly pairs is trivial (as they could think that the pairs can be simply aggregated into super elements). It would be better to point out that the aggregation leads to a weighted instance outside the problem. \n- Considering that Constrained Correlation Clustering is a generalization of Correlation Clustering, we can see that the present paper also simplifies the analysis of some better-than-2 approximations for Correlation Clustering. This point could be better highlighted. \n- Section 4 could be organized better using subsections etc. \n- What the \"fractional clustering\" refers to should be explained. \n- Lemmas 4.2 and 4.13 are trivial and do not need the proofs. Alternatively, Corollary 4.14 is not so straightforward and the proof would be helpful. \n- On Page 5, we do not need to mention the range of the cost to see the polynomial time complexity of Algorithm 1. \n- The reason why we are required to use the fractional clustering, as stated on Page 6, is not quite clear. Is it to simplify the analysis?\n- The first sentence of the last paragraph of the proof of Lemma 4.16 is not clear. \n- It might be unusual not to have a concluding section. \n\nTypos: \n- Page 2: Wirt -> Wirth\n- Page 2: an $(1+\\epsilon)$ -> a $(1+\\epsilon)$\n- Page 3: unweighted, undirected -> unweighted, undirected, complete\n- Page 5: Some $E^+$ and $E^-$ should be $\\mathcal{E}^+$ and $\\mathcal{E}^-$, respectively. \n- Lemma 4.10 is not exactly the same as Lemma 6 of Cao et al. (2024) due to the generalization.", "questions_for_authors": "Please see the above comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Correlation Clustering is a fundamental “clustering under imperfect information” problem, several variants of which have been studied for more than two decades especially from an approximation-algorithms viewpoint. In the basic problem, we are given a complete graph G on n vertices with edges labeled either + or -, and one example objective is to efficiently find a partition of the vertices that minimizes the sum of the (number of + edges across parts) and the (number of - edges within parts). 

This paper studies a natural version of the problem with hard constraints of the following form: some pairs of vertices may be labeled as “hard positive” or “hard negative”---we should not separate any hard-positive pair and must not keep any hard-negative pair in the same cluster. This problem is harder than standard Correlation Clustering.

The paper combines two state-of-the-art methods: the “Cluster Linear Program” (LP) and local-search techniques presented very recently in major theoretical CS conferences in the last two years. Expert reviewers found it remarkable that these two techniques could be extended to handle the hard-constrained version of the problem and combined to obtain better approximation bounds. The idea of using the clusters output by the Cluster LP as input clusters for local search was viewed as a particularly innovative way to handle the hard constraints.
Decision: Accept (spotlight poster)