Dejan Slepčev
Carnegie Mellon University

Variational Problems on Graphs and Their Continuum Limits

Abstract
We discuss variational problems arising in machine learning and their limits as the number of data points goes to infinity. Consider point clouds obtained as random samples of an underlying "ground-truth" measure on a Euclidean domain. Graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points. Many machine learning tasks, such as clustering and classification, can be posed as minimizing functionals on such graphs. We consider functionals involving graph cuts and their limits. The question is considered in the setting of Gamma convergence. The Gamma limit, and associated compactness property, are considered with respect to a topology which uses optimal transportation to suitably compare $L^1$ functions defined on graphs, that is with respect to the empirical measure of the random sample, with functions defined with respect to the continuum ground-truth measure. Taking the Gamma limit relies on connecting the graph cuts with the nonlocal continuum perimeter. The talk is primarily based on joint work with Nicolas Garcia Trillos, as well as on works with Xavier Bresson, Thomas Laurent, and James von Brecht.
Back to schedule
Back to main page