How to transfer algorithmic reasoning knowledge to learn new algorithms?
Year: 2021

Abstract:
Learning to execute algorithms is a fundamental problem that has been widely studied. Prior work [1] 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 Prim and Dijkstra. Due to the fundamental differences between algorithmic reasoning knowledge and feature extractors such as used in Computer Vision or NLP, we hypothesise 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.

heading: 1 Introduction
text: Transfer learning [2] has been responsible for significant successes in multiple areas of machine learning, including Natural Language Processing (NLP) [3, 4] and Computer Vision (CV) [5]. Pretraining and reusing the learned weights, by freezing them as feature extractors, or fine-tuning from them as an initialisation, are common approaches to transfer in these domains. This has enabled successful learning on problems where data is limited in some form.
Algorithmic reasoning on graphs [1, 6] is a fundamental problem that has been studied under the assumption that we have access to the execution traces of the algorithms we want to learn. In practice, such as many real world reasoning tasks, this may not be true. Due to the limited data, we look to transfer learning to enable us to solve algorithmic tasks without intermediate steps. Specifically, we
∗Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021)
investigate how to transfer knowledge between similar graph algorithms in the setting where we have access to the execution traces for some (e.g. PRIM [7, 8]), but not others (e.g. DIJKSTRA [9]). This has not been explored before, but is important as many reasoning related fields care deeply about systematic generalisation, while only having input-output pairs to learn from. One such example is knowledge graph link prediction. There exists a reasoning process that can answer the question: what is the tail entity given the head entity and the relation. However, we do not have access to its execution trace, i.e. the step-by-step deductions of the reasoning process, but we do have input-output pair examples. We envision that the set-up studied and the direction proposed in this paper will help to learn neural networks that can solve reasoning-style problems by using other reasoning knowledge as an inductive bias. A slightly different, but related application may be when the data the graph algorithm needs to operate on is encoded in a high-level space. This is a scenario encountered in reinforcement learning and concurrent work Deac et al. [10] has already started investigating the process of pre-training an encoder with graph algorithms.
Veličković et al. [1] successfully trained graph neural networks (GNNs) [11, 12, 13, 14] to execute graph algorithms. Two key ingredients were access to the intermediate steps of the algorithm and algorithmic alignment [15]. Algorithmic alignment [15] refers to the concept of a computation structure—in our case neural networks—and the structure of an algorithm ‘aligning’—in this paper graph algorithms. ‘Alignment’ means there exists a mapping between substructures of the computation architecture and simple substeps of the algorithm, where the substructures can ‘easily’ compute the corresponding substep they are mapped to—for some definition of easy, usually linear.
Extending this work, we enable solving tasks without access to the intermediate steps using other similar algorithms as an inductive bias. To do this we add several new algorithms. Further, since the algorithms studied in [1] were all expressible with only linear components in the GNN, we extend their architecture with a more expressive encoder to enable algorithmic alignment with more tasks.
One assumption we make is that the algorithms are similar (e.g. both PRIM and DIJKSTRA greedily select nodes from a priority queue). This shared algorithmic knowledge should serve as an inductive bias to enable a neural network to systematically generalise, even when learning only on input-output pairs. We hypothesise that due to differences between feature extraction and algorithmic reasoning, successful approaches to transfer as used in CV and NLP will provide only minimal improvements when transferring from one base algorithm to a target algorithm. While features across images may be similar, the features of algorithms differs (e.g. shortest distance in DIJKSTRA and lightest edge to the tree in PRIM), but are processed in a conceptually similar manner. Our intuition is that this conceptual relationship may not yield weights that are near each other in the weight space, thus making transfer difficult. We instead propose to use the base algorithms as inductive biases by training them with the intermediate steps along side training the target algorithm, for which we do not provide intermediate supervision. Our second hypothesis is that this will help systematic generalisation. We validate both hypotheses—transfer does not help, while multi-task learning helps—empirically.
The contributions of this paper are:
1. presenting a new benchmark for transferring algorithmic reasoning knowledge on graphs; 2. sampling the best trajectory to stabilise training when no execution traces are available; 3. show that standard transfer techniques fail to significantly improve systematic generalisation; 4. demonstrate how systematic generalisation can instead be improved on algorithmic tasks
with multi-task learning.

