기술 요약: 계층적 클러스터링에서의 개별 공정성 (Individual Fairness)

1. 문제 정식화

본 논문은 고전적인 계층적 클러스터링의 근본적인 한계를 다룬다. 이러한 방법들은 울트라메트릭(ultrametric)에 의해 정의되는 다중 해상도 표현(덴드로그램)을 생성하지만, 개별 데이터 포인트의 처리에 관한 보장은 결여되어 있는 경우가 많다. 표준적인 접근 방식들은 전역적 목적 함수를 최적화하거나 탐욕적 연결 규칙(greedy linkage rules)을 따르는데, 이는 국소적 유사성을 왜곡하여 특정 개인에게 불균형한 영향을 미칠 수 있다. 계층 구조는 상위 단계로 전파되기 때문에, 국소적 이웃에서의 초기 왜곡은 더 거친 해상도의 모든 단계에 영향을 미친다.

저자들은 계층적 클러스트링에서의 개별 공정성 문제를 정식화한다. 핵심 요구사항은 유사한 개인(메트릭 $d$에 의해 정의됨)이 유사하게 취급되어야 한다는 것이다. 구체적으로, 본 논문은 다음 두 가지 조건을 만족하는 울트라메트릭 표현 $u$가 존재하는지 조사한다:

1. 지배성 (Domination): 모든 쌍에 대해 $u(i, j) \ge d(i, j)$ (거리가 축소되지 않음).
2. 국소 공정성 (Local Fairness): 임의의 점 $i$에 대한 $k$-최근접 이웃($k$-NN) 이웃 내에서, 울트라메트릭 거리는 원래의 메트릭에 대해 곱셈적 여유(multiplicative slack) $\alpha$ (및 덧셈적 여여 $\beta$) 내에서 제한된다: 모든 $j \in N_k(i)$에 대해 $u(i, j) \le \alpha d(i, j) + \beta$.

주요 목표는 이러한 실행 가능한 울트라메트릭이 존재하기 위해 필요한 최소 곱셈적 여유 $\alpha^\star(d, k)$를 규명하는 것이다.

2. 방법론 및 이론적 프레임워크

실행 가능성 지형 (Feasibility Landscape)

저자들은 지배적 울트라메트릭이 국소 리프시츠(Lipschitz) 제약 조건을 준수하는지 분석한다. 이들은 상호(mutual) 이웃(여기서 $j \in N_k(i)$ 이고 $i \in N_k(j)$임)과 단방향 이웃을 구분한다.

주요 이론적 결과

• 국소 필요 여유 (정리 1): 저자들은 국소적 이질성 비율 $\alpha^{\text{mut}}_k(d)$를 정의하며, 이는 상호 $k$-최근접 이웃 스타(star) 내에서의 최대 척도 분리(scale separation)를 측정한다. 이들은 실행 가능한 모든 곱셈적 여유 $\alpha$가 $\alpha \ge \alpha^{\text{mut}}_k(d)$를 만족해야 함을 증명한다. 이는 날카로운 국소 임계치를 설정하며, 만약 여유가 이 값보다 낮다면 공정성은 수학적으로 불가능하다.
• 안정성 (정리 2): 메트릭의 유계된 $\ell_\infty$ 섭동 하에서 최소 여유 임계치가 리프시치 안정성(Lipschitz stable)을 가짐을 보여준다 (단, $k$-최근접 이웃의 정체는 변하지 않는 $\epsilon$-안정 이웃 조건 하에).
• 구성적 충분성 (정리 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는 병합 선택 과정 중에 공정성 제약을 강제함으로써 표준 응집 클러스터링을 수정한다. 이는 병합 순서를 결정하는 연결 점수(linkage score)와 병합 높이 할당을 분리한다.
• 높이 할당: 병합 높이는 $h(A, B) = \max(\ell(A, B), \max_{i \in A, j \in B} d(i, j))$로 설정되어, 지배 조건($u \ge d$)이 충족되도록 한다.
• 실행 가능성 체크: 두 클러스터를 병합하기 전에, 알고리즘은 제안된 높이가 클러스터 간의 임의의 이웃 쌍에 대해 공정성 제약($h \le \alpha d(i, j) + \beta$)을 위반하는지 확인한다.
• 복잡도: 알고리즘은 최악의 경우 $O(n^3 k)$ 시간에 실행된다. 저자들은 기저의 실행 가능성 결정 문제의 정확한 계산 복잡도를 결정하는 것이 여전히 열린 과제로 남아 있다고 언급한다.

3. 실험 결과

저자들은 합성 데이터셋 및 실제 데이터셋(Gaussian mixtures, random 3-regular graphs, UCI Census Income, German Credit Data, Iris)을 통해 이론적 주장을 검증한다.

• 실행 가능성 임계치: Gaussian mixtures에 대한 실험은 실행 가능성의 급격한 전이를 보여준다. 최소 실행 가능 여유 $\alpha^\star$는 국소 상호 임계치인 5.08보다 현저히 높은 17.46으로 나타났으며, 이는 국소적 일관성이 전역적 왜곡 요구 사항을 과소평가함을 확인해 준다.
• 국소-전역 간극: Random 3-regular graph에서 국소 비율 $\alpha^{\text{mut}}_k(d)$는 1로 유지되었으나, 최소 실행 가능 여유 $\alpha^\star$는 $n$에 따라 증가하였다. 이는 명제 1에서 예측한 $\Theta(\log n)$ 간극을 경험적으로 입증한다.
• 스케일링 동작:
  • 이질적인 데이터셋(예: Adult)에서 $\alpha^\star$는 샘플 크기 $n$에 따라 크게 증가하였으며, 이는 희귀한 국소적 기하학적 위반이 누적되어 전역적 왜곡을 증폭시킬 수 있음을 시사한다.
  • 보다 안정적인 데이터셋(예: German Credit)에서는 $n$이 증가함에도 불구하고 $\alpha^\star$가 비교적 일정하게 유지되었다.
• 방해 포화 (Obstruction Saturation): 최소 여유 $\alpha^\star$는 작은 이웃 크기($k \approx 3$)에서 포화되는 경향을 보였는데, 이는 전역적 울트라메트릭 방해가 소규모 척도의 기하학적 구성에 의해 결정됨을 나타낸다.
• 알고리즘 비교: Adult 데이터셋($n=800$)에서 FCAC (MST 기반) 변형 모델은 1.00의 여유를 달축한 반면, FRT 임베딩(표준 트리 임베딩 방법)은 FRT의 이론적 $O(\log나)$ 보장에도 불구하고 평균 67.26의 여유를 보였다. 이는 데이터 인지적(geometry-aware) 구축 방식이 실제 환경에서 일반적인 임베딩 경계값보다 훨씬 뛰어난 성능을 낼 수 있음을 시사한다.

4. 의의 및 주장

본 논문은 계층적 클러스터링에서 개별 공정성에 대한 최초의 구조적 실행 가능성 분석을 제공한다고 주장한다. 그 의의는 다음과 같다:

1. 공정성의 재정의: 전역적 목적 함수를 최적화하는 것에서, 울트라메트릭의 엄격한 기하학적 구조 내에서 국소 공정성 제약의 실행 가능성을 규명하는 것으로 초점을 전환했다.
2. 내재적 비용의 정량화: 계층적 표현에서의 공정성 비용이 메트릭 왜곡과 본질적으로 연결되어 있음을 확립하였으며, 특히 특정 메트릭 군에 대해 국소 유사성과 전역적 울트라메트릭 실현 가능성 사이의 피할 수 없는 $\Theta(\log n)$ 분리를 식별하였다.
3. 알고리즘적 기여: 이러한 제약을 강제하는 구성적 알고리즘(FCAC)을 제공하고, 데이터 인지적 방법(특히 MST 기반 변형)이 일반적인 임베딩 기술에 비해 최적에 가까운 여유를 달성할 수 있음을 경험적으로 입증하였다.

저자들은 국소적 조건이 필요조건이긴 하지만, 전역적 실행 가능성을 결정하기에는 불충분하며, 최소 여려 $\alpha^\star$는 데이터의 기하학적 구조에 따른 근본적인 속성이라고 결론짓는다. 향-후 연구로는 실행 가능성 문제의 계산 복잡도를 규명하고, 이를 다른 다중 척도 표현으로 확장하는 것이 제안되었다.