A multi-scale reconstruction method for the anomaly detection in stochastic dynamic networks

Detecting anomalous edges and/or nodes is a challenging problem for dynamic networks, due to the spatio-temporal (ST) patterns and randomness underneath the time-varying topology and node attributes. Existing methods commonly ignore randomness, and the anomaly detectors would be sensitive, especially in highly variable dynamic networks. In this paper, a new reconstruction method, the multi-scale variational graph recurrent autoencoder (M-VGRAE), is designed to detect anomalies in stochastic dynamic networks. Overall, upon the framework of Learning from Pure Normal (LPN), the M-VGRAE is trained to reconstruct the normal nodes and edges, and is used to detect the anomalies that cannot be reconstructed well by the trained M-VGRAE. To reduce sensitivity against the high variability, the reconstruction of stochastic dynamic networks is performed in a multi-scale manner. Specifically, the randomness is modeled by introducing multiple latent random variables at each node, each of which models the local randomness of attributes and connectivity within the temporal neighborhoods in a specific hop and historical interval. Then, the local randomness is approximated by employing the variational autoencoder (VAE) with a designed multi-scale ST feature extractor based on graph neural networks and recurrent neural networks. By such design, the capture of ST patterns and the modeling of randomness are jointly achieved. To show the effectiveness of the M-VGRAE in detecting anomalous edges and nodes, experiments are conducted on four real-world datasets of dynamic networks. The results demonstrate that the M-VGRAE consistently outperforms the existing baselines in terms of AUC score on anomaly detection.