Petar Veličković: Graph Deep Learning: Monoids and time, Embracing asynchrony in (G)NNs

Speaker: Petar Veličković
Date: 18 April 2024
Title: Graph Deep Learning: Monoids and time, Embracing asynchrony in (G)NNs
Abstract:
Virtually all present graph neural network (GNN) architectures blur the distinction between the definition and invocation of the message function, forcing a node to send messages to its neighbours at every layer, synchronously. When applying GNNs to learn to execute various algorithms, however, on most steps only a handful of the nodes would have meaningful updates to send. One, hence, runs the risk of inefficiencies by sending too much irrelevant data across the graph. But more importantly, many intermediate GNN steps have to learn the identity functions, which is a non-trivial learning problem. In this talk, I will show how we can explicitly separate the concepts of node state update and message function invocation. With this separation, we obtain a mathematical formulation that allows us to reason about asynchronous computation in both algorithms and neural networks. Our analysis yields several practical implementations of synchronous scalable GNN layers that are provably invariant under various forms of asynchrony.