nips nips2006 nips2006-98 nips2006-98-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael G. Rabbat, Mário Figueiredo, Robert Nowak
Abstract: We consider the problem of inferring the structure of a network from cooccurrence data: observations that indicate which nodes occur in a signaling pathway but do not directly reveal node order within the pathway. This problem is motivated by network inference problems arising in computational biology and communication systems, in which it is difficult or impossible to obtain precise time ordering information. Without order information, every permutation of the activated nodes leads to a different feasible solution, resulting in combinatorial explosion of the feasible set. However, physical principles underlying most networked systems suggest that not all feasible solutions are equally likely. Intuitively, nodes that co-occur more frequently are probably more closely connected. Building on this intuition, we model path co-occurrences as randomly shuffled samples of a random walk on the network. We derive a computationally efficient network inference algorithm and, via novel concentration inequalities for importance sampling estimators, prove that a polynomial complexity Monte Carlo version of the algorithm converges with high probability. 1
[1] E. Klipp, R. Herwig, A. Kowald, C. Wierling, and H. Lehrach. Systems Biology in Practice: Concepts, Implementation and Application. John Wiley & Sons, 2005.
[2] D. Zhu, A. O. Hero, H. Cheng, R. Khanna, and A. Swaroop. Network constrained clustering for gene microarray data. Bioinformatics, 21(21):4014–4020, 2005.
[3] Y. Liu and H. Zhao. A computational approach for ordering signal transduction pathway components from genomics and proteomics data. BMC Bioinformatics, 5(158), October 2004.
[4] M. G. Rabbat, J. R. Treichler, S. L. Wood, and M. G. Larimore. Understanding the topology of a telephone network via internally-sensed network tomography. In Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005.
[5] O. Sporns and G. Tononi. Classes of network connectivity and dynamics. Complexity, 7(1):28–38, 2002.
[6] O. Sporns, D. R. Chialvo, M. Kaiser, and C. C. Hilgetag. Organization, development and function of complex brain networks. Trends in Cognitive Science, 8(9), 2004.
[7] M.G. Rabbat, M.A.T. Figueiredo, and R.D. Nowak. Supplement to inferring network structure from co-occurrences. Technical report, University of Wisconsin-Madison, October 2006.
[8] J. Kubica, A. Moore, D. Cohn, and J. Schneider. cGraph: A fast graph-based method for link analysis and queries. In Proc. IJCAI Text-Mining and Link-Analysis Workshop, Acapulco, Mexico, August 2003.
[9] D. Heckerman, D. Geiger, and D. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20:197–243, 1995.
[10] N. Friedman and D. Koller. Being Bayesian about Bayesian network structure: A Bayesian approach to structure discovery in Bayesian networks. Machine Learning, 50(1–2):95–125, 2003.
[11] R. A. Boyles. On the convergence of the EM algorithm. J. Royal Statistical Society B, 45(1):47–50, 1983.
[12] C. F. J. Wu. On the convergence properties of the EM algorithm. Ann. of Statistics, 11(1):95–103, 1983.
[13] C. Robert and G. Casella. Monte Carlo Statistical Methods. Springer Verlag, New York, 1999.
[14] B. S. Caffo, W. Jank, and G. L. Jones. Ascent-based Monte Carlo EM. J. Royal Statistical Society B, 67(2):235–252, 2005.