Structure Learning via ADMM in Networks obeying Conservation Laws
Rohith Reddy Mada, Rajasekhar Anguluri · 2025
Read Structure Learning via ADMM in Networks obeying Conservation Laws by Rohith Reddy Mada, Rajasekhar Anguluri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03189.txt.
Introduction
Rohith Reddy Mada and Rajasekhar Anguluri wrote this paper in two thousand twenty-five. It learns the wiring of a network from flow samples, for systems where what flows in must flow out, with a fast split algorithm.
The hidden wiring sits in the sparsity pattern of a Laplacian matrix that links flows to potentials. Past work set up a penalized likelihood fit but solved it with a slow general tool. The new method uses ADMM, the alternating direction method of multipliers, which is clear and fast. A Riccati equation turns out to run the core update. Tests on fake and real power and water nets show the speed.
Catalog record
| CREATOR | Rohith Reddy Mada, Rajasekhar Anguluri |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-03189
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Structure Learning via ADMM in Networks obeying Conservation Laws Rohith Reddy Mada, Rajasekhar Anguluri 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 = L ∗ y x=L^{\ast}y , where x x and y ∈ ℝ p y\in\mathbb{R}^{p} represent injected flows (inputs) and potentials (outputs), respectively. The sparsity pattern of the p × p p\times p Laplacian L ∗ L^{\ast} 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 y . Recent work by [ 1 ] has established statistical consistency results for this learning problem by considering an ℓ 1 \ell_{1} -regularized maximum likelihood estimator. However, their approach did not develop a scalable algorithm but relies on solving a convex program via the CVX package. To address this gap, we propose an alternating direction method of multipliers (ADMM), which is transparent and fast. A key contribution is to demonstrate the role of an algebraic matrix Riccati equation in the primal update step of ADMM. Numerical experiments on a host of synthetic and benchmark networks, including power and water systems, show the efficiency of our method. I Introduction Critical infrastructure systems—such as power, water, and traffic networks—are modeled as graphs, where conservation laws enforce that nodal flows across the edges of the network are neither created nor lost. In steady state, these conservation laws reduce to linear relation x=L^{*}y , where L^{*}\in\mathbb{R}^{p\times p} is a weighted symmetric Laplacian encoding the network’s edge structure through its off-diagonal entries [ 2 ] . The p -dimensional vectors x and y denote nodal injections and potentials, respectively. In practice, the edge connectivity structure is unknown and must be learned from data [ 3 , 4 , 5 ] . This entails recovering the sparsity pattern of the unknown (true) L^{*} using finite samples or summary statistics of the injection–potential pairs \{x,y\} . Assuming random injection x , and given the sample covariance matrix S of y , [ 1 ] proposed estimating the network structure by solving the optimization problem: \displaystyle\hat{L}=\underset{L\in\mathcal{S}_{p}^{++}}{\text{arg\,min }}\Tr(SL^{2})-2\log\det(L)+\lambda\|L\|_{1,\text{off}}, (1) where \mathcal{S}_{p}^{++} is the set of real-valued p\times p symmetric positive definite matrices and \|L\|_{1,\text{off}} is the \ell_{1} -norm applied to off-diagonals of L . The edge structure can then be inferred from the sparsity pattern of the estimate \hat{L} (see Section II ). Ref. [ 1 ] have established many properties of the problem in ( 1 ). Chief among them are that the problem is convex and that its statistical complexity depends on the maximum degree of the network. Further, ( 1 ) is related to many graph learning problems (see related work in [ 1 , 6 ] ). Thus, developing simple and fast iterative algorithms for solving ( 1 ) is of great interest. This motivates our use of the alternating direction method of multipliers (ADMM). We highlight that although ( 1 ) resembles the sparse inverse covariance estimation (ICE) problem in graphical models, a key difference lies in the trace \operatorname{Tr(\cdot)} . In ( 1 ), \operatorname{Tr}(\cdot) is quadratic in the variable L , whereas in ICE it is linear. This subtle yet significant distinction makes the development of an ADMM for ( 1 ) challenging and interesting. Our contributions are: 1. For the unregularized case ( \lambda=0 ), we show that the global minimizer \hat{L} of ( 3 ) is equal to the inverse of the positive semi-definite square root matrix of the sample covariance S , if inverse exists (see Prop. II.1 ). 2. We propose a simple ADMM algorithm to numerically solve the structure learning problem in ( 3 ) for any \lambda\geq 0 . We show that the dual and Lagrange multiplier update subproblems can be solved in closed form. 3. The primal subproblem of our ADMM algorithm does not admit closed-form solution, as it involves solving an algebraic Riccati equation (NARE). Therefore, we resort to a Newton’s method to solve the NARE. In Remark 1 , we clarify why this is not an issue in the closely related sparse ICE problem in Gaussian graphical models. Numerical results on many synthetic and real-world benchmark networks demonstrate the superior efficiency (in terms of iterations and execution time; see Table. I ) of our ADMM method compared to the CVX-based approach in [ 1 ] . The limitations of the proposed approach and future work are discussed toward the end of the paper. Related Research : There is a wide literature on developing ADMM-based methods for matrix-valued statistical learning problems (see [ 7 , 8 , 9 ] ). Structure learning in conservation networks has been studied in various contexts, which broadly fall into two categories. The first is the mean-based approach, where both x and y are observed, reducing the learning problem to a sparse regression task [ 10 , 11 , 12 ] . The second category assumes x and y are random, but only y is observed. Here, the network is inferred from the (sample) covariance of y (see [ 4 , 13 , 1 , 14 ] ). Notably, [ 3 ] and [ 5 ] surveys structure learning in power systems. II Preliminaries and Problem Setup Consider an undirected, connected graph with p+1 nodes, where the node set is V=\{0,1,2,\ldots,p\} and the edge set E\subset V\times V . Each edge (i,j)\in E is assigned a non-negative weight a_{ij}\geq 0 . Let x,y\in\mathbb{R}^{p+1} denote the vectors of nodal injections and potentials, respectively. The conservation law is represented by x=L_{\text{full}}^{*}y , where L_{\text{full}}^{*}\in\mathbb{R}^{(p+1)\times(p+1)} is the full Laplacian matrix defined by [L^{*}_{\text{full}}]_{ij}=\begin{cases}-a_{ij},&\text{if }i\neq j,\\ \sum_{k\neq i}a_{ik},&\text{if }i=j.\end{cases} Thus, (i,j)\in E iff [L^{*}_{\text{full}}]_{ij}\neq 0 . The applicability of linear conservation laws and their extensions is elegantly discussed in [ 2 ] . Fig. 1 illustrates the sparsity pattern of L^{*} . Following [ 6 , 1 , 4 ] , we work with the reduced Laplacian matrix L^{*} , obtained by removing node 0 and its incident edges from the graph. In particular, L^{*}\in\mathbb{R}^{p\times p} is formed by deleting the row and column corresponding to node 0 from L_{\text{full}}^{*} . The reduced matrix is symmetric and positive definite, and therefore invertible, ensuring that L^{*} , or at least its sparsity pattern, can be recovered from data. Fig. 1: sparsity pattern of a Laplacian encoding edge structure : (left) A network consisting of seven nodes labeled in a counterclockwise direction, with node 1 positioned to the left of node 7. Each node is assigned a pair (x_{i},y_{i}) , where arrows represent the injection of flows x_{i} . (right) The indices of blue-colored cells in L^{*} indicate the presence of edges between nodes identified by these indices, while white-colored cells signify the absence of edges. Structure learning problem [ 1 ] : Estimate the sparsity pattern of the unknown true Laplacian matrix L^{*} using N i.i.d. samples of the potential vector y , assuming that the nodal injection vector x is a zero-mean Gaussian random vector with a known, inverse covariance matrix \Theta_{x}\succ 0 . The Gaussian random injection assumption is common in the literature