Convergence Analysis of the Graph Allen-Cahn Scheme

Abstract

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, 10(3):1090 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 2016
Accession Number
AD1014925

Entities

People

  • Andrea Bertozzi
  • Xiyang Luo

Organizations

  • University of California

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Science
  • Computer Programs
  • Data Sets
  • Eigenvalues
  • Eigenvectors
  • Equations
  • Information Science
  • Iterations
  • Machine Learning
  • Numerical Analysis
  • Probability
  • Probability Distributions
  • Random Walk
  • Reliability
  • Sequences
  • Theorems

Readers

  • Approximation Theory.
  • Computational Fluid Dynamics (CFD)
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms