Learning the Structure of Large Networked Systems Obeying Conservation Laws
Authors: Anirudh Rayas
Rajasekhar Anguluri
Gautam Dasarathy
Venue: NeurIPS 2022 Accept (2022)
Keywords: Structure Learning
Networked Systems
Conservation Laws
Gaussian Graphical models
Sparsistency
High dimensional regime

Abstract: 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 are modeled as balance equations of the form $X = B^\ast Y$, where the sparsity pattern of $B^\ast \in \mathbb{R}^{p\times p}$ captures the connectivity of the network on $p$ nodes, 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 which aim to balance out the potential difference, 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 to facilitate modeling, management, and control. To this end, 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^\ast$ 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 tackling this problem in the high-dimensional regime where the size of the network may be vastly larger than the number of samples $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^\ast$ is possible with high probability; $d$ is the degree of the underlying graph. We also establish guarantees for the recovery of $B^\ast$ 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.

Learning the Structure of Large Networked Systems Obeying Conservation Laws
Anirudh Rayas Arizona State University
Rajasekhar Anguluri Arizona State University rangulur@asu. edu
Gautam Dasarathy Arizona State University gautamd@asu. edu
ahrayasOasu.edi
Abstract
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 electric networks and opinion consensus in social networks, Conservation laws in networked systems are modeled as Y*Y, where the sparsity pattern of E Rexp
balance equations of the form captures the connectivity of the network of potentials and injected flows at the nodes respectively. The node potentials cause flows across edges which aim to balance out the potential difference, and the flows X injected at the nodes are extraneous to the network dynamics. practical systems, the network structure often unknown and needs to be estimated from data to facilitate modeling, management, and control. To this end, 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 3* from samples of Y under the assumption that the node injections X follow a Gaussian distribution with a known covariance Ex. We propose a new f1-regularized maximum likelihood estimator for tackling this problem in the high-dimensional regime where the size of the network may be vastly larger than the number of samples n. We show that this optimization problem is convex in the objective and admits a unique solution. Under 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; and is the degree of the underlying graph. We also establish guarantees for the recovery of B* in the element-wise maximum, Frobenius, and operator norms. Finally, we complement our theoretical results with experimental validation of the performance of the proposed estimator on synthetic and real-world data.
p nodes, and Y, X Rº vectors
several
1 Introduction
Let G = ([p), E)) be a directed graph on the vertex set [p] & (1.2.....P} with a size m edge set E c [p] [p]. Let D denote the p incidence matrix that encodes the edges of G as follows: each column D associated with an edge (i.j) E and a vector of zeros except at the locations i and where it is - and +1 respectively. Let X R be vector of injected flows signals at the vertices and let f E Ih'h be the vector of flows through the edges. Then, the basic conservation law between these flows may be expressed as Df + X 0; that is, at each vertex, the flow (which is a linear combination of flows at the edges incident on the vertex) has to balance the injections. In physical systems, edge flows f often arise as a way to balance the differences between certain potentials Y E R2 at the vertices. That is, the flows satisfy f - TY: notice that this implies that
"This work was supported in part by the National Science Foundation (NSF) under the grants CCF-2048223 and OAC-1934766, and by the National Institutes of Health (NIH) under the grant IRO1 IRO1GM1 GM140468-01
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the flow at the edge (1 is given by y, Yz Thus, the above conservation law yields the following relationship, called balance equation, between the node potentials and injected flows:
X B²Y=0.
where B" - DD E RPxP is the symmetric Laplacian matrix [4, 60]. In an electrical circuit (with unit resistances on edges), Y corresponds the voltage potentials at the vertices, f corresponds to the edge currents, and X denotes the injected currents at the vertices. Indeed, this picture can be generalized by assigning weights the edges of the network (conductances in the case of an electric network). and allowing the flows to be weighted by these weights. The model in (1) is referred to as generalized Kirchoff's law, and importantly, this models the relationship between flows and potentials in range of systems that satisfy conservation laws such as hydraulic networks. opinion consensus in networks (see [60, 40, 55] and references therein).
social networks, and transportation/distrbbuiiii
It can be readily seen that the Laplacian B" is a positive semi-definite that encodes the edges of G. Specifically, (i.j) E E if and only if B A O. The Laplacian lies at the heart of spectral graph theory [15], and owing to its fascinating properties has found a range of applications in diverse areas such image processing, manifold learning, spectral clustering, and bandits [52, 6, 62, 58, 32, 56]. In this paper, we consider a situation where the edge set E' of the graph is unknown and needs to be estimated from measurements of the node potentials Y. Based on the above discussion, we will cast this as a problem of learning an unknown positive definite B" (or the sparsity pattern thereof) from measurements of Y. Further, we suppose that we only have access to the statistics of X, namely, that it is a O-mean Gaussian random vector with covariance matrix Σx. The situations where Ex is unknown and B is non-invertible briefly discussed in the remarks in Section 2. We list a variety of applications where this learning problem arises naturally.
1. Topology learning in electric networks: Consider an electric network (or circuit) with nodes, current injections X, node voltages Y, conductances A. 2 between nodes i and j. and shunt conductances As 2 0 connecting i-th node to the ground. The current- balance equation is given by (1), where B" the Laplacian with Bi -Ay and B;; A4+ +E Aij [21]. In real electric grids, current injections are unknown random variables. To ensure reliable power supply, learning 3 and its underlying graph from voltage samples is important and has been widely studied [20, 33, 13, 1J. The current-bal -aarentt-bbaaneeeeee equation also appears in Markov chains and flow networks where Kirchoff laws apply [60, 46].
2. Brain connectivity from graph filters: The structural connectivity of the human brain is often studied using a network with nodes representing brain regions, and the edge weights representing the density of anatomical connections [45, 25, 61]. Recent studies showed that the weights can be inferred using gileer satisfying (I) with 8* = (E/=) ) where A is the symmetric adjacency matrix; by is the filter coefficient; and X is the latent graph signal. For brain networks, [51, 36] showed that L = is a reasonable choice. Additionally, for large L, the graph filter B" can be approximated as B = 1 - a using matrix power series expansion, thus a feasible choice for analysis. Graph filters are also used in social and protein interaction networks [50, 37].
3. Structural equation models (SEM): Structural equation models are used to explain relation- ships among exploratory variables in several domains; for e.g.. psychoanalysis [22], social sciences [16], medical research, and neuroimaging [7, 47, 38]. Using SEMs, [42] provided a causal interpretation of Linear Hawkes Processes. In SEM with no latent variables, we let y= Ay + x. where A is the path matrix. Then the SEM satisifies (1) with B =I A.
4. Linear dynamical (diffusion) networks: These network dynamics are satisfied by many sys- tems including consensus dynamics, thermal capacitance networks, power swing dynamics, [54]. Further, by lifting approach, these dynamics can be used to study periodic/cyclic behavior in atmospheric systems [53].
Before we detail our topology discovery method, we comment on a few competing approaches that only have limited utility in our setting. First, penalized (nodal) regression methods [39] are not applicable here since these require samples of both X and Y. Yet other works have considered the estimation of topology from linear measurements [2, 9, 33, 65, 11, 14, 18, 19]. but these assume direct linear access to the graph (via the adjacency or appropriate covariances) or assume low-rankedness in the underlying structure. A recent line of work [20, 1], proposed estimating 3 by estimating the

