Persistent Message Passing
arXiv:2103.01043
Abstract
Graph neural networks (GNNs) are a powerful inductive bias for modelling algorithmic reasoning procedures and data structures. Their prowess was mainly demonstrated on tasks featuring Markovian dynamics, where querying any associated data structure depends only on its latest state. For many tasks of interest, however, it may be highly beneficial to support efficient data structure queries dependent on previous states. This requires tracking the data structure's evolution through time, placing significant pressure on the GNN's latent representations. We introduce Persistent Message Passing (PMP), a mechanism which endows GNNs with capability of querying past state by explicitly persisting it: rather than overwriting node representations, it creates new nodes whenever required. PMP generalises out-of-distribution to more than 2x larger test inputs on dynamic temporal range queries, significantly outperforming GNNs which overwrite states.
arXiv comment7 pages, 2 figures. Published as a workshop paper at ICLR 2021 SimDL Workshop. Accepted at the ICLR 2021 Workshop on Geometrical and Topological Representation Learning
References in corpus (11)
- Adam: A Method for Stochastic Optimization
- Neural Message Passing for Quantum Chemistry
- How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
- Temporal Graph Networks for Deep Learning on Dynamic Graphs
- Neural Episodic Control
- Solving Mixed Integer Programs Using Neural Networks
- Pointer Graph Networks
- Neural Shuffle-Exchange Networks -- Sequence Processing in O(n log n) Time
- Neural Execution Engines: Learning to Execute Subroutines
- XLVIN: eXecuted Latent Value Iteration Nets
- Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks