Source-linked AI summary
Network Lasso: Clustering and Optimization in Large Graphs
David Hallac, Jure Leskovec, Stephen Boyd
TL;DR
The paper addresses the lack of optimization methods that are simultaneously general and scalable for large datasets. It introduces network lasso and a distributed ADMM solver, then applies the framework across several problem types; the authors report broad practical improvements, while the non-convex extension lacks global-optimality guarantees.
Problem
General convex optimization solvers often do not scale, while scalable solvers are frequently specialized to narrow problem classes.
Method
The paper formulates network lasso as graph optimization combining node objectives with norm-based edge regularization and solves it using distributed ADMM.
Results
The framework expresses many common problems and is reported as fast and accurate across binary classification, housing-price prediction, and event detection.
Takeaways & Limitations
Network lasso provides a unified way to combine optimization with graph-based clustering while retaining scalable distributed solution methods.
Takeaways & Limitations
The non-convex extension is not guaranteed to converge or reach a global optimum, and solutions can depend on initialization and algorithm parameters.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper introduces network lasso as a graph-based optimization framework that combines scalable optimization with clustering. It targets problems where generic solvers lack scalability and problem-specific methods lack generality.
- Motivation: Large-scale convex optimization needs solvers that are both broadly applicable and scalable to immense datasets.Classical interior-point methods can scale cubically with problem size when no exploitable structure is known.
- Formulation: Network lasso combines node-specific objectives with edge penalties that encourage neighboring variables to reach exact consensus.The edge penalty uses weighted norms of differences, while λ controls the trade-off between node objectives and agreement across edges.
- Clustering: For smaller λ, equal-valued nodes form clusters; sufficiently large λ can produce consensus across the entire graph.This supports simultaneous clustering and model fitting, including shared models for geographically related houses.
- Contributions: The proposed solver is distributed, scalable, and globally convergent for convex network lasso problems.Each vertex variable is managed by an agent that exchanges small messages over graph edges.
- Related work: The framework unifies a diverse class of optimization problems while occupying a stated trade-off between generality and scalability.The paper relates network lasso to Bayesian inference, general convex optimization, fused lasso, and total variation.
2. CONVEX PROBLEM DEFINITION
The convex network lasso problem assigns local objectives to graph nodes and norm-based penalties to differences across edges. Its regularization path ranges from independent node solutions to a common consensus solution, with intermediate values yielding clusters.
- Problem definition: Network lasso is a convex optimization problem over node variables, with optional private variables eliminated by partial minimization.The node variables may include local dummy variables that are not themselves included in the lasso penalty.
- Regularization path: At λ = 0, each node minimizes its own objective independently; as λ increases, neighboring solutions are increasingly encouraged to agree.λ scales edge objectives relative to node objectives.
- Regularization path: Intermediate regularization values define a path from local solutions to global consensus and can produce clustered node solutions.The clusters consist of nodes whose optimal variables are equal.
- Regularization path: Beyond a finite λcritical, the optimal solution is the consensus solution with the same variable at every node.Increasing λ further has no effect once consensus is reached.
- Network penalty: The edge penalty uses the ℓ2-norm of neighboring-variable differences, encouraging exact equality without heavily penalizing large outliers.Zero edge differences group connected nodes into sets sharing equal variable values.
- Inference on new nodes: A new node can be estimated by solving a weighted Weber problem using its neighboring solutions and edge weights.The estimate acts as a weighted median of neighbor solutions and remains computable for large problems.
3. PROPOSED SOLUTION
The proposed ADMM method decomposes network lasso into node- and edge-local updates that can be distributed across the graph. A warm-started regularization-path procedure reuses solutions across λ values and stops at consensus.
- Scalability: The paper presents network lasso as a distributed alternative for large problems where centralized methods and repeated path solves can be infeasible.The method is designed to avoid computational and storage limits constraining application scale.
- ADMM: The solver introduces edge-local copies of node variables, converting the problem into an ADMM-compatible consensus formulation.For each edge ij, zij copies xi and zji copies xj, with constraints enforcing equality.
- ADMM: The x-update is separable by node, so agents can solve their local subproblems independently and in parallel.This decomposition supports distributed computation over the graph.
- ADMM: The z-update and u-update are separable across edges, with the z-update jointly handling both directed copies on each edge.The z-update has a closed-form analytical solution, while u denotes the scaled dual variable.
- Convergence: Because the convex problem is solved with ADMM, the algorithm is guaranteed to converge to a global optimum.Stopping can use primal and dual residual thresholds, although high accuracy is typically reached more slowly than modest accuracy.
- Regularization path: The regularization path begins at λ = 0, increases λ geometrically, and stops when successive solutions reach consensus.Each new λ is warm-started from the previous solution, which can reduce distance from the next optimum.
4. NON-CONVEX EXTENSION
The paper replaces the convex network-lasso penalty with a concave function to better approximate ℓ0-style clustering, then adapts ADMM heuristically for the resulting non-convex problem. The method can favor consensus edges, but convergence and global optimality are no longer guaranteed.
- Replacing the group-lasso penalty with a nondecreasing concave function φ(u) brings the edge penalty closer to the ℓ0-norm.The group lasso penalizes the magnitude of every nonzero edge difference, whereas the concave penalty reduces this pull between already-separated clusters.
- Because the objective is non-convex, ADMM may fail to converge, may reach different solutions from different initial conditions, and is not guaranteed to find a global optimum.The implementation therefore tracks the lowest-objective iterate and runs for a fixed number of iterations because primal and dual residuals need not vanish.
- The non-convex extension changes only the ADMM z-update while retaining the convex-case algorithmic structure.The z-update reduces to a one-variable problem whose candidate solutions are compared by objective value.
- The z-update searches solutions on the line segment between the relevant endpoint vectors, including cases where the two solutions coincide.When the solutions coincide, the edge difference is zero and the edge is in consensus; otherwise, the optimizer lies on the segment between a and b.
- The algorithm compares all resulting candidate objectives and selects the z-update solution with the smallest objective.The comparison includes the consensus candidate and stationary solutions of the reduced one-variable problem.
- As λ increases, the quadratic equation more frequently has no real roots, so the update sets θ = 1/2 and places the edge in consensus.This rule is part of the easy-to-implement non-convex ADMM analogue, not a global-optimality guarantee.
5. EXPERIMENTS
The experiments apply network lasso to classification, housing-price prediction, and event detection, showing useful clustering, scalable optimization, and performance advantages over baselines.
- Experiments: Network lasso is evaluated on synthetic SVM classification, geographic housing-price prediction, and building event detection.The three applications illustrate how the framework handles heterogeneous optimization problems on graphs.
- Network-Enhanced Classification: 86.68% (convex) and 87.94% (non-convex) are the maximum SVM test-set prediction accuracies.Performance peaks near λ = 1, after which stronger coupling rapidly reduces accuracy by pulling different clusters together.
- Network-Enhanced Classification: ADMM solves problems with 1 million unknowns in seconds and 100 million unknowns in under 15 minutes.The method retains a general convex node-objective solver rather than relying on a specialized update class.
- Spatial Clustering with Regressors: A viable housing-data regularization level yields low MSE while partitioning the network into neighborhoods of different sizes.Small λ fails to form neighborhoods, whereas large λ forces together neighborhoods that are very different.
- Spatial Clustering with Regressors: Near the optimal housing-data λ, anomalous houses can form singleton clusters while separate models remain relatively accurate for the subsets.The method isolates nodes that do not fit their local model without strongly adversely affecting them or their neighbors.
- Event Detection in Time Series Data: The event-detection convex and non-convex methods outperform the Poisson baseline, although the convex approach performs noticeably better.The Poisson method requires 264 predictions to find all 30 reported events, and the reported events represent only partial ground truth.
6. CONCLUSION AND FUTURE WORK
The paper concludes that the network lasso provides a useful framework for understanding and improving machine learning and network-analysis problems. It identifies future directions for faster, more robust ADMM implementations and easier distributed software.
- The network lasso represents convex optimization problems within a single framework for machine learning and network analysis.
- Experimental improvements suggest that the network lasso merits further exploration and development.
- Future ADMM improvements include closed-form solutions for common objective functions, automatic selection of ρ, and more general edge objective functions.
- Easy-to-use software could let programmers solve large-scale optimization problems distributively without specifying implementation details.
A. ANALYTICAL SOLUTION TO Z-UPDATE
The section establishes uniqueness through strict convexity and derives the z-update by separating equal and unequal variable cases. Algebraic manipulation reduces the unequal case to linear equations and a threshold condition involving θ.
- Strict convexity guarantees that the z-update solution is unique.
- The derivation treats equal and unequal zij and zji as separate cases because the objective is nondifferentiable when their difference is zero.
- For unequal variables, setting the gradient to zero gives the necessary and sufficient optimality conditions.
- Treating μ as constant converts the equations for zij and zji into a linear system that can be solved algebraically.
- Substituting the solved variables into μ yields an equation that determines μ from ρ, c, and the distance between a and b.
- The unequal-variable solution is valid only under its stated condition on θ; otherwise, the equal-variable case applies with θ = 1/2.