Consistency of spectral clustering

DOI10.1214/009053607000000640zbMath1133.62045arXiv0804.0678OpenAlexW2002276939WikidataQ57408122 ScholiaQ57408122MaRDI QIDQ2426615

Olivier Bousquet, Mikhail Belkin, Ulrike von Luxburg

Publication date: 23 April 2008

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0804.0678

zbMATH Keywords

consistency spectral clustering graph Laplacian convergence of eigenvectors

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Applications of graph theory (05C90) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Applications of operator theory in probability theory and statistics (47N30)

Related Items (only showing first 100 items - show all)

Consistency of modularity clustering on random geometric graphs ⋮ Adaptive edge weighting for graph-based learning algorithms ⋮ Operator-theoretic framework for forecasting nonlinear time series with kernel analog techniques ⋮ Construction and Monte Carlo estimation of wavelet frames generated by a reproducing kernel ⋮ Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model ⋮ Kernel spectral clustering of large dimensional data ⋮ From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Geometry on probability spaces ⋮ A survey of kernel and spectral methods for clustering ⋮ Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs ⋮ Concentration of kernel matrices with application to kernel spectral clustering ⋮ Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation ⋮ Strong Consistency of ReducedK-means Clustering ⋮ Convergence of the graph Allen-Cahn scheme ⋮ Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations ⋮ Universally consistent vertex classification for latent positions graphs ⋮ On information plus noise kernel random matrices ⋮ Spectral analysis of weighted Laplacians arising in data clustering ⋮ Koopman analysis of the long-term evolution in a turbulent convection cell ⋮ The discrete Gaussian free field on a compact manifold ⋮ Spectral clustering-based community detection using graph distance and node attributes ⋮ Some remarks on MCMC estimation of spectra of integral operators ⋮ Generalization errors of Laplacian regularized least squares regression ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Consistency of Dirichlet Partitions ⋮ A geometric heat-flow theory of Lagrangian coherent structures ⋮ Kernel-based methods for solving time-dependent advection-diffusion equations on manifolds ⋮ Heat kernel embeddings, differential geometry and graph structure ⋮ An empirical feature-based learning algorithm producing sparse approximations ⋮ Agglomerative clustering via maximum incremental path integral ⋮ Clustering and outlier detection using isoperimetric number of trees ⋮ Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator ⋮ Variable bandwidth diffusion kernels ⋮ On the regularized Laplacian eigenmaps ⋮ Spectral convergence of the connection Laplacian from random samples ⋮ Population dynamics and statistical physics in synergy. Abstracts from the workshop held March 6--12, 2022 ⋮ Core-periphery structure in networks: a statistical exposition ⋮ Multiway spectral clustering: a margin-based perspective ⋮ Continuum limit of Lipschitz learning on graphs ⋮ Spectral clustering based on local linear approximations ⋮ Feature selection in the Laplacian support vector machine ⋮ A similarity measure for second order properties of non-stationary functional time series with applications to clustering and testing ⋮ Spectral clustering and the high-dimensional stochastic blockmodel ⋮ \(\varepsilon\)-coverings of Hölder-Zygmund type spaces on data-defined manifolds ⋮ Extraction and prediction of coherent patterns in incompressible flows through space-time koopman analysis ⋮ Delay-coordinate maps, coherence, and approximate spectra of evolution operators ⋮ Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ Spectral convergence of graph Laplacian and heat kernel reconstruction in \(L^\infty\) from random samples ⋮ Manifold learning with arbitrary norms ⋮ The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous ⋮ Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics ⋮ Think globally, fit locally under the manifold setup: asymptotic analysis of locally linear embedding ⋮ Robust dimension-free Gram operator estimates ⋮ Horseshoes in multidimensional scaling and local kernel methods ⋮ Towards a theoretical foundation for Laplacian-based manifold methods ⋮ Learning and approximation by Gaussians on Riemannian manifolds ⋮ Cover-based bounds on the numerical rank of Gaussian kernels ⋮ Consistency of regularized spectral clustering ⋮ Random matrix-improved estimation of covariance matrix distances ⋮ Stability analysis of learning algorithms for ontology similarity computation ⋮ Spectral methods for graph clustering - a survey ⋮ Automatically finding clusters in normalized cuts ⋮ Quantile-based clustering ⋮ Diffusion maps tailored to arbitrary non-degenerate Itô processes ⋮ Convergence of the point integral method for Laplace-Beltrami equation on point cloud ⋮ A note on Fiedler vectors interpreted as graph realizations ⋮ A variational approach to the consistency of spectral clustering ⋮ A Graph Framework for Manifold-Valued Data ⋮ Uncovering latent structure in valued graphs: a variational approach ⋮ Reproducing kernel Hilbert space compactification of unitary evolution groups ⋮ Fractional diffusion maps ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Foundations of a multi-way spectral clustering framework for hybrid linear modeling ⋮ Diffuse Interface Models on Graphs for Classification of High Dimensional Data ⋮ Cluster forests ⋮ Limit theorems for eigenvectors of the normalized Laplacian for random graphs ⋮ Topology and data ⋮ The embedding dimension of Laplacian eigenfunction maps ⋮ Hydrodynamic limit of the symmetric exclusion process on a compact Riemannian manifold ⋮ A Cheeger cut for uniform hypergraphs ⋮ Optimality of spectral clustering in the Gaussian mixture model ⋮ A General Hybrid Clustering Technique ⋮ SVM LEARNING AND L^p APPROXIMATION BY GAUSSIANS ON RIEMANNIAN MANIFOLDS ⋮ Delay-coordinate maps and the spectra of Koopman operators ⋮ Analysis of spectral clustering algorithms for community detection: the general bipartite setting ⋮ On strong consistency of kernel \(k\)-means: a Rademacher complexity approach ⋮ Localized Fourier analysis for graph signal processing ⋮ Error bounds of the invariant statistics in machine learning of ergodic Itô diffusions ⋮ Kernel-based prediction of non-Markovian time series ⋮ Koopman spectra in reproducing kernel Hilbert spaces ⋮ Large data and zero noise limits of graph-based semi-supervised learning algorithms ⋮ Data-driven spectral decomposition and forecasting of ergodic dynamical systems ⋮ Data spectroscopy: eigenspaces of convolution operators and clustering ⋮ Spatiotemporal pattern extraction by spectral analysis of vector-valued observables ⋮ Theoretical Analysis of Active Contours on Graphs ⋮ Grouped spatial autoregressive model ⋮ The geometry of kernelized spectral clustering ⋮ Role of normalization in spectral clustering for stochastic blockmodels ⋮ Continuum limit of total variation on point clouds

Cites Work

This page was built for publication: Consistency of spectral clustering