技術要約：階層的F-クラスタリング：近似と困難性

1. 問題定義

本論文は、古典的な階層的クラスタリング問題の一般化である階層的F-クラスタリング（HC-F）を導入している。標準的な階層的クラスタリングでは、データセット（重み付きグラフ $G$ として表現される）は、すべてのクラスターがシングルトン（単一要素）になるまで再帰的に分割される。解の品質は、階層の初期段階（すなわちクラスターサイズが大きい時）にエッジを切断することにペナルティを課すダスグプタ（Dasgupta）の目的関数によって測定される。

HC-Fの変種では、クラスターが特定のグラフクラス $\mathcal{F}$ に属する場合、再帰プロセスを終了させることが許容される。目的は引き続きダスグプタの目的関数を最小化することであるが、得られるクラスタリング木のリーフノード（葉）は、シングルトンではなく、グラフ $\mathcal{F}$ に属するグラフでなければならない。著者らは、$\mathcal{F}$ の自然な選択肢として以下の2つに焦点を当てている：

1. 木 ($\mathcal{T}$): 非巡回グラフであるクラスター。
2. 有界直径グラフ ($\mathcal{D}_d$): 直径（任意の2ノード間の最大距離）が高々 $d$ であるクラスター。

本論文では、$\mathcal{F}$ は部分グラフの下で閉じ、多項式時間で識別可能であることを前提としている。

2. メソドロジーとフレームワーク

著者らは、**$\alpha(n)$-well-behaved（$\alpha(n)$-良好な挙動を示す）**と呼ぶグラフクラスに対する、HC-Fの近似のための一般的なフレームワークを提案している。コアとなるメソドロジーは、「フラットニング（平坦化）」技術に依拠しており、階層的な問題を、線形計画法（LP）に導かれた一連の「フラットな」分割問題へと分解するものである。

2.1 $\alpha(n)$-well-behaved 条件

グラフクラス $\mathcal{F}$ が $\alpha(n)$-well-behaved であるとは、関連する $p\mathcal{F}$-パーティショニング（$p\mathcal{F}$-P） 問題が以下を満たすことを指す：

1. エッジカット変数を用いた自然な整数線形計画法（ILP）定式化が存在すること。
2. 制約が「カバー型」の制約（例：$\sum_{e \in R} y_e \geq 1$）としてエンコードされており、端末集合に対して構造的述語 $p_\mathcal{F}$ が満たされることを保証していること。
3. 多項式時間で解けるLP緩和が存在すること。
4. LP解を与えられたとき、コストがLPコストの最大 $\alpha(n)$ 倍となる有効なカットを生成する丸めアルゴリズムが存在すること。

$p\mathcal{F}$-P の例には以下が含まれる：

• フィードバック・エッジ集合 (FES): 端末を介したサイクルを断ち切るためにエッジを除去する（木に関連）。
• 最小マルチカット (Min-Multicut, MMC): 特定の端末ペアを切り離す（有界直径に関連）。
• $\rho$-セパレータ: 端末を含むコンポーネントが限定された重みを持つようにグラフを分割する。

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

アルゴリズムは、トップダウン形式でクラスタリング木を構築する。

フェーズ1：前処理とLP緩和
著者らは、レベルベースの変数を用いて階層構造をエンコードするILP (ILP-HC-F) を構築する。

• 変数 $y^t_e$ は、エッジ $e$ がレベル $t$ でカットされるかどうかを示す。
• 変数 $x^t_v$ は、頂点 $v$ がレベル $t$ において $\mathcal{F}$-述語を満たすかどうかを示す。
• この定式化には、クラスターが十分に分離されていることを保証するためのスプレッディング・メトリクス制約（CharikarとChatziafratisによるものを適応）と、階層構造を維持するためのリファインメント（精緻化）制約が含まれる。
• ILPはLP (LP-HC-F) に緩和され、解かれる。丸め手順では、$x^t_v \geq 1/2$ であれば $x^t_v = 1$ と設定し、エッジ変数を $y^t_e$ を2倍にスケールすることで、部分的に整数の解を得る。

フェーズ2：再帰的構築
アルゴリズムは、クラスタリング木をトップダウンで構築する：

