Geometric methods for graph partitioning

Start: 05/04/2015 - 12:00pm
End  : 05/04/2015 - 1:00pm

Applied Math Seminar

Braxton Osting (University of Utah)


Several geometric methods for graph partitioning have been introduced in the past few years, with wide applications in clustering, community detection, and image analysis. These methods, which I'll review, are built on graph-based analogues of total variation, motion by mean curvature, the Ginzburg-Landau functional, and the Merriman-Bence-Osher threshold dynamics. In this talk, I'll discuss a new graph partitioning method where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. The resulting eigenvalue optimization problem can be solved by a rearrangement algorithm, which we show to converge in a finite number of iterations to a local minimum of a relaxed objective function. The method compares well to state-of-the-art approaches when applied to clustering problems on graphs constructed from synthetic data, MNIST handwritten digits, and manifold discretizations. The model has a semi-supervised extension and provides natural representatives for the clusters as well.

Kravis 100