# Local Graph Clustering with Network Lasso

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2020.

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

- [Graph Self-Supervised Learning: A Survey](https://mlsanity.com/paper/2103.00111/) (2021)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [Cluster Attack: Query-based Adversarial Attacks on Graphs with Graph-Dependent Priors](https://mlsanity.com/paper/2109.13069/) (2021)
- [Querying in the Age of Graph Databases and Knowledge Graphs](https://mlsanity.com/paper/2106.11456/) (2021)
- [Adaptive Local Clustering over Attributed Graphs](https://mlsanity.com/paper/2503.20488/) (2025)
- [Graph-based hierarchical record clustering for unsupervised entity resolution](https://mlsanity.com/paper/2112.06331/) (2021)
- [Survey of Generative Methods for Social Media Analysis](https://mlsanity.com/paper/2112.07041/) (2021)
- [Data-driven Influence Based Clustering of Dynamical Systems](https://mlsanity.com/paper/2204.02373/) (2022)
- [flow-based clustering and spectral clustering: a comparison](https://mlsanity.com/paper/2206.10019/) (2022)
- [Plug In and Learn: Federated Intelligence over a Smart Grid of Models](https://mlsanity.com/paper/2302.04363/) (2023)
- [Overlapping Community Detection in Temporal Text Networks](https://mlsanity.com/paper/2101.05137/) (2021)
- [A Modular Framework for Centrality and Clustering in Complex Networks](https://mlsanity.com/paper/2111.11623/) (2021)
- [Graph-theoretical approach to robust 3D normal extraction of LiDAR data](https://mlsanity.com/paper/2205.11460/) (2022)
- [Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs](https://mlsanity.com/paper/2209.14825/) (2022)

## Abstract (arXiv)

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.