  Message passing graph neural networks (GNNs) would appear to be powerful
tools to learn distributed algorithms via gradient descent, but generate
catastrophically incorrect predictions when nodes update asynchronously during
inference. This failure under asynchrony effectively excludes these
architectures from many potential applications, such as learning local
communication policies between resource-constrained agents in, e.g., robotic
swarms or sensor networks. In this work we explore why this failure occurs in
common GNN architectures, and identify "implicitly-defined" GNNs as a class of
architectures which is provably robust to partially asynchronous "hogwild"
inference, adapting convergence guarantees from work in asynchronous and
distributed optimization, e.g., Bertsekas (1982); Niu et al. (2011). We then
propose a novel implicitly-defined GNN architecture, which we call an energy
GNN. We show that this architecture outperforms other GNNs from this class on a
variety of synthetic tasks inspired by multi-agent systems, and achieves
competitive performance on real-world datasets.
