Persistent Message Passing
This addresses a limitation in GNNs for tasks requiring historical data structure queries, such as dynamic temporal range queries, offering a novel mechanism for non-Markovian reasoning.
The paper tackles the problem of enabling graph neural networks (GNNs) to query past states of data structures in non-Markovian tasks, introducing Persistent Message Passing (PMP) which persists node representations instead of overwriting them, resulting in generalization to more than 2x larger test inputs on dynamic temporal range queries and significant performance improvements over traditional GNNs.
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.