颜色让聚类更难，新算法突破公平性限制，逼近最优解。
Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering
- 发现颜色干扰是性能下降主因，导致不可回避的额外开销。
- 理论证明两色情况下最优解为2.0967，比标准聚类差0.0367。
- 提出耦合颜色的新算法，实测在公平约束下逼近2.06最优解。
染色相关聚类（CCC）通过为边分配语义颜色，并要求每个簇仅含单一颜色标签来扩展标准相关聚类。与标准CC在完全图上线性规划松弛积分差距为2且存在2.06近似不同，CCC对应的线性规划松弛存在严格下界2.11，现有最佳舍入算法仅达2.15。本文揭示其根源在于跨边颜色干扰：不匹配候选簇颜色的中立边引入了标准CC中不存在的不可约成本，迫使任何独立于颜色的舍入方案承担额外误配惩罚。本文提出四项贡献：首先，建立全局积分差距分解定理，证明任意独立于颜色的舍入算法的差距等于标准CC差距加上一个恒正的染色惩罚Δ(L)；其次，求解相关极小极大问题，导出阶梯公式Δ(L) = ((L-1)/L)Δ_∞，其中Δ_∞≈0.0734，特别地，两色情况下的差距为2.0967，已将CCC与标准CC区分开；第三，提出颜色耦合相关聚类（C4），通过添加有效全局约束∑_c x_uv^c ≥ L−1和相关区间打包舍入策略，使中立边行为类似经典负边，恢复2.06近似性能，绕过无耦合线性规划的2.11下限；第四，对极端实例、真实多关系网络及公平性基准的实验验证理论预测：经验线性规划差距遵循阶梯规律，且C4在公平约束下达到无约束近似比。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。