Graph Partitioners

The goals of a graph partitioner, also called mesh partitioner, is to separate the vertices of a graph into almost equal-sized components such that the number of edges between components is minimized. Finding good graph partitions has been the focus of much recent research because it can be used to reduce the communication among processors in a parallel machine. In particular if the graph represents the communication structure of a set of entities, then the graph partitioner can be used to allocate the entities to processors such that communication is reduced. Graph partitioners also have many other uses.

We have implemented three algorithms for finding separators of graphs in NESL for the purpose of comparing the quality of the cuts. These algorithms are: coordinate bisection, geometric random circles, and spectral. The first two algorithms require geometric information about locations of the vertices, while the third does not. All three algorithms are based on cutting the graph into two components, and then being applied recursively to split into more components. Here we outline how the partition into two is made.

Coordinate bisection:: This algorithm considers each axis (x, y or z in three dimension) and takes a median along that axis. It then measures the number of edges that will be cut if we separate the vertices into the ones less and greater than the median. We select the axis (one of x, y or z) that minimizes the number of edges cut. An animation of this algorithm is available. The Nesl code.
Random Circles:: This technique due to Miller, Teng, Thurston and Vavasis, is also geometric in nature. Instead of making planar cuts as in the coordinate bisection, it makes spherical cuts (or circular in 2 dimensions). These cuts are made by projecting the vertices onto the surface of a sphere in one higher dimension and then making a planar cut on that sphere (these cuts will transform into spherical cuts when projected back into the lower dimension). The random circles technique can generate much better cuts than coordinate bisection. The Nesl code.
Spectral bisection: This algorithm is based on finding the second eigenvector of the Jacobian of the graph. This vector is then sorted and all the vertices are split based on amplitude. The algorithm is described in more detailed in a paper by Pothen, Simon, and Wang. The Nesl code.

Our work is joint with several other groups here at Carnegie Mellon and elsewhere, including Gary Miller, the iWarp project, Mike Heroux at Cray Research, Shanghua Teng at the University of Minnesota, and Eric Schwabe at Northwestern. Here is a paper that overviews the work.

Related Work (online)

The METIS graph partitioner from the University of Minnesota.
Archimedes and the Quake project at CMU.
Scalable Libraries for Graph Partitioning at Syracuse University.
How Good is Recursive Bisection? by Horst D. Simon and Shang-Hua Teng.
A Parallel Graph Partitioner on a Distributed Memory Multiprocessor, by P. Buch, J. Sanghavi, and A. Sangiovanni-Vincentelli.
A graph partitioner from OGI.

Up to the Irregular Algorithms page, the NESL page, or the Scandal page.

guy.blelloch@cs.cmu.edu.