pith. sign in

arxiv: 2604.15738 · v1 · submitted 2026-04-17 · 💻 cs.LG

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

Ibne Farabi Shihab , Sanjeda Akter , Anuj Sharma This is my paper

Pith reviewed 2026-05-10 08:15 UTC · model grok-4.3

classification 💻 cs.LG
keywords chromatic correlation clusteringintegrality gapcorrelation clusteringapproximation algorithmsfair clusteringrounding schemesneutral edges
0
0 comments X

The pith

Color assignments in correlation clustering add an irreducible penalty on top of the standard gap, but a coupled method avoids it.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that requiring clusters to have single color labels on colored edges creates extra mismatch costs from neutral edges that standard color-independent roundings must incur. This penalty is isolated in a decomposition theorem that adds a positive chromatic term Delta(L) to the usual correlation clustering gap of 2. The term follows a simple staircase formula solved from a min-max problem over color configurations. The authors then give a color-coupled algorithm that adds a global constraint and correlated rounding to treat neutral edges like ordinary negative edges, recovering the best known 2.06 ratio and the 2.11 lower bound for uncoupled LPs.

Core claim

The integrality gap of any color-independent rounding for chromatic correlation clustering equals the standard correlation clustering gap plus an irreducible chromatic penalty Delta(L) > 0, with Delta(L) = ((L-1)/L) * Delta_infinity where Delta_infinity is approximately 0.0734; Color-Coupled Correlation Clustering bypasses the 2.11 lower bound by adding the valid constraint sum_c x_uv^c >= L-1 and using interval-packing rounding to achieve the 2.06 approximation.

What carries the argument

The chromatic penalty Delta(L) isolated by the Global Integrality Gap Decomposition Theorem, which quantifies the extra cost forced by neutral edges under color-independent rounding.

If this is right

  • The two-color case separates immediately from standard correlation clustering with gap 2.0967.
  • As the number of colors grows, the relative penalty shrinks toward its asymptotic value of 0.0734.
  • C4 matches the unconstrained 2.06 ratio while satisfying the single-color-per-cluster fairness constraint.
  • Empirical LP gaps on extremal and real networks follow the predicted staircase formula.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar irreducible penalties are likely to appear in other fair clustering problems that enforce label consistency across edges.
  • The coupling technique of adding global constraints and joint rounding may apply to multi-relational networks beyond clustering.
  • One could check whether the staircase formula continues to predict gaps on non-complete graphs or under different objective weights.

Load-bearing premise

That every color-independent rounding scheme must pay the full chromatic penalty and that the added global constraint remains valid without introducing new violations.

What would settle it

An explicit finite instance with L colors where some color-independent rounding achieves a gap strictly below 2 + Delta(L), or where the coupled algorithm exceeds 2.06 on the same instance.

Figures

Figures reproduced from arXiv: 2604.15738 by Anuj Sharma, Ibne Farabi Shihab, Sanjeda Akter.

