Abstract: We present new methods for segmentation of large datasets with graph based structure. The method combines ideas from classical nonlinear PDE-based image segmentation with fast and accessible linear algebra methods for computing information about the spectrum of the graph Laplacian. The goal of the algorithms is to solve semi-supervised and unsupervised graph cut optimization problems. The methods make parallels between geometric ideas in Euclidean space such as motion by mean curvature, ported to a graphical framework. These ideas can be made rigorous through total variation minimization, and gamma convergence results, and convergence of time stepping methods in numerical analysis. We show diverse examples including image processing applications such as image and video labeling and hyperspectral video segmentation, and machine learning and community detection in social networks, including modularity optimization posed as a graph total variation minimization problem.
The Coble Memorial Lectures will be given March 27-29, 2018, by Andrea Bertozzi (UCLA). A reception will follow the first lecture on March 27.