Network Topology Change-Point Detection from Graph Signals with Prior Spectral Signatures

We consider the problem of sequential graph topology change-point detection from graph signals. We assume that signals on the nodes of the graph are regularized by the underlying graph structure via a graph filtering model, which we then leverage to distill the graph topology change-point detection problem to a subspace detection problem. We demonstrate how prior information on the spectral signature of the post-change graph can be incorporated to implicitly denoise the observed sequential data, thus leading to a natural CUSUM-based algorithm for change-point detection. Numerical experiments illustrate the performance of our proposed approach, particularly underscoring the benefits of (potentially noisy) prior information.

1. INTRODUCTION

Networks or graphs have emerged as effective tools to understand and summarize complex systems across multiple domains of knowledge [1]–[3]. Representing interconnected systems as graphs, where nodes correspond to agents and edges correspond to pairwise interactions between these agents, allows us to apply tools from graph theory to reveal key properties of the underlying systems such as the emergence of community structure [4],[5] or the existence of influential agents [6],[7].