Online Time-Varying Topology Identification Via Prediction-Correction Algorithms

Alberto Natali, Mario Coutino, Elvin Isufi, Geert Leus

TL;DR

This paper introduces a new online algorithm for tracking the structure of a network (graph topology) as it changes over time. By using a "prediction-correction" framework from time-varying optimization, the authors can infer shifting relationships between data points on-the-fly, providing a faster and more memory-efficient alternative to traditional batch-processing methods.

What Problem Does This Paper Address?

In many fields—from monitoring power grids to analyzing brain activity—we have data flowing from various points (nodes), but we don't always know how those points are connected (the topology). This is known as topology identification.

The challenge gets significantly harder when the network is dynamic. Most existing methods use "batch processing": they collect a window of data, assume the network is static during that window, and solve a complex optimization problem. This approach has three major flaws:

  1. It’s slow and memory-intensive.
  2. It struggles to handle real-time streaming data.
  3. It requires researchers to manually decide how to "window" the data or how to mathematically enforce "smoothness" between time steps.

The authors aim to solve this by creating an adaptive, online algorithm that tracks the network structure as each new data point arrives.

Methods

The authors leverage a Time-Varying Optimization framework. Instead of solving one giant problem, they solve a sequence of smaller problems as time progresses. The core of their approach is a two-step "Prediction-Correction" cycle:

  1. Prediction: Before the next data point arrives, the algorithm uses a Taylor expansion of the previous state to "guess" how the network is evolving. This gives the solver a head start.
  2. Correction: Once the new data arrives, the algorithm performs a few steps of a Projected Gradient (PG) descent to refine that guess and move closer to the true current topology.

They specialize this framework for the Gaussian Graphical Model (GGM), where the goal is to estimate a "precision matrix." In a GGM, a zero entry in this matrix means two nodes are independent (no edge), while a non-zero entry indicates a connection.

A unique feature of this method is implicit regularization. Because the algorithm only performs a limited number of iterations (an "iteration budget") at each time step, it naturally prevents the model from changing too wildly or over-fitting to noise. This removes the need for complex, explicit mathematical penalties for "jittery" network changes.

Datasets

The paper evaluates the algorithm using synthetic datasets designed to simulate "triggering events":

  • Small Scale: A graph with $N=8$ nodes where the topology is held constant for 200 time steps, then abruptly perturbed (changing edge weights by 20%), repeated over 600 time steps.
  • Large Scale: A graph with $N=128$ nodes to test the algorithm's scalability and tracking performance in higher dimensions.

The data consists of graph signals drawn from a multivariate Gaussian distribution based on these changing topologies.

Key Insights and Ideas

  • Early Stopping as a Feature: Usually, "early stopping" is a compromise for speed. Here, the authors argue it acts as a temporal regularizer, enforcing similarity between consecutive network states without needing an explicit "smoothness" constraint in the cost function.
  • Tracking a Moving Target: By using the time-derivative of the gradient, the "Prediction" step allows the algorithm to follow the "optimal" solution trajectory even when the underlying statistics are non-stationary.
  • On-the-Fly Adaptability: Unlike windowing methods, this algorithm doesn't need to know when a change happens. It simply reacts to the stream of incoming data.

Key Results

  • Superior Tracking: The Prediction-Correction (P-C) approach consistently achieved lower Normalized Mean Square Error (NMSE) compared to a "Correction-Only" approach, especially immediately after a network change (the "triggering events" at $t=200$ and $t=400$).
  • Convergence: The algorithm successfully converged toward the optimal Batch Maximum Likelihood Estimation (B-MLE) solution over time.
  • Scalability: The authors demonstrated that the framework remains functional even as the number of nodes increases to $N=128$, where computing a full batch solution would be computationally prohibitive for real-time use.

Limitations and Future Work

  • Synthetic Constraints: The current evaluation relies on synthetic data with relatively simple perturbation models. The authors acknowledge the need to validate the algorithm on real-world datasets in future work.
  • Sparsity Assumptions: While the algorithm tracks weights well, the authors plan to extend the work to cases where the "sparsity pattern" (which edges exist at all) is known or needs to be more strictly enforced.
  • Cost Function Variety: The current study focuses on the GGM (Gaussian) cost function. Future research could explore different cost functions suited for non-Gaussian data or directed graphs (causal relationships).

Summary updated

Abstract

Signal processing and machine learning algorithms for data sup-ported 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.
BibTeX
@inproceedings{natali2021online,
  author = {Alberto Natali and Mario Coutino and Elvin Isufi and Geert Leus},
  title = {{Online Time-Varying Topology Identification Via Prediction-Correction Algorithms}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=fqLSrJVYb8},
}

Loading related content...

Figure