Learning the Structure of Large Networked Systems Obeying Conservation Laws
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 \in
\mathbb{R}^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
$\Sigma_X$. We propose a new $\ell_{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.