# Does the ℓ1-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models?

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2020.

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

- [Adaptive Estimation of Graphical Models under Total Positivity](https://mlsanity.com/paper/2210.15471/) (2022)
- [Time-Varying Graph Learning for Data with Heavy-Tailed Distribution](https://mlsanity.com/paper/2501.00606/) (2024)
- [Distributed Graph Learning with Smooth Data Priors](https://mlsanity.com/paper/2112.05887/) (2021)
- [Learning Networks from Wide-Sense Stationary Stochastic Processes](https://mlsanity.com/paper/2412.03768/) (2024)

## Abstract (arXiv)

We consider the problem of learning a sparse graph under the Laplacian constrained Gaussian graphical models. This problem can be formulated as a penalized maximum likelihood estimation of the Laplacian constrained precision matrix. Like in the classical graphical lasso problem, recent works made use of the ℓ1-norm regularization with the goal of promoting sparsity in Laplacian constrained precision matrix estimation. However, we find that the widely used ℓ1-norm is not effective in imposing a sparse solution in this problem. Through empirical evidence, we observe that the number of nonzero graph weights grows with the increase of the regularization parameter. From a theoretical perspective, we prove that a large regularization parameter will surprisingly lead to a complete graph, i.e., every pair of vertices is connected by an edge. To address this issue, we introduce the nonconvex sparsity penalty, and propose a new estimator by solving a sequence of weighted ℓ1-norm penalized sub-problems. We establish the non-asymptotic optimization performance guarantees on both optimization error and statistical error, and prove that the proposed estimator can recover the edges correctly with a high probability. To solve each sub-problem, we develop a projected gradient descent algorithm which enjoys a linear convergence rate. Finally, an extension to learn disconnected graphs is proposed by imposing additional rank constraint. We propose a numerical algorithm based on based on the alternating direction method of multipliers, and establish its theoretical sequence convergence. Numerical experiments involving synthetic and real-world data sets demonstrate the effectiveness of the proposed method.