Kalman Filter for Tracking Network Dynamic

Abstract

In this paper, we address the problem of tracking dynamic changes in graph topology under a linear graph filtering random process. We propose a graph-based state-space model (SSM), where the measurements are graph signals and the underlying evolving topology serves as the state variable. The proposed approach is based on representing the graphical process as a graph filtering process, and leveraging the incidence matrix-based representation of the Laplacian to formulate the linear SSMs associated with the Kalman filter. We explore two scenarios. In the first scenario, we have a known edge set, and we aim to track the network weights. We show that under suitable reformulation, this scenario can be solved by the classical Kalman filter. In the second scenario, we assume an unknown edge set, where the goal is to track both network connectivity changes and the weights. We discuss three Kalman-filter-based approaches for this scenario by incorporating sparsity-driven techniques: 1) an ignorant Kalman filter that processes the entire signal; 2) a Kalman filter with thresholding of the predicted graph at each iteration; and 3) partial-thresholding, where the estimator update occurs without thresholding. The simulation results demonstrate the performance of the proposed approaches in tracking changes in graph topologies.