A variational approach to the consistency of spectral clustering

DOI10.1016/J.ACHA.2016.09.003zbMATH Open1396.49013arXiv1508.01928OpenAlexW2963111412MaRDI QIDQ723005FDOQ723005

Authors: Nicolás García Trillos, Dejan Slepčev 

Publication date: 30 July 2018

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Abstract: This paper establishes the consistency of spectral approaches to data clustering. We consider clustering of point clouds obtained as samples of a ground-truth measure. A graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points they connect. We investigate the spectral convergence of both unnormalized and normalized graph Laplacians towards the appropriate operators in the continuum domain. We obtain sharp conditions on how the connectivity radius can be scaled with respect to the number of sample points for the spectral convergence to hold. We also show that the discrete clusters obtained via spectral clustering converge towards a continuum partition of the ground truth measure. Such continuum partition minimizes a functional describing the continuum analogue of the graph-based spectral partitioning. Our approach, based on variational convergence, is general and flexible.

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

Recommendations

• Consistency of spectral clustering
• Consistency of Cheeger and ratio graph cuts
• Learning Theory
• Consistency of regularized spectral clustering
• Convergence of spectral clustering with a general similarity function

zbMATH Keywords

spectral clusteringgamma-convergencerandom geometric graphpoint cloudDirichlet energygraph Laplaciandiscrete to continuum limit

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Geometric probability and stochastic geometry (60D05) Graph theory (including graph drawing) in computer science (68R10) Methods involving semicontinuity and convergence; relaxation (49J45) Existence of optimal solutions to problems involving randomness (49J55)

Cites Work

• Strong consistency of k-means clustering
• Spectral clustering and the high-dimensional stochastic blockmodel
• Diffusion maps
• Random Geometric Graphs
• Towards a theoretical foundation for Laplacian-based manifold methods
• Consistency of Single Linkage for High-Density Clusters
• Graph clustering
• Gradient flows in metric spaces and in the space of probability measures
• Consistency of spectral clustering
• An introduction to \(\Gamma\)-convergence
• Variational Analysis in Sobolev andBVSpaces
• A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
• The Generic Chaining
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A first course in Sobolev spaces
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• From graph to manifold Laplacian: the convergence rate
• Continuum limit of total variation on point clouds
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• Sharp thresholds for monotone properties in random geometric graphs
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Title not available (Why is that?)
• Title not available (Why is that?)
• The normalized graph cut and Cheeger constant: from discrete to continuous
• A new approach to Sobolev spaces and connections to \(\Gamma\)-convergence
• Upper and lower bounds for stochastic processes. Modern methods and classical problems
• Learning Theory
• Expander flows, geometric embeddings and graph partitioning
• Minimax grid matching and empirical measures
• A graph discretization of the Laplace-Beltrami operator
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Convergence of the \(k\)-means minimization problem using \(\Gamma\)-convergence
• Title not available (Why is that?)
• Operator norm convergence of spectral clustering on level sets

Cited In (75)

• Uniform upper bounds on Courant sharp Neumann eigenvalues of chain domains
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• On a class of nonlocal continuity equations on graphs
• A geometrical method for low-dimensional representations of simulations
• Uniqueness of a solution to a general class of discrete system defined on connected graphs
• Variational methods for evolution. Abstracts from the workshop held December 5--8, 2023
• Posterior consistency of semi-supervised regression on graphs
• Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing
• Title not available (Why is that?)
• Conditional expectation using compactification operators
• Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
• CURE: curvature regularization for missing data recovery
• Braverman’s Spectrum and Matrix Diagonalization Versus iK-Means: A Unified Framework for Clustering
• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
• Manifold learning with arbitrary norms
• Learning Theory
• Lipschitz regularity of graph Laplacians on random data clouds
• Properly-weighted graph Laplacian for semi-supervised learning
• Consistency of Dirichlet partitions
• Delay-coordinate maps and the spectra of Koopman operators
• Title not available (Why is that?)
• Continuum limit of total variation on point clouds
• Minimum spectral connectivity projection pursuit. Divisive clustering using optimal projections for spectral clustering
• How the result of graph clustering methods depends on the construction of the graph
• A topological approach to spectral clustering
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Analysis of \(p\)-Laplacian regularization in semisupervised learning
• Delay-coordinate maps, coherence, and approximate spectra of evolution operators
• Deep limits of residual neural networks
• Consistency of regularized spectral clustering
• Consistency of modularity clustering on random geometric graphs
• Operator norm convergence of spectral clustering on level sets
• A metric on directed graphs and Markov chains based on hitting probabilities
• Graph approximations to the Laplacian spectra
• Consistency of spectral clustering
• On the Gamma convergence of functionals defined over pairs of measures and energy-measures
• Consistency of archetypal analysis
• A spectral approach to the shortest path problem
• Nonlocal-interaction equation on graphs: gradient flow structure and continuum limit
• Stochastic block models are a discrete surface tension
• A maximum principle argument for the uniform convergence of graph Laplacian regressors
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Title not available (Why is that?)
• Higher-order spectral clustering for geometric graphs
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Consistency of coefficient-based spectral clustering with image-regularizer
• Learning Theory for Dynamical Systems
• Variational limits of \(k\)-NN graph-based functionals on data clouds
• An exemplar-based clustering using efficient variational message passing
• Title not available (Why is that?)
• Consistency of Cheeger and ratio graph cuts
• Entropy dissipation of Fokker-Planck equations on graphs
• The geometry of kernelized spectral clustering
• On the rate of convergence of empirical measure in \(\infty \)-Wasserstein distance for unbounded density function
• Nonlocal gradient operators with a nonspherical interaction neighborhood and their applications
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Spectral analysis of weighted Laplacians arising in data clustering
• Fractional diffusion maps
• Clustering methods based on variational analysis in the space of measures.
• Think globally, fit locally under the manifold setup: asymptotic analysis of locally linear embedding
• Rates of convergence for Laplacian semi-supervised learning with low labeling rates
• An introduction to gamma-convergence for spectral clustering
• Mumford-Shah functionals on graphs and their asymptotics
• Measuring Segregation via Analysis on Graphs
• Spectral clustering-based community detection using graph distance and node attributes
• A multiscale environment for learning by diffusion
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• Transfer operators from optimal transport plans for coherent set detection
• Convergence of spectral clustering with a general similarity function
• Title not available (Why is that?)
• A continuum limit for the PageRank algorithm
• On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms
• Large data limit for a phase transition model with the p-Laplacian on point clouds
• An \({\ell_p}\) theory of PCA and spectral clustering
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs

This page was built for publication: A variational approach to the consistency of spectral clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q723005)