Neural Execution of Graph Algorithms
Authors: Petar Veličković
Rex Ying
Matilde Padovano
Raia Hadsell
Charles Blundell
Venue:  (2020)
Keywords: Graph Neural Networks
Graph Algorithms
Learning to Execute
Program Synthesis
Message Passing Neural Networks
Deep Learning

Abstract: Graph Neural Networks (GNNs) are a powerful representational tool for solving problems on graph-structured inputs. In almost all cases so far, however, they have been applied to directly recovering a final solution from raw inputs, without explicit guidance on how to structure their problem-solving. Here, instead, we focus on learning in the space of algorithms: we train several state-of-the-art GNN architectures to imitate individual steps of classical graph algorithms, parallel (breadth-first search, Bellman-Ford) as well as sequential (Prim's algorithm). As graph algorithms usually rely on making discrete decisions within neighbourhoods, we hypothesise that maximisation-based message passing neural networks are best-suited for such objectives, and validate this claim empirically. We also demonstrate how learning in the space of algorithms can yield new opportunities for positive transfer between tasks---showing how learning a shortest-path algorithm can be substantially improved when simultaneously learning a reachability algorithm.

Published as a conference paper at ICLR 2020
NEURAL EXECUTION OF GRAPH ALGORITHMS
Petar Veličkovié
Rex Ying" Stanford University
Matilde Padovano"
DeepMind
University of Cambridge
petarvegoogle.com
rexy i texyingesee wtgestaaoorrd..e...oo edu
mp8610 camm. ac. uk
Raia Hadsell
Charles Blundell DeepMind @blunde:1@google.co
DeepMind
raia@google.com
ABSTRACT
Graph Neural Networks (GNNs) are a powerful representational tool for solving problems on graph-structured inputs. In almost all cases so far, however, they have been applied to directly recovering final solution from raw inputs, without Here, instead, we
explicit guidance on how to structure their problem-solving focus on learning in the space of algorithms: we train several state-of-the-art GNN architectures to imitate individual steps of classical graph algorithms, parallel (breadth-fire firstt search, Bellman- Ford)) as well as sequential (Prim's 's algorithm). As graph algorithms usually rely on making discrete decisions within neighbourhoods, we hypothesise that maximisation based message passing neural networks are best- suited for such objectives, and validate this claim empirically. We also demonstrate how learning in the space of algorithms can yield new opportunities for positive transfer between tasks-showing how learning shortest-path algorithm can be substantially improved when simultaneously learning reachability algorithm.
INTRODUCTION
multitude of important real-world tasks can be formulated as tasks over graph-structured inputs, such as navigation, web search, protein folding, and game-playing. Theoretical computer science has successfully discovered effective and highly influential algorithms for many of these tasks. But many problems are still considered intractable from this perspective.
Machine learning approaches have been applied to many of these classic tasks, from tasks with known polynomial time algorithms such as shortest paths (Graves et al. 2016 Xu et al. 2019) and sorting (Reed & De Freitas 2015), to intractable tasks such as travelling salesman Vinyals et al. 2015 Bello
et al. 2016) Kool et 2018), boolean satisfiability (Selsam et al.) 2018: Selsam & Björner 2019).
and even probabilistic inference (Yoon et al. (2018). Recently, this work often relies on advancements
in graph representation learning (Bronstein al. 2017 Hamilton et al. 2017 Battaglia al.
2018
with graph neural networks (GNNs) (Li et al. 2015] Kipt & Welling [016:] Gilmer et al.
2017
Veličković et 2018). almost all cases so far, ground-truth solutions are used to drive learning.
giving the model complete freedom to find a mapping from raw inputs to such solution!
Many classical algorithms share related subroutines: for example, shortest path computation (via the Bellman- Ford (Bellman, 1958) algorithm) and breadth- first search both must enumerate sets of edges adjacent to a particular node. Inspired by previous work on the more general tasks of program synthesis and learning to execute (Zaremba & Sutskever 2014 Kaiser & Sutskever] 2015 Kurach et al.) 2015; Reed & De Freitas] [2055] [Santoro et al. 2018), we show that by learning several algorithms simultaneously and providing supervision signal, our neural network is able to demonstrate positive knowledge transfer between learning different algorithms. The supervision signal is driven by how a known classical algorithm would process such inputs (including any relevant intermediate outputs), providing explicit (and reusable) guidance on how to tackle graph-structured problems. We call this approach neural graph algorithm execution.
Work performed while the author was at DeepMind. We note that there exist good reasons for choosing this approach, e.g. case of optimisation.

---

