Neural algorithmic reasoning

Abstract

We present neural algorithmic reasoning-the art of building neural networks that are able to execute algorithmic computation-and provide our opinion on its transformative potential for running classical algorithms on inputs previously considered inaccessible to them.

Figure 1

The blueprint of neural algorithmic reasoning We assume that our real-world problem requires learning a mapping from natural inputs, x, to natural outputs, y—for example, fastest-time routing based on real-time traffic information. Note that natural inputs are often likely high-dimensional, noisy, and prone to changing rapidly—as is often the case in the traffic example. Further, we assume that solving our problem would benefit from applying an algorithm, A—however, A only operates over abstract inputs, $\overline{x}$. In this case, A could be Dijkstra’s algorithm for shortest paths, which operates over weighted graphs with exactly one scalar weight per node, producing the shortest path tree. First, an algorithmic reasoner is trained to imitate A, learning a function $g\left(P\left(f\left(\overline{x}\right)\right)\right)$, optimizing it to be close to ground-truth abstract outputs, $A\left(\overline{x}\right)$. P is a processor network operating in a high-dimensional latent space, which, if trained correctly, will be able to imitate the individual steps of A. f and g are encoder and decoder networks, respectively, designed to carry abstract data to and from P’s latent input space. Once trained, we can replace f and g with $\tilde{f}$ and $\tilde{g}$—encoders and decoders designed to process natural inputs into the latent space of P and decode P’s representations into natural outputs, respectively. Keeping P’s parameters fixed, we can then learn a function $\tilde{g}\left(P\left(\tilde{f}\left(x\right)\right)\right)$, allowing us an end-to-end differentiable function from x to y, without any low-dimensional bottlenecks—hence it is a great target for neural network optimization.