Timezone: »

 
Poster
How to transfer algorithmic reasoning knowledge to learn new algorithms?
Louis-Pascal Xhonneux · Andreea-Ioana Deac · Petar Veličković · Jian Tang

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »

Learning to execute algorithms is a fundamental problem that has been widely studied. Prior work (Veličković et al., 2019) has shown that to enable systematic generalisation on graph algorithms it is critical to have access to the intermediate steps of the program/algorithm. In many reasoning tasks, where algorithmic-style reasoning is important, we only have access to the input and output examples. Thus, inspired by the success of pre-training on similar tasks or data in Natural Language Processing (NLP) and Computer vision, we set out to study how we can transfer algorithmic reasoning knowledge. Specifically, we investigate how we can use algorithms for which we have access to the execution trace to learn to solve similar tasks for which we do not. We investigate two major classes of graph algorithms, parallel algorithms such as breadth-first search and Bellman-Ford and sequential greedy algorithms such as Prims and Dijkstra. Due to the fundamental differences between algorithmic reasoning knowledge and feature extractors such as used in Computer vision or NLP, we hypothesis that standard transfer techniques will not be sufficient to achieve systematic generalisation. To investigate this empirically we create a dataset including 9 algorithms and 3 different graph types. We validate this empirically and show how instead multi-task learning can be used to achieve the transfer of algorithmic reasoning knowledge.

Keywords: Deep Learning · Vision · Graph Learning · Language

Author Information

Louis-Pascal Xhonneux (Montreal Institute for Learning Algorithms, University of Montreal, University of Montreal)
Andreea-Ioana Deac (Mila)
Petar Veličković (DeepMind / University of Cambridge)
Jian Tang (Mila)

More from the Same Authors