Spectral Anomaly Detection in Very Large Graphs: Models, Noise, and Computational Complexity
Benjamin A. Miller, Lincoln Laboratory, Computing and Analytics Group, Massachusetts Institute of Technology
Friday, Jan. 16, 2015
12:00 p.m.
Brickyard (BYENG) 210, Tempe campus [map]
Abstract
Anomaly detection in massive networks has numerous theoretical and computational challenges, especially as the behavior to be detected becomes small in comparison to the larger network. This presentation focuses on recent results in three key technical areas, specifically geared toward spectral methods for detection. We first discuss recent models for network behavior, and how their structure can be exploited for efficient computation of the principal eigenspace of the graph. In addition to the stochasticity of background activity, a graph of interest may be observed through a noisy or imperfect mechanism, which may hinder the detection process. A few simple noise models are discussed, and we demonstrate the ability to fuse multiple corrupted observations and recover detection performance. Finally, we discuss the challenges in scaling the spectral algorithms to large-scale high-performance computing systems, and present preliminary recommendations to achieve good performance with current parallel eigensolvers.
Biosketch
Benjamin A. Miller received the B.S. degree (with highest honors) and the M.S. degree in computer science in 2005 from the University of Illinois at Urbana-Champaign. In 2005, he joined Lincoln Laboratory at the Massachusetts Institute of Technology as an Associate Staff member in the Embedded Digital Systems (later Embedded and High Performance Computing) group. In this role, he developed novel algorithms for real-time linearization of radio-frequency electronics, researched methods and models for signal recovery in multi-sensor compressed sensing, and developed efficient spectral techniques for the detection of anomalies in large graphs. Since 2012, he has been a Technical Staff member of the Computing and Analytics group at Lincoln Laboratory, where his research is focused on the theoretical and computational aspects of anomaly detection in large networks and other dynamic, combinatorial structures. Mr. Miller is a member of the Institute of Electrical and Electronics Engineers (including the IEEE Signal Processing Society), the Association for Computing Machinery, and the Society for Industrial and Applied Mathematics. He holds 5 patents and is author or co-author of 32 peer-reviewed conference and journal papers on nonlinear signal processing, compressive sensing, and detection and estimation theory for graph-based data.
1) B. A. Miller, N. Arcolano, and N. T. Bliss, “Efficient anomaly detection in dynamic, attributed graphs,” in Proc. IEEE Int. Conf. Intelligence and Security Informatics, pp. 179–184, 2013.
2) B. A. Miller and N. Arcolano, “Spectral subgraph detection with corrupt observations,” in Proc. IEEE Int. Conf. Acoust., Speech and Signal Process., pp. 3449–3453, 2014.
3) M. M. Wolf and B. A. Miller, “Sparse matrix partitioning for parallel eigenanalysis of large static and dynamic graphs,” in Proc. IEEE High Performance Extreme Computing Conf., 2014.
http://www.ll.mit.edu/mission/cybersec/publications/Computing-publications-by-author/miller-b.html
