# Inferring and Encoding Graph Partitions

Speaker:
Chris Wiggins, Columbia University
Date:
Feb 3 2014 - 4:30pm
Event type:
PACM Colloquium
Room:
Fine 214
Abstract:

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.