How to transfer algorithmic reasoning knowledge to learn new algorithms?
Authors: Louis-Pascal A. C. Xhonneux
Andreea Deac
Petar Veličković
Jian Tang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Learning algorithms
Transfer
Graph Neural Networks

Abstract: 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.

How to transfer algorithmic reasoning knowledge to learn new algorithms?
Louis-Pascal A. Xhonneux*
Andreea Deac Université de Montréal
Université de Montréal Mila xhonneul @malammmaa....mllll emila.quebec
Mila deacandr@mila.com Quebe
Petar Veličković DeepMind, London UK petarvggoogle.cmm com
Jian Tang
HEC Montréal
Mila jian. taantennehec.co ca
Abstract
Learning to execute algorithms is 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 pro- gram/algorithm. In many reasoning tasks, where algorithmic-style reasoning is important, 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 Pro- cessing (NLP) and Computer Vision, we algorithmic reasoning knowledge. Specifically, we investigate how we can use algorithms for which we have access the execution trace learn solve similar tasks for which we do not. We investigate two major classes of graph algorithms, parallel algorithms such breadth-first search and Bellman-Foo and sequential greedy algorithms such as Prim and Dijkstra. Due to the fundamental differences between algorithmic reasoning knowledge and feature extractors such as used Computer Vision or NLP, we hypothesise that standard transfer techniques will not sufficient to achieve systematic generalisation. To investigate this empirically we create 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.
to study how
transfer
Introduction
Transfer learning (2 has been responsible for significant successes in multiple areas of machine learning, including Natural Language Processing (NLP) [34 and Computer Vision (CV) [5]. Pre- training and reusing the learned weights, by freezing them 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 limited some form.
Algorithmic reasoning on graphs [ 6 is fundamental problem that has been studied under the assumption that we have access the execution traces of the algorithms we such as many real world reasoning tasks, this may not be true. Due to the limited data, we look to transfer learning enable solve algorithmic tasks without intermediate steps. Specifically,
learn In practice,
"oorreponning author
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

investigate how to transfer knowledge between similar graph algorithuss in the setting where we have access to the execution traces for some (e.g. PRIM 7 () but not others (e.g. DUKSTRA (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 ceasoning-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 high-level space. This is 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.
to execute graph algorithms. Two key ingredients were access to the intermediate steps of the algorithm and algorithmic alignment [[S. Algorithmic aligmment [15] refers to the concept of a computation structure-in our case neural networks-ant the structure of an algorithm "aligning" -n this paper graph algorithms. 'Alignment' means there exists mapping between substructures of the computation architecture and simple substeps of the algorithm, where the substructures can 'casily' compute the corresponding substep they are mapped to for some definition of easy, usually linear.
Veličković et al. [ successfully trained graph neural networks (GNNs) 12 13 14
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 [ 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 DUKSTRA greedily select nodes from priority queue). This shared algorithmic knowledge should serve as an inductive bias to enable 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 hase algorithm to target algorithm. While features across images may be similar, the features of algorithms differs (e.g. shortest distance in DIKSTRA and lightest edge to the tree in PRIM), but are processed 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 ttrnsferrrneereeeee 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.
2 Related Work
Neural Execution: Many papers have studied how to execute algorithms before [6
17
18 19 20
With the rise of graph representation learning (2 22 23 and graph neural networks
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.
recent work has looked at executing graph algorithms
2

---

Transfer learning: Transfer learning was originally proposed in the 1970s 25 26
Today, it is task 22 3 5
common tool in NLP and Computer Vision to use pre-trained models and fine-tune them on the target This is helpful when the target task is similar and the available data is limited in some way. Our work differs 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 partially missing specifically the execution trace the algorithm is missing.
3 Background
This section gives background on the algorithms and graphs used for the experiments. To be precise we consider graph to be tuple G = (V, with set of vertices V and set of edges E C V v
This section explains the algorithms studied this paper in more detail. After that, we give brief introduction into graph neural networks, the standard architecture paradigm for graph inputs.
3.1 Algorithms
broadly study two classes of algorithmic reasoning: parallel and sequential reasoning. Specifically, the parallel algorithms (shown in Algorithm I studied in this paper exchange messages with their neighbours until an equilibrium is reached. Sequential algorithms, presented in Algorithm [ greedily remove elements from priority queue and updating the neighbouring nodes' keys.
Algorithm Parallel
Algorithm Sequential
Input: graph G, weights w, source index initialise_ initialise_nodes(GG.. Modes((.verticees, i)
Input: graph G, edge weights w, source node index
repeat
initialise ciiialissennodssC.vvriii i)
for (u, v) E G.edges() do
Q t PriorityQuece((..eetieee)
relax_edge( v, w)
repeat
end for until none of the nodes change
- Q-pop_ppppm min()
for E G. G.eiighbours(u) do
relax_ feexx_eeee(,,, v, w)
end for until Q empty
Different algorithms will implement their own velax_edg' and initialise_tse _nndes 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, key feature for the priority queue, and pointer to the predecessor node.
We study the following algorithms: PARALLEL
SEQUENTIAL
1. BREADTH-FIRST SEARCH (BFS)
1. PRIMS
2. BELLMAN-FORD
2. DUKSTRA
3. WIDEST PATH (PARALLEI.)
3. DEPTH-FIRST SEARCH (DFS)
4. MOST RELIABLE-PATH (PARALLEL)
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 increasingly difficult to learn for the neural network as you go down the list: PRIMS uses the edge weight key, thus the relax_edge function is the identity, for DUKSTRA and DERSH-FIRST SEARCH addition necessary to compute the edge update, for WIDEST-PATH we need to take a maximum, which with ReLU activation still be done exactly, and for MOST RELJAALLE-PATH the neural network needs to learn to approximate multiplication?
Thhroughout the paper we use graphs that are simple with weights. We note that the tasks are all linear time in the size of the graph. More challenging problems such as NP-hard problems primarily more difficult because of their increased timtimm and hence longer sequences allowing

---

3.2 Graph Neural Networks
general framework describe several graph neural network architecture is the message passing framework introduced by Gilmer et al. [T3]. Such graph neural networks (GNNs) consist of three parts: message function M, an update function U, and an aggregator A 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 O;
3. finally, each node updates embedding using
The message function in this paper takes imput 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 and provides algorithmic alignment [15] between the architecture and the tasks. The update function takes input the node's previous embedding and aggregated messages.
determined work best Veličković et al. []]
3.3 Problem definition
We study learning graph algorithms that take in graph G, a weight function w - R that assigns weight each edge in the graph, and node features X V - R Algorithms compute an output Y V + 1*t and a predecessor P V + V at each time step. This encompasses large class of graph algorithms solving tasks such reachability or shortest-path.
For instance, for a sequential algorithm the ith node's features X 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 Y, and the predecessor for each P. (pred variable in pseudocode $3.I). Yr and Pr at the final step considered the output of the algorithm. The intermediate steps refers X,, Y,, P. 1I E (1, ( }} after each iteration.
4 Methods
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.
4.1 Architecture
As our starting point we choose the encoder-pros woweeer-roocsso-deccooo architecture proposed Veličković al. [I]. The high-level idea is that the network encodes the current node state into 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 ($ (.J).. The point of this architecture is to allow several algorithms to use the same processor architecture, A more detailed summary of the architecture given below:
4.1.1 NeuralExecutor
The NeuralExecutor (NE) 11 uses an mncoder-procesoo-deeoder architecture. Let X E Rank be node states, where nı, are the number nodes and features, respectively. Each edge (u,v) v) has weight w(u v) E R. The architecture keeps hidden state for each node H Raxt with features, which is initialised to all zeros. The encoder & consists of a linear layer and computes a hidden embedding E (X,, H,) Z., where indicates the ith step the computation. The processor P is message passing neural network (MPNN) with max aggregator with linear message and update functions, The processor computes the new hidden state for each node P(H,, A, w) H Then, we have the decoder D(2, 1) = Y,41 and predecessor predictor S( S(Z,, Hi+1) = S,. Finally, termination network a aT (HH,,))) 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 emors and propagate them.

---

(9) 6
.a.
.1 x
W
h
node encoder
edge encoder
latent encoder
latent encoder
edge encoder
edge encoder
processor
processor
decoder
decoder
decoder
(106 Mn (Po-PL)
(y0.Po)
(91-P1)
(a)
(b)
Figure I: To, are the node states of two algorithms respectively. w are the edge weights. po. Pr are the predecessor predictions for the two algorithms respectively and you y1 are the next node state predictions. h,s are the previous hidden state kept by the network and elts) the computed edge weight embedding. Superscript indices indicate a particular node. (a) Shows the original Neural Executor architecture when doing multi-task learning.
(b) Shows the more expressive Neural
Executor++ when doing multi-task learning. The key difference is that (b) forces a common way to operate on hidden embedding space, while (a) focuses on achieving both at the same time.
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 module
4.1.2 NeuralExecutor++
Veličković et al. [ 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. T. This has the advantage of giving strong guidance to the secondary algorithm learned in this multi-task set-up. However, ideally we are able 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 re- place it with latent encoder for each task that operates edges and for an edge (i,j) takes in [A(0) (i),,, e(tf), h,6), xز0ب (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.
Further, we change the latent encoder to consist a linear and non- non-linear encoder in parallel that added together. This should allow for algorithmic alignment with 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 [5 by having the neural network only learn linear components, which will not be able to overfit easily
4.2 Training and Loss functions
Sequential algorithms (Seq): We used tmax for the prediction of the next node to be removed from the queue and smax for the predecessor prediction, where masked out all nodes except the neighbours and the node itself. We used a smooth 4 loss with 3 = 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.
We used smooth loss with 3 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 given time step.
Parallel algorithms (Par):
"We remove the ReLU because 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 a more appropriate than a linear layer. See the Supplementary for more formal description.
5

---

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 change the sof smax for predicting the next node binary cross entropy for sequential algorithms. The next inputs are those predicted by the network using gumbel tmax 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 gumbel softmax. The idea is that only the best loss 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.
4.3 Standard transfer methods
We try three main approaches:
Freeze weights: This is standard transfer technique, where we use the learned weights of the processor unit on 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 was learned with teacher forcing, while T is learned with no-algorithm. We note that mecoder-decode 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- 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 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 it does not forget the information given by the domain algorithm, but retains the flexibility to adapt the processor.
together. One of the processor
4.4 Transfer via multi-task learning
stronger inductive bias 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 Veličković al. M and Neural Executor++ (see Fig- [T. 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.
4.5 Graphs
We study three kinds of graphs:
i) Erdos-Renyl p min (lopz) [V] .o.5). .i) Barabasi-Albert, iii) 2d-grid graphs.
[ogga VV
Erdos-Renyi graphs are random graphs where each possible edge has probability p of being added to the graph. Barabasi-Albertt graphs are power-law graphs with a few highly connected nodes and many dangling nodes. 2d 2d-grid graphs are very regular graphs 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 Veličković et al. [ notes that very regular graphs tend to transfer poorly from or to random graphs. Birdos-Renys graphs tend to be sparse, but highly likely to be connected. Barabasi-Alber 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.

---

Table 1: Teacher forcing (seq.). NE++ worse performance on DUKSTRA showing the downside of higher model capacity.
DUKSTRA
MOST RELIABLE
Model
NNdels
Next node
Key
Predecessor
Next mode
Key
Predecessor
20
0.018 0.004
0.0367
0.01
0.005 0.002
0.238 1 0.05
0.0358 1 0.02
0.053 1 0.01
NE
50
0.089 + 0.009
0.569 0.7
0.02 0.00
0.557 +: 0.08
0.0697 + 0.05
0.099 +: 0.01
100
0.341 0.02
4.79 +
0.064 0.04
0.763 = 0.07
0.0924 + 0.06
0.167 0.007
20
0.008
1: 0.003
0.0108 1: 0.004
0.003 1: 0.0008
0.174 1 0.07
0.0264 1: 0.02
0.047 1: 0.03
NE
0.35 0.03
445
0.211 0.02
0.492 : 0.2
0.0676 + 0.05
0.1 = 0.05
100
0.729 0.01
1. 1.62e10 + 2e10
0.522 0.07
0.699 = 0.2
0.0906 + 0.06
0.171 = 0.06
Table 2: No algorithm (seq.). Size-generalisation is lacking without intermediate steps, especially on the more difficult MOST RELIABLE.
DUKSTRA
MOST RELIABLE
Model
#Nodes
Key
Predecessor
Key
Predecessor
0.000104
76:05
0.01
0.00829
0.187
NE
50
9.71e6 + 1e06
0.121 = 0.1
20 +
0.897 + 0.08
100
3.34e16 + 5e16
0.194 = 0.2
1.32e6 1e5
0.768 0.05
20
6.4e-06 3c-06
0.006 0.003
0.000465
6e-06
0.126 0.00
NE ++
50
1.81 +
0.149 : 0.06
125 + 70
0.566 + 0.06
0.388
4e13
0.76
For all graphs, we generate edge weights that are uniformly between [0.2, 1.0], this range prevents key values such shortest path from becoming too extreme
Experiments
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 (8 with a learning rate of 0.0005, 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
V100 GPU in less than hours for the longest experiment.
We measure the average performance over all 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
5.1 Metrics
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 (Nexr) 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.
Sequential 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 binary choice between 0 and 1. Predecessor (Pred.) accuracy measures the accuracy of predicting the predecessor node.
Parallel algorithms:
6 Results and Discussion
For the sequential algorithms study transfer from PRIM DUKSTRA and from WIDEST PATH to MOST RELIABLE PATHI for parallel Algorithms we study transfer from BFS to BELLMAN-FORD and from WIDEST PATII to MOST RELIABLE PATII
6 All code to generate data and train models will be released upon acceptance with an MIT license. See the Supplementary for more detailed explanation.
7

---

Table 3: Transfer to no algorithm (seq.). Pre-trained on PRIM and WIDEST, respectively. Classic transfer learning fails to provide sizz-generalliattoon and often performs worse than no transfer.
DUKSTRA
MOST RELIABLE
Model
#Nodes
Key
Predecessor
Key
Predecessor
20
0.014 0.005
0.081 1 0.03
0.0235 1 0.003
0.248 1 0.06
NE. Freeze
50
122 + 200
0.597 + 0.09
3.91e5 + 3e4
0.864 + 0.009
100
3.18e6 + 4eG
0.607 + 0.1
5.06e + 7414
0.761 + 0.04
20
0.0021 1: 0.0009
0.05 4: 0.02
0.036 4: 0.005
0.227 1: 0.07
NE Fine-tune
50
1.1 + 1e3
0.241 + 0.09
2c3 200
0.636
100
5,93e7 + Se7
0.388 + 0.1
1.06e9 + 1e8
0.709 + 0.02
20
0,00136 + 0. 0.0005
0.06 : 0.03
0.0163 = 0.003
0.231 + 0.08
NE Processor
14.2
1: 0.06
30
1 0.04
100
1.04e4 + 1e4
0.305 + 0.07
1.22.10 + 4e9
0.815 + 0.03
20
0.00136 1: 0.001
0.063 1: 0.02
0.00687 1: 0.0008
0.199 1 0.09
NE+ Frezze
50
42.6 50
0.841 + 0.04
465 100
0.58 0.1
100
262 + 400
0.895 + 0.07
8.06e7 4: 3e7
0.672 1: 0.08
20
0.0001111 = 0.0003
0.031 = 0.02
0,00669 0,002
0.191 0,07
NE++ Fine-tune
50
13.5 + 20
0.962 + 0.03
1.79c5 + 2e5
0.737 + 0.05
100
2.51c4 1. 4c4
0.962 1. 0.04
8.17e14 1 5e14
0.774 1: 0.05
0.00143 + 0.002
0.0022 0,0003
0.15-1
NE++ Procesoor
50
16.6 1. 20
0.356 1: 0.1
306 1: 70
0.644 1: 0.03
100
4.66e3 + 6e3
0.779 + 0.02
3.58e6 + 9e5
0.791 + 0.02
Table 4: Multi-tast (seq.): Using PRIM and WIDEST as inductive bias, respectively. Multi-task learning shows good generalisation, especially the Key metric for DUKSTRA and on Predecessor for MOST RELIABLE.
DUXSTRA
RELIABLE
Model
#Nodes
Key
Predecessor
Key
Predecessur
20
0.00362 + 0.0005
0.042 = 0.01
0.207 : 0.03
0.452 0.09
NE
50
11.0 =
0.134
1.85 0.5
0.501 0.06
100
126 + 30
0.303 1: 0.3
6.47 + 3
0.597 0.01
20
0.000178 86-05
0.019 0.000
0.00279 + 0.0004
0.106
NE
50
0,413 + 0.4
0.161 = 0.1
0,199 + 0.3
0,185 + 0.009
100
2.91 =
0.282 0:92:0:0 0.2
0.843 +
0.267 + 0.1
6.1
Sequential
The first experiments establish baselines in terms of achievable performance given the intermediate steps and trained with teacher-foree forcing (Tab. [T. 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++ (& 1.22)) seems to hurt systematic generalisation even with the large amount of data available (Tab. [ as can on DUJSTRA. 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 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 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 (8 4.4). We hypothesised that the standard transfer experiments (fine-tune 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 Pred. prediction in all cases. The only benefit that can be observed is better generalisation 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 the cost of harming Pred. accuracy.
Multi-task helps systematic generalisation: In the multi-task set-up (Tab. several things occur: the Key prediction generalises even better and is predicting in a reasonable range given the longest
8

---

Table 5: 2-Proc. transfer pre-trained on PRIM, DUKSTRA, & DFS for sequential and BFS & BELLMAN- for parallel. Pre-training on several tasks does not improve classic transfer.
MOST RELIABLE (SDQ)
MOSt RELIABLE (PAR)
Model #Nodes
Key
Prodecessor
Key
Predecessor
20
0.00237 0.0003
0.163
0.06
0.0408 i 0.009
0.227 1 0.07
NE ++ 2-Proc.
50
62.9 + 20
0.606
0.05
0.161 + 0.1
0.363 1 0.04
100
1.76 4e5
0.768
0.07
4
0.448 + 0.08
Table 6: No algorithm (par.): For transfer we report the results of the best method ($ 4.3 Pre-trained on BFS and WIDEST respectively. Reliance on intermediate steps is lower for this class of problems, but multi-task transfer of knowledge is still beneficial in terms of size-generalisation.
BELIMAN-FORR
MOST RELJABLE
Model
#Nodes
Key
Predecessor
Key
Predecessor
20
0.0182 0.02
0.057 0.02
0.018 0.002
0.226 0.06
(NA)
50
59 + 80
0.164 : 0.1
0,147 + 0.2
0.327 + 0.02
100
1.98c6 + 3e6
0.261 0.2
10.4 = 10
0.435 = 0.05
20
0.00253 0.002
0.028
0.00957 0.004
0.145 - 0.06
NE++ (NA)
50
0.226 + 0.3
0.057 0.01
0.0367 0.04
0.171 = 0.03
196 300
+.955
0.02
20
0.0386 0.02
0.07
0.0221 + 0.006
0.237 = 0.06
NE (Transfer Fine-tune)
50
25 40
0.162
0.332 0.4
0.331 - 0.02
100
1.72e5 + 265
0,242
230 + 300
0.402 0.03
20
0.0223 1 0.02
0.062 0.00
0.0131 1 0.003
0.196 1 0.07
NE++ (Transfer 2-Proc.)
0.666 0.7
0.005
3.04
0.313 + 0.05
100
10.8 + 10
0.168
579 = 800
0.411 0.1
20
0.0154 0.002
0.004
0.173 +
0.346 + 0.02
NE (Multi-task)
50
6.22 =
0.051 0.004
0.407 0.4
0.362 0.03
100
1.53e3 + le3
0.096 0.02
0.615 0.6
0.376 + 0.05
20
0.00353 0.004
0.023 1 0.00
0.00672 1 0.0005
0.153 1 0.06
NE++ (Multi-task)
50
0.0141 0.02
0.03 1: 0.006
0.00805 0.002
0.182 1 0.01
100
8.84 + 10
0.13
0.00971 - 0.002
0.212 = 0.02
shortest path in graphs of size 100. Further, NE in this setting has similar Pred. accuracy on DUKSTRA compared NA. NE++ benefitted from the inductive bias in terms of its Pred. accuracy on graphs of size 100 for DUKSTRA. 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 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.
Finally, we study to what extent the models are able 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. [ that multi- 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.
Trying to extract shared subroutines does not help transfer:
6.2 Parallel
Parallel algorithms are significantly casier 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. (.. Interestingly, it seems that in this setting expressivity was helpful for systematic generalisation, even in the BELLMAN-FORD setting.
Transfer harms performance: In Tab. 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 parallel to each edge, which then only need to learn the relax relax_edge function. Pre-training on several algorithms did not help (Tab. 5).

---

Multi-task only helps Key accuracy: Similarly to sequential reasoning multi-tane task vastly outper- forms 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.
6.3
Why transfer learning fails?
Transfer via freezing and/or fine-tuning clearly does not work as demonstrated by the results in Tab. B 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 [ fails to work is that the initial weights of a similar algorithm not near 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.
Thus, we hypothesis that the reason why transfer
6.4 Why multi-task fairs better?
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 guarantee that the final weights stem from minima that systematically generalises.
7 Conclusion
We set out to investigate how systematic generalisation could be improved on algorithmic tasks when the intermediate steps of the algorithm 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 iss contributions 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.
fundamental in nature and thus, the societal impact of this paper is
'Experiment (in the Supplementary material) shows that the information from a processor can be used and recovered.
10

---

Acknowledgments and Disclosure of Funding
We would like 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 Al Lab Chino-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-2009-33881139777
Petar Veličković a Research Scientist at DeepMind.

---

References
[1] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. arXiv preprint 1rxiiv/9910 10593, 2019.
[2] Dumitru Erhan, Aaron Courville, Yoshua Bengio, and Pascal Vincent. Why does unsupervised pre-training help deep learning? In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 201-208. JMLR Workshop and Conference Proceedings, 2010.
[3] Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
[4] TB Brown, B Mann, N Ryder, M Subbiah, J Kaplan, P Dhariwal, A Neelakantan, P Shyam, G Sastry, A Askell, et al. Language models are few-shot learners. arxiv 2020. arXiv preprint arXiv:2005.14165 14165, 4, 2020.
[5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2020.
[6] Petar Veličković, Lars Buesing, Matthew C Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. arXiv preprint arXiv:2006.063:: 2020.
[7] Vojtëch Jarník. On a certain problem of minimization. Práce moravskè přárodovvdecké společnosti 6, fasc. pages 57-63, 1930. URL http::///hdll httt:://hdd.handeee hwndle....e...c .et.oleeenet/133....1 cmw.11333..m.c....mmmmm 500726
[8] R.C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, pages 1389-1401, 1957. URL /tL/httts::/rrcciveeeoo
bosiii/ss/sss//-oooo 1389
[9] E.W. Dijkstra. A note on two problems in connexion commexioon with graphs. Numerische Mathematik, pages 269-271, 1959. URL /ttpttppe///oo..o//1001100/////1
[10] Andreea Deac, Petar Veličković, Ognjen Milinković, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolić. Xlvin: executed latent value iteration nets, 2020.
[11] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: 2015.
[12] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 16X.vv/609002007 2016.
[13] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning. pages
PMLR, 2017.
[14] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
[15] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about?, 2020.
[16] Wojeiech Zaremba and Ilya Sutskever. Learning execute, 2015.
[17] Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms, 2016.
[18] Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-acces, machines, 2016.
[19] Scott Reed and Nando de Freitas. Neural programmerr-nteeppetrss,, 2016.
12

---

[20]
Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals. Razvan Pascanu, and Timothy Lillicrap. Relational recurrent neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https http://poooedddn.......os www.ggs....iis..... cc/ cc/paper/2018/ [tlp::/ccccas8722000eeeeee622223
pdf
[21] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4): 42, Jul 2017. ISSN 1558-0792. doi: 10.1109/ms..2017.26522 261729944........ URL http:
//dx. dox..doi.. org/ 10. 1109/MSP 2017 2693418
[22] William I.. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and upplications, 2018
[23] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals. Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks, 2018.
[24] Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning execute subroutines, 2020.
[25] S Bozinovski and A Fulgosi. The influence of pattern similarity and transfer learning upon training of a base perceptron b2. In Proceedings of Symposium Informatica, pages 3-121, 1976.
[26] S Bozinovski. Teaching space: A representation concept for adaptive pattern classification. Technical report, COINS Technical Report, University of Massachusetts Amherst, 1981
[27] Brenden Petersen, Mikel Landajuela Larma, Terrell N. Mundhenk, Claudio Prata Santiago, Soo Kyung Kim, and Joanne Taery Kim. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. In International Conference on Learning Representations, 2021. URL httpps:/ http::/pppppeeeeeeeeeeeeeerrrree
(28) Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 142,69,4,, 2014.
13


Reviews:
[{"review_id": "Zgu_57tlU4", "reviewer": "Reviewer_JA8z", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am leaning towards rejecting the paper. My main concerns are the potential impact and technical novelty.\n\nStrengths:\n* The experiments are extensive and cover many different settings.\n* The experiments have some interesting results. It is interesting to see that transfer learning and multi-task learning have quite different results.\n\nWeaknesses:\n* I am doubtful about the usefulness of this setting. It’s unclear what real-world scenarios require this type of transfer learning --- I would assume that execution traces are easy to get for graph algorithms (given their algorithmic nature).\n* The technical contribution is a little thin. While the paper is the first to study the proposed transfer learning settings, the techniques used are not new (standard transfer/multi-task learning methods). The paper does propose a modified version of NeuralExtractor, so there is some novelty there.\n* While the comparison between multi-task and transfer learning is interesting, the paper does not explain *why* the two methods are different very well. The paper provides some intuition in the introduction (line 44-53), but I find it a little vague (or maybe I didn't fully understand this part). I think this is an important takeaway from the paper, so maybe it's worth expanding this intuition with a more detailed example from experiments.\n\nSuggestions:\n* I would love to see more convincing examples of why this setting is important. It's possible that I miss some interesting applications, so I would be happy to upgrade my scores if this can be addressed.\n* Another way to improve the paper is to provide a deeper (possibly theoretical) analysis for why transfer learning and multi-task learning are so different in the experiments. This will shed light on the difference between the two techniques and may inspire future research in both graph algorithm learning and multi-task/transfer learning. \n\nOther minor suggestions/questions:\n* The current draft seems to assume that the reader knows the concept of algorithmic alignment. The paper may be more accessible if there is an explanation of this concept in the background section.\n* Is there a reason why L1 loss is used instead of L2?\n\n**Update after author response:**\n\nThe author response clarifies the motivation for the setting, so I've upgraded my rating from 4 to 5. I recommend adding an expanded version of this discussion to the paper, since motivation is very important when proposing a new research direction. It would be even better if the discussion can be connected to the particular graph algorithms used in the experiments.\n\nHowever, I am still leaning towards rejection. The author response does not provide a convincing explanation of why multi-task learning and transfer learning, so I think the empirical analysis can still be improved.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact. I do not have anything to add.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "EZGsfOceZZW", "reviewer": "Reviewer_AnUG", "summary": "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.\nThe main contributions of this paper are:\n1. A new benchmark for transferring algorithmic knowledge\n2. Study on training and loss functions case by case for different graph algorithms and setup\n3. Shows standard transfer learning technique fails on algorithm learning, but multi-task learning helps.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Originality: 3/5\nAlthough there are a few works studying how to utilize neural networks to solve program/algorithm generation, few of them study algorithmic knowledge transferability in a principled way. The results reveal transfer learning is non-trivial in algorithmic tasks, and multi-task is a better choice. \n\n### Quality: 3/5\nThe authors present a solid study of algorithmic transfer learning. They focus on the graph algorithms and vary on the a) transfer methods b) algorithm type c)algorithm difficulty d) graph size. The authors also note that all of these algorithms they have studied are O(n) and discuss the potential to extend to NP-hard problems. However, I still think adding polynomial complexity algorithms will help to make this work more complete, such as SCC. Further, the authors make an assumption that the algorithms are similar enough. Is it possible to transfer knowledge between different types of algorithms? For example, we know PATH is linear and is the prerequisite for learning SCC. Multi-task learning will probably run into a bottleneck in this setup.\n\n### Clarity: 3/5\nThe overall structure and experiment setup are pretty clear. The description of NeuralExecutor and NeuralExecutor++ is a bit abstract, and it would be nice to illustrate them in a running example. It would also be helpful to have the evaluation metric of Key and Predecessor in a unified manner, either both \"lower is better\" or \"higher is better\". \n\n### Significance: 3/5\nThe result reveals the current transfer learning techniques cannot be applied to algorithmic tasks easily. While multi-task learning can help with generalizability, this work may inspire future work on algorithmic task-specific transfer learning. \n\n----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nUpdate: \n\nI have read the response from the authors and the other reviewers. The authors promise to improve the presentation and provide more experiments between different classes of algorithms. This helps to address my concern. On the other hand, the authors provide an intuitive analysis on why transfer learning fails to work on algorithm tasks, while multi-task learning can. The study is quite informative and I hope there will be a theoretical section analysis of the difference in the updated paper. In terms of the score, I would like to maintain my original assessment. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n1. What is the multi-task learning performance on non-linear algorithms, such as SCC?\n2. What is the transferability between algorithm types, such as transferring PATH to SCC?\nTo improve:\n3. Better description of NeuralExecutor and NeuralExecutor++.\n4. Unify the evaluation metric of  Key and Predecessor, either both \"lower is better\" or \"higher is better\". ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}, {"review_id": "8Ze07VysOhJ", "reviewer": "Reviewer_ZoqR", "summary": "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.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work is relatively innovative in the sense that it addressed the transfer learning of algorithmic reasoning when intermediate steps are not available. It extended NeuralExecutor by Velicˇkovic ́ et al. so that the multi-task learning paradigm works even when execution traces are not available.\n\nI have several concerns about the soundness of the paper. First, the authors' argument that NE++ is definitely better seems not conclusive. In Line 248 in the main text, it says that NE++ actually has worse performance in some cases (Tab. 1). Even with the help of multi-task training, the NE++’s Predecessor accuracy on DIJKSTRA nodes 100 (0.718, Tab. 4) is still worse than the NE’s Predecessor accuracy on DIJKSTRA nodes 100 (0.806, Tab. 2). Furthermore, in line 296 - 299, the authors mentioned that “Multi-task only helps improve Key accuracy, but not Pred. prediction\".\n\nThere is another flaw with the paper. The authors state that “Key accuracy measures the node features mean squared error for all algorithms” (line 236-237), And the authors report the average with standard deviation in the main paper. I noticed that in some cases the mean and the standard deviation are extremely large (e.g., the cell of NE++(NA), nodes100, BELLMAN-FORD, key 1.98e6 ± 3e6). This is worrisome since an extremely large standard deviation indicates the instability of the results, making the corresponding conclusion less convincing. If the authors could respond to this that would be great. \n\nThe submission is not very clearly written. The tables lack proper caption to describe the information presented in the table. For instance, in table 1, the authors should briefly mention the definition of the evaluation metrics presented in the table. Otherwise, the readers won’t know how to interpret the numbers. Similarly, since each table represents a slightly different training paradigm, the caption should briefly capture the overall training schemes. Naming the table as “No algorithm (seq.)” is very confusing and not readable at all. Finally, the authors could consider highlighting the winning algorithms in bold in each training condition so that it's easier to compare the performances of multiple models.\n\n------------------------\n\nUpdated: I've read the authors' responses to my review as well as the ones to the other reviewers'. I don't think my concerns were fully addressed. If the authors did not intend to argue that NE++ always works better than the NE model, then they need to clarify when NE++ is expected to be better than NE and why. It did not bring any insight into the problem if the authors only show the empirical results that NE++ \"sometimes\" works better than NE but sometimes doesn't. Also, although the authors re-stated the potential reason for the large standard deviation, it didn't address my concern. When the reported metrics have large standard deviations, the reported mean is less convincing and is likely driven by extreme values. Therefore, I'm not confident of the comparisons between those means. Given the above reasons, I decided to keep my original rating for the paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mentioned that the potential risk of having any negative societal impact is low and there are no associated ethical risks, which I largely agree with.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "0sQlpfkZ5Do", "reviewer": "Reviewer_A7vb", "summary": "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. \n\nThe 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. \n\nThe authors experiment with several transfer-learning and Multi-task learning (MTL) approaches on the proposed benchmark tasks. \nThe 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. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper presents a set of tasks to benchmark transfer learning of algorithmic reasoning. This is an important problem and the proposed tasks would help further research in this area.\n2. The paper proposes modifications to the neural executor model that improves the performance on certain metrics\n3. The results and conclusions drawn by the paper about transfer learning methods are interesting and would be helpful to the community for future research in this area. \n\n\nConcerns, questions, and suggestions\n1. An analysis of the results is lacking. As mentioned, the results lead to some interesting conclusions, such as pertaining methods are ineffective compared to multi-task learning. The paper might benefit from some experiments that shed light on why this would be the case. Does some sort of catastrophic forgetting occur when the model is fine-tuned on a different task? And could this be better illustrated with an experiment?\n2. The results are hard to understand in the way they are presented. The reader is often required to compare numbers from different tables on different pages. Perhaps, a graph comparing the results would be more intuitive. If possible, the authors can add (in the caption), what the reader needs to look for in the results table. \n3. In line 301, the authors claim that the gradients are more stable due to MTL. Could the authors expand on this? \n4. Line 153 - delete repeated has\n\nOverall, I think the paper reaches an interesting result on the comparison of pretraining methods vs MTL for transfer learning for algorithmic reasoning. I feel the arguments of the paper would be bolstered by some analysis that better elucidates the reason for the claims. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the limitations and societal impact of the approach.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates how algorithms for which we have access to the execution trace can be leveraged to learn to solve similar tasks for which we do not have execution traces. The authors create a dataset that covers 9 algorithms and 3 different graph types to investigate transfer learning in two major classes of graph algorithm, parallel and sequential. They also introduce modifications to the existing NeuralExtractor model that improve its performance in some experimental settings.

The paper makes an interesting empirical discovery: according to their results, standard methods for transfer learning are ineffective in transferring algorithmic reasoning knowledge, while multi-task learning does effectively transfer this kind of knowledge. I think this observation is important to share with the community, particularly as it arises from experiments that Reviewer JA8z says "are extensive and cover many different settings." One possible concern with reliability of the finding is the large standard deviation in some of the results, as pointed out by Reviewer ZoqR.

A relevant issue raised by several reviewers is that the paper offered no analysis of why MTL is better than pre-training approaches for algorithmic transfer learning. In their response, the authors admit that they cannot provide a conclusive explanation for this observation, although they do argue for the exclusion of some standard hypotheses like catastrophic forgetting. They also conducted two more experiments during the review period that reveal more about why transfer learning might fail (although they don't prove their hypothesis on generalizing minima conclusively). However, I think it's fine for papers to identify important open questions and leave their answers as future work for the community. 

Some reviewers questioned the paper's technical novelty (the modelling innovation amounts only to a modified NeuralExtractor that extends prior work), but I don't think that's what this paper is really about. Its impact lies in the novelty of its empirical observations.

Finally, the authors pledged to address reviewers' concerns around the clarity of the results presentation and the detail of their model description. I'm confident that they can do this straightforwardly.

For these reasons, I lean towards accepting the paper even though its aggregate review score puts it slightly below the acceptance threshold.





Decision: Accept (Poster)