그래프 분할

수치해석 시뮬레이션 마지막 수정: 2026-08-13 04:12:41

1. 개요[편집]

그래프 분할 Graph Partitioning
입력	가중 그래프 $G=(V,E,w)$, 조각 수 $k$, 불균형 허용치 $\varepsilon$
목적함수	절단 간선 가중치 합 (또는 통신 볼륨)
제약	조각 크기 균형
복잡도	$k=2$ 균등 분할부터 이미 NP-난해
대표 해법	스펙트럴 이분 · KL/FM 국소 개선 · 다단계 기법
주 소비처	병렬 해석, 희소행렬 순서화, VLSI 배치

절단 자체는 다항시간에 풀린다. 어려워지는 건 “반반씩”이라는 세 글자를 붙이는 순간부터다.

그래프 분할(graph partitioning)은 그래프의 정점 집합을 크기가 균형 잡힌 $k$ 개의 조각으로 나누되, 서로 다른 조각을 잇는 간선의 가중치 합을 최소화하는 조합 최적화 문제다. 정점을 계산량, 간선을 데이터 의존성으로 읽으면 “일을 골고루 나눠주되 서로 말을 덜 걸게 하라”는 병렬 계산의 근본 문제가 되고, 정점을 픽셀, 간선을 유사도로 읽으면 영상 분할이 되며, 정점을 회로 소자로 읽으면 VLSI 배치가 된다. 같은 문제가 이렇게 여러 분야에서 독립적으로 재발견된 탓에 용어가 분야마다 다르다는 것도 이 주제의 특징이다.¹

이 문서는 문제의 정식화와 난이도, 스펙트럴 완화, 국소 개선의 원리를 다룬다. 실무 1순위인 다단계(coarsen–partition–uncoarsen) 구현의 세부 — HEM 코스닝, 버킷 자료구조, k-way 정련, 다중 제약 — 는 METIS 문서에 있고, 피들러 벡터 자체의 성질·계산은 피들러 벡터가, 분할 결과를 실제로 프로세스에 태우는 이야기는 영역 분할법과 병렬 컴퓨팅이 담당한다.

2. 문제의 정식화[편집]

가중 그래프 $G=(V,E)$ , 정점 가중치 $c: V \to \mathbb{R}_{>0}$ , 간선 가중치 $w: E \to \mathbb{R}_{>0}$ 이 주어진다. 분할 $P = \{V_1,\dots,V_k\}$ 는 $V$ 의 서로소 분해이고, 표준 문제는 이렇다.

\min_{P}\ \mathrm{cut}(P) = \!\!\sum_{\substack{(u,v)\in E\\ P(u)\neq P(v)}}\!\! w(u,v) \qquad \text{s.t.}\qquad c(V_i) \le (1+\varepsilon)\,\frac{c(V)}{k}\quad \forall i

$\varepsilon = 0$ 이면 완전 균등 분할( $k=2$ 일 때 최소 이분, minimum bisection), $\varepsilon$ 을 풀면 그만큼 절단을 아낄 여지가 생긴다. 이 다이얼 하나가 실무에서 가장 자주 만지는 손잡이인데, 조이면 절단이 나빠지고 풀면 제일 무거운 조각이 전체를 기다리게 만든다.

목적함수 선택지가 여럿이고, 무엇을 최소화하느냐에 따라 문제의 성격이 통째로 바뀐다.

목적함수	정의(말로)	균형 제약	주 무대
절단 간선 (edge cut)	잘린 간선 가중치 합	명시적으로 붙임	병렬 해석, VLSI
통신 볼륨	정점마다 걸친 조각 수에서 1을 뺀 값의 합	명시적으로 붙임	하이퍼그래프 분할
최대 조각 통신량	조각별 경계량의 최댓값	명시적으로 붙임	지연시간 지배 인터커넥트
비율 절단 (RatioCut)	절단을 양쪽 정점 수로 나눠 더함	목적함수에 내장	이론, 스펙트럴
컨덕턴스 / 정규화 절단	절단을 양쪽 차수 합으로 나눠 더함	목적함수에 내장	군집화, 확장자 이론

