A variational approach to the consistency of spectral clustering
From MaRDI portal
(Redirected from Publication:723005)
spectral clusteringgamma-convergencerandom geometric graphpoint cloudDirichlet energygraph Laplaciandiscrete to continuum limit
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 6378006 (Why is no real title available?)
- scientific article; zbMATH DE number 1254188 (Why is no real title available?)
- scientific article; zbMATH DE number 750648 (Why is no real title available?)
- scientific article; zbMATH DE number 1865939 (Why is no real title available?)
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 5681750 (Why is no real title available?)
- A first course in Sobolev spaces
- A graph discretization of the Laplace-Beltrami operator
- A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
- A new approach to Sobolev spaces and connections to \(\Gamma\)-convergence
- A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
- An introduction to -convergence
- Consistency of Single Linkage for High-Density Clusters
- Consistency of spectral clustering
- Continuum limit of total variation on point clouds
- Convergence of the k-means minimization problem using -convergence
- Diffusion maps
- Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
- Expander flows, geometric embeddings and graph partitioning
- From graph to manifold Laplacian: the convergence rate
- Gradient flows in metric spaces and in the space of probability measures
- Graph clustering
- Learning Theory
- Minimax grid matching and empirical measures
- On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
- Operator norm convergence of spectral clustering on level sets
- Random Geometric Graphs
- Sharp thresholds for monotone properties in random geometric graphs
- Spectral clustering and the high-dimensional stochastic blockmodel
- Strong consistency of k-means clustering
- The Generic Chaining
- The normalized graph cut and Cheeger constant: from discrete to continuous
- The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
- Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
- Towards a theoretical foundation for Laplacian-based manifold methods
- Upper and lower bounds for stochastic processes. Modern methods and classical problems
- Variational Analysis in Sobolev andBVSpaces
Cited in
(85)- Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs
- Manifold learning with arbitrary norms
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
- Properly-weighted graph Laplacian for semi-supervised learning
- Learning Theory
- Delay-coordinate maps and the spectra of Koopman operators
- Lipschitz regularity of graph Laplacians on random data clouds
- Consistency of Dirichlet partitions
- Continuum limit of total variation on point clouds
- scientific article; zbMATH DE number 7306882 (Why is no real title available?)
- 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
- Uniform upper bounds on Courant sharp Neumann eigenvalues of chain domains
- Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
- Delay-coordinate maps, coherence, and approximate spectra of evolution operators
- Analysis of p-Laplacian regularization in semisupervised learning
- Consistency of regularized spectral clustering
- Deep limits of residual neural networks
- Consistency of modularity clustering on random geometric graphs
- Graph-to-local limit for the nonlocal interaction equation
- Operator norm convergence of spectral clustering on level sets
- A metric on directed graphs and Markov chains based on hitting probabilities
- On a class of nonlocal continuity equations on graphs
- Consistency of spectral clustering
- On the Gamma convergence of functionals defined over pairs of measures and energy-measures
- Discrete-to-continuum rates of convergence for nonlocal p-Laplacian evolution problems
- Graph approximations to the Laplacian spectra
- 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
- Graph Laplacian-based Bayesian multi-fidelity modeling
- 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
- From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
- Higher-order spectral clustering for geometric graphs
- scientific article; zbMATH DE number 7255037 (Why is no real title available?)
- Consistency of coefficient-based spectral clustering with image-regularizer
- Convergence rates of the fractional to the local Dirichlet problem
- A geometrical method for low-dimensional representations of simulations
- Learning Theory for Dynamical Systems
- Variational limits of \(k\)-NN graph-based functionals on data clouds
- 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
- An exemplar-based clustering using efficient variational message passing
- Consistency of Cheeger and ratio graph cuts
- Evolution equations on co-evolving graphs: long-time behaviour and the graph-continuity equation
- Entropy dissipation of Fokker-Planck equations on graphs
- scientific article; zbMATH DE number 7370580 (Why is no real title available?)
- The geometry of kernelized spectral clustering
- Posterior consistency of semi-supervised regression on graphs
- On the rate of convergence of empirical measure in -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
- Manifold filter-combine networks
- Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing
- The graph -Laplacian eigenvalue problem
- Fractional diffusion maps
- Consistency of anchor-based spectral clustering
- Clustering methods based on variational analysis in the space of measures.
- Spectral convergence of symmetrized graph Laplacian on manifolds with boundary
- 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
- scientific article; zbMATH DE number 7626762 (Why is no real title available?)
- Spectral clustering-based community detection using graph distance and node attributes
- Mumford-Shah functionals on graphs and their asymptotics
- Conditional expectation using compactification operators
- Measuring Segregation via Analysis on Graphs
- Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
- CURE: curvature regularization for missing data recovery
- A multiscale environment for learning by diffusion
- Braverman’s Spectrum and Matrix Diagonalization Versus iK-Means: A Unified Framework for Clustering
- 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
- scientific article; zbMATH DE number 7071835 (Why is no real title available?)
- A continuum limit for the PageRank algorithm
- Large data limit of the MBO scheme for data clustering: -convergence of the thresholding energies
- 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
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)
