A Generalist Neural Algorithmic Learner (2022-09-22T00:00:00.000000Z)

TL;DR

A generalist learner is constructed that effectively incorporates knowledge captured by specialist models, and a series of improvements to the input representation, training regime and processor architecture over CLRS are presented, improving average single-task performance by over 20% from prior art.

Abstract

The cornerstone of neural algorithmic reasoning is the ability to solve algorithmic tasks, especially in a way that generalises out of distribution. While recent years have seen a surge in methodological improvements in this area, they mostly focused on building specialist models. Specialist models are capable of learning to neurally execute either only one algorithm or a collection of algorithms with identical control-flow backbone. Here, instead, we focus on constructing a generalist neural algorithmic learner -- a single graph neural network processor capable of learning to execute a wide range of algorithms, such as sorting, searching, dynamic programming, path-finding and geometry. We leverage the CLRS benchmark to empirically show that, much like recent successes in the domain of perception, generalist algorithmic learners can be built by"incorporating"knowledge. That is, it is possible to effectively learn algorithms in a multi-task manner, so long as we can learn to execute them well in a single-task regime. Motivated by this, we present a series of improvements to the input representation, training regime and processor architecture over CLRS, improving average single-task performance by over 20% from prior art. We then conduct a thorough ablation of multi-task learners leveraging these improvements. Our results demonstrate a generalist learner that effectively incorporates knowledge captured by specialist models.

Authors

References73 items

The CLRS Algorithmic Reasoning Benchmark

A Generalist Agent

Graph Neural Networks are Dynamic Programmers

A data-driven approach for learning to control computers

End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking

In Defense of the Unitary Scalarization for Deep Multi-Task Learning

How to transfer algorithmic reasoning knowledge to learn new algorithms?

The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization

Neural Algorithmic Reasoners are Implicit Planners

MiniHack the Planet: A Sandbox for Open-Ended Reinforcement Learning Research

Reasoning-Modulated Representations

Neural algorithmic reasoning

Size-Invariant Graph Representations for Graph Classification Extrapolations

Snowflake: Scaling GNNs to High-Dimensional Continuous Control via Parameter Freezing

Combinatorial optimization and reasoning with graph neural networks

From Local Structures to Size Generalization in Graph Neural Networks

My Body is a Cage: the Role of Morphology in Graph-Based Incompatible Control

How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

Pointer Graph Networks

The NetHack Learning Environment

Leveraging Procedural Generation to Benchmark Reinforcement Learning

Neural Execution of Graph Algorithms

What Can Neural Networks Reason About?

Structured agents for physical construction

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

Relational inductive bias for physical construction in humans and machines

Graph networks as learnable physics engines for inference and control

Learning Latent Permutations with Gumbel-Sinkhorn Networks

NerveNet: Learning Structured Policy with Graph Neural Networks

Attention is All you Need

DeepPermNet: Visual Permutation Learning

Learning Combinatorial Optimization Algorithms over Graphs

Neural Message Passing for Quantum Chemistry

Layer Normalization

End-To-End Memory Networks

Adam: A Method for Stochastic Optimization

On the difficulty of training recurrent neural networks

Understanding the difficulty of training deep feedforward neural networks

Curriculum learning

ON A ROUTING PROBLEM

Who is a Generalist?

Multitask Learning

Introduction to algorithms

A Learning Algorithm for Continually Running Fully Recurrent Neural Networks

THE TRAVELING SALESMAN PROBLEM A Guided Tour of Combinatorial Optimization

Programming pearls: algorithm design techniques

Fast Pattern Matching in Strings

On the Identification of the Convex Hull of a Finite Set of Points in the Plane

Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set

Concerning nonnegative matrices and doubly stochastic matrices

A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices

Algorithm 97: Shortest path

A note on two problems in connexion with graphs

Shortest connection networks and some generalizations

Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?

Haiku: Sonnet for JAX, 2020

JAX: composable transformations of Python+NumPy programs

Sinkhorn Networks: Using Optimal Transport Techniques to Learn Permutations

Gradient-based learning applied to document recognition

On the evolution of random graphs

The Design and Analysis of Computer Algorithms

. Algorithm 232: heapsort. Commun. ACM , 7:347–348, 1964. 6 [49] Charles AR Hoare. Quicksort

On the shortest spanning subtree of a graph and the traveling salesman problem

Execute A on the resulting input, recording intermediate states, to obtain the training trajectory

Additional experimental details

we generate the dataset in an online manner, providing the model with an infinite source of training data, to avoid overreliance on any particular fixed-size dataset. The original CLRS-30 dataset

We use an embedding size h = 128 across all experiments. We train in batches of size 32 using an Adam optimizer

• We vary the needle length, m, to avoid overreliance on specific needle/haystack boundaries in string matching. The original CLRS-30 dataset

Choose a connection probability

Generate an input, represented as a graph with n nodes, and with input node, edge and graph features sampled to match the algorithm’s spec

If the task is a string algorithm, choose a pattern length 1 ≤ m ≤ ⌊ n 2 ⌋ at random. Then use the first n − m nodes to represent the string to be searched (the haystack)

If the task is a graph algorithm, for every pair of nodes (u, v), decide whether to connect them with an edge by sampling e uv ∼ Bernoulli(p)