A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

TLDR

Multilevel graph partitioning algorithms collapse vertices and edges, partition a smaller graph, and uncoarsen to produce a partition for the original graph, but it was unclear whether they could consistently yield high‑quality partitions across diverse application domains. The study aims to evaluate various strategies for coarsening, coarsest‑graph partitioning, and refinement in a multilevel graph partitioning framework. The authors introduce a heavy‑edge coarsening heuristic that keeps the coarse partition size close to the final partition size and a faster variant of the Kernighan–Lin refinement algorithm, then evaluate the scheme on graphs from finite element, linear programming, VLSI, and transportation domains. Experiments show the scheme consistently outperforms spectral partitioning in both quality and speed, and yields sparser fill‑reducing orderings than the multiple minimum degree algorithm. Related work includes Bui and Jones (1993) and Hendrickson & Leland (1993).

Abstract

Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [Bui and Jones, Proc. of the 6th SIAM Conference on Parallel Processing for Scientific Computing, 1993, 445--452; Hendrickson and Leland, A Multilevel Algorithm for Partitioning Graphs, Tech. report SAND 93-1301, Sandia National Laboratories, Albuquerque, NM, 1993]. From the early work it was clear that multilevel techniques held great promise; however, it was not knownif they can be made to consistently produce high quality partitions for graphs arising in a wide range of application domains. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme produces partitions that are consistently better than those produced by spectral partitioning schemes in substantially smaller time. Also, when our scheme is used to compute fill-reducing orderings for sparse matrices, it produces orderings that have substantially smaller fill than the widely used multiple minimum degree algorithm.