heading: 2 Related Work
text: Neural Execution: Many papers have studied how to execute algorithms before [16, 17, 18, 19, 20]. With the rise of graph representation learning [21, 22, 23] and graph neural networks [11, 12, 13, 14], recent work has looked at executing graph algorithms [1, 6]. This line of work assumes access to the intermediate steps of the algorithm. Further, people have looked at teaching transformers to learn explicitly denoted subroutines and then learn how to combine them [24]. The key difference between our work and prior work is that we look at the setting of learning graph algorithms where we do not have access to the execution trace and we do not denote subroutines explicitly. Instead we propose to use similar algorithms as an inductive bias and look at how to enable this transfer of algorithmic knowledge.
Transfer learning: Transfer learning was originally proposed in the 1970s [25, 26]. Today, it is a common tool in NLP and Computer Vision to use pre-trained models and fine-tune them on the target task [2, 3, 5]. This is helpful when the target task is similar and the available data is limited in some way. Our work differs in two ways; firstly, we focus on algorithmic reasoning knowledge, which we hypothesis will require different techniques than reusing weights. Secondly, the data on the target task is partially missing specifically the execution trace of the algorithm is missing.

heading: 3 Background
text: This section gives background on the algorithms and graphs used for the experiments. To be precise we consider a graph to be a tuple G = (V,E) with a set of vertices V and a set of edges E ⊆ V ×V 2. This section explains the algorithms studied in this paper in more detail. After that, we give a brief introduction into graph neural networks, the standard architecture paradigm for graph inputs.

heading: 3.1 Algorithms
text: We broadly study two classes of algorithmic reasoning: parallel and sequential reasoning. Specifically, the parallel algorithms (shown in Algorithm 1) studied in this paper exchange messages with their neighbours until an equilibrium is reached. Sequential algorithms, presented in Algorithm 2, greedily remove elements from a priority queue and updating the neighbouring nodes’ keys.
Algorithm 1 Parallel Input: graph G, weights w, source index i initialise_nodes(G.vertices, i) repeat
for (u, v) ∈ G.edges() do relax_edge(u, v, w)
end for until none of the nodes change
Algorithm 2 Sequential Input: graph G, edge weights w, source node index i initialise_nodes(G.vertices, i) Q← PriorityQueue(G.vertices) repeat
u← Q.pop_min() for v ∈ G.neighbours(u) do
relax_edge(u, v, w) end for
until Q is empty
Different algorithms will implement their own relax_edge and initialise_nodes functions, however, the overall framework stays the same and can be learned by our GNN architecture (§ 4.1). For the sequential algorithms each node has a state feature indicating whether it has been removed from the priority queue, a key feature for the priority queue, and a pointer to the predecessor node.
We study the following algorithms: PARALLEL
1. BREADTH-FIRST SEARCH (BFS) 2. BELLMAN-FORD 3. WIDEST PATH (PARALLEL) 4. MOST RELIABLE-PATH (PARALLEL) SEQUENTIAL 1. PRIMS 2. DIJKSTRA 3. DEPTH-FIRST SEARCH (DFS) 4. WIDEST PATH (PARALLEL) 5. MOST RELIABLE-PATH (PARALLEL)
We give the pseudo-code for all algorithms in the supplementary. Note that the relax_edge function is increasingly difficult to learn for the neural network as you go down the list: PRIMS uses the edge weight as a key, thus the relax_edge function is the identity, for DIJKSTRA and DEPTH-FIRST SEARCH addition is necessary to compute the edge update, for WIDEST-PATH we need to take a maximum, which with a ReLU activation can still be done exactly, and for MOST RELIABLE-PATH the neural network needs to learn to approximate multiplication.3
2Throughout the paper we use graphs that are simple with weights. 3We note that the tasks are all linear time in the size of the graph. More challenging problems such as NP-hard problems are primarily more difficult because of their increased run-time and hence longer sequences allowing

