Anomaly Detection with MIDAS

Anomaly detection in graphs is a severe problem finding strange behaviors in systems, like intrusion detection, fake ratings, and financial fraud. To minimize the effect of malicious activities as soon as possible, we need to detect anomalies in real-time to identify an incoming edge and decide if it is anomalous or not. Existing methods, process edge streams in an online manner and can miss a large amount of suspicious activity; in contrast to this, MIDAS detects microclusters anomalies in edge streams using constant time and memory, providing theoretical bounds on the false positive probability. Main MIDAS contributions are: 1. Streaming Microcluster Detection, novel streaming approach for detecting microcluster anomalies; 2. Theoretical Guarantee, on the false positive probability of MIDAS; 3. Effectiveness, MIDAS' experimental results show that MIDAS outperforms the baseline approaches by 42%-48% accuracy and processes the data 162–644 times faster. If we compare MIDAS to previous approaches that detect anomalies in edge streams, we see that MIDAS includes more features like Microcluster Detection and Guarantee on false-positive probability, keeping the other elements of other approaches.