Abstract
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.
Introduction
In many modern data-driven applications—ranging from social network analysis to sensor grid monitoring—the underlying graph structure that dictates the relationships between data points is often hidden or dynamic. Identifying this latent topology is a fundamental task in Graph Signal Processing (GSP). While batch algorithms have been developed to learn graphs from "smooth" signals (where connected nodes exhibit similar values), they scale poorly as data accumulates over time. This paper addresses the challenge of learning a latent graph structure from a continuous stream of smooth signals, ensuring the algorithm is lightweight and capable of tracking temporal changes.
Methodology
The core of our approach is the Online Proximal ADMM (OPADMM) algorithm. It is designed to solve a time-varying optimization problem where the goal is to find a graph adjacency matrix that minimizes signal smoothness (Total Variation) while adhering to sparsity and connectivity constraints.
Recursive Dissimilarity Tracking
To handle streaming data, the algorithm maintains a recursive estimate of the node dissimilarity matrix. By employing a forgetting factor, OPADMM can prioritize recent observations, allowing the model to adapt as the underlying network topology evolves.
Proximal ADMM Framework
We adapt the proximal variant of ADMM for the online setting. A key innovation is the inclusion of a proximal term in the update steps. While originally intended to ensure convergence, this term acts as a temporal regularizer, penalizing large, erratic jumps between consecutive graph estimates. This ensures that the learned topology changes smoothly over time.
Computational Efficiency
To remain lightweight, OPADMM performs only a single optimization iteration per new signal observation. The update rules are entrywise separable, allowing for parallelization and ensuring a fixed computational complexity of $O(n^2)$ per time step, where $n$ is the number of nodes.
Experimental Evaluation
We evaluated OPADMM against two primary baselines: Online Proximal Gradient (PG) and Dual Proximal Gradient (DPG).
Datasets
- Synthetic Graphs: We utilized three standard models—Gaussian (Random Geometric), Erdős-Rényi (ER), and Preferential Attachment (PA)—in both stationary and dynamic (piecewise stationary) configurations.
- Real-World Networks: We tested the algorithm on structural and power network topologies from the SuiteSparse Matrix Collection, including the
mesh1e1,bcspwr03, andlshp_265datasets.
Performance Results
In stationary environments, OPADMM demonstrates significantly faster convergence to the ground-truth topology compared to PG and DPG. This is evident across various real-world datasets, as shown in Figure 1.
The algorithm's true strength lies in its tracking capability. In dynamic scenarios where the graph structure changes abruptly, OPADMM exhibits a much sharper recovery curve. As illustrated in Figure 2, the algorithm quickly adapts to the new network state, maintaining lower error levels than competing online methods.
Conclusion
OPADMM offers a robust and efficient solution for learning graphs from streaming signals. By integrating proximal terms into an online ADMM framework, the algorithm achieves superior tracking performance and faster convergence while remaining computationally lightweight. Theoretical analysis confirms a sublinear static regret of $O(\sqrt{p})$, providing strong guarantees for its long-term performance. Future research will explore automated hyperparameter tuning and extensions to more complex signal models.
Summary updated