# Online Proximal ADMM for Graph Learning from Streaming Smooth Signals

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 19 Sep 2024.

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

- [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)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information](https://mlsanity.com/paper/2007.03653/) (2020)
- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [Optimization and Learning with Information Streams: Time-varying Algorithms and Applications](https://mlsanity.com/paper/1910.08123/) (2019)
- [Learning Graphs with Monotone Topology Properties and Multiple Connected Components](https://mlsanity.com/paper/1705.10934/) (2017)
- [Learning Undirected Graphs in Financial Markets](https://mlsanity.com/paper/2005.09958/) (2020)
- [Joint Network Topology Inference in the Presence of Hidden Nodes](https://mlsanity.com/paper/2306.17364/) (2023)
- [Learning Time-Varying Graphs from Online Data](https://mlsanity.com/paper/2110.11017/) (2021)
- [Online Graph Learning under Smoothness Priors](https://mlsanity.com/paper/2103.03762/) (2021)
- [Learning Graph Structure from Convolutional Mixtures](https://mlsanity.com/paper/2205.09575/) (2022)
- [Graph Structure Learning with Interpretable Bayesian Neural Networks](https://mlsanity.com/paper/2406.14786/) (2024)
- [Dual-based Online Learning of Dynamic Network Topologies](https://mlsanity.com/paper/2211.07449/) (2022)

## Abstract (arXiv)

Graph signal processing deals with algorithms and signal representations that leverage graph structures for multivariate data analysis. Often said graph topology is not readily available and may be time-varying, hence (dynamic) graph structure learning from nodal (e.g., sensor) observations becomes a critical first step. In this paper, we develop a novel algorithm for online graph learning using observation streams, assumed to be smooth on the latent graph. Unlike batch algorithms for topology identification from smooth signals, our modus operandi is to process graph signals sequentially and thus keep memory and computational costs in check. To solve the resulting smoothness-regularized, time-varying inverse problem, we develop online and lightweight iterations built upon the proximal variant of the alternating direction method of multipliers (ADMM), well known for its fast convergence in batch settings. The proximal term in the topology updates seamlessly implements a temporal-variation regularization, and we argue the online procedure exhibits sublinear static regret under some simplifying assumptions. Reproducible experiments with synthetic and real graphs demonstrate the effectiveness of our method in adapting to streaming signals and tracking slowly-varying network connectivity. The proposed approach also exhibits better tracking performance (in terms of suboptimality), when compared to state-of-the-art online graph learning baselines.