Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: weakness:

1.  the motivation is not well-established.
2.the novelty compared with previous works is not sufficient

questions: 1.what is the exact novelty and challenge compared with GLASSO? 

It 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.

2. 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
applicability of the proposed framework seems to be limited to power grids.
societal limitation not discussed
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength:
(1) Formulation of a convex problem using penalized log-likelihood for estimation of Laplacian matrices under the conservation laws of the network flow.
(2) Theoretical results on the error bounds on estimated Laplacian using $\ell_\infty$, Frobenius, and operator norms.
(3) Theoretical results on the support recovery of Laplacian matrices under the condition of sparsity in the Laplacian population matrix.

Weakness:
(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.
(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.
questions: 1. Is it possible to address the situation of unknown covariance matrices (which is pretty natural in real data contexts) in more detail?
2. What are the computational costs of these methods and up to what size of networks can be handled by this method?
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: Strengths:

1. The paper is well-written and developed a $\ell_1$-regularized MLE for the support of $B^*$ from limited potential samples. 
2. The proposed estimator is proved to be convex in B, therefore, it has a unique solution regardless of the size of problem. 
3. It is consistent to the true $B^*$ in terms of elementwise maximum, Frobenius and operator norms. 
4. Theorems of the support recovery are given for Gaussian, sub-Gaussian node potentials and the ones with bounded moments. 
4. Relatively, it requires less number of potentials samples than the baseline GLASSOR+SR.

Weaknesses:

The 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? 
questions: Minors:

1. Last sentence in the caption of Fig1: ... there are no **spuruious** edges in it -> ... there are no **spurious** edges in it.
2. L125: $\lVert A \lVert_{\infty}$ has two more vertical lines?
4. L187: ...might not be be strictly convex. -> ...might not be strictly convex.
5. An explicit definition of the support of $B^*$ will be better.
limitations: YES.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
Given 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$.
Furthermore, under relatively standard assumptions, the solution $\hat B$ is shown to match several properties of the actual graph matrix.
Some experiments are presented to show the practical benefits of the proposed optimization problem
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.

At 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. 

The statements of the main theorems/results seem correct and reasonable, although I did not check the proofs in details.

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.

L65-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

The 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.

Only 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. 

In the experiments it should be highlighted whether or not the assumptions of Thm 1 are satisfied.

In 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.

L361: The empirical support recovery probability should be defined more precisely

Figure 3 should report vertical lines to highlight the value of $d^2\log p$ and $d^4\log p$. 

The IEEE 33 network is not regular, so what is $d$?

The experiments only verify the sparsity structure. How about sign consistency and norm distance $\|\hat B-B^*\|$? 

It is not clear to me whether your derivations and approach work also for weighted (non-binary) graphs.

L121: $T_1,T_2$ are subsets of $[p]$ not $[p]\times [p]$.
L125: the sentence is not clear
L:135: $\Theta^*$ requires some inverse

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.
Also, 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.
review_title: null

Meta-review: metareview: The reviewers and the area chair judged the paper as technically sound and found that the problem treated is an interesting variant in the spirit of (but different from) the well-known group-LASSO. The range of applicability of the approach was considered promising. While the narrative of the proof leading to a convex problem was judged standard and by itself perhaps less interesting, overall the contribution was judged as valuable to the community and we recommend acceptance of the paper. 
confidence: Less certain
Decision: Accept