heading: 3.2 Graph Neural Networks
text: A general framework to describe several graph neural network architecture is the message passing framework introduced by Gilmer et al. [13]. Such graph neural networks (GNNs) consist of three parts: a message function M , an update function U , and an aggregator ⊕ . M and U are arbitrary neural networks. The high-level idea is
1. each node computes a message for its neighbours using M ; 2. then each node aggregates the received messages using ⊕ ;
3. finally, each node updates its embedding using U .
The message function in this paper takes as input the sending and receiving nodes’ representation as well as an encoding of the edge feature along which the message is sent. The aggregator chosen is the max aggregator applied element-wise as it was determined to work best by Veličković et al. [1] and provides algorithmic alignment [15] between the architecture and the tasks. The update function takes as input the node’s previous embedding and aggregated messages.

heading: 3.3 Problem definition
text: We study learning graph algorithms that take in a graph G, a weight function w : E → R that assigns a weight to each edge in the graph, and node features X : V → Rk. Algorithms compute an output Y : V → F k and a predecessor P : V → V at each time step. This encompasses a large class of graph algorithms solving tasks such as reachability or shortest-path.
For instance, for a sequential algorithm the ith node’s features Xt[i] would be the key value and the state variable. Given Xt, the graph G, and the edge weights, the graph algorithm at each iteration returns the node features Yt and the predecessor for each Pt (pred variable in pseudocode § 3.1). YT and PT at the final step are considered the output of the algorithm. The intermediate steps refers to Xt, Yt, Pt ∀t ∈ {1, . . . , T − 1} after each iteration.

heading: 4 Methods
text: In this section, we first briefly present two architectures we will use for training and then discuss how existing algorithmic knowledge can be used to solve tasks when no execution trace is given.

heading: 4.1 Architecture
text: As our starting point we choose the encoder-processor-decoder architecture proposed in Veličković et al. [1]. The high-level idea is that the network encodes the current node state into a hidden embedding, on which a graph neural network unit, called the processor, is applied using the graph structure. The results are then decoded by the decoder, which does the prediction of the node features at the next time step (§ 3.1). The point of this architecture is to allow several algorithms to use the same processor architecture. A more detailed summary of the architecture is given below:

heading: 4.1.1 NeuralExecutor
text: The NeuralExecutor (NE) [1] uses an encoder-processor-decoder architecture. Let X ∈ Rn×k be node states, where n, k are the number of nodes and features, respectively. Each edge (u, v) has a weight w(u, v) ∈ R. The architecture keeps a hidden state for each node H ∈ Rn×l with l features, which is initialised to all zeros. The encoder E consists of a linear layer and computes a hidden embedding E(Xi, Hi) = Zi, where i indicates the ith step in the computation. The processor P is message passing neural network (MPNN) with a max aggregator with linear message and update functions. The processor computes the new hidden state for each node P(Hi, A,w) = Hi+1. Then, we have the decoder D(Zi, Hi+1) = Yi+1 and predecessor predictor S(Zi, Hi+1) = Si. Finally, a termination network σ(T (Hi+1)) decides whether we should terminate or not.
for more accumulation of errors. As long as we have algorithmic alignment [15] between the architecture and the algorithm in question there is no additional challenge to NP-hard problems except the length of their sequence and hence more opportunities to introduce errors and propagate them.
We make minor changes to allow for better algorithmic alignment: we remove the ReLU activations from the processor and replace the termination layer with a processor and linear module4.

heading: 4.1.2 NeuralExecutor++
text: Veličković et al. [1] showed positive transfer when learning algorithms in a multi-task setup with intermediate steps. They did so by concatenating together the node features and encoding them together into the same h embedding (see Fig. 1). This has the advantage of giving strong guidance to the secondary algorithm learned in this multi-task set-up. However, ideally we are able to only use the base algorithm during training without having to use it at inference time introducing another failure mode. Thus, we propose to change the architecture as follows:
Since the node encoder is unable to learn the individual subroutines operating on edges, we replace it with a latent encoder for each task that operates on edges and for an edge (i, j) takes in [h(i), x(i), e(ij), h(j), x(j)] (Fig. 1). The important difference is that each has task has its own encoder rather than all tasks sharing one encoder. The goal is to force the model to learn the shared subroutines in the processor only and the specialised subroutines in the latent encoder only (see Fig. 1).
Further, we change the latent encoder to consist of a linear and non-linear encoder in parallel that are added together. This should allow for algorithmic alignment with a much larger array of tasks (specifically WIDEST PATH), but comes at the cost that overfitting is more likely, which may hurt generalisation to larger graphs. This last problem has been avoided in prior work [1, 15] by having the neural network only learn linear components, which will not be able to overfit easily.5

