Graph Merriman-Bence-Osher as a semidiscrete implicit Euler scheme for graph Allen-Cahn flow

Research output: Contribution to journalArticleScientificpeer-review


In recent years there has been an emerging interest in PDE-like flows defined on finite graphs, with applications in clustering and image segmentation. In particular for image segmentation and semisupervised learning Bertozzi and Flenner [Multiscale Model. Simul., 10 (2012), pp. 1090--1118] developed an algorithm based on the Allen--Cahn (AC) gradient flow of a graph Ginzburg--Landau functional, and Merkurjev, Kostić, and Bertozzi [SIAM J. Imaging Sci., 6 (2013), pp. 1903--1930] devised a variant algorithm based instead on graph Merriman--Bence--Osher (MBO) dynamics. This work offers rigorous justification for this use of the MBO scheme in place of AC flow. First, we choose the double-obstacle potential for the Ginzburg--Landau functional and derive well-posedness and regularity results for the resulting graph AC flow. Next, we exhibit a “semidiscrete” time-discretization scheme for AC flow of which the MBO scheme is a special case. We investigate the long-time behavior of this scheme and prove its convergence to the AC trajectory as the time-step vanishes. Finally, following a question raised by Van Gennip, Guillen, Osting, and Bertozzi [Milan J. Math., 82 (2014), pp. 3--65], we exhibit results toward proving a link between double-obstacle AC flow and mean curvature flow on graphs. We show some promising $\Gamma$-convergence results and translate to the graph setting two comparison principles used by Chen and Elliott [Proc. Math. Phys. Sci., 444 (1994), pp. 429--445] to prove the analogous link in the continuum.

Read More:
Original languageEnglish
Pages (from-to)4101–4139
Number of pages39
JournalSIAM Journal on Mathematical Analysis
Issue number5
Publication statusPublished - 2020


  • Allen–Cahn equation
  • Ginzburg–Landau functional
  • Merriman–Bence–Osher scheme
  • mean curvature flow
  • double-obstacle potential
  • graph dynamics
  • Γ-convergence

Fingerprint Dive into the research topics of 'Graph Merriman-Bence-Osher as a semidiscrete implicit Euler scheme for graph Allen-Cahn flow'. Together they form a unique fingerprint.

Cite this