# Sparse Graph Learning Under Laplacian-Related Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 16 Nov 2021.

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

- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [Robust Graph Learning from Noisy Data](https://mlsanity.com/paper/1812.06673/) (2018)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Node-Based Learning of Multiple Gaussian Graphical Models](https://mlsanity.com/paper/1303.5145/) (2013)
- [Support recovery without incoherence: A case for nonconvex regularization](https://mlsanity.com/paper/1412.5632/) (2014)
- [Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fields](https://mlsanity.com/paper/1404.6640/) (2014)
- [Structured Graph Learning for Clustering and Semi-supervised Classification](https://mlsanity.com/paper/2008.13429/) (2020)
- [Maximum likelihood estimation in Gaussian models under total positivity](https://mlsanity.com/paper/1702.04031/) (2017)
- [Learning Graphs with Monotone Topology Properties and Multiple Connected Components](https://mlsanity.com/paper/1705.10934/) (2017)
- [Learning High-dimensional Gaussian Graphical Models under Total Positivity without Adjustment of Tuning Parameters](https://mlsanity.com/paper/1906.05159/) (2019)

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

- [Efficient Graph Laplacian Estimation by Proximal Newton](https://mlsanity.com/paper/2302.06434/) (2023)
- [Learning Multi-Attribute Differential Graphs with Non-Convex Penalties](https://mlsanity.com/paper/2505.09748/) (2025)
- [Multi-Attribute Graph Estimation with Sparse-Group Non-Convex Penalties](https://mlsanity.com/paper/2505.11984/) (2025)
- [Learning Time-Varying Graphs from Incomplete Graph Signals](https://mlsanity.com/paper/2510.17903/) (2025)
- [Learning Conditional Independence Differential Graphs From Time-Dependent Data](https://mlsanity.com/paper/2512.06960/) (2025)

## Abstract (arXiv)

We consider the problem of learning a sparse undirected graph underlying a given set of multivariate data. We focus on graph Laplacian-related constraints on the sparse precision matrix that encodes conditional dependence between the random variables associated with the graph nodes. Under these constraints the off-diagonal elements of the precision matrix are non-positive (total positivity), and the precision matrix may not be full-rank. We investigate modifications to widely used penalized log-likelihood approaches to enforce total positivity but not the Laplacian structure. The graph Laplacian can then be extracted from the off-diagonal precision matrix. An alternating direction method of multipliers (ADMM) algorithm is presented and analyzed for constrained optimization under Laplacian-related constraints and lasso as well as adaptive lasso penalties. Numerical results based on synthetic data show that the proposed constrained adaptive lasso approach significantly outperforms existing Laplacian-based approaches. We also evaluate our approach on real financial data.