Optimal Change Point Detection and Localization in Sparse Dynamic Networks

Abstract

We study the problem of change point localization in dynamic networks models. We assume that we observe a sequence of independent adjacency matrices of the same size, each corresponding to a realization of an unknown inhomogeneous Bernoulli model. The underlying distribution of the adjacency matrices are piecewise constant, and may change over a subset of the time points, called change points. We are concerned with recovering the unknown number and positions of the change points. In our model setting we allow for all the model parameters to change with the total number of time points, including the network size, the minimal spacing between consecutive change points, the magnitude of the smallest change and the degree of sparsity of the networks. We first identify a region of impossibility in the space of the model parameters such that no change point estimator is provably consistent if the data are generated according to parameters falling in that region. We propose a computationally-simple algorithm for network change point localization, called Network Binary Segmentation, that relies on weighted averages of the adjacency matrices. We show that Network Binary Segmentation is consistent over a range of the model parameters that nearly cover the complement of the impossibility region, thus demonstrating the existence of a phase transition for the problem at hand. Next, we devise a more sophisticated algorithm based on singular value thresholding, called Local Refinement, that delivers more accurate estimates of the change point locations. Under appropriate conditions, Local Refinement guarantees a minimax optimal rate for network change point localization while remaining computationally feasible.

49 pages

References in corpus (11)

• Emergence of scaling in random networks
• Stochastic blockmodels and community structure in networks
• Matrix estimation by Universal Singular Value Thresholding
• Dynamic stochastic blockmodels for time-evolving social networks
• Rate-optimal graphon estimation
• Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
• Change-point detection in panel data via double CUSUM statistic
• Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features
• Locality statistics for anomaly detection in time series of graphs
• Change Point Estimation in a Dynamic Stochastic Block Model
• Sequential change-point detection in high-dimensional Gaussian graphical models

Cited by in corpus (16)

• Change-point detection in dynamic networks via graphon estimation
• Bootstrapping Networks with Latent Space Structure
• Optimal nonparametric change point detection and localization
• Localizing Changes in High-Dimensional Vector Autoregressive Processes
• A review on minimax rates in change point detection and localisation
• Change point localization in dependent dynamic nonparametric random dot product graphs
• Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality
• Optimal network online change point localisation
• Localizing Changes in High-Dimensional Regression Models
• Inference on the Change Point for High Dimensional Dynamic Graphical Models
• These Unprecedented Times: The Dynamic Pattern Of COVID-19 Deaths Around The World
• Adaptive Inference for Change Points in High-Dimensional Data
• Sequential (Quickest) Change Detection: Classical Results and New Directions
• Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• Adversarially robust change point detection