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

Abstract

Let M be a bounded domain of a Euclidian space with smooth boundary. We relate the Cheeger constant of M and the conductance of a neighborhood graph defined on a random sample from M. By restricting the minimization defining the latter over a particular class of subsets, we obtain consistency (after normalization) as the sample size increases, and show that any minimizing sequence of subsets has a subsequence converging to a Cheeger set of M.

References in corpus (3)

• Consistency of spectral clustering
• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• A nonparametric approach to the estimation of lengths and surface areas

Cited by in corpus (5)

• Continuum limit of total variation on point clouds
• A Sampling Theory Perspective of Graph-based Semi-supervised Learning
• Diffusion $K$-means clustering on manifolds: provable exact recovery via semidefinite relaxations
• A Cheeger Cut for Uniform Hypergraphs
• Distributional limits of graph cuts on discretized grids