2024/09/19 by Hector Chahuara, Chahuara, Hector, Gonzalo Mateos +1
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #FOS: Electrical engineering #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and ELM #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2409.12916
openalex publication_date 2024/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.