Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 

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. 

main_review: Strengths:
1. 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.
2. The paper proposes modifications to the neural executor model that improves the performance on certain metrics
3. 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. 


Concerns, questions, and suggestions
1. 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?
2. 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. 
3. In line 301, the authors claim that the gradients are more stable due to MTL. Could the authors expand on this? 
4. Line 153 - delete repeated has

Overall, 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. 


limitations_and_societal_impact: The authors address the limitations and societal impact of the approach.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: I am leaning towards rejecting the paper. My main concerns are the potential impact and technical novelty.

Strengths:
* The experiments are extensive and cover many different settings.
* The experiments have some interesting results. It is interesting to see that transfer learning and multi-task learning have quite different results.

Weaknesses:
* 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).
* 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.
* 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.

Suggestions:
* 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.
* 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. 

Other minor suggestions/questions:
* 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.
* Is there a reason why L1 loss is used instead of L2?

**Update after author response:**

The 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.

However, 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.
limitations_and_societal_impact: The authors have addressed the limitations and potential negative societal impact. I do not have anything to add.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

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.

I 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".

There 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. 

The 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.

------------------------

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

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.
main_review: ### Originality: 3/5
Although 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. 

### Quality: 3/5
The 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.

### Clarity: 3/5
The 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". 

### Significance: 3/5
The 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. 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Update: 

I 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. 
limitations_and_societal_impact: Limitations:
1. What is the multi-task learning performance on non-linear algorithms, such as SCC?
2. What is the transferability between algorithm types, such as transferring PATH to SCC?
To improve:
3. Better description of NeuralExecutor and NeuralExecutor++.
4. Unify the evaluation metric of  Key and Predecessor, either both "lower is better" or "higher is better".
review_title: null

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)