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

• arxiv url: http://arxiv.org/abs/2604.15738v1
• Date: Fri, 17 Apr 2026 06:25:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-20 22:00:19.764352
• Title: Why Colors Make Clustering Harder:Global Integrality Gaps, the Price of Fairness, and Color-Coupled Algorithms in Chromatic Correlation Clustering
• Title（参考訳）: 色がクラスタリングを難しくする理由:クロマティック相関クラスタリングにおけるグローバル不整合ギャップ、フェアネスの価格、カラーカップリングアルゴリズム
• Authors: Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma,
• Abstract要約: 相関クラスタリング(CCC)は、エッジにセマンティックカラーを割り当て、各クラスタが単一のカラーラベルを受け取る必要があることによって、相関クラスタリングを拡張する。 我々は、このギャップを困難の原因であるクロスエッジ色干渉を分離することによって説明する。 色が候補クラスタの色と一致しない中性エッジは、標準CCを欠いた既約コストを生み出す。 極端インスタンス、実マルチレルネットワーク、公平性ベンチマークの実験は、この理論を検証する。
• 参考スコア（独自算出の注目度）: 6.908972852063454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.
• Abstract（参考訳）: クロマティック相関クラスタリング(CCC)は、エッジにセマンティックカラーを割り当て、各クラスタに単一のカラーラベルを受け取る必要があることで、相関クラスタリングを拡張する。 LP緩和が完全グラフ上で積分ギャップ2を持ち2.06近似を持つ標準CCとは異なり、CCCの類似LPは厳密な下限2.11を持ち、最もよく知られているLPラウンドアルゴリズムは2.15である。 我々は、このギャップを困難の原因であるクロスエッジ色干渉を分離することによって説明する。 色が候補クラスタの色と一致しない中性エッジは、標準CCから外れた既約コストを発生させ、任意の色に依存しないラウンドリングスキームにさらなるミスマッチペナルティを支払うように強制する。 私たちは4つの貢献をします。 まず、任意の色非依存のCCCラウンドリングアルゴリズムのギャップが標準CCギャップと既約色のペナルティ Delta(L) > 0 と等しいことを示すGlobal Integrality Gap Decomposition理論を証明した。 次に、関連するmin-max問題を解き、Delta(L) = ((L-1)/L) Delta_infinityを導出する。 特に2色ギャップは2.0967であり、CCCと標準CCをL = 2で分離している。 第3に、カラー結合相関クラスタリング(C4)を導入する。 有効な大域的制約sum_c x_uv^c >= L-1 と相関する間隔包装丸めスキームは、中立エッジを古典的な負のエッジのように振る舞い、最適な2.06近似を回復し、未結合LPの2.11下界をバイパスする。 実験的なLPギャップは予測された階段に従っており、C4はフェアネス制約の下での制約のない近似比と一致している。

関連論文リスト

• A Phase-Space Geometric Measure of Magic in Qubit Systems [0.0]
  状態の離散ウィグナー関数から安定化ウィグナー関数の凸包までの l1 距離 C(rho) を導入する。 我々は、その安定化度Gamma(rho)との関係を、Kappa(rho) := (Gamma(rho)-1)/C(rho)を介して研究する。
  論文  参考訳（メタデータ） (2026-03-21T12:33:13Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences [0.0]
  CBLは、一つのグローバルな評価に拡張しない局所的な真理代入を許すことで命題論理を一般化する。 等価なシャーフと排他性グラフのセマンティクスと、フラットリミットで保守的な文脈対応の証明計算を与える。 iid, AR(1)関連, 対向的有界摂動による雑音をモデル化し, ベンジャミン・ホックバーグFDR制御による変分に基づく重要度を提供する。
  論文  参考訳（メタデータ） (2025-10-06T11:34:08Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Screening for a Reweighted Penalized Conditional Gradient Method [20.62129327196916]
  条件勾配法(CGM)は大規模なスパース凸最適化に広く用いられている。 一般化一般化器の疎性獲得特性の調整方法を示す。 本実験では,正則化器の凹凸を調整し,スクリーニング規則のアグレッシブ性を検証する。
  論文  参考訳（メタデータ） (2021-07-02T14:37:37Z)
• Federated Functional Gradient Boosting [75.06942944563572]
  フェデレーション学習における機能最小化に関する研究 FFGB.C と FFGB.L は、特徴分布がより均一になるにつれて収束半径が 0 に縮まる。
  論文  参考訳（メタデータ） (2021-03-11T21:49:19Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• Fair Correlation Clustering [18.00619071013106]
  本稿では,各ノードが色を持つ相関クラスタリング問題に対して,公平性制約の2つのバリエーションを検討する。 本研究では,実世界のデータセットに対する実験的な評価により,公平なクラスタを生成するアルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2020-02-10T02:59:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。