The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous

DOI10.1239/aap/1354716583zbMath1318.62105arXiv1004.5485OpenAlexW3098439932MaRDI QIDQ4906501

Ery Arias-Castro, Pierre Pudlo, Bruno Pelletier

Publication date: 28 February 2013

Published in: Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

empirical processneighborhood graphspectral clustering\(U\)-processCheeger isoperimetric constant of a manifoldconductance of a graph

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Nonparametric estimation (62G05)

Related Items (13)

Kazdan-Warner equation on infinite graphs ⋮ Consistency of modularity clustering on random geometric graphs ⋮ From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Optimal Cheeger cuts and bisections of random geometric graphs ⋮ Diffusion \(K\)-means clustering on manifolds: provable exact recovery via semidefinite relaxations ⋮ Cheeger inequalities for unbounded graph Laplacians ⋮ A variational approach to the consistency of spectral clustering ⋮ Network connectivity assessment and improvement through relay node deployment ⋮ A Cheeger cut for uniform hypergraphs ⋮ Estimating perimeter using graph cuts ⋮ Theoretical Analysis of Active Contours on Graphs ⋮ Variational Limits of $k$-NN Graph-Based Functionals on Data Clouds ⋮ Continuum limit of total variation on point clouds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local empirical processes near boundaries of convex bodies
• Spectral partitioning works: planar graphs and finite element meshes
• Exact rates in density support estimation
• Towards a theoretical foundation for Laplacian-based manifold methods
• Some remarks on uniqueness and regularity of Cheeger sets
• The theory of multidimensional persistence
• On the area and perimeter of a random convex hull in a bounded convex set
• Granulometric smoothing
• Computing persistent homology
• On the cover time and mixing time of random geometric graphs
• Consistency of spectral clustering
• Finding the homology of submanifolds with high confidence from random samples
• Variation and optimization of formes. A geometric analysis
• From graph to manifold Laplacian: the convergence rate
• A nonparametric approach to the estimation of lengths and surface areas
• $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
• Curvature Measures
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
• Topology and data
• A note on the isoperimetric constant
• Random Geometric Graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Weak feature size and persistent homology
• Operator norm convergence of spectral clustering on level sets
• A graph-based estimator of the number of clusters
• On the Volume of Tubes

This page was built for publication: The Normalized Graph Cut and Cheeger Constant: From Discrete to Continuous