heading: 4.2 Training and Loss functions
text: Sequential algorithms (Seq): We used softmax for the prediction of the next node to be removed from the queue and softmax for the predecessor prediction, where we masked out all nodes except the neighbours and the node itself. We used a smooth l1 loss with β = 0.001 for the prediction of the key of the selected node. Finally, we used binary cross entropy for termination prediction. We only update the node state of the chosen node, this helps with drift of the node state at test time.
Parallel algorithms (Par): We used a smooth l1 loss with β = 0.001 for the prediction of the key except for BFS where we used binary cross-entropy as the node state is either 0 or 1. In this setting, during teacher-forcing, we masked out nodes that are unreachable at a given time step.
4We remove the ReLU because it limits the ability of the max aggregator to minimise values by using negative inputs. The termination condition depends on whether the remaining nodes are still reachable hence an MPNN is a more appropriate than a linear layer.
5See the Supplementary for a more formal description.
Teacher forcing (TF): We train the network to predict the next step given the ground truth inputs. At test time the networks prediction are used instead of the ground truth.
No algorithm (NA): We train the network using only the loss on the final outputs, this means we change the softmax for predicting the next node to a binary cross entropy for sequential algorithms. The next inputs are those predicted by the network using gumbel softmax to predict the next node at each stage. The number of steps are given to the network in this scenario. Inspired by [27], we sample 10 trajectories using the best one for back-propagation, when using a gumbel softmax. The idea is that only the best loss is of interest at evaluation time and not the average loss. We show in the supplementary that this helps stabilise and improve training compared to taking the mean of the trajectories.

heading: 4.3 Standard transfer methods
text: We try three main approaches:
Freeze weights: This is a standard transfer technique, where we use the learned weights of the processor unit on a base algorithm B for learning a target algorithm T . In this set-up we freeze the weights of the processor and only the encoder-decoder part of the architecture can be learned. We assume that the algorithm B was learned with teacher forcing, while T is learned with no-algorithm. We note that encoder-decoder weights cannot be reused because in general the input/output dimensions may differ from algorithm to algorithm.
Fine-tune weights: This is the same as the previous technique except that we do not freeze the processor weights and instead let them be changed by the gradient descent algorithm.
2-Processors: Again we assume we have access to the processor weights learned on a base algorithm B. This setting uses two processors in parallel whose outputs we sum together. One of the processor uses the learned processor weights and is frozen, while the other processor is free to learn the necessary changes and is randomly initialised. We suspect this will be the best transfer method as it does not forget the information given by the domain algorithm, but retains the flexibility to adapt the processor.

heading: 4.4 Transfer via multi-task learning
text: A stronger inductive bias is to train the base algorithm B, for which we have access to intermediate steps, together with the target algorithm T , for which we do not. This multi-task set-up highlights the difference between the original Neural Executor architecture proposed in Veličković et al. [1] and Neural Executor++ (see Fig. 1). The former simply concatenates the node features of B and T and forces them to share the hidden embedding. The latter allows different encoder-decoders and only shares the weights of the processor, i.e. each algorithm has its own hidden embedding. This second approach encourages the network to execute the shared subroutine in the processor and the individual subroutines in the encoder-decoder. The overall idea is that the base algorithm B serves as an inductive bias as to how to structure the latent space and teach the processor how to evolve T .

heading: 4.5 Graphs
text: We study three kinds of graphs:
i) Erdos-Renyi p = min (
log2 |V | |V | , 0.5
) , ii) Barabasi-Albert, iii) 2d-grid graphs.
Erdos-Renyi graphs are random graphs where each possible edge has probability p of being added to the graph. Barabasi-Albert graphs are power-law graphs with a few highly connected nodes and many dangling nodes. 2d-grid graphs are very regular graphs in an arbitrary 2d-grid shape. We chose these 3 classes of graphs because they represent some of the major possible differences between graphs. 2d-grid graphs are very regular and Veličković et al. [1] notes that very regular graphs tend to transfer poorly from or to random graphs. Erdos-Renyi graphs tend to be sparse, but highly likely to be connected. Barabasi-Albert graphs tend to be quite dense graphs with shorter average path-length than random graphs. As such these graph classes differ significantly from each other.
For all graphs, we generate edge weights that are uniformly between [0.2, 1.0], this range prevents key values such as shortest path from becoming too extreme6.

