Recent work has shown that one can learn the structure of Gaussian
Graphical Models by imposing an L1 penalty on the precision matrix,
and then using efficient convex optimization methods to find the
penalized maximum likelihood estimate. This is similar to performing
MAP estimation with a prior that prefers sparse graphs. In this paper,
we use the stochastic block model as a prior. This prefer graphs that
are blockwise sparse, but unlike previous work, it does not require
that the blocks or groups be specified a priori.  The resulting
problem is no longer convex, but we devise an efficient variational
Bayes algorithm to solve it.  We show that our method has better test
set likelihood on two different datasets (motion capture and gene
expression) compared to independent L1, and can match the performance
of group L1 using manually created groups.