Online Proximal ADMM for Graph Learning from Streaming Smooth Signals
This work addresses the need for efficient dynamic graph structure learning in applications like sensor networks, though it appears incremental as it builds on existing ADMM methods for online adaptation.
The paper tackles the problem of learning time-varying graph topologies from streaming smooth signals, proposing an online proximal ADMM algorithm that processes data sequentially to reduce memory and computational costs. The method demonstrates effectiveness in adapting to streaming signals and tracking slowly-varying network connectivity, showing better tracking performance compared to state-of-the-art online baselines.
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.