  Message passing neural networks have recently evolved into a state-of-the-art
approach to representation learning on graphs. Existing methods perform
synchronous message passing along all edges in multiple subsequent rounds and
consequently suffer from various shortcomings: Propagation schemes are
inflexible since they are restricted to $k$-hop neighborhoods and insensitive
to actual demands of information propagation. Further, long-range dependencies
cannot be modeled adequately and learned representations are based on
correlations of fixed locality. These issues prevent existing methods from
reaching their full potential in terms of prediction performance. Instead, we
consider a novel asynchronous message passing approach where information is
pushed only along the most relevant edges until convergence. Our proposed
algorithm can equivalently be formulated as a single synchronous message
passing iteration using a suitable neighborhood function, thus sharing the
advantages of existing methods while addressing their central issues. The
resulting neural network utilizes a node-adaptive receptive field derived from
meaningful sparse node neighborhoods. In addition, by learning and combining
node representations over differently sized neighborhoods, our model is able to
capture correlations on multiple scales. We further propose variants of our
base model with different inductive bias. Empirical results are provided for
semi-supervised node classification on five real-world datasets following a
rigorous evaluation protocol. We find that our models outperform competitors on
all datasets in terms of accuracy with statistical significance. In some cases,
our models additionally provide faster runtime.
