Change Point Detection in Dynamic Networks via Regularized Tensor Decomposition

AbstractDynamic 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.Keywords: Fused lassolatent factor modelmulti-layer networknetwork embeddingtensor power methodDisclaimerAs a service to authors and researchers we are providing this version of an accepted manuscript (AM). Copyediting, typesetting, and review of the resulting proofs will be undertaken on this manuscript before final publication of the Version of Record (VoR). During production and pre-press, errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal relate to these versions also. AcknowledgmentThe authors are grateful to the associate editor and two anonymous referees, whose insightful comments and constructive suggestions have led to significant improvements in the article. JZ's research is supported in part by" USTC Research Funds of the Double First-Class Initiative" YD2040002020, YS's research is supported in part by NSFC Grant 12171479, and JW's research is supported in part by HK RGC Grants GRF-11304520, GRF-11301521, GRF-11311022, and CUHK Startup Grant 4937091. The authors report there are no competing interests to declare.