Pointer Graph Networks

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 5× larger test inputs on dynamic graph connectivity tasks, outperforming unrestricted GNNs and Deep Sets. (1) , continuing the process. The latents may be used to provide answers, y (t) , to queries about the underlying data. We highlight masked out nodes in red, and modified pointers and latents in blue. See Appendix A for a higher-level visualisation, along with PGN's gradient flow. PGNs take a hybrid approach, assuming that the practitioner may specify part of the graph structure, and then adaptively learn a linear number of pointer edges between nodes (as in [50] for RNNs). The pointers are optimised through direct supervision on classical data structures [5] . We empirically demonstrate that PGNs further increase GNN generalisation beyond those with static graph structures [12] , without sacrificing computational cost or sparsity for this added flexibility in graph structure. Unlike prior work on algorithm learning with GNNs [54, 47, 55, 6, 40] , we consider algorithms that do not directly align to dynamic programming (making them inherently non-local [53] ) and, crucially, the optimal known algorithms rely upon pointer-based data structures. The pointer connectivity of these structures dynamically changes as the algorithm executes. We learn algorithms that operate on two distinct data structures-disjoint set unions [11] and link/cut trees [38] . We show that baseline GNNs are unable to learn the complicated, data-driven manipulations that they perform and, through PGNs, show that extending GNNs with learnable dynamic pointer links enables such modelling.