In this paper, we consider the problem of learning a sparse graph from the Laplacian constrained Gaussian graphical model. This problem can be formulated as a penalized maximum likelihood estimation of the precision matrix under Laplacian structural constraints. Like in the classical graphical lasso problem, recent works made use of the $\ell_1$-norm with the goal of promoting sparsity in the Laplacian constrained precision matrix estimation. However, through empirical evidence, we observe that the $\ell_1$-norm is not effective in imposing a sparse solution in this problem. From a theoretical perspective, we prove that a large regularization parameter will surprisingly lead to a solution representing a fully connected graph instead of a sparse graph. To address this issue, we propose a nonconvex penalized maximum likelihood estimation method, and establish the order of the statistical error. Numerical experiments involving synthetic and real-world data sets demonstrate the effectiveness of the proposed method.

In this paper, we consider the problem of learning a sparse graph from the Laplacian constrained Gaussian graphical model. This problem can be formulated as a penalized maximum likelihood estimation of the precision matrix under Laplacian structural constraints. Like in the classical graphical lasso problem, recent works made use of the \ell_1 -norm with the goal of promoting sparsity in the Laplacian constrained precision matrix estimation. However, through empirical evidence, we observe that the \ell_1 -norm is not effective in imposing a sparse solution in this problem. From a theoretical perspective, we prove that a large regularization parameter will surprisingly lead to a solution representing a fully connected graph instead of a sparse graph.

Weaknesses: Theorem 3.1 and its empirical results in Figure 1 bring the following concern: The fully connected graph obtained by lambda larger than certain value (e.g., lambda*), which is related to the input data covariance S. So, the scaling of X impacts lambda*. How does the lambda from 0 to lambda* theoretically impact the sparsity of the optimal graph? The proposed algorithm for solving nonconvex optimization is the combination of linearization of nonconvex regularization and projected gradient descent method. The convergence results are shown in Theorem 3.8. This can guarantee the convergence, but how many iterations are required for both inner and outer iterations in Algorithm 1 and what is the computational complexity?

All reviewers but one agree that the contribution of the paper is novel, interesting and that the experiments are compelling. Bit all reviewers also agree that the paper lacks either an intuitive or even formal explanation of the surprizing properties of the L1 norm regularization in this setting. The proofs provided show that the stated facts are correct, but this is not explained in the text. The authors are strongly encouraged to include an explanation in the final version of the manuscript.

In this paper, we consider the problem of learning a sparse graph from the Laplacian constrained Gaussian graphical model. This problem can be formulated as a penalized maximum likelihood estimation of the precision matrix under Laplacian structural constraints. Like in the classical graphical lasso problem, recent works made use of the \ell_1 -norm with the goal of promoting sparsity in the Laplacian constrained precision matrix estimation. However, through empirical evidence, we observe that the \ell_1 -norm is not effective in imposing a sparse solution in this problem. From a theoretical perspective, we prove that a large regularization parameter will surprisingly lead to a solution representing a fully connected graph instead of a sparse graph.