Graclus software


The program

Graclus (Version 1.1 & Version 1.0) is a fast graph clustering software that computes normalized cut and ratio association for a given graph without any eigenvector computation. This is possible because we establish a 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 embed the weighted kernel k-means algorithm in a multilevel framework and develop this fast software for graph clustering.

See description of the algorithm in these papers.


Example Data

The following are images. For these, we used code from Jianbo Shi to preprocess the images and create the graphs. To view the segmentation, use displaySegmentation.m using the original image file and the segmentation returned by Graclus.



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: