Aarti Singh - Carnegie Mellon University

Starts: 4:00 pm on Thursday, September 23, 2010
Ends: 5:00 pm on Thursday, September 23, 2010
Location: MCS 149

TITLE: Identifying graph-structured network activations. ABSTRACT: The problem of identifying an activation pattern in a complex, large-scale network that is embedded in very noisy measurements is relevant to several applications, such as detecting traces of a biochemical spread by a sensor network, expression levels of genes, and anomalous activity or congestion in the Internet. Extracting such patterns is a challenging task specially if the network is large (pattern is very high-dimensional) and the noise is so excessive that it masks the activity at any single node. Most prior work considers situations in which the activation/non-activation of each node is statistically independent. In this case, the signal-to-noise ratio needs to increase as the network size increases, to accommodate for multiple hypothesis testing effects. However, typically there are statistical dependencies in the network activation process that can be leveraged to fuse the measurements of multiple nodes and enable reliable extraction of high-dimensional noisy patterns. In this talk, I will describe a method based on projecting the measurements onto an appropriate basis that is adapted to the structure of the dependency graph. We show that this procedure enables consistent recover of high-dimensional graph-structured patterns even when the signal-to-noise ratio decreases with the network size.