Mean curvature, threshold dynamics, and phase field theory on finite graphs
In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatori...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Springer Basel
2014
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/3186/ |
| _version_ | 1848790973371383808 |
|---|---|
| author | van Gennip, Yves Guillen, Nestor Osting, Braxton Bertozzi, Andrea L. |
| author_facet | van Gennip, Yves Guillen, Nestor Osting, Braxton Bertozzi, Andrea L. |
| author_sort | van Gennip, Yves |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatorial problems, which demands deeper theoretical underpinnings of the graph processes. The aim of this paper is to introduce these graph processes in the light of their continuum counterparts, provide some background, prove the first results connecting them, illustrate these processes with examples and identify open questions for future study.
We derive a graph curvature from the graph cut function, the natural graph counterpart of total variation (perimeter). This derivation and the resulting curvature definition differ from those in earlier literature, where the continuum mean curvature is simply discretized, and bears many similarities to the continuum nonlocal curvature or nonlocal means formulation. This new graph curvature is not only relevant for graph MBO dynamics, but also appears in the variational formulation of a discrete time graph mean curvature flow.
We prove estimates showing that the dynamics are trivial for both MBO and AC evolutions if the parameters (the time-step and diffuse interface scale, respectively) are sufficiently small (a phenomenon known as ``freezing'' or ``pinning'') and also that the dynamics for MBO are nontrivial if the time step is large enough. These bounds are in terms of graph quantities such as the spectrum of the graph Laplacian and the graph curvature. Adapting a Lyapunov functional for the continuum MBO scheme to graphs, we prove that the graph MBO scheme converges to a stationary state in a finite number of iterations. Variations on this scheme have recently become popular in the literature as ways to minimize (continuum) nonlocal total variation. |
| first_indexed | 2025-11-14T18:21:07Z |
| format | Article |
| id | nottingham-3186 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:21:07Z |
| publishDate | 2014 |
| publisher | Springer Basel |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-31862020-05-04T20:18:19Z https://eprints.nottingham.ac.uk/3186/ Mean curvature, threshold dynamics, and phase field theory on finite graphs van Gennip, Yves Guillen, Nestor Osting, Braxton Bertozzi, Andrea L. In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatorial problems, which demands deeper theoretical underpinnings of the graph processes. The aim of this paper is to introduce these graph processes in the light of their continuum counterparts, provide some background, prove the first results connecting them, illustrate these processes with examples and identify open questions for future study. We derive a graph curvature from the graph cut function, the natural graph counterpart of total variation (perimeter). This derivation and the resulting curvature definition differ from those in earlier literature, where the continuum mean curvature is simply discretized, and bears many similarities to the continuum nonlocal curvature or nonlocal means formulation. This new graph curvature is not only relevant for graph MBO dynamics, but also appears in the variational formulation of a discrete time graph mean curvature flow. We prove estimates showing that the dynamics are trivial for both MBO and AC evolutions if the parameters (the time-step and diffuse interface scale, respectively) are sufficiently small (a phenomenon known as ``freezing'' or ``pinning'') and also that the dynamics for MBO are nontrivial if the time step is large enough. These bounds are in terms of graph quantities such as the spectrum of the graph Laplacian and the graph curvature. Adapting a Lyapunov functional for the continuum MBO scheme to graphs, we prove that the graph MBO scheme converges to a stationary state in a finite number of iterations. Variations on this scheme have recently become popular in the literature as ways to minimize (continuum) nonlocal total variation. Springer Basel 2014 Article PeerReviewed van Gennip, Yves, Guillen, Nestor, Osting, Braxton and Bertozzi, Andrea L. (2014) Mean curvature, threshold dynamics, and phase field theory on finite graphs. Milan Journal of Mathematics, 82 (1). pp. 3-65. ISSN 1424-9286 spectral graph theory Allen-Cahn equation Ginzburg-Landau functional Merriman-Bence-Osher threshold dynamics graph cut function total variation mean curvature flow nonlocal mean curvature gamma convergence graph coarea formula http://dx.doi.org/10.1007/s00032-014-0216-8 doi:10.1007/s00032-014-0216-8 doi:10.1007/s00032-014-0216-8 |
| spellingShingle | spectral graph theory Allen-Cahn equation Ginzburg-Landau functional Merriman-Bence-Osher threshold dynamics graph cut function total variation mean curvature flow nonlocal mean curvature gamma convergence graph coarea formula van Gennip, Yves Guillen, Nestor Osting, Braxton Bertozzi, Andrea L. Mean curvature, threshold dynamics, and phase field theory on finite graphs |
| title | Mean curvature, threshold dynamics, and phase field theory on finite graphs |
| title_full | Mean curvature, threshold dynamics, and phase field theory on finite graphs |
| title_fullStr | Mean curvature, threshold dynamics, and phase field theory on finite graphs |
| title_full_unstemmed | Mean curvature, threshold dynamics, and phase field theory on finite graphs |
| title_short | Mean curvature, threshold dynamics, and phase field theory on finite graphs |
| title_sort | mean curvature, threshold dynamics, and phase field theory on finite graphs |
| topic | spectral graph theory Allen-Cahn equation Ginzburg-Landau functional Merriman-Bence-Osher threshold dynamics graph cut function total variation mean curvature flow nonlocal mean curvature gamma convergence graph coarea formula |
| url | https://eprints.nottingham.ac.uk/3186/ https://eprints.nottingham.ac.uk/3186/ https://eprints.nottingham.ac.uk/3186/ |