Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Quaid Morris, Brendan J. Frey
This paper addresses the problem of untangling hidden graphs from a set of noisy detections of undirected edges. We present a model of the generation of the observed graph that includes degree-based structure priors on the hidden graphs. Exact inference in the model is intractable; we present an e–cient approximate inference algo- rithm to compute edge appearance posteriors. We evaluate our model and algorithm on a biological graph inference problem.
1
Introduction and motivation
The inference of hidden graphs from noisy edge appearance data is an important problem with obvious practical application. For example, biologists are currently building networks of all the physical protein-protein interactions (PPI) that occur in particular organisms. The importance of this enterprise is commensurate with its scale: a completed network would be as valuable as a completed genome sequence, and because each organism contains thousands of difierent types of proteins, there are millions of possible types of interactions. However, scalable experimental meth- ods for detecting interactions are noisy, generating many false detections. Motivated by this application, we formulate the general problem of inferring hidden graphs as probabilistic inference in a graphical model, and we introduce an e–cient algorithm that approximates the posterior probability that an edge is present.
In our model, a set of hidden, constituent graphs are combined to generate the ob- served graph. Each hidden graph is independently sampled from a prior on graph structure. The combination mechanism acts independently on each edge but can be either stochastic or deterministic. Figure 1 shows an example of our generative model. Typically one of the hidden graphs represents the graph of interest (the true graph), the others represent difierent types of observation noise. Independent edge noise may also be added by the combination mechanism. We use probabilistic in- ference to compute a likely decomposition of the observed graph into its constituent parts. This process is deemed \untangling". We use the term \denoising" to refer to the special case where the edge noise is independent. In denoising there is a single hidden graph, the true graph, and all edge noise in the observed graph is due