heading: 5 Experiments
text: For all experiments we use 5,000 graphs of each type (Erdos-Renyi (ER), Barabasi-Albert (BA), 2d-Grids (2d-G)) with 20 nodes each. We train using ADAM [28] with a learning rate of 0.0005, a batch size of 64, and use early stopping with a patience of 10 to prevent overfitting. We test on graphs size 20, 50, and 100 nodes. The hidden embedding size is set to 32 except for NE++ for multi-task experiments, where it is 16 to account for the additional expressivity of having several encoders. Each experiment was executed on a V100 GPU in less than 5 hours for the longest experiment.
We measure the average performance over all 3 graph types at evaluation separately and present the average with standard deviation in the main paper. Large standard deviation may arise due to the extreme difference between random graphs of type ER or BA versus 2d-G graphs.7

heading: 5.1 Metrics
text: Sequential algorithms: Predecessor (Pred.) error rate is the most important measure as to whether a task has been successfully completed as it gives us the path predicted by the network. Next node (Next) error rate measures whether the next node is the correct one to pick. Key accuracy measures whether the key of the picked node is correct, measured in mean squared error. Next node are indicative of whether the correct algorithm is being executed, while Pred. and Key primarily serves to indicate the correctness of the solutions found. Lower is always better.
Parallel algorithms: Key accuracy measures the node features mean squared error for all algorithms except BFS, where it is measured in accuracy as the node feature is a binary choice between 0 and 1. Predecessor (Pred.) accuracy measures the accuracy of predicting the predecessor node.

heading: 6 Results and Discussion
text: For the sequential algorithms we study transfer from PRIM to DIJKSTRA and from WIDEST PATH to MOST RELIABLE PATH, for parallel Algorithms we study transfer from BFS to BELLMAN-FORD and from WIDEST PATH to MOST RELIABLE PATH.
6All code to generate data and train models will be released upon acceptance with an MIT license. 7See the Supplementary for a more detailed explanation.

heading: 6.1 Sequential
text: The first experiments establish baselines in terms of achievable performance given the intermediate steps and trained with teacher-forcing (Tab. 1). We run each algorithm separately. Next we establish the performance in the no-algorithm setting (Tab. 2), i.e. what is achievable without intermediate supervision.
Expressivity can harm systematic generalisation: Firstly, we note that the additional expressivity of the NE++ (§ 4.1.2) seems to hurt systematic generalisation even with the large amount of data available (Tab. 1) as we can see on DIJKSTRA. On MOST RELIABLE both do equally well on Key and Pred., but looking at Next node we can see that NE++ does better in simulating the algorithm. MOST RELIABLE is a non-linear task so a non-linear encoder is expected to help. We also note that as the graphs grow in size, the number of reachable nodes in the priority queue increases, making it more likely we pick the wrong node without affecting the correctness of prediction.
Secondly, we note that in the NA setting (Tab. 2) the NE is able to solve the Pred. prediction quite well up to 100 nodes, but clearly found an alternative way of reasoning as the key prediction is hugely wrong for larger graphs. Note that the largest shortest distances will be found in 2-grid graphs, where it will be upper bounded by 51. Also for MOST RELIABLE the performance on Pred. drop at 50 nodes is significantly more severe with less representation power.
Transfer yields little improvement: The two key experiments are the transfer setting (§ 4.3) and the multi-task setting (§ 4.4). We hypothesised that the standard transfer experiments (fine-tune and freeze) would not help systematic generalisation. None of the transfer methods (Tab. 3) help generalise either task significantly. In fact, they harm systematic generalisation in terms of Pred. prediction in all cases. The only benefit that can be observed is better generalisation on Key accuracy indicating that the network outputs are less extreme. The best transfer method is 2-Processor as we hypothesised in § 4.3, which improves Key prediction at the cost of harming Pred. accuracy.
Multi-task helps systematic generalisation: In the multi-task set-up (Tab. 4), several things occur: the Key prediction generalises even better and is predicting in a reasonable range given the longest
shortest path in graphs of size 100. Further, NE in this setting has similar Pred. accuracy on DIJKSTRA compared to NA, NE++ benefitted from the inductive bias in terms of its Pred. accuracy on graphs of size 100 for DIJKSTRA. The results on MOST RELIABLE are significantly improved and NE++ achieves good levels of systematic generalisation in solving the task. NE interestingly worsens in its performance on 20 nodes, but maintains a stable Pred. accuracy on larger graphs. Demonstrating that the inductive bias from WIDEST prevents overfitting in distribution and improves the performance on larger graphs. Overall, the results validate our initial hypothesis that multi-task learning is the correct approach to transfer knowledge.
Trying to extract shared subroutines does not help transfer: Finally, we study to what extent the models are able to separate the common shared subroutines and the subroutines individual to each algorithm by training multiple algorithms with TF in a multi-task set-up together (Tab. 5). If the processor successfully captures only the shared subroutines, then we might expect the transfer results to be improve. We can see in Tab. 5 that multi-task pre-training does not significantly improve results and that multi-task learning with the target algorithm is still the best approach. However, one alternative explanation is that given a good processor, the encoder struggles to learn the expected encoding by the processor and thus performs poorly.

