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.

通过梯度下降来学习分布式算法的消息传递图神经网络（GNNs），当节点在推断期间异步更新时，会产生灾难性的错误预测。本研究探讨了这种失败在常见GNN架构中的原因，并将“隐式定义”GNN作为一类架构来证明其对部分异步“hogwild”推断具有鲁棒性，从而适应了异步和分布式优化领域的收敛性保证。然后，我们提出了一种新颖的隐式定义GNN架构，称为能量GNN。我们证明了这种架构在受多智能体系统启发的各种合成任务上胜过了该类中的其他GNN，并在实际数据集上实现了竞争性能。

图神经网络疯狂去派对