CSAIL Event Calendar

Signal Processing for Graphs

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.

See other events that are part of Biomedical Imaging and Analysis 2012/2013

See other events happening in December 2012