heading: 6.2 Parallel
text: Parallel algorithms are significantly easier than sequential ones due to their much shorter length and the lack of a central data-structure that needs to be learned to execute. This can be observed in the much higher performance in the NA setting (Tab. 6). Interestingly, it seems that in this setting expressivity was helpful for systematic generalisation, even in the BELLMAN-FORD setting.
Transfer harms performance: In Tab. 6 we show only the best transfer result, but as we can see this actually harms Pred. accuracy for NE++ for both algorithms, while producing roughly the same result for NE. In both cases, the results suggest that random initialisations are better than transfer ones. We think this may because the shared algorithmic knowledge of parallel algorithms is already inherently captured by GNNs as they apply message functions in parallel to each edge, which then only need to learn the relax_edge function. Pre-training on several algorithms did not help (Tab. 5).
Multi-task only helps Key accuracy: Similarly to sequential reasoning multi-task vastly outperforms transfer techniques and significantly improves Key prediction compared to NA, while keeping Pred. similar. Contrary to sequential reasoning the Pred. prediction is comparable between NA and multi-task. We think this is due to the shorter execution length providing less of an inductive bias for the target algorithm and the strong inductive bias of GNN architectures towards parallel algorithms. However, the access to more stable gradients due to the multi-task learning approach seems to help learning to some extent due to the improved Key predictions. Further, we observe that when the model has less capacity (NE on MOST RELIABLE PATH) multi-task is still able to improve systematic generalisation on Pred. at the cost of slightly worse in-distribution (20 nodes) performance.

heading: 6.3 Why transfer learning fails?
text: Transfer via freezing and/or fine-tuning clearly does not work as demonstrated by the results in Tab. 3. The fact that having two processors, one frozen and one to fine-tune, also does not help transfer is telling, because neither the fine-tuning process losing information, nor the rigidity of the network can be at fault. In other words, fine-tuning has the disadvantage that we lose the original weights and hence potentially lose information. Freezing weights significantly limits the weights that can be changed and thus making it harder to fit the data. However, the 2-processor approach suffers from neither problem and yet still does not work.8 Thus, we hypothesis that the reason why transfer fails to work is that the initial weights of a similar algorithm are not near a good (as in generalising) minimum for the target algorithm, in fact the minimum is often worse than the minimum found from randomly initialised weights (see Tab. 2).

heading: 6.4 Why multi-task fairs better?
text: Multi-task on the other hand does not rely on the weights being near a good minimum, but instead enforces them to be the same for the processor. This is a very different way to use the base algorithm as an inductive bias. This inductive bias is successful because the final weights are from a minimum that systematically generalises (on at least one of the algorithms) with the additional constraint that it performs well on the second target algorithm. For transfer the initial weights might systematically generalise on the original task there is no guarantee that the final weights stem from a minima that systematically generalises.

