Minimal Dirichlet energy partitions for graphs
This work addresses graph partitioning for clustering applications, offering a novel approach with potential benefits in data analysis, but it appears incremental as it builds on existing eigenvalue-based methods.
The authors tackled the problem of graph partitioning by introducing a new non-convex objective based on Dirichlet eigenvalues, proposing a rearrangement algorithm that converges to local minima, and applied it to clustering tasks on synthetic data, MNIST, and manifold discretizations, achieving results that provide cluster representatives and semi-supervised extensions.
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.