  Supervised learning problems with side information in the form of a network
arise frequently in applications in genomics, proteomics and neuroscience. For
example, in genetic applications, the network side information can accurately
capture background biological information on the intricate relations among the
relevant genes. In this paper, we initiate a study of Bayes optimal learning in
high-dimensional linear regression with network side information. To this end,
we first introduce a simple generative model (called the Reg-Graph model) which
posits a joint distribution for the supervised data and the observed network
through a common set of latent parameters. Next, we introduce an iterative
algorithm based on Approximate Message Passing (AMP) which is provably Bayes
optimal under very general conditions. In addition, we characterize the
limiting mutual information between the latent signal and the data observed,
and thus precisely quantify the statistical impact of the network side
information. Finally, supporting numerical experiments suggest that the
introduced algorithm has excellent performance in finite samples.