heading: 7 Conclusion
text: We set out to investigate how systematic generalisation could be improved on algorithmic tasks when the intermediate steps of the algorithm are not available. Inspired by the success of transfer learning in domains such as CV and NLP, we investigated it’s applicability to learning graph algorithms in this setting. We showed that standard transfer learning is inadequate to leverage algorithmic knowledge learned from intermediate steps to new algorithmic tasks. Further, we showed how multi-task learning can enable the successful transfer of inductive biases learned from other algorithms when intermediate steps are available, significantly improving systematic generalisation. The results are especially strong in the more difficult sequential reasoning domain. Moreover, we conclude that expressivity can hurt systematic generalisation if the task is too easy and intermediate supervision is available. This should be taken into account when choosing the model. These disadvantages disappeared when trying to learn algorithmic reasoning without intermediate steps in our multi-task set-up, in this setting NE++ always outperforms the simpler architecture. Both architectures can achieve systematic generalisation. Limitations of our work are that the results are specific to algorithms on static graphs. Furthermore, as the number of execution steps increases faster than linear in the number of nodes results are likely to worsen significantly.
This paper’s contributions are fundamental in nature and thus, the societal impact of this paper is low and there are no associated ethical risks. Any benefits or risks stem from further advances in reasoning systems that may be in some form be based on this work.
8Experiment 1 (in the Supplementary material) shows that the information from a processor can be used and recovered.
Acknowledgments and Disclosure of Funding
We would like to thank Meng Qu, Zhaocheng Zhu, and Zuobai Zhang for proof reading the manuscript prior to submission.
This project is supported by the Natural Sciences and Engineering Research Council (NSERC) Discovery Grant, the Canada CIFAR AI Chair Program, collaboration grants between Microsoft Research and Mila, Samsung Electronics Co., Ltd., Amazon Faculty Research Award, Tencent AI Lab Rhino-Bird Gift Fund and a NRC Collaborative R&D Project (AI4D-CORE-06). This project was also partially funded by IVADO Fundamental Research Project grant PRF-2019-3583139727.
Petar Veličković is a Research Scientist at DeepMind.

Review summaries:
This paper discusses how to transfer the knowledge from known step-by-step algorithms to learn new algorithms with only input and output pairs. The authors reach the conclusion: transfer learning does not help, but multi-task learning helps with the systematic generalization. The main contributions of this paper are: 1. A new benchmark for transferring algorithmic knowledge 2. Study on training and loss functions case by case for different graph algorithms and setup 3. Shows standard transfer learning technique fails on algorithm learning, but multi-task learning helps.

The authors studied how to transfer algorithmic reasoning knowledge. Particularly, they aim at using algorithms for which we have access to the execution trace to learn to solve similar tasks for which execution trace is not available. The authors examined two classes of graph algorithms, parallel algorithms and sequential greedy algorithms. They tested the hypothesis that standard transfer techniques are not sufficient and showed that multi-task learning can be used instead to achieve the transfer of algorithmic reasoning knowledge. 

The paper studies a transfer learning setting for learning graph algorithms, where we do not have the execution traces for the target algorithm, but we have execution traces for a related algorithm. The paper uses an adapted version of NeuralExecutor (Velickovic et al., 2019) and investigates transfer learning within two families of graph algorithms: sequential algorithms and parallel algorithms. The paper finds that standard transfer learning techniques don’t help in this setting, but multi-task training is useful.

The paper studies the problem of transferring algorithmic reasoning knowledge from a task to another similar task. The authors first propose a set of benchmark tasks to evaluate transfer learning for algorithmic reasoning on graphs.   The authors then propose modifications to the Neural Extractor model by replacing the node encoder with a latent edge encoder. Along with this, they propose using two latent encoders, one with a linear layer and one with a non-linear layer to allow the model to learn more types of tasks. Also, a separate encoder is used for each task.   The authors experiment with several transfer-learning and Multi-task learning (MTL) approaches on the proposed benchmark tasks.  The authors conclude that standard methods for transfer learning are ineffective on transferring algorithmic reasoning knowledge. They further show that the MTL approach effectively transfers knowledge thus improving systematic generalization.