  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.
