  Graph neural networks (GNNs) based on message passing between neighboring
nodes are known to be insufficient for capturing long-range interactions in
graphs. In this project we study hierarchical message passing models that
leverage a multi-resolution representation of a given graph. This facilitates
learning of features that span large receptive fields without loss of local
information, an aspect not studied in preceding work on hierarchical GNNs. We
introduce Hierarchical Graph Net (HGNet), which for any two connected nodes
guarantees existence of message-passing paths of at most logarithmic length
w.r.t. the input graph size. Yet, under mild assumptions, its internal
hierarchy maintains asymptotic size equivalent to that of the input graph. We
observe that our HGNet outperforms conventional stacking of GCN layers
particularly in molecular property prediction benchmarks. Finally, we propose
two benchmarking tasks designed to elucidate capability of GNNs to leverage
long-range interactions in graphs.
