  Long-range interactions are essential for the correct description of complex
systems in many scientific fields. The price to pay for including them in the
calculations, however, is a dramatic increase in the overall computational
costs. Recently, deep graph networks have been employed as efficient,
data-driven surrogate models for predicting properties of complex systems
represented as graphs. These models rely on a local and iterative message
passing strategy that should, in principle, capture long-range information
without explicitly modeling the corresponding interactions. In practice, most
deep graph networks cannot really model long-range dependencies due to the
intrinsic limitations of (synchronous) message passing, namely oversmoothing,
oversquashing, and underreaching. This work proposes a general framework that
learns to mitigate these limitations: within a variational inference framework,
we endow message passing architectures with the ability to freely adapt their
depth and filter messages along the way. With theoretical and empirical
arguments, we show that this simple strategy better captures long-range
interactions, by surpassing the state of the art on five node and graph
prediction datasets suited for this problem. Our approach consistently improves
the performances of the baselines tested on these tasks. We complement the
exposition with qualitative analyses and ablations to get a deeper
understanding of the framework's inner workings.
