Pointer Graph Networks
arXiv:2006.06380
Abstract
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.
arXiv commentTo appear at NeurIPS 2020 (Spotlight talk)
References in corpus (27)
- Adam: A Method for Stochastic Optimization
- Neural Message Passing for Quantum Chemistry
- Interaction Networks for Learning about Objects, Relations and Physics
- Learning to Simulate Complex Physics with Graph Networks
- Learning Deep Generative Models of Graphs
- How Powerful are Graph Neural Networks?
- Learning to Execute
- Neural Relational Inference for Interacting Systems
- Benchmarking Graph Neural Networks
- PairNorm: Tackling Oversmoothing in GNNs
- Neural GPUs Learn Algorithms
- Learning Discrete Structures for Graph Neural Networks
- Order Matters: Sequence to sequence for sets
- Differentiable Graph Module (DGM) for Graph Convolutional Networks
- Neural Episodic Control
- Neural Arithmetic Logic Units
- Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs
- Generalization and Representational Limits of Graph Neural Networks
- Graphite: Iterative Generative Modeling of Graphs
- Can Graph Neural Networks Count Substructures?
- Non-Local Graph Neural Networks
- Improving Graph Attention Networks with Large Margin-based Constraints
- Set2Graph: Learning Graphs From Sets
- Normalized Attention Without Probability Cage
- Neural Bipartite Matching
- Neural Execution Engines: Learning to Execute Subroutines
- Graph neural induction of value iteration