Mean curvature, threshold dynamics, and phase field theory on finite graphs

Abstract

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.

76 pages, 7 figures (consisting of 25 subfigures in total) v2 has a typo in Lemma 5.2, isolated, but important for potential future use/reference. Corrected in v3. Some ambiguities in Section 3.3 are clarified in v4

References in corpus (4)

• Regularity for non-local almost minimal boundaries and applications
• Analysis and Comparison of Large Time Front Speeds in Turbulent Combustion Models
• Nonlinear elliptic Partial Differential Equations and p-harmonic functions on graphs
• Calculus on Graphs

Cited by in corpus (21)

• Algebraic Representations for Volumetric Frame Fields
• Minimal Dirichlet energy partitions for graphs
• Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images
• The Total Variation Flow in Metric Random Walk Spaces
• Classification and image processing with a semi-discrete scheme for fidelity forced Allen--Cahn on graphs
• A Graph Framework for Manifold-valued Data
• NFFT meets Krylov methods: Fast matrix-vector products for the graph Laplacian of fully connected networks
• Graph MBO as a semi-discrete implicit Euler scheme for graph Allen-Cahn flow
• A metric on directed graphs and Markov chains based on hitting probabilities
• An MBO scheme for minimizing the graph Ohta-Kawasaki functional
• Stochastic Block Models are a Discrete Surface Tension
• Variational Graph Methods for Efficient Point Cloud Sparsification
• $(BV,L^p)$-decomposition, $p=1,2$, of Functions in Metric Random Walk Spaces
• A mean curvature flow arising in adversarial training
• Diffusion generated methods for denoising target-valued images
• Graph Laplacian-based Bayesian Multi-fidelity Modeling
• Joint reconstruction-segmentation on graphs
• Semi-Supervised First-Person Activity Recognition in Body-Worn Video
• A Nonlocal Graph-PDE and Higher-Order Geometric Integration for Image Labeling
• Principal eigenvalue problem for infinity Laplacian in metric spaces
• Semi-supervised Learning for Aggregated Multilayer Graphs Using Diffuse Interface Methods and Fast Matrix Vector Products