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.