Change point localization in dependent dynamic nonparametric random dot product graphs

Abstract

In this paper, we study the offline change point localization problem in a sequence of dependent nonparametric random dot product graphs. To be specific, assume that at every time point, a network is generated from a nonparametric random dot product graph model \citep[see e.g.][]{athreya2017statistical}, where the latent positions are generated from unknown underlying distributions. The underlying distributions are piecewise constant in time and change at unknown locations, called change points. Most importantly, we allow for dependence among networks generated between two consecutive change points. This setting incorporates edge-dependence within networks and temporal dependence between networks, which is the most flexible setting in the published literature. To accomplish the task of consistently localizing change points, we propose a novel change point detection algorithm, consisting of two steps. First, we estimate the latent positions of the random dot product model, our theoretical result being a refined version of the state-of-the-art results, allowing the dimension of the latent positions to diverge. Subsequently, we construct a nonparametric version of the CUSUM statistic \citep[e.g.][]{Page1954, padilla2019optimal} that allows for temporal dependence. Consistent localization is proved theoretically and supported by extensive numerical experiments, which illustrate state-of-the-art performance. We also provide in depth discussion of possible extensions to give more understanding and insights.

References in corpus (11)

• Simultaneous whole-animal 3D-imaging of neuronal activity using light field microscopy
• Matrix estimation by Universal Singular Value Thresholding
• Change-point detection in panel data via double CUSUM statistic
• Nonparametric maximum likelihood approach to multiple change-point problems
• Locality statistics for anomaly detection in time series of graphs
• Change-point detection in high-dimensional covariance structure
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Optimal Covariance Change Point Localization in High Dimension
• Change-point detection in dynamic networks via graphon estimation
• Optimal nonparametric change point detection and localization

Cited by in corpus (3)

• A review on minimax rates in change point detection and localisation
• Multiple Network Embedding for Anomaly Detection in Time Series of Graphs
• Optimal Change-Point Detection with Training Sequences in the Large and Moderate Deviations Regimes