앞의 셋은 “제약을 걸고 절단을 최소화”, 뒤의 둘은 “균형을 목적함수 안에 녹여서 제약을 없앤다”는 서로 다른 전략이다. 뒤쪽은 조각 수를 정확히 맞출 필요가 없는 스펙트럴 군집화 계열에서 자연스럽고, 앞쪽은 프로세스 수 $k$ 가 하드웨어로 못 박힌 병렬 해석에서 자연스럽다.

그리고 절단 간선은 통신량의 대리지표일 뿐이라는 점은 반드시 짚어야 한다. 정점 하나가 이웃 셋을 다른 조각에 두면 잘린 간선은 3개지만 실제로 보내는 데이터는 자기 값 하나다. 이 어긋남을 정확히 세려면 하이퍼그래프가 필요하고, 격자처럼 차수가 낮고 균질한 그래프에서는 둘이 거의 비례해서 실무가 그럭저럭 굴러간다는 사정은 METIS 문서에 정리돼 있다.

3. 왜 어려운가[편집]

재미있는 것은 균형 제약이 없으면 이 문제가 쉽다는 사실이다. 두 정점 $s,t$ 를 지정한 최소 절단은 네트워크 흐름의 최대유량-최소절단 정리로 다항시간에 풀리고, $s,t$ 지정 없는 전역 최소 절단도 슈토어-바그너 알고리즘으로 $O(|V||E| + |V|^2\log|V|)$ 에 풀린다. 그런데 여기에 “양쪽 크기가 같아야 한다”를 얹는 순간 NP-난해가 된다.² 이유는 직관적이다 — 제약 없는 최소 절단은 대개 그래프에서 가장 헐거운 귀퉁이 하나를 톡 떼어내는 자명한 답을 내놓는데, 균형 제약은 정확히 그 자명한 답을 금지하면서 조합 폭발을 불러온다.

난이도의 지형은 대략 이렇다.

$k=2$ 균등 분할(minimum bisection)이 이미 NP-난해다(Garey–Johnson–Stockmeyer, 1976). $k$ 를 키운다고 쉬워질 리 없다.
일반 그래프에서 상수배 근사 알고리즘은 알려져 있지 않다. 절단값을 절대오차 기준으로 근사하는 것조차 NP-난해라는 결과가 있다(Bui–Jones, 1992). 알려진 다항시간 근사비는 로그 규모다.
그래서 이론 쪽 표준은 이중기준(bicriteria) 근사 — 균형을 조금 어기는 대가로 절단에 대한 보증을 얻는 방식이다. 균일 희소 절단(uniform sparsest cut)에 대한 아로라–라오–바지라니(2004)의 $O(\sqrt{\log n})$ 근사가 대표적이며, 준정부호 계획법 완화 위에서 돌아간다.
트리에서는 부분트리 크기별 동적 계획법으로 다항시간에 풀린다. 격자처럼 구조가 규칙적이면 손으로도 최적을 안다.

정리하면, 실무 도구들이 전부 휴리스틱인 것은 게으름이 아니라 최적을 노리는 순간 게임이 끝나기 때문이다. 백만 셀 격자를 512조각으로 쪼개는 데 몇 초를 쓰느냐, 최적성을 증명하느라 며칠을 쓰느냐 중에 답은 이미 정해져 있다.

4. 스펙트럴 이분[편집]

지시벡터 $\mathbf{x}\in\{-1,+1\}^n$ 로 두 조각을 표시하면, 그래프 라플라시안 $L = D - A$ 에 대해

\mathbf{x}^{\top} L \mathbf{x} = \sum_{(i,j)\in E} w_{ij}(x_i - x_j)^2 = 4\,\mathrm{cut}(P)

