# Learning Sparse Graphs Under Smoothness Prior

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2016.

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

- [Learning Connectivity with Graph Convolutional Networks for Skeleton-based Action Recognition](https://mlsanity.com/paper/2112.03328/) (2021)
- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [Online Graph Learning under Smoothness Priors](https://mlsanity.com/paper/2103.03762/) (2021)
- [Learning Sheaf Laplacian Optimizing Restriction Maps](https://mlsanity.com/paper/2501.19207/) (2025)
- [Learning Product Graphs from Spectral Templates](https://mlsanity.com/paper/2211.02893/) (2022)
- [A Markov Random Field model for Hypergraph-based Machine Learning](https://mlsanity.com/paper/2308.14172/) (2023)
- [Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty](https://mlsanity.com/paper/2105.05458/) (2021)
- [Graph Structure Learning with Interpretable Bayesian Neural Networks](https://mlsanity.com/paper/2406.14786/) (2024)
- [Robust Graph Learning Under Wasserstein Uncertainty](https://mlsanity.com/paper/2105.04210/) (2021)
- [Learning graphs and simplicial complexes from data](https://mlsanity.com/paper/2312.10545/) (2023)
- [Learning Cartesian Product Graphs with Laplacian Constraints](https://mlsanity.com/paper/2402.08105/) (2024)
- [Joint Network Topology Inference via Structured Fusion Regularization](https://mlsanity.com/paper/2103.03471/) (2021)
- [Skeleton-based Hand-Gesture Recognition with Lightweight Graph Convolutional Networks](https://mlsanity.com/paper/2104.04255/) (2021)
- [Task-Based Graph Signal Compression](https://mlsanity.com/paper/2110.12387/) (2021)
- [Plug In and Learn: Federated Intelligence over a Smart Grid of Models](https://mlsanity.com/paper/2302.04363/) (2023)
- [Explainable Spatio-Temporal GCNNs for Irregular Multivariate Time Series: Architecture and Application to ICU Patient Data](https://mlsanity.com/paper/2411.01070/) (2024)
- [Scalable Hypergraph Structure Learning with Diverse Smoothness Priors](https://mlsanity.com/paper/2504.03583/) (2025)
- [Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition](https://mlsanity.com/paper/2104.05482/) (2021)
- [Teaching MLP More Graph Information: A Three-stage Multitask Knowledge Distillation Framework](https://mlsanity.com/paper/2403.01079/) (2024)
- [Joint Data Inpainting and Graph Learning via Unrolled Neural Networks](https://mlsanity.com/paper/2407.11429/) (2024)
- [Cramer-Rao Bounds for Laplacian Matrix Estimation](https://mlsanity.com/paper/2504.04576/) (2025)
- [Learning Kronecker-Structured Graphs from Smooth Signals](https://mlsanity.com/paper/2505.09822/) (2025)
- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)

## Abstract (arXiv)

In this paper, we are interested in learning the underlying graph structure behind training data. Solving this basic problem is essential to carry out any graph signal processing or machine learning task. To realize this, we assume that the data is smooth with respect to the graph topology, and we parameterize the graph topology using an edge sampling function. That is, the graph Laplacian is expressed in terms of a sparse edge selection vector, which provides an explicit handle to control the sparsity level of the graph. We solve the sparse graph learning problem given some training data in both the noiseless and noisy settings. Given the true smooth data, the posed sparse graph learning problem can be solved optimally and is based on simple rank ordering. Given the noisy data, we show that the joint sparse graph learning and denoising problem can be simplified to designing only the sparse edge selection vector, which can be solved using convex optimization.