Local Graph Clustering with Network Lasso

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)

Authors

Date

2021

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

5

Series

IEEE Signal Processing Letters, Volume 28, pp. 106-110

Abstract

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.

Description

Keywords

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

Other note

DOI

10.1109/LSP.2020.3045832

Citation

Jung, A & Sarcheshmehpour, Y 2021, 'Local Graph Clustering with Network Lasso', IEEE Signal Processing Letters, vol. 28, 9298875, pp. 106-110. https://doi.org/10.1109/LSP.2020.3045832

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202108048179

Collections

[article-cris] Perustieteiden korkeakoulu / SCI