# Learning the Structure of Large Networked Systems Obeying Conservation Laws

arXiv: https://arxiv.org/abs/2206.07083 · HTML: https://mlsanity.com/paper/2206.07083/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 78 references that are in the map.
- First posted on arXiv 14 Jun 2022.

## Builds on (most cited first, 17 of 17)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Stationary Graph Processes and Spectral Estimation](https://mlsanity.com/paper/1603.04667/) (2016)
- [Support recovery without incoherence: A case for nonconvex regularization](https://mlsanity.com/paper/1412.5632/) (2014)
- [Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming](https://mlsanity.com/paper/1310.0807/) (2013)
- [ROP: Matrix recovery via rank-one projections](https://mlsanity.com/paper/1310.5791/) (2013)
- [The Gaussian Graphical Model in Cross-sectional and Time-series Data](https://mlsanity.com/paper/1609.04156/) (2016)
- [Active Learning Algorithms for Graphical Model Selection](https://mlsanity.com/paper/1602.00354/) (2016)
- [Physics Informed Topology Learning in Networks of Linear Dynamical Systems](https://mlsanity.com/paper/1809.10535/) (2018)
- [Graphical Models in Meshed Distribution Grids: Topology estimation, change detection and limitations](https://mlsanity.com/paper/1905.06550/) (2019)
- [Thresholding Graph Bandits with GrAPL](https://mlsanity.com/paper/1905.09190/) (2019)
- [Modeling of Physical Network Systems](https://mlsanity.com/paper/1510.04984/) (2015)
- [Convex Formulation for Regularized Estimation of Structural Equation Models](https://mlsanity.com/paper/1809.06156/) (2018)
- [Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model](https://mlsanity.com/paper/2102.13135/) (2021)
- [Extreme Compressive Sampling for Covariance Estimation](https://mlsanity.com/paper/1506.00898/) (2015)
- [Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications](https://mlsanity.com/paper/1909.05487/) (2019)
- [Sparse Cholesky covariance parametrization for recovering latent structure in ordered data](https://mlsanity.com/paper/2006.01448/) (2020)

## Built on by (most cited first, 1 of 1)

- [Learning Networks from Wide-Sense Stationary Stochastic Processes](https://mlsanity.com/paper/2412.03768/) (2024)

## Abstract (arXiv)

Many networked systems such as electric networks, the brain, and social networks of opinion dynamics are known to obey conservation laws. Examples of this phenomenon include the Kirchoff laws in electric networks and opinion consensus in social networks. Conservation laws in networked systems may be modeled as balance equations of the form X = B* Y, where the sparsity pattern of B* captures the connectivity of the network, and Y, X ∈ ℝp are vectors of "potentials" and "injected flows" at the nodes respectively. The node potentials Y cause flows across edges and the flows X injected at the nodes are extraneous to the network dynamics. In several practical systems, the network structure is often unknown and needs to be estimated from data. Towards this, one has access to samples of the node potentials Y, but only the statistics of the node injections X. Motivated by this important problem, we study the estimation of the sparsity structure of the matrix B* from n samples of Y under the assumption that the node injections X follow a Gaussian distribution with a known covariance SigmaX. We propose a new ℓ1-regularized maximum likelihood estimator for this problem in the high-dimensional regime where the size of the network p is larger than sample size n. We show that this optimization problem is convex in the objective and admits a unique solution. Under a new mutual incoherence condition, we establish sufficient conditions on the triple (n,p,d) for which exact sparsity recovery of B* is possible with high probability; d is the degree of the graph. We also establish guarantees for the recovery of B* in the element-wise maximum, Frobenius, and operator norms. Finally, we complement these theoretical results with experimental validation of the performance of the proposed estimator on synthetic and real-world data.