1. 現在のクラスター $H$ に対して、特定のレベル $t = w(H)/2$ において $\mathcal{F}$-述語を満たす頂点（$X_1$）と満たさない頂点（$X_0$）を特定する。
2. カット1 ($E_F$): $X_1$ に制限されたLP解を $p\mathcal{F}$-P 問題のガイドとして使用する。$p\mathcal{F}$-P に対する $\alpha(n)$-近似アルゴリズムを実行してエッジをカットし、頂点が $X_1$ において述語を満たすことを保証する。
3. カット2 ($E_\rho$): $X_0$ に制限されたLP解を $\rho$-セパレータ 問題（$\rho=1/2$）のガイドとして使用する。残りのコンポーネントが十分に小さくなる（親の重みの $2/3$ 以下となる）ことを保証するために、二基準近似アルゴリズム（比率 $\beta(n) = O(\log n)$）を用いてエッジをカットする。
4. カットの和集合が $H$ をより小さなコンポーネントへと分割し、それらは再帰的に処理される。

3. 主な結果

3.1 近似アルゴリズム

主要な定理は、もし $\mathcal{F}$ が $\alpha(n)$-well-behaved であるならば、$O(\alpha(n) + \beta(n))$-近似アルゴリズムが HC-F に対して存在することを述べている。ここで $\beta(n) = O(\log n)$ は $\rho$-セパレータ問題の近似比である。

これを具体的なクラスに適用すると：

• 階層的木クラスタリング (HC-$\mathcal{T}$): フィードバック・エッジ集合問題がLP丸めを通じて $O(\log n \cdot \log \log n)$-近似を認めるため、著者らは HC-$\mathcal{T}$ に対して $O(\log n \cdot \log \log n)$-近似を達成している。
• 階層的有界直径クラスタリング (HC-$\mathcal{D}_d$): 最小マルチカット問題が $O(\log n)$-近似を認めるため、著者らは HC-$\mathcal{D}_d$ に対して $O(\log n)$-近似を達成している。

これらは、これらの特定の HC-F 変種に対する最初の多項式時間近似アルゴリズムとして提示されている。

3.2 近似の困難性

本論文は、Small Set Expansion Hypothesis (SSEH) の下での強い近似困難性を確立している：

• HC-$\mathcal{T}$ および HC-$\mathcal{D}_d$ は、いずれも定数倍の近似すら不可能である。
• 証明は、古典的な階層的クラスタリングの近似困難性からのブラックボックス的な還元を用いている。
  • HC-$\mathcal{D}_d$ の場合、すべての頂点に直径 $d$ のガジェットを付加することで、アルゴリズムがそのガジェットを元の頂点の代表として扱うように強制する。
  • HC-$\mathcal{T}$ の場合、頂点に三角形を付加する。著者らは、最適な階層的クラスタリングのコストが Minimum Linear Arrangement (MLA) コストによって下限付けられるという性質を利用し、この下限が構築されたインスタンスにおいても保持されることを示している。

4. 意義と主張

本論文は、階層的F-クラスタリング問題に対する最初のアルゴリズム的結果を提供することを主張している。その主要な貢献は、あるクラスが $\alpha(n)$-well-behaved 条件を満たす限り、階層的クラスタリングの近似を様々な構造的クラスへと統合する一般的なフレームワークである。

著者らは、彼らのアプローチが木や有界直径グラフに限定されるものではなく、対応するフラットな分割問題（マルチウェイカットなど）が自然なILP定式化と証明可能な丸め保証を持つあらゆるクラスに適用可能であることを強調している。また、これらの近似比を $O(\log n)$ の因子の向こう側へ改善することは、現在において改善が困難であると考えられている基本的なカット問題やセパレータ問題（Sparsest Cut や Multicut など）の近似におけるブレイクスルーが必要になるであろうことを指摘している。

また、本研究は実用的な動機も強調している。例えば、すべてのクラスターを強制的にシングルトンにするのではなく、「単純な」コンポーネント（ファイルシステムのディレクトリや電子商取引における製品カテゴリなど）で停止するクラスタリング構造の必要性であり、これにより意味のある粒度のレベルをエンコードできる。