技術要約：階層的クラスタリングにおける個別の公平性

1. 問題の定式化

本論文は、古典的な階層的クラスタリングにおける根本的な限界に対処している。これらの手法は、超距離（ウルトラメトリック）によって定義されるマルチレゾリューション表現（デンドログラム）を生成するが、個々のデータ点の扱いに関する保証を欠いていることが多い。標準的なアプローチは、グローバルな目的関数を最適化するか、貪欲な連結ルールに従うが、これらは局所的な類似性を歪め、特定の個人に不当な影響を与える可能性がある。階層構造は上方へと伝播するため、局所的な近傍における初期の歪みは、より粗い解像度のすべてに影響を及ぼす。

著者らは、**階層的クラスタリングにおける個別の公平性（Individual Fairness in Hierarchical Clustering）**という問題を定式化している。核心となる要件は、類似した個人（距離 $d$ で定義される）が同様に扱われることである。具体的には、以下の2つの条件を満たす超距離表現 $u$ が存在するかどうかを調査している：

1. 支配（Domination）: すべてのペアに対して $u(i, j) \ge d(i, j)$ である（距離が縮小されない）。
2. 局所的公平性（Local Fairness）: 任意の点 $i$ の $k$-近傍（$k$-NN）内において、超距離は元の距離に対して乗法的スラック $\alpha$（および加法的スラック $\beta$）の範囲内に収まる：すべての $j \in N_k(i)$ に対して $u(i, j) \le \alpha d(i, j) + \beta$。

主な目的は、そのような実現可能な超距離が存在するために必要な最小限の乗法的スラック $\alpha^\star(d, k)$ を特徴付けることである。

2. 手法と理論的枠組み

実現可能性の景観（Feasibility Landscape）

著者らは、局所的なリプシッツ制約を尊重する、支配的な超距離を見つけることの実現可能性を分析している。彼らは、**相互的（mutual）**な近傍（$j \in N_k(i)$ かつ $i \in N_k(j)$）と、片方向の近傍を区別している。

主要な理論的結果

• 局所的必要スラック（定理1）: 著者らは、局所的な異質性比 $\alpha^{\text{mut}}_k(d)$ を定義しており、これは相互 $k$-近傍スター内における最大スケール分離を測定するものである。彼らは、実現可能な乗法的スラック $\alpha$ は必ず $\alpha \ge \alpha^{\text{mut}}_k(d)$ を満たさなければならないことを証明した。これにより、鋭い局所的閾値が確立される。もしスラックがこの値未満であれば、公平性は数学的に不可能となる。
• 安定性（定理2）: 最小スラックの閾値は、$k$-近傍の同一性が変化しない場合（$\epsilon$-安定な近傍）、距離の有界な $\ell_\infty$ 摂動の下でリプシッツ安定であることが示されている。
• 構成的十分性（定理3）: 古典的なツリー埋め込み理論（特に [11] の結果）に基づき、著者らは、任意の $n$ 点距離に対して、スラック $\alpha = O(\log n)$ を持つ支配的な超距離が常に存在することを証明した。これは、必要な歪みのグローバルな上限値を提供する。
• 内在的な局所・グローバル間のギャップ（命題1）: 重要な発見は、局所的な構造とグローバルな実現可能性の間の分離である。著者らは、局所的な異質性比が自明な値（$\alpha^{\text{mut}}_k(d) = 1$）であるが、任意の支配的な超距離が $\Theta(\log n)$ の歪みを必要とする、エクスパンダーグラフに基づく距離族を構築した。これは、局所的な一貫性がグローバルな実現可能性を保証しないことを示している。
• 単調性（定理4）: 最小の実現可能なスラック $\alpha^\star(d, k)$ は、近傍サイズ $k$ に関して非減少である。局所的な公平性の制約を強化すること（$k$ を増やすこと）は、要求されるグローバルなスラックを減少させることはない。

アルゴリズム的アプローチ: FCAC

実現可能な超距離を構築するために、本論文は**公平性制約付き凝集クラスタリング（Fairness Constrained Agglomerative Clustering: FCAC）**を提案している。

