Consistency of Cheeger and Ratio Graph Cuts
  This paper establishes the consistency of a family of graph-cut-based
algorithms for clustering of data clouds. We consider point clouds obtained as
samples of a ground-truth measure. We investigate approaches to clustering
based on minimizing objective functionals defined on proximity graphs of the
given sample. Our focus is on functionals based on graph cuts like the Cheeger
and ratio cuts. We show that minimizers of the these cuts converge as the
sample size increases to a minimizer of a corresponding continuum cut (which
partitions the ground truth measure). Moreover, we obtain sharp conditions on
how the connectivity radius can be scaled with respect to the number of sample
points for the consistency to hold. We provide results for two-way and for
multiway cuts. Furthermore we provide numerical experiments that illustrate the
results and explore the optimality of scaling in dimension two.
