Groups and interactions in data, networks and biology

Consistency of Cheeger and ratio graph cuts

Nicolas Garcia Trillos

Brown University

In this talk I consider point clouds obtained as samples of a ground-truth measure. The purpose is to investigate approaches to clustering based on minimizing objective functionals defined on proximity graphs of the given sample of points. The focus is on functionals based on graph cuts like the Cheeger and ratio cuts. I will discuss some results about the convergence of minimizers of these cuts as the sample size increases, towards a minimizer of a corresponding continuum cut (which partitions the ground-truth measure). Moreover, I will present sharp conditions on how the connectivity radius can be scaled with respect to the number of sample points for the consistency to hold. I will provide results for two-way and for multiway cuts. This is joint work with Dejan Slepcev, James von Brecht, Thomas Laurent and Xavier Bresson.