Project details for 1SpectralClustering

Logo 1SpectralClustering 1.0

by tbuehler - January 13, 2011, 01:32:49 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ]

view (12 today), download ( 3 today ), 3 subscriptions


1-Spectral Clustering is a graph-based clustering method which relaxes the NP-hard problem of finding the optimal balanced cut of a similarity graph to a nonlinear eigenproblem involving the eigenvectors of the nonlinear graph 1-Laplacian.

In contrast to the standard spectral relaxation, this relaxation is tight in the sense that the second eigenvalue of the (normalized) graph 1-Laplacian is equal to the optimal (normalized) ratio Cheeger cut and the second eigenvector is the indicator function of the optimal partition.

We use our nonlinear inverse power method to compute a nonconstant eigenvector of the graph 1-Laplacian. Note that convergence to the second eigenvector is not guaranteed but we can guarantee that the bipartitioning of 1-Spectral Clustering is at least as good as the one of Spectral Clustering and empirically it is in general much better.

1-Spectral Clustering supercedes our previous p-Spectral Clustering, as 1-Spectral Clustering is much faster and yields better cuts. As the underlying optimization method is based on a first order method, the method easily scales to large sparse graphs (more than 100000 vertices).

Changes to previous version:

Initial Announcement on

BibTeX Entry: Download
Corresponding Paper BibTeX Entry: Download
URL: Project Homepage
Supported Operating Systems: Agnostic
Data Formats: Matlab
Tags: Spectral Clustering, Clustering, Graph Partitioning
Archive: download here

Other available revisons

Version Changelog Date
  • improved optimization of ncut and rcut criterion
  • optimized eigenvector initialization
  • changed default values for number of runs
  • several internal optimizations
  • made console output more informative
May 1, 2018, 19:26:07
  • fixed bug occuring when input graph is disconnected
  • reduced memory usage when input graph has large number of disconnected components
  • more user-friendly usage of main method OneSpectralClustering
  • faster computation of eigenvector initialization + now thresholded according to multicut-criterion
  • several internal optimizations
June 27, 2011, 10:45:57

Initial Announcement on

January 13, 2011, 01:32:49


No one has posted any comments yet. Perhaps you'd like to be the first?

Leave a comment

You must be logged in to post comments.