Optimal change point detection and localization in sparse dynamic networks

DOI10.1214/20-AOS1953MaRDI QIDQ97726zbMATH OpenOpenAlexFDO

Authors Daren Wang, Yi Yu, Alessandro Rinaldo

Publication date 1 February 2021

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.09602, https://projecteuclid.org/euclid.aos/1611889224

zbMATH Keywords

change point detectionlow-rank networksminimax optimalitystochastic block model

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Nonparametric hypothesis testing (62G10) Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Neural nets and related approaches to inference from stochastic processes (62M45) Economic time series analysis (91B84)

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.

Review text

The study refers to a dynamic network model consisting of a sequence (A(t))\(^T_{t=1}\) of \(n\times n\) adjacency matrices of independent inhomogeneous Bernoulli networks with means (\(\theta\)(t))\(^T_{t=1}\) that satisfy a set of conditions, summarized as Assumption~1. The model is described by the parameters: \(\Delta\), \(k_0\), \(n\) and \(\rho\). When \(T\) grows unbounded, the parameters will change as functions of \(T\) and the number \(K\) of change points will change, too. One is concerned with the problem of estimating the number and location of the change points, based on one observation \((A(1),\dots, A(T))\) of adjacency matrices satisfying Assumption~1. The feasibility of a consistent estimation of the change point location is studied in the second section. One develops an algorithm called network binary segmentation, NBS, which is able to localize multiple change points consistently. In the third section, one shows that under stronger conditions on model and scaling, a two-step procedure can achieve a minimax optimal localization rate. The procedure applies first NBS and then a local refinement procedure, the LR algorithm. The authors prove that the LR procedure indeed improves localization rates, it is nearly minimax optimal. New assumptions are introduced. Simulation results are presented in the fourth section. Proofs of the main results are presented in the Appendix part. Some details, discussion and technical elements can be found in the supplementary material to this article, \url{doi:10.1214/20-AOS1953SUPP;.pdf}.

Recommendations

• Optimal nonparametric change point analysis
• Optimal covariance change point localization in high dimensions
• The Bethe Hessian and information theoretic approaches for online change-point detection in network data
• Univariate mean change point detection: penalization, CUSUM and optimality
• Multiple change points detection and clustering in dynamic networks

Cites work

• A MOSUM procedure for the estimation of multiple random change points
• A survey of statistical network models
• Attribute Fusion in a Latent Process Model for Time Series of Graphs
• Change point estimation in a dynamic stochastic block model
• Change-point detection in panel data via double CUSUM statistic
• CONTINUOUS INSPECTION SCHEMES
• Dynamic network models and graphon estimation
• Emergence of Scaling in Random Networks
• Global spectral clustering in dynamic networks
• High dimensional change point estimation via sparse projection
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• Latent space models for dynamic networks
• Locality Statistics for Anomaly Detection in Time Series of Graphs
• Matrix estimation by universal singular value thresholding
• Multiple-Change-Point Detection for High Dimensional Time Series via Sparsified Binary Segmentation
• Narrowest-Over-Threshold Detection of Multiple Change Points and Change-Point-Like Features
• Network cross-validation for determining the number of communities in network data
• Random Dot Product Graph Models for Social Networks
• Rate-optimal graphon estimation
• Spectral clustering in the dynamic stochastic block model
• Statistical clustering of temporal networks through a dynamic stochastic block model
• Time-varying network models
• Topics at the Frontier of Statistics and Network Analysis
• Univariate mean change point detection: penalization, CUSUM and optimality
• Wild binary segmentation for multiple change-point detection

Cited in

(48)

• Multiple change points detection and clustering in dynamic networks
• Minimax rates in sparse, high-dimensional change point detection
• Community detection on mixture multilayer networks via regularized tensor decomposition
• The Bethe Hessian and information theoretic approaches for online change-point detection in network data
• Discussion of `Detecting possibly frequent change-points: wild binary segmentation 2 and steepest-drop model selection'
• On change-point estimation under Sobolev sparsity
• Univariate mean change point detection: penalization, CUSUM and optimality
• Detection and localization of change-points in high-dimensional network traffic data
• Changepoint Inference for Erdős–Rényi Random Graphs
• Change point estimation in a dynamic stochastic block model
• scientific article; zbMATH DE number 7626763 (Why is no real title available?)
• Exact tests for offline changepoint detection in multichannel binary and count data with application to networks
• Change point estimation in high dimensional Markov random-field models
• Covariate-assisted matrix completion with multiple structural breaks
• Time‐varying β‐model for dynamic directed networks
• Optimal multiple change-point detection for high-dimensional data
• Optimal change-point detection and localization
• Network online change point localization
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• Change-point inference in high-dimensional regression models under temporal dependence
• Monitoring Network Changes in Social Media
• Change point estimation for a stochastic heat equation
• Multilayer random dot product graphs: estimation and online change point detection
• On the impossibility of detecting a late change-point in the preferential attachment random graph model
• Aggregate spectral clustering for community detection in multi-layer popularity adjusted block model
• Multiple network embedding for anomaly detection in time series of graphs
• Change Point Detection in Dynamic Networks via Regularized Tensor Decomposition
• Estimating time-varying networks for high-dimensional time series
• Optimal Network Pairwise Comparison
• Euclidean Mirrors and Dynamics in Network Time Series
• On the tightness of graph-based statistics
• Robust change point detection for high-dimensional linear models with tolerance for outliers and heavy tails
• Bootstrapping networks with latent space structure
• Improving power by conditioning on less in post-selection inference for changepoints
• Online network change point detection with missing values and temporal dependence
• Change-Point Detection for Object-Valued Time Series
• Random interval distillation for detection of change-points in Markov chain Bernoulli networks
• On Optimal Tracking of Structural Changes in Time-Varying Networks
• Detecting a late changepoint in the preferential attachment model
• Dynamic clustering for heterophilic stochastic block models with time-varying node memberships
• Joint estimation of edge probabilities for multi-layer networks via neighborhood smoothing
• Detection and estimation of vertexwise latent position shifts across networks
• A note on the Cox-model based partial likelihood for change-point detection in a covariate
• Adaptive inference in a dynamic nonparametric -model for networks
• Euclidean mirrors and first-order changepoints in network time series
• Localising change points in piecewise polynomials of general degrees
• Optimal covariance change point localization in high dimensions
• changepoints

Describes a project that uses

Uses Software

• wbs

This page was built for publication: Optimal change point detection and localization in sparse dynamic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q97726)