A variational approach to the consistency of spectral clustering

DOI10.1016/j.acha.2016.09.003zbMath1396.49013arXiv1508.01928OpenAlexW2963111412MaRDI QIDQ723005

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)

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

zbMATH Keywords

gamma-convergenceDirichlet energyrandom geometric graphspectral clusteringpoint cloudgraph 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)

Related Items (50)

A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors ⋮ Lipschitz Regularity of Graph Laplacians on Random Data Clouds ⋮ Measuring Segregation via Analysis on Graphs ⋮ Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model ⋮ From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Clustering Dynamics on Graphs: From Spectral Clustering to Mean Shift Through Fokker–Planck Interpolation ⋮ Large data limit for a phase transition model with the p-Laplacian on point clouds ⋮ A continuum limit for the PageRank algorithm ⋮ Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs ⋮ Graph approximations to the Laplacian spectra ⋮ Entropy dissipation of Fokker-Planck equations on graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Spectral analysis of weighted Laplacians arising in data clustering ⋮ Spectral clustering-based community detection using graph distance and node attributes ⋮ Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering ⋮ Consistency of Dirichlet Partitions ⋮ Deep limits of residual neural networks ⋮ On the Gamma convergence of functionals defined over pairs of measures and energy-measures ⋮ Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing ⋮ Rates of convergence for Laplacian semi-supervised learning with low labeling rates ⋮ Unnamed Item ⋮ An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs ⋮ Learning Theory for Dynamical Systems ⋮ Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator ⋮ Nonlocal gradient operators with a nonspherical interaction neighborhood and their applications ⋮ Mumford–Shah functionals on graphs and their asymptotics ⋮ Uniqueness of a solution to a general class of discrete system defined on connected graphs ⋮ Delay-coordinate maps, coherence, and approximate spectra of evolution operators ⋮ CURE: Curvature Regularization for Missing Data Recovery ⋮ Manifold learning with arbitrary norms ⋮ Gromov-Hausdorff limit of Wasserstein spaces on point clouds ⋮ Unnamed Item ⋮ Posterior consistency of semi-supervised regression on graphs ⋮ Think globally, fit locally under the manifold setup: asymptotic analysis of locally linear embedding ⋮ Properly-weighted graph Laplacian for semi-supervised learning ⋮ 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 ⋮ Fractional diffusion maps ⋮ A Geometrical Method for Low-Dimensional Representations of Simulations ⋮ Analysis of $p$-Laplacian Regularization in Semisupervised Learning ⋮ Delay-coordinate maps and the spectra of Koopman operators ⋮ On the rate of convergence of empirical measure in $\infty $-Wasserstein distance for unbounded density function ⋮ A multiscale environment for learning by diffusion ⋮ Transfer operators from optimal transport plans for coherent set detection ⋮ A Metric on Directed Graphs and Markov Chains Based on Hitting Probabilities ⋮ Unnamed Item ⋮ Consistency of Archetypal Analysis ⋮ Variational Limits of $k$-NN Graph-Based Functionals on Data Clouds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Continuum limit of total variation on point clouds
• Graph clustering
• A new approach to Sobolev spaces and connections to \(\Gamma\)-convergence
• Spectral clustering and the high-dimensional stochastic blockmodel
• Minimax grid matching and empirical measures
• Towards a theoretical foundation for Laplacian-based manifold methods
• Strong consistency of k-means clustering
• 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\)
• An introduction to \(\Gamma\)-convergence
• A graph discretization of the Laplace-Beltrami operator
• Consistency of spectral clustering
• Diffusion maps
• From graph to manifold Laplacian: the convergence rate
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
• Variational Analysis in Sobolev andBVSpaces
• Convergence of the $k$-Means Minimization Problem using $\Gamma$-Convergence
• 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
• Consistency of Single Linkage for High-Density Clusters
• A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies
• Random Geometric Graphs
• The Generic Chaining
• The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous
• Upper and Lower Bounds for Stochastic Processes
• Operator norm convergence of spectral clustering on level sets
• Learning Theory
• Expander flows, geometric embeddings and graph partitioning

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