# Efficient Graph Laplacian Estimation by Proximal Newton

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 70 references that are in the map.
- First posted on arXiv 13 Feb 2023.

## Builds on (most cited first, 11 of 11)

- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Structured Graph Learning Via Laplacian Spectral Constraints](https://mlsanity.com/paper/1909.11594/) (2019)
- [Learning Undirected Graphs in Financial Markets](https://mlsanity.com/paper/2005.09958/) (2020)
- [Detection of false data injection attacks in smart grids based on graph signal processing](https://mlsanity.com/paper/1810.04894/) (2018)
- [Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation](https://mlsanity.com/paper/1306.3212/) (2013)
- [Bayesian Estimation of Graph Signals](https://mlsanity.com/paper/2103.15520/) (2021)
- [Sparse Graph Learning Under Laplacian-Related Constraints](https://mlsanity.com/paper/2111.08161/) (2021)
- [A multilevel framework for sparse optimization with application to inverse covariance estimation and logistic regression](https://mlsanity.com/paper/1607.00315/) (2016)
- [Effective Learning of a GMRF Mixture Model](https://mlsanity.com/paper/2005.09030/) (2020)
- [Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields](https://mlsanity.com/paper/2109.08666/) (2021)
- [State Estimation in Unobservable Power Systems via Graph Signal Processing Tools](https://mlsanity.com/paper/2106.02254/) (2021)

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

- [Learning Multi-Attribute Differential Graphs with Non-Convex Penalties](https://mlsanity.com/paper/2505.09748/) (2025)
- [Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning](https://mlsanity.com/paper/2506.10628/) (2025)
- [Fast Graph Laplacian Estimation using Effective Resistance](https://mlsanity.com/paper/2609.23668/) (2026)
- [Graph Learning with Spectral Connectivity Priors for Scarce Data](https://mlsanity.com/paper/2609.27278/) (2026)

## Abstract (arXiv)

The Laplacian-constrained Gaussian Markov Random Field (LGMRF) is a common multivariate statistical model for learning a weighted sparse dependency graph from given data. This graph learning problem can be formulated as a maximum likelihood estimation (MLE) of the precision matrix, subject to Laplacian structural constraints, with a sparsity-inducing penalty term. This paper aims to solve this learning problem accurately and efficiently. First, since the commonly used ℓ1-norm penalty is inappropriate in this setting and may lead to a complete graph, we employ the nonconvex minimax concave penalty (MCP), which promotes sparse solutions with lower estimation bias. Second, as opposed to existing first-order methods for this problem, we develop a second-order proximal Newton approach to obtain an efficient solver, utilizing several algorithmic features, such as using Conjugate Gradients, preconditioning, and splitting to active/free sets. Numerical experiments demonstrate the advantages of the proposed method in terms of both computational complexity and graph learning accuracy compared to existing methods.