# Network Topology Inference with Sparsity and Laplacian Constraints

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 2 Sep 2023.

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [Graph Signal Processing: History, Development, Impact, and Outlook](https://mlsanity.com/paper/2303.12211/) (2023)
- [Signal Processing on Directed Graphs](https://mlsanity.com/paper/2008.00586/) (2020)
- [Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fields](https://mlsanity.com/paper/1404.6640/) (2014)
- [Maximum likelihood estimation in Gaussian models under total positivity](https://mlsanity.com/paper/1702.04031/) (2017)
- [Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity](https://mlsanity.com/paper/2112.01939/) (2021)
- [Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction](https://mlsanity.com/paper/1503.02893/) (2015)
- [Hankel Matrix Nuclear Norm Regularized Tensor Completion for N-dimensional Exponential Signals](https://mlsanity.com/paper/1604.02100/) (2016)
- [Maximum Likelihood Estimation for Brownian Motion Tree Models Based on One Sample](https://mlsanity.com/paper/2112.00816/) (2021)
- [Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery -- Application in Fast NMR Spectroscopy](https://mlsanity.com/paper/1809.00750/) (2018)
- [Adaptive Estimation of Graphical Models under Total Positivity](https://mlsanity.com/paper/2210.15471/) (2022)

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

- [Learning Large-Scale MTP2 Gaussian Graphical Models via Bridge-Block Decomposition](https://mlsanity.com/paper/2309.13405/) (2023)
- [Learning Networks from Wide-Sense Stationary Stochastic Processes](https://mlsanity.com/paper/2412.03768/) (2024)
- [Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation](https://mlsanity.com/paper/2606.24011/) (2026)
- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)

## Abstract (arXiv)

We tackle the network topology inference problem by utilizing Laplacian constrained Gaussian graphical models, which recast the task as estimating a precision matrix in the form of a graph Laplacian. Recent research citeying2020nonconvex has uncovered the limitations of the widely used ℓ1-norm in learning sparse graphs under this model: empirically, the number of nonzero entries in the solution grows with the regularization parameter of the ℓ1-norm; theoretically, a large regularization parameter leads to a fully connected (densest) graph. To overcome these challenges, we propose a graph Laplacian estimation method incorporating the ℓ0-norm constraint. An efficient gradient projection algorithm is developed to solve the resulting optimization problem, characterized by sparsity and Laplacian constraints. Through numerical experiments with synthetic and financial time-series datasets, we demonstrate the effectiveness of the proposed method in network topology inference.