  This paper studies asynchronous message passing (AMP), a new paradigm for
applying neural network based learning to graphs. Existing graph neural
networks use the synchronous distributed computing model and aggregate their
neighbors in each round, which causes problems such as oversmoothing and limits
their expressiveness. On the other hand, AMP is based on the asynchronous
model, where nodes react to messages of their neighbors individually. We prove
that (i) AMP can simulate synchronous GNNs and that (ii) AMP can theoretically
distinguish any pair of graphs. We experimentally validate AMP's
expressiveness. Further, we show that AMP might be better suited to propagate
messages over large distances in graphs and performs well on several graph
classification benchmarks.
