SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via
  Self-Supervised Learning
Jongha Lee Sunwoo Kim Kijung Shin
To detect anomalies in real-world graphs, such as social, email, and
financial networks, various approaches have been developed. While they
typically assume static input graphs, most real-world graphs grow over time,
naturally represented as edge streams. In this context, we aim to achieve three
goals: (a) instantly detecting anomalies as they occur, (b) adapting to
dynamically changing states, and (c) handling the scarcity of dynamic anomaly
labels. In this paper, we propose SLADE (Self-supervised Learning for Anomaly
Detection in Edge Streams) for rapid detection of dynamic anomalies in edge
streams, without relying on labels. SLADE detects the shifts of nodes into
abnormal states by observing deviations in their interaction patterns over
time. To this end, it trains a deep neural network to perform two
self-supervised tasks: (a) minimizing drift in node representations and (b)
generating long-term interaction patterns from short-term ones. Failure in
these tasks for a node signals its deviation from the norm. Notably, the neural
network and tasks are carefully designed so that all required operations can be
performed in constant time (w.r.t. the graph size) in response to each new edge
in the input stream. In dynamic anomaly detection across four real-world
datasets, SLADE outperforms nine competing methods, even those leveraging label
supervision.