# Multiclass Data Segmentation using Diffuse Interface Methods on Graphs

arXiv: https://arxiv.org/abs/1302.3913 · HTML: https://mlsanity.com/paper/1302.3913/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2013.

## Built on by (most cited first, 15 of 15)

- [Graph-based Active Learning for Semi-supervised Classification of SAR Data](https://mlsanity.com/paper/2204.00005/) (2022)
- [Double-well Net for Image Segmentation](https://mlsanity.com/paper/2401.00456/) (2023)
- [Graph Laplacian for Semi-Supervised Learning](https://mlsanity.com/paper/2301.04956/) (2023)
- [BASiS: Batch Aligned Spectral Embedding Space](https://mlsanity.com/paper/2211.16960/) (2022)
- [Consistency of semi-supervised learning, stochastic tug-of-war games, and the p-Laplacian](https://mlsanity.com/paper/2401.07463/) (2024)
- [An Empirical Study of Graph-Based Approaches for Semi-Supervised Time Series Classification](https://mlsanity.com/paper/2104.08153/) (2021)
- [Joint reconstruction-segmentation on graphs](https://mlsanity.com/paper/2208.05834/) (2022)
- [Integrating Transformer and Autoencoder Techniques with Spectral Graph Algorithms for the Prediction of Scarcely Labeled Molecular Data](https://mlsanity.com/paper/2211.06759/) (2022)
- [Persistent Laplacian-enhanced Algorithm for Scarcely Labeled Data Classification](https://mlsanity.com/paper/2305.16239/) (2023)
- [MALADY: Multiclass Active Learning with Auction Dynamics on Graphs](https://mlsanity.com/paper/2409.09475/) (2024)
- [Graph-Based Semi-Supervised Segregated Lipschitz Learning](https://mlsanity.com/paper/2411.03273/) (2024)
- [Graph-Based Bidirectional Transformer Decision Threshold Adjustment Algorithm for Class-Imbalanced Molecular Data](https://mlsanity.com/paper/2406.06479/) (2024)
- [Interface Laplace Learning: Learnable Interface Term Helps Semi-Supervised Learning](https://mlsanity.com/paper/2408.05419/) (2024)
- [Neural Networks for Threshold Dynamics Reconstruction](https://mlsanity.com/paper/2412.09079/) (2024)
- [Propagate, Then Sharpen: Post-Hoc Refinement of Frozen Node Classifiers](https://mlsanity.com/paper/2609.35080/) (2026)

## Abstract (arXiv)

We present two graph-based algorithms for multiclass segmentation of high-dimensional data. The algorithms use a diffuse interface model based on the Ginzburg-Landau functional, related to total variation compressed sensing and image processing. A multiclass extension is introduced using the Gibbs simplex, with the functional's double-well potential modified to handle the multiclass case. The first algorithm minimizes the functional using a convex splitting numerical scheme. The second algorithm is a uses a graph adaptation of the classical numerical Merriman-Bence-Osher (MBO) scheme, which alternates between diffusion and thresholding. We demonstrate the performance of both algorithms experimentally on synthetic data, grayscale and color images, and several benchmark data sets such as MNIST, COIL and WebKB. We also make use of fast numerical solvers for finding the eigenvectors and eigenvalues of the graph Laplacian, and take advantage of the sparsity of the matrix. Experiments indicate that the results are competitive with or better than the current state-of-the-art multiclass segmentation algorithms.