MIDAS
Microcluster-Based Detector of Anomalies in Edge Streams
Table of Contents
- Features
- Use Cases
- Getting Started
- Demo
- Command-Line Options
- Input File Format
- Datasets
- MIDAS in other languages
- Blog Posts and Tutorials
- Citation
Features
- Finds Anomalies in Dynamic/Time-Evolving Graphs
- Detects Microcluster Anomalies (suddenly arriving groups of suspiciously similar edges e.g. DoS attack)
- Theoretical Guarantees on False Positive Probability
- Constant Memory (independent of graph size)
- Constant Update Time (real-time anomaly detection to minimize harm)
- Up to 48% more accurate and 644 times faster than the state of the art approaches
For more details, please read the paper - MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams. Siddharth Bhatia, Bryan Hooi, Minji Yoon, Kijung Shin, Christos Faloutsos. AAAI 2020.
Use Cases
- Intrusion Detection
- Fake Ratings
- Financial Fraud
Getting started
- Run
make
to compile code and create the executable. - Run
./midas -i
followed by the input file path and name.
Demo
- Run
./demo.sh
to compile the code and run it on an example dataset.
Command-Line Options
-h --help
: produce help message-i --input
: input file name-o --output
: output file name (default: scores.txt)-r --rows
: Number of Hash Functions (default: 2)-b --buckets
: Number of Buckets (default: 769)-a --alpha
: Temporal Decay Factor (default: 0.6)--norelations
: Run MIDAS instead of MIDAS-R--undirected
: Treat graph as undirected instead of directed
Input File Format
MIDAS expects the input edge stream to be stored in a single file containing the following three columns in order:
source (int)
: source ID of the edgedestination (int)
: destination ID of the edgetime (int)
: timestamp of the edge
Thus, each line represents an edge. Edges should be sorted in non-decreasing order of their timestamps and the column delimiter should be ,
Datasets
MIDAS in other languages
- Rust and Python by Scott Steele
- Ruby by Andrew Kane
Blog Posts and Tutorials
- Towards Data Science: Controlling Fake News using Graphs and Statistics
- Towards Data Science: Anomaly detection in dynamic graphs using MIDAS
- Towards AI: Anomaly Detection with MIDAS
Citation
If you use this code for your research, please consider citing our paper.
@article{bhatia2019midas,
title={MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams},
author={Bhatia, Siddharth and Hooi, Bryan and Yoon, Minji and Shin, Kijung and Faloutsos, Christos},
journal={arXiv preprint arXiv:1911.04464},
year={2019}
}
Webpage https://www.comp.nus.edu.sg/~sbhatia/ · Email siddharth@comp.nus.edu.sg · Twitter @siddharthb_