Diffuse Interface Models on Graphs for Classification of High Dimensional Data

This paper is a republication of an MMS paper [A. L. Bertozzi and A. Flenner, Multiscale Model. Simul., 10 (2012), pp. 1090--1118] describing a new class of algorithms for classification of high dimensional data. These methods combine ideas from spectral methods on graphs with nonlinear edge/region detection methods traditionally used in the PDE-based imaging community. The algorithms use the Ginzburg--Landau functional, extended to a graphical framework, which has classical PDE connections to total variation minimization. Convex splitting algorithms allow us to quickly find minimizers of the proposed model and take advantage of fast spectral solvers of linear graph-theoretic problems. We review the diverse computational examples presented in the original paper, involving both basic clustering and semisupervised learning for different applications. Case studies include feature identification in images, segmentation in social networks, and segmentation of shapes in high dimensional datasets. Since the pape...