Graclus software


The program

Graclus (latest: Version 1.2) is a fast graph clustering software that computes normalized cut and ratio association for a given undirected graph without any eigenvector computation. This is possible because of the mathematical equivalence between general cut or association objectives (including normalized cut and ratio association) and the weighted kernel k-means objective. One important implication of this equivalence is that we can run a k-means type of iterative algorithm to minimize general cut or association objectives. Therefore unlike spectral methods, our algorithm totally avoids time-consuming eigenvector computation. We have embedded the weighted kernel k-means algorithm in a multilevel framework to develop very fast software for graph clustering.

New for Version 1.2! The latest release has a number of new features.

1. MATLAB Interface: We now included an interface for running Graclus in MATLAB, making it easier to use Graclus for problems such as image segmentation. The interface has been tested on 32-bit Linux, 64-bit Linux, and Windows.
2. 64-bit compatibility: Version 1.2 now trivially compiles for 64-bit Linux, unlike previous versions.
3. Spectral at the base phase: When using the MATLAB interface, there is now the option of using spectral clustering at the base clustering phase. Versions 1.0 and 1.1 did not offer spectral at the base phase (due to the difficulty of integrating the LAPACK libraries easily).
4. Better image segmentation features: We have included code for using Graclus for doing image segmentation. Previous versions did not have any image segmentation code.
5. Bug fixes etc: We have removed various bugs in the code, including local search bugs and a bug in the connected component computation.

See description of the algorithm in these papers.

Important: Bug Fix for Graclus 1.2 The release of Graclus 1.2 before February 10, 2009 had a bug in the graclus.m file for the Matlab interface. The correct version is graclus.m, and the package has been updated to fix the bug.


Example Data for the Command Line Interface

Using Graclus for Image Segmentation

Download code from Jianbo Shi for preprocessing of the image and creation of the graphs. To segment an image with Graclus, use GraclusImageSegmentation.m (in the MATLAB directory) after adding the path to the image segmentation code.

The following are example images.


On the Berkeley Segmentation Dataset, Graclus achieved lower normalized cut on 67 percent of the test images and was on average 3.2 times faster than the spectral methods. See this page for further details on this comparison.

Download


Citation

You are welcome to use the code under the terms of the GNU Public License (GPL), however please acknowledge its use with a citation: