  We provide an explicit solution of the problem of level-set percolation for
multivariate Gaussians defined in terms of weighted graph Laplacians on complex
networks. The solution requires an analysis of the heterogeneous
micro-structure of the percolation problem, i.e., a self-consistent
determination of locally varying percolation probabilities. This is achieved
using a cavity or message passing approach. It can be evaluated, both for
single large instances of locally tree-like graphs, and in the thermodynamic
limit of random graphs of finite mean degree in the configuration model class.
