# Pointer Graph Networks

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 30 of 53)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Neuro-Symbolic Artificial Intelligence: Current Trends](https://mlsanity.com/paper/2105.05330/) (2021)
- [Message passing all the way up](https://mlsanity.com/paper/2202.11097/) (2022)
- [Relational Attention: Generalizing Transformers for Graph-Structured Tasks](https://mlsanity.com/paper/2210.05062/) (2022)
- [Code Execution with Pre-trained Language Models](https://mlsanity.com/paper/2305.05383/) (2023)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [How to transfer algorithmic reasoning knowledge to learn new algorithms?](https://mlsanity.com/paper/2110.14056/) (2021)
- [Dual Algorithmic Reasoning](https://mlsanity.com/paper/2302.04496/) (2023)
- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)
- [Neural Approximation of Graph Topological Features](https://mlsanity.com/paper/2201.12032/) (2022)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [Persistent Message Passing](https://mlsanity.com/paper/2103.01043/) (2021)
- [Reasoning-Modulated Representations](https://mlsanity.com/paper/2107.08881/) (2021)
- [Boosting Graph Structure Learning with Dummy Nodes](https://mlsanity.com/paper/2206.08561/) (2022)
- [Asynchronous Algorithmic Alignment with Cocycles](https://mlsanity.com/paper/2306.15632/) (2023)
- [Algorithmic Concept-based Explainable Reasoning](https://mlsanity.com/paper/2107.07493/) (2021)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)
- [On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods](https://mlsanity.com/paper/2403.04929/) (2024)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search](https://mlsanity.com/paper/2311.03583/) (2023)
- [Learning on Large Graphs using Intersecting Communities](https://mlsanity.com/paper/2405.20724/) (2024)
- [Latent Space Representations of Neural Algorithmic Reasoners](https://mlsanity.com/paper/2307.08874/) (2023)

## Abstract (arXiv)

Graph neural networks (GNNs) are typically applied to static graphs that are assumed to be known upfront. This static input structure is often informed purely by insight of the machine learning practitioner, and might not be optimal for the actual task the GNN is solving. In absence of reliable domain expertise, one might resort to inferring the latent graph structure, which is often difficult due to the vast search space of possible graphs. Here we introduce Pointer Graph Networks (PGNs) which augment sets or graphs with additional inferred edges for improved model generalisation ability. PGNs allow each node to dynamically point to another node, followed by message passing over these pointers. The sparsity of this adaptable graph structure makes learning tractable while still being sufficiently expressive to simulate complex algorithms. Critically, the pointing mechanism is directly supervised to model long-term sequences of operations on classical data structures, incorporating useful structural inductive biases from theoretical computer science. Qualitatively, we demonstrate that PGNs can learn parallelisable variants of pointer-based data structures, namely disjoint set unions and link/cut trees. PGNs generalise out-of-distribution to 5x larger test inputs on dynamic graph connectivity tasks, outperforming unrestricted GNNs and Deep Sets.