Article
A MINIMAL SURFACE CRITERION FOR GRAPH PARTITIONING
Authors
Dominique Zosso, Braxton Osting
Publication
Inverse Problems and Imaging
Abstract
We consider a geometric approach to graph partitioning based on the graph Beltrami energy, a discrete version of a functional that appears in classical minimal surface problems. More specifically, the optimality criterion is given by the sum of the minimal Beltrami energies of the partition components. Since the Beltrami energy interpolates between the Total Variation and Dirichlet energies, various results for optimal partitions for these two energies can be recovered. We adapt primal-dual convex optimization methods to solve for the minimal Beltrami energy for each component of a given partition. A rearrangement algorithm is proposed to find the graph partition to minimize a relaxed version of the objective. The method is applied to several clustering problems on graphs constructed from manifold discretizations, synthetic data, the MNIST handwritten digit dataset, and image segmentation. The model has a semisupervised extension and provides a natural representative for the clusters as well.
Links
How is this information collected?
This collection of Montana State authored publications is collected by the Library to highlight the achievements of Montana State researchers and more fully understand the research output of the University. They use a number of resources to pull together as complete a list as possible and understand that there may be publications that are missed. If you note the omission of a current publication or want to know more about the collection and display of this information email Leila Sterman.