Signal Processing for Graphs

Speaker: Ben Miller
Speaker Affiliation: MIT Lincoln Laboratory
Host: Polina Golland
Host Affiliation: MIT CSAIL

Date: 12-11-2012
Time: 4:00 PM - 5:30 PM
Location: 32D-463 (Star)

In numerous applications, detection of a small subset of nodes in a network is a problem of significant interest. While detection theory provides a framework that enables analysis of the detectability of small anomalies in large networks, the combinatorial nature of graphs—the common mathematical object for network representation—complicates the application of detection theory, requiring NP-hard problems to be solved for optimal detection. This presentation outlines Lincoln Laboratory’s Signal Processing for Graphs effort, which aims to create a  computationally tractable framework for anomalous subgraph detection. The framework uses a regression-based residuals analysis, leveraging tools from community detection for the problem of detecting small anomalies. Issues of parameter estimation and fitting the data  to a given model are discussed, and a processing chain for detection in graph data is presented. The processing chain uses several detection statistics, which improve in detection performance as the increase in computational  complexity. Temporal dynamics are also incorporated into  the chain, enabling detection that would not be possible by considering a static graph, as we demonstrate on both simulated and application data.