Local Graph Clustering with Network Lasso

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)
55 Downloads (Pure)


We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundaries and seed nodes. While spectral clustering methods are guided by a minimization of the graph Laplacian quadratic form, nLasso minimizes the total variation of cluster indicator signals. As demonstrated theoretically and numerically, nLasso methods can handle very sparse clusters (chain-like) which are difficult for spectral clustering. We also verify that a primal-dual method for non-smooth optimization allows to approximate nLasso solutions with optimal worst-case convergence rate.

Original languageEnglish
Article number9298875
Pages (from-to)106-110
Number of pages5
JournalIEEE Signal Processing Letters
Early online date2020
Publication statusPublished - 2021
MoE publication typeA1 Journal article-refereed


  • Clustering methods
  • Convergence
  • Laplace equations
  • Message passing
  • Minimization
  • Optimization
  • TV


Dive into the research topics of 'Local Graph Clustering with Network Lasso'. Together they form a unique fingerprint.

Cite this