이고, 균등 분할 조건은 $\mathbf{x}^{\top}\mathbf{1} = 0$ 으로 정확히 표현된다. 즉 최소 이분은

\min_{\mathbf{x}\in\{-1,+1\}^n,\ \mathbf{x}^{\top}\mathbf{1}=0} \mathbf{x}^{\top}L\mathbf{x}

라는 이차 정수계획이다. 여기서 $\pm1$ 이라는 정수 제약만 풀어 실수를 허용하면 문제는 상수 모드에 직교하는 레일리 몫 최소화가 되고, 답은 $L$ 의 두 번째로 작은 고유값에 대응하는 고유벡터 — 피들러 벡터다. 이 연속해를 다시 이산화하는 것(부호 절단, 중앙값 절단, 문턱값 훑기)이 스펙트럴 이분(spectral bisection)의 전부이며, 부하 균형이 걸린 병렬 분할에서는 정확히 반씩 나뉘는 중앙값 절단이 기본값이다.

정점 176개·간선 579개 그래프에서 라플라시안 L = D − A 의 피들러 벡터를 란초스로 반복해 구하고, 매 반복의 추정 벡터를 그 자리에서 중앙값 이분해 절단 간선을 다시 센다. 무작위 시작벡터의 절단 292개가 8반복 만에 44개로 떨어지고, 이어 붙인 케르니건-린 쌍교환 정련이 균형 88:88 을 유지한 채 28개까지 깎는다. λ₂ = 0.1721076 은 같은 행렬의 조밀 야코비 고유분해와 상대오차 6e−14 안에서 일치한다.

이 완화가 단순한 눈속임이 아니라는 보증이 치거 부등식이다. 정규화 라플라시안의 $\lambda_2$ 와 컨덕턴스 $h_G$ 사이의 양방향 부등식이 “어떤 절단도 $\lambda_2/2$ 보다 좋을 수 없다”는 하계와 “문턱값 훑기로 얻은 절단은 최적의 제곱근 규모 안에 든다”는 상계를 동시에 준다. 조합 최적화 문제의 연속 완화가 이런 양방향 보증을 갖는 경우는 드물다 — 자세한 진술과 유도는 피들러 벡터 참고.

$k$ 조각으로 곧장 가려면 하위 $k$ 개 고유벡터로 정점을 $\mathbb{R}^k$ 에 심고 그 위에서 다시 나누면 된다. 이 절차가 그대로 스펙트럴 군집화이고, 실제로 두 분야는 같은 대상을 “조각”과 “군집”이라는 다른 이름으로 부르고 있을 뿐이다. 다만 부하 균형이라는 딱딱한 제약이 붙는 쪽에서는 실수 좌표를 균등 조각으로 되돌리는 반올림 단계가 훨씬 까다롭다.

스펙트럴 방법이 1990년 전후 표준이었다가 실무 1순위 자리를 내준 이유는 비용 하나다. 란초스로 하위 고유쌍 몇 개만 뽑아도 반복마다 희소 행렬-벡터 곱이 필요하고, 대칭성이 높은 격자에서는 $\lambda_2 \approx \lambda_3$ 로 고유공간이 축퇴돼 수렴이 늘어진다. 다단계 휴리스틱이 간선 수에 사실상 선형인 시간에 대등하거나 더 좋은 절단을 내놓자, 스펙트럴은 다단계의 초기 분할 단계와 품질 비교용 기준선, 그리고 하계를 주는 이론적 도구로 자리를 옮겼다.³

5. 국소 개선 — 커니핸-린과 피두치아-마테이시스[편집]

어떤 방법으로든 초기 분할을 얻었으면 다음은 다듬기다. 이 분야의 원형은 1970년 벨 연구소의 커니핸-린(Kernighan–Lin, KL) 알고리즘이다.

