A fast and high quality multilevel scheme for partitioning irregular graphs

George Karypis and Vipin Kumar
SIAM Journal on Scientific Computing, Vol. 20, No. 1, pp. 359 - 392, 1999
Download Paper
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 known if 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.
This is an expanded version of the ICPP 95 paper that introduced the algorithms of [hlink:[metis/metis/overview][METIS]].
Research topics: Graph partitioning | METIS