# Network Lasso: Clustering and Optimization in Large Graphs

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2015.

## Built on by (most cited first, 30 of 43)

- [Efficient Distribution Similarity Identification in Clustered Federated Learning via Principal Angles Between Client Data Subspaces](https://mlsanity.com/paper/2209.10526/) (2022)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [Heterogeneous-Agent Trajectory Forecasting Incorporating Class Uncertainty](https://mlsanity.com/paper/2104.12446/) (2021)
- [Data-heterogeneity-aware Mixing for Decentralized Learning](https://mlsanity.com/paper/2204.06477/) (2022)
- [Temporal Graph Signal Decomposition](https://mlsanity.com/paper/2106.13517/) (2021)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [The Contextual Lasso: Sparse Linear Models via Deep Neural Networks](https://mlsanity.com/paper/2302.00878/) (2023)
- [Improving Your Graph Neural Networks: A High-Frequency Booster](https://mlsanity.com/paper/2210.08251/) (2022)
- [Clustered Federated Learning based on Nonconvex Pairwise Fusion](https://mlsanity.com/paper/2211.04218/) (2022)
- [On Convex Clustering Solutions](https://mlsanity.com/paper/2105.08348/) (2021)
- [Multi-Task Learning Regression via Convex Clustering](https://mlsanity.com/paper/2304.13342/) (2023)
- [Model-Agnostic Graph Regularization for Few-Shot Learning](https://mlsanity.com/paper/2102.07077/) (2021)
- [Learning with latent group sparsity via heat flow dynamics on networks](https://mlsanity.com/paper/2201.08326/) (2022)
- [Heterogeneous Federated Learning on a Graph](https://mlsanity.com/paper/2209.08737/) (2022)
- [Compressed Regression over Adaptive Networks](https://mlsanity.com/paper/2304.03638/) (2023)
- [Enabling tabular deep learning when d gg n with an auxiliary knowledge graph](https://mlsanity.com/paper/2306.04766/) (2023)
- [Time-varying Graph Learning Under Structured Temporal Priors](https://mlsanity.com/paper/2110.05018/) (2021)
- [A Bayesian approach to multi-task learning with network lasso](https://mlsanity.com/paper/2110.09040/) (2021)
- [flow-based clustering and spectral clustering: a comparison](https://mlsanity.com/paper/2206.10019/) (2022)
- [Binary Representation via Jointly Personalized Sparse Hashing](https://mlsanity.com/paper/2208.14883/) (2022)
- [Analysis of Total Variation Minimization for Clustered Federated Learning](https://mlsanity.com/paper/2403.06298/) (2024)
- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Federated k-Means over Networks](https://mlsanity.com/paper/2510.09718/) (2025)
- [Time Adaptive Gaussian Model](https://mlsanity.com/paper/2102.01238/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Inference of Multiscale Gaussian Graphical Model](https://mlsanity.com/paper/2202.05775/) (2022)
- [Online Heavy-tailed Change-point detection](https://mlsanity.com/paper/2306.09548/) (2023)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [Decentralised Traffic Incident Detection via Network Lasso](https://mlsanity.com/paper/2402.18167/) (2024)

## Abstract (arXiv)

Convex optimization is an essential tool for modern data analysis, as it provides a framework to formulate and solve many problems in machine learning and data mining. However, general convex optimization solvers do not scale well, and scalable solvers are often specialized to only work on a narrow class of problems. Therefore, there is a need for simple, scalable algorithms that can solve many common optimization problems. In this paper, we introduce the network lasso, a generalization of the group lasso to a network setting that allows for simultaneous clustering and optimization on graphs. We develop an algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve this problem in a distributed and scalable manner, which allows for guaranteed global convergence even on large graphs. We also examine a non-convex extension of this approach. We then demonstrate that many types of problems can be expressed in our framework. We focus on three in particular - binary classification, predicting housing prices, and event detection in time series data - comparing the network lasso to baseline approaches and showing that it is both a fast and accurate method of solving large optimization problems.