Change point detection in dynamic networks via regularized tensor decomposition

Dynamic network captures time-varying interactions among multiple entities at different time points, and detecting its structural change points is of central interest. This paper proposes a novel method for detecting change points in dynamic networks by fully exploiting the latent network structure. The proposed method builds upon a tensor-based embedding model, which models the time-varying network heterogeneity through an embedding matrix. A fused lasso penalty is equipped with the tensor decomposition formulation to estimate the embedding matrix and a power update algorithm is developed to tackle the resultant optimization task. The error bound of the obtained estimated embedding matrices is established without incurring the computational-statistical gap. The proposed method also produces a set of estimated change points, which, coupled with a simple screening procedure, assures asymptotic consistency in change point detection under much milder assumptions. Various numerical experiments on both synthetic and real datasets also support its advantage.