Graclus
- A fast and efficient graph clustering software
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.
Download
- 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.
Version Information
New for Version 1.2! The latest release has a number of new features.- 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.
- 64-bit compatibility: Version 1.2 now trivially compiles for 64-bit Linux, unlike previous versions.
- 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).
- Better image segmentation features: We have included code for using Graclus for doing image segmentation. Previous versions did not have any image segmentation code.
- Bug fixes etc: We have removed various bugs in the code, including local search bugs and a bug in the connected component computation.
Citation
This software is released under the GNU Public License (GPL) but please acknowledge its use with a citation to at least one of the following publications:- Weighted Graph Cuts without Eigenvectors: A Multilevel Approach (pdf, software)
I. Dhillon, Y. Guan, B. Kulis.
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 29(11), pp. 1944-1957, November 2007. - A Fast Kernel-based Multilevel Algorithm for Graph Clustering (pdf, software)
I. Dhillon, B. Kulis.
In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 629-634, August 2005. - Kernel k-means, Spectral Clustering and Normalized Cuts (pdf, software)
I. Dhillon, Y. Guan, B. Kulis.
In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 551-556, August 2004.
(A longer version appears as UTCS Technical Report #TR-04-25, June 30, 2004.) - add32.graph
- finance256.graph
- gupta2.graph
- memplus.graph
- pcrystk02.graph
- rajat10.graph
- ramage02.graph
- imdb.graph
Additional Information
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.