An MBO scheme for clustering and semi-supervised clustering of signed networks

Mihai Cucuringu, Andrea Pizzoferrato, Yves Van Gennip

Research output: Contribution to journalArticlepeer-review

5 Citations (SciVal)
26 Downloads (Pure)


We introduce a principled method for the signed clustering problem, where the goal is to partition a weighted undirected graph whose edge weights take both positive and negative values, such that edges within the same cluster are mostly positive, while edges spanning across clusters are mostly negative. Our method relies on a graph-based diffuse interface model formulation utilizing the Ginzburg-Landau functional, based on an adaptation of the classic numerical Merriman-Bence-Osher (MBO) scheme for minimizing such graph-based functionals. The proposed object ive function aims to minimize the total weight of inter-cluster positively-weighted edges, while maximizing the total weight of the inter-cluster negatively-weighted edges. Our method scales to large sparse networks, and can be easily adjusted to incorporate labelled data information, as is often the case in the context of semisupervised learning. We tested our method on a number of both synthetic stochastic block models and real-world data sets (including financial correlation matrices), and obtained promising results that compare favourably against a number of state-of-the-art approaches from the recent literature.

Original languageEnglish
Pages (from-to)73-109
Number of pages37
JournalCommunications in Mathematical Sciences
Issue number1
Publication statusPublished - 24 Mar 2021


  • clustering
  • graph Laplacians
  • Merriman—Bence—Osher scheme
  • signed networks
  • spectral methods
  • threshold dynamics
  • time series

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics


Dive into the research topics of 'An MBO scheme for clustering and semi-supervised clustering of signed networks'. Together they form a unique fingerprint.

Cite this