Published as a conference paper at ICLR 2020
Given that the majority of popular algorithms requires making discrete decisions neighbourhoods (e.g. "which edge should be taken?"), "), we suggest that a highly suitable architecture for this task is a cressage-passingg neural network (Gilmer al. 2017) with maximisation aggregator- claim verify, demonstrating clear performance benefits for simultaneously learning breadth-first search for reachability with the Bellman-Ford algorithm for shortest paths. We also verify its applicability to sequential reasoning, through learning Prim's algorithm (Prim) 1957) for minimum spanning trees.
Note that our approach complements Reed & De Freitas (2015): we show that a relatively simple graph neural network architecture is able to learn and algorithmically transfer among different tasks, do require explicitly denoting subroutines, and tackle tasks with superlinear time complexity.
PROBLEM SETUP
2.1 GRAPH ALGORITHMS
We consider graphs G = (V, E) where V is the set of nodes (or vertices) and E' is the set of edges (pairs of nodes). We will consider graphs for two purposes: 1) part of the task to be solved (e.g.. the graph provided as input to breadth first search), 2) as the input to a graph neural network.
A graph neural network receives sequence of T E N graph-structured inputs. For each element of the sequence, we will use a fixed G and vary meta-data associated with the nodes and edges of the graph in the input. In particular, to provide graph G (V, as input to graph neural network, each node E V has associated node features x(60 E N2 where E (1....,7) denotes the index in the input sequence and N₂ is the dimensionality of the node features. Similarly, each edge (i.j) E E
(1) has associated edge features Eij E N. where N₂ is the dimensionality the edge features. At each step, the algorithm produces node-level outputs V," E RR Some of these outputs may then be reused as inputs on the next step; i.e., x ((++1 may contain some elements of y,
(()
2.2 LEARNING TO EXECUTE GRAPH ALGORITHMM
We are interested in learning a graph neural network that can execute one or more of several potential algorithms. The specific algorithm be executed, denoted A, is provided as an input to the network. The structure of the graph neural network follows the et al. 2018). First we will describe the encode-pree wowedddproeess-decoeee architecture and then describe the specific parameterisations that are used for each sub-network. The relation between the variables used by the graph algorithm and our neural algorithm executor setup is further illustrated in Figure [|
paradigm (Hamrick)
For each algorithm A we define encoder network fA. It is applied to the current input features and {t) previous latent features Ti [((t-1) (with [T(0) 0) produce encoded impuls, z as such:
(t) fa( ((
The encoded inputs are then processed using the processor network P. The processor network shares its parameters among all algorithms being learnt. The processor network takes as input the encoded inputs (t) hev and edge features E(t)
{et)) JoeR and produces output latent node
features, (t) [M] E RRKK Jiev:
H (t) = P(Z
(2)
The node and algorithm specific outputs are then calculated by the decoder-network, gAi
J (a(" (t) ((())
(3)
Note that the processor network also needs to make decision whether to terminate the algorithm. This is performed by an aegorithm-sppciffi termination network, TA, which provides the probability of termination (t)) (fter applying the logistic sigmoid activation a-as follows:
(t) (T's (H*) H())
(4)
where H [V] Eiey [(0)
is the average node embedding. If the algorithm hasn't 't terminated (e.g.
(1) 7()) 0.5) the computation of Eqns. 1 is repeated with parts of j7 potentially reused in (1(11)
2

---

Published as a conference paper at ICLR 2020
i0
(
2
10
20
34
of
z00)
e
11
R00
<(1]
612
A011
- C24
16
22
222
Figure 1: A visualisation of the relation between local computations of graph algorithms (left) and the neural graph algorithm executor (right). In graph algorithms, node values D, (() (e.g. reachability, shortest-path distance) are updated at every step of execution. Analogously, the node values are predicted by the neural executor from the hidden representation (1()) computed via message passing.
In our experiments, all -eeeedee-deeedeent networks, fA, 9A and T'. are all linear projections, placing the majority of the representational power of our method in the processor network P. As we would like the processor network to be mindful of the structural properties of the input, we employ graph neural network (GNN) layer capable of exploiting edge features P. Specifically, we compare graph attention networks (GATs) (Veličković et al. 2018). (Equation 5 left) against message- pesssag-passing
neural networks (MPNNs) (Gilmer al. 2017 (Equation right):
T ReLU
Σ a
W (1)
T = U
M
(A)ER
GAEEE
where W a learnable projection matrix, a is an attention mechanism producing scalar coefficients, while M and U are neural networks producing vector messages. Q is elementwise aggregation operator, such as maximisation, summation or averaging. We use linear projections for M and U.
Note that the processor network P is algorithm--gnoste and can hence be used execute several algorithms simultaneously. Lastly, we note that the setup also easily allows for including edge-level outputs, and graph-level inputs and croputs-however these were not required in our experiments.
EXPERIMENTAL SETUP
Graph generation To provide our learner with wide variety of input graph structure types, we follow prior work (You et al. 2018 2019) and generate undirected graphs from seven categories:
Ladder graphs;
2D grid graphs;
Trees, uniformly randomly generated from the Prüfer sequence;
Erdös-Rényí (Erdös & Rényi 1960) graphs, with edge probability min
(~ 0.5):
log, V
Barabási-Alban (Albert & Barabási 2002 graphs, attaching either four or five edges to every incoming node;
4-Community graphs-fin first generating four disjoint Erdös-Rémp Rénnsi graphs with edge probabil- ity 0.7, followed by interconnecting their nodes with edge probability 0.01;
4- Caveman (Watss 1999) graphs, having each of their intra-clique edges removed with probability 0.7, followed by inserting 0.025|V| additional shortcut edges between cliques.
We additionally insert a self-edge every node in the graphs, in order support easier retention of self-information through message passing. Finally, we attach a real-valued weight to every edge, drawn uniformly from the range (0.2, 1). These weight values serve the sole edge features, e for
(()
3

---

Published as a conference paper at ICLR 2020
10
M
20
(6)
M
(0)
supervise
100
min SS.MER
up + Cun
Figure 2: Illustrating the aligmment of one step of the Bellman-Foore algorithm (left) with one step of a message passing neural network (right), and the supervision signal used for the algorithm learner.
all steps Note that sampling edge weights in this manner essentially guarantees the uniqueness of the recovered solution, simplifying downstream evaluation. We also ignore corner-case inputs (such as negative weight cycles), leaving their handling to future work.
We aim to study the algorithm execution task from a "programmer" perspective: human experts may manually inspect only relatively small graphs, and any algorithms derived from this should apply to arbitrarily large graphs. For each category, we generate 100 training and 5 validation graphs of only 20 nodes. For testing, 5 additional graphs of 20, 50 and 100 nodes are generated per category.
Parallel algorithms We consider two classical algorithms: breadth-first search for reachability, and the Bellman- Ford algorithm (Bellman 1958) for shortest paths. The former maintains single-bit value each node, determining whether said node is reachable from a source node, and the latter maintains scalar value in each node, representing its distance from the source node.
In both cases, the algorithm is initialised by randomly selecting the source node, s. As the initial input to the algorithms, I (1) we have:
BFS x 11
f1 i ==
Bellman Fallman-Ford: x! So
i ==
(6)
+
+00
+
This information is then propagated according to the chosen algorithm: a node becomes reachable from s if any of its neighbours are reachable from and we may update the distance to a given node as the minimal way reach any of its neighbours, then taking the connecting edge:
aith =1
(1+1) BFS: 2
((+1) B-F 2
(00 2 min 2
(0)
=1
min
ejf
"GAEE"
otherwise
For breadth-first search, no additional information is being computed, hence y! =x ((+1) Addition- ally, at each step the Bellman-Fort algorithm may compute, for each node, the "predecessor" node, pi in the shortest path (indicating which edge should be taken to reach this node). This information ultimately used reconstruct shortest paths, and hence represents the crucial output:
i
Bellman-Ford p,
argmin (0 + +e d.(..))E
i +
(8)
Hence, for Dellman-Fordd,
((+1) where is concatenation. To provide numerically stable value for +0o, we set all such entries to the length the longest shortest path in the graph + 1.
(1)
p; ||= ||x;+t1]
We learn to execute these two algorithms simultaneously-at each step, concatenating the relevant ,i() (()) and 17 values for them. As both of the algorithms considered here (and most others) rely
4

---

Published as a conference paper at ICLR 2020
discrete decisions over neighbourhoods, learning to execute them should be naturally suited for the MPNN with the max-aggregatue a claim which we directly verify in the remainder of this section.
Sequential algorithms Unlike the previous two algorithms, single iterations of many classical graph algorithms will specifically focus on one node at a time-very often the case with constructive tasks. We seek to demonstrate that neural graph algorithm execution paradigm aligns well with this setting too, and in this context we study Prim's 's algorithm (Prim 1957) for minimum spanning trees.
Prim's 's algorithm maintains partially constructed minimum spanning tree singleton tree consisting of only a source node, 8. At each step, Prim's 's algorithm searches for a new node to connect to the chTechosen so that the edge attaching it the tree is the lightest possible:
it is
f1 i=s 1
Prim x2 0 i i
(1+1) Prim x
argmin
min
jk
(9)
j s.t. 2/== =o bat o
otherwise
Once the new node selected, the algorithm attaches to the MST via this edge similarly to Bellman-Food Ford, we can keep track of predecessor nodes, Pi (9)
i=s
1)
i + S I
(t)
=1
Prim Pi
argmin
(t)
a (t) = 0 0 a ((+1) =1
(10)
jst. =1
(undefined)
otherwise
In Equations 10 the boxed updates are the only modifications the state of the algorithm at step t- centering only on the selected node to attach to the MST. Once again, the algorithm requires discrete decisions based on neighbourhood edge weights, hence we expect outperformance of MPNN-max.
For a visualisation of the expected alignment between graph algorithm and our neural graph executors, refer to Figure 2 We provide an overview all of the inputs and supervision signals used here for the executor in Appendix A
Neural network architectures To assess the comparative benefits of different architectures for the neural algorithm execution task, we consider many candidate networks executing the computation of Equations [ especially the processor network P: For the MPNN update rulc, we consider maximisation, mean and summation aggregators. For the GAT update rule, consider the originally proposed attention mechanism of Velićković et al. (2018), as well as Transformer attention (Vaswani al., 2017) Additionally for GAT, we consider also attending over the full graph-adding a second attention head, only acting on the non-edges of the graph (and hence not accepting any edge features). The heads' features are then concatenated and passed through another linear layer.
Analogously to our expectation that the best pesst-erforming MPNN rule will perform maximisation, we attempt force the attentional coefficients of GAT be as sharp as aussible-applying either an entropy penalty to them (as in Ying et al. (018)) or the Gumbel softmax trick (Jang et al. 2016).
We perform additional sanity check ensure that GNN-like architecture is necessary in this case. Prior work (Xu et al. 2019) has already demonstrated the unsuitability of MLPs for reasoning tasks like these, and they will not support variable amounts of nodes. Here, instead, we consider an LSTM (Hochreiter & Schmidhuber] 1997) architecture into which serialised graphs are fed (we use an edge list, in a setup similar to (Graves et al. 2016)).
In all cases, the neural networks compute a latent dimension of K = 32 features, and are optimised using the Adam SGD optimiser (Kingma & Ba 2014) on the binary cross-entropy for the reacha- bility predictions, mean squared error for the distance predictions, categorical cross-entropy for the predecessor node predictions, and binary cross- cross-entropy for predicting termination (all applied simul- taneously). We use initial learning rate of 0.0005, and perform early stopping the validation accuracy for the predecessor node (with a patience of 10 epochs). If the termination network T, does not terminate the neural network computation within [V] steps, it is assumed terminated at that point.
5

---

Published as a conference paper at ICLR 2020
Table Accuracy of predicting reachability at different test-set sizes, trained on graphs of 20 nodes. GAT correspond to the best GAT setup as per Section 3 (GAT-full using the full graph).
Reachability (mean step accuracy last-step accuracy)
Model
20 nodes
50 nodes
100 nodes
LSTM (Hochreiter& & Schmidhuber
1997
81.97% / 82.29%
88.35% 91.49%
68.19% / 63.37%
GAT Veelčkooii et al. 2018)
93.28% 99.86%
100.0% % 85.76% 91.83%
93.97%
92.34% 199.97 % 88.98% /9151%
GAT-full (
(Vaswam el al. 2017
78.40% / 77.86%
MPNN-mean (Gilmer et al
2017)
100.0% 100.0 %
61.05%
57.89%
27.17% 21.40%
MPNN-sum Gilmer cl al.
201
99.66% 100.0 %
94.25%
100.0 %
94.72% 98.633
MPNN-max Gilmer al.
2017)
100.0% 100.0% %
100.0% 100.0% %
99.92% / 999.80%
Table 2: Accuracy of predicting the shortest-path predecessor node at different test-set sizes. (cur- riculum) corresponds to a curriculum wherein reachability is learnt first. (no-reach) corresponds to training without the reachability task. (no-algo) corresponds to the classical setup of directly training on the predecessor, without predicting any intermediate outputs or distances.
Predecessor (mean step accuracy / last-step accuracy)
Model
20 nodes
50 nodes
100 nodes
LSTM (Hochreiter & Schmidhuber
1997)
47.20%
47.04%
36.34% 35.24%
27.59% 27.31%
GAT (Veličković et al.
2018)
64.77%
60.37%
52.20%
49.71%
47.23%
44.90%
GAT-full Vaswam al.
2017
67.31% 63.99%
50.54% 48.51% %
43.12% 41.80%
MPNN-mean Gilmer al.
2017)
93.83% 93.20%%
58.60%
58.02%
44.24%
43.93%
MPNN-sum Gilmer el al.
2017)
82.46% 80.49%
54.78%
52.06%
37.97%
37.32%
MPNN-max Gilmer et al.
2017
97.13% / 96.84 %
94.71 % 93.88 %
90.91 % 88.79% %
MPNN-max (curriculum)
95.88% 195, 55.5
91.00% 88.74%
84.18% 83.16%
MPNN-max (no-reach)
82,40% 78.29%
78.79 18.79% 77.533
81 $1.04% 81.06%
MPNN-max (no-algo)
78.97% 95.56%
83.82% 85.87%
79.77% 78.84%
For Prim's s algorithm, as only one node at a time is updated, we optimise the categorical cross-entropy of predicting the next node, masked across all the nodes not added to the MST yet.
should be noted that, when learning to execute Bellman-Ford and Prim's 's algorithms, the prediction (t) of Pr is performed by scoring each node-pair using an edge-wise scoring network (a neural network
predicting a scalar score from (((0) | (( followed by a softmax over all neighbours of i.
RESULTS AND DISCUSSION
Parallel algorithm execution In order to evaluate how faithfully the neural algorithm executor replicates the two parallel algorithms, we propose reporting the accuracy of predicting the reachabil- ity (for breadth-first search; [a. as well as predicting the predecessor node (for Bellman-Ford We report this metric averaged across all sleps i (to give sense of how well the algorithm is imitated across time), as well as the last-step performance (which corresponds to the final solution). While it is not necessary for recovering the final answer, we also provide the mean squared error of the models on the Bellman-Fort distance information, as well as the termination accuracy (computed each step separately) (pparatel)-avvrragee across all timesteps- in Table 3
Table 2
The results confirm our hypotheses: the MPNN-me -ax model exhibits superior generalisation perfor- mance both reachability and shortest- path predecessor node prediction. Even when allowing for hardening the attention of GAT-like models (using entropy or Gumbel softmax), the more flexible
Note that the BFS update rule is, in isolation, fully learnable by all considered GNN architectures. Results here demonstrate performance when learning to execute BFS simultaneously with Fellman-FFord Specifically, in this regime, MPNN-sum's messages explode when generalising to larger sizes, while MPNN-mean dedicates most of its capacity to predicting the shortest path (ef. Tables 2

---

Published as a conference paper at ICLR 2020
Table 3: Mean squared error for predicting the intermediate distance information from Bellman-Ford. and accuracy of the termination network compared to the ground-truth algorithm, averaged across all timesteps. (curriculum) corresponds to a curriculum wherein reachability is learnt first. (no-reach) corresponds to training without the reachability task.
B-F mean squared error / mean termination accuracy
Model
20 nodes
50 nodes
100 nodes
LSTM (Hochreiter & Schmidhuher
1997
3.857 83.43%
11.92 / 86.74%
74.36 83.55%
GAT Vellčković et al.
2018)
43.49/ 85.33%
123.1 84. 848 28.89/ 75.5 %
183.6 82.16%
GAT-full
Vaswani ct a
2017)
7.189/ / 77. .14
58.08 77.30%
MPNN-mman Gilmer el al.
2017
0.021 / 98.57%
23.73 89.29%
91.58/ 86.81%
MPNN-sum Gilmer et al.
2017
0,156 / 98 09%
4,745 88 11% %
+00 / 87.71 17.71% %
MPNN-max
Gilmer et al.
2017
0.005 98 89%
0.013 / 98.58 %
0.238 97.82% %
MPNN-max (curriculum)
0.021 98.99 %
0.351 96.34%
3.650 92.34%
MPNN-max (no-reach)
0.452/ / 10.18%
2.512 91.77%
2.628 85.22%
Table 4: Shortest-part path predecessor accuracy of the MPNN-max model trained jointly with the reachability objective on 20-node graphs, different test graph sizes (up to 75x larger).
MPNN-max predecessor prediction
Metric
20 nodes
nodes
100 nodes
500 nodes
1000 nodes
1500 nodes
Mean step accuracy
97.13%
94.71%
90.91%
83.08%
77.53%
74.90%
Last-step accuracy
96.84%
93.88%
88.79%
76.46%
72.74%
67.66%
computational model of MPNN is capable of outperforming them. The performance gap predicting the predecessor also widens significantly as the test graph size increases.
Our findings are compounded by observing the mean squared error metrie on the intermediate result: with the MPNN-max being the only model providing a reasonable level of regression error at the 100- node generalisation level. It further accentuates that, even though models like the MPNN-sum model may also learn various thresholding functions-as demonstrated by (Xu et al. 2018) aggregating messages in this way can lead outputs of exploding magnitude, rendering the network hard to numerically control for larger graphs.
We perform two additional studies, executing the shortest-path prediction on MPNN- mmx without predicting reachability, and without supervising on any intermediate algorithm computations that is, learning to predict predecessors (and termination behaviour) directly from the inputs, (1) Note that this is the primary way such tasks have been tackled by graph neural networks in prior work. We report these results as no-reach and no-algo in Table 2 respectively.
Looking at the no-reach ablation, we observe clear signs of positive knowledge transfer occurring between the reachability and shortest-pale tasks: when the shortest path algorithm is learned in isolation, the predictive power of MPNN-max drops significantly (while still outperforming many other approaches). In Appendix B we provide brief theoretical insight to justify this. Similarly, considering the no-algo experiment, we conclude that there is a clear benefit to supervising on the distance information-giving an additional performance improvement compared to the standard approach of only supervising on the final downstream outputs. Taken in conjunction, these two results provide encouragement for studying this particular learning setup.
Lastly, report the performance of curriculum learning (Bengio et al. 2009) strategy (as curriculum): here, BFS is learnt first in isolation (to perfect validation accuracy), followed by fine- tuning on Bellman-Foor Fordd We find that this approach performs worse than learning both algorithms simultaneously. and as such we do not consider it in further experiments.
Desirable properties of the MPNN- -ax as algorithm executor persist when generalising larger graphs, as we demonstrate in Table demonstrating favourable generalisation on graphs up to 75 as large the graphs originally trained on. We note that our observations also still hold
7

---

Published as a conference paper at ICLR 2020
Table The predictive performance of MPNN-max on 100-node graphs, after training on 20-node graphs of a particular type (Erdōs-Rényi, or trees).
Reachability
Predecessor
Graph type
From Erdös-Rényi
From frees
From -rdds-Rényi
From frees
Ladder
93.16% 93.98%
99.93% / 99.67%%
76.63% 65.94%
94.99% 92.55%
2-D Grid
87.05% 92.86%
99.85% / 99.32%%
70.75% 79.50%
94.06% / /91339%
Tree
82.72% 82.07%
99.92% 99.622%
70.16% 63.26%
98.44% 997.33%
Erdás-Rén
100.0% 100.0%
100.0%
100.0%
96.17% / 193, 94%
91.11% / 85 $5.94%
Barabási-Albers
100.0%
100.0%
100.0%
100.0%
94.91% 1 92.90%%
83.90% 75.79%
4 Community
100.0%
1000%
100.0%
100.0%
90.01%
86.38%
75.88% 64.04%
4 Caveman
100.0%
100.0%
100.0%
100.0%
91.55% 90.04%
80.02% 72.06%
10901
Figure 3: The per-step algorithm execution performances in terms of reachability accuracy (left), distance mean-squared saaandd eтror (middle) and predecessor accuracy (right), tested on 100-node graphs after training on 20-node graphs. Please mind the scale of the MSE plot.
when training on larger graphs (Appendix C.
We also find that there is significant overfitting to particular input graph category however we do provide an in-depth analysis of per-category performance in Appendix
Additional metrics The graphs we generate may be roughly partitioned into two types based on their local regularity-peecfically the ladder, grid and tree graphs all exhibit regular local structure, while the remaining four categories are more variable. As such, we hypothesise that learning from graph of one such type only will exhibit better generalisation for graphs of the same type. We verify this claim in Table where we train either only Erdōs-Rénn Rényi graphs or trees of 20 nodes, and report the generalisation performance on 100-node graphs across the seven categories. The results directly validate our claim, implying that the MPNN-max model is capable of biasing itself to the structural regularities found in the input graphs. Despite this bias, the model still achieves generalisation performances that outperform any other model, even when trained on the full dataset.
Further, we highlight that our choices aggregation metrics may not be the most ideal way to assess performance of the algorithm executors: the last-step performance provides indication of faithfulness to the original algorithm, while the mean-step performance may be artificially improved by terminating the algorithm single-numbl metric to future work, we also decide to compound the results in Tables [ by also plotting the test eaachability/preeeeess accuracies for each timestep of the algorithm individually (for 100-node graphs): refer to Figure
latter point. While here leave the problem of determining better
Such visualisations help identify cases where neural executors "cheating", by e.g. immediately predicting every node is reachable: in these cases, we can see a tharacteristic-inittalll weak but steadily pwwhiingperffrmannce curve. It also further solidifies the outperformance of MPNN-max.
Lastly, in Appendix D we apply the recently proposed GNNExplainer (Ying et al. 2019) model to detecting which graph substructures contributed the most to certain predictions.
Sequential algorithm execution cuting Prim's algorithm within Table 6 We provide the accuracy of predicting the next MST node
We demonstrate results for all considered architectures on exe-
8

---

Published as a conference paper at ICLR 2020
Table 6: Accuracy of selecting the next node to add the minimum spanning tree, and predicting the minimum spanning tree predecessor node- at different test-set sizes. (no-algo) corresponds to the classical setup of directly training on the predecessor, without adding nodes sequentially.
Accuracy (next MST node / MST predecessor)
Model
20 nodes
50 nodes
100 nodes
LSTM (Hochreiter & Schmidhuber
1997)
11.29% 52.81%
3.54% / 47.74%
2.66% / 40.89%
GAT Vellčkovvić et al.
2018)
27.94% 61.74% 29.94% 64.27%
22.11% % / /8.6686.6666 88.66%
10.97% 53.80%
GAT-full Vaswani
18.91 % 53.34%
14.83% 51.49%
MPNN- mean (Gilmer al.
2017
90.56% / 93.63 %
52.23% 88.97%
20.63%
80.50%
MPNN-sum
Gilmer al.
48.05%
07.41%%
24.40% 61.83%
31.60%
43.98%
MPNN- mmx
Gilmer et al.
2017
87.85% / 193.23%
63.89 % 91.14%
41.37 %
90.02% %
MPNN-ma max (no-algo)
771.02%
449.83%
/23.61%
(computed against the algorithm's 's "ground-truth" ordering), well as the accuracy of reconstructing the final MST (via the predecessors)
As anticipated, our results once again show strong generalisation outperformance of MPNN-max We additionally compared against a non-sequential version (no-algo), where the MPNN-max model was trained directly predict predecessors (without requiring sequentially chosing nodes). This resulted in poor generalisation to larger graphs, weaker than even the LSTM sequential baseline.
The insights from setup verify that our neural graph execution paradigm is applicable sequential algorithm execution as well sull-ssusttaniilly expanding its range of possible applications.
CONCLUSIONS
In this manuscript, have presented the neural graph algorithm execution task, prior approaches- optimise neural networks to imitate individual steps and all intermediate outputs of classical graph algorithms, parallel well as sequential. Through extensive on the tasks of reachability, shortest paths and minimum spanning trees-we have determined message passing neural networks, and identified
highly suitable architecture maximisation-baat clear benefits for multi-task learning and positive transfer, as many classical algorithms share related subroutines. We believe that the results presented here should serve as strong motivation for further work in the area, attempting to learn more algorithms simultaneously and exploiting the similarities between their respective subroutines whenever appropriate.
REFERENCES
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzaez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01266 2018.
Richard Bellman. On routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforeement learning. arXiv preprint 1rXiv:1611.09900 2016.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pp. 41-48. ACM, 2009.
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):18 422 2017.

---

Published as a conference paper at ICLR 2020
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprini vrXXiv:704.01222 2017.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471, 2016.
William Hamilton, Rex Ying, and Jure Leskovec, Representation learning on graphs: Methods and applications. arXiv preprint (00.00//7005558 2017.
Jessica B Hamrick, Kelsey Allen, Victor Bapst, Tina Zhu, Kevin R McKee, Joshua B Tenenbaum, and Peter W Battaglia. Relational inductive bias for physical construction in humans and machines. arXiv preprint arXiv: 00200,, 2018.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizatiion with gumbel-softmax. arXiv preprint 1rXiv:/611.000 144, 2016.
Eukasz Kaiser and lly Sutskever. Neural gpus learn algorithms. arXiv preprint 15 2015.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6990, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint wrxivv1803.08441 2018.
Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-access machines. arXiv preprint arXiv:1511.000 2015.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint
Robert Clay Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal, 13896):38991144 1957.
Scott Reed and Nando De Freitas. Neural programmeerinneerretees arXiv preprint arXiv:1511.06279 2015.
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 Advances in Neural Information Processing Systems, pp. 7299-7310, 2018.
Daniel Selsam and Nikolaj Bjørner. Guiding tigh-performanc sat solvers with unsat-core predictions. In International Conference on Theory and Applications of Satisfiability Testing, pp. 336-353. Springer, 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. arXiv preprint 1802 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
10

---

Published as a conference paper at ICLR 2020
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
URL htR/httpss///peeeeeeees net. net/
Eorum 1
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Duncan J Watts. Networks, dynamics, and the small-world phenomenon. American Journal of sociology, 105(():493-533 527, 1999.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008220 2018.
Keyulu Xu, Jingling Li, Mozhi Zhang. Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? arXiv preprint 1rXiv:1905.33211, 2019.
Rex Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. arXiv preprint arXiv: 1806. 00.008444 2018.
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnn explainer: A tool for post-hoc explanation of graph neural networks. arXiv preprint arXiv:1903003894 2019.
KiJung Yoon, Renjie Liao, Yuwen Xiong, Lisa Zhang, Ethan Fetaya, Raquel Urtasun, Richard Zemel, and Xaq Pitkow. Inference in probabilistic graphical models by graph neural networks. arXiv preprint arXiv:1803.07711 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: A deep generative model for graphs. arXiv preprint arXiv:1802.08777. 2018.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awarc graph neural networks. arXiv preprint arXiv: 04817, 2019.
Wojeiech Zaremba and Ilya Sutskever. Learning execute. arXiv preprint arXiv: arXiv:1410.444 1410.461,, 2014.

---

Published as a conference paper at ICLR 2020
Table 7: Summary of inputs and supervision signals of the three algorithms considered.
Algorithm
Inputs
Supervision signals
(t+1)
Breadth-first search
; is reachable from s S hops?
has the algorithm terminated?
( shortest distance from s to
Bellman-Ford
(using I hops)
p predecessor of
shortest path tree (in S hops)
Prim's algorithm
< is node in the (partial) MST
(built from after steps)?
predecessor of in the partial MST
A SUMMARY OF ALGORITHM INPUTS AND SUPERVISION SIGNALS
To aid clarity, within Table 7 we provide an overview of all the inputs and outputs (supervision signals) for the three algorithms considered here (breadth-fin first search, Bellman -Ford and Prim).
B THEORETICAL INSIGHTS
We provide brief theoretical insight into why learning to imitate multiple algorithms simultaneously may provide benefits to downstream predictive power.
Our insight comes from an information-thenne -hheorettcc that both operate on the same input, and produce outputs yA and yB, respectively. We consider the task learning to execute A (that is, predicting μa from æ), with and without yn provided We operate on the further assumption that A and B share subroutines-implye information content preserved between VA and yp- Formally, we say that the conditional mutual information of the corresponding random variables, [YY:; YB X)), is positive.
perspective. Consider two algorithms, A and B,
that, knowing there
Expanding out the expression for (Y YB [X), denoting Shannon entropy by H, we obtain:
Ya H(Ya|X) + H(ys XX) H(YA.Ya|X)
H(Ya(X) + H(BB X) (H(YalV,, + H(Yb(X)
H(YAlX) - -Y.
(1I)
As ( > 0, we conclude ((Ya(X) > B(Y X); therefore, providing yB upfront strictly reduces the information -hoomation--heoreticc uncertainty in yA, thus making it potentially more suitable for being learned by optimisation techniques.
C LARGER-SCALE STUDIES
To investigate the models' behaviour when generalising to larger graphs, we conduct experiments for executing the two parallel algorithms (BFS and Bellman-Ford) when training on graphs with 100 nodes, and testing graphs with 1000 nodes, reported in Table These results further solidify the outperformance of MPNN-based models, even outside the studied "programmer" regime.
D PERFORMANCE PER GRAPH TYPE
As our training and testing graphs come from specific set of seven categories, it is natural to study the predictive power of the model conditioned on the testing category. Firstly, in Table 9 we provide
Note that here we'ne re implicitly assuming that ye is trivial enough be fully learnt on its and thus be provided the model. This strict way of assuming that B is "simpler" algorithm than A.
12

---

Published as a conference paper at ICLR 2020
Table 8: Results of scaling to large graphs with 1000 nodes, while training on graphs with 100 nodes.
Model
Reachability
Predecessor
LSTM
66.63% / 72.62%
33.73% / 32.36% 37.53% 16%
GAT
83.43% 89.18%
MPNN-max
100.0% / 99.99% %
96.45 96.25 %
Table The predictive performance of MPNN-mat on 100-node graphs after training on 20-node sraphs-partitioned
graphs partitioneed by graph type.
Graph type
Reachability
Predecessor
Ladder
95.57% 98.633%
94.13% /91.47%
2-D grid
95.93% 993.28%
87.90%
83.77%
Tree
99.55% / /98.32%
98.60% / 997.83%
Erdös-Rént
100.0%
100.0%
94.00%
89.655 69.65%
Barabási-Albert
100.0%
100.0%
92.71%
88, 88.60%
4- Community
100.0%
100.0%
86.25%
79.65%
4 Caveman
100.0% 100.0%
91.55% 86.96%
the per-category results of predicting reachability and predecessor for MPNN-max. We report that the performance is roughly evenly distributed across the sategories-winn trees being the easiest to leamn on and grids/community graphs the hardest. These results align well with our expectations:
In trees, computing the shortest path tree is equivalent to a much simpler task- -rooting the input tree in the source vertex-that model may readily pick up on.
Making proper choices on grids requires propagating decisions over long trajectorie as such, a poor decision early on may more strongly compromise the overall performance of retrieving the shortest path tree.
As the community graphs are composed of four interconnected dense graphs (Erdös-Rén) with p = 0.7), the node degree distribution the model required to handle may change drastically as graphs increase in size. This may require the model to aggregate messages over substantially larger neighbourhoods than is used to during training.
E EXPLAINING GNN PREDICTIONS
We provide further qualitative analysis of what the MPNN-max architecture has learnt when performing algorithm execution. In particular, we apply a model similar to GNNExplainer (Ying) eet al. (2019) for explaining the decisions made during the neural execution. For the reachability task, the explainer asnwers the question: "for a given node u, which node in the neighbourhood of influences the reachability prediction made by the neural execution model?".
We use the best performing model, MPNN-max, to demonstrate the explanation. Given an already trained model on graphs with 20 nodes, starting from any node u of the neural exccution sequence. we optimise for an adjacency mask M, that is initialized to for all edges that connect to and everywhere else. Instead of the original adjacency matrix A, we use A C (M) as the input adjacency to the model. We fix the model parameters and only train on the adjacency mask using the same reachability loss, with the additional term of the sum of values the adjacency mask. This encourages the explanation to remove many edges as possible from the immediate neighbourhood of u, while still being able to perform the correct reachability updates.
When the mask is trained until convergence, pick the edge that has the maximum weight in the mask to be the predecessor that explains the reachability of the node.
'Note that this is also the case with ladder graphs, but these trajectories cannot get very complicated in this case, as the ladder graph product of two path graphs.
13

---

Published as a conference paper at ICLR 2020
432
Figure 4: Identified reachability paths for noisy Caveman graph and tree graph, using GNNExplainer. The purple edges indicate the predecessor relationships identified by the explainer, while the yellow edges are the remainder of the graph's s edges.
We then perform the same explanation procedure on the ground-truth predecessor of in the BFS algorithm, and continue the process until we reach the source node, of the BFS algorithm. If all explanations are correct, we will observe a path that connects the node to the starting node of the BFS algorithm. Any disconnection indicates an incorrect explanation that deviates from the ground- truth, which could either be due to the incorrect prediction of the model, or incorrect explanation. Using the standard training dataset our experiments, we observe that 82. the instances have path explanation with of these examples are visualised in Figure 4 Additionally, 93.85% of the predecessor explanation correspond to the ground-truth, providing further qualitative insight into the algorithm execution capacity of MPNN-max.
in the explanation compared to the ground-trute predecessors. Two
14


Reviews:
[{"review_id": "SJg7FXl6KS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nNonetheless, 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.\n\nOther comments:\n1. 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.\n2. 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HklfytHTKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \nAuthors try to learn BFS, Bellman-Ford and Prim algorithms on various types of random graphs. \nExperimental results suggest that MPNN with max aggregator outperforms other variants significantly in terms of generalization. \n\nOverall, this paper presents a solid contribution on learning graph algorithms using GNNs, despite the caveat for some clarifications on the model and experiments. \nGiven these clarifications in an author response, I would be willing to increase the score.\n\nPros:\n\n1, 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.\n\n2, Experimental comparisons are adequate and convincing. The detailed analysis of empirical results also provide good explanation.\n\nCons & Suggestions:\n\n1, 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? \n\n2, 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. \n\n3, 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?\n\n4, 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.\n\n5, 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].\n\n[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.\n[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).\n\n======================================================================================================\n\nThanks for the thorough response! It resolves my concerns. I improved my score.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgYLHqx5H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper uses message-passing neural networks to learn to predict which\nnodes to update with what metadata. Experiments are shown that the algorithm\ncan learn to visit nodes in the same order as a breadth-first-search as well\nas the Bellman-Ford shortest-path algorithm.\n\nFeedback:\n\nI'm not sure what problem this paper is trying to solve. We are provided\nthe graph and graph algorithm as input to the network so that we can\nlearn what the algorithm will do next? I'm not sure why this is a problem?\nAre these algorithms badly written and need to be improved? Do we want to\nlearn how to execute graph algorithms in general?\n\nI found the paper fairly hard to read and follow. I wish the\nmodel were described all in one place and the related work also\nin just one place. I think this paper would be greatly improved\nby more work on explaining the motivation as well as more\nclearly. I also feel the paper could be much stronger if it was grounded\nin an existing problem others in the community might have.\n\nClarifications:\n\nIn page 4, I don't know what it means to execute these two algorithms\nsimulatenously?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

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