Back to Departmental Colloquium: Spring 2014
Departmental Colloquium
Date: Thursday, Feb 6, 2014
Time: 4:00PM
Location: LCB 219
Braxton Osting
Univeristy of California, Los Angeles
Title |
Geometric methods for graph partitioning |
Abstract |
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. |
Commutative Algebra
Combinatorics
Topology