Estimating Network Statistics Through Nonparametric Denoising

• Activity Number: 395
• Type: Invited
• Date/Time: Tuesday, August 6, 2013 : 2:00 PM to 3:50 PM
• Sponsor: SSC
• Author(s): Prakash Balachandran*+ and Eric Kolaczyk and Edo Airoldi
• Companies: Boston University and Boston University and Harvard University
• Keywords: Networks ; Nonparametric ; Estimation ; Spectral Theory ; Denoising

Abstract

Consider observing an undirected network that is `noisy' in the sense that there are Type I and Type II errors in the observation of edges. Such errors can arise, for example, in the context of inferring gene regulatory networks in genomics or functional connectivity networks in neuroscience. Given a single observed network then, to what extent are summary statistics for that network representative of their analogues for the true underlying network? Can we infer such statistics more accurately by taking into account the noise in the observed network edges?

In this paper, we answer both of these questions. In particular, we develop a spectral-based methodology to `denoise' the observed network data and produce more accurate inference of the summary statistics of the true network. We characterize its performance through bounds on appropriate notions of risk using several new concentration inequalities for coefficients of orthonormal transformations of weighted Laplacians and novel bounds on spectral averages of the combinatorial Laplacian by edge density. We conclude by illustrating the practical impact of this work on synthetic and real-world data.