Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
Authors: Chenglin Fan
Dahoon Lee
Euiwoong Lee
Venue: NeurIPS 2025 poster ()
Keywords: Correlation Clustering
Chromatic Clustering
Approximation Algorithms
Graph Algorithms
Primary area: theory
TL;DR: This paper improves approximation algorithms for Chromatic and pseudometric-weighted Correlation Clustering

Abstract: Correlation Clustering (CC) is a foundational problem in unsupervised learning that models binary similarity relations using labeled graphs. While classical CC has been well studied, many real-world applications involve more nuanced relationships—either multi-class categorical interactions or varying confidence levels in edge labels. To address these, two natural generalizations have been proposed: Chromatic Correlation Clustering (CCC), which assigns semantic colors to edge labels, and pseudometric-weighted CC, which allows edge weights satisfying the triangle inequality. In this paper, we develop improved approximation algorithms for both settings. Our approach leverages LP-based pivoting techniques combined with problem-specific rounding functions. For the pseudometric-weighted correlation clustering problem, we present a tight $\frac{10}{3}$-approximation algorithm, matching the best possible bound achievable within the framework of standard LP relaxation combined with specialized rounding. For the Chromatic Correlation Clustering (CCC) problem, we improve the approximation ratio from the previous best of $2.5$ to  $2.15$, and we establish a lower bound of $2.11$ within the same analytical framework, highlighting the near-optimality of our result.

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighhe Correlation Clustering
Chenglin Fan
Dahoon Lee Department of Mathematical Sciences Seoul National University Seoul, 08826, South Korea
Department of Computer Science and Engineering Seoul National University
Seoul, 08826, South Korea
fanchenglin@ee ac.kr kr
dahoon46@emu. ac
Euiwoong Lee Computer Science and Engineering Division University of Michigan Ann Arbor, MI 48 109, USA euivoong@umi ch. edu
Abstract
Correlation Clustering (CC) is foundational problem in unsupervised learning that models binary similarity relations using labeled graphs. While classical CC has been widely studied, many real-world applications involve more nuanced relationships, either multi-class categorical interactions or varying confidence levels in edge labels. To address these. two natural generalizations have been proposed: Chromatic Correlation Clustering, which assigns semantic colors to edge labels, and pseudometric-wert weightted Correlation Clustering, which allows edge weights satisfying the triangle inequality. In this paper, we develop improved approximation algorithms for both settings. Our approach leverages L.P-based pivoting techniques combined with problem-specific rounding functions. For the aseudometric-weiihree correlation clustering problem, we present tight 3 approximation algorithm, matching the best possible bound achievable within the framework of standard LP relaxation combined with specialized rounding. For the Chromatic Correlation Clustering (CCC) problem, improve the approximation ratio from the previous best of 2.5 to 2.15, and we establish lower bound 2.11 within the same analytical framework, highlighting the near-optimality of result.
Introduction
Clustering is fundamental task in unsupervised learning, where the goal is to partition set of objects into groups based on their pairwise relationships. One prominent problem in this domain is Correlation Clustering (CC) [5], which models binary similarityddisimilarty between items using an edge- graph: similar pairs are marked with "+' label and dissimilar pairs with a "_". The objective is partition the nodes minimize disagreements- i.e., cases where the partitioning contradicts the edge labels. Due to its flexibility in not requiring predefined number of clusters, CC has been widely utilized in various areas such detecting communities in networks [17], inferring labels from user interactions [ and resolving ambiguous entities (8
Authorr listed in alphahctical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, classic CC models only binary relationships, which is insufficient for many practical applications. For example, in social network, edges may represent diverse relationship types such as "colleague," "classmate," or "family." To address this limitation, Bonchi et al. [00] introduced the Chromatic Correlation Clustering (CCC) problem, which generalizes CC to multi-class categorical settings. In CCC, the input is an edge-colored graph where each color represents a different rela- tionship type. The goal is to cluster the nodes and assign a single color to each cluster such that the number of disagreements- edges whose color does not match the cluster's ' assigned color, or edges that should be separated-is minimized. CCC has wide applications in link classification, entity resolution, and clustering in bioinformatics
[10 30].
In parallel, another important generalization of CC the weighted correlation clustering problem. where edges are associated with weights reflecting the reliability or cost of violating a given label. When weights are unrestricted, obtaining a constant-factor approximation known to hard (under the Unique Games Conjecture) [29]. However, when edge weights form pseudometric- satisfy the triangle inequality-
they inequality-constann constant-factor approximations become feasible. This weighted setting more faithfully models scenarios where not all edges are equally trustworthy.
1.1 Related Works
The Correlation Clustering problem has been widely studied since its introduction [9] and it is known to be APX-hare leading to efforts to develop approximation algorithms. Early work by Bansal, Blum, and Chawla introduced constant-factor approximation algorithm [5]. Charikar et al. [15] improved
this to a 4-approximation using linear programming. Ailon, Charikar, and Newman then introduced the Pivot algorithm (2), which achieved a 3-approximation in linear time. Chawla et al. [16] further improved this to 2.06 using more refined I.P-runniing techniques. More recently, researchers have surpassed the 2-approximation barrier. Cohen-Addad, Lee, and Newman 23 used the Sherali- Adams hierarchy to develop a (1 (1.994 + e)-approximation, while Cohen-Addad et al. 22 proposed preclustering, which improved the approximation (1.73 =). The most recent breakthrough by Cao et al. [1]] introduced the cluster LP, which unifies all known LP relaxations for CC. They show that this can be approximated efficiently using preclustering. achieving (1.437 + a)aaprroximttion the best known guarantee for CC so far. In a more recent work [2]. they introduced a new approach to find feasible solution for the cluster LP in sublinear time.
Chromatic Correlation Clustering is an extension of the classical Correlation Clustering problem, where edge colors represent different types of relationships. Bonchi et al. [10] introduced CCC with a heuristic lacking guarantees. Anava et al. 3 gave a 4-aprroximation via LP rounding, plus two practical methods: Reduce and Cluster (RC, ratio 11) and Deep Cluster (DC). Klodt et al. (30) showed that Pivot [2] yields 3-approximation and that RC achieves 5-approximation. More recently, Xiu et al. (32] developed a 2.5-approximation algorithm for CCC based on linear programming approach, improving upon the previous best-known ratio. They also introduced a greedy heuristic that achieves strong empirical results.
In modern data analysis, correlation clustering must often be performed under computational con- straints such limited memory streaming access to data. Consequently, substantial research has focused on crafting clustering algorithms specifically tailored for dynamic, streaming, online, and
distributed settings
31
25
27
T8
26
19 21
20
1.2 Our Results
Our Contributions. In this work, we present improved approximation algorithms for both the CCC and pseudometric-weighted CC problems.
For the pseudometric- weighted correlation clustering problem. we develop a refined LP- based pivoting algorithm that achieves tight 10 "approximatioon We further prove that this approximation factor is optimal within the standard LP relaxation framework combined advanced rounding functions.
For the Chromatic Correlation Clustering problem, we enhance the LP-based method through a new analysis that yields 2. 1.1pppprooinntinnn improving upon the previous best bound of 2.5 by Xiu et al. [32]. We also establish lower bound of 2.11 within the same analytical framework, underscoring the near-optimality of our approach.

---

Both results are obtained by extending and unifying the triple-base sapee analysis of LP LPProunding schemes. Our work improves the theoretical guarantees for two natural and practically motivated generalizations of correlation clustering and contributes new insights into their structural and algorithmic properties.
Technical Overview. Our algorithms for both Chromatic Correlation Clustering (CCC) and soanddmmttrieweeigheee Correlation Clustering (CC) build on linear programming (LP) relaxations and unified triple-based rounding framework [6 Below, outline the key technical insights:
Sesdoometric-Weiihheee CC: The upper bound for the approximation factor 10/3 is derived using the LP-based Pivot algorithm and a more careful rounding function. For the lower bound, By assuming the existence of an a-approximation and analyzing carefully constructed hard instances, the technique derives necessary conditions that any rounding function must satisfy. These conditions expose inherent conflicts, demonstrating that a cannot be arbitrarily small. particular, the analysis establishes that must be at least 10 The core idea is to identify instance configurations that induce 3' contradiction between the properties required of the rounding functions, ultimately leading to this lower bound on
Chromatic Correlation Clustering (CCC): Building on the LP formulation introduced by Xiu et al. [32], which jointly encodes fractional cluster membership and color assignments. The decoupling of color assignment from cluster formation, allowing us to preserve color structure without entangling it with clustering decisions. Using triple-based analysis, we introduce tailored rounding func- tions-particularly for neutral edges-to better align the rounding behavior with the LP's structure and avoid overcounting. This careful handling of intra-color, conflicting, and neutral edges reduces the approximation factor from 2.5 to 2.15. Our lower bound analysis builds on the general triple-based framework, augmented with structural insights specific the LP-CCC algorithm and its associated LP solution. We carefully define the cost and LP contribution of each edge aype-pattcuularyy neutral edges and construct adversarial instances that expose limitations of any rounding strategy.
Paper Organization. The remainder of the paper is structured follows: Section 2 introduces the problem formulations and IP relaxations for both pseudometric-weighee and chromatic correlation clustering. Section 3 presents our approximation algorithms and outlines their design. Section defines the rounding functions used in the LP-based algorithms. Section provides a detailed triele-based analysis of the approximation guarantees. We conclude with summary and discussion in Section
Preliminaries
The correlation clustering (CC) problem takes as input a signed undirected graph G = (V, = E A E'),, ). where each edge E The objective is to find a partition of the nodes such that the number of disagreements-iee negative edges within the same cluster and positive edges between different clusters is minimized. In other words, the cost of the clustering C is as follows:
E' is assigned a sign '+' or '-", described by E E+ or
obj(C) = Σ Eae +
E -Euv)
E+
WOEE-
where Fan = 0 indicates that there exists C' E such that u, E C, and Fue = otherwise.
CC has a standard LP relaxation leveraging the viewpoint
discrete metric between partitions.
Since the x above satisfies the triangle incquality, we can relax the range x from {0, 1] to [0. 1]. resulting in the following LP:
minimize
Σ Duo + Σ (1- Fuv)
(CC-LP)
WEEE+
uVEE
subject to
Euv + Few 2 Twui
Euv E [0, 1].
(2)
The integrality gap CC-LP on a complete graph known to be [5), which indicates that the standard LP-based algorithm cannot obtain better approximation factor below 2.
3

---

2.1 Pseudomeerri--weihteed Correlation Clustering
The weighted Correlation Clustering problem generalization of the classical CC problem in which each edge is associated with a nonnegative violation cost. Specifically, for each edge we in a complete graph, weight War 2 is provided, and violating the edge's label (either '+ or "-) incurs a penalty of Was- This differs from the standard setting, where all violations incur uniform cost of The weighted variant allows us to encode edge-wis, giiee reliability: when Who large, is more reasonable to follow the given label between u and v.
However, assuming the Unique Games Conjecture, no apppapooronnatooon algorithm exists for the general weighted case [24]. An exception occurs when the weight function satisfies the triangle inequality, i.e., the weights form a pseudometric. In this pseudometric-weigihee setting. constant- factor approximation is known [14]. Following the analysis of Charikar and Gao with L = 2 yields an approximation factor of BhR + +
2 - 1) + 17, since the second type of charge occurs at most L 1 time in the charging scheme. The following is a natural LP relaxation of the weighted CC problem, extending (CC-LP):
minimize
Wuv Luv
Σ R-
Wav (1 Tww)
(wCC-LP)
M+EE+
subject to Due + Tew Twns
Tue E [0, 1].
Here, the variable can be viewed as defining a pseudometric over the vertex set, representing the distance between clusters. Since CC on bipartite graphs has an integrality gap of 3 [16], and is special case of pseudometric-weighhee CC also has an integrality gap of at least 3.
CC, the LP relaxation (wCC-LP) for sreudometric-weighhee
2.2 Chromatic Correlation Clustering Problem
The Chromatic Correlation Clustering problem is variant of the classical CC problem in which each cluster is additionally assigned a color [10]. The input includes complete graph (V, (²) and set of L possible colors, as well as a special color y that denotes that two vertices should not be placed in the same fluster-analopee single cluster color), CCC reduces to the standard CC problem with a complete instance.
negative (*-") edge in the classical CC setting. When L = 1 (i.e.,
The following is linear programming (LP) relaxation of the CCC problem 110
minimize
Σ d(uv)#
((wv) I uv
+
Σ Σa - (
(CCC-LP)
d(uv)=ycEL
subject to
i 2 xn xeg
(5)
Ee + z 2 I
(6)
Σ x = L - 1,
(7)
GET.
T F E [0, 1].
(8)
Here, the variables σ and u are soft assignments:
1 S E [0, 1] represents the fractional assignment of vertex cluster of color c. . 1 2 [0. indicates the fractional agreement between vertices and under color
These variables measure the likelihood of vertices edges being assigned to color, with {1-r. ) )eEL forming a probability distribution over the colors assigned to vertex u, subject to constraints and 88
There also a geometric interpretation of these variables. Consider discrete pseudometric spaces (Ve, de) where V. {ue E VJ. and vertex is connected to u. with link of length z Then,

---

Tur represents the bottleneck distance between u and conditioned on traversing the auxiliary connections ur and v + ve. This view generalizes the classical CC setting, where the cluster-wise discrete metric can be regarded as special case of bottleneck distances.
Since CCC generalizes the standard CC problem, the integrality gap of (CCC-LP) is at least large as that of (CC-LP). which is 2.
3 Approximation Algorithm
Building on the LP formulations introduced in the previous sections, we now present approximation algorithms for both secudoeetri-weiihhee CC and CCC settings. LP-PIVOT (Algorithm[) I extends the classical LP-based pivoting method. The set of edges is divided into 3 subsets: E and E- indicate a set '+' and "-' edges, respectively, while E" indicates a set of edges that always incur cost regardless of the output. The last subset is involved in the CCC case, some of the edges might already be misclassified before the execution. f f and f are rounding functions, which The time complexity of the algorithm is 0([V1))
explained in Section 4
Algorithm 1 LP-PIVOT
Input: Complete graph G V. (2) = E A WEETEE A E
LP solution { ("))
Output: Clustering C of
Pick a pivot
uniformly random.
Set C = [v]. for V [u), do Set Pao as following:
ft (Iav),
w E E+;
Puv
5 (Fuv); (Iuv);
we E
WE E
Update C + CU {u} with probability Puv. end for return C {C} U.-PUPLOOOoO((
The algorithm for the pseudometric-weighhee CC problem is LP-PIvoT((V, E+ u E U 9), {=tte) (din))ve(()) along with selected rounding functions given by equation III The time complex- ity of the algorithm is dominated by solving the LP, which is polynomial in [V].
The algorithm for the CCC problem
D-CCCC(G,e d (Algorithm 2 along with the differently selected rounding functions given by equations [12 and 13). which first partitions the vertices according their LP-derived color distributions, followed by applying the LP-PivOT algorithm. with edge types partitioned by color. The final clustering is obtained by combining the [T] number of outputs from the .P-PPVOT algorithm. The color plassaassiiication step requires ((VV][ time and the following LP-PIVOT step requires at most O(1 V\2) time in total, which are both dominated by the time complexity of solving (CCC-LP). which polynomial in [V] and L].
Rounding Functions
The effectiveness of the LP-PIVOT and LP-CCC algorithms critically depends on the choice of rounding functions used in the clustering process. Rounding functions f+, f- f [0, (0, 1] convert the LP value Tun to the non-selection probability Pue [16). The sign of the edge uv- ur-eetther '+', "_,, 'o determiiess which rounding function is applied. The sign "o" indicates that the edge does not belong to E. The following natural conditions are imposed on any rounding function f:
S(0) = 0, f(1) = I マ > f(x) fv)
(10)
5

---

Algorithm 2 LP-CCC
Input:
Complete graph
V, E
(5))
color function ø - LU {n). LP solution
(rihheV, CEL ce and (ou
cEL. cEL. Output: Clustering C of V, Coloring function C - I.
Initialize 0, S. = 0 for all c E L. for
do if 3 s.t. s.t. 2 < 2. then Update S. + S. {u}.
else
Update c CU Assign {({u}) as arbitrary color.
end
end for
for c E do
Ge (Soz E. - / E2), where E. (
and E E l E defined as partition by color c, 7, [A(c) respectively.
Set C. = L.P-PPVOT(Ge; x l
Update <- Ce.
Assign (bC') = for all C' E C..
end for return C, 4.
Condition 9 not only intuitive but also necessary in certain cases, such as ensuring f+) and (1) I. Other constraints not required in the proof's of Theorems |
and 3 which thus provide
lower bounds on the approximation factors for 'general' rounding functions.
Lemma 1. The LP-PIVOT algorithm achieves a constant-factor approximation in expectation only if f+(0)= 0 and f (1) 1.
Proof. We prove it by contradiction some graph instances.
E 0). The optimal clustering is C = [V}, satisfying obj(C*) = 0, and the optimal LP solution is x = 0.
Case ft (0) 0. Consider G (V,
Suppose f+(0)= 0. Then Pr.LP-PIVOT(C.. + C*] Since obj(C) if and only if C*, this leads to contradiction with the assumption of the expected constant factor approximation.
Case 2 f (1) 1. Consider G = EV (
0 w E w 0). The optimal clustering is C' = ((v) : VV.. The following arguments are similar to Case 1.
Different variants of the CC problem may use different rounding functions. In this paper, we provide rounding functions for both the pseudometric-weighne CC and CCC problems.
4.1 Preudometricc-weihhted Correlation Clustering
We propose the following rounding functions that yield a tight approximation factor:
0,
<< 0.4;
(-))=
J 0.4 < < 0.6;
(11)
1, 2 0.6.
With these functions, the algorithm achieves an expected approximation factor of 10/3. Moreover, no other rounding function can improve this factor, shown in Section 5.1

---

Prevented Regions vs Rounding function
1.0
0.8
0.6
0.4
0.0
0.0
0.2
0.4
0.6
0.8
1.0
x
Figure 1: The region where f violates the 2.15-approinmation for CCC using the proposed f defined in (13)
4.2 Chromatic Correlation Clustering
We further consider the rounding functions f+, f from Chawla al. [16], which yield 2.06- approximation for classical CC, and introduce new function fo to handle o-edges for CCC:
0,
0.19;
[+(x)
2-
0.19 < x < 0.5095;
(xx =x,
(12)
0.5095 1.5095-0.19
2 0.5095,
1.7x, 0.3x + 0.7,
I < 0.5;
(x)
(13)
x 2 0.5.
This function was designed not to intersect with analytic bounds that violate an approximation factor of 2.15, illustrated in Figure From Figure I x refers the LP value corresponding to the pivot edge (i.e., one of the endpoints is a pivot vertex) whose color differs from the color under execution of the pivot-based algorithm, while y refers the corresponding probability of containing the edge in a single cluster. The plot shows the choice of our ʃ and the region of (æ, y) such that: The triple-based analysis in Section 5 cannot guarantee an a 2. apprroooooiiiio if the value x is assigned to the probability of by the rounding function fo.
4.3 Comparison with Prior Work
Pseudometric-weighhee CC: The SLMUUM-PPIOO algorithm, recently proposed by Charikar and Gao [14] for the Ultrametric Violation Distance (UMVD) problem, follows a pivoting-bas rounding strategy applied to an LP relaxation. When the number of distinct pairwise distances between elements, denoted by L, is equal to 2, their algorithm can be viewed as special case of LP-PivoT framework. In this setting, the two distances dj and de correspond the '_' and ' labels, respectively, used in our rounding procedure. The rounding functions used are:
T < O; a < x < 1 - 1 0
0, I < aB;
-(x)=f((0
max x- a3,00
f(x) =
I.
aß < x 1-
1 1-a0
1 x> 1 10...

---

Here, and 3 are fixed algorithmic parameters. For the pseudometric-weeighee CC problem, they are set to a = and 0, and fo is unused.
With triple-based analysis, this choice yields an approximation factor of 6, as shown in the subsec- tion ??.
Chromatic CC:
The LP-based pivoting algorithm by Xiu et al. uses LP values directly as probabilities, corresponding to the following rounding functions:
(*(x) = (z) = x.
This setting is known to achieve an approximation factor 2.5.
Triple-based Analysis
To complete the analysis of the algorithm, it suffices to show that for every triple of vertices u, v, V. the expected cost incurred by the algorithm, denoted ALG(wvro), is at most a factor a times the corresponding LP cost LP(www). That is,
ALG(uvw) S a LP(uvw).
the inequality holds for every triple, then the total expected cost of the algorithm is at most a L.P. To show this, the analysis expresses the expected algorithmic cost and LP cost as averages over all possible pivot choices and vertex triples. Specifically, it defines:
e.cost (u, u): the expected cost of violating constraint (u, v), conditioned pivot e.lp (u, v): the expected LP charge of edge (u, v), conditioned on pivot w.
Here, LP charge is an event that either of the endpoints of the edge is gathered with the pivot vertex, multiplied by the LP value of the edge. Since charging occurs exactly once for each edge, accumulating every charge results in exactly the LP cost.
5.1 Pseudometric-weighted Correlation Clustering
In the CC setting, we use the function C, as defined in [16), to measure the gap:
C C(Ewor Trnas Tarus Puvs Pows Pww) = a LP(uow) - ALG(uuw),
where
ALG(uww) e.cost.((uv) + e.cost.(vw)) + (w.)s L.((ww)) c.lp + e.lpa(ww) + e.ppo
and
Puw Pow) + (1 Puw) Wy E E+: Wu E E
e.cost (u,
(1 Puw) (1 pow),
e.lp (1 PuwPowl (aleaa))rr Fuvs
We E+: ue E E
ProPPow Dnv),
In the weighted CC setting, edge weights further influence the value of C:
C( Tows waas Pavs Pows Pweus Waes Wones Wwn) LP((ww) ALG((uw), with the definition for e.cost and e.lp remains the same; the classical CC corresponds to (Wavs wy:: Wwr) 1,).
Under the pseudometric constraint on weights w, we can reduce the number of cases to consider in the analysís.
Lemma 2. a LP(www) - ALG(uww) 2 0 holds for weight configurations (Ways Monry War) 1,1,1,0,, (1,0,1), 1, 1,)), then the inequality also holds for any configuration (Waey Wonyy Wrnn) satisfying the triangle inequality.

---

Proof. Let all Tuey Tow, Tura: Pav, Pow: Pwn be fixed. ALG(urw) and LP(uew) can be written as ALG(urr) Wav (wv) + Wow e.cost,. + Wwu c.cost,(wa)
and
LP(wvi)) = Wov" (up) + Wonn e.lpa + Wonu - e.lp.(wa).
Therefore, the function aLP(uvw) ALG(uvw) is linear w.rpp (Wuv: Wow Wwn).
Since the set of (Wav: Wow, Wara) that satisfies the triangle inequality forms a convex cone generated
by (1, 1, 0), (1, O. 1), (0, 1,), the function value is nonnegative for all such (Ways Wew: Wwu) if and only if the value is nonnegative for (Wav. Wyw, War) {(1, 0), (1, 1), (0)
This lemma implies that the algorithm achieves an approximation factor of a if all of the following incqualities are satisfied for every possible configuration the triangle uew:
(.v)s + e.cost,, (vw) S a (e.Ipm. (wv) (.lp.(ww)) e.cost (wv) + e.cost, (wv) I (e.Ipw (ww) + e.lp((w))), e.cost, (vw) + e.cost. (wr) S (e.lpa
We obtain a lower bound on the approximation factor of P.PPIVOT by verifying the feasibility of rounding functions that satisfy the above inequalities. To this end, we analyze several configurations of L.P values and edge signs on triangle uow.
In Theorems I and 3 the notation '(a, b, c) with (s1, 82, 83)" denotes (Zuvs Tow, Tww) = (a, b, c),
where each edge sign is given by 81, 82, and 83, respectively.
Theorem 1. The lower bound on the approximation factor of LP-PIVOT psendometric-weiggned correlation clustering is 10/3. The proof is deferred to the Appendix.
Conversely, there exist rounding functions f+, f making the approximation factor of LP-PIVOT by 10/3, providing that the lower bound above is tight.
Theorem 2. The LP-PIVOT algorithum with the rounding function defined in equation 11 yields ///p/pppooiinaiionn algorithu for pseudometric- CC. The proof is deferred to the Appendix.
5.2 Chromatic Correlation Clustering
We analyze the performance of the LP-CCC algorithm. This algorithm begins by assigning each vertex to its majority color based on the LP solution, followed by a pivot-based clustering routine.
Due to the strict majority condition, any edge not included in ( E. must have an LP value of at least 1/2. Thus, the cost incurred by such edges is at most twice their LP contribution 32
Within each color class Se, corresponding to color c, we follow an analysis similar to that of Chawla et al. [16]: edges of color are treated as positive edges (E+), edges of the adversarial color y as negative edges (F: ), and all other edges as neutral (F5)).
For positive and negative edges, the definitions of e.cost and e.lp remain consistent with those in [6 The other three cases, particularly those involving neutral edges, require more careful treatment.
Consider negative edge uv E ==; the LP value is
e. (u, v) = -1 200-2))211 2 "
dEt.
For neutral edge wv ES, the expected cost arises from the event that and are not separated by w, i.e., at least one of them shares cluster with w. The expected cost is thus given by the probability that u and v are not simultaneously separated from w.
The LP contribution in this case is the product this probability with anv where d(uv) af is the
color of edge uv in the input. While o(ue), is not tied to color e, we can still bound it below using

---

Funs For Fon due to LP constraints 32
((vv)
max
(uv)
(((()))
MM max
1
x
2
max
2 Fues
Summarizing the results, we express the expected cost and lower bound on the LP value for fixed pivot w follows:
Paw (1 Pow) + (1 Pro Pww)
E+;
e.costw(u,
Puu) (1 (1- - Puur),
UN E E
(14)
PuwPows
WV E E
(1 PumpPort )areer
E+;
e.lpo 2
(1 Puw [1 x(ue)
uE E E
(15)
PumpPoo) max (3:
F 1
I wru
uu E E
These formulations are central to the analysis. Since a LP ALG is always at least the expression obtained from the LP lower bound, we can prove that this bound is nonnegative.
As in Section 5.1 the algorithm achieves a-approximation if the following inequality holds for all triangles uow:
e.cost (we) + e.cost, (vw) + e.costy (wr) S a (a.(e.lpuuvx) + e.lpu (vw) + e.lp.
This inequality leads to the following result on the approximation guarantee for LP-CCC:
Theorem The approximation factor of LP-CCC for CCC is bigger than 2.11. The proof is deferred to the Appendix.
Analogous to the classical CC setting- where the lower bound and the approximation ratio LP- PIVOT differ by less than 0.04 [16] augmenting the LP rounding with a suitable f yields the following:
Theorem LP-CCC, using the rounding functions 12 and 13 achieves 2.15-pprroximation for Chromatic Correlation Clustering. The proof is deferred to the Appendix.
6 Conclusion
In this work, we studied two important variants correlation clustering: pseudometric-weighter correlation clustering and chromatic correlation clustering For both problems, we developed and analyzed specialized rounding functions that are essential for achieving improved approximation guarantees via the I.P-PIVOT algorithm.
For the pseudometric-weighhe the setting that achieves a 10/ //ppppppoxiiaaiinn and showed that alternative function within our analytical framework can yield better factor. For the chromatic correlation clustering variant, we designed distinct rounding function that respects the constraints imposed by color restrictions and achieves an approximation factor of 2..5. The function is constructed using a piecewise-lineat and leverages careful analysis of triple costs.
setting, we proposed a piecewise-linear rounding function tailored for
a form
Overall, our work highlights the importance of designing principled and variant-specine rounding strategies to extend L.P-baed techniques to structured clustering problems, yielding strong theoretical guarantees.
Acknowledgment
This work by CF and DL was partially supported by the New Faculty Startup Fund at SNU.
10

---

References
[1] R. Agrawal, A. Halverson, K. Kenthapadi, N. Mishra, and P. Tsaparas. Generating labels from clicks. In Proceedings of the 2nd ACM International Conference on Web Search and Data Mining (WSDM), pages 172-181, 2009.
[2] N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: ranking and clustering. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 684-693. ACM, 2008.
[3] Y. Anava, N. Avigdor-Elgrabli, and I, Gamzu. Improved theoretical and practical guarantees for chromatic correlation clustering. In Proceedings of the 24th International Conference World Wide Web (WWW). pages 55 65. ACM, 2015.
[4] S. Assadi and C. Wang. Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 10:1-10:20, 2022.
[5] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Proceedings of the 45th Annual Symposiun on Foundations of Computer Science (FOCS), 2004.
[6] M. Bateni, H. Esfandiari, H. Fichtenberger. M. Henzinger. R. Jayaram, V. Mirrokni, and A. Wiese. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In Proceedings of the 2023 Annual ACM-SIAM SIAM Symposium on Discrete Algorithms (SODA). pages 2677-2727, 2023.
[7] S. Behnezhad, M. Charikar, W. Ma, and L. Tan. Almost 3-approximate correlation clustering in constant rounds. In 63rd IEEE Annual Symposium Foundations of Computer Science (FOCS), pages 720-731, 2022.
[8] S. Behnezhad, M. Charikar, W. Ma, and L. Tan. Single-pass streaming algorithms for correlation clustering. In Proceedings of the 2023 ACM-SIAM Symposium Discrete Algorithms (SODA), pages 819-849, 2023.
[9] A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. Journal of Computational Biology, (05-4):281297,, 1999.
[10] F. Bonchi, A. Gionis, F. Gullo, and A. Ukkomen. Chromatic correlation clustering. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1321-1329. ACM, 2012.
[11] V. Braverman, P. Dharangutte, S. Pai, and V. Shah. Fully dynamic adversarially robust correlation clustering in polylogarithmic update time. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS), 2025.
[12] N. Cao, V. Cohen- S. Li, E. Lee, D. R. Lolck, A. Newman, M. Thorup, L. Vogl. S. Yan, and H. Zhang. Solving the correlation cluster Ip in sublinear time. arXiv preprint arXivv2503.20883. 2024. Available at: https://doo 100 48550/arXiv 25033. 20..2550.2000 20883
[13] D. Chakrabarti, R. Kumar, and K. Punera. A graph-theoretic approach to webpage segmentation. In Proceedings of the 17th International World Wide Web Conference (WWW). pages 377-386, 2008.
[14] M. Charikar and R. Gao. Improved approximations for ultrametric violation distance. In Proceedings of the 2024 ACM-SIAM Symposium Discrete Algoritiuns, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1 1704-1737. SIAM, 2024.
[15] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 7163):600-383, 2005.
[16] S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal lp rounding algorithm for correlation clustering on complete and complete k- k-partite graphs. In Proceedings of the 47th Annual ACM Symposium on Theory Computing (STOC), pages 219 228, 2015.
[17] Y. Chen, S. Sanghavi, and H. Xu. Clustering sparse graphs. In Proceedings of the 25th Annual Conference Neural Information Processing Systems (NeurIPS), pages 2204-2212, 2012.
[18] V. Cdden-Addad, N. Hjuler, N. Parotsidis, D. Saulpic, and C. Schwiegelshohn. Fully dynamic consistent facility location. In Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), 2019.
[19] V. Cohen-Addad, Lattanzi, A. Maggiori, and N. Parotsidis. Online and consistent correlation clustering. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 4157-4177 2022.
11

---

[20] V. Codan-Addad, S. Lattanzi, A. Maggiori, and N. Parotsidis, Dynamic correlation clustering in sublinear update time. In Proceedings the 41st International Conference Machine Learning (ICML), pages 9230-9270, 2024.
[21] V. Cohen-Addad, S. Lattanzi, S. Mitrovie, A. Norouzi-Fard, N. Parotsidis, and Tamnawski. Conelltiin clustering constant many parallel rounds. Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages
2021.
[22] V. Cohen-Addad, E. Lee, Li, and A. Newman. Handling correlated rounding error via preclustering: 1.73 a73-approximation for correlation clustering. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1082 1104, 2023.
[23] V. Cohen-Addad, E. Lee, and A. Newman. Correlation Clustering with Sherali-Adams. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 651-661 Los Alamitos, CA, USA, November 2022. IEEE Computer Society.
[24] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 12)-172-187, 2006. Approximation and Online Algorithms.
[25] H. Fichtenberger, V. Mirrokni, and M. Zadimoghaddam. Correlation clustering in data streams. In Proceedings of the 33rd Annual ACM Symposium on Parallelism in Algorithmms and Architectures (SPAA), 2021.
[26] A. Guo, S. Mitrovic, and S. Vassilvitskii. Distributed correlation clustering. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[27] M. Jaghargh, S. Vassilvitskii, and S. Lattanzi. Scalable coreeltiinn clustering: An empirical study. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 2019.
[28] D. Kalashnikov, Z. Chen, Mchrotra, and R. Nuray- Turan. Web people search via connection analysis. IEEE Transactions on Knowledge and Data Engineering, 20(11):1550-15 1560, 2008
[29] S. Khot. the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 767-775. ACM, 2002.
[30] N. Klodt, L. Seifert, A. Zahn, Casel, Issac, and Friedrich. color- boind-lind 3-approximation for chromatic correlation clustering and improved heuristics. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 882-891. ACM, 2021.
[31] S. Lattanzi and S. Vassilvitskii, Consistent k- cluustrringg In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1975 1984, 2017.
[32] Q Xiu, K. Han, Tang, S. Cui, and H. Huang. Chromatic correlation clustering, revisited. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Informatin Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract and introduction summarizes the main contributions and their
scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Replace by [Yes], [No], or [NA].
Answer: [Yes]
13

---

Justification:
We have discussed pseudometric condition in the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide full proof of each result in appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our results are mainly thcoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
Our results are mainly thcoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.cc/pbllc/guideeee http://oeeubiiisssoooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: Our methods do not need training process.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our results are mainly theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our results are mainly theoretical.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
We follow the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We present theory work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: We present a theory work.
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We present theory work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We present theory work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: We present theory work.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We present theory work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLM all.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy autte:e//eerrrpscccc///ferrreerp for what should or should not be described.
19


Reviews:
[{"review_id": "IMsQEjMYQR", "reviewer": "Reviewer_2HYj", "summary": "The manuscript addresses two variants of the correlation clustering problem. The first variant is clustering correlation with pseudo metric weights. The second variant is chromatic clustering correlation. In both cases the manuscript provides approximation algorithms based on LP relaxations. Both algorithms provide optimal, or near optimal, results (within the LP framework). On the one hand, the novelty and originality of the paper are somewhat limited, in the sense that the methods and arguments are fairly standard, and the authors are able to obtain improved results via a detailed case analysis and very careful selection of certain rounding functions. On the other hand, the theoretical results improve the state of the art, and this is a significant achievement.", "questions": "I would be interested to see answers to the weak points, W1--W3, mentioned above.", "limitations": "I did not find much discussion on limitations. My overall impression is that the authors do not make a significant effort to offer a critical assessment of their work along different dimensions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \nS1. The problem of correlation clustering and its variants have been studied extensively in the literature of theoretical computer science. The current manuscript makes a good improvement of the state of the art results, for the approximation ratio of the problems under study.\nWeaknesses:\nW1. The methods and ideas are not so novel. The improvement has been possible via a detailed case analysis and careful selection of rounding functions. The resulting algorithm may give improved quality guarantee but it is not so novel and not so elegant.\nW2. The methods rely on LP relaxation, which is not so practical. Overall, this is a theory paper and there are no experiments.\nW3. In terms of presentation, it is not always so clear when the authors refer to the problem where all the edges are present (clique) and when the edges may be missing (no + or - signs, or no color labels).", "was_revised": true, "final_justification": "The paper provides improved results for two variants of the correlation clustering problem but I have raised some concerns about the technical novelty and the practicality of the work. The authors have answered to these questions, but their response has not added any information that could convince me to change my opinion. Thus, I keep my recommendation to \"borderline accept\". The positive score is for the theoretical improvements, and the \"borderline\" for the above mentioned weaknesses.", "rebuttal": "Thanks for your thoughtful review. Please find our responses for each question in the following:\n\n> The methods and ideas are not so novel. The improvement has been possible via a detailed case analysis and careful selection of rounding functions. The resulting algorithm may give improved quality guarantee but it is not so novel and not so elegant.\n> \n\n**Response**: This paper differs from previous papers in the following ways:\n\n1. To the best of our knowledge, this paper presents the earliest theoretical inspection particularly on the pseudometric-weighted CC problem, whose significance is discussed in Section 2.1.\\\nMoreover, since the lower bound of the approximation factor for the pivot-based algorithm is a fractional value of 10/3 and is achievable (which is quite unusual), it can also be hypothesized that the integrality gap of the pseudometric-weighted standard LP is also 10/3. This is slightly higher than the integrality gap of 3 for the easier problem: A CC whose presenting edges form a k-partite graph. Providing such an integrality gap of 10/3 would indicate that there are more features from pseudometric compared to ultrapseudometric (i.e., a pseudometric retaining cluster-like features) as a weight that affects the hardness of the LP or the problem.\n\n2. This paper also emphasizes the applicability and the effectiveness of the rounding technique that was explicitly used only for the original CC before (as far as we know). Whenever the triple-based analysis is involved, one can think of fitting the rounding functions, which is simple yet likely to be effective, as in the result of the paper.\\\nDespite its simplicity, it is also important to check the extent of its applicability and to check if the overall procedure is analyzable. For example, while designing the algorithm for CCC, we had to define an additional sign of ‘$\\circ$’ with the corresponding rounding function; while analyzing the performance for pseudometric-weighted CC, the ideas that the tuple $(w_{uv},w_{vw},w_{wu})$ satisfying triangle inequality forms a convex cone and that $\\alpha\\cdot LP-ALG$ is affine with respect to the tuple were crucial in reducing uncountable cases for analysis to only 3 cases consisting extremal rays of the cone.\n\n> The methods rely on LP relaxation, which is not so practical. Overall, this is a theory paper and there are no experiments.\n> \n\n**Response**: Although solving the LP might be a limitation on the practicality, recent work on solving cluster LP implies that the near-optimal solution for the LP can be constructed in $\\tilde{O}(2^{\\text{poly}(1/\\varepsilon)}|V|)$ time using multiplicative weight update (MWU) method if the framework is generalizable to each variant.\\\nMoreover, since the state-of-the-art algorithm for CC uses both pivot-based and cluster-based algorithms, the proposed rounding functions can behave as a good initial choice of rounding functions for the pivot-based algorithm in the mixed algorithm for variants.\n\n> In terms of presentation, it is not always so clear when the authors refer to the problem where all the edges are present (clique) and when the edges may be missing (no + or - signs, or no color labels).\n> \n\n**Response**: Thank you for pointing out the ambiguity. In every case, all the edges are present; missing edges can only be encoded as arbitrary-signed edges with zero weight for pseudometric-weighted CC. We’ve made a clarification regarding the comment."}, {"review_id": "EI7wk1pPX6", "reviewer": "Reviewer_dZ2e", "summary": "This paper studied two variants of correlation clustering, i.e., pseudometric-weighted correlation clustering and chromatic correlation clustering, and proposed specialized rounding functions for these two problems to achieve improved theoretical approximation guarantees.", "questions": "1. What is the time complexity of the proposed algorithm?\n2. Can we extend the proposed algorithms to solve other variants of correlation clustering problems and achieve improved approximation guarantees? If no, what are the difficulties?", "limitations": "The authors did not explicitly pinpoint the limitations of the work.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "S1. The contributions of this work is clearly stated and justified. The comparison with previous work is provided.\n\nS2. The contributions of this work are theoretically solid. Improved approximation guarantees are achieved for Pseudometric-Weighted CC and CCC problems.\n\nW1. The paper is heavy in mathematical notations. There is a lack of intuitive understanding of the rationale of the proposed solution.\n\nW2. No empirical results are provided to validate the theoretical outcome.\n\nW3. Time complexity analysis is not given.", "was_revised": true, "final_justification": "Thank you for the responses. I agree with other reviewers comments and would maintain my rating.", "rebuttal": "Thanks for your thoughtful review. Please find our responses for each question in the following:\n\n> 1. What is the time complexity of the proposed algorithm?\n> \n\n**Response**: Solving the LP takes $\\text{poly}(|V|,|L|)$ time (e.g., $\\tilde{O}(|V|^{6.5}|L|^{2.5})$ using Vaidya's algorithm, or can be made significantly faster by exploiting the sparsity of the constraint matrix in practice).\\\nThe following pivot-based algorithm for pseudometric-weighted CC takes $O(|V|^2)$ time, while for CCC takes $O(|V||L|+\\sum_{c\\in L}|S_c|^2)=O(|V|(|L|+|V|))$ ($S_c$ is a set of vertices such that $c$ is a color of strict majority).\n\nAlthough solving the LP is the bottleneck, this can be addressed if the $\\tilde{O}(2^{\\text{poly}(1/\\varepsilon)}|V|)$ time algorithm via the multiplicative weight update (MWU) method for solving the cluster LP [STOC’25] is generalizable to each variant.\n\n> 2. Can we extend the proposed algorithms to solve other variants of correlation clustering problems and achieve improved approximation guarantees? If no, what are the difficulties?\n> \n\n**Response**: As long as the problem possesses both a standard LP and a theoretically guaranteed pivot-based algorithm, the technique is still valid to make the approximation factor closer to the known integrality gap."}, {"review_id": "w0nQRikJ0s", "reviewer": "Reviewer_HMDC", "summary": "The paper studied polynomial-time algorithms for the pseudo-metric correlation clustering and the chromatic correlation clustering problems. The problems are natural generalizations of the classical correlation clustering problems (with (+) and (-) edges and possibly weights). \n\n- In the pseudo-metric correlation clustering problem, our goal is to put vertices of a given graph $G=(V,E)$ to clusters such that the total number of disagreements, defined as the total *weights* of (+) edges crossing clusters and (-) edges inside the same clusters, are minimized. In general, it is impossible to obtain poly-time algorithms for correlation clustering on weighted graphs under plausible hardness assumptions. The paper instead considered the case when the weights satisfy triangle inequalities and obtained a $10/3$-approximation.\n- In the chromatic CC problem, we are given an associated color with each edge (or a label of (-)), and our goal is to produce clusters such that the total number of color disagreements and (-) edges inside the same clusters is minimized. For this problem, the paper obtained a $2.15$ approximation, which improved upon the previous 2,5 approximation given by XHTCH [NeurIPS’22].\n\nFor both problems, the paper gave lower bounds for the specific algorithms (using the LP integrity gap). \n\nThe core techniques for both problems are linear programming (known in the literature) and new rounding algorithms (which are the main novelty of the paper). With fractional random variables, we can obtain the exact answer in polynomial time for the corresponding linear programs for both problems. To produce an integral solution, one of the popular techniques is the pivot-based rounding: we pick a vertex $w$ uniformly at random, and for each neighboring vertex $u$, we add $u$ to the cluster of $w$ based on the variable $x_{uw}$ and the edge label of $(u,w)$. The main technical contributions of the paper are new rounding functions $f^+$, $f^-$, and $f^\\text{neutral}$ for different edge types. The paper adopted a region-based analysis to show the upper bound for the approximation algorithm, which appears to follow the same idea as in CMSY [STOC’15].", "questions": "Some of the questions were asked when I was flagging the weaknesses. Some additional questions and comments (comments are mostly about presentations):\n- Since your lower bound proofs (for both the pseudometric CC and CCC) are based on integrality gaps, I assume one could not hope for better rounding algorithms based on these LPs, am I correct?\n- If yes, then do you believe the more recent correlation clustering LPs, e.g., the one in “Understanding the Cluster LP for Correlation Clustering” [STOC’24] will be helpful for further improvements?\n- I do not understand Figure 1. Here, what are the x and y axes? What does the figure want to say? I hope it could give some insights for the choice of the intricate constants.\n- Notations $E^\\circ$ and $f^\\circ$ were used before being defined.\n- Missing parentheses for equation (13) on the caption of Figure 1.\n- In the appendix, you used tables to show that by the choice of $\\alpha$, we have $\\alpha\\cdot LP - ALG \\geq 0$. The captions of these tables are “caption” – change this.", "limitations": "The paper is theoretical in nature, and I do not see any immediate negative societal impacts.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I read the first 9 pages of the paper to some fair amount of detail, and I briefly looked into the appendix. My general opinion of the paper is positive: I agree that the pseudometrics CC and CCC are important generalizations for the correlation clustering problem with a wide range of potential applications. The algorithms, while using ideas similar to the ones in the literature, also contain non-trivial technical aspects. I unfortunately did not get a time to check the correctness in detail; a spot check found no issues on this front.\n\nSome weaknesses I want to flag:\n- The paper assumes access to the LP solution, which might not be very efficient in practice. Maybe the author could comment on how fast could one solve the LPs listed in this paper (a recent STOC’25 paper showed “correlation clustering LP” (not the one listed in this paper) could be solved in $O(n \\text{polylog}(n))$ time – can you get similar guarantees?)\n- The concerns about efficiency could also be alleviated by some experiments. Unfortunately, the paper does not contain experiments.\n- I also think the paper could do a much better job on the *accessibility* front. I’m fairly familiar with the topic, so I don’t find many issues reading the results. However, when reading the analysis, I was confused why the charges on the triangles should be $\\sum_{(u,v) \\in E^+}(1-p_{uw}p_{vw})x_{uv}+sum_{(u,v) \\in E^-}(1-p_{uw}p_{vw})(1-x_{uv})$. In fact, the definition of “charge”  was never introduced in this paper, and I do not think the general audience will be able to follow (I had to read the section in CMSY [STOC’15] to remind myself why it’s the case). \n\nOverall, I’m supportive of the paper and will be happy to see it get accepted.", "was_revised": true, "final_justification": "The paper is technically solid and contains enough novel results, as I pointed out in my initial review. The author also engaged in the discussion and answered my questions. I'll be happy to see the paper accepted.", "rebuttal": "Thanks for your thoughtful review. Please find our responses for each question in the following:\n\n> Since your lower bound proofs (for both the pseudometric CC and CCC) are based on integrality gaps, I assume one could not hope for better rounding algorithms based on these LPs, am I correct?\n> \n\n**Response**: We apologize for causing such confusion. The lower bound provides that the pivot-based algorithm with an arbitrary rounding function cannot bypass that value. The best-known integrality gaps for pseudometric-weighted CC and CCC are still 3 and 2, respectively. However, when it comes to the case of pseudometric-weighted CC, since the selected rounding functions meet the lower bound of 10/3, we hypothesize the integrality gap for the LP as 10/3 and leave it as future work.\n\n> If yes, then do you believe the more recent correlation clustering LPs, e.g., the one in “Understanding the Cluster LP for Correlation Clustering” [STOC’24] will be helpful for further improvements?\n> \n\n**Response**: Thank you for your insightful comment. Indeed, both variants can be easily formulated as variants of cluster LP, which would provide an algorithm with an approximation factor less than 2 by accounting for the cluster-based algorithm as well, as long as the (near-)optimal solution for the LP is provided. The main challenge for using the cluster LP framework for those variants is obtaining a near-optimal solution for those new LPs.\n\n> I do not understand Figure 1. Here, what are the x and y axes? What does the figure want to say? I hope it could give some insights for the choice of the intricate constants.\n> \n\n**Response**: $x$ refers to the LP value corresponding to the pivot edge (i.e., one of the endpoints is a pivot vertex) whose color differs from the color under execution of the pivot-based algorithm, while $y$ refers to the corresponding probability not to contain the edge in a single cluster. The plot shows the choice of our $f^\\circ$, and the region of $(x,y)$ such that: The triple-based analysis in Section 5 cannot guarantee an $\\alpha=2.15$-approximation if the value $x$ is assigned to the probability of $y$ by the rounding function $f^\\circ$.\n\nOverall, the computation of the region acts as a primary test for our construction of $f^\\circ$: Once the proposed function doesn’t intersect with the region, we can attempt to validate the approximation factor of $2.15$.\n\nWe’ve added the explanation in Section 4.2 regarding the comment.\n\n> Notations $E^\\circ$ and $f^\\circ$ were used before being defined.\n> \n\n**Response**: Thank you for pointing out the typo. We’ve added a detailed explanation in Section 3 regarding the comment.\n\n> Missing parentheses for equation (13) on the caption of Figure 1.\n> \n\n**Response**: Thank you for pointing out the typo. We’ve revised regarding the comment.\n\n> In the appendix, you used tables to show that by the choice of $\\alpha$, we have $\\alpha\\cdot LP-ALG\\geq 0$. The captions of these tables are “caption” – change this.\n> \n\n**Response**: Thank you for pointing out the typo. We’ve revised regarding the comment."}]

Author rebuttal:

Meta-review: This paper studies two variants of correlation clustering: chromatic version and weighted version. The main results are constant approximation algorithms that run in polynomial time. The variants of the problems are relevant to ML, the result is theoretically solid, and the techniques are based on sophisticated LP-rounding framework. Both results improve existing approximation ratios. The main weakness is that the algorithm can run in high-degree polynomial which may hurt the scalability and applicability in practice.

Overall, this is still a solid contribution that may lead to further studies. The reviews are generally positive, and consensus is basically reached during rebuttal. I recommend to accept the paper.
Decision: Accept (poster)