  In the quest for scalable Bayesian computational algorithms we need to
exploit the full potential of existing methodologies. In this note we point out
that message passing algorithms, which are very well developed for inference in
graphical models, appear to be largely unexplored for scalable inference in
Bayesian multilevel regression models. We show that nested multilevel
regression models with Gaussian errors lend themselves very naturally to the
combined use of belief propagation and MCMC. Specifically, the posterior
distribution of the regression parameters conditionally on covariance
hyperparameters is a high-dimensional Gaussian that can be sampled exactly (as
well as marginalized) using belief propagation at a cost that scales linearly
in the number of parameters and data. We derive an algorithm that works
efficiently even for conditionally singular Gaussian distributions, e.g., when
there are linear constraints between the parameters at different levels. We
show that allowing for such non-invertible Gaussians is critical for belief
propagation to be applicable to a large class of nested multilevel models. From
a different perspective, the methodology proposed can be seen as a
generalization of forward-backward algorithms for sampling to multilevel
regressions with tree-structure graphical models, as opposed to single-branch
trees used in classical Kalman filter contexts.