Figure 1
Figure 1. Figure 1: Empirical evaluation on synthetic maximally interfering instances. The standard color [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
read the original abstract

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

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that Chromatic Correlation Clustering (CCC) has an integrality gap for color-independent roundings that decomposes as the standard Correlation Clustering gap plus an irreducible chromatic penalty Delta(L) > 0 obtained by solving an explicit min-max problem, yielding the staircase Delta(L) = ((L-1)/L) * Delta_infinity with Delta_infinity ≈ 0.0734 (hence 2.0967 for L=2). It introduces Color-Coupled Correlation Clustering (C4) via the global constraint sum_c x_uv^c >= L-1 and interval-packing correlated rounding to recover the optimal 2.06-approximation while bypassing the 2.11 lower bound on the uncoupled LP, with experiments confirming the predicted gaps on extremal, real, and fairness instances.

Significance. If the decomposition theorem and min-max solution hold, the work provides a precise explanation for the increased difficulty of CCC over standard CC by isolating the neutral-edge chromatic interference cost, together with a practical C4 algorithm that matches the best-known CC ratio under the added fairness constraints. The explicit staircase formula, the proof of the Global Integrality Gap Decomposition Theorem, and the experimental validation of the predicted gaps on both synthetic extremal instances and real multi-relational networks are notable strengths.

major comments (2)
  1. [Global Integrality Gap Decomposition Theorem] Global Integrality Gap Decomposition Theorem (abstract and §3): the claim that the chromatic penalty is irreducible for every color-independent rounding scheme relies on the min-max problem exactly characterizing the worst-case extra mismatch cost. The formulation appears to restrict to local per-edge rounding functions (cut probability depending only on x_uv); it is not shown that globally correlated but still color-agnostic procedures cannot coordinate decisions across edges to reduce neutral-edge cost below the computed Delta(L), which would make the additive penalty non-irreducible.
  2. [Min-max problem solution] Min-max problem and staircase formula (abstract): Delta_infinity ≈ 0.0734 is obtained numerically. The manuscript should specify the exact parameterization of the min-max, the solver or discretization method, convergence criteria, and any duality or bounding arguments establishing that the reported value is the global optimum rather than a local one; without this the derived two-color gap of 2.0967 and the general staircase remain only approximately supported.
minor comments (2)
  1. [Experiments] Experimental section: while the staircase is said to be validated on extremal and real instances, the manuscript should report the precise protocol for generating the extremal instances, the number of trials, and quantitative measures (e.g., maximum deviation from the predicted Delta(L)) rather than qualitative agreement.
  2. [C4 algorithm] Notation: the global constraint sum_c x_uv^c >= L-1 is introduced as valid for C4; a short proof or reference showing it does not alter the feasible region for the original CCC LP would clarify why the 2.11 lower bound is bypassed.

Circularity Check

0 steps flagged

Derivation chain is self-contained with no circular reductions

full rationale

The paper establishes the Global Integrality Gap Decomposition Theorem by isolating neutral-edge mismatch as an additive chromatic penalty Delta(L) obtained from an independently formulated and solved min-max problem, from which the staircase formula is algebraically derived. The C4 construction adds the explicitly valid global constraint sum_c x_uv^c >= L-1 and applies a new correlated interval-packing rounding that treats neutral edges like classical negative edges, recovering the known 2.06 ratio. None of these steps reduce the claimed gap decomposition, penalty value, or approximation guarantee to the inputs by definition, fitted data, or self-citation; the numerical Delta_infinity is the output of the external min-max computation rather than a tautological renaming or presupposition.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The chromatic penalty Delta(L) rests on a min-max optimization whose numerical optimum supplies the constant 0.0734; the base gap of 2 is taken from prior CC literature.

free parameters (1)
  • Delta_infinity = approximately 0.0734
    Numerical value obtained by solving the min-max problem that defines the irreducible chromatic penalty.
axioms (2)
  • standard math The LP relaxation of standard correlation clustering has integrality gap 2 and admits a 2.06-approximation.
    Used as the base gap to which the chromatic penalty is added in the decomposition theorem.
  • domain assumption Neutral edges create an irreducible mismatch cost for any color-independent rounding scheme.
    This isolation of cross-edge chromatic interference is the key premise of the Global Integrality Gap Decomposition Theorem.

pith-pipeline@v0.9.0 · 5648 in / 1686 out tokens · 54643 ms · 2026-05-10T08:15:05.549248+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Ahmadi, S

    S. Ahmadi, S. Galhotra, B. Saha, and R. Schwartz. Fair correlation clustering. InProc. AISTATS 2020, 2020

    work page 2020

  2. [2]

    Ahmadian, A

    S. Ahmadian, A. Epasto, R. Kumar, and M. Mahdian. Fair correlation clustering revisited. arXiv:2206.05050, 2022

    work page arXiv 2022

  3. [3]

    Ailon, M

    N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and cluster- ing. InProc. 39th STOC, pages 684–693, 2008

    work page 2008

  4. [4]

    Anava, N

    Y . Anava, N. Avigdor-Elgrabli, and I. Gamzu. Improved theoretical and practical guarantees for chro- matic correlation clustering. InProc. 24th WWW, pages 55–65, 2015

    work page 2015

  5. [5]

    Fair correlation clustering meets graph parameters.arXiv:2602.15683, 2025

    Anonymous. Fair correlation clustering meets graph parameters.arXiv:2602.15683, 2025

    work page arXiv 2025

  6. [6]

    Balkanski et al

    E. Balkanski et al. Cost-free fairness in online correlation clustering. InProc. ALT 2025, 2025

    work page 2025

  7. [7]

    Bansal, A

    N. Bansal, A. Blum, and S. Chawla. Correlation clustering. InProc. 45th FOCS, 2004

    work page 2004

  8. [8]

    S. Bera, D. Chakrabarty, N. Flores, and M. Negahbani. Fair algorithms for clustering. InProc. NeurIPS 2019, 2019

    work page 2019

  9. [9]

    Bonchi, A

    F. Bonchi, A. Gionis, F. Gullo, and A. Ukkonen. Chromatic correlation clustering. InProc. 18th KDD, pages 1321–1329, 2012. 12

    work page 2012

  10. [10]

    N. Cao, V . Cohen-Addad, S. Li, E. Lee, D. R. Lolck, A. Newman, M. Thorup, L. V ogl, S. Yan, and H. Zhang. Solving the correlation clustering LP in sublinear time. InProc. 56th STOC, 2024

    work page 2024

  11. [11]

    Charikar, V

    M. Charikar, V . Guruswami, and A. Wirth. Clustering with qualitative information.J. Comput. Syst. Sci., 71(3):360–383, 2005

    work page 2005

  12. [12]

    Chawla, K

    S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and completek-partite graphs. InProc. 47th STOC, pages 219–228, 2015

    work page 2015

  13. [13]

    Chierichetti, R

    F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. InProc. NeurIPS 2017, pages 5029–5037, 2017

    work page 2017

  14. [14]

    Cohen-Addad, E

    V . Cohen-Addad, E. Lee, and A. Newman. Correlation clustering with Sherali-Adams. InProc. 63rd FOCS, pages 651–661, 2022

    work page 2022

  15. [15]

    C. Fan, D. Lee, and E. Lee. Improved approximation algorithms for chromatic and pseudometric- weighted correlation clustering. InProc. NeurIPS 2025, 2025

    work page 2025

  16. [16]

    Klodt, L

    N. Klodt, L. Seifert, A. Zahn, K. Casel, D. Issac, and T. Friedrich. A color-blind3-approximation for chromatic correlation clustering and improved heuristics. InProc. 27th KDD, pages 882–891, 2021

    work page 2021

  17. [17]

    Q. Xiu, K. Han, J. Tang, S. Cui, and H. Huang. Chromatic correlation clustering, revisited. InProc. NeurIPS 2022, 2022. 13 A Exact Derivation of the∆ ∞ ≈0.0734Asymptote We rigorously derive the exact bounding constant for the structural chromatic penalty utilizing continuous optimization over the KKT first-order conditions. Following the decomposition in ...

    work page 2022