Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
From MaRDI portal
Publication:2189394
Abstract: Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly little theory about performance guarantees for spectral clustering. This issue is partly due to the fact that spectral clustering typically involves two steps which complicated its theoretical analysis: first, the eigenvectors of the associated graph Laplacian are used to embed the dataset, and second, k-means clustering algorithm is applied to the embedded dataset to get the labels. This paper is devoted to the theoretical foundations of spectral clustering and graph cuts. We consider a convex relaxation of graph cuts, namely ratio cuts and normalized cuts, that makes the usual two-step approach of spectral clustering obsolete and at the same time gives rise to a rigorous theoretical analysis of graph cuts and spectral clustering. We derive deterministic bounds for successful spectral clustering via a spectral proximity condition that naturally depends on the algebraic connectivity of each cluster and the inter-cluster connectivity. Moreover, we demonstrate by means of some popular examples that our bounds can achieve near-optimality. Our findings are also fundamental for the theoretical understanding of kernel k-means. Numerical simulations confirm and complement our analysis.
Recommendations
Cites work
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- scientific article; zbMATH DE number 1183917 (Why is no real title available?)
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 1333614 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A variational approach to the consistency of spectral clustering
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Clustering subgaussian mixtures by semidefinite programming
- Community detection and stochastic block models: recent developments
- Consistency of spectral clustering
- Consistency of spectral clustering in stochastic block models
- Diffusion maps
- Exact Recovery in the Stochastic Block Model
- Expander flows, geometric embeddings and graph partitioning
- From graph to manifold Laplacian: the convergence rate
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps
- Graph theory with applications
- Improved spectral-norm bounds for clustering
- Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
- Learning Theory
- Least squares quantization in PCM
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- NP-hardness of Euclidean sum-of-squares clustering
- On semidefinite relaxations for the block model
- Probably certifiably correct \(k\)-means clustering
- Random Laplacian matrices and convex relaxations
- Relax, no need to round: integrality of clustering formulations
- Spectra of graphs
- Spectral clustering and the high-dimensional stochastic blockmodel
- Spectral convergence of the connection Laplacian from random samples
- The Planar k-Means Problem is NP-Hard
- The Rotation of Eigenvectors by a Perturbation. III
- User-friendly tail bounds for sums of random matrices
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
Cited in
(9)- Optimality of spectral clustering in the Gaussian mixture model
- Learning by unsupervised nonlinear diffusion
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- scientific article; zbMATH DE number 5957371 (Why is no real title available?)
- \(k\)-median: exact recovery in the extended stochastic ball model
- Convex programming based spectral clustering
- scientific article; zbMATH DE number 7370580 (Why is no real title available?)
- A performance guarantee for spectral clustering
- The ratio-cut polytope and K-means clustering
This page was built for publication: Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189394)
