[기술 요약] 그래프의 Normalized Cut을 위한 Expander Hierarchy

1. 문제 정의 (Problem Statement)

그래프 클러스터링(Graph Clustering)의 핵심 목표 중 하나는 그래프를 여러 개의 부분 집합으로 나누되, 각 집합 내부의 연결성은 높고 집합 간의 연결성은 낮게 만드는 것입니다. 이 중 **Normalized Cut (N-cut)**은 클러스터의 크기 불균형 문제를 해결하기 위해 각 클러스터의 부피(volume)로 경계(border)를 나누어 정규화하는 매우 인기 있는 목적 함수입니다.

하지만 N-cut 문제는 NP-hard이며, 기존의 주요 해결 방식들은 다음과 같은 한계가 있습니다:

• Spectral Methods (스펙트럴 방법): 라플라시안 행렬의 고유벡터(eigenvector)를 계산해야 하므로 대규모 그래프에서 메모리 사용량과 계산 시간이 기하급수적으로 증가합니다.
• Multilevel Partitioning (다단계 분할): METIS나 KaHiP 같은 도구들은 균형 잡힌 분할(balanced cut)에는 강하지만, N-cut 목적 함수를 직접 최적화하지는 않습니다.
• Expander Decomposition (익스팬더 분해): 이론적으로는 강력하지만, 기존 알고리즘들은 최대 유량(maximum flow) 문제에 의존하여 실제 대규모 그래프에 적용하기에는 너무 느렸습니다.

2. 방법론 (Methodology)

본 논문은 이론적 보장과 실용적 효율성을 동시에 잡기 위해 새로운 알고리즘인 XCut을 제안합니다. XCut은 크게 세 단계로 구성됩니다.

A. Random-Walk 기반 Expander Decomposition (핵심 혁신)

기존의 무거운 유량 기반 알고리즘 대신, **무작위 보행(Random Walk)**을 사용하여 익스팬더 분해를 수행합니다.

• 원리: 익스팬더(연결성이 좋은 그래프)에서는 무작위 보행이 빠르게 수렴(convergence)한다는 점을 이용합니다. 보행이 빠르게 수렴하지 않는다면, 그 그래프에는 연결성이 낮은(low conductance) 지점이 존재한다는 뜻이므로 이를 찾아 분할합니다.
• 효율성: 유량 계산 없이 선형 시간에 가까운 속도로 동작하며, 이를 통해 그래프를 계층적 구조인 **Expander Hierarchy (Tree Flow Sparsifier)**로 변환합니다.

B. Sparsifier 상에서의 해결 (Solving on the Sparsifier)

생성된 계층적 트리 구조(Sparsifier)는 원본 그래프의 구조를 보존하면서 크기는 훨씬 작습니다. 이 트리 위에서 N-cut을 해결하기 위해 두 가지 휴리스틱을 사용합니다:

1. Greedy (탐욕법): 매 단계에서 N-cut 값을 최소로 만드는 간선을 선택합니다.
2. Dynamic Programming (동적 계획법): 트리의 구조를 활용하여 최적의 분할을 찾습니다. (실험 결과 Greedy가 더 효율적임이 밝혀짐)

C. Refinement (정제 단계)

트리에서 찾은 초기 해를 원본 그래프로 다시 매핑(uncoarsening)하면서, 각 계층을 내려갈 때마다 국소적 탐색(local search)을 통해 해를 지속적으로 개선합니다.

3. 주요 기여 (Key Contributions)

1. 최초의 실용적인 익스팬더 계층 구현: 이론적으로만 존재하던 익스팬더 계층 구조를 실제 대규모 그래프에 적용할 수 있는 효율적인 알고리즘으로 구현했습니다.
2. 새로운 Random-Walk 기반 알고리즘: 유량 계산의 병목 현상을 제거하여 익스팬더 분해를 실용적인 속도로 수행할 수 있게 했습니다.
3. XCut 알고리즘 제안: N-cut 목적 함수에 특화된 새로운 솔버를 제안하여 이론과 실무 사이의 간극을 메웠습니다.

4. 실험 결과 (Results)

50개의 다양한 대규모 그래프(인용 네트워크, 이메일, 소셜 네트워크, 웹 그래프 등)를 대상으로 실험한 결과는 다음과 같습니다.

• 해의 품질 (Solution Quality): 기존의 state-of-the-art 솔버인 Graclus와 비교했을 때, 특히 소셜 네트워크, 인용 네트워크, 웹 그래프 등에서 N-cut 값을 대폭(평균적으로 70% 이상) 낮추는 압도적인 성능을 보였습니다.
• 실행 시간 (Running Time): Graclus보다는 다소 느리지만(평균 3배), 대규모 그래프에서도 최대 18분 이내에 완료될 만큼 경쟁력 있는 속도를 유지했습니다.
• 다중 $k$ 지원: 한 번의 Sparsifier 계산만으로 클러스터 개수($k$)를 바꿔가며 빠르게 여러 해를 구할 수 있어, 탐색적 데이터 분석(EDA)에 매우 유리합니다.

5. 의의 (Significance)

이 논문은 **"이론적으로 우수한 알고리즘이 왜 실제로는 쓰이지 못하는가?"**라는 질문에 대한 답을 제시합니다. 저자들은 익스팬더 분해의 복잡한 계산 비용을 무작위 보행이라는 단순하고 빠른 도구로 대체함으로써, 강력한 이론적 도구인 익스팬더 계층을 실용적인 그래프 클러스터링 도구로 탈바꿈시켰습니다. 이는 향후 다양한 그래프 분할 문제에 익스팬더 계층 구조를 적용할 수 있는 새로운 길을 열었습니다.