Name
Abstract | ||
|---|---|---|
We present a generalized version of spectral clustering using the graph p-Laplacian, a nonlinear generalization of the standard graph Laplacian. We show that the second eigenvector of the graph p-Laplacian interpolates between a relaxation of the normalized and the Cheeger cut. Moreover, we prove that in the limit as p → 1 the cut found by thresholding the second eigenvector of the graph p-Laplacian converges to the optimal Cheeger cut. Furthermore, we provide an efficient numerical scheme to compute the second eigenvector of the graph p-Laplacian. The experiments show that the clustering found by p-spectral clustering is at least as good as normal spectral clustering, but often leads to significantly better results. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1553374.1553385 | ICML |
Keywords | Field | DocType |
optimal cheeger cut,cheeger cut,graph p-laplacian,spectral clustering,better result,p-spectral clustering,graph p-laplacian converges,graph p-laplacian interpolates,normal spectral clustering,standard graph,graph laplacian,eigenvectors | Adjacency matrix,Laplacian matrix,Discrete mathematics,Strength of a graph,Spectral clustering,Combinatorics,Graph energy,Spectral graph theory,Line graph,Mathematics,Voltage graph | Conference |
Citations | PageRank | References |
70 | 2.41 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Bühler | 1 | 156 | 6.32 |
| Matthias Hein | 2 | 663 | 62.80 |