Abstract
Signal processing and machine learning algorithms for data supported over graphs require the knowledge of the graph topology. Unless this information is given by the physics of the problem (e.g., water supply networks, power grids), the topology has to be learned from data. Topology identification is a challenging task, as the problem is often ill-posed, and becomes even harder when the graph structure is time-varying. In this paper, we address the problem of dynamic topology identification by building on recent results from time-varying optimization, devising a general-purpose online algorithm operating in non-stationary environments. Because of its iteration-constrained nature, the proposed approach exhibits an intrinsic temporal-regularization of the graph topology without explicitly enforcing it. As a case-study, we specialize our method to the Gaussian graphical model (GGM) problem and corroborate its performance.
Introduction
In many modern data-driven fields—ranging from power grid monitoring to neuroimaging—the underlying structure or "topology" of a network is not explicitly known. Topology identification aims to infer these connections from observed data signals. However, real-world networks are rarely static; they evolve over time.
Traditional approaches to this problem typically rely on "batch processing," where data is collected over a fixed window and analyzed under the assumption of a static network. This approach suffers from significant drawbacks: it is computationally expensive, memory-intensive, and struggles to adapt to real-time streaming data. Furthermore, batch methods often require manual tuning of temporal smoothness constraints to prevent erratic changes between windows. This paper introduces an online, adaptive algorithm designed to track time-varying topologies efficiently as new data arrives.
Methodology
The proposed approach leverages a Time-Varying Optimization framework, which treats the network identification as a sequence of evolving optimization problems. The core of the strategy is a two-step Prediction-Correction cycle, detailed in Algorithm 1.
- Prediction: Before new data arrives at time $t+1$, the algorithm uses a Taylor expansion of the previous state to estimate the trajectory of the optimal solution. This provides a "warm start" for the solver.
- Correction: Once the new data is received, the algorithm performs a limited number of Projected Gradient (PG) descent steps to refine the estimate and move closer to the true current topology.
This framework is applied to the Gaussian Graphical Model (GGM), where the objective is to estimate a precision matrix representing node dependencies. A key innovation of this method is implicit regularization. By restricting the number of iterations per time step (the "iteration budget"), the algorithm naturally enforces temporal smoothness. This prevents the model from over-fitting to instantaneous noise or changing too abruptly, eliminating the need for explicit mathematical penalties for non-smoothness.
Experimental Results
The algorithm was evaluated using synthetic datasets designed to simulate abrupt network changes ("triggering events"). The study examined both small-scale ($N=8$ nodes) and large-scale ($N=128$ nodes) scenarios.
As shown in the results, the Prediction-Correction (P-C) approach consistently achieves a lower Normalized Mean Square Error (NMSE) than a Correction-Only (C-O) baseline. The advantage of the prediction step is most evident immediately following a topology shift (e.g., at iterations 200 and 400 in the $N=8$ case), where the P-C method recovers the new structure much faster. Furthermore, the algorithm demonstrates strong scalability; it remains functional and accurate for $N=128$ nodes, a regime where full batch solutions become computationally prohibitive for real-time applications.
Conclusion
This work presents a robust online framework for tracking dynamic network topologies. By utilizing a prediction-correction mechanism, the algorithm effectively follows the optimal solution trajectory in non-stationary environments. The use of an iteration budget provides a natural temporal regularization, making the approach both computationally efficient and stable. Future research will focus on validating the algorithm with real-world datasets and extending the framework to handle unknown sparsity patterns and non-Gaussian data distributions.
Summary updated