• メカニズム: FCACは、マージ選択プロセス中に公平性制約を強制することにより、標準的な凝集クラスタリングを修正する。これは、マージ順序を決定する連結スコアと、マージ高さの割り当てを分離する。
• 高さの割り当て: マージ高さは $h(A, B) = \max(\ell(A, B), \max_{i \in A, j \in B} d(i, j))$ と設定され、支配条件（$u \ge d$）が満たされることを保証する。
• 実現可能性チェック: 2つのクラスターをマージする前に、アルゴリズムは、提案された高さがクラスター間の近傍ペアに対して公平性制約（$h \le \alpha d(i, j) + \beta$）に違反していないかどうかを確認する。
• 計算量: アルゴリズムは、最悪の場合 $O(n^3 k)$ 時間で動作する。論文では、基礎となる実現可能性決定問題の正確な計算複雑性を決定することは、依然として未解決の方向であると述べている。

3. 実験結果

著者らは、合成データおよび実世界のデータセット（ガウス混合モデル、ランダムな3-正則グラフ、UCI Census Income、German Credit Data、Iris）を用いて、彼らの理論的主張を検証している。

• 実現可能性の閾値: ガウス混合モデルを用いた実験では、実現可能性における急激な遷移が見られた。最小の実現可能なスラック $\alpha^\star$ は、局所的な相互閾値（5.08）よりも大幅に高い値（17.46）であり、局所的な一貫性がグローバルな歪みの要求を過小評価していることを裏付けている。
• 局所・グローバルのギャップ: ランダムな3-正則グラフにおいて、局所的な比 $\alpha^{\text{mut}}_k(d)$ は 1 のままであったが、最小の実現可能なスラック $\alpha^\star$ は $n$ と共に増加した。これは、命題1で予測された $\Theta(\log n)$ のギャップを経験的に示している。
• スケーリング挙動:
  • 不均質なデータセット（例：Adult）では、$\alpha^\star$ はサンプルサイズ $n$ とともに大幅に増加した。これは、稀な局所的幾何学的違反が蓄積し、グローバルな歪みを増幅させることを示唆している。
  • より安定したデータセット（例：German Credit）では、$\alpha^\star$ は $n$ が増加しても比較的一定であった。
• 障害の飽和: 最小スラック $\alpha^\star$ は、小さな近傍サイズ（$k \approx 3$）で飽和することが観察された。これは、グローバルな超距離による障害が、小規模な幾何学的構成によって決定されることを示している。
• アルゴリズム比較: Adult データセット（$n=800$）において、FCAC (MSTベース) のバリアントは 1.00 のスラックを達成したが、FRT 埋め込み（標準的なツリー埋め込み手法）は、理論的な $O(\log n)$ の保証があるにもかかわらず、平均スラック 67.26 を示した。これは、幾何学を考慮した構成が、実用において汎用的な埋め込み境界を大幅に上回る可能性があることを示唆している。

4. 意義と主張

本論文は、階層的クラスタリングにおける個別の公平性の最初の構造的実現可能性分析を提供すると主張している。その意義は以下の点にある：

1. 公平性の再定義: グローバルな目的関数の最適化から、超距離の厳格な幾何学内における局所的な公平性制約の実現可能性を特徴付けることへと焦点を移した。
2. 内在的なコストの定量化: 公平性のコストは、距離の歪みと本質的に結びついており、特定の距離族に対して、局所的な類似性とグローバルな超距離の実現可能性との間に回避不能な $\Theta(\log n)$ の分離が存在することを特定した。
3. アルゴリズム的貢献: これらの制約を強制する構成的アルゴリズム（FCAC）を提供し、データ依存の手法（特に MST ベースのバリアント）が、汎用的な埋め込み技術と比較して、実用において最適に近いスラックを達成できることを経験的に示した。

著者らは、局所的な条件は必要条件ではあるが、グローバルな実現可能性を決定するには不十分であり、要求される最小スラックはデータの幾何学的構造の根本的な特性であると結論づけている。今後の課題として、実現可能性問題の計算複雑性の特徴付けや、他のマルチスケール表現へのフレームワークの拡張が示唆されている。