# Neural Priority Queues for Graph Neural Networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 21 references that are in the map.
- First posted on arXiv 18 Jul 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets](https://mlsanity.com/paper/1503.01007/) (2015)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [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)
- [Persistent Message Passing](https://mlsanity.com/paper/2103.01043/) (2021)

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

- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Open-Book Neural Algorithmic Reasoning](https://mlsanity.com/paper/2501.00072/) (2024)
- [A Context-Enhanced Framework for Sequential Graph Reasoning](https://mlsanity.com/paper/2412.09056/) (2024)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)
- [Richer Representations for Neural Algorithmic Reasoning via Auxiliary Reconstruction](https://mlsanity.com/paper/2606.00559/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have shown considerable success in neural algorithmic reasoning. Many traditional algorithms make use of an explicit memory in the form of a data structure. However, there has been limited exploration on augmenting GNNs with external memory. In this paper, we present Neural Priority Queues, a differentiable analogue to algorithmic priority queues, for GNNs. We propose and motivate a desiderata for memory modules, and show that Neural PQs exhibit the desiderata, and reason about their use with algorithmic reasoning. This is further demonstrated by empirical results on the CLRS-30 dataset. Furthermore, we find the Neural PQs useful in capturing long-range interactions, as empirically shown on a dataset from the Long-Range Graph Benchmark.