# Online Graph Learning under Smoothness Priors

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 22 references that are in the map.
- First posted on arXiv 5 Mar 2021.

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [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)
- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Learning Sparse Graphs Under Smoothness Prior](https://mlsanity.com/paper/1609.03448/) (2016)
- [Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information](https://mlsanity.com/paper/2007.03653/) (2020)
- [Learning Undirected Graphs in Financial Markets](https://mlsanity.com/paper/2005.09958/) (2020)
- [Online Discriminative Graph Learning from Multi-Class Smooth Signals](https://mlsanity.com/paper/2101.00184/) (2021)
- [Time-Varying Graph Learning with Constraints on Graph Temporal Variation](https://mlsanity.com/paper/2001.03346/) (2020)
- [Online Sparse Subspace Clustering](https://mlsanity.com/paper/1902.10842/) (2019)

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

- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [Learning Sparse Graphs via Majorization-Minimization for Smooth Node Signals](https://mlsanity.com/paper/2202.02815/) (2022)
- [Time-Varying Graph Learning for Data with Heavy-Tailed Distribution](https://mlsanity.com/paper/2501.00606/) (2024)
- [Online Graph Learning in Dynamic Environments](https://mlsanity.com/paper/2110.05023/) (2021)
- [Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks](https://mlsanity.com/paper/2307.04374/) (2023)
- [Scalable Hypergraph Structure Learning with Diverse Smoothness Priors](https://mlsanity.com/paper/2504.03583/) (2025)
- [Online Proximal ADMM for Graph Learning from Streaming Smooth Signals](https://mlsanity.com/paper/2409.12916/) (2024)
- [Dynamic Elliptical Graph Factor Models via Riemannian Optimization with Geodesic Temporal Regularization](https://mlsanity.com/paper/2605.18316/) (2026)

## Abstract (arXiv)

The growing success of graph signal processing (GSP) approaches relies heavily on prior identification of a graph over which network data admit certain regularity. However, adaptation to increasingly dynamic environments as well as demands for real-time processing of streaming data pose major challenges to this end. In this context, we develop novel algorithms for online network topology inference given streaming observations assumed to be smooth on the sought graph. Unlike existing batch algorithms, our goal is to track the (possibly) time-varying network topology while maintaining the memory and computational costs in check by processing graph signals sequentially-in-time. To recover the graph in an online fashion, we leverage proximal gradient (PG) methods to solve a judicious smoothness-regularized, time-varying optimization problem. Under mild technical conditions, we establish that the online graph learning algorithm converges to within a neighborhood of (i.e., it tracks) the optimal time-varying batch solution. Computer simulations using both synthetic and real financial market data illustrate the effectiveness of the proposed algorithm in adapting to streaming signals to track slowly-varying network connectivity.