Minimal Dirichlet Energy Partitions for Graphs

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.

• Publication year

  2013

• Venue

  SIAM Journal on Scientific Computing

• Publication date

  2013-08-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/130934568arXiv 1308.4915
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Threshold Dynamics for Networks with Arbitrary Surface Tensions

  2015cited by this paper
• Fast Multiclass Segmentation using Diffuse Interface Methods on Graphs

  2013cited by this paper
• Efficient Rearrangement Algorithms for Shape Optimization on Elliptic Eigenvalue Problems

  2013cited by this paper
• Multiclass Data Segmentation Using Diffuse Interface Methods on Graphs

  2013cited by this paper
• Mean Curvature, Threshold Dynamics, and Phase Field Theory on Finite Graphs

  2013cited by this paper
• Multiclass Total Variation Clustering

  2013cited by this paper
• Multiphase Shape Optimization Problems

  2013cited by this paper
• I and J

  2012cited by this paper
• Asymmetric Cheeger cut and application to multi-class unsupervised clustering

  2012cited by this paper
• Clustering by Nonnegative Matrix Factorization Using Graph Random Walk

  2012cited by this paper
• AN MBO SCHEME ON GRAPHS FOR SEGMENTATION AND IMAGE PROCESSING

  2012cited by this paper
• Finding Exemplars from Pairwise Dissimilarities via Simultaneous Sparse Recovery

  2012cited by this paper
• Approximation of Partitions of Least Perimeter by Γ-Convergence: Around Kelvin’s Conjecture

  2011cited by this paper
• NUMERICAL SIMULATIONS FOR NODAL DOMAINS AND SPECTRAL MINIMAL PARTITIONS

  2010cited by this paper
• COMPUTATIONAL AND APPLIED MATHEMATICS A Rayleigh-Chebyshev Procedure For Finding the Smallest Eigenvalues and Associated Eigenvectors of Large Sparse Hermitian Matrices

  2010cited by this paper
• On Spectral Minimal Partitions: A Survey

  2010cited by this paper
• Remarks on two notions of spectral minimal partitions

  2009cited by this paper
• the sphere

  2009cited by this paper
• Optimal Partitions for Eigenvalues

  2009influential reference
• Principal eigenvalue for an elliptic problem with indefinite weight on cylindrical domains.

  2008cited by this paper
• A tutorial on spectral clustering

  2007influential reference
• An Optimal Partition Problem for Eigenvalues

  2007influential reference
• Random walks and local cuts in graphs

  2007cited by this paper
• Clustering by Passing Messages Between Data Points

  2007cited by this paper
• Diffusion maps

  2006cited by this paper
• On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering

  2005cited by this paper
• Diffusion maps, spectral clustering and reaction coordinates of dynamical systems

  2005cited by this paper
• Image processing and analysis - variational, PDE, wavelet, and stochastic methods

  2005cited by this paper
• Numerical minimization of eigenmodes of a membrane with respect to the domain

  2004cited by this paper
• Efficient spatiotemporal grouping using the Nystrom method

  2001cited by this paper
• Symmetry Breaking and Other Phenomena in the Optimization of Eigenvalues for Composite Membranes

  1999cited by this paper
• Learning the parts of objects by non-negative matrix factorization

  1999cited by this paper
• Efficient Algorithms for Diffusion-Generated Motion by Mean Curvature

  1998cited by this paper
• Normalized cuts and image segmentation

  1997influential reference
• Spectral partitioning works: planar graphs and finite element meshes

  1996cited by this paper
• The two phase drum with the deepest bass note

  1991cited by this paper

• High-quality quad-dominant mesh generation aided by the virtual topological model generated after automatic suppression of small geometric features

  2026cites this paper
• Spectral minimal partitions of unbounded domains

  2025cites this paper
• An Efficient and Versatile Variational Method for High-Dimensional Data Classification

  2024cites this paper
• Stability of spectral partitions with corners

  2024cites this paper
• Homology of spectral minimal partitions

  2024cites this paper
• An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs

  2024cites this paper
• Graph-Based Active Learning for Nearly Blind Hyperspectral Unmixing

  2023cites this paper
• Escape times for subgraph detection and graph partitioning

  2022cites this paper
• A generalized expansion method for computing Laplace-Beltrami eigenfunctions on manifolds

  2022cites this paper
• The Potts Model with Different Piecewise Constant Representations and Fast Algorithms: A Survey

  2021cites this paper
• A Level Set Method for the Dirichlet k-Partition Problem

  2021cites this paper
• An efficient unconditionally stable method for Dirichlet partitions in arbitrary domains

  2021cites this paper
• A Level Set Method for the Dirichlet k-Partition Problem

  2021cites this paper
• A theory of spectral partitions of metric graphs

  2020cites this paper
• Dirichlet energy of Delaunay meshes and intrinsic Delaunay triangulations

  2020cites this paper
• Learning the Structure of Auto-Encoding Recommenders

  2020cites this paper
• A maximum principle argument for the uniform convergence of graph Laplacian regressors

  2019cites this paper
• A Two-stage Classification Method for High-dimensional Data and Point Clouds

  2019cites this paper
• Forecasting Trajectory and Behavior of Road-Agents Using Spectral Clustering in Graph-LSTMs

  2019cites this paper
• A diffusion generated method for computing Dirichlet partitions

  2018influential citation
• Diffusion generated methods for denoising target-valued images

  2018cites this paper
• Explorer Uncertainty quantification in graph-based classification of high dimensional data

  2018cites this paper
• Extremal spectral gaps for periodic Schrödinger operators

  2018cites this paper
• Optimal partition problems for the fractional Laplacian

  2017cites this paper
• Efficient algorithm for large spectral partitions

  2017cites this paper
• Discrete Version of an Optimal Partitioning Problem

  2017cites this paper
• Uncertainty Quantification in Graph-Based Classification of High Dimensional Data

  2017cites this paper
• Consistency of Dirichlet Partitions

  2017cites this paper
• An Effective Region Force for Some Variational Models for Learning and Clustering

  2017cites this paper
• A novel partitioning method for block-structured adaptive meshes

  2017cites this paper
• Towards Spectral Sparsification of Simplicial Complexes Based on Generalized Effective Resistance

  2017cites this paper
• Efficient algorithm for optimizing spectral partitions

  2017cites this paper
• Spectral sparsification of simplicial complexes for clustering and label propagation

  2017cites this paper
• Two-Dimensional Compact Variational Mode Decomposition

  2017cites this paper
• The method of fundamental solutions applied to boundary eigenvalue problems

  2016influential citation
• A minimal surface criterion for graph partitioning

  2016influential citation
• Minimal Partitions for p-norms of Eigenvalues

  2016cites this paper
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies

  2015cites this paper
• A Dirichlet Energy Criterion for Graph-Based Image Segmentation

  2015influential citation
• An eigenvalue optimization problem for graph partitioning

  2014cites this paper
• Towards a sampling theorem for signals on arbitrary graphs

  2014cites this paper
• A computational approach to an optimal partition problem on surfaces

  2014cites this paper
• Active semi-supervised learning using sampling theory for graph signals

  2014cites this paper
• Nonnegative Matrix Factorization of Transition Matrices via Eigenvalue Optimization

  2013cites this paper