정점 $a$ 에 대해 외부 비용 $E_a$ (다른 조각에 걸린 간선 가중치 합)와 내부 비용 $I_a$ 를 정의하고 $D_a = E_a - I_a$ 라 두면, 양쪽 조각의 정점 $a, b$ 를 맞바꿨을 때 줄어드는 절단은

g_{ab} = D_a + D_b - 2\,w(a,b)

다. 마지막 항은 $a$ 와 $b$ 가 직접 이어져 있으면 서로 상대편으로 따라가므로 이득이 그만큼 깎인다는 보정이다. KL의 한 패스는 이렇게 돌아간다.

모든 쌍 중 $g_{ab}$ 가 최대인 쌍을 골라 (가상으로) 교환하고 두 정점을 잠근다.
잠기지 않은 정점들의 $D$ 값을 갱신하고 1을 반복해 교환 시퀀스 $g_1, g_2, \dots$ 를 끝까지 만든다.
누적 이득 $\sum_{i\le m} g_i$ 가 최대가 되는 $m$ 을 찾아 거기까지만 실제로 반영하고 나머지는 되돌린다.

핵심은 3번이다. 당장 이득이 음수인 교환도 일단 저지르고 나중에 되감는다 — 이 “손해 보고 넘어가기”가 없으면 그리디 국소탐색과 다를 게 없어 첫 번째 국소최적에서 멈춘다. 쌍을 전수조사하므로 소박한 구현은 패스당 $O(n^3)$ 이라 큰 그래프에는 못 쓴다.

1982년 피두치아-마테이시스(Fiduccia–Mattheyses, FM) 가 이걸 실용 궤도에 올렸다. 쌍 교환을 단일 정점 이동으로 바꾸고(그래서 균형이 깨질 수 있는 만큼 허용 범위를 명시적으로 관리한다), 각 정점의 이득을 정수 버킷 배열 + 이중연결 리스트에 담아 최대 이득 정점을 $O(1)$ 에 뽑는다. 패스 비용이 간선 수에 선형이 되고, 하이퍼그래프에도 그대로 확장된다. 잠금·음의 이득 허용·최적 접두사 되감기라는 KL의 골격은 그대로 물려받았다. 버킷 자료구조와 경계 정련 최적화의 실제 모양은 METIS 문서에 있다.

문제는 KL/FM 모두 국소 탐색이라는 것이다. 초기 분할이 나쁘면 결과도 나쁘고, 정점 하나씩 옮겨서는 “조각 경계 전체를 통째로 반대편으로 옮겨야 좋아지는” 종류의 개선을 절대 찾지 못한다. 이 한계를 정면으로 뚫은 것이 다단계 기법이다 — 그래프를 정점 수백 개가 될 때까지 뭉쳐 놓으면 거친 레벨에서 정점 하나를 옮기는 것이 원 그래프에서는 수천 개를 한꺼번에 옮기는 것과 같아진다. 다중격자법이 저주파 오차를 조대 격자에서 잡는 것과 발상이 똑같고, 그래서 다단계 분할은 사실상 “절단에 대한 멀티그리드”다.

6. 기하 정보를 쓰는 방법들[편집]

메시처럼 정점에 좌표가 있으면 그래프 구조를 무시하고 공간만 쪼개는 값싼 방법들이 있다.

재귀 좌표 이분(RCB) — 가장 긴 축을 골라 중앙값에서 자르기를 재귀적으로 반복. 구현 30줄, 결과는 정확히 균등. 축에 정렬되지 않은 형상에서 절단이 나쁘다.
관성 이분(inertial bisection) — 정점 좌표의 공분산에서 주축을 뽑아 그 축에 수직으로 자른다. 길쭉한 형상에서 RCB보다 훨씬 낫다. 주성분 분석 한 번이 전부인 셈.
공간 채움 곡선 — 힐베르트/모턴 곡선으로 셀을 1차원으로 늘어놓고 $k$ 등분한다. 국소성이 상당히 보존되고, 무엇보다 증분적이라 적응 격자 세분화로 격자가 매 스텝 바뀌는 문제에서 재분할 비용이 거의 없다. 절단 품질은 다단계보다 확실히 나쁘지만, 매 스텝 다시 분할해야 한다면 총합에서는 이길 수 있다.

