Phase-field models on graphs

For a graph with vertices V and edge weights ${\displaystyle \omega _{i,j}}$, the graph Ginzburg–Landau functional of a map ${\displaystyle u:V\to \mathbb {R} }$ is given by

${\displaystyle F_{\varepsilon }(u)={\frac {\varepsilon }{2}}\sum _{i,j\in V}\omega _{ij}(u_{i}-u_{j})^{2}+{\frac {1}{\varepsilon }}\sum _{i\in V}W(u_{i}),}$

where W is a double well potential, for example the quartic potential W(x) = x²(1 − x²). The graph Ginzburg–Landau functional was introduced by Bertozzi and Flenner. [1] In analogy to continuum phase-field models, where regions with u close to 0 or 1 are models for two phases of the material, vertices can be classified into those with u_j close to 0 or close to 1, and for small ${\displaystyle \varepsilon }$, minimisers of ${\displaystyle F_{\varepsilon }}$ will satisfy that u_j is close to 0 or 1 for most nodes, splitting the nodes into two classes.

To effectively minimise ${\displaystyle F_{\varepsilon }}$, a natural approach is by gradient flow (steepest descent). This means to introduce an artificial time parameter and to solve the graph version of the Allen–Cahn equation,

${\displaystyle {\frac {d}{dt}}u_{j}=-\varepsilon (\Delta u)_{j}-{\frac {1}{\varepsilon }}W'(u_{j}),}$

where ${\displaystyle \Delta }$ is the graph Laplacian. The ordinary continuum Allen–Cahn equation and the graph Allen–Cahn equation are natural counterparts, just replacing ordinary calculus by calculus on graphs. A convergence result for a numerical graph Allen–Cahn scheme has been established by Luo and Bertozzi.[2]

It is also possible to adapt other computational schemes for mean curvature flow, for example schemes involving thresholding like the Merriman–Bence–Osher scheme, to a graph setting, with analogous results.[3]

• Graph cuts in computer vision