Mass-conserving diffusion-based dynamics on graphs

Abstract

An emerging technique in image segmentation, semi-supervised learning and general classification problems concerns the use of phase-separating flows defined on finite graphs. This technique was pioneered in Bertozzi and Flenner (2012, Multiscale Modeling and Simulation 10(3), 1090-1118), which used the Allen-Cahn flow on a graph, and was then extended in Merkurjev et al. (2013, SIAM J. Imaging Sci. 6(4), 1903-1930) using instead the Merriman-Bence-Osher (MBO) scheme on a graph. In previous work by the authors, Budd and Van Gennip (2020, SIAM J. Math. Anal. 52(5), 4101-4139), we gave a theoretical justification for this use of the MBO scheme in place of Allen-Cahn flow, showing that the MBO scheme is a special case of a 'semi-discrete' numerical scheme for Allen-Cahn flow. In this paper, we extend this earlier work, showing that this link via the semi-discrete scheme is robust to passing to the mass-conserving case. Inspired by Rubinstein and Sternberg (1992, IMA J. Appl. Math. 48, 249-264), we define a mass-conserving Allen-Cahn equation on a graph. Then, with the help of the tools of convex optimisation, we show that our earlier machinery can be applied to derive the mass-conserving MBO scheme on a graph as a special case of a semi-discrete scheme for mass-conserving Allen-Cahn. We give a theoretical analysis of this flow and scheme, proving various desired properties like existence and uniqueness of the flow and convergence of the scheme, and also show that the semi-discrete scheme yields a choice function for solutions to the mass-conserving MBO scheme.