Graclus (latest: Version 1.2) is a
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
eigenvector computation. We have embedded the weighted kernel k-means algorithm in
a multilevel framework to develop very fast software for graph
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.
- The README of the code for Version 1.2 is here.
The code is released under the GNU Public License (GPL).
The code has been compiled using gcc 3.0.3 in Solaris and Linux.
However, bug reports and comments are always appreciated.
- Please enter your e-mail address and press the left button below.
You should receive the software via e-mail.
Otherwise, request the software directly from me.
You are welcome to use the code under the terms of the GNU Public License (GPL), however please acknowledge its use with a citation:
- Weighted Graph Cuts without Eigenvectors: A Multilevel Approach,
I. Dhillon, Y. Guan, and B, Kulis,
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 29:11, pages 1944-1957, November 2007.
- A Fast Kernel-based Multilevel Algorithm for Graph Clustering,
I. Dhillon, Y. Guan, and B, Kulis,
The 11th ACM SIGKDD, Chicago, IL, August 21-24, 2005.
- Kernel k-means, Spectral Clustering and Normalized Cuts,
I. Dhillon, Y. Guan, and B. Kulis,
The 10th ACM SIGKDD, Seattle, WA, August 22-25, 2004.
(Also, appears as UTCS Technical Report #TR-04-25, June 30, 2004.
[Abstract & Download])