A variational approach to the consistency of spectral clustering

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

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

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
• Title not available (Why is that?)
• 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?)
• Title not available (Why is that?)
• 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
• 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 (61)

• 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
• 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
• Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing
• Conditional expectation using compactification operators
• 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
• Properly-weighted graph Laplacian for semi-supervised learning
• Variational Limits of $k$-NN Graph-Based Functionals on Data Clouds
• Delay-coordinate maps and the spectra of Koopman operators
• A Geometrical Method for Low-Dimensional Representations of Simulations
• Title not available (Why is that?)
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Delay-coordinate maps, coherence, and approximate spectra of evolution operators
• Deep limits of residual neural networks
• On the rate of convergence of empirical measure in $\infty $-Wasserstein distance for unbounded density function
• Graph approximations to the Laplacian spectra
• On the Gamma convergence of functionals defined over pairs of measures and energy-measures
• 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
• Mumford–Shah functionals on graphs and their asymptotics
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Title not available (Why is that?)
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• CURE: Curvature Regularization for Missing Data Recovery
• Learning Theory for Dynamical Systems
• An exemplar-based clustering using efficient variational message passing
• Title not available (Why is that?)
• Entropy dissipation of Fokker-Planck equations on graphs
• Title not available (Why is that?)
• Consistency of Dirichlet Partitions
• Posterior consistency of semi-supervised regression on graphs
• Nonlocal gradient operators with a nonspherical interaction neighborhood and their applications
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Lipschitz Regularity of Graph Laplacians on Random Data 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
• Title not available (Why is that?)
• Measuring Segregation via Analysis on Graphs
• Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation
• Spectral clustering-based community detection using graph distance and node attributes
• A multiscale environment for learning by diffusion
• Analysis of $p$-Laplacian Regularization in Semisupervised Learning
• Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering
• A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities
• Transfer operators from optimal transport plans for coherent set detection
• Title not available (Why is that?)
• Consistency of Archetypal Analysis
• A continuum limit for the PageRank algorithm
• A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors
• 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)