Breaches in network security that lead to financial frauds have touched an all-time high. To help businesses, communities and individuals deal with these breaches, anomaly detection has been used. It has emerged as an important issue in recent times with data scientists around the world are working on the subject. In a recent development, a team from the National University of Singapore discovered a new approach to anomaly detection – MIDAS.
MIDAS stands for Microcluster-Based Detector of Anomalies in Edge Streams and has been developed by PhD candidate Siddharth Bhatia and his team (Bryan Hooi, Minji Yoon, Kijung Shin, and Christos Faloutsos). They claim that MIDAS provides a new approach to anomaly detection that is capable of outlining baseline approaches in both speed and accuracy. MIDAS detects microcluster anomalies or similar suspicious edges in graphs. The primary objective of MIDAS is to detect anomalies in real-time at a much faster pace than any other existing state-of-the-art models.
The technology can help social media platforms such as Twitter and Facebook detect fake profiles that are often used for spam and phishing. It can also help investigators identify online sexual predators. That is not all – other cases of anomaly detection may include data preprocessing, credit card fraud detection, and network security, among others.
When compared to previous approaches that were used to detect anomalies in edge streams, it was found that MIDAS comes with more extensive features. This includes Microcluster Detection and Guarantee on false-positive probability. The experiment performed by the team of researchers found that MIDAS beats the baseline approaches by higher accuracy and processes the data 162 to 644 times faster.
Algorithm
The team of researchers proposed two approaches – the MIDAS and the MIDAS-R. The overview of the algorithm begins with Streaming Hypothesis Testing Approach, which works with the help of MIDAS. It provides guarantees on false positive probability using streaming data structures in a hypothesis test-based framework. The second one deals with Detection and Guarantees. The team decided on the procedure to determine if a point is abnormal or not, to probably acquire false-positives. The final one is Incorporating Relations, where MIDAS-R bridges a relationship between temporary and spatial edges.
Accuracy
The curve mentioned above gives a crystal picture of the MIDAS’s accuracy. The ROC curve for MIDAS, MIDAS-R and SedanSpot clearly shows how MIDAS is 42% to 48% accurate compared to other baselines, and also runs faster.
In the second graph, the team has plotted the average precision score vs the running time. It is seen that MIDAS is much more precise by at least 27% compared to the baseline. On the other hand, MIDAS-R’s performance is even better, with an accuracy of 29%, achieving the highest average precision scores.
Scalability
The graph depicts the scalability of MIDAS and MIDAS-R compared to other ages. As shown, the scalability of both the MIDAS, when compared to the processing time per edge along with an increase in the number of edges, is much higher. They achieve real-time anomaly detection with a processing rate of 4M edges with 0.5 seconds.
Real-World Effectiveness
To compare how effective MIDAS could be, the team chose the Twitter Security Dataset (2.6 million tweets related to security events in 2014) for anomaly detection. To compare the performance of MIDAS, it selected baselines such as RHSS and SedanSpot. However, RHSS had a low AUC measure of 0.17 on the Darpa dataset. So, the team measured MIDAS’s accuracy, running time, and real-world effectiveness by comparing against SedanSpot.
The graph shows the anomaly scores vs day, from May to September 2014. As can be seen, there are different peaks of anomalies which coincides with important events in the TwitterSecurity timeline for MIDAS. Compared to MIDAS, SedanSpot could only highlight high anomalousness scores, which led to its low AUC.
Conclusion
An anomaly detection algorithm like MIDAS can be applied by different industries. From detecting strange behaviour in machines that are interconnected to detecting fake news, MIDAS can play a crucial role by identifying abnormal patterns in real-time, and reducing and preventing losses. One can learn more about how MIDAS and MIDAS-R detect the anomalies in edge streams by reading the MIDAS repository and Siddharth Bhatia’s paper on the subject.
