Phase-field models on graphs explained

Phase-field models on graphs are a discrete analogue to phase-field models, defined on a graph. They are used in image analysis (for feature identification) and for the segmentation of social networks.

Graph Ginzburg–Landau functional

For a graph with vertices V and edge weights

\omega _{i,j} , the graph Ginzburg–Landau functional of a map u:V\to R is given byF _{\varepsilon(u)} = (\varepsilon 2)/(\sum) _{i,j\in} \omega _{ij} (u _{i-u} ^{2} ^{j)} + (1 \varepsilon)/(\sum) _{i} 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 \varepsilon , minimisers of F _{\varepsilon} will satisfy that u_j is close to 0 or 1 for most nodes, splitting the nodes into two classes.

Graph Allen–Cahn equation

To effectively minimise

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,(d)/(dt) u _{j} = - \varepsilon (\Delta u) _{j - (1 \varepsilon)/(W'(u)} _{j),} where \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]

See also

• Graph cuts in computer vision

Notes and References

1. Bertozzi . A. . Andrea_Bertozzi . Flenner . A. . 2012-01-01 . Diffuse Interface Models on Graphs for Classification of High Dimensional Data . Multiscale Modeling & Simulation . 10 . 3 . 1090–1118 . 10.1137/11083109X . 1540-3459. 10.1.1.299.4261 .
2. Luo . Xiyang . Bertozzi . Andrea L. . 2017-05-01 . Convergence of the Graph Allen–Cahn Scheme . Journal of Statistical Physics . en . 167 . 3 . 934–958 . 10.1007/s10955-017-1772-4 . 2017JSP...167..934L . 1572-9613. free .
3. van Gennip, Yves. Graph Ginzburg–Landau: discrete dynamics, continuum limits, and applications. An overview. In Ei . S.-I. . Giga . Y. . Hamamuki . N. . Jimbo . S. . Kubo . H. . Kuroda . H. . Ozawa . T. . Sakajo . T. . Tsutaya . K. . 2019-07-30 . Proceedings of 44th Sapporo Symposium on Partial Differential Equations . Hokkaido University Technical Report Series in Mathematics . 177 . 89–102 . 10.14943/89899.