# Optimal network online change point localisation

arXiv: https://arxiv.org/abs/2101.05477 · HTML: https://mlsanity.com/paper/2101.05477/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 14 Jan 2021.

## Builds on (most cited first, 11 of 11)

- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [High-dimensional, multiscale online changepoint detection](https://mlsanity.com/paper/2003.03668/) (2020)
- [ecp: An R Package for Nonparametric Multiple Change Point Analysis of Multivariate Data](https://mlsanity.com/paper/1309.3295/) (2013)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Sequential change-point detection based on nearest neighbors](https://mlsanity.com/paper/1604.03611/) (2016)
- [Optimal Change Point Detection and Localization in Sparse Dynamic Networks](https://mlsanity.com/paper/1809.09602/) (2018)
- [A likelihood ratio approach to sequential change point detection for a general class of parameters](https://mlsanity.com/paper/1802.07696/) (2018)
- [Sequential change-point detection in high-dimensional Gaussian graphical models](https://mlsanity.com/paper/1806.07870/) (2018)
- [Sequential nonparametric tests for a change in distribution: an application to detecting radiological anomalies](https://mlsanity.com/paper/1612.07867/) (2016)
- [Online detection of local abrupt changes in high-dimensional Gaussian graphical models](https://mlsanity.com/paper/2003.06961/) (2020)

## Built on by (most cited first, 5 of 5)

- [Online Change Point Detection for Weighted and Directed Random Dot Product Graphs](https://mlsanity.com/paper/2201.11222/) (2022)
- [Graph similarity learning for change-point detection in dynamic networks](https://mlsanity.com/paper/2203.15470/) (2022)
- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [Network two-sample test for block models](https://mlsanity.com/paper/2406.06014/) (2024)
- [Multiresolution Analysis and Statistical Thresholding on Dynamic Networks](https://mlsanity.com/paper/2506.01208/) (2025)

## Abstract (arXiv)

We study the problem of online network change point detection. In this setting, a collection of independent Bernoulli networks is collected sequentially, and the underlying distributions change when a change point occurs. The goal is to detect the change point as quickly as possible, if it exists, subject to a constraint on the number or probability of false alarms. In this paper, on the detection delay, we establish a minimax lower bound and two upper bounds based on NP-hard algorithms and polynomial-time algorithms, i.e., [ mboxdetection delay begincases gtrsim log(1/α) fracmaxr2/n, , 1kappa02 n ρ, lesssim log(Delta/α) fracmaxr2/n, , log(r)kappa02 n ρ, & mboxwith NP-hard algorithms, lesssim log(Delta/α) fracrkappa02 n ρ, & mboxwith polynomial-time algorithms, endcases ] where kappa0, n, ρ, r and α are the normalised jump size, network size, entrywise sparsity, rank sparsity and the overall Type-I error upper bound. All the model parameters are allowed to vary as Delta, the location of the change point, diverges. The polynomial-time algorithms are novel procedures that we propose in this paper, designed for quick detection under two different forms of Type-I error control. The first is based on controlling the overall probability of a false alarm when there are no change points, and the second is based on specifying a lower bound on the expected time of the first false alarm. Extensive experiments show that, under different scenarios and the aforementioned forms of Type-I error control, our proposed approaches outperform state-of-the-art methods.