Sparse Structure Learning via ADMM in Networks Obeying Conservation Laws

Abstract

Learning the edge connectivity structure of networked systems from limited data is a fundamental challenge in many critical infrastructure domains, including power, traffic, and finance. Such systems obey steady-state conservation laws: x(t) = L∗y(t), where x(t) and y(t) ∈ Rᵖ represent injected flows (inputs) and potentials (outputs), respectively. The sparsity pattern of the p x p Laplacian L* encodes the underlying edge structure. In a stochastic setting, the goal is to infer this sparsity pattern from zero-mean i.i.d. samples of y(t). Recent work by Rayas et al. [1] has established statistical consistency results for this learning problem by considering an ℓ₁-regularized maximum likelihood estimator. However, their approach did not focus on developing a scalable algorithm but relies on solving a convex program via the CVX package in Python. To address this gap, we propose an alternating direction method of multipliers (ADMM) algorithm. Our approach is simple, transparent, and computationally fast. A key contribution is demonstrating the role of a non-symmetric algebraic Riccati equation in the primal step of ADMM. Numerical experiments on a host of synthetic and benchmark networks, including power and water systems, show that our method achieves high recovery accuracy.