# How to learn a graph from smooth signals

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

## Key facts

- Cited by 146 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jan 2016.

## Built on by (most cited first, 30 of 146)

- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [A Survey on Graph Structure Learning: Progress and Opportunities](https://mlsanity.com/paper/2103.03036/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [AbDiffuser: Full-Atom Generation of in vitro Functioning Antibodies](https://mlsanity.com/paper/2308.05027/) (2023)
- [Multi-modal Graph Learning for Disease Prediction](https://mlsanity.com/paper/2203.05880/) (2022)
- [Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing](https://mlsanity.com/paper/2208.08302/) (2022)
- [Modeling Multivariate Biosignals With Graph Neural Networks and Structured State Space Models](https://mlsanity.com/paper/2211.11176/) (2022)
- [Learning to Learn Graph Topologies](https://mlsanity.com/paper/2110.09807/) (2021)
- [Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach](https://mlsanity.com/paper/2209.08264/) (2022)
- [Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition](https://mlsanity.com/paper/2405.13707/) (2024)
- [Learning Connectivity with Graph Convolutional Networks for Skeleton-based Action Recognition](https://mlsanity.com/paper/2112.03328/) (2021)
- [Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Neural Networks](https://mlsanity.com/paper/2212.10822/) (2022)
- [SLMRec: Distilling Large Language Models into Small for Sequential Recommendation](https://mlsanity.com/paper/2405.17890/) (2024)
- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [Signal processing on simplicial complexes](https://mlsanity.com/paper/2106.07471/) (2021)
- [Learning Time-Varying Graphs from Online Data](https://mlsanity.com/paper/2110.11017/) (2021)
- [GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2306.11264/) (2023)
- [Chasing Fairness in Graphs: A GNN Architecture Perspective](https://mlsanity.com/paper/2312.12369/) (2023)
- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [MM-GNN: Mix-Moment Graph Neural Network towards Modeling Neighborhood Feature Distribution](https://mlsanity.com/paper/2208.07012/) (2022)
- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [Principle of Relevant Information for Graph Sparsification](https://mlsanity.com/paper/2206.00118/) (2022)
- [Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering](https://mlsanity.com/paper/2206.02386/) (2022)
- [A Unified Framework for Optimization-Based Graph Coarsening](https://mlsanity.com/paper/2210.00437/) (2022)
- [Learning Hypergraphs From Signals With Dual Smoothness Prior](https://mlsanity.com/paper/2211.01717/) (2022)
- [Online Graph Learning under Smoothness Priors](https://mlsanity.com/paper/2103.03762/) (2021)
- [Learning Graphical Factor Models with Riemannian Optimization](https://mlsanity.com/paper/2210.11950/) (2022)
- [LAN: Learning Adaptive Neighbors for Real-Time Insider Threat Detection](https://mlsanity.com/paper/2403.09209/) (2024)

## Abstract (arXiv)

We propose a framework that learns the graph structure underlying a set of smooth signals. Given X∈ℝm× n whose rows reside on the vertices of an unknown graph, we learn the edge weights w∈ℝ_+m(m-1)/2 under the smoothness assumption that trX^top LX is small. We show that the problem is a weighted ℓ-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.