그래프 분할(graph partitioning)은 수학 및 컴퓨터 과학에서 그래프의 정점(노드) 집합을 여러 개의 상호 배타적인 부분집합으로 나누는 문제이다. 이때 각 부분(파티션)의 크기는 가능한 동일하게 유지하면서, 서로 다른 부분 사이를 연결하는 간선(절단 간선, cut edge)의 수를 최소화하는 것을 목표로 한다. 그래프를 두 개의 부분으로 나누는 특수한 경우는 그래프 이등분(graph bisection) 문제라고 한다.
그래프 분할 문제는 조합 최적화 문제 중 하나로, NP-완전(NP-complete)에 속하는 대표적인 난제이다. 따라서 일반적인 경우 최적해를 직접 구하는 것은 실용적인 시간 내에 불가능하며, 휴리스틱(heuristic) 알고리즘이나 근사 알고리즘을 통해 근사해를 구하는 방식이 주로 사용된다.
문제의 정의는 다음과 같다. 그래프 G = (V, E)가 주어졌을 때, V를 k개의 부분집합 V₁, V₂, ..., Vₖ로 나눈다. 각 부분은 서로 중복되지 않으며 크기가 균등해야 한다(균형 분할, balanced partition). 최소화해야 하는 목적 함수는 서로 다른 부분 사이를 연결하는 간선들의 가중치 합(절단 크기, cut size)이다. 변형 문제로는 간선마다 가중치를 부여하거나, 각 부분의 정점 수가 일정 범위 내에서 차이가 나는 것을 허용하는 경우 등이 있다.
주요 알고리즘으로는 국지적 탐색 기반의 커니핸-린(Kernighan–Lin) 알고리즘과 FM(Fiduccia-Mattheyses) 알고리즘, 스펙트럼 분할(spectral partitioning) 기법, 다중 수준(multi-level) 분할 방식 등이 있다. 다중 수준 분할 방식의 대표적인 소프트웨어로는 METIS, Scotch, KaHIP, KaHyPar 등이 있다.
응용 분야는 과학 계산(scientific computing), VLSI 회로 설계, 다중 프로세서 컴퓨터에서의 작업 스케줄링, 소셜 네트워크 분석, 생물학적 네트워크에서의 군집 탐지(clustering) 등 매우 다양하다. 최근에는 그래프 라플라시안(Graph Laplacian)의 고유벡터를 이용한 스펙트럴 클러스터링(spectral clustering)과 모듈러티(modularity) 최적화 기법이 커뮤니티 탐지 분야에서 널리 활용되고 있다.
