기술 요약: 계층적 F-클러스터링: 근사 및 난해도

1. 문제 정의

본 논문은 고전적인 계층적 클러스터링(Hierarchical Clustering) 문제의 일반화인 **계층적 F-클러스터링(Hierarchical F-Clustering, HC-F)**을 소개한다. 표준 계층적 클러스터링에서는 데이터셋(가중치 그래프 $G$로 표현됨)이 모든 클러스터가 싱글톤(singleton)이 될 때까지 재귀적으로 분할된다. 솔루션의 품질은 Dasgupta의 목적 함수(Dasgupta's objective)에 의해 측정되며, 이 함수는 계층 구조의 초기 단계(즉, 클러스터 크기가 클 때)에서 유사도가 높은 에지를 절단하는 것에 대해 페널티를 부여한다.

HC-F 변형에서는 재귀적 과정이 특정 그래프 클래스 $\mathcal{F}$에 속하는 클러스터가 나타날 때 언제든 종료될 수 있도록 허용된다. 목표는 여전히 Dasgupta의 목적 함수를 최소화하는 것이지만, 결과적인 클러스터링 트리의 리프 노드(leaf nodes)는 싱글톤이 아니라 $\mathcal{F}$에 속하는 그래프여야 한다. 저자들은 $\mathcal{F}$에 대한 두 가지 자연스러운 선택지를 제시한다:

1. 트리 ($\mathcal{T}$): 비순환(acyclic) 구조를 가진 클러스터.
2. 유계 직경 그래프 ($\mathcal{D}_d$): 직경(임의의 두 노드 사이의 최대 거리)이 최대 $d$인 클러스터.

본 논문은 $\mathcal{F}$가 부분 그래프(subgraph)에 대해 닫혀 있고 다항 시간 내에 인식 가능한 클래스라고 가정한다.

2. 방법론 및 프레임워크

저자들은 자신들이 $\alpha(n)$-well-behaved라고 명명한 그래프 클래스들에 대해 HC-F를 근사하기 위한 일반적인 프레임워크를 제안한다. 핵심 방법론은 계층적 문제를 선형 계획법(LP)에 의해 유도된 일련의 "평면적(flat)" 분할 문제들로 분해하는 "플래트닝(flattening)" 기법에 의존한다.

2.1 $\alpha(n)$-Well-Behaved 조건

그래프 클래스 $\mathcal{F}$가 $\alpha(n)$-well-behaved라는 것은 해당 $p\mathcal{F}$-분할($p\mathcal{F}$-P) 문제가 다음을 충족함을 의미한다:

1. 에지 컷(edge-cut) 변수를 사용하는 자연스러운 정수 선형 계획법(ILP) 정식화(formulation)를 가짐.
2. 일련의 터미널(terminals)에 대해 구조적 술어(structural predicate) $p_\mathcal{F}$가 만족되도록 보장하는 "커버 유형(cover-type)" 제약 조건(예: $\sum_{e \in R} y_e \geq 1$)이 인코딩됨.
3. 다항 시간 내에 풀 수 있는 LP 완화(relaxation) 모델을 가짐.
4. LP 솔루션을 입력받아, LP 비용의 최대 $\alpha(n)$ 배만큼의 비용을 갖는 유효한 컷(cut)을 생성하는 라운딩(rounding) 알고리즘을 가짐.

$p\mathcal{F}$-P의 예시는 다음과 같다:

• 피드백 에지 셋 (Feedback Edge Set, FES): 터미널을 통과하는 사이클을 끊기 위해 에지를 제거함 (트리와 관련됨).
• 최소 멀티컷 (Min-Multicut, MMC): 특정 터미널 쌍들을 분리함 (유계 직경과 관련됨).
• $\rho$-세퍼레이터 ($\rho$-Separator): 터미널을 포함하는 컴포넌트의 가중치가 제한되도록 그래프를 분할함.

2.2 알고리즘 프레임워크

알고리즘은 두 가지 주요 단계로 진행된다:

단계 1: 전처리 및 LP 완화
저자들은 **레벨 기반 변수(level-based variables)**를 사용하여 계층 구조를 인코딩하는 ILP(ILP-HC-F)를 구성한다.

• 변수 $y^t_e$는 레벨 $t$(클러스터 가중치에 대응)에서 에지 $e$가 절단되는지 여부를 나타낸다.
• 변수 $x^t_v$는 레벨 $t$에서 정점 $v$가 $\mathcal{F}$-술어를 만족하는지 여부를 나타낸다.
• 이 정식화는 클러스터들이 충분히 분리되도록 보장하는 스프레딩 메트릭(spreading-metrics) 제약 조건(Charikar와 Chatziafratis의 방식 차용)과 계층 구조를 유지하기 위한 정제(refinement) 제약 조건을 포함한다.
• ILP는 LP(LP-HC-F)로 완화되어 풀리며, 라운딩 절차는 $x^t_v \geq 1/2$인 경우 $x^t_v = 1$로 설정하고 에지 변수 $y^t_e$를 2배로 스케일링하여 부분적으로 정수화된 솔루션을 얻는다.

단계 2: 재귀적 구성
알고리즘은 상향식(top-down)으로 클러스터링 트리를 구축한다:

1. 현재 클러스터 $H$에 대해, 특정 레벨 $t = w(H)/2$에서 $\mathcal{F}$-술어를 만족하는 정점 집합($X_1$)과 만족하지 않는 집합($X_0$)을 식별한다.
2. 컷 1 ($E_F$): $X_1$에 제한된 LP 솔루션을 $p\mathcal{F}$-P 문제의 가이드로 사용한다. $X_1$ 내의 정점들이 술어를 만족하도록 보장하기 위해 $p\mathcal{F}$-P를 위한 $\alpha(n)$-근사 알고리즘을 실행하여 에지를 절단한다.
3. 컷 2 ($E_\rho$): $X_0$에 제한된 LP 솔루션을 $\rho$-세퍼레이터 문제(여기서 $\rho=1/2$)의 가이드로 사용한다. 남은 컴포넌트들이 충분히 작아지도록(부모 가중치의 $2/3$ 이하) 비크리테리온(bicriteria) 근사 알고리즘(비율 $\beta(n) = O(\log n)$)을 사용하여 에지를 절단한다.
4. 절단된 에지들의 합집합은 $H$를 더 작은 컴포넌트들로 분할하며, 이들은 재귀적으로 처리된다.

3. 주요 결과

3.1 근사 알고리즘

주요 정리에 따르면, $\mathcal{F}$가 $\alpha(n)$-well-behaved라면, HC-F에 대해 $O(\alpha(n) + \beta(n))$-근사 알고리즘이 존재한다 (여기서 $\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 근사의 난해도 (Hardness of Approximation)

본 논문은 소 집합 확장 가설(Small Set Expansion Hypothesis, SSEH) 하에서 강력한 근사 불가능성(inapproximability) 결과를 확립한다:

• HC-$\mathcal{T}$와 HC-$\mathcal{D}_d$ 모두 상수 배(constant factor) 내로 근사될 수 없다.
• 증명은 고전적 계층적 클러스터링의 근사 불가능성으로부터 블랙박스 리덕션(reduction)을 사용한다.
  • HC-$\mathcal{D}_d$의 경우, 모든 정점에 직경 $d$를 가진 가젯(gadget)을 부착하여 알고리즘이 해당 가젯을 원래 정점의 대표로 취급하도록 강제한다.
  • HC-$\mathcal{T}$의 경우, 정점에 삼각형(triangle)을 부착한다. 저자들은 최적의 계층적 클러스터링 비용이 최소 선형 배치(Minimum Linear Arrangement, MLA) 비용에 의해 하한선이 결정된다는 성질을 활용하여, 구성된 인스턴스에서도 이 하한선이 유지됨을 보여준다.

4. 의의 및 주장

본 논문은 계층적 F-클러스터링 문제에 대한 최초의 알고리즘적 결과를 제공한다고 주장한다. 주요 기여는 다양한 구조적 클래스에 대해 계층적 클러스터링의 근사를 통합하는 일반적인 프레임워크를 제공하는 것이다. 이는 해당 클래스들이 $\alpha(n)$-well-behaved 조건을 만족할 때 가능하다.

저자들은 자신들의 접근 방식이 단순히 트리나 유계 직경 그래프에 국한되지 않고, 그에 대응하는 평면적 분할 문제(예: 멀티웨이 컷)가 자연스러운 ILP 정식화와 증명 가능한 라운딩 보증을 갖는 모든 클래스에 적용될 수 있음을 강조한다. 또한, 이러한 근사 비율을 $O(\log n)$ 인자 너머로 개선하는 것은 Sparsest Cut이나 Multicut와 같은 근본적인 컷 및 세퍼레이터 문제의 근사 성능에 대한 획기적인 돌파구가 필요할 것임을 언급하며, 현재 이 문제들의 근사 성능을 개선하는 것은 매우 어렵다고 보고 있다.

또한, 본 연구는 실무적인 동기도 강조한다. 즉, 모든 클러스터를 싱글톤으로 강제하는 대신, "단순한" 컴포넌트(예: 파일 시스템의 디렉토리나 이커머스의 상품 카테고리)에서 멈출 수 있는 클러스터링 구조가 필요하며, 이를 통해 의미 있는 세밀도(granularity) 수준을 인코딩할 수 있다는 점을 들어 설명한다.