---

inverse covariance (or precision) matrix O* of Y using the graphical LASSO (GLASSO) [66, 23]. In particular, [20, 1] showed that O' has non-zeros corresponding to those pairs of vertices that are connected by paths of length at most two; that is, the (i. entry of @* is non zero if and only if (i, is an edge in 9 or there is a [p] such that A - j is path in G. The authors then estimated edges of G by identifying (and eliminating) the pairs of vertices that have two-hop connections in & (see Fig. 1)-for future reference, we call this estimator as GLASSO+2HR (2 hop refinement). However, this estimator requires strong structural assumptions on G such triangle- freeness. Further, the precision matrix @* of Y is far more dense than the underlying graph G since x
O* X (B*)). (T=)"; this results in sub-optimal data requirements for reliable recovery (see Remark 3). Finally, if Σx is a diagonal matrix, we can estimate the sparsity pattern of B* by taking the principal square root of the empirical covariance matrix of Y. Unfortunately, this method does not allow for any corrllation between the node injections which is not the case in practice. Importantly, this method is numerically unstable unless one has a large number of samples (z) of Y so that the empirical covariance matrix is invertible-22 requirement that is at odds with the high-dimensional regime where one typically desires n to be smaller than the number of variables p.
In light of the limitations of previous approaches, we study natural penalized maximum likelihood estimator for B" using the samples {Y;)== This estimator not only statistically efficient but also obviates the restrictive assumptions imposed by the aforementioned methods. We now summarize the main contributions the paper:
We propose novel & regularized maximum likelihood estimator (MLE) for B from samples of YY. It is worth noting that the optimization program we propose is not the standard graphical LASSO program [66, 23] as involves terms that are quadratic in the optimization variable. Our first result shows that, notwithstanding its form, the E regularized MLE is convex in B and it has unique minimum even in the high-dimensional regime (n < p) under certain standard conditions.
Under new mutual incoherence condition, we provide sufficient condition on the number of samples n required to recover the exact sparsity of B with high probability. Furthermore, under these sufficient conditions we also establish the consistency of our estimator in the element-wiss maximum, Frobenius, and spectral norms. Formally, we show that if (d log then with where d is the degree of the underlying graph.
high probability | - l E
theoretical results with experimental results both on the synthetic data sets and data from a benchmark power distribution system. Our experiments demonstrate the clear benefit of the proposed estimator over baseline and competing methods.
Finally, complement
(a) true graph (b) graphical model (c) MLE (this paper) (d) GLASSO+2HR
Figure 1: Stylistic visualization of 4 4-MLEE vs GLASSO+2HR in [20]. (a) True graph & with B"; (b) graphical model of - = """""(""'* (c) estimate of B by our proposed E regulaariz MLE estimator; and (d) estimate of B by GLASSO [20]. Graph G and the graphical model of O" have same of vertices; however, in the latter, there are spurious edges (dashed lines (b)) between vertices that are two-hop neighbors in & (see main text in Introduction). In Fig 1(c) and I(d), we depict potential outputs of & -MLE and GLASSO+2HR respectively for some sample covariance matrix. Since the outputs are random objects, the graphs in Fig (cc) and 1(d) can have missing and false edges that are not present in the true graph in ((a). The GLASSO+2HR estimate advocated in [20] recovers B" by first estimating O = B E'E'' (B*)* which potentially dense when compared to B" (see Fig ((a) and Fig 1(b)). Hence, the GLASSS++HR estimate in Fig I(d) might have more edges than the true graph. However, since our MMME directly estimates the sparse matrix B", likely, the estimated and the true graph might only differ on a few edges, shown in Fig I (c). Our experimental results in Section 4 validate this claim.
Organization of the paper: Section 2, we introduce an errgeuulrrized ML estimation problem for networked systems obeying conservation laws. In Section 3, we show that this optimization problem convex the objective and establish consistency and support recovery rates for our estimator. In Section 4, we provide simulation results. In Section 5, we summarize paper with future directions.
3

---

Notation: For any two subsets Ti and T22 of [p] [p], we denote by AT,T, the submatrix of A with rows and columns indexed by Ti and T2, respectively. When Ti = T2 we denote the submatrix by Ar, For a matrix = (As.) E Roxp, we use || - maxi, [Ayl to denote the maximum element-wise norm, and ||-|]|r and |A]| to denote the Frobenius norm and the operator norm. We denote the -matrix norm of A defined as
=l maxx==1....p Σ5=1 Ayjl- We use ||A||I.off = E, |Ayi to denote the off-diagonal é norm. We use (Ac(A) to denote the p²-vector formed by stacking the columns of A and use ((A) = (/ < A) to denote the kronecker product of A with the identity matrix T. For symmetric positive definite matrices A and A2, we use A > A to denote A₁ - A2 is positive definite. We define sign(Asg) = +1 Arj > and sign(AA) = -1 if As < O. For two-real valued functions f-) and g(-), we write f(n) (g())) if f(n) S cg(n)
and (() = Mig(n)) if (n) 2 c'g(n) for constants e, c' > O.
Problem Setup
Consider a p-dimensional random vector X following the Gaussian distribution (N, Σx) with known covariance matrix Σx > 0 (we outline relaxation of this assumption in Remark 1). Let Y = (B*)-'X with a p x p matrix B* > and note that Y N O*-"), where 0 B Bx B". Define the sample covariance matrix S n >i= Y.Y,", where (Y,.... Y,) } the n (possibly
n < p) i.i.d. samples of Y. For some A, > 0, we consider the & regularized MLE for estimating B*:
arg min B~0,0=BEx-1
[Tr(S)) log det + \
(2)
is the 4-norm applied to the off-diagonal entries of B E RRPP, The loss function in (2) without the & penalty is the negative log- log-likelihood of Y,, and maximizing it to estimate B" yields an unrestricted MLE.
where || 1,00 = Eijt} BBy]
The optimization problem in (2) looks similar to the & lrreuularized log-determinant problem. which has a rich, long history in high-dimensional statistics, machine learning, signal processing, and network sciences (see for instance [35, 3, 66, 23)). The bulk of this literature focuses on estimating O". The resultant estimator, referred to as the graphical LASSO (or GLASSO), has many nice theoretical properties (e.g., asymptotic consistency and support recovery in the high-dimensional regime) [48, 49, 67]. However, our estimator in (2) is significantly different from GLASSO because we are estimating B" rather than O', Other studies close to our setup estimate sparse Cholesky factor of O' [27. 17, 28]. Recall that the Cholesky decomposition is given by O' LL" where L > 0 is a lower triangular matrix. We differ from this line of work on multiple fronts: (i) we do not require B to be a lower upper triangular Cholesky factor; (ii) our method allows for arbitrary correlations between the nodal injections resulting in an extra Σx² between the factors; and (iii) to the best of our knowledge, ours is the first work to provide guarantees on the sample complexity for estimating 8* in the high-dimensional regime.
Remark 1. (Unknown covariance matrix Σx). In problem (2), we assume that Σx is known. If this is not the case, we can slightly modify (2) to estimate B" D instead of B', where D is the unique square root of Σx1 satisfying 2 Σx* This approach works best if the sparsity of B" (approximately) equals the sparsity of B* D, which for instance happens when Σxx is (approximately) diagonal. II
Remark 2. (On invertibility of B*) The invertiblity assumption of B ensures that B is identifiable from samples. This holds in several upplications including the ones in (2)-(4) ) in Section 1. However, this might not be true if B" is a Laplacian matrix that has zero eigenvalues. One common work around (see e.g., [24, 20, 21]) is to work with reduced Laplacian matrix by deleting k rows and columns of B (we employ this insight in our experiments; see Section 4).
3 A Convex Estimator and Statistical Guarantees
In this section, we first recast the objective in (2) in terms of B for a known Ex. We then present our main results on the performance of our estimator in (2) when X is Gaussian and non-Gaussian. We comment on extending our results to other convex loss functions and conclude with an overview of the key steps in proving our results. Full details are given in the appendix.
We begin by rewriting the problem in (2) in form that is more suitable to methods of analysis. Let D be the unique square root of ynx satisfying D2 Vxx (sce [8]). Substituting B BT and

---

θ = =B in the cost function of (2) yields the following:
arg B=-
arg min [T(DDBBDD) log det + An |
(3)
where we use the fact that the trace operator cyclic and the determinant of a matrix product equals the product of matrix determinants. We dropped constants that have no effect on the estimate. The symmetry and invertibility of B is sufficient enough to ensure that log(+) is well-defined. In other words, the positive-definttness assumption is not needed for the well- pell-posessess of (3).
Lemma below is the starting point of our analysis. It establishes two key properties of the estimator
in (3) under the positive definiteness of B: (i) loss function in (3) is convex in B and (ii) B is unique. The following result is proved in Appendix A.3.
Lemma 1. (Convexity and Uniqueness) For any Xn >0 0 and B O, if the diagonal elements of the sample covariance matrix Sü > 0 for all i, then (i) the l-llog determinant problem in (3) is convex and (i) B in (3) is the unique minima satisfying the sub- mub-gradient condition 2D BS BS-2B - Z= O. Here Z belong to the sub-gradient BlI I off with Zip = 0, for i = and Zij = sign( (iz) when
B, # 0 and Ziyl 5 when Bij = 0. for #
few comments of Lemma are in order. (Cnvexity) First, we recall that the compositions of two convex functions is in general not convex. As example, consider two convex functions f(x) = x² and g(z) = -r, however, (f())) = =²² is not convex. Therefore, in light of the fact that the loss function is a composite function of B, it is not clear if (3) is convex. Nonetheless, in Lemma I we prove that (3) is a convex program. Key to our proof is the notion of monotone convex functions. (Uniqueness) Second, the uniqueness result is non- non-trivial in gigh-dimensions (n p) because the Hessian is rank deficient, and hence, the loss function in (3) might not be be strictly convex. However, in Lemma (ii) we show that B is unique. Key to our proof is the notion of coercivity and it adapts techniques in [48] to the case where the objective function is quadratic in the optimization variable.
3.1 Statement of Main result
Our first result theoretically characterizes the performance of B in (3) when Y is Gaussian. Instead, our second result provides such characterization for D when Y is non- non- Gaussian. At crude level, our results guarantee that when the number of samples n scales as d2 log p. our f1-regularized MLE correctly recovers the support of B" and is close to B" (measured in Frobenius and operator norms) with high probability. Here, d is the degree of the graph underlying B*.
Since we consider an & regularized log-determinant program for our ML estimator (3), our results might appear similar to that of [48]. However, as also pointed in Section 3.2, our main results, including the assumptions and sufficient conditions needed to derive them, are not subsumed by those in [48], or vice versa (see Remark 3 and Section 4 for more thorough discussion).
We begin with the few assumptions that are essential to prove our theoretical statements. Similar subset of assumptions in the context of é regularized least squares problem appeared in [63, 57, 39, 68], and in the context of & regularized inverse covariance estimation problem appeared in [48, 67]. We define the edge set E(B*) {(i.) j) Bi + O, for all A j}. Let E == (E(B*) U (1, 1)
(p. p)} be the augmented set including the diagonal elements. Let E be the complement of E.
[A1] Mutual incoherence condition. Let 1* be the Hessian of the log-determinant function in (3):
2 B log B)] B Ba
(4)
For I" in (4), there exists some a E (0, 1] such that, ||| E g (Tee)) -
$ 51aa
[A2] Hessian regularity condition. Let d be the maximum number of non zero entries among all the
rows in 8 (i.c., the degree of the underlying graph), O- = B B², and D2 = = Then,
(5)
4d loc D2
few comments are in order. [A1] Our novel mutual incoherence condition on B" regulates the influence of irrelevant variables (elements of Hessian restricted to E x E) relevant variables
5

---

(elements of Hessian restricted to E x E). The a-incoherence assumption of the above type is standard in literature, and [48] demonstrates its validity for several graphs, including chain and grid graphs, which we will explore in experimental section. Notice that the a-incoherence in [48] is imposed on O*. Instead, we require it on B [A2] This condition in parallel with bounding the maximum eigenvalue of @ condition for estimating sparse O* (see for e.g.. (0)).
Our problem set-up assumes that the injected flows X,, i E [p], are Gaussian. Given that the vector of node potentials Y depends X via the balance equation (see equation (I)), we have that Y is Gaussian. However, we work with sub-Gaussian distributions, a natural generalization to the Gaussian case, which encompasses many well known distributions that occur practice (for e.g., bounded random variables, gaussians and mixture of gaussians). We define this distributional assumption below.
Definition 1. Gaussian if there exists a constant o >> O such that for any I R, Blexp(IZ)] S exp (o2 /2).
random variable) A zero mean random variable Z is said to be sub-
Our first main result below provides sufficient conditions on the number of samples needed for ß in (3) to exactly recover the sparsity structure of B and to achieve sign consistency, defined as sign( B.y)) = Bij), for all (1,j) E E. We recall that VA = ||l - maxj=il....P Σi=1 Aigl
and define Vn" ---1 to be the covariance matrix of the node potential Y.
Theorem 1. (Support Recovery: (ab-Gaussian) Let X = (Xi...., .p) be the vector of injected flows. Suppose that for all i, Xi/ ((i( is sub- sub-Gaussian with parameter a and assumptions [A1-A2] hold. Let the regularization parameter A, =CovT(log 4p)/n, where Co is given below. Given n independent samples from Y, if the sample size cfd log p + log 4), the following hold with probability at least for some T > 2:
(a) B exactly recovers the sparsity structure of B*: that is. Bg = 0,
(b) B satisfies the element-wise too bound [ Bo S Cap r log p+ and
(c) B satisfies sign consistency if Biinl 2 202
rlopp4 n
Buin A min(,.EE(BB)) Bigh
where C1 192 192 (<()++)))))(())))))))))))))))))) (IX""""""""("xxxxxxX""" 1) max lug. 1, 20 1 10g 11.-1, 2a -d-
C2= = (64v2(1 40 (o²))(E)) 1n- Co (2/(44)--1) and k(.)) is the condition number.
The quantities (Vr--1, VD2, Vn", K: (E*), Tr(Ex)) capture the inherent complexity of the model and do not depend on the number of samples As long as the magnitude of the entries in r*=1 D2. and 8 scale as (1/d),, the model complexity parameters do not depend on (p, d). That is, as the size of the network grows with (p, d) the edge strengths decay with d. Suppose that the model complexity parameters are constants and that n ((d p)..). Then part (a) of Theorem guarantees that our ML estimator does not falsely include entries (or edges in the underlying graph) that are not in the support of B*. Part (b) establishes the element-wise foo norm consistency of B; that is, [ B* [| = O(v /log nn). Finally, part (c) establishes sign consistency of B, and hence, our estimator does not falsely exclude entries that are in the support of B'. Crucial is the requirement of |B = (V(log))/ p)/n). which puts a limit on the minimum (in absolute) value of the entries in B* This condition parallels the familiar beta-min condition in the LASSO literature (see [63, 59]).
We now present a corollary Theorem 1 that gives consistency rates of convergence for B in the Frobenius and operator norms. Let E(8*) = ((..j) B,, + 0, for all i * j} be the edge set of B*.
Corollary 1. Let s = |E(B)) be the cardinality of E(*). Under the same hypotheses in Theorem 1, with probability greater than 1 2, the estimator B satisfies
(T logp+4) and | - B²1l2 S C2 min (d, V log p + 4 n Proof sketch. Both the Frobenius and operator norm bounds follows by applying standard matrix norm inequalities to the foo consistency bound in part (b) of Theorem 1. Importantly, + p is the
B -BB-B'Ie== S
n

---

bound on maximum number of non zero entries in B", where s, by definition, is the total number of off-diagonal non-zeros in B*. Complete details are provided in Appendix A.3.
Thus far we have assumed that the nodal potentials Y; are sub-Gaussian random variables. We now explore another broad class of random variables with bounded kth moments, which are known to have tails that decay according to some power law [44]. An important example of power law distributions are Pareto distributions which finds applications in a wide variety of areas [43, 41J. Motivated by such important practical considerations, we state our next result for random variables with bounded moments. We begin with the following definition.
Definition 2. (Bounded moments) A random variable Z is said to have bounded 4h moment if there exists a constant M₁ E R. such that E [(Z)ak] S Ma.
sk]
Results below parallel Theorem 1 and Corollary 1 for random variables with bounded moments.
Theorem 2. (Support Recovery: Bounded Moments) Let X (X Xp) be the vector of injected flows such that for all i, the node potential Y:/ V has bounded moment as in Definition 2 and assumptions [A1-A2] hold. Let the regularization parameter X.. CoogTlog 4p)/n, with Co defined in Theorem I. Given n independent samples from Y, the sample size n. > CadPp=/k, k, then with probability greater than 1/p" 2, ffror some 2, the following hold: (a) B exactly recovers the sparsity structure of B (that is Bg= = 0); (b) the element-wise foo bound [| 1B S CaV pT/4
and (c) B satisfies sign consistency if B > 2C5
pTlk
The constants and their dependence on the model complexity parameters are given in Appendix A.3. Corollary Suppose the hypotheses Theorem 2 hold. Then with probability greater than 37 -2-
|| 1r S CsV (e+p)(pr/>) and [ - 111 S Cs mimmi, vs + p) V
pr/k where 8 = |((B))
Interpretations of Theorem and Corollary also hold for Theorem 2 and Corollary 2. However, in this setting, have different sample size n (dd2p) /k) and |Bin (2Vpp// /n), where A is given by Definition 2. In contrast, for sub-Gaussian case we have logarithmic dependence in (the number of vertices). Finally, albeit fundamentally different from GLASSO estimator, we were able to obtain consistency rates for B (3) that are similar to those in [48, 12].
Remark 3. (Comparison with the GLASSO estimator). For simplicity, suppose that Σx is diagonal. Then, it follows that B* 0 is the unique square root of O* = (B*)². Thus, a naive way to estimate B by taking the square root of the GLASSO estimate +. Let us call this estimator Bsn and note that Bsn inherits its optimal properties from é. We show that θ has sub-optimal estimation rate than B in (3) for estimating B" Let B" contains d non-zero elements in every row. Then the underlying graph of O² is two-hop network with degree d² Using sample complexity results from [48], follows that θ requires n (2(d log p) estimate B", Instead, our l Ez-regularized MLE requires
n (d log samples. This reduction is more pronounced for networks with a large degree d. O
3.2 Outline of Main Analysis
We provide an outline of our methods and main strategies to prove Theorem 1. We employ the primal- dual wilness technique-a a well-known method used derive to statistical guarantees for sparse convex estimators [63, 64, 34]. This technique involves constructing a primal-dual pair (B, Z) satisfying the surorsubgradient condition of the convex problem in (3), such that (the primal) B has the correct (signed) support. Suppose this construction succeeds, from the uniqueness result in Lemma 1, follows that B = B, and the dual is an optimal solution to the dual of (1). Thus, at the heart of analysis is in showing that the primal-dual construction succeeds with high- probabilityy Similar technique is also used to prove Theorem 2 (i.e., the non- Gaussiin case); see Appendix A.3.
While our proof methods are inspired from [48, 63], our analysis is more involved due to the presence of B2, as opposed to B, in the loss function of (3). Consequently, we require more nuanced assumption (as in [A2]) and dual fcasiblity condition than the ones in [48] (see below).
7

---

3.3 Primal-dual pair and supporting lemmas
We briefly introduce the primal-dual witness construction. Lemma 2, we provide sufficient conditions under which this construction succeeds.
We construct the primal-dual pair (B, Z) follows. The primal solution B is determined by solving
a
arg min B", Oge
(T(DBBBD) log det( + An 11.tt
Here (6) is restricted problem, in that, we impose Bg- O. Also, we have B > 0 and Bg- 0.
The dual Z E 0 B|]|i is chosen such that it satisfies the zero-subgradient condition of (6). This is obtained by setting 2 2A,, Zi, = [B- [D BS] for all (i,j) E E It can be verified that (B. 7) satisfies the zero-subgradient condition (see the statement of Lemma 1) of the original problem in (3). Thus, it remains to establish the strict dual feasibility condition; that Zzyl 1, for any (i.j) E
We introduce some notation. Let W & S 0 be measure of noise in the data, where S the sample covariance and O is the true covariance of Y. Let A - B B be measure of distortion between the primal solution B as defined equation (6) and the true matrix be estimated B*. We also need the the higher order terms (denoted by R (()) of the Taylor expansion of the gradient v log det B) centered around B* [10]:
V log det det(B) B + B" BB-'AB" B-1 B²1 B"- AB
R(A)
Lemma (Sufficient conditions for strict dual feasibility) Let the regularization parameter Xn and a be defined as in [A1]. Suppose the following holds
max <III[(D'A)) [1I[(("')++(("">>>)) | ||clllc__|[((A))))))_ [( 10
loc, ||(())
1100
An
(8)
24
Then the dual vector Z satisfies |l 1, and hence, B = B.
Proof sketch: The proof essentially involves expressing the sub- aub-gradient condition in Lemma 1 as vectorized form using R(A) (in (7)) and W. By manipulating the vectorized sub- aub-gradient condition,
we obtain an expression of ge that is function of the quantities in (8). We finish off the proof by repeated applications of triangle inequality of norms and invoking assumptions in Lemma (8).
The following results provides us with dimension and model complexity dependent bounds on the reminder term R(A) in (7) and the distortion A.
Lemma 3. (Control of reminder) Suppose that the element-wise loo -boud || 3v holds,
where Vg- ||||| Then || < 11
11
The proof. adapted from [48], is algebraic in nature and relies certain matrix expansions. The details are provided Appendix. In the following result, we provide a sufficient condition under which the element-wise -ooud on A in Lemma 3 holds.
Lemma
4. (Control of )
A) Let
App--1 (VDaVD- || [W >0 0..An.]
S
min| 30 6up- -1n--118h 18 10 adj. Then we have the element-wise foe bound || = |1 Ba 11
S
Proof sketch: By construction Bg. B = O. Hence, |A = ||A where A = B B We construct a continous vector valued function F AE + AE that has a unique fixed point. Invoking assumptions [A1]-AA]] we show that F(-) is a contractive map the Exe ball defined as B, (A ||A|] S r) with r defined in the statement of the lemma. Specifically, we show that F(B,)) C B,, Finally, we finish off the proof by an application of Brower's 's fixed point theorem [29] to show that the unique fixed point is inside B,,, Consequently, ||o S
Finally, the result in Theorem follows by putting these lemmas together for an appropriate choice of An and the sample size requirement, and there upon, invoking some known concentration inequalities. Refer Appendix A.3 for complete details.
8

---

chain graph with d=2
20
2
24
17
3
25
22
15
5
14
6
13
9
28 27
29
29
30
31
52
33
(b) grid graph with d-4
(c) IEEE 33 bus power network
(4) sparsity of B* (c)
(e) sparsily squared in
Figure 2: Graphs used in experiments. (a) Chain graph with maximum degree = 2. (b) Grid graph d 4. (c) IEEE 33 bus (node) distribution network with additional loops (shown in dashed lines). (d) Sparsity of B* associated with the TEFE 33 bus network. (d) Sparsity of (B*)² Notice that ( (B*)² is denser relative to B". Consequently, CLASSO+HR needs samples than & 2-MLE recover the support (see plots in Fig. 3).
Experiments
We validate the support recovery performance of our & fi-regularized MLE on synthetic and a bench- mark power distribution network (see Fig. 2). We choose An proportional to /log p/n. Our results are averaged over 100 trials of n independent samples of Y. We compare f1-regularized MLE performance with (i) the square-root estimator (hereafter, GLASSO+SR) that identifies the support of
B by determining (i.j) for which + * 0; and (ii) the GLASSO+2HR (Hop Refinement) estimator [20] that identifies the support of B" by determining (i, for which O.,- S -T for r 1 02. Here θ is the GLASSO estimate of the inverse covariance matrix of Y [23]. These estimators are described in detail in Introduction. To have fair comparison with the GLASSO based estimators, we set Σx (X is the injected vector) to be diagonal. However, as discussed earlier. our & regularized ML estimator works for any Σx > We consider p to be as large as 64 nodes, Computational examples involving large data matrices for B" having lower triangular matrix form has been reported in [28].
(i) Synthetic data: We consider two undirected graphs for B" the chain graph and the grid graph for p = {32, 64] nodes. We set B edge set of the chain or grid graph. We then adjust the diagonal elements of 1 ensure 8 >
for (i, E and B", = for (i,j) E E where can be the
(ii) Power network: We set to be the Laplacian of the IEEE 33 bus power distribution network [69]. For this data, note that B" is non-invertible because of one zero eigenvalue. We obtain the reduced B" by deleting the first row and column of B" We also slightly modify the network by adding three loops of cycle length three, two of cycle length four, and one loop of cycle length five (see Fig 2). We made these modifications to highlight that fMMLEE imposes no connectivity assumptions the graph underlying B" except sparsity. In contrast, GLASSO+2HR estimator [20] restricts the graph underlying B" from having cycles of length three (i.e., triangle-free).
In Fig. 3. we show empirical support recovery probabilities for all three estimators function of the number of samples n. Both on synthetic and power network data, MMME achieved superior rates than the other competing estimators. In fact, f-MEE exactly recovers the support of 3* when the number of samples the order of d² log which in excellent agreement with the proposed theory. Instead, for similar performance, GLASSO+SR needed dt log samples (see Remark 3).
5 Discussions and Future Work
High dimensional networks obeying conservation laws of the form X B are often used model and study interactions among different conserved quantities in various engineering and scientific disciplines. For such systems, with unknown structure of the network, or equivalently the sparsity pattern of B", we estimate the the sparsity structure of B" using an L fj-regularized ML estimator. Our estimator relies on samples of the node potentials Y. with some knowledge of the statisties of the node injections X. We showed that this estimator is the unique optimal solution to variant of the convex log-determinant program. Using novel mutual incoherence conditions, we have provided (theoretical) sparsity and support recovery consistency for our estimator. Finally, using several numerical results we not only validated our theory but also showed that our errrgularizee estimator outperforms methods that employ GLASSO based estimators.

---

Probabiiity of support menner
Probabality of supparr recovery
1.0
Probsiin hallitylyyyyyy of support recovesy
MGE
1246 poverr dicrictne carverk
0.
0.0
0.6
9.4
CLASSOHS2 pm
4tn
BC0
1000
400 620
100n
number of samples (t)
number of samples
number of samples
Figure 3: Empirical probability of success of various estimators versus the raw sample size for (left) chain graph, (middle) grid graph, and (right) IEEE 33 bus network. For chain and grid graph, compare & regularized MLE performance with GLASSO+SR for p E (32, 64). Instead, for IEEE bus network, we compare & regularized MLE GLASSO+SR and GLASSO+2HR.
In our setup, we neither require actual injected flows (X), nor B to be a Laplacian matrix, nor n > p, thereby allowing our learning problem to be general enough to be applicable a variety of domains ranging from electrical networks to social networks. Consequently, our framework and theoretical results admits many future extensions and refinements. For instance, verifying the assumptions [A1-A2] in practice is fruitful future direction. It is worth noting that, in order to the proposed algorithm/cssimato, one need not verify the assumptions. Notice that from Lemma the loss funetion/objective is convex and admits unique solution if the regularization constant An > 0 and is positive definite, therefore the unknown structure of the network can be recovered by finding the unique minima. However, in order theoretically guarantee the properties of the estimator mentioned Theorem and Theorem 2, assumptions [A [A1-A2] are needed. possible extension to the current problem is recast the objective function in (2) as the minimization of the Bregman divergence for more general loss functions. Another promising direction is to generalize (2) include non-invertible network matrix B*. We leave this our future work.
References
[1] Rajasekhar Anguluri, Gautam Dasarathy, Oliver Kosut, and Lalitha Sankar. Grid topology identification with hidden nodes via structured norm minimization. IEEE Control Systems Letters, 6: 6:124-1249 2022.
[2] Martin Azizyan, Akshay Krishnamurthy, and Aarti Singh. Extreme compressive sampling for covariance estimation. IEEE Transactions Information Theory, 64(12):7613-7635 2018.
[3] Onureena Banerjee, Laurent El Ghaoui, and Alexandre Asppremont Model selection through sparse maximum likelihood estimation for multivariate gaussian binary data. The Journal of Machine Learning Research, 9:485-516, 2008
[4] Ravindra B Bapat. Graphs and matrices, volume 27. Springer, 2010.
[5] Heinz H Bauschke, Patrick L. Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
[6] Mikhail Belkin and Partha Niyogi. Towards theoretical foundation for laplacian- based manifold methods. In International Conference on Computational Learning Theory, pages 486-500. Springer, 2005.
[7] Tanya N Beran and Claudio Violato. Structural equation modeling in medical research: primer. BMC research notes, 3(1):1-10, 2010.
[8] Rajendra Bhatia. Positive definite matrices. In Positive Definite Matrices. Princeton university press, 2009.
[9] José M Bioucas-Dias, Deborah Cohen, and Yonina C Eldar. Covalsa: Covariance estimation from compressive measurements using alternating minimization. In 2014 22nd European Signal Processing Conference (EUSIPCO), pages 999-1003, IEEE, 2014.
10

---

[10] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[11] Tony Cai and Anru Zhang. Rop: Matrix recovery via rank-one projections. The Annals of Statistics, 43(1):102- 138, 2015.
[12] Tony Cai, Weidong Liu, and Xi Luo. A constrained &1- minimization approach to sparse precision matrix estimation. Journal of the American Statistical Association, 106(494):594-607, 2011.
[13] G. Cavraro, V. Kekatos, L. Zhang, and G. B. Giannakis. Chapter learning power grid topologies. In Advanced Data Analytics for Power Systems, pages 3-27. Cambridge, 2021.
[14] Yuxin Chen, Yuejie Chi, and Andrea J Goldsmith. Exact and stable covariance estimation from quadratic sampling via convex programming. IEEE Transactions on Information T'heory 61(7): 4034 4059, 2015.
[15] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[16] Mustafa Emre Civelek. Essentials of structural equation modeling. Essentials of Structural Equation Modeling (2018), 2018.
[17] Irene Córdoba, Concha Bielza, Pedro Larrañaga, and Gherardo Varando. Sparse cholesky covariance parametrization for recovering latent structure in ordered data. IEEE Access, 154614-154624, 2020.
[18] Gautam Dasarathy, Parikshit Shah, Badri Narayan Bhaskar, and Robert D Nowak. Sketching sparse matrices, covariances, and graphs via tensor products. IEEE Transactions on Information Theory, 61(3):1373-138 2015.
[19] Gautam Dasarathy, Parikshit Shah, and Richard G Baraniuk. Sketched covariance testing: A cnapresssion-taatittiii tradeoff. 2017 IEEE International Symposium on Information Theory (ISIT), pages 2268-2272. IEEE, 2017.
[20] Deepjyoti Deka, Saurav Talukdar, Michael Chertkov, and Murti V. Salapaka. Graphical models in meshed distribution grids: Topology estimation, change detection & limitations. IEEE Transactions on Smart Grid, 1(55):229-444 4310, 2020.
[21] Florian Dorfler and Francesco Bullo. Kron reduction graphs with applications to electrical networks. IEEE Transactions Circuits and Systems I: Regular Papers, 60(1):150-163,, 2012.
[22] Sacha Epskamp. Lourens Waldorp. René Möttus, and Denny Borsboom. The gaussian graphical model in cross-sectional and time-series data. Multivariate behavioral research, 53 (4):453-480, 2018.
[23] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics. 9(3):432-444) 2008.
[24] Robert Grone, Russell Merris, and VS_ Sunder. The laplacian spectrum of graph. SIAM Journal on matrix analysis and applications, 1 11(2)218-238, 1990.
[25] Patric Hagmann, Leila Cammoun, Xavier Gigandet, Reto Meuli, Christopher J Honey, Van J Wedeen, and Olaf Sporns. Mapping the structural core of human cerebral cortex. PLoS biology, 657):e159, 2008.
[26] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[27] Jianhua Huang, Naiping Liu, Mohsen Pourahmadi, and Linxu Liu. Covariance matrix selection and estimation via penalised normal likelihood. Biometrika, 93(1):85-98, 2006.
[28] Vladisav Jelisavcic, Ivan Stojkovic, Veljko Milutinovic, and Zoran Obradovic. Fast learning of scale-free networks based on cholesky factorization. International Journal of Intelligent Systems, 3322) 2018.

---

[29] R Bruce Kellogg, Tien- Yien Li, and James Yorke. A constructive proof of the brouwer fixed- point theorem and computational results. SIAM Journal on Numerical Analysis, 13(():473-48, 1976.
[30] Clifford Lam and Jianqing Fan. Sparsistency and rates of convergence large covariance matrix estimation. Annals of statistics, 37(6B))4254, 2009.
[31] Alan J Laub. Matrix analysis for scientists and engineers, volume 91. Siam, 2005.
[32] Daniel LeJeune, Gautam Dasarathy, and Richard Baraniuk. Thresholding graph bandits with GrAPI.. In International Conference on Artificial Intelligence and Statistics, pages 2476-2485.
PMLR, 2020.
[33] Tongxin Li, Lucien Werner, and Steven Low. Learning graphs from linear measurements: Fun- damental trade-off's and applications. IEEE Transactions Signal and Information Processing over Networks, 6: 6:163-178, 2020.
[34] Po-Ling Loh and Martin J Wainwright. Support recovery without incoherence: A case for nonconvex regularization. The Annals of Statistics, 45(6):2455-2482, 2017.
[35] Marloes Maathuis, Mathias Drton, Steffen Lauritzen, and Martin Wainwright. Handbook of graphical models. CRC Press, 2018.
[36] Antonio G Marques, Santiago Segarra, Geert Leus, and Alejandro Ribeiro. Stationary graph processes and spectral estimation. IEEE Transactions Signal Processing, 65(22).5911-5926. 2017.
[37] Gonzalo Mateos, Santiago Segarra, Antonio G Marques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Processing Magazine, 36(3):16-433 2019.
[38] AR McIntosh and Francisco Gonzalez-Lima Structural equation modeling and its application network analysis in functional brain imaging. Human brain mapping, 2(1-2):2-22, 1994.
[39] Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the lasso. The annals of statistics, 34(3):1436-14 1462, 2006.
[40] Mehran Mesbahi and Magnus Egerstedt. Graph theoretic methods in multiagent networks. In Graph Theoretic Methods in Multiagent Networks. Princeton University Press, 2010.
[41] Staša Milojević. Power law distributions in information science: Making the case for logarithmic binning. Journal of the American Society for Information Science and Technology, 61(2) 2417-2425, 2010.
[42] Søren Wengel Mogensen. Equality constraints in linear hawkes processes. In First Conference on Causal Learning and Reasoning, 2021.
[43] Mark EJ Newman, Power laws, pareto distributions and zipf's law. Contemporary physics, 46 (5):323-351, 2005.
[44] Valentin Petrov. Limit theorems of probability theory; sequences of independent random variables. Technical report, 1995.
[45] Arnan Pongrattanakul. Puttichai Lertkultanon, and Jitkomut Songsiri. Sparse system identifica- tion for discovering brain connectivity from fmni time series. In The SICE Annual Conference 2013, pages 949-954, IEEE, 2013.
[46] Constantine Pozrikidis. introduction to grids, graphs, and networks. Oxford University Press, 2014.
[47] Anupon Pruttiakaravanich and Jitkomut Songsiri. Convex formulation for regularized estimation of structural equation models. Signal Processing, 166:10 2020.
12

---

[48] Pradeep Ravikumar, Martin J Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensionn covariance estimation by minimizing & -penallize log-determinant divergence. Electronic Journal of Statistics, 5:935-980, 2011.
[49]
Adam J Rothman, Peter J Bickel, Elizaveta Levina, and Ji Zhu. Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2:494-515, 2008.
[50] Rasoul Shafipour and Gonzalo Mateos. Online network topology inference with partial connec- tivity information. In 2019 IEEE 8th International Workshop Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 226-230. IEEE, 2019.
[51] Rasoul Shafipour, Santiago Segarra, Antonio G Marques, and Gonzalo Mateos. Network topology inference from non-stationary graph signals. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5870-5874. IEEE, 2017.
[52] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22)8))888 (188)88880058 -05, 2000.
[53] Saurav Talukdar, Mangal Prakash, Donatello Materassi, and Murti V Salapaka. Reconstruction of networks of cyclostationary processes. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 783-788. IEEE, 2015.
[54] Saurav Talukdar, Deepiyoti Deka, Harish Doddi, Donatello Materassi, Michael Chertkov, and Murti Salapaka. Physics informed topology learning in networks of linear dynamical systems. Automatica, 112:108705, 2020.
[55] Oleg N Temkin, Andrew V Zeigarnik, and Danail Bonchev. Chemical reaction networks: graph-theoretical approach. CRC Press, 2020.
(56) Parth K Thaker, Nikhil Rao, Mohit Malu, and Gautam Dasarathy. Pure exploration in multi- armed bandits with graph side information. arXiv preprint arXiv:2 0/ 152, 2021.
[57] Joel Tropp. Just relax: Convex programming methods for identifying sparse signals noise. IEEE transactions information theory, 1203):1030-105,, 2006.
[58] Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. International Conference on Machine Learning, pages 46-54. PMLR, 2014.
[59] Sara A Van de Geer. High-dimensional generalized linear models and the lasso. The Annals of Statistics, 14-644, 2008.
[60] Arjan van der Schaft. Modeling of physical network systems. Systems & Control Letters, 101: 21-27, 2017.
[61] Giuseppe Vinci, Gautam Dasarathy, and Genevera I Allen. Graph quilting: graphical model selection from partially observed covariances. arXiv preprint arXiv: 2019.
[62] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing. 10 17(4):395 2007.
[63] Martin Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using f-coonttrained quadratic programming (lasso). IEEE transactions on information theory, 55(5): 2183-2202, 2009.
[64] Martin J Wainwright. High ditidiiiinsiooall statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[65] Thakshila Wimalajeewa, Yonina C Eldar, and Pramod Varshney. Recovery of sparse matrices via matrix sketching. arXiv preprint arXiv:/311.2448, 2013.
[66] Ming Yuan and Yi Lin. Model selection and estimation in the gaussian graphical model. Biometrika, 94(1):19-35, 2007.
[67] Teng Zhang and Hui Zou. Sparse precision matrix estimation via lasso penalized d-trace loss. Biometrika, 101(1):003-120, 2014.
13

