MIDAS
Anomaly Detection on Dynamic (time-evolving) Graphs in Real-time and Streaming manner. Detecting intrusions (DoS and DDoS attacks), frauds, fake rating anomalies.
view repo
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 detect individually surprising edges. In this work, we propose MIDAS, which focuses on detecting microcluster anomalies, or suddenly arriving groups of suspiciously similar edges, such as lockstep behavior, including denial of service attacks in network traffic data. We further propose MIDAS-F, to solve the problem by which anomalies are incorporated into the algorithm's internal states, creating a 'poisoning' effect which can allow future anomalies to slip through undetected. MIDAS-F introduces two modifications: 1) We modify the anomaly scoring function, aiming to reduce the 'poisoning' effect of newly arriving edges; 2) We introduce a conditional merge step, which updates the algorithm's data structures after each time tick, but only if the anomaly score is below a threshold value, also to reduce the `poisoning' effect. Experiments show that MIDAS-F has significantly higher accuracy than MIDAS. MIDAS has the following properties: (a) it detects microcluster anomalies while providing theoretical guarantees about its false positive probability; (b) it is online, thus processing each edge in constant time and constant memory, and also processes the data 130 to 929 times faster than state-of-the-art approaches; (c) it provides 41 approaches.
READ FULL TEXT
Given a stream of graph edges from a dynamic graph, how can we assign an...
read it
Given a dynamic graph stream, how can we detect the sudden appearance of...
read it
Given a stream of graph edges from a dynamic graph, how can we assign an...
read it
Given a stream of entries in a multi-aspect data setting i.e., entries h...
read it
An edge stream is a common form of presentation of dynamic networks. It ...
read it
This paper introduces a novel graph-analytic approach for detecting anom...
read it
In a cloud of m-dimensional data points, how would we spot, as well as r...
read it
Comments
There are no comments yet.