Convergence Analysis of the Graph Allen-Cahn Scheme
University of California Los Angeles Los Angeles United States
Pagination or Media Count:
Graph partitioning problems have a wide range of applications in machine learning. This work analyzes convergence conditions for a class of diffuse interface algorithm A.L. Bertozziand A. Flenner, Multiscale Modeling and Simulation, 1031090 1118, 2012 for binary and multi-class partitioning. Using techniques from numerical PDE and convex optimization, convergence and monotonicity are shown for a class of schemes under a graph-independent timestep restriction. We also analyze the effects of spectral truncation, a common technique used to save computational cost. Convergence of the scheme with spectral truncation is also proved under a timestep restriction inversely proportional to the size of the graph. Moreover, this restriction is shown to be sharp in a worst case. Various numerical experiments are done to compare theoretical results with practical performance.
- Operations Research
- Theoretical Mathematics