Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: Summary:

This paper uses message-passing neural networks to learn to predict which
nodes to update with what metadata. Experiments are shown that the algorithm
can learn to visit nodes in the same order as a breadth-first-search as well
as the Bellman-Ford shortest-path algorithm.

Feedback:

I'm not sure what problem this paper is trying to solve. We are provided
the graph and graph algorithm as input to the network so that we can
learn what the algorithm will do next? I'm not sure why this is a problem?
Are these algorithms badly written and need to be improved? Do we want to
learn how to execute graph algorithms in general?

I found the paper fairly hard to read and follow. I wish the
model were described all in one place and the related work also
in just one place. I think this paper would be greatly improved
by more work on explaining the motivation as well as more
clearly. I also feel the paper could be much stronger if it was grounded
in an existing problem others in the community might have.

Clarifications:

In page 4, I don't know what it means to execute these two algorithms
simulatenously?
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper investigates using GNNs to learn graph algorithms. It proposes a model which consists of algorithm-dependent encoder and decoder, and algorithm-independent processor. 
Authors try to learn BFS, Bellman-Ford and Prim algorithms on various types of random graphs. 
Experimental results suggest that MPNN with max aggregator outperforms other variants significantly in terms of generalization. 

Overall, this paper presents a solid contribution on learning graph algorithms using GNNs, despite the caveat for some clarifications on the model and experiments. 
Given these clarifications in an author response, I would be willing to increase the score.

Pros:

1, Although it is less satisfying to learn to solve graph problems where polynomial-time algorithms exist, I still appreciate the contribution of the paper, especially the algorithm-independent processor. It is one step forward to models which could learn meta-level representation of algorithms. The findings of this paper may suggest that different types of operators used in the GNN may have different inductive bias in learning different types of algorithms.

2, Experimental comparisons are adequate and convincing. The detailed analysis of empirical results also provide good explanation.

Cons & Suggestions:

1, Given the dynamic programming nature of the most of tasks, it is not that surprising that MPNN with max aggregation could solve them pretty well. What surprises me is that MPNN-mean / MPNN-sum could not generalize well (i.e., performance drops significantly on 50 and 100 nodes settings) on the reachability task. In my opinion, the reachability task could be easily handled by any diffusion/propagation based models including, e.g., MPNN, GCN, GAT, as long as the information is spread over the input graph. Could you explain why does this happen? 

2, Training details are sparse. If I understood correctly, the training of various GNNs is done by teacher forcing such that each step some supervised information collected from the underlying graph algorithms is provided to GNNs. However, it is not clear that what supervised information is exactly provided under each graph algorithm. It would be great to have a table to summarize what the input and supervised output information is for each graph algorithm. 

3, The processor is trained to learn multiple graph algorithms simultaneously. A natural question to ask is how does the performance change when you train the processor with different combinations of algorithms? What is the impact of correlations between different graph algorithms? Did you explore learning with graph algorithms following some sequential schedule, e.g., curriculum learning?

4, It would be great to provide more results on larger size graphs, e.g., trained on 20 nodes but test on 1000 or more nodes. I saw one set of experiments trained on 100 and test 1000 nodes in the appendix. More results along this line would make the paper more convincing on the generalization.

5, It would be great to discuss [1] as it also studies how to use GNNs to learn a special class of graph algorithms, i.e., probabilistic inference algorithms on graphs. It is shown in [1] that belief propagation algorithm could be seen as a specially constructed GNN. Interestingly, some well-known graph algorithms could be re-formulated as probabilistic inference algorithms, e.g., graph-cut could be reformulated as max-product [2].

[1] Yoon, K., Liao, R., Xiong, Y., Zhang, L., Fetaya, E., Urtasun, R., Zemel, R. and Pitkow, X., 2018. Inference in probabilistic graphical models by graph neural networks. arXiv preprint arXiv:1803.07710.
[2] Tarlow, D., Givoni, I.E., Zemel, R.S. and Frey, B.J., 2011, July. Graph Cuts is a Max-Product Algorithm. In UAI (pp. 671-680).

======================================================================================================

Thanks for the thorough response! It resolves my concerns. I improved my score.

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: The paper suggests training neural network to imitate graph algorithms in a more fine-grained way than done before: by learning primitives and subroutines rather than the final output. The paper makes quite a strong case for the advantage of this approach, citing the fact that many graph algorithms share subroutines, which could simplify learning and support joint training and transfer learning. The experiments are detailed an elaborate.

The main weakness I see is the size of the graphs in the experiments. They are mainly limited to graphs with up to 100 nodes, with additional brief results for 1000 nodes in the appendix. These sizes are so small so as to raise doubts if the reported accuracy results would indeed scale, or whether they might require a significantly heavier network architecture. Moreover graphs of this size do not actually pose any difficulty for classic graph algorithms, that would justify invoking such heavy cannons like neural networks.

Nonetheless, I find this to be a conceptually strong paper with interesting ideas and thorough experiments (which in the least establish proof of concept; I am willing to accept leaving the issue of handling larger graphs to future work). I think the paper should be accepted.

Other comments:
1. The legend font in Figure 3 is to small (I am positively unable to read it off page) and the MPNN-sum plot is invisible in print. I hope the authors can reproduce the plots more clearly.
2. I don't quite see the point in Appendix A, brief as it is. It apparently just states the fact that if two random variables share mutual information then knowing one reduces the entropy of the other. This is rather obvious both intuitively and formally.
review_title: Official Blind Review #3

Meta-review: It seems to be an interesting contribution to the area. I suggest acceptance.
Decision: Accept (Poster)