# Persistent Message Passing

arXiv: https://arxiv.org/abs/2103.01043 · HTML: https://mlsanity.com/paper/2103.01043/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 25 references that are in the map.
- First posted on arXiv 1 Mar 2021.

## Builds on (most cited first, 18 of 18)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Learning Mesh-Based Simulation with Graph Networks](https://mlsanity.com/paper/2010.03409/) (2020)
- [Directional Message Passing for Molecular Graphs](https://mlsanity.com/paper/2003.03123/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Episodic Control](https://mlsanity.com/paper/1703.01988/) (2017)
- [How to represent part-whole hierarchies in a neural network](https://mlsanity.com/paper/2102.12627/) (2021)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Relational inductive bias for physical construction in humans and machines](https://mlsanity.com/paper/1806.01203/) (2018)
- [Neural Execution Engines: Learning to Execute Subroutines](https://mlsanity.com/paper/2006.08084/) (2020)
- [XLVIN: eXecuted Latent Value Iteration Nets](https://mlsanity.com/paper/2010.13146/) (2020)
- [Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks](https://mlsanity.com/paper/2010.13547/) (2020)

## Built on by (most cited first, 13 of 13)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [DRew: Dynamically Rewired Message Passing with Delay](https://mlsanity.com/paper/2305.08018/) (2023)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Relating Graph Neural Networks to Structural Causal Models](https://mlsanity.com/paper/2109.04173/) (2021)
- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)
- [Reasoning-Modulated Representations](https://mlsanity.com/paper/2107.08881/) (2021)
- [Asynchronous Algorithmic Alignment with Cocycles](https://mlsanity.com/paper/2306.15632/) (2023)
- [Algorithmic Concept-based Explainable Reasoning](https://mlsanity.com/paper/2107.07493/) (2021)
- [Neural Priority Queues for Graph Neural Networks](https://mlsanity.com/paper/2307.09660/) (2023)
- [Memory-Augmented Graph Neural Networks: A Brain-Inspired Review](https://mlsanity.com/paper/2209.10818/) (2022)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)

## Abstract (arXiv)

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.