We focus in this work on the sets minimizing the Cheeger constant of a subset M of R^d. This latter 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 convergence 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).