여기서 동적 재분할(dynamic repartitioning)이라는 별도의 문제가 나온다. AMR이나 입자 이동으로 부하가 기울었을 때 목적함수는 절단만이 아니라 데이터 이주 비용까지 포함해야 한다. 절단이 아무리 좋아도 전체 격자를 랭크 사이로 실어 나르면 손해다. 그래서 확산 기반 재분할(이웃 조각끼리 부하를 국소적으로 흘려보내는 방식)이나 이주 비용에 가중치를 주는 정식화가 쓰이고, 이 지점이 부하 분산과 그래프 분할이 갈라지는 경계다.

7. 어디에 쓰이나[편집]

영역 분할법과 병렬 해석 — 셀을 정점, 면 공유를 간선으로 하는 쌍대 그래프를 나눠 랭크별 소유 셀과 halo 교환 패턴을 정한다. 유한체적법·유한요소법 병렬화의 첫 단추.
희소행렬 순서화 — 분리자를 재귀적으로 뒤로 미는 중첩 분할(nested dissection)이 촐레스키 분해·LU 분해의 채움을 극적으로 줄인다. 많은 사용자가 분할기를 링크해 놓고도 자기가 쓰는 줄 모르는 용도.
VLSI 배치·분할 — FM 알고리즘이 원래 태어난 곳. 회로를 칩·블록에 나눌 때 핀 수(하이퍼에지 절단)를 줄이는 문제다.
영상 분할 — 픽셀 그래프에서 정규화 절단을 최소화하는 그래프 컷 계열. 이쪽은 균형 제약 대신 정규화가 목적함수에 들어간다.
대수적 조대화 — 대수적 다중격자법이 미지수들을 응집(aggregation)해 조대 레벨을 만드는 절차도 결국 “강하게 결합된 것끼리 묶어라”라는 같은 문제의 국소판이다.

마지막으로 실무 팁 하나. 절단 숫자만 보고 분할 품질을 판단하지 말 것. 조각별 셀 수, 조각별 경계면 수, 그리고 이웃 조각 개수를 함께 봐야 한다. 절단이 같아도 이웃이 4개인 분할과 30개인 분할은 실제 스케일링이 전혀 다르다.⁴

8. 관련 문서[편집]

병렬 수치해석에서는 “도메인 분할”, 회로 설계에서는 “파티셔닝”, 기계학습에서는 “군집화”, 사회연결망 분석에서는 “커뮤니티 탐지”라고 부른다. 논문을 읽다가 낯익은 알고리즘이 낯선 이름을 달고 나오면 대개 이 넷 중 하나다. ↩
그래서 “절단 문제니까 다항시간이겠지”라고 방심하면 안 된다. 최대유량으로 푸는 최소 절단과 균형 그래프 분할은 이름이 비슷할 뿐 복잡도 등급이 다른 세계에 산다. ↩
“느린데 더 좋지도 않다”는 평가는 냉정하지만 정확했다. 다만 다단계 구현들이 조대 레벨 초기 분할 옵션으로 스펙트럴을 아직 들고 있는 것을 보면, 완전히 은퇴한 건 아니고 관리직으로 옮긴 쪽에 가깝다. ↩
대역폭보다 지연시간이 아픈 인터커넥트에서는 이웃 개수가 실제 병목이 된다. 표준 분할기들은 이 값을 직접 최소화하지 않으므로, 노드 내부를 먼저 나누고 노드 간을 나중에 나누는 계층적 분할로 우회하는 것이 정석이다. ↩