Dirichlet Graph Partitions

Tuesday, April 11, 2017 - 1:25pm - 2:25pm
Lind 305
Braxton Osting (The University of Utah)
I’ll discuss a geometric approach to graph partitioning where the optimality criterion is given by the sum of the first Laplace-Dirichlet eigenvalues of the partition components. This 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. This partitioning method compares well to state-of-the-art approaches on a variety of graphs constructed from manifold discretizations, synthetic data, the MNIST handwritten digit dataset, and images. Finally, I'll present a consistency result for geometric graphs, stating convergence of graph partitions to an appropriate continuum partition.