2025-11-10T02:53:59.476691

Chromatic correlation clustering via cluster LP

Abbasi, An, Byrka et al.

Correlation Clustering is a fundamental clustering problem, and there has been a line of work on improving the approximation ratio for this problem in recent years. A key algorithmic component in these works is the cluster LP. Chromatic Correlation Clustering is an interesting generalization that has also been intensively studied. In light of success of the cluster LP in Correlation Clustering, it would be an interesting question whether the cluster LP can be used in Chromatic Correlation Clustering. We answer this question with affirmatives by presenting a $(2+\varepsilon)$-approximation algorithm for Chromatic Correlation Clustering using a chromatic cluster LP.

academic

色彩相関クラスタリングとクラスタLP

基本情報

論文ID: 2510.13446
タイトル: Chromatic correlation clustering via cluster LP
著者: Fateme Abbasi, Hyung-Chan An, Jarosław Byrka, Changyeol Lee, Yongho Shin
分類: cs.DS (データ構造とアルゴリズム)
発表日: 2025年10月15日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2510.13446

概要

相関クラスタリング(Correlation Clustering)は基礎的なクラスタリング問題であり、近年この問題の近似比の改善に関する一連の研究が行われています。これらの研究における主要なアルゴリズム成分はクラスタLPです。色彩相関クラスタリング(Chromatic Correlation Clustering)は興味深い一般化であり、深く研究されています。相関クラスタリングにおけるクラスタLPの成功を踏まえ、クラスタLPが色彩相関クラスタリングに適用可能かどうかは興味深い問題です。本論文は、色彩クラスタLPを用いた $(2+\varepsilon)$ -近似アルゴリズムを提案することで、この問題に肯定的に答えています。

研究背景と動機

問題背景

相関クラスタリング問題：相関クラスタリングは組合せ最適化と機械学習分野の基礎問題であり、頂点を複数のクラスタに分割し、正辺(+辺)の端点を同じクラスタ内に、負辺(-辺)の端点を異なるクラスタに配置することを目標とします。
色彩相関クラスタリング：相関クラスタリングの一般化であり、各正辺に色ラベルが付与され、同じクラスタ内の頂点は同じ色の辺で接続される必要があります。
研究動機：
- 近年、相関クラスタリングの近似比は継続的に改善され、初期の3-近似から現在の1.437-近似へと向上しています
- クラスタLPはこれらの改善の主要な技術成分です
- 色彩相関クラスタリングの既存手法は色盲アルゴリズム、標準相関クラスタリングへの帰約、または標準LP緩和の使用に限定されています
- 最新の2.15-近似アルゴリズムも依然として帰約法に基づいています

研究意義

クラスタLP技術が色彩相関クラスタリングに直接適用可能かを探索し、より良い近似比を得ることは、理論と実践の両面で重要な意義を持ちます。

核心的貢献

色彩クラスタLPの提案：相関クラスタリングにおけるクラスタLPの自然な一般化を設計し、色彩相関クラスタリング問題に適用します
多項式時間求解：色彩クラスタLPが多項式時間で近似最適に求解可能であることを証明します
2-近似丸め処理アルゴリズム：色彩クラスタLPの可行解を整数解に丸める際の近似比が2であるアルゴリズムを設計します
$(2+\varepsilon)$ -近似アルゴリズム：上記の2つの結果を組み合わせ、色彩相関クラスタリングの $(2+\varepsilon)$ -近似アルゴリズムを得て、従来の2.15-近似を改善します
事前クラスタリング技術：相関クラスタリングの事前クラスタリング(preclustering)概念を色彩の場合に一般化します。これは多項式時間求解の実現に不可欠です

方法の詳細

問題定義

入力：

色集合 $L$
完全グラフ、各辺は+辺または-辺とマークされている
各+辺 $e$ に色 $c_e \in L$ が関連付けられている

出力：

頂点分割 $C$
着色関数 $\chi: C \to L$ 、各クラスタに色を割り当てる

目標：不一致辺の数を最小化します。不一致辺は以下のように定義されます：

-辺の両端が同じクラスタ内にある
+辺の両端が異なるクラスタ内にある
+辺の両端が同じクラスタ内にあるが、クラスタの色が辺の色と一致しない

色彩クラスタLP

核となる線形計画緩和は以下のように定義されます：

$\min \sum_{S\subseteq V,\ell\in L} \left(\frac{|\delta^+(S)|}{2} + |E^{-\ell}[S]|\right) z^\ell_S$

制約条件： $\sum_{S\ni v,\ell\in L} z^\ell_S = 1, \quad \forall v \in V$ $z^\ell_S \geq 0, \quad \forall S \subseteq V, \forall\ell \in L$

ここで：

$z^\ell_S$ は集合 $S$ が色 $\ell$ のクラスタであるかどうかを表します
$\delta^+(S)$ は $S$ を横切る+辺の集合です
$E^{-\ell}[S]$ は $S$ 内の $\ell$ 色+辺以外のすべての辺の集合です

アルゴリズムフレームワーク

ステップ1：事前クラスタリング構築

定数近似アルゴリズムを使用して初期解 $(C^{init}, \chi^{init})$ を取得します
特定の条件を満たす頂点をマークします（パラメータ $\alpha, \beta$ に基づく）
事前クラスタリング $K$ と色割り当て $\chi^{pre}$ を構築します

ステップ2：有界部分クラスタLP

探索空間をサイズが $r = \Theta(\varepsilon^{-12})$ 以下のクラスタに限定します
多項式サイズのLPを構築して求解します

ステップ3：モンテカルロサンプリング

LP解から $\Delta y_\emptyset$ 個の着色クラスタをサンプリングします
Raghavendra-Tan丸め処理アルゴリズムを使用します
最終的な可行解を構築します

主要な技術革新

色彩事前クラスタリング：
- 事前クラスタリング概念を色彩の場合に一般化します
- 最適解は事前クラスタリング構造を尊重する必要があることを証明します
- 許容辺の数を $O(\varepsilon^{-2})\text{opt}$ に制御します
クラスタベースの丸め処理アルゴリズム：
- 専門的な確率的丸め処理プロセスを設計します
- 異なるタイプの辺が不一致になる確率を分析します
- 2倍の近似比を証明します