Anomaly detection in autoregressive networks

Abstract

We study anomaly detection in temporally dependent network sequences. Methods based only on adjacency matrices, which are widely used for static networks, can miss changes in the way edges evolve. We instead represent each pair of consecutive networks by separate formation and dissolution event matrices, and embed the resulting matrix sequences using unfolded adjacency spectral embedding. Comparing these embeddings against a stationary baseline yields vertex- and network-level statistics that detect an anomalous transition and identify whether it involves formation, dissolution, or both. For autoregressive random dot product graphs, we establish uniform rowwise consistency of the transition-event embeddings and derive high-probability guarantees for vertex- and network-level detection and exact recovery of the anomalous vertex set. The theory separates a vertex's own displacement from interference caused by other vertices and from autoregressive memory. We quantify the memory left by an earlier anomaly, show that it decays geometrically after the transition mechanism returns to baseline, and give conditions under which it is negligible. A degree-corrected stochastic block model extension gives exact community recovery and provides community-reassignment, centre-shift, split, and merge anomaly statistics with high-probability detection and recovery guarantees. Simulations and applications to an international trade dataset and a primary-school contact network illustrate the performance of the proposed method, revealing a dissolution-driven trade decline followed by formation-driven recovery during COVID-19 and temporary merge-type mixing between school classes.