Local Graph Clustering with Network Lasso

2020-04-25 · Alexander Jung, Yasmin SarcheshmehPour

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 boundary 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 nonsmooth optimization allows to approximate nLasso solutions with optimal worst-case convergence rate.

📄 PDF Abstract BibTeX arXiv:2004.12199

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringGraph Clustering

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

The Cluster Graphical Lasso for improved estimation of Gaussian graphical models

2013-07-19 · Kean Ming Tan, Daniela Witten, Ali Shojaie

We consider the task of estimating a Gaussian graphical model in the high-dimensional setting. The graphical lasso, which involves maximizing the Gaussian log likelihood subject to an l1 penalty, is a well-studied approa…

Clustering Model Selection

On the Duality between Network Flows and Network Lasso

2019-10-04 · Alexander Jung

Many applications generate data with an intrinsic network structure such as time series data, image data or social network data. The network Lasso (nLasso) has been proposed recently as a method for joint clustering and …

Clustering Time Series Time Series Analysis

Statistical control for spatio-temporal MEG/EEG source imaging with desparsified multi-task Lasso

2020-09-29 · Jérôme-Alexis Chevalier, Alexandre Gramfort, Joseph Salmon, Bertrand Thirion

Detecting where and when brain regions activate in a cognitive task or in a given clinical condition is the promise of non-invasive techniques like magnetoencephalography (MEG) or electroencephalography (EEG). This probl…

Clustering Constrained Clustering EEG Electroencephalogram (EEG)+2

Statistical control for spatio-temporal MEG/EEG source imaging with desparsified mutli-task Lasso

2020-12-01 · NeurIPS 2020 12 · Jerome-Alexis Chevalier, Joseph Salmon, Alexandre Gramfort, Bertrand Thirion

Clustering Constrained Clustering EEG Electroencephalogram (EEG)+2

Analysis of Network Lasso for Semi-Supervised Regression

2018-08-22 · A. Jung, N. Vesselinova

We apply network Lasso to semi-supervised regression problems involving network structured data. This approach lends quite naturally to highly scalable learning algorithms in the form of message passing over an empirical…

Clustering regression