Joint Ph.D. Program in Statistics & Machine Learning
Carnegie Mellon University
Anomaly Detection in Graphs and Time Series: Algorithms and Applications
With the increasing availability of web-scale graphs and high-frequency sensor data, anomaly detection in massive datasets has seen growing focus. Social networks such as Facebook and Twitter contain up to billions of users. Similarly, large-scale sensor data includes networks of traffic speed detectors spanning major cities, as well as numerous types of industrial, weather and environmental sensors. Given large graphs or sensor data, how can we automatically monitor this data, and flag users or events which are anomalous or of interest?
This thesis focuses on these problems, by developing scalable, principled algorithms that detect unusual behavior or events using connectivity and temporal information. For static graphs, we study how to distinguish normal from abnormally dense subgraphs, and also propose an adversarially robust detection approach. For sensor data, we propose approximation or streaming algorithms for sensor selection, change detection, and anomaly detection, for identifying both the time and location of events on the graph.
Christos Faloutsos (Chair)
Vipin Kumar (University of Minnesota)