Minimal Dirichlet energy partitions for graphs

Abstract

Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulation is identified and a novel rearrangement algorithm is proposed, which we show is strictly decreasing and converges in a finite number of iterations to a local minimum of the relaxed objective function. Our method is applied to several clustering problems on graphs constructed from synthetic data, MNIST handwritten digits, and manifold discretizations. The model has a semi-supervised extension and provides a natural representative for the clusters as well.

17 pages, 6 figures

References in corpus (2)

• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• On spectral minimal partitions: the case of the sphere

Cited by in corpus (10)

• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
• Learning the Structure of Auto-Encoding Recommenders
• Spectral Sparsification of Simplicial Complexes for Clustering and Label Propagation
• Uncertainty quantification in graph-based classification of high dimensional data
• Extremal Spectral Gaps for Periodic Schrödinger Operators
• A diffusion generated method for computing Dirichlet partitions
• Optimal partition problems for the fractional laplacian
• Diffusion generated methods for denoising target-valued images
• Efficient algorithm for large spectral partitions