acceptodds
Withdrawn from ICLR 2027

Exclusivity Without Marginal Loss: A Coupled-Rounding Primitive and Full-LP Obstruction for Chromatic Correlation Clustering

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

12 views

Abstract

Chromatic Correlation Clustering (CCC) assigns each cluster one color and penalizes positive edges unless they are co-clustered under their input color. The standard vertex-pair LP already implies cross-color pairwise packing. We turn this property into disjoint potential color claims using one uniform draw per pivot-pair, preserving each selected-color admission marginal. When multiple colors have positive affinity, a claim-respecting projection of independent claims cannot preserve those marginals and exclusivity simultaneously. For the resulting independent pivot-pair algorithm, a feasible three-vertex LP solution makes the true-color third-pivot loss unbounded relative to the positive edge's LP charge; a corrected accounting also includes wrong-color single capture. We analyze a shared-threshold variant that correlates admissions across endpoints: it minimizes the immediate positive-edge loss at fixed marginals, but maximizes negative-edge co-admission. On the witness, every within-pivot coupling preserving the pivot and color laws and the canonical marginals incurs an immediate third-pivot loss of at least one-third of the positive-edge LP charge, exceeding the residual budget of the considered proof route. The barrier extends to every with all colors active. A compact pivot-consistency LP excludes the witness and bounds this immediate loss for the shared-threshold rule; it does not control continuation or yield a new approximation ratio. Alongside a synthetic mechanism check, we report a clustering-quality audit against existing rounding and certified small-instance optima. No improved worst-case approximation factor is claimed.

Primary area:
optimization
Keywords:
chromatic correlation clustering, correlation clustering, LP rounding, approximation algorithms, dependent rounding

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_sZMgOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers the chromatic correlation clustering problem. It suggests a rounding technique for the standard LP relaxation, but argues that it does not provide any improvement on approximation ratios, even over those using the standard LP relaxation. The paper then introduces more constraints to the standard LP relaxation, but it does not give any further improvement, either.

Critical strengths

None

Critical weaknesses

It’s hard for me to say the paper gives some interesting results. It just gives some attempts to resolve some cases, but these attempts do not generalize. Moreover, I believe the paper would benefit a lot from revision. I have to say that it was very complicated for me to understand the paper, and I suspect most researchers with proper background may also find the paper difficult. Please read Questions For Authors, where I list comments and concerns. Considering these points, I don’t think the paper would attract enough interest from the audience of the conference.

Questions for authors
  1. I don’t think the paper is easy to follow because it uses many specific terms without proper definitions, which I don’t feel are standard enough. For example, even in the first four sentences of the abstract, I had little sense of the meaning of the following terms: “vertex-pair LP”, “cross-color pairwise packing”, “selected-color admission marginal”, “positive affinity”, and “claim-respecting projection of independent claims”. The same tendency happens throughout the whole manuscript, but I don’t see it is worth pointing out every single place of this issue I found here.
  2. In Line 51, the paper suddenly drops ∑cyuvc≤1\sum_c y^c_{uv} \leq 1, where yuvc=1−xuvcy^c_{uv} = 1 -x^c_{uv}, while it never defined what xuvcx^c_{uv} means.
  3. The description of Algorithm 1 looks misleading. If we follow what is written there, then we set ℓwvc\ell^c_{wv} only when ww is sampled in Line 5, draw θwv\theta_{wv} in Line 8, and never consider the pair w,vw, v again since ww is certainly removed from UU after this point. Then, it makes little sense how we “pack” IwvcI^c_{wv}, because we visit IwvcI^c_{wv} only once throughout the entire execution of the algorithm.
  4. In Line 181, the paper says the scheme is always feasible (which I understand well-defined) because ∑cℓwvc≤∑cywvc≤1\sum_{c} \ell^c_{wv} \le \sum_{c} y^c_{wv} \le 1, but isn’t it simply because we remove at least the pivot every iteration?
  5. Isn’t Lemma 4.2 satisfied only when we have more condition that ww is the pivot and vv still remains in UU?
  6. In Proposition 4.3, where is the definition of an “independent color-wise claim FcF_c”?
  7. In Line 245, “neutral”?
  8. In Line 259, “endpoint-first charge”?
  9. In Lemma 6.5, “canonical marginals”?
  10. In Figure 2, pp?
  11. In Line 351, swap the last two entries of (ε,(1−ε)/2,(1+ε)/2)(\varepsilon, (1-\varepsilon)/2, (1+\varepsilon)/2)?
Reviewer_Wf8mOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers a new LP rounding scheme for Chromatic Correlation Clustering (CCC). The existing CCC literature revolves around LP relaxations in which, for every vertex and color, there is a fractional variable corresponding to one minus the assignment and for every vertex pair and color, there is a fractional variable xuvcx^c_{uv} that corresponds to the level of separation of the pair uvuv in terms of color cc. The authors observe that the standard LP implies a packing constraint: ∑cxuvc\sum_{c} x^c_{uv} is at least the number of colors minus one. This can be used for a new rounding scheme that, however, does not offer any better approximation guarantees.

Critical strengths

The authors find a new rounding scheme for the LP relaxation of CCC.

Critical weaknesses

The authors observe that the standard LP relaxation implies a packing constraint, which allows another rounding procedure. The authors however are unable to use this to improve on any of the known approximation guarantees, and fail to mention any other benefits of the approach.

Moreover, the introduction of the paper (and also later parts) are almost unintelligible ans partially errorneous. For example, the first sentence of the abstract reads "[CCC] assigns each cluster one color and penalizes positive edges unless they are co-clustered under their input color". The authors fail to explain what CCC even is, mentions that it penalizes something without really specifying the output or the objective, and forgets to mention that negative edges within a cluster are also penalized. The next two sentences go on and (in a very compactified way) try to explain the authors' rounding scheme, which is absolutely unintelligible at this point. The issues with legibility continue from here on.

Questions for authors

None.

Reviewer_nCL6OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies Chromatic Correlation Clustering (CCC), a generalization of standard correlation clustering where each positive edge also has an associated color. The objective is to find a partition that minimizes violations of both the positive and negative relationships and the color requirements, i.e., each cluster is assigned a single color, and a positive edge is satisfied only if its endpoints belong to a cluster of that color.

The paper's main contention is that existing LP-based rounding approaches do not explicitly exploit the relationship between different colors already captured by the standard LP. In particular, the authors argue that independently testing different colors can lead to multiple colors claiming the same pair, even though a pair can belong together under only one color. To address this, they propose a coupled-rounding scheme using a single uniform random variable per pivot–vertex pair and disjoint intervals for different colors, which avoids such conflicting potential claims while preserving the original probabilities. The authors then investigate whether their rounding scheme can support a 2.06-approximation analysis for CCC using the standard LP, improving upon the cited 2.15 ratio (Fan et al., 2025) and matching the ratio previously achieved for standard correlation clustering using LP rounding (Chawla et al., 2015). However, they identify an issue with the independent vertex-admission decisions in their proposed pivot-based rounding scheme, which can lead to large disagreement probabilities even when the corresponding LP cost is very small. They construct a counterexample showing that a particular bound needed for their proposed 2.06-approximation analysis cannot hold over all feasible standard-LP solutions, and investigate correlated rounding and stronger LP constraints as possible ways to address this issue.

Critical strengths

None.

Critical weaknesses

W1. The paper is written in an extremely dense manner, especially for readers who are not familiar with the existing literature on chromatic correlation clustering. Notation and terminology are often introduced without any context, making it very hard to follow.

W2. The motivation and significance of the technical contributions are not sufficiently clear. While the paper investigates limitations of standard-LP rounding, it is difficult to understand how these results relate to existing approximation algorithms, particularly since stronger approximation guarantees are already known using other LP relaxations. The paper would benefit from a clearer explanation of what limitation of existing methods is being addressed and why the proposed rounding framework is of independent interest.

Questions for authors

Please respond to W1 and W2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.