Network Lasso: Clustering and Optimization in Large Graphs

Abstract

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 \emph{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.

References in corpus (3)

• Splitting Methods for Convex Clustering
• Hinge-loss Markov Random Fields: Convex Inference for Structured Prediction
• Feature Engineering for Knowledge Base Construction

Cited by in corpus (49)

• Meta-Path Guided Embedding for Similarity Search in Large-Scale Heterogeneous Information Networks
• Multitask learning over graphs: An Approach for Distributed, Streaming Machine Learning
• An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
• Network-Clustered Multi-Modal Bug Localization
• Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
• Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Provable Convex Co-clustering of Tensors
• Localized Linear Regression in Networked Data
• Gaussian Process Regression with Local Explanation
• Mumford-Shah functionals on graphs and their asymptotics
• Latent Variable Time-varying Network Inference
• Local Graph Clustering with Network Lasso
• Temporal Graph Signal Decomposition
• On the Duality between Network Flows and Network Lasso
• Convexity in complex networks
• Compressed Regression over Adaptive Networks
• Fast local linear regression with anchor regularization
• DJAM: distributed Jacobi asynchronous method for learning personal models
• Neural Generators of Sparse Local Linear Models for Achieving both Accuracy and Interpretability
• Element-wise estimation error of a total variation regularized estimator for change point detection
• Graph-based regularization for regression problems with alignment and highly-correlated designs
• Understanding and Predicting Delay in Reciprocal Relations
• Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach
• Social Discrete Choice Models
• Federated Learning From Big Data Over Networks
• On the Sample Complexity of Graphical Model Selection for Non-Stationary Processes
• Model-Agnostic Graph Regularization for Few-Shot Learning
• On Convex Clustering Solutions
• When is Network Lasso Accurate: The Vector Case
• Pursuit of the Cluster Structure of Network Lasso: Recovery Condition and Non-convex Extension
• Bayesian Model Selection with Graph Structured Sparsity
• Optimal partition recovery in general graphs
• Time Adaptive Gaussian Model
• svReg: Structural Varying-coefficient regression to differentiate how regional brain atrophy affects motor impairment for Huntington disease severity groups
• Learning Networked Exponential Families with Network Lasso
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
• Time-varying Graph Learning Under Structured Temporal Priors
• Multi-task Learning for Compositional Data via Sparse Network Lasso
• An Algorithm for Graph-Fused Lasso Based on Graph Decomposition
• High-dimensional Gaussian graphical model for network-linked data
• A Bayesian approach to multi-task learning with network lasso
• Convex Covariate Clustering for Classification
• New nonasymptotic convergence rates of stochastic proximal pointalgorithm for convex optimization problems
• PrecoG: an efficient unitary split preconditioner for the transform-domain LMS filter via graph Laplacian regularization
• Distributed and Asynchronous Algorithms for N-block Convex Optimization with Coupling Constraints
• Distributed Machine Learning for Predictive Analytics in Mobile Edge Computing Based IoT Environments
• Distributed Networked Real-time Learning
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models