A Dirichlet energy criterion for graph partitioning
主 题: A Dirichlet energy criterion for graph partitioning
报告人: Prof. Braxton Osting (The University of Utah)
时 间: 2015-01-08 10:30 - 11:30
地 点: 理科一号楼 1365
I'll discuss a 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, provides natural representatives for the clusters, and is related to a certain random process.