Variational Limits of Graph Cuts on Point Clouds

The main goal of this thesis is to develop tools that enable us to study the convergence of minimizers of functionals defined on point clouds towards minimizers of equivalent functionals in the continuum; the point clouds we consider are samples of a ground-truth distribution. In particular, 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 these cuts converge as the sample size increases to a minimizer of a corresponding continuum cut (which partitions the ground-truth distribution). 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 multi-way cuts. The results are obtained by using the notion of Γ-convergence and an appropriate choice of metric which allows us to compare functions defined on point clouds with functions defined on continuous domains.