Unsupervised Anomaly Detection in Dynamic Graphs via Compatibility Modeling and Boundary Learning

Abstract

Anomaly detection in dynamic graphs is essential for monitoring evolving systems such as transaction networks and online platforms. Yet existing methods remain limited in realistic edge-stream settings: snapshot-based approaches discretize continuous interactions and miss fine-grained temporal signals, while many continuous-time models rely on scarce node/edge attributes and often fail to explicitly assess whether a destination is compatible with a source’s recent context. Moreover, under extreme class imbalance and the lack of anomaly labels, unsupervised detectors frequently yield ill-defined normality criteria and ambiguous decision boundaries. We propose BAD, an unsupervised framework for anomaly detection in continuous-time dynamic graphs. BAD adopts a minimalistic design that represents nodes with learnable identity embeddings and performs pairwise compatibility modeling via cross-attention between each destination node and the source’s recent neighbors, enabling direct characterization of context-dependent deviations without requiring attributes. To obtain a principled separating boundary, BAD further integrates normalizing flows to model the distribution of normal interactions and derive likelihood-based anomaly scores. Extensive experiments on four real-world datasets demonstrate that BAD consistently performs well, highlighting its robustness under feature-scarce and label-scarce conditions.