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. 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.
We also provide efficient code to solve the much faster, linearized minimal surface criterion instead (Dirichlet energy).

The toolbox includes a simple five-moons test data set (dbmoon.mat) and example code to reproduce the five-moons example.

The code is immediately based on the following two papers (to referred to as documentation and to be cited as reference):

[1] Dominique Zosso, Braxton Osting, "A minimal surface criterion for graph partitioning", Inverse Problems and Imaging 10(4):1149-1180, 2016. http://dx.doi.org/10.3934/ipi.2016036

and its linearized, faster version :

[2] Dominique Zosso, Braxton Osting, Stanley J. Osher, "A Dirichlet Energy Criterion for Graph-Based Image Segmentation", 2015 IEEE ICDM Workshop. http://dx.doi.org/10.1109/ICDMW.2015.112