[talks] 4:30pm Tue Apr 29 talk by Robert Nowak on network inference

Jennifer Rexford jrex at CS.Princeton.EDU
Fri Apr 25 11:55:28 EDT 2008

*Speaker:      *Robert Nowak, Professor of Engineering at the University 
of Wisconsin-Madison

*Date:           *Tuesday, April 29th

*Time:          *4:30pm

*Room:         *B205 ~ Equad

*Title:           *Network Inference from Co-Occurrences


*Abstract:      *The discovery of networks is a fundamental problem 
arising in numerous fields of science and engineering, including 
communication systems, biology, sociology, and neuroscience. 
Unfortunately, it is often difficult to obtain data that directly reveal 
network structure, and so one must infer a network from incomplete data. 
This paper considers inferring network structure and transmission 
pathways from ``co-occurrence'' data; observations that identify which 
network components (e.g., routers, proteins) carry each transmission but 
do not indicate the order in which they handle the transmission. Without 
order information, the number of networks that are consistent with the 
data grows exponentially with the size of the network. Yet, the basic 
engineering/ evolutionary principles underlying most networks strongly 
suggest that not all data-consistent networks are equally likely. In 
particular, network components that co-occur in many observations are 
probably closely connected. With this in mind, we model the 
co-occurrence observations as independent realizations of a random walk 
on the network graph, subjected to random permutations which account for 
the lack of order information. The network can be estimated using this 
model and the Maximum Likelihood (ML) criterion. The computational 
complexity of direct ML estimation is combinatorial in the size of the 
network, and so we derive a more efficient approach using an 
Expectation-Maximization (EM) algorithm. The EM algorithm complexity is 
combinatorial in the length of the transmission pathways, rather than 
the size of the entire network. This is a significant improvement, but 
the computational cost of the EM algorithm is still prohibitive for 
large networks. For large-scale network inference, we propose a 
polynomial-time Monte Carlo version of the EM algorithm which is 
guaranteed to converge with high probability. Applications arising in 
telecommunications, natural language processing, and systems biology 
will be discussed.

* *

*Bio:    *Robert Nowak received the B.S. (with highest distinction), 
M.S., and Ph.D. degrees in electrical engineering from the University of 
Wisconsin-Madison in 1990, 1992, and 1995, respectively. He was a 
Postdoctoral Fellow at Rice University in 1995-1996, an Assistant 
Professor at Michigan State University from 1996-1999, held Assistant 
and Associate Professor positions at Rice University from 1999-2003, and 
was a Visiting Professor at INRIA in 2001. Dr. Nowak is now the 
McFarland-Bascom Professor of Engineering at the University of 
Wisconsin-Madison. He has served as an Associate Editor for the IEEE 
Transactions on Image Processing, and is currently an Associate Editor 
for the ACM Transactions on Sensor Networks and the Secretary of the 
SIAM Activity Group on Imaging Science. He has also served as a 
Technical Program Chair for the IEEE Statistical Signal Processing 
Workshop and the IEEE/ACM International Symposium on Information 
Processing in Sensor Networks. Dr. Nowak received the General Electric 
Genius of Invention Award in 1993, the National Science Foundation 
CAREER Award in 1997, the Army Research Office Young Investigator 
Program Award in 1999, the Office of Naval Research Young Investigator 
Program Award in 2000, and IEEE Signal Processing Society Young Author 
Best Paper Award in 2000. His research interests include statistical 
signal processing, machine learning, imaging and network science, and 
applications in communications, bio/medical imaging, and systems biology.

More information about the talks mailing list