Network Lasso: Clustering and Optimization in Large Graphs

By David Hallac, Jure Leskovec, Stephen P. Boyd. Knowledge Discovery and Data Mining, 2015

314 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/30fca19560538122f42c52cdce315257f9fb7b30

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

1. Huan Liu
2. Liang Wu
3. Jundong Li
4. Xia Hu
5. Xiao Huang
6. Jure Leskovec

In Computer Networks and Communications

1. Huan Liu
2. Jundong Li
3. Rok Sosic
4. Liang Wu
5. Xia Hu
6. Xiao Huang
7. Jure Leskovec
8. Jaewon Yang

In Statistics and Probability

1. Huan Liu
2. Liang Wu
3. Jundong Li
4. Xia Hu
5. Xiao Huang
6. Jure Leskovec
7. Rok Sosic

Citations in the corpus

• SNAP: A General Purpose Network Analysis and Graph Mining Library (2016, background): “2014], network optimization [Hallac et al. 2015], information diffusion [Leskovec et al.”
• Accelerated Attributed Network Embedding (2017, methodology): “It is also a regularization parameter that balances number of clusters [9, 22].”
• Tracing Fake-News Footprints: Characterizing Social Media Messages by How They Propagate (2018, methodology): “Motivated by recent research on network regularization, we fortify the representation of nodes with proximity by the network lasso regularization term [12]: where A ∈ R n × n is the microscopic structure matrix, A ij = 1 if we aim to preserve the proximity between i and j in the latent space.”