On Graph Cut and the Cheeger Constant

• Activity Number: 181
• Type: Contributed
• Date/Time: Monday, August 1, 2011 : 10:30 AM to 12:20 PM
• Sponsor: IMS
• Author(s): Bruno Pelletier*+ and Ery Arias-Castro and Pierre Pudlo
• Companies: Universite Rennes 2 and University of California at San Diego and Universite Montpellier 2, France
• Keywords: Isoperimetric inequality ; Graph cut ; Clustering ; U-statistics ; Empirical processes

Abstract

In connection with graph partitioning clustering algorithms, we consider the estimation of the sets minimizing the Cheeger constant of a subset M of R^d. The Cheeger constant minimizes the ratio of a perimeter to a volume among all subsets of M. Given an n-sample drawn from the uniform measure on M, we introduce a regularized version of the conductance of the neighborhood graph defined on the sample. Then, we establish the convergence of the regularized conductance to the Cheeger constant of M. In addition, we prove the convergence of the sequences of optimal graph partitions to the Cheeger sets of M for the topology of L1(M). This result implies the consistency of a penalized bipartite graph cut algorithm.