Inferring and Encoding Graph Partitions

Monday, February 3, 2014 -
4:30pm to 5:30pm
Connections among disparate approaches to graph partitioning may be made by reinterpreting the problem as a special case of one of either of two more general and well-studied problems in machine learning: inferring latent variables in a generative model or estimating an (information-theoretic) optimal encoding in rate distortion theory. In either approach, setting in a more general context shows how to unite and generalize a number of approaches. As an encoding problem, we see how heuristic measures such as the normalized cut may be derived from information theoretic quantities. As an inference problem, we see how variational Bayesian methods lead naturally to an efficient and interpretable approach to identifying ``communities" in graphs as well as revealing the natural scale (or number of communities) via Bayesian approaches to complexity control.
Chris Wiggins
Columbia University
Event Location: 
Fine Hall 214