Neural algorithmic reasoning

An article in The Gradient examines neural algorithmic reasoning: research aimed at capturing classical computation, such as shortest path-finding, sorting and dynamic programming, with deep neural networks. The author writes that classical algorithms are provably correct, generalise strongly, and are interpretable and compositional, while deep networks often lack guarantees, fail on out-of-distribution inputs and act as black boxes.

The article traces the field to the question of whether neural networks can learn to execute classical algorithms, studied by the author starting in 2019. It cites the paper "What Can Neural Networks Reason About?" from an MIT team, whose main theorem states that better algorithmic alignment leads to better generalisation, framed in terms of sample complexity. The article describes how a graph neural network can be decomposed to follow Bellman-Ford's data flow: distance variables correspond to node features, adding edge distance corresponds to the message function, and choosing the optimal neighbour corresponds to permutation-invariant aggregation.

The author's concurrent paper, Neural Execution of Graph Algorithms, reported an empirical analysis and found that algorithmic alignment does not permit recklessness, since GNNs can overfit and sidestep the procedure. Three measures are described: an encode-process-decode paradigm with a single shared processor iterated for a variable number of steps; max aggregation for local optimisation in path-finding; and step-wise supervision using algorithmic invariants. The article says the changes allowed generalising to 5x larger inputs at test time.

Beyond execution, the article describes applications. In work that reached the cover of Nature, GNNs were trained on mathematical datasets and gradient saliency methods flagged salient inputs for mathematicians, contributing to knot theory and representation theory. With ETH Zürich collaborators, neural algorithmic reasoning was applied to network configuration synthesis, where the article reports over 490x speedup over the prior state of the art for certain configurations, with occasional inaccuracies and average constraint satisfaction consistently above 90% on evaluated distributions.

The article also notes prior architectures such as the neural Turing machine and differentiable neural computer, which it says are now virtually unused in practice, and reports a reviewer comment questioning whether learning-to-execute research should exist, while noting that a target algorithm will execute itself at least as well.