Chromatic Correlation Clustering, Revisited
Authors: Qing Xiu
Kai Han
Jing Tang
Shuang Cui
He Huang
Venue: NeurIPS 2022 Accept (2022)
Keywords: chromatic correlation clustering
approximation algorithm

Abstract: Chromatic Correlation Clustering (CCC) (introduced by Bonchi et al. [6]) is a natural generalization of the celebrated Correlation Clustering (CC) problem, introduced by Bonchi et al. [6]. It models objects with categorical pairwise relationships by an edge-colored graph, and has many applications in data mining, social networks and bioinformatics. We show that there exists a $2.5$-approximation to the CCC problem based on a Linear Programming (LP) approach, thus improving the best-known approximation ratio of 3 achieved by Klodt et al. [21] . We also present an efficient heuristic algorithm for CCC leveraging a greedy clustering strategy, and conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithm.

Chromatic Correlation Clustering, Revisited
Qing Xiu
Kai Han"
School of Computer Science and Technology Suzhou Institute for Advanced Research University of Science and Technology of China xiuq@mail ustc.utcooo. edu.
School of Computer Science and Technology Soochow University hankai @suda edu. cn
Jing Tang
Shuang Cui
The Hong Kong University of Science and Technology (Guangzhou) The Hong Kong University of Science and Technology j ingtang@ust. hk
School Computer Science and Technology Suzhou Institute for Advanced Research University of Science and Technology of China lakers &mail 1 .stc..cc. edu.cn.
He Huang'
School of Computer Science and Technology Soochow University huangh@suda, edu. cn
Abstract
Chromatic Correlation Clustering (CCC) (introduced by Bonchi 66] is a natural generalization of the celebrated Correlation Clustering (CC) problem. It models objects with categorical pairwise relationships by an edge-colored graph, and has many applications in data mining, social networks and bioinformatics. We show that there exists a 2.5-approximation to the CCC problem based on a Linear Programming (LP) approach, thus improving the best-known approximation ratio achieved by Klodt et al. (25). We also present an efficient heuristic algorithm for CCC leveraging a greedy clustering strategy, and conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithm.
Introduction
Clustering is the task of partitioning set of objects into groups according to their relationships. One of the most important clustering problems Correlation Clustering (CC), which has attracted great interests in recent years (e.g.. 11100). ). In the CC problem, the input instance is undirected complete graph with each edge labeled as either similar or dissimilar, and the goal to partition the graph nodes into arbitrary number of clusters such that the number of disagreements is minimized, where a "disagreement" occurs if a dissimilar edge links two nodes in the same cluster or a similar edge links two nodes in different clusters. However, CC only models binary relationships, which is insufficient in many applications. For example, the relationships in social network could have multiple types such colleague, schoolmate, and family. To address this issue. Bonchi et al. 66] generalize the CC problem to the Chromatic Correlation Clustering (CCC) problem, where an edge-colored graph is used model the multi-type relationships in practice, i.e., each edge is associated with color and each color represents a type of relationship. The goal CCC is to partition the graph nodes into several clusters and assign color each cluster to minimize the number disagreements, where disagreement happens in any case other than that two non-adjacent nodes belong to different clusters
"Conesponding author: Kai Han Slaakai@ssda.ceee
and He Huang <huangh @suda.edu.cm
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

or that two adjacent nodes belong to the same cluster with the cluster's 's color being identical to the color of the edge between these nodes. Due to its generality, CCC has wide applications including link classification, entity de-duplication, mining protein complexes in protein-protein interaction networks, and so on 25
Related work. The original Correlation Clustering (CC) problem has been extensively studied since the seminal work of Ben-Dor et al. [5]. Bansal al. 4 proved its NP-hardness and gave the first constant-factor approximation, which was improved to 4 in [9] by rounding the solution to a linear programming relaxation. Ailon et al. proposed a simple linear-time algorithm dubbed Pivot that achieves 3-approximation, and also proposed an LP-rrunding based algorithm with an improved approximation ratio of 2.5. Chawla et al. [10] further improved this ratio to 2.06 by using a more sophisticated LP- LP-rounding technique, which nearly matches the known integrality gap of 2
9 for the I.P formulation of CC. Some studies also proposed fast heuristic algorithms for CC 16, 17 29 30 334, but without providing any performance guarantee. Due to the importance of
CC, a lot of its variants and related problems have been investigated in the literature
7 9
13
[4|
[8
21
22 24
26 27 31 32 33
Bonchi et al. O initiated the studies on the Chromatic Correlation Clustering (CCC) problem and proposed a heuristic for it without a provable approximation ratio. Anava et al. 3 presented a 4approximation algorithm for CCC based on LP-rounding, and also provided a more efficient 1 --aappooimmation algorithm dubbed Reduce and Cluster (RC) and heuristic dubbed Deep Cluster (DC). Recently, Klodt et al. [25] showed that the classical Pivot algorithm proposed in Ailon et al. 2 for the CC problem also has an approximation ratio of 3 for CCC, and showed that the RC algorithm proposed (3] actually has an approximation ratio of 5 for CCC. Although Pivot has the best-known approximation ratio for CCC, it works in a color-blind manner and hence has unsatisfying practical performance. Therefore, Klodt et al. [25) further proposed heuristic dubbed Greedy Expansion (GE) which has better practical performance but without performance guarantee. Therefore, it still remains as an open problem to find an approximation ratio for CCC tighter than the 3-approximation achieved by Pivot. CC (or CCC) also bears some similarities to the clique partitioning, multicut and wwwnter/k-mmeeeeeeee proposals (e.g.. [ [5 19 20).. However, it is highly non-trivial (if possible) to adapt the solutions of these studies to the CCC problem.
problems, which have been studied in some excellent
Our contributions. In this paper, we propose 2.5-approximatton to the CCC problem based on an LP approach, improving the best-known ratio of achieved by Klodt et al. 22] and being very close to previously known integrality gap of 2 [9] We achieve this ratio by using a simple yet effective algorithm based on rounding the optimal solution to a linear programming relaxation of CCC, which is very different from the rounding algorithm proposed in 33. More specifically, we first classify all vertices of the graph into several groups, with the vertices in each group colored the same, and then cluster the nodes in each group using procedure similar to the canonical Pivot algorithm. Both the classifying phase and the clustering phase described above use the Lo--solution to CCC to ensure guaranteed clustering quality. Although our LP-based clustering algorithm is randomized, it can be de-randomized to achieve a deterministe 2.5-approximation Due to this novel clustering framework, our performance analysis is more involved than previous work address the difficulty of counting the number of disagreements in a color-sensitive manner.
We notice that the algorithms proposed by prior studies for CCC with the best empirical performance are heuristics without performance guarantees. Therefore, we also propose a fast heuristic dubbed Greedy Vote that adopts novel greedy strategy roughly explained as follows. Greedy Vote creates a cluster by firstly picking two neighboring "seed vertices", and then growing the seed set by letting the seed vertices vote for every unclustered vertex and greedily adding vertices with the largest vote counts into the seed set. We conduct extensive experiments using real-world datasets and the results strongly demonstrate the superiorities of Greedy Vote in terms of both clustering quality and efficiency, compared to the state-of-the-an algorithms with or without performance guarantees.
2 Preliminaries
In the Chromatic Correlation Clustering (CCC) problem, an input instance consists of a finite set L of colors (representing positive relationships), a special color 7 & (representing negative relationship or no relationship), and an undirected complete graph G' = (V, E) with color function o: E +
2

---

(n). The objective is to find colored partition of the vertex set V that minimizes the number of disagreements. More formally, a solution to this problem is a clustering S (C. 4) consisting of partition of the vertices C: V + (C1, C2,... } and cluster-coloring function cb range(C) + L. The number of disagreements between G and S can be written as Enve da.s(un) where
0 (uv) 7 A(u)) + C(u),
(wv)(
((u)) L A ((u) C(v) ((C(u)) d(ur),
(1)
otherwise.
For simplicity, we use d(uv) as shorthand for de.s (wv). There also exists Linear Programming (LP) relaxation of the chromatic correlation clustering problem [3) i... [CCC-LP] listed below. Let us consider an integral solution satisfying zu.. zy E {0, } for all u E V, ue E E, c E L to [CCC-LP]. The variable z; indicates whether vertex u is in a cluster of color e E or not (i.e.. if #f = 0 then is in the cluster colored by c). Similarly, the variable Fy indicates whether two vertices and are clustered into the same cluster colored by c C L (i.e., x ur belong to the same cluster colored by c). Constraint
then and 4 guarantees that each node belongs to one colored cluster. Constraint ( implies that the edge wy can be in the cluster colored by c E L only if both vertex u and are in this cluster. Constraint (3) ensures that if wv and are in the same cluster then the edge wu must also be the same cluster. According to the definition of the variable Euyy we know that edge E E with color e L does not cause disagreement only if x O, and that an edge uy with color y does not cause a disagreement only if x = 1 for any color E L. As such, the objective function of [CCC-LP] consists of two parts: the first part counts the number of disagreements caused by the edges colored by c E L, and the second part counts the number of disagreements caused by the edges colored by y. Note that can omit the variable xa when L = and then it becomes the same L.P-formulation of CC (2, and hence the integrality gap of [CCC-LP] is least 2 19]
min
E
((v) uo
Σ
Σ - m
[CCC-LP]
E d(un)EL
WEE :: p(un)= 1EL.
s.t.
uu 2 xy J
V, L
(2)
E + E.w 2 I
Wu,
(3)
Σ x = [T.]
V
(4)
DEL
2e = x
L L L
(5)
Ty L [0.1]
(6)
3 An LP-based Approximation Algorithm
In this section, we present an L.-based approximation algorithm as shown in Algorithm 1 namely LP- Clustering. It is randomized and we will show how to de-randomize it in Section C Intuitively, we aim to round the LP solution x; for all E V.c E L and x:f for all wv E E, E integers being feasible to the LP problem such that the objective value of the rounded integer solution is close to that of the optimal fractional solution as much as possible. In a nutshell, our plusterng algorithm consists of two phases, including a vertex partitioning phase by rounding x for all e E V, E L and a clustering phase for each partition by rounding x: for all we E E, c E The detailed procedures of the two phases are given follows.
Phase Partitioning (Lines 2 the vertex set V is partitioned into [L] disjoint subsets such that S. {v E V 26
}}} for each L and O = V (U.et Sc). Note that S. may be an empty set for c E L. And all S. are determined.
Phase 2 Clustering (Lines 12 (i) for the partition O, each outlier E O is assigned to singleton cluster with an arbitrary color (Lines (Lin (ii) and for each partition S., the algorithm iteratively chooses unclustered vertex from S. uniformly at random the center of new cluster C³ with color and adds each unclustered vertex u E S. to C₁ with probability of (1 _ independently (Lines 12)..
In the following, we elaborate the intuition. Recall that the variables of indicates the impossibility of vertex being cluster of color while σG, represents the distance between vertices and v with
3

---

Next, we finalize the clustering by rounding z with respect to the rounded value of œ for each E V and E Specifically, for each outlier v E O, assigming containing this node only, is equivalent to round x to for every =h x 2 1/2, such a rounding ensures the corresponding cost of the integer solution within twice of that of the fractional solution. Moreover, for the subset S. of V containing vertices with color we iteratively select an unclustered vertex from S. uniformally at random and create new cluster CA {v), until every vertex in S, is included in some cluster. Then, we add each unclustered vertex E S. Cs with probability of (1 - rr i.e., rounding xff with a probability of (1 = and to with the other probability that the rounded = in expectation is exactly x Such Algorithm 1: LP-Clustering
Input: An undirected complete graph = (V,E) E) with color function 6: + LU {7), the
LP solution z, i.c., {xf; Yu E V, Vc E L} and f Yuv E, Ye 4}
Output: A clustering {C1, C2....) and a cluster-coloring function
Initialize & <- 0 and O 4 V;
2 foreach e E L do
Let S. be the subset of nodes in with value x. < 52 i... Se + (uE x. <
Remove S. from O;
foreach O do
Create a new cluster Ck = {0} by increasing & by 1, and set ((Ca) as an arbitrary color;
foreach c E do
while S. * 0 do
Pick vertex v S. uniformly at random;
10
Create new cluster Ck + {v) by increasing k by 1, and set (CC)) +
11
foreach E Se {v} do add u to C with probability Fuvi
Remove Cj from Sc;
return (C1, C2....,, C
respect color c. Based on this observation, our LP-Clustering algorithm first determines the verier color for each vertex v by rounding 2f, i.e., the color of the cluster to which vertex v belongs with the maximum likelihood. That is, u will be assigned to a cluster with color e r < 1/2, which ensures that r I x for any č E L implied by Observation 4.1 This is equivalent to round æ to 0 and xf to 1 for every ē * c. Meanwhile, we call a vertex outlier if x; 2 1/2 for every E L., which is far away from any other vertex u as to every color due to the fact that z 2 x 2 1/2. Then, for each outlier u, we just arbitrarily choose color e (e.g., the one with the smallest value of ax))) to round x; to 0 and x to 1 for every č + It is trivial to see that the rounding of x actually utilizes a greedy strategy such that for each v, the smallest 2 rounded to 0 while the others are rounded to
a singleton cluster, i.c., cluster
V \ {u} and E L. Since
rounding again ensures the corresponding cost of the integer solution within a constant factor of that of the fractional solution.
In the following theorem, we give our main result that the LP-Clustering algorithm achieves 2. 2.5-approximation in expectation for the Chromatic Correlation Clustering (CCC) problem, which improves the best-known factor of 3 achieved by Klodt al. (25
Theorem 3.1. The LP-Clustering algorithm achieves an approximation of 2.5 in expectation for the CCC problem.
Next Section we prove our main theoretical result Theorem 3.1 where the full proof of core lemma (i.e., Lemma 4.3) requires a non-trivial analysis and can be found in Appendix A
4
Performance Analysis
4.1
Overview
For our randomized rounding approach based on the IP solution, the expected total number of disagreements is B/EwveF d( d(we)], where d(ur) is defined in (I). Similarly, the objective function in

---

[CCC-LP] can be written as EwvE (p(uv), where 1p(ue) denotes the cost on edge ut, i.e.,
((()))
if d(u()) L, if ((wv)) = 7.
1p(ue)
Eue
ECEL
Therefore, to prove Theorem 3.1 it suffices to show that
d(wv)
S
Σ WVEB
Ip(uv).
(8)
WEEE
Since the cost is characterized by each edge ut, according the partitioning of V = OU (UOEL Se). we partition the edge set E into [.] + disjoint subsets Eg, E2 and E.e for E T,, i.e.,
E, = { [wo E E: e EEO
E; {wo E: u Se, St, 2).
E. = {wo E E: u S., Sc). V
Ee). particular, E, the set of edges incident on outliers in O: E; is the set of edges between non-outliers cross two vertex partitions S. and S5, and E, is the set of edges between vertices within the same vertex partition S., In what follows, we establish the relation between LP-Clustering and LP (i.e., the objective function of [CCC-LP)) in terms of the cost on different category edge.
Clearly, = E,
For each edge ue E E., is an inter-cluster edge. By we can get that d(uv) = 1 if ((vv) E L and d(uv) otherwise. Meanwhile, constraint (2) ensures that au x 2 for every u # and d(un) if @(v)) L and (p(uv)
E L when v is outlier. This implies that (p(ue) Iun
otherwise. We immediately have d(uv) s 2 Ip((uv).
For each edge we E E,, it is again an inter-cluster edge, indicating that d(we) if ((uv) E L and d(wv) otherwise. To derive (p(uv), we first present useful property of the fractional solution.
Observation 4.1. Given vertex v E V and any distinct colors C1, 02 E L then x
xx 2 1.
In fact, Observation 4.1 can be easily obtained by contradiction, since otherwise EoEL x < [
which contradicts constraint (4). Denote by e, the vertex color of u such that x
2. Then, by
c(u) Observation 4.1 we have x 2 & for any e o Cu. As a consequence, (p(uv) = Iue alue)
2 ztu
((ue)
>
((wv) E L {cu (p(wv) = Ine o(un)
2 x.
2 1/2 if o(uv) = Cu + cu. and (p(uv) 2 0 otherwise.
This concludes that cl( (wv) I 2 1222p((u)) ip(uv).
Finally, if we show that EEEEvEE, d(wv)] S a.. a E.EE, (p(uv) for every e L and some a 2 combing with the above analysis, we immediately derive an upper bound on the expected cost of our output clustering, i.e.,
E
Σ
d(wo)]
Σ d(wv) + Σ d(uv)
Σ E
Σ d(ww)
E.
NUEE;
CEL.
WOEE E
S 2
Σ (p(uv) +2.
Σ
(p(uv) + a Σ
Σ Ip(uv) cEL uvEE.
u
uVEE.
Sa. Σ 1p(ur).
We thus obtain the following lemma.
Lemma 4.1. Given a 2 2, if the clustering returned by LP-Clustering far every c E L,
Σ d(wv)
S a Σ Ip(uv),
BVEE.
then LP-Clustering achieves approximation guarantee of for chromatic correlation clustering.
Therefore, to get the approximation ratio of LP-Clustering, by Lemma 4.1 we just need to show the relation between E.EEE d(uv)] and Ewver, [p( (p(w)) for each color L.
5

---

4.2 More Detailed Analysis
In what follows, we focus on the elementary analysis over E. for every c L. For each given Se. LP-Clustering iteratively chooses some vertices to create new cluster. Denote by S the unclustered vertex set at the beginning of iteration by Ex the induced edge set by S. containing all the edges with both endpoints in 5% and by C² the cluster created in this iteration. With removing C from S the edges incident on vertices in C i.e., E E {wo E Eec: u, v E St (u C. V C.), are also removed from E.. Then, the number of disagreements of these edges (i.e., E \ E denoted by Dr, can be derived by
D, Σ
1(E)
E
(1 + ((E+t)) +
E
1(
R. ((an)=e
WEE ((w))EA(
WEERE ((uN)=y
where (E) denotes the indicator function of the event &, Eu_,, denotes the event that only one of and is in C. and Eu-o denotes the event that both and are in Co Similarly, the LP cost on E. denoted by Le, can be derived by
Lr
Σ
((( (((u)))
Σ (I(EL-)++((EE))
Σ
WVEE: d(uoJEL
WEE ((av)=y
Let T be the stopping time such that all vertices in S. are clustered after T iterations. Then, we know that Ei Dr = EuvE d(uv) and Σ Le EwrgFF F. Ip(uv), since each edge in E. can only be removed exactly once. If we show that [[D[ a. Lu] for all t. then we know that Ze E, Di=o(aL, D:) is submartingale (i.e., Z s+1
Zz] Z,) and hence B[Zr] 2 B[Zo].
which yields that
Σ
1p(uv)- - E Σ d(uv)
E[Zr] 2 B[Zo] = aE|Lo] E[Do] 2 0.
NOE F
To get [[D2] S. LE it suffices to show its conditional version that D[ S < aB S for all S C Sc. Given St. each vertex E St is picked as the center of the cluster C with a probability
of |sg.. Thus, given an event &, we have
BIL(E) S = Pr(E S =
Σ WESt
Pr[E center = w, St
S
For simplicity, let
Pr(E
center w, St
if ((uv) c, if ((uv) E L {c), if (uvv) =
d(wv] w) ==
Pr(E center = w, St + Priet center = w. St),
Pr(E utv center = w, St),
Moreover, according to the definitions of E and Eu we have
Pr(E
center w. St (1 x un ) + (1 x 2
Pr( center w. S (1 x (1 x-w))-
Note that by setting T = O for each u E St the above equations also hold when w = u or w v. As consequence, we have
(1 x D + x )
if (uvv) = if (duv) E T. (c), if d(uv) = 7.
d(uv w) =
re T
x )1 x(w)
Putting it together, we can express E(D;
S as
E Dr
S
Σ d(uv w))
Σ a.
d(we [w),
S
2|5
WESt uv
where d(uu w) 0 for all u, St. Similarly, let
(1 x ) d(uv)
if (Tu()) E L, if ((uu)) =
Ip(ue) () =
(1 r in x EiEL (1 xtt x:r))

---

Algorithm 2: GreedyVote
Input: An undirected graph G = (V, E) with a color function E' - L, parameters e and m.
Output: A clustering S2........ S and cluster-coloring function d.
Initialize O;
while E * 1 do
Let M be set of m edges sampled with replacement from E;
Let ue be the edge M that maximizes [N (a)
[N(a)U(N)) Create new cluster S = [u, ) by increasing & by one, and remove Sy from V:
while V * 0 do
Let each vertex in Sy. vote for every vertex in V such that vote 0.5 when there is an edge between the two vertices, and an extra 0.5 if the edge color is p(uv); Let V be the vertex with the largest vote count and let be the vote count of w; if 1 S|Sk| then Add w to S₁ and remove w from V; else Break;
Let be the most frequent color of the edges with both endpoints in St. and set (Sk) c Remove edges in (uu Eluu E S from E;
12
foreach V do
14 Create new cluster SІ = {w} by increasing & by one:
15 Let & (Sx) = e where is an arbitrary color L;
return {S1, S2 .... S4}.9 +b
Then, E[L, S can be expressed as
E Le S
Σ weE By
lp(uv w) 2 2
Σ (p(ue | ww)
S
WES,
a.,.EEtt
where (p(uu w) == for all u, w E St Observing that d(wv w) S a Ip(ue hold, thanks the symmetry, consider D(urw) d(uo w)) d(ow u) + d(wn v) whole. That is,
ue w) does not always
D
(d(wv) | w) + d(ww u.) + d(wu u))
Σ
D(uvw).
S u.S.uESE
u.w.west
Similarly, letting L(uew) = 1p(ue w) + 1p(ww u) + (p(wu u). we have
E[L, [
(Lp(wv) w) + 1p(ww u) + lp(wu vi)
L(uvw)-
6
N.T.WES
Therefore, suffices to show that D(urw) S (L(ww).. We thus obtain the following lemma.
Lemma 4.2. Given vertex set Se, it always holds that D(wew) I aL(uvw) for all u, v. St. we have E d(uv)] & a EueeE, Ip(ue)
Finally, the following lemma gives such relation.
Lemma 4.3. For all L and u, v, w St. we have D(wew) < 2.5L(
The proof of Lemma 4.3 is based on a nontrivial case analysis with respect to the the edge color of d(we), @(ew) and ((wu), which can be found in Appendix A Now, putting it together of Lemmas concludes Theorem 3.I
Greedy Clustering Heuristic
For the CCC problem, prior studies have shown that some heuristics without any performance guarantees (e.g., the Deep Cluster algorithm [ and the Greedy Expansion algorithm in (25) can empirically perform much better than the existing algorithms with provable approximation ratios including the Pivot algorithm with the best-known ratio 3. This motivates us design a fast heuristic with better performance in practice, namely the GreedyVote algorithm shown in Algorithm 2 Roughly speaking, Greedy repeats iterations and creates a cluster Sş the kth iteration according to the following two phases of operations:

---

Phase 1 Seed selection (Lines 3 5) Randomly select m candidate edges and pick one of them (denoted by un) to create a "sedd set" S = {u, w};
Phase 2 Vote to grow (Lines 6 I0
Each vertex in the seed set Sy votes for (or scores) every currently unclustered vertex, and the vertex w with the largest vote count is added into Sy if satisfying the condition in Line 9 Repeat this process until there are no qualified vertices.
In the sequel, we provide more detailed explanations on the two phases mentioned above. The purpose of the "seed selection" phase is to identify two neighboring nodes that are "most likely" to be in the same cluster of good solution. To achieve this, we use a metric inspired by the well-known Jaceard Similarity to measure the goodness of and v being clustered together, i.e.,
(M) [M
in Line 4 where (2)) denotes the set of all neighbors of u and Ne(u): : Vc L denotes the set of vertices adjacent to by c-colored edges. Instead of checking every pair of neighboring nodes for this metric, we randomly check m edges and pick the best one among them save running time.
Given the initial seed set constructed by Phase 1, the purpose of the "vote to grow" phase is to identify some qualified vertices and add them into Sy one by one. The rational for judging whether a candidate vertex w should be added into S₃ or not is roughly explained as follows. Let ES(S w)l denote the number of edges with color (Ve L) linking w and any vertex in Sk, and let (rror((s) denote the number of disagreements caused by edges with both endpoints in St. Let u and be the initial two seed vertices in Sy found by Line 4 and suppose that S& is assigned the color of @(wv). Then, not adding w into S₁ would cause at least Er = error (Sx) + EeEL [Ec, w) disagreements, while adding w into S₁. would bring Er² = (rror(Sk) + |S - |Fr(uv)) (Sk. w) disagreements. Clearly, adding w into S₁ would be beneficial only when Er² Eri = | - [E w)l - Ener. E (St; w) S 0, or equivalently (e (St. w) + E.er (Sk, w)] 2 |Sk] Actually, is not hard to verify that the voting mechanism in Line 7 results in the vote count of any candidate vertex ue being equal to 0.5| Fes(v)) (Se, wi] + 0.5 E.Er,
L (S w)). while we replace |S& by c|Sa
in the if-condition of Line 9 to offset the inaccuracy of counting the number of disagreements by considering every vertex individually.
When Phase and Phase 2 described above finishes, no qualified vertices can be added into the current clusters. So GreedyVote creates cluster for each leftover vertex and assign it an arbitrary color in L (Lines 13 15) It can be seen that GreedyVote can be implemented to run in O(E) + A(Vl) time for any constant m, where A the maximum degree of G (see Appendix for a formal proof).
Performance Evaluation
In this section, compare our GreedyVote (GV) algorithm (i.e., Algorithm 2 with six state-of-
the-art algorithms for the CCC problem, including: (1) The Pivot Algorithm 2 (2) The Reduce
and Cluster (RC) Algorithm 33 (3) The Deep Cluster (DC) algorithm 3 (4) The Chromatic Ball
(CB) algorithm 66:: (5) The Greedy Expansion (GE) Algorithm (25]: and (6) The modified greedy expansion (GER) Algorithm (25). Among these algorithms, Pivot and RC have approximation ratios 3 and 5, respectively, and all other algorithms are heuristics. In our experiments, we set e = 0.55 and m = 10 for the GV algorithm, and follow all the parameter settings (if any) of other algorithms according to their proposals. We implement the evaluated algorithms using Python and also use the public code of Klodt al. (25) for implementation. All our experiments are conducted on an Intel(R) Xeon(R) Gold 6126 CPU @ 2.60GHz with 128GB of RAM. Each algorithm is run for 50 times and the average result is reported.
We use ten real-world datasets from different domains in our experiments, as listed in Table Among these datasets, Facebookl, Facebook2, Lastfm and Twitter are social network graphs downloaded from (28), where vertices represent users and edges represent friendships. Each user has several properties representing the "social circles" interested by the user. Following the setting in Anava et al. (3), we assign each social circle a color and set the color of each edge we as the color of u and e's common social circle (if there are multiple common circles then choose an arbitrary one). The
DAWN dataset [ 25 models drug abuse warning network where vertices represent drugs and edges indicate that they were used together before an emergency room visit. Following (25 the color of the edge represents the most common outcome of the visit. The Cooking dataset [3 25
models an ingredient co-occur network where vertices represent ingredients and edges indicate that they co-occur in some recipes. Following [25), the color of the edge represents the most common
8

---

Table 1: Characteristics of the datasets used in the experiments.
Datasets
[V]
L
Facebook1
2871
62334
193
Facebook2
3978
78011
Lastfin
7624
27806
10
Twitter
74402
1003951
99
DAWN
2109
96047
10
Cooking
6714
479921
Stringl
17458
419190
String2
18152
401582
DBLP
73624
835414
100
MAG
80198
237261
11
Table 2: Compare all algorithms the Number of Disagreements (NOD), where the reported data of all algorithms except GV are normalized by those of GV. Lowest values are highlighted in bold.
Datasets
Pivot (
RC 3
DC
3
CB
6
GE 22
GER 25
GV (ours)
Facebook1
1.486
1.283
1.218
1.246
1.015
1.022
38,773
Facebook2
1,419
1.305
1.236
1.220
1.015
1.025
52,164
Lastfm
1.442
1.267
1.267
1.056
1.013
1.034
23,046
Twitter
1,449
1.138
1.134
1.050
1.004
1.007
925,028
DAWN
1.460
1,236
1.253
1.115
0.995
1.035
84,492
Cooking
1.306
1.110
1.092
1.039
1.004
1.001
456435
Stringl
1.535
1,219
1.229
1.072
1.018
1.038
359,202
String2
1,424
1.409
1,214
1,429
1.018
1.017
112,340
DBLP
1.563
1.143
1.103
1.141
1.014
1.040
540,683
MAG
1.568
1.294
1.286
1.078
1.021
1.040
127,383
cuisine. Stringl and String2 12 are networks containing protein-protein interactions, where vertices
represent proteins and edges represent pairs of interacting proteins. Following 66] 255, assign each protein-interaction color and choose an arbitrary color for an edge there are multiple interactions between two proteins. Finally, DBLP and MAG (25) are co-authorship networks where vertices represent authors and each edge is labeled (colored) by the most frequent journal or conference that two authors co-authored.
In Table 2,
we list the Number of Disagreements (NOD) of all the evaluated algorithms, where the reported data of all algorithms except GV are normalized by those of GV. It can be seen that Pivot performs the worst, as it works a color-blind way. Although RC has a worse approximation ratio than Pivot, it performs better than Pivot but worse than CB and DC, while CB and DC have similar performance on NOD. The GER algorithm outperforms the Pivot, RC, CB and DC algorithms on be seen that our GV algorithm
NOD, while GE even performs better than GER. However, outperforms the best baseline GE in the literature on all the datasets except DAWN, while the gap between GV and GE is more than 0.5% the DAWN dataset. This demonstrates the superiority of our GV algorithm on the metric of NOD.
In Table compare the running time of the implemented algorithms. It can be seen that Pivot and GE generally incur the shortest and longest running time, respectively. Compared to GE, GV runs faster all datasets except String2, MAG and Cooking, with the performance gain ranging from 11.0% to 78.8%, while the average performance gain 27%. This can explained by the fact that GV has better time complexity of O + A)Vl) than the O L E + A)V) time complexity of GE, where Ar. is the maximum number of distinct colors of the edges incident to any vertex.
In summary, the experimental results demonstrate that, our Greedy algorithm outperforms all the implemented state-of-the algorithms (with or without performance guarantee) in terms of the objective function value of chromatic correlation clustering, and it also runs significantly faster than GE in general, where GE is the heuristic proposed by Klodt et al. [25] with the known empirical performance on clustering quality.

---

Table 3: Compare all algorithms on the running time (seconds).
Datasets
Pivot 2
RC [
DC
CB
6
GE 25
GER 25
GV (ours)
Facebookl
0.06
0.43
0.64
0.08
0.86
0.80
0.54
Facebook2
0.07
0.55
0.89
0.10
0.93
1.04
0.66
Lastfm
0.03
0.25
0.34
0.06
0.54
0.52
0.41
Twitter
0.87
6.71
8.78
2.16
17.27
10.75
15.00
DAWN
0.06
0.57
1.16
0.12
1.31
1.01
1.18
Cooking
0.24
3.28
4.92
1.17
8.73
4.27
9.54
Stringl
0.23
2.77
4.72
0.78
8.99
5,90
5,85
String2
0.57
3.10
3.35
0.60
2.97
5.36
3.37
DBLP
0.97
6.78
7.03
2.15
18,81
9.74
10.52
MAG
0.48
2.54
2.90
0.66
3.96
4.53
3.99
7
Conclusion
We have revisited the Chromatic Correlation Clustering (CCC) problem, which generalizes the correlation clustering problem and has many important applications machine learning and data mining. For this problem, prior studies have proposed both approximation algorithms with provable performance ratios and heuristics with better practical performance. We have proposed a 2.5- approximation CCC based rounding the solution to linear programming relaxation of CCC, and also a heuristic algorithm based on "greedy voting" strategy. Our theoretical analysis and extensive experiments on real-world datasets demonstrate that our approach outperforms the existing ones both on the theoretical approximation ratio and on the practical performance in terms of time efficiency and clustering quality.
Acknowledgement
Kai Han's work partially supported by National Natural Science Foundation of China (NSFC) under Grant No. 62172384. He Huang's work is partially supported by National Natural Science Foundation China (NSFC) under Grant No. U20A20182 and Grant No. 61873177. The work of Qing Xiu and Shuang Cui is done under the guidance of their supervisor: Kai Han.
References
[1] Substance Abuse and Mental Health Services Administration. Drug abuse warning network, 2011: National estimates of drug-related emergency department visits. HHS Publication (SMA). page 4760, 2013.
[2] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: ranking and clustering. Symposium on Theory of Computing (STOC), pages 684-693, 2005.
[3] Yael Anava, Noa Swigdor-Elgrable and Iftah Gamzu. Improved theoretical and practical guarantees for chromatic correlation clustering. In World Wide Web (WWW), pages 55-65, 2015.
[4] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning (ML), 56(1-3):89-113, 2004.
[5] Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering gene expression patterns. Journal of Computational Biology, 6(3-4):281-29)) 1999.
[6] Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Antti Ukkonen. Chromatic correlation clustering. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 1321-1329, 2012.
[7] Marco Bressan, Nicolò Desa-Bianchi, Andrea Paudice, and Fabio Vitale. Correlation clustering with adaptive similarity queries. In Conference on Neural Information Processing Systems (NeurIPS), pages 12510-12510 2019.
10

---

[8] Mark Bun, Marek Eliás, and Janardhan Kulkarni. Differentially private correlation clustering. In International Conference on Machine Learning (ICML), pages 1136-1146, 2021.
[9] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 524 533, 2003.
[10] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In Symposium on Theory of Computing (STOC), pages 219-228, 2015.
[11] Sunil Chopra and M. R. Rao. The partition problem. Math. Program., 59:87-115, 1993.
[12] Szklarczyk D, Gable AL, Lyon D, Junge A, Wyder S. Huerta-Cepas J, Simonovic M. Doncheva NT, Morris JH, Bork P, Jensen LJ, and Mering CV. String v11: protein pootein-protein association net- works with increased coverage, supporting functional discovery in genome- sedde experimental datasets. https: htttps://cn.stringgbbb org/ January 2019.
[13] Erik D. Demaine and Nicole Immorlica. Correlation clustering with partial information. In International Workshop Randomization and Approximation Techniques in Computer Science (RANDOM). International Workshop on Approximation Algorithms for Combinatorial Opti- mization (APPROX), volume 2764 of Lecture Notes in Computer Science, pages 1-13, 2003.
[14] Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):122-18,, 2006.
[15] Michel Deza, Martin Grötschel, and Monique Laurent. Clique-web facets for multicut polytopes. Math. Oper. Res., 17(4):911-1000, 1992.
[16] Micha Elsner and Eugene Charniak. You talking to me? A corpus and algorithm for conversation disentanglement, In Annual Meeting of the Association for Computational Linguistics (ACL), pages 834-842, 2008
[17] Micha Elsner and Warren Schudy. Bounding and comparing methods for correlation clustering beyond ilp. In Proceedings of the Workshop on Integer Linear Programming for Natural Langauge Processing, page 19-27, 2009.
[18] Aristides Gionis. Heikki Mannila, and Panayiotis Tsaparas. Clustering aggregation. In IEEE International Conference on Data Engineering (ICDE), pages 341-352, 2005.
[19] Martin Grötschel and Yoshiko Wakabayashi. A cutting plane algorithm for a clustering problem. Math. Program., 45(1-3):59-95 1989.
[20] Kai Han, Fei Gui, Xiaokui Xiao, Jing Tang, Yuntian He, Zongmai Cao, and He Huang. Efficient and effective algorithms for clustering uncertain graphs. Proceedings of the VLDB Endowment, 12(6))667-660, 2019.
[21] Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, and Yury Makarychev. Correlation clustering with asymmetric classification errors. In International Conference Machine Learning (ICML), pages 4641-4650, 2020.
[22] Jafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, and Yury Makarychev. Local correlation clustering with asymmetric classification errors. In International Conference Machine Learning (ICML). pages 4677-4686, 2021.
[23] Kaggle. What's 's cooking?
www.:kawwggeecoo/ccccaatttoooooo 2014.
[24] Sanchit Kalhan, Konstantin Makarychev, and Timothy Zhou. Correlation clustering with local objectives. In Conference on Neural Information Processing Systems (NeurIPS), pages 9341-9350, 2019.
[25] Nicolas Klodt, Lars Seifert, Arthur Zahn, Katrin Casel, Davis Issac, and Tobias Friedrich. A color-blind 3-approximation for chromatic correlation clustering and improved heuristics. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 882-891, 2021.

---

[26] Jan-Hendrik Lange, Andreas Karrenbauer, and Bjoern Andres. Partial optimality and fast lower bounds for weighted correlation clustering. In International Conference on Machine Learning (ICML), pages 2898-2907, 2018.
[27] Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang, and Rudy Zhou. Ro- bust online correlation clustering. In Conference on Neural Information Processing Systems (NeurIPS), pages 4688-4699 2021.
[28] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap. stanford edu/data, June 2014.
[29] Andrzej Lingas, Mia Persson, and Dzmitry Sledneu. Iterative merging heuristics for correlation clustering. International Journal of Metaheuristics (IJMileur), 3(2):105-117, 2014.
[30] Vincent Ng and Claire Gardent. Improving machine learning approaches to coreference resolution. In Annual Meeting of the Association for Computational Linguistics (ACL), pages 104-111, 2002.
[31] Jean Pouget-Abass Abadie, Kevin Aydin, Warren Schudy, Kay Brodersen, and Vahab S. Mirrokni. Variance reduction in bipartite experiments through correlation clustering. In Conference on Neural Information Processing Systems (NeurIPS), pages 13288-13298, 2019.
[32] Gregory J. Puleo and Olgica Milenkovic. Correlation clustering and biclustering with locally bounded errors. In International Conference on Machine Learning (ICML), pages 869-877, 2016.
[33] Nimita Shinde, Vishnu Narayanan, and James Saunderson. Memory-efficiet approximation algorithms for max-k-cut and correlation clustering. In Conference on Neural Information Processing Systems (NeurIPS), pages
2021.
[34] Wee Meng Soon, Hwee Tou Ng, and Chung Yong Lim. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521-544, 2001.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See the Abstract and Section [
(b) Did you describe the limitations of your work? [Yes] See the Abstract and Section 6
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section 2
(b) Did you include complete proofs of all theoretical results? [Yes] See section and the supplemental material
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See the supplemental material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see Section 6
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
12

---

(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes] We used public datasets
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "xdeHMK1U5Uj", "reviewer": "Reviewer_77Xk", "summary": "This paper introduces a new 2.5-approximation LP-based algorithm for Chromatic Correlation Clustering improving upon existing state-of-the-art 3.0-approximation result of Klodt et al. The authors also present a two-phase greedy algorithm (without guarantees) and demonstrate empirically that it performs better in terms of clustering found (minimizing number of disagreements) with improved time complexity compared to previous state-of-the-art solution of Klotz et al. \n", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n+ Well-written with clear presentation of main results. \n+ New rounding procedure based on the LP solution with careful analysis leading to 2.5-approximation compared to previous state-of-the-art theoretical result of Klotz et al. \n+ GreedyVote algorithm which performs better empirically compared to previous methods on standard CCC datasets. \n\n## Weaknesses\n- Limited impact for wider Neurips audience - More suited to KDD/WWW possibly?\n  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "icfgcD4Kap", "reviewer": "Reviewer_FWeo", "summary": "The authors propose improved algorithms for the chromatic correlation clustering (CCC), which is a generalization of the correlation clustering problem to multiple labels. The authors present a 2.5 approximation algorithm for this problem based on rounding of a linear program; this bound is tighter than the best-known approximation of 3. The authors also propose a heuristic motivated by their rounding procedure. Experimental results show that the proposed heuristic outperforms existing heuristics and approximation algorithms in minimizing the objective function.", "questions": "Have you implemented LP-Clustering?\nCan you provide experimental results for LP-Clustering?\nHow does the improvement in performance in the objective function translate to a practical benefit? GE and GER have very similar performance.", "limitations": "Yes", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Rigorous theoretical results and an improved approximation bound to a problem that has been of interest in the past 10 years\n- Proposed heuristic outperforms existing alternatives\n- Compelling mix of theoretical and empirical results\n- Supplementary material makes it very easy to reproduce the results in the paper\n\nWeaknesses:\n- Lack of experimental results for the approximation algorithm\n- Impact is somewhat unclear. How does the improvement in performance in the objective function translate to a practical benefit?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QFBRLHTeZC5", "reviewer": "Reviewer_4VF8", "summary": "In this paper, the authors propose two algorithms to tackle the chromatic correlation clustering problem. The first algorithm is a randomized algorithm that outputs a feasible solution to the chromatic correlation clustering problem that is a 2.5-approximation on average. The second procedure is instead a heuristic. The authors provide a theoretical analysis regarding the first method as well as numerical experiments that show the effectiveness of the second algorithm.", "questions": "- Is the analysis in section 4 tight?\n- Why are we guaranteed that Algorithm 2 does not get stuck in the first while loop? In fact, as long as E has at least one edge we stay in the loop, however we need at least m edges to perform all the operations inside of the while loop (and then remove edges from E). It looks to me like the algorithm could arrive at a point where E is not empty but contains less than m edges. This would result in getting stuck in the loop.", "limitations": "The discussion is adequate for this theoretical work. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is overall well-written and easy to read. The authors argue well why this problem is relevant. On the one hand, they improve by 0.5 the previously best ratio for a chromatic correlation clustering approximation algorithm. On the other one, their heuristic algorithm outperforms the current state-of-the-art heuristics on the tested data sets.\n\nThere are four main weaknesses: \n1. The approximation algorithm (which should be the main result of this paper) has not been implemented and tested on the data sets. It is somehow disappointing to only see computational experiments for the heuristic approach. In particular, it would have been nice to see how tight the approximation ratio is in practice.\n2. The statement in the abstract about the approximation algorithm is misleading. The information that the approximation algorithm is a randomized algorithm appears for the first time in Section 3. Moreover, the authors show that the approximation ration is attained in expectation and therefore not always. This is in contradiction to the (deterministic) statements in the abstract and introduction.\n3. The choice of references a bit odd. It would be nice if the vast literature on the clique partitioning/multicut problem was cited. In this literature, the correlation clustering ILP is studied in great detail. See e.g. Groetschel & Wakabayashi, Chopra & Rao, Deza & Groetschel & Laurent, Bandelt et. al. ... (and references therein).\n4. The approximation algorithm (Algorithm 1) is only defined for unweighted complete graphs even if the chromatic correlation clustering problem is defined in general for arbitrary graphs. The authors do not bring up this issue, nor explain how (if?) their approach could be generalized to arbitrary graphs (would the same approximation ratio hold in this case?). Note that here there is no generic cost objective function so that it would suffice to add edges of zero costs, and in this way trivially transform any graph in a complete graph. \n\nBelow are further comments:\n1. The first sentence in the abstract sounds a bit as if Bonchi et. al. had introduced regular CC.\n2. In the last sentence of the abstract, \"efficiency of our proposed algorithms\", I would remove the plural since experiments are included for one of the two algorithms only.\n3. In the first part of the introduction where the problem is introduced informally, a reader could get the impression that a multigraph is considered whenever there exist two types of relationships between two given nodes.\n4. Page 2, line 49: The authors mention several times that CC has an integrality gap of 2, and that therefore this transfers to the chromatic correlation clustering. However, they are actually only talking about approximations obtained by rounding some LP relaxation. If one were not to use LP relaxation in order to derive approximations algorithm, this is not necessarily true anymore. In fact, having an integrality gap of 2 does not imply that there cannot be an approximation algorithm with a better guarantee than 2 in general. The authors should be more open and clear about it.\n5. Page 2, line 72: it would be nice if the meaning of gamma was described with words. From my understanding, an edge labeled with gamma is a \"must cut\" edge. I would suggest the authors to provide this intuition sometime before equation (1).\n6. Page 2 (and everywhere it is stated): CCC-LP cannot be a formulation of the chromatic correlation clustering. In fact, an optimal solution to CCC-LP is in general fractional and cannot correspond to a clustering. An INTEGER solution does, not a fractional. Therefore, if the authors were to add binary constraints to CCC-LP, then they would have a proper formulation of the chromatic correlation clustering. Currently, the LP model they propose, CCC-LP, is just a relaxation of the chromatic correlation clustering, not a formulation.\n7. Page 2, starting from line 82 and then a bit everywhere in the paper: the authors should add the corresponding quantifiers whenever they write x^c_{uv}, x^c_u, x^c_v and similar things. Is it for all c,u,v or just a subset? If so, which?\n8. Advice about Algorithm 1 line 3, observation 4.1 and related issues: I would make it explicit that for a fixed v there exists a unique c such that x_v^c < 1/2, and I would write this remark early on, as soon as the reader reads the algorithm so that it is clear that line 3 is well-defined.\n9. Algorithm 1, line 9: what does \"pivot\" mean? Is it just any node in S_c or does a node need to satisfy specific properties in order to be a pivot?\n10. Page 3, line 101-102: also lines 5,6 in the algorithm provide a partitioning.\n11. Page 3, line 108: I would replace \"rationality\" with something more like \"motivation, intuition, idea behind it...\".\n12. Page 3, lines 109-110: \"as to\" --> \"with respect to\"?\n13. Page 4, first paragraph: Note that the rounding of x_u^c does not affect the objective value. I do not understand what is supposed to be greedy here.\n14. Page 4, line 125: \"until every vertex in S_c is included in a cluster\" from the way it is written it sounds like all these vertices become singletons, while this is not the case since you grow these clusters C_k.\n15. Page 4, lines 130-133: the authors should mention where the proof can be found. Note that the complete proof is not available in this manuscript since part of it has been moved to the appendix.\n16. Page 4, line 145: what is LP? CCC-LP?\n17. Page 5, line 158: write \"some alpha >= 2\" to emphasize that in inequality does not need to hold for every alpha. Observe that if it were for all alphas, then it would hold also for alpha = 2 and we would have a 2-approximation.\n18. Page 5, line 175: it looks to me like E^t_c should be E^t_c \\setminus E^{t+1}_c.\n19. End of page 5: Why is it necessary to argue with submartingales? Here, we are dealing with an expected value of a finite sum and the linearity of the expected value should be all that is necessary for this argument.\n20. Algorithm 2: Why is not Output described here? See Algorithm 1.\n21. Algorithm 2, line 3: \"a set\" not \"the set\". \n22. Algorithm 2: see second question in section \"3. Questions\".\n23. Algorithm 2, line 7: One can get the impression that being a \"seed\" vertex is a special property. But by my understanding every vertex in \"S_k\" is a seed vertex. For me, it would be easier to understand if it just said \"Let each vertex in S_k vote...\".\n24. Algorithm 2: Why are the clusters called S instead of C as above?\n25. Page 7, line 220: I would introduce this notation before so that the reader is not confused when he/she first reads it in the fourth line of the algorithm.\n26. Page 8, line 241: It would be nice to see how the constant m affects the runtime.\n27. Checklist 1b: I do not see a discussion of the limitations neither in the abstract nor in section 6.\n28. Checklist 3c: the error bars are not present in the main paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2SzsQxHkG_e", "reviewer": "Reviewer_7M1G", "summary": "The authors develop a 2.5-approximation algorithm for chromatic correlation clustering (CCC), which is a generalization of the well-known correlation clustering problem introduced in 2012. Their algorithm is LP-based, while it improves the best-known approximation ratio of 3 developed in 2021. A greedy heuristic is also developed and compared against state-of-the-art algorithms on real-world data, showing promising results. ", "questions": "see my comments above.", "limitations": "There doesn't seem to be any negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ the authors develop the best approximation algorithm for chromatic correlation clustering. In contrast with the previous best 3-approximation algorithm, their algorithm is not color blind, which is interesting.  \n+ the experimental evaluation on real-world data is promising (although still preliminary)\n+ the paper is well written and organized\n\n- the theoretical results are not surprising with some of the ideas already presented in [2] and [3]\n- it is not clear whether the analysis of their algorithm is tight. That is, is there an example where their algorithm produces solutions with an approximation ratio of 2.5?\n- the experimental evaluation is not convincing. As most of the algorithms are randomized, the authors should report the variance of their results. As their results are very close to the ones of [20], there might not be much difference, statistically. Also it seems that the parameters of their algorithms have been optimized w.r.t. to the datasets considered (eps and m have been set to 0.55 and 10 respectively), while the default settings for the other algorithms have been used. It is not clear why, the Cooking dataset from [20] has not been included in their experimental evaluation. This does not seem to be a fair evaluation.\n- the code of their algorithm does not seem to be publicly available\n\nsome other comments:\n- “It is noted that CCC is a generalized version of CC and hence also has an integrality gap of 2 as the lower bound for  any achievable approximation ratio for it. “ This claim is ambiguous. It should be noted that this lower bound holds only for the LP-formulation considered in the paper. This claim alone does not prevent the existence of another LP-formulation with smaller integrality gap or a completely different algorithm with approximation guarantee < 2. \n- there seems to be some confusion between randomly and arbitrarily (e.g. line 116)\n- theorem 3.1, it should be stated that the approx is in expectation.\n- which LP-solver has been used in the experimental evaluation?\n\nOverall the paper contains some interesting ideas, while it has strong potential. In particular they provide the best approximation algorithm for CCC. However, I feel that the points discussed above should be addressed before being accepted for publication.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept