Neural execution of graph algorithms

Computer program synthesis has been a major challenge since the early days of AI. More recently Machine Learning (ML) and Deep Learning (DL) have achieved great success in computer vision or natural language processing tasks. The increasing popularity of ML and DL, has resulted in a variety of probabilistic approaches attempting to address the problem of program synthesis. Tasks and approaches range from inducing latent knowledge about
the program properties from input/output (I/O) behaviour to aiding the search in existing search-based program synthesis systems and even translating natural language sentences into executable SQL queries. However, in most cases, there is no or little coverage of learning any algorithmic knowledge, such as how to perform merge sort, or how to implement a graph search.
This research proposes a review of some of the more recent advancements in using neural networks to induce latent program knowledge or synthesise a program. Based on our observations, we propose a research project of learning to synthesise algorithms not only from I/O data, but also taking into account traces of intermediate steps of the execution. If successful, the research project could open up the possibility of both synthesising more useful programs (e.g. modifying an existing algorithm for a new situation) and synthesising new algorithms (from information obtained from a brute-force solution).