A Time-Aware Self-Supervised Framework for Anomaly Detection in Temporal Graphs

Anomaly detection in temporal graphs aims to identify fraudulent users, malicious transactions, and other irregular behavior as interaction networks evolve. Two practical realities constrain this task. Labeled anomalies are scarce and costly to obtain, and real-world graphs grow to scales where many detection methods become computationally infeasible. To address both constraints, we propose T-ADTG, a self-supervised framework that requires no anomaly labels and scales near- linearly with the number of interactions. T-ADTG treats time as a first-class signal throughout the detection pipeline rather than as an auxiliary feature. At the interaction level, Temporal Rotary Message Encoding embeds each timestamp directly into the propagated message through a magnitude- preserving rotation, while Similarity-Aware Message Aggregation weights neighbors by how similarly their behavior has evolved. At the node level, a gated memory module accumulates each node’s behavioral trajectory across interactions. A multi-level contrastive objective then enforces consistency between a node’s present, its past, and its neighborhood, and deviations from this consistency directly yield the anomaly score in a single forward pass. We evaluate T-ADTG on five benchmark datasets against fifteen baselines, obtaining the best mean AUROC on every dataset. Despite using no labels, it matches or exceeds supervised and semi-supervised methods, and remains effective on a 330K-node graph where several static and snapshot-based baselines exhaust memory. These results show that accurate, label-free anomaly detection at scale is achievable, precisely in the fraud and abuse settings where labels are hardest to obtain.