Rapid Change Localization in Dynamic Graphical Models

Abstract

Gaussian graphical models have emerged as a powerful tool for modeling and understanding multivariate data across various domains. In this paper, we consider the problem of change localization in the Gaussian graphical model, where it is known that a change has occurred in the underlying graph structure, and the goal is to localize the change rapidly. This paradigm occurs in various applications, from cyber-physical systems and biological networks to social networks and epidemiology. We introduce a novel algorithm, dubbed FOLk-DGM (Fast Online Localization in Dynamic Graphical Models), that is both computationally efficient and performs change localization with provably low latency (time elapsed before the change is localized). We present the theoretical properties of the algorithm and complement our theoretical results with experimental results.