---

[68] Peng Zhao and Bin Yu. On model selection consistency of lasso. The Journal of Machine Learning Research, 7:2541-2563, 2006.
[69] Ray Daniel Zimmerman, Carlos Edmundo Murillo-Sánchez, and Robert John Thomas. Mat- power: Steady-state operations, planning, and analysis tools for power systems research and education. IEEE Transactions on power systems, 26(1):12-19, 2010.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The limitations of this work will
be discussed in detail in the appendix
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code and it's related details will be made available in the appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] These will be mentioned in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "r6te4jzzvmx", "reviewer": "Reviewer_8D2X", "summary": "This paper proposes a $\\ell^1$-regularized log-determinant program for estimating the graph structure encoded in a matrix $B$ from a conservation law $BX=Y$, where the node potentials $Y$ are measured and the injected signals $X$ are Gaussian.\nGiven the sample covariance of $Y$, the objective function is recast into a $\\ell^1$-regularized log-determinant program on $B$. The new objective function is shown to be convex with a unique minimizer $\\hat B$.\nFurthermore, under relatively standard assumptions, the solution $\\hat B$ is shown to match several properties of the actual graph matrix.\nSome experiments are presented to show the practical benefits of the proposed optimization problem", "questions": "I find Figure 1 difficult to understand. Why do (c) and (d) have a missing edge? In what way are the spurious edges removed in (d)? I believe the presentation would improve significantly with a more detailed discussion here on the related work and approaches.\n\nL65-71: This example is not clear. The equation $B^*=(\\sum_l h_l A^L)^{-1}$ seems odd as $A^L$ does not depend on $l$. Also what does it mean that $L=3$ and $B^*=(I-\\alpha A)^{-1}$ are reasonable choices? $B^*$ is a function of $L$ and this function does not coincide with $(I-\\alpha A)^{-1}$ when $L=3$. Finally, I believe that in most cases the matrix $B^*=(I-\\alpha A)^{-1}$ is almost full, so it does not seem like a good example of application of your approach\n\nThe experiments only consider very small graphs (up to 64 nodes) but this is claimed to be a method for high-dimensional networks. I find this a little odd, please explain.\n\nOnly a very small set of (three) graphs is considered in the experiments. The paper would highly benefit from a more extensive experimental section where a larger number of graphs with different structural properties is considered. \n\nIn the experiments it should be highlighted whether or not the assumptions of Thm 1 are satisfied.\n\nIn the synthetic experiments $B$ is chosen as the adjacency matrix of the graph, and it is then perturbed to become pd. More details on the precise perturbation made are needed here.\n\nL361: The empirical support recovery probability should be defined more precisely\n\nFigure 3 should report vertical lines to highlight the value of $d^2\\log p$ and $d^4\\log p$. \n\nThe IEEE 33 network is not regular, so what is $d$?\n\nThe experiments only verify the sparsity structure. How about sign consistency and norm distance $\\|\\hat B-B^*\\|$? \n\nIt is not clear to me whether your derivations and approach work also for weighted (non-binary) graphs.\n\nL121: $T_1,T_2$ are subsets of $[p]$ not $[p]\\times [p]$.\nL125: the sentence is not clear\nL:135: $\\Theta^*$ requires some inverse\n", "limitations": "It seems like one limitation of the approach is that it works for relatively small graphs only. This should be clarified in the paper.\nAlso, it is not clear whether the assumptions of Theorem 1 and its corollaries are verified in practice and how stringent they are. This should be discussed in more details and verified on the graphs the method is tested on.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper well written and the contribution is well presented. The whole theoretical machinery quite tightly follows previous work on high-dimensional covariance estimation in [39], the main difference being the fact that the objective function is quadratic in the variable $B$. While this certainly complicates the analysis with respect to [39], the novelty with respect to [39] from the theoretical point of view may be limited.\n\nAt the same time, when compared with previous GLASSO technique(s) for recovering the graph structure based on the same $\\ell^1$-regularized log-determinant program (e.g. [54,16,13]), the proposed approach provides interesting novelties. In particular, while GLASSO allows to reconstruct the graph pattern only for paths of length two, and thus requires $O(d^4\\log p)$ samples to reconstruct the graph, the proposed estimator recovers the graph with only $O(d^2\\log p)$ samples. \n\nThe statements of the main theorems/results seem correct and reasonable, although I did not check the proofs in details.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MOBRuyorT_1", "reviewer": "Reviewer_tryY", "summary": "The paper deals with the estimation of graphical models under the constraints of conservation laws of network flow. The paper focuses on the problem of estimation of Laplacian matrices using the log-likelihood of multivariate Gaussian distributions. The paper considers solving an optimization problem involving penalized log-likelihood of Gaussian distribution extending the graphical lasso methods. The paper also provides theoretical results on the consistency of the estimated Laplacian matrices as well as support recovery under sparsity conditions. The paper provides both theoretical conditions on the error bounds on the estimates as well as a simulation study demonstrating the effectiveness of the penalized estimation.", "questions": "1. Is it possible to address the situation of unknown covariance matrices (which is pretty natural in real data contexts) in more detail?\n2. What are the computational costs of these methods and up to what size of networks can be handled by this method?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n(1) Formulation of a convex problem using penalized log-likelihood for estimation of Laplacian matrices under the conservation laws of the network flow.\n(2) Theoretical results on the error bounds on estimated Laplacian using $\\ell_\\infty$, Frobenius, and operator norms.\n(3) Theoretical results on the support recovery of Laplacian matrices under the condition of sparsity in the Laplacian population matrix.\n\nWeakness:\n(1) The situation of the unknown covariance matrix in Remark 1 requires more explanations. Rigorous statements on how the problem change in this case, and how the estimation of $B^*$ can still be possible should be mentioned in more detail.\n(1) The innovations in the proof techniques for proving Theorems 1 and 2 have not been properly explained. The assumptions of [A1]-[A3], as well as the primal-dual witness construction, are standard in the literature, so a bit more explanation on the difficulty and innovations in section 3.3 would be appealing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GLOO_QUmDp3", "reviewer": "Reviewer_HeKM", "summary": "This submission studies how to learn the structure of large network that obeys conservation law, a l1-regularized formulation is introduced, and the problem is convex. ", "questions": "1.what is the exact novelty and challenge compared with GLASSO? \n\nIt seems to the reviewer, and also confirmed by the authors that the formulation in (2) is the same as GLASSO, the only difference is B instead of Theta is being estimated. However, this makes the problem convex, and henceforth it seems to be simpler than GLASSO, Given that the problem formulation is simpler and the solving is easier, the novelty and challenge need to be further discussed.\n\n2. the experiments only show synthetic and real power grids data, are there any other application domains? if so, should be discussed and more experimental results in other applications should be include to show the generality of the proposed framework. If not, then the applicability of the framework is quite limited.", "limitations": "lack of discussion about the novelty\napplicability of the proposed framework seems to be limited to power grids.\nsocietal limitation not discussed", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "weakness:\n\n1.  the motivation is not well-established.\n2.the novelty compared with previous works is not sufficient\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9sEozKBYyv", "reviewer": "Reviewer_fKZ9", "summary": "The paper developed a $\\ell_1$-regularized MLE of the sparsity structure of $B^∗$ in the conservation laws $X=B^* Y$ observed in many networked systems. The authors assumed that the covariance matrix $\\Sigma_X$ of the node injections $X$ is known, and the proposed MLE can recover the topology of the structure of the graph from $B^*$ with high probability. With appropriate choices of the regularization coefficient $\\lambda_n$ and the sample size $n\\ll p$, the proposed estimator is theoretically sound and proved to be effective on synthetic datasets and a real power distribution network. The authors provided detailed proofs to reach the conclusions on the support recovery performance. Also, they compared the proposed MLE against the baselines GLASSOR+2HR and GLASSOR+SR, and the proposed MLE outperformed.\n", "questions": "Minors:\n\n1. Last sentence in the caption of Fig1: ... there are no **spuruious** edges in it -> ... there are no **spurious** edges in it.\n2. L125: $\\lVert A \\lVert_{\\infty}$ has two more vertical lines?\n4. L187: ...might not be be strictly convex. -> ...might not be strictly convex.\n5. An explicit definition of the support of $B^*$ will be better.", "limitations": "YES.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and developed a $\\ell_1$-regularized MLE for the support of $B^*$ from limited potential samples. \n2. The proposed estimator is proved to be convex in B, therefore, it has a unique solution regardless of the size of problem. \n3. It is consistent to the true $B^*$ in terms of elementwise maximum, Frobenius and operator norms. \n4. Theorems of the support recovery are given for Gaussian, sub-Gaussian node potentials and the ones with bounded moments. \n4. Relatively, it requires less number of potentials samples than the baseline GLASSOR+SR.\n\nWeaknesses:\n\nThe developed estimator claimed to be able to avoid the assumptions that are imposed on prior works, such as triangle-freeness of $\\mathcal G$, no correlation between the node injections, and the invertibility of the empirical covariance matrix. However, it relies on three necessary assumptions [A1,A2 and A3]. How to verify that these conditions hold in practice? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept