1SpectralClusteringhttp://mloss.orgUpdates and additions to 1SpectralClusteringenTue, 01 May 2018 19:26:07 -00001SpectralClustering 1.2<html><p>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. </p> <p>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. </p> <p>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. </p> <p>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. </p></html>matthias hein, thomas buehlerTue, 01 May 2018 19:26:07 -0000 clusteringclusteringgraph partitioning