Long-term evolutionary patterns matter: Self-supervised anomaly detection on dynamic graphs

doi:10.1016/j.knosys.2025.113049

Long-term evolutionary patterns matter: Self-supervised anomaly detection on dynamic graphs

2025-02-01

1

PRE

AI

DOI：10.1016/j.knosys.2025.113049

Original

Original request for help

Save

Abstract

En 中文

Graph anomaly detection (GAD) plays a crucial role in identifying anomalous individuals (e.g., nodes or edges) whose behaviors or patterns deviate significantly from the normal majority within a graph. Recent years have witnessed breakthrough advancements in research on static graphs. However, the GAD problem becomes more challenging when switching from static graphs to dynamic graphs due to the temporal evolution of graph structures and the scarcity of anomaly labels. Although various approaches have been proposed to address these challenges, they often struggle to capture the evolving dynamics and neglect the potential of capturing nodes' smooth long-term evolutionary patterns for self-supervised anomaly detection in dynamic graph. In this work, we empirically demonstrate that normal nodes exhibit smooth long-term evolutionary patterns, while anomalous nodes deviate significantly from their long-term histories. Motivated by this observation, we propose a multi-step histories-based contrastive learning framework, MHisCL, to detect anomalies in dynamic graphs in a self-supervised manner. Specifically, we treat a node's current state and its multi-step historical states as a positive contrastive pair, encouraging alignment between them to capture the smooth long-term evolutionary patterns of normal nodes. Consequently, MHisCL is capable of efficiently detecting anomalies by measuring the disagreement of nodes' positive pairs through a simple similarity computation. Furthermore, to better capture complex evolving dynamics, MHisCL incorporates a novel state space time encoding (SSTE), which explicitly models the temporal evolution of node representations through a linear dynamical system. We evaluate MHisCL on several dynamic graph benchmarks, and it outperforms state-of-the-art baseline by large margins.

Keywords:

Anomaly detection

Dynamic graphs

Contrastive learning

Long-term evolutionary patterns matter: Self-supervised anomaly detection on dynamic graphs

Abstract

Journal

Organization