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

Ery Arias-Castro, Bruno Pelletier, Pierre Pudlo

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…