• 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.


  • 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.
  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.


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: