SEDANSPOT: Detecting Anomalies in Edge Streams
Given a stream of edges from a time-evolving (un)weighted (un)directed graph, we consider the problem of detecting anomalous edges in near real-time using sublinear memory. We propose SEDANSPOT, a principled randomized algorithm, which exploits two tell-tale signs of anomalous edges: they tend to (i) occur as bursts of activity and (ii) connect parts of the graph which are sparsely connected. SEDANSPOT has the following desirable properties: (a) Burst resistance: It provably downsamples edges from bursty periods of network traffic, (b) Holistic scoring: It takes into account the whole (sampled) graph while scoring the anomalousness of an edge, giving diminishing importance to far-away neighbors, (c) Efficiency: It supports fast updates and scoring and hence can be efficiently maintained over stream; further, it can detect anomalous edges in sublinear space and constant time per edge. Through experiments on real-world data, we demonstrate that SEDANSPOT is 3× faster and 270% more accurate (in terms of AUC) than the state-of-the-art.
Code (1)
Tasks
Anomaly Detection in Edge StreamsSimilar Papers 제목 키워드 기반
SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via Self-Supervised Learning
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, nat…
Anomaly DetectionAnomaly Detection in Edge StreamsSelf-Supervised LearningF-FADE: Frequency Factorization for Anomaly Detection in Edge Streams
Edge streams are commonly used to capture interactions in dynamic networks, such as email, social, or computer networks. The problem of detecting anomalies or rare events in edge streams has a wide range of applications.…
Anomaly DetectionAnomaly Detection in Edge StreamsMIDAS: Microcluster-Based Detector of Anomalies in Edge Streams
Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? Existing approaches aim to…
Anomaly Detection in Edge StreamsSubset Multivariate Collective And Point Anomaly Detection
In recent years, there has been a growing interest in identifying anomalous structure within multivariate data streams. We consider the problem of detecting collective anomalies, corresponding to intervals where one or m…
Anomaly DetectionReal-Time Anomaly Detection in Edge Streams
Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? Existing approaches aim to…
Anomaly DetectionAnomaly Detection in Edge Streams