  Anomaly detection in dynamic graphs presents a significant challenge due to
the temporal evolution of graph structures and attributes. The conventional
approaches that tackle this problem typically employ an unsupervised learning
framework, capturing normality patterns with exclusive normal data during
training and identifying deviations as anomalies during testing. However, these
methods face critical drawbacks: they either only depend on proxy tasks for
general representation without directly pinpointing normal patterns, or they
neglect to differentiate between spatial and temporal normality patterns,
leading to diminished efficacy in anomaly detection. To address these
challenges, we introduce a novel Spatial-Temporal memories-enhanced graph
autoencoder (STRIPE). Initially, STRIPE employs Graph Neural Networks (GNNs)
and gated temporal convolution layers to extract spatial features and temporal
features, respectively. Then STRIPE incorporates separate spatial and temporal
memory networks, which capture and store prototypes of normal patterns, thereby
preserving the uniqueness of spatial and temporal normality. After that,
through a mutual attention mechanism, these stored patterns are then retrieved
and integrated with encoded graph embeddings. Finally, the integrated features
are fed into the decoder to reconstruct the graph streams which serve as the
proxy task for anomaly detection. This comprehensive approach not only
minimizes reconstruction errors but also refines the model by emphasizing the
compactness and distinctiveness of the embeddings in relation to the nearest
memory prototypes. Through extensive testing, STRIPE has demonstrated a
superior capability to discern anomalies by effectively leveraging the distinct
spatial and temporal dynamics of dynamic graphs, significantly outperforming
existing methodologies, with an average improvement of 15.39% on AUC values.
