Directed Acyclic Graph Neural Networks
Authors: Veronika Thost
Jie Chen
Venue: ICLR 2021 Poster (2021)
Keywords: Graph Neural Networks
Graph Representation Learning
Directed Acyclic Graphs
DAG
Inductive Bias

Abstract: Graph-structured data ubiquitously appears in science and engineering. Graph neural networks (GNNs) are designed to exploit the relational inductive bias exhibited in graphs; they have been shown to outperform other forms of neural networks in scenarios where structure information supplements node features. The most common GNN architecture aggregates information from neighborhoods based on message passing. Its generality has made it broadly applicable. In this paper, we focus on a special, yet widely used, type of graphs---DAGs---and inject a stronger inductive bias---partial ordering---into the neural network design. We propose the directed acyclic graph neural network, DAGNN, an architecture that processes information according to the flow defined by the partial order. DAGNN can be considered a framework that entails earlier works as special cases (e.g., models for trees and models updating node representations recurrently), but we identify several crucial components that prior architectures lack. We perform comprehensive experiments, including ablation studies, on representative DAG datasets (i.e., source code, neural architectures, and probabilistic graphical models) and demonstrate the superiority of DAGNN over simpler DAG architectures as well as general graph architectures.

Published as a conference paper at ICLR 2021
DIRECTED ACYCLIC GRAPH NEURAL NETWORKS
Veronika Thost & .iie Chen" MIT-IBM Watson Al Lab, IBM Research
Veronika. Thost ( eibm. com, chen j ie@us..... ibm. com
ABSTRACT
Graph-structured data ubiquitously appears in science and engineering. Graph neural networks (GNNs) are designed exploit the relational inductive bias ex- hibited in graphs; they have been shown to outperform other forms of neural networks in scenarios where structure information supplements node features. The most common GNN architecture aggregates information from neighborhoods based on message passing. Its generality has made broadly applicable. In this paper, we focus a stronger inductive bias-partial ordering-into the neural network design. We propose the directed acyclic graph neural network, DAGNN, architecture that processes information according to the flow defined by the partial order. DAGNN can be considered framework that entails carlier works special cases (e.g.. models for trees and models updating node representations recurrently). but we identify several crucial components that prior architectures lack. We perform comprehensive experiments, including ablation studies, on representative DAG datasets (i.e., source code, neural architectures, and probabilistic graphical mod- els) and demonstrate the superiority of DAGNN over simpler DAG architectures as well as general graph architectures.
special, yet widely used, type graphs-DAGGs and inject
INTRODUCTION
data is ubiquitous across various disciplines (Gilmer et al. 2017 Zitnik et al, 2018 Sonnchez-Gonzalzz al., 2020). Graph neural networks (GNNs) both the graph struc- ture and node features to produce vectorial representation, which can be used for classification, regression (Hu al. 2020), and graph decoding (Li et al. 2018 Zhang et al./ 2019). Most popular GNNs update node representations through iterative message passing between neighboring nodes, followed by pooling (either flat or hierarchical (Lee et al. 2019 Ranjan al. (0200) to produce
graph representation (Li et al.) 2016 Kipf & Welling 2017; Gilmer et al., 2017 Veličković et al., 2018 Xu et al. 2019). The relational inductive bias (Santoro et al.J 2017 Battaglia et al. 2018 Xu et al.) 2020) neighborhood
eergattionemmowerss GNNs to outperform graph-agnostic neu- neural network (MPNN) architecture, which computes representations h,, for all nodes v in graph G in every layer and a final graph representation hgg as (Gilmer et al. (017)):
ral networks. To facilitate subsequent discussions, we formalize a message-passin
h COMBINE' (n-- AGGREGATE ((h uue (eN())))) é= L= L, (1)
hg READOUT (h,, VEV).
where ho the input feature of u. (v) denotes neighborhood of node (sometimes including itself), V denotes the node set of G, is the number of layers, and AGGREGATE', COMBINE', and READOUT are parameterized neural networks. For notational simplicity, we omit edge at- tributes; but they can be straightforwardly incorporated into the framework
Directed acyclic graphs (DAGs) are special type of graphs, yet broadly seen across domains. Examples include parsing results source code (Allamanis et al., 2018), logical formulas (Crouse)
al. 2019), and natural language sentences, as well probabilistic graphical models (Zhang al.
2019 neural architectures (Zhang et al., 2019), and automated planning problems (Ma et al. 2020
To whom correspondence should be addressed.

---

Published as a conference paper at ICLR 2021
A directed graph is DAG if and only if the edges define partial ordering the nodes. The partial order is an additionally strong inductive bias one naturally desires to incorporate into the neural network. For example, neural architecture seen DAG defines the acyelic dependency of computation, an important piece of information when comparing architectures and predicting their performance. Hence, this information should be incorporated into the architecture representation for higher predictive power.
In this work, we propose DAGNNs-directed acyclic graph neural networks-that produce rep- resentation for a DAG driven by the partial order. In particular, the order allows for updating node representations based on those of all their predecessors sequentially, such that nodes without succes- sors digest the information of the entire graph. Such processing manner substantially differs from that of MPNNs where the information landed on node is limited by a multi-hop local neighborhood and thus restricted by the depth L. of the network.
Modulo details to be elaborated in sections that follow, the DAGNN framework reads
h Fd 18-1 G (he u E P(u)), (( )) 8=1,...,
(3)
kgg R ( t= (. ((..
(4)
where P(e)) denotes the set of direct predecessors of v, T denotes the set of nodes without (di- rect) successors, and G Fe, and R are parameterized neural networks that play similar roles to AGGREGATE'S COMBINE', and READOUT, respectively.
inside the underlined part of 1 is advanced to é in the counterpart in (3 In other words, MPNN aggregates neighborhood information from the past layer, whereas DAGNN uses the information the current layer. advantage is that DAGNN always uses more recent information to update node representations.
notable difference between 3 and I
is that the superscript
Equations 3 (4) outline several other subtle but important differences between DAGNN and MPNNs, such as the use of only direct predecessors for aggregation and the pooling on only nodes without successors. All these differences are unique to the special structure a DAG enjoys. Ex- ploiting this structure properly should yield more favorable vectorial representation of the graph.
In Section 2 we will elaborate the specifics of 3 4 The technical details include (i) attention for node aggregation, (ii) multiple layers for expressivity, and (iii) topological batching for efficient implementation, all of which yield an instantiation of the DAGNN framework that is state of the art.
For theoretical contributions, we study topological batching and justify that this technique yields maximal parallel concurrency in processing DAGs. Furthermore, we show that the mapping defined by DAGNN invariant node permutation and injective under mild assumptions. This result reassures that the graph representation extracted by DAGNN is discriminative.
Because DAGS appear in many different fields, neural architectures for DAGS (including, notably, D-VAE (Zhang et al., 2019)) or special cases (e.g., trees) are scattered around the literature over the years. Generally, they are less explored compared to MPNNs; and some are rather application- specific. In Section 3 we unify several representative architectures as special cases of the frame- work 3
We compare the proposed architecture to them and point out the differences that lead to its superior performance.
In Section 4 we detail our comprehensive, empirical evaluation on datasets from three domains: (i) source code parsed DAGs (Hu et al., 2020); (ii) neural architecture search (Zhang et al. 2019), where each architecture
DAG; and (ii) score-based Bayesian network learning (Zhang et al. 2019). We show that DAGNN outperforms many representative DAG architectures and MPNNs.
Overall, this work contributes a specialized graph neural network, a theoretical study of its proper- ties, an analysis of a topological batching technique for enhancing parallel concurrency, a framework interpretation that encompasses prior DAG architectures, and comprehensive evaluations. Supported code is available at ht/ttss: thub. wwt./ooost/ttattt.....o
2 THE DAGNN MODEL
A DAG is a directed graph without cycles. Denote by G = E) DAG, where V and C V x the node set and the edge set, respectively. A (strong) partial order over set S is binary
2

---

Published as a conference paper at ICLR 2021
H
AGGREGATE
AGGREGATE
COMBINE (GRU))
COMBINE (GRU")
Figure 1: Processing of node u 3 (orange). For each layer l, we collect representations h for all nodes in a matrix H., where each row represents one node. The initial feature matrix X' = H.. In the first layer, the representations of the direct predecessors P(v) {0, 1, (blue) have been computed; they are aggregated together with the past representation of o (orange) to produce message. The GRU treats the message the hidden state and the past representation of v as input and outputs an updated representation for v (green). This new representation will be used by v's direct successors {4} in the same layer and also input to the next layer. Note that the figure illustrates the processing of only one node. In practice, a batch nodes is processed; see Section 2.2
relation < that is transitive and asymmetric. Some authors use reflexivity versus irreflexivity to distinguish weak partial order over strong partial order. To unify concepts, we forbid self-loops (which otherwise are considered cycles) in the DAG and mean strong partial order throughout. A set S with partial order S is called poset and denoted by tuple (5.
A DAG (V, E) and a poset (S, S) are closely related. For any DAG, one can define a unique partial order S the node set V, such that for all pairs of elements u, V, S v if and only if there is directed path from u to c. On the other hand, for any poset (S, S). there exists (possibly more than) one DAG that uses as the node and that admits directed path from u u whenever u S v.
In a DAG, all nodes without (direct) predecessors are called sources and we collect them in the set S. Similarly, all nodes without (direct) successors called largets and we collect them in the T. Additionally, we let = [ho, v E V} be the set of input node features.
2.1
MODEL
The main idea of DAGNN is to process nodes according to the partial order defined by the DAG. Using the language of MPNN, at every node v, we "aggregate" information from its neighbors and "combine" this aggregated information (the "message") with e's information to update the repre- sentation of The main differences to MPNN are that (i) past-layer, information to compute the current-layer representation of v and that (ii) we aggregate from the prrecc-predccesoor set Pvv) only, rather than the entire (or randomly sampled) neighbor- hood (v). They lead to a straightforward difference the final "readout" also. In the following, we propose an instantiation of Equations 3 See Figure for an illustration of the architecture.
the current-layer, rather than the
One layer. We use the attention mechanism to instantiate the aggregate operator G For a node the ê-th layer, the output message m computed by Gt is weighted combination of h for all nodes u E P(v) at the same layer E:
m = Gd (1h u u(()) = Σ uEP(v)
a
1 quory
h
(5)
message
key
value
The weighting coefficients a follow the query-key design usual attention mechanisms, whereby the representation of in the past layer, 1t--1 serves as the query. Specifically, we define
Ou 16-1 6- n1) = softmax (wf h + w/ ni,
(6)
wEP(v)
3

---

Published as a conference paper at ICLR 2021
where wf and w/ are model parameters. We use the additive form, opposed to the usual dot- product form [ |since it involves fewer parameters. An additional advantage is that it is straightfor- ward to incorporate edge attributes into the model, will be discussed soon.
The combine operator F' combines the message m. with the previous representation of v, h h and produces updated representation hg- We employ recurrent architecture, which is usually used for processing data in sequential order but similarly suits processing in partial order:
message
h = Frt (16-1 m²) GRU
input
state
where h6-1, m. and h are treated as the input, past state, and updated state/output of a GRU, respectively. This design differs from most MPNNS that use simple summation or concatenation to combine the representations. further differs from GG-NN (Li et al. (016) (which also employs a GRU), wherein the roles of the two arguments are switched. In GG-NN, the message is treated as the input and the node representation is treated as the state. In contrast, we start from node features and naturally use them as inputs. The message tracks the processed part of the graph and serves better the role of hidden state, being recurrently updated.
By convention, we define G (0.-) O for the aggregator that for nodes with an empty direct- predecessor set, the message (or, equivalently, the initial state of the GRU) is zero.
Bidirectional processing. Just like in sequence models where sequence may be processed by either the natural order or the reversed order, we optionally invert the directions of the edges in G to create reverse DAG G. We will use the tilde notation for all terms related to the reverse DAG. For example, the representation of node v in G at the ε-th layer is denoted by h.
Readout. After L layers of (bidirectional) processing, we use the computed node representations to produce the graph representation. We follow common practice-coonatenate the representations across layers, perform max max-pooling across nodes, and apply fully-connected layer produce the output. Different from the usual practice, however, we pull across only the target nodes and concate- nate the pooling results from the directions. Recall that the target nodes contain information of the entire graph following the partial order. Mathematically. the readout R produces
hg = FC (c(Max-PPol
( [i AC) || Max-Pool ( K()). WES
(8)
E=
E=
Note that the target set 7 of & is the same as the source set S of G. If the processing is unidirectional, the right pooling in dropped.
Edge attributes. The instantiation of the framework so far has not considered edge attributes. in fact simple incorporate them. Let T(u, v) be the type of edge (u,v) and let y/ be representation of edges of type т. We insert this information during message calculation in the aggregator. Specifically, we replace the attention weights af defined in (6) by
au [h A.)) softmax (wf" ht-1 we h + w/ Vr(n.o)) uEP(v)
In practice, we experiment with slightly fewer parameters by setting w/ = wf and find that the model performs equally well. The edge representations y- trainable embeddings of the model. Alternatively, if input edge features are provided, (r(a.e) can be replaced by neural network- transformed embedding for the edge (I,, v).
2.2 TOPOLOGICAL BATCHING
A key difference to MPNN is that DAGNN processes nodes sequentially owing to the nature of the aggregator G obeying the partial order. Thus, for computational efficiency, is important to max- imally exploit concurrency as better leverage parallel computing resources (e.g., GPUs). One
'The usual dot not-product form reads a (b (()) = softmax( (Wf" バt-1, W (.)). We find that in practice the dot oot-product form and the additive form perform rather similarly, but the former requires substan- tially more parameters. We are indebted to Hyoungjin Lim who pointed out that, however, in the additive form, the query will be canceled inside the softmax computation.
4

---

Published as a conference paper at ICLR 2021
BF=
B3
B2
82
B
5
B,
Figure 2: Topological batching. Left: for the original graph G; right: for the reverse graph G.
observation is that nodes without dependency may be grouped together and processed concurrently, if their predecessors have all been processed. See Figure for illustration.
To materialize this idea, we consider topological batching, which partitions the node set V into ordered batches {B; J:20 so that (i) the B,'s s are disjoint and their union is V: (ii) for every pair of nodes u, V B, for some i, there is not a directed path from to v or from v to u; (ii) for every i > O, there exists one node in B, such that it is the tail of an edge whose head is in B The concept was proposed by Crouse al. (219 in what follows, we derive several properties that legitimizes its use our setting. First, topological batching produces the minimum number of sequential batches such that all nodes in each batch can be processed in parallel.
The number of batches from a partitioning that satisfies (i)-tii) described in the pre- ceding paragraph is equal to the number of nodes in the longest path of the DAG. As consequence, this partitioning produces the minimum number of ordered batches such that for all S u, ifu E B; Note that the partial order S is defined at the beginning of Section 2
Theorem 1.
and u E By, then
The partitioning procedure may be as follows. All nodes without direct predecessors, S, form the initial batch. Iteratively, remove the batch just formed from the graph, as well the edges emitting from these nodes. The nodes without direct predecessors in the remaining graph form the next batch. Remark 1. To satisfy Properties (i)-(ii), it is not necessary that B, S; but the above procedure achieves so. Applying this procedure on the reverse DAG G, we obtain By T. Note that the last batch for 9 may not the same as T; and the last batch for may not be the same as S either.
Remark 2. Topological batching can be straightforwardly extended to multiple graphs for better parallel concurrency: one merges the B; for the same across graphs into a single batch. This equivalent treating the multiple DAGs a single (albeit disconnected) DAG and applying topological batching on it.
2.3 PROPERTIES
In the following, we summarize properties of the DAGNN model; they are consistent with the cor- responding results for MPNNs. To formalize these results, we let M V x & x X' + he denote the mapping defined by Equations
3 For notational consistency, we omit bidirectional processing, The first results state that DAGNN produces the same graph
and thus ignore the tilde term representation invariant to node permutation.
Theorem 2. The graph representation hg is invariant to node indexing if all G F". and R are so. Corollary 3. The functions G F², and R defined in are invariant to node iddexng.. Hence, the resulting gruph representation hig is, too.
The next result states that the framework will not produce the same graph representation for different graphs (i.c., non-isomorphic graphs), under a common condition.
Theorem 4. The mapping M is injective G Ff. and R, considered multiset functions,
The condition required by Theorem 4 is not restrictive. There exist (infinitely many) injective mul- tiset functions G Fº, and R, although the ones instantiated by (5)- X are not necessarily injective.
The modification to injection can be done by using the e-trick applied in GIN (u et al. 2019), but,
"ee also earlier implementation httpa//wawwot.......oo..oooo.ooo
5

---

Published as a conference paper at ICLR 2021
similar to the referenced work, the that ensures injection is unknown. In practice, it is either set as zero or treated as a tunable hyperparameter.
3 COMPARISON TO RELATED MODELS
In this section, we compare to the most closely related architectures for DAGs, including trees. Natural language processing is a major source of these architectures, since semantic parsing forms rooted tree or DAG. Recently, D-VAE (Zhang et al. 2019) has been suggested as a general- purpose autoencoder for DAGs. Its encoder architecture is the most similar one to ours, but we highlight notable differences that support the improvement DAGNN gains over the D-VAE encoder. All the models we compare with may be considered as restricted cases of the framework
Rooted trees do usually not come with directed edges, because either direction (top-down or bottom- up) is sensible. Hence, we use the terminology "parent" and "child" instead. Unified under our framework, recursive neural networks tailored trees (Socher al., 2011 2012 2013 Ebrahimi & Dou 2015) are applied to fixed number of children when the aggregator acts on a concatenation of the child representations. Moreover, they assume that internal nodes do not come with input representations and hence the combine operator misses the first argument.
Tree-LSTM (ai et 2015 Zhu et al. 2015 Zhang al., 2016 Kiperwasser & Goldberg 2016) and DAG-RNN (Shuai et al. 2016), like DAGNN, employ recurrent architecture as the combine operator, but the message (hidden state) therein is naive sum or element-wise product of child rep- resentations. In a variant of Tree-LSTM, the naive sum is replaced by sum of child representations multiplied by separate weight matrices. limitation of this variant that the number of children must be the same and the children must be ordered. Another limitation is that both architectures assume that there is a single terminal node (in which case a readout is not invoked).
The most similar architecture to DAGNN is the encoder of D-VAE, There are two notable differ- ences. First, D- VAE uses the gated sum as aggregator but we use attention which leverages the information of not only the summands (h()) but also that of the node under consideration (h(-1), This additional source of information enables attention driven by external factors and improves over self attention. Second, similar to all the aforementioned models, D- VAE does not come with layer notion. On the contrary, we use multiple layers, which are more natural and powerful in the light of findings about general GNNs. Our empirical results described in the following section confirm so.
4 EVALUATION
In this section, we demonstrate the effectiveness of DAGNN on multiple datasets and tasks over a comprehensive list of baselines. We compare timing and show that the training cost of DAGNN is comparable with that of other DAG architectures. We also conduct ablation studies to verify the importance of its components, which prior DAG architectures lack.
4.1 DATASETS, TASKS, METRICS, AND BASELINES
The OGBG-CODI dataset (Hu et al. 2020) contains 452,741 Python functions parsed into DAGs. We consider the TOK task, predicting the tokens that form the function name; it is included in the Open Graph Benchmark (OGB). Additionally, we introduce the LP task, predicting the length of the longest path of the DAG. The metric for TOK is the F1 score and that for LP is accuracy. Because of the vast size, we also create a 15% training subset, OGBG-CODE-15 for similar experiments.
For this dataset, we consider three basic baselines and several GNN models for comparison. For the TOK task, the Node2Token baseline predicts tokens from the attributes of the second graph node, while the TargetInGraph baseline predicts tokens that appear in both the ground truth and in the attributes of some graph node. These baselines exploit the fact that the tokens form node attributes and that the second node's 's attribute contains the function name if it is part of the vocabulary. For the LP task, the Majority Valid baseline constantly predicts the majority length seen from the validation set. The considered GNN models include four from OGB: GCN (Kipf & Welling 2017), GIN (Xu et al. 2019). GCN- VNN GIN-VN (where -VN means adding a virtual node connecting all existing nodes); two using attention//ated--su mechanisms: GAT (Veličković et. 2018), GG-NN

---

Published as a conference paper at ICLR 2021
Table 1: Prediction performance on the full dataset OGBG-CODE and a 15% subset OGBG-
CODE-15 5 for two tasks: TOK and LP. Best results are boldfaced and second best are underlined.
TOK
TOK-15
LP
LP-15
Model
FI f
FIT
Acc
Acc f
Node2Token
13.04
13.04
TarphtInGraph
27.32
27.08+000
MajorityInVali Valid
22.66+000
22.66+0000
GCN
31.63
24.39+000
95.55
90.66+200
GCN-VN
32.63=0.13
24.444t025
96.62#004
92.87+1.19
GIN
31.63
21.49
98. 98
92.53+
GIN-VN
32.04
21.1010611
98.60
93.27
GAT
33,59
2:.37
93.71
83.15+1.4
GG-NN
28.04
23.15 1.0.9
96.48
89. 19916342331
SAGPool
31 00.39
24.45
72.68 114.2
60.66=11.42
ASAP
28.30
35.0611037
87.8 27.84
71.5613776
D-VAE
32.64
27.08 +:0.9
99.90+0.02
99.78 99.78++000
DAGNN
34.41
29.11
99.93
99.86.1044
Table 2: Predictive performance of latent representations for datasets NA and BN.
BN
Model
RMSE
Pearson's
RMSE
Pearson's 's f
S-VAE
0.521 +0000
0.847
0.499
0.873
GraphRNN
0.579
0.807=00001
0.779
0.634=2.00
GCN
0.4822
0.871 200001
0.599=0.006
0.809
DeepGMG
0.478 #0.002
0.873
0.843
0.555 #0000
D-VAE
0.375
0.904
0,281 +000004
0,964 0.001
DAGNN
0.264-10.00
0.9644
0.122 0.004
0.993 0.000
Li et al. 2016;; two hierarchical pooling approaches using attention: SAGPool (Lee et al. 2019). ASAP (Ranjan et al. 2020); and the D-VAE encoder.
The NA dataset (Zhang et al., 2019) contains 19,020 neural architectures generated by the ENAS software. The task is to predict the architecture performance on CIFAR- under the weight-sharing scheme. Since it is regression task, the metrics RMSE and Pearson's 's To gauge performance with Zhang et al.] (2019). we similarly train (unsupervised) autoencoders and use sparse Gaussian process regression serves as the encoder and we pair it with an adaptation of the D-VAE decoder (see Appendix D We compare to D-VAE and all the autoencoders compared therein: S-VAE (Bowman al. 2016
the latent representation to predict the architecture performance. DAGNN
GraphRNN You et al. 2018).
GCN (Zhang et al. 2019), and DeepGMG (Li Li al. 2018).
The BN dataset Zhang et al. 2019 contains 200,000 Bayesian networks generated by using the R
package bnlearn. The task is to predict the BIC score that measures how well a BN fits the Asia dataset (Lauritzen Spiegelhalter 1988). We use the same metrics and baselines for NA.
4.2 RESULTS AND DISCUSSION
Prediction performance, token prediction (TOK), Table The general trend is the same across the full dataset and the 15% subset. DAGNN performs the best. GAT achieves the second best result, surprisingly outperforming D-VAE (the third best). Hence, using attention aggregator during message passing benefits this task. On the 15% subset, only DAGNN, GAT, and D-VAE match or surpass the TargetInGraph baseline. Note that not all ground-truth tokens are in the vocabulary and thus the best achievable Fl is 90.99. Even so, all methods are far from reaching this ceiling performance. Furthermore, although most of the MPNN models (middle section of the table) use as many as five layers for message passing, the generally good performance DAGNN and D- D-VAE indicates that DAG architectures not restricted by the network depth benefit from the inductive bias.

---

Published as a conference paper at ICLR 2021
10
Arg Time! Epodi (mik)
10
GAT
S-VAE
GG-NN
GragiKNN
SAGPoo)
100
CCN
10a
ASAP
DeePGMG
D-VAE
D-VAE
DAGNN
10-1
DAGINN
OGBG-CODE
NA
Figure 3; Average training time per epoch, on logarithmic scale. Standard deviation is negligible.
Table 3: Ablation results.
TOK-15
LP-15
NA
BN
Configuration
F1
Acc 1
RMSE +
Pearson's 's
RMSE +
Pearson's 's
DAGNN
29.11 10.44
99.86=0.04
0.264:1.004
0.964
0. 0.0004
0.993
Gated-sum aggr.
24.981045
99.88=
0.45 1 1:00002
0.887110001
0.486.20.005
0.878
Single layer
28.39
99.74 99.74_0.10
0.207:10000
0.960
0.324
0.950
FC layer
20.08
99. -9.85_0.02
0.280
0.959400001
0.362=#0.02
0.934
Pool all nodes
28.40
99.78=0.00
0.302
0.952
0.098
0.996=0.001
W/o edge attr.
28.85
99.82
Prediction performance, length of longest path (LP), Table This analytical task interestingly reveals that many of the findings for the TOK task do not directly carry over. DAGNN still performs the best, but the second place is achieved by D-VAE while GAT lags far behind. The unsatisfactory performance of GAT indicates that attention alone is insufficient for DAG representation learning. The hierarchical pooling methods also perform disappointingly, showing that ignoring nodes may modify important properties of the graph (in this case, the longest path). It is worth noting that DAGNN and D- D-VAE achieve nearly perfect accuracy. This result corroborates the theory of Xu et al. (202)), who state that when the inductive bias is aligned with the reasoning algorithm (in this case, path tracing), the model learns to reason more easily and achieves better sample efficiency.
On NA and BN, DAGNN also outperforms D- VAE, which in turn outperforms the other four baselines (among them, DeepGMG works the best on NA and S-VAE works the best on BN, consistent with the findings of Zhang et al. (2019).) While D-VAE demonstrates the benefit of incorporating the DAG bias, DAGNN proves the superiority of its architectural components, as will be further verified in the subsequent ablation study.
Prediction performance, scoring the DAG, Table 2
Time cost, Figure 3 The added expressivity of DAGNN comes with tradcoff: the sequential processing of the topological batches requires more time than does the concurrent processing of all graph nodes, as in MPNNs. Figure sshww shows that such trade-off is innate to DAG architectures, in- cluding the D- DAE encoder. Moreover, the figure shows that, when used as a component of larger architecture (autoencoder), the overhead of DAGNN may not be essential. For example, in this par- ticular experiment, DeepGMG (paired with the S-VAE encoder) takes an order of magnitude more time than does DAGNN (paired with the D-VAE decoder). Most importantly, ure is that DAGNN learns better and faster at larger learning rates, leading to fewer learning epochs. For example, DAGNN reaches the best performance at epoch 45, while D-VAE around 200.
reflected in the fig-
Ablation study, Table 3, While the D-VAE encoder performs competitively owing similarly to the incorporation of the DAG bias, what distinguishes our proposal are several architecture components that gain further performance improvement. In Table we summarize results under the following cases: replacing attention in the aggregator by gated sum; reducing the multiple layers to one; replacing the GRUs by fully connected layers; modifying the readout by pooling over all nodes; and removing the edge attributes. One observes that replacing attention generally leads to the highest degradation in performance, while modifying other components yields losses too. There two exceptions. One occurs on LP-15, where gated-sum aggregation surprisingly outperforms attention by tight margin, considering the standard deviation. The other occurs the modification of
8

---

Published as a conference paper at ICLR 2021
Table 4: DAGNN results for different numbers of layers.
TOK-15
LP-15
NA
BN
# Layers
F1 1
Acc 1
RMSE
Pearson's r
RMSE 5
Pearson's 's
28.39
99.74=0.10
0.277 +0.00
0.960=t0001
0.324
0.950
2 29.11
99.86=0.04
0.204
0.964=
0.122
0.993-10.000
3
28, 28.9771027
99.81=0.0
0.260
0.965:10.01
0.129
0.993
28.91 28.91100 1:043
99.78=
0.265
0.963:10.001
0.129-0.00
0.993
the readout for the BN dataset. In this case, a Bayesian network factorizes the joint distribution of all variables (nodes) it includes. Even though the DAG structure characterizes the conditional independence of the variables, they play equal roles to the BIC score and thus it is possible that emphasis of the target nodes adversely affects the predictive performance. In this case, pooling over all nodes appears to correct the overemphasis.
Sensitivity analysis, Table and Figure 4 It is well known that MPNNs often achieve best performance with small num- ber of layers, curious behavior distinet from other neural net- works. It is important to see if such behavior extends to DAGNN. In Table 4 we list the results for up to four layers. One observes that indeed the best performance occurs at ei- ther two or three layers. In other words, one layer is insuff- cient (as already demonstrated in the ablation study) and more than three layers offer no advantage. We further extend the ex- perimentation on TOK-15 15 with additional layers and plot the results in Figure The trend corroborates that the most signif- icant improvement occurs when going beyond single layer. is also interesting to see that a single layer yields the highest variance subject to randomization.
|11
29
28
1 2 6 7 910
Layers
Figure 4: Extending Table with further layers on TOK-15.
Structure learning, Figure(5, For an application of DAGNN, extend the use the BN dataset to learn the Bayesian net- work for the Asia data. In particular, we take the Bayesian optimization approach and optimize the BIC score over the la- tent space of DAGs. We use the graphs in BN as pivots and encode every graph by using DAGNN. The optimization yields DAG with BIC score - 11117.22 29 (see F5g This DAG is almost the same as the ground truth (see Figure 2 of Lauritzen & Spiegelhalter (1988) ) except that it does not include the edge from "visit to Asia?" to "Tuberculosis?". It is interesting to note that the identified DAG has higher BIC score than that of the ground truth, -11109.1 74. Furthermore, the BIC score is also much higher than that found by using the D-VAE encoder, - 111125.75 75 (Zhang et al., 2019). This encouraging result corroborates the superior encoding quality of DAGNN and the effective use of it in downstream tasks.
S
L
X
Figure 5: The Bayesian network identified by using Bayesian opti- mization over the latent space en- coded by DAGNN.
5 CONCLUSIONS
We have developed DAGNN, a GNN model for a special yet widely used class of graphs-DAGs It incorporates the partial ordering entailed by DAGs as strong inductive bias towards represen- tation learning. With the blessing of this inductive bias, we demonstrate that DAGNNs outperform MPNNs on several representative datasets and tasks. Through ablation studies, we also show that the DAGNN model well designed, with several components serving as crucial contributors to the per- formance gain other models that also incorporate the DAG bias, notably, D-V.E. Furthermore, we theoretically study a batching technique that yields maximal parallel concurrency in processing DAGs and prove that DAGNN is permutation invariant and injective.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
This work supported in part by DOE Award DE-OE0000910. Most experiments were conducted on the Satori cluster (satori .mit.e.. .iit.edu).
REFERENCES
Miltiadis Allamanis, Earl T. Barr, Premkumar T. Devanbu, and Charles A. Sutton. A survey of machine learning for big code and naturalness. ACM Comput. Surv. 51(4):81:1-81:3 2018.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzaler Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1806.01 2018. 11261
URL httt::tttatiiiiiee org/
Samuel R. Bowman, Luke Vilnis, Oriol Vinyals, Andrew M. Dai, Rafal Józefowicz, and Samy Bengio. Generating sentences from continuous space. In Yoav Goldberg and Stefan Riezler (eds.), Proc. of Conference on Computational Natural Language Learning, CoNLL, pp. 10-21, 2016.
Maxwell Crouse, Ibrahim Abdelaziz, Cristina Cornelio, Veronika Thost, Lingfei Wu, Kenneth For- bus, and Achille Fokoue. Improving graph neural network representations of logical formulae with subgraph pooling, 2019.
Javid Ebrahimi and Dejing Dou. Chain based RNN for relation classification. In Proc. of Confer- ence of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL HLT, pp. 1244-1244 2015.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In Proc. of ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George F. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Tch (eds.), Proc. of International Conference on Machine Learning, ICML, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. CoRR, abs/2005.00687, 2020. URL
Eliyahu Kiperwasser and Yoav Goldberg. fasy- dependency parsing with hierarchical tree Istms. Trans. Assoc. Comput. Linguistics, 4:445-461 2016.
index.
Thomas Kipf and Max Welling. Semi-supervised learning with graph convolutional neural networks. In Proc. of International Conference on Learning Representations, ICLR, 2017.
Alex Krizhevsky. Learning multiple layers
of features from tiny images. Technical report, 2009.
S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical struc- tures and their application to expert systems. Journal of the Royal Statistical Society. Series (Methodological), 50(2):157-224 1988. ISSN 00359246.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proc. of Interna- tional Conference on Machine Learning, ICMI., volume of Proceedings of Machine Learning Research, pp. 3734-3743. PMLR, 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neu- ral networks. In Yoshua Bengio and Yann LeCun (eds.), Proc. of International Conference on Learning Representations, ICLR, 2016.
10

---

Published as a conference paper at ICLR 2021
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter W. Battaglia. Learning deep gener- ative models of graphs. CoRR, abs/1803.03322, 2018.
Tengfei Ma, Patrick Ferber, Siyu Huo, Jie Chen, and Michael Katz. Online planner selection with graph neural networks and adaptive scheduling. In Proc. of Thirty-Fourth Conference Artificial Intelligence, AAAI, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Proc. of Advances in Neural Information Processing Systems, NeurIPS, pp- 8024 8024-8035. 2019.
Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Jennifer G. Dy and Andreas Krause (eds.), Proc. of Interna- tional Conference Machine Learning, ICML, volume 80 of Proceedings of Machine Learning PMLR, 2018.
Research, pp. 4092-4101.
Ekagga Ranjan, Soumya Sanyal, and Partha P. Talukdar. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In Proc. of The Thirty- Conference Artificial Intelligence, AAAI, pp. 5470-5477, 2020.
Alvaro Sanchez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter W. Battaglia. Learning to simulate complex physics with graph networks. CoRR, abs/2002.09405, 2020. URL /ttp/:tts///aaaa
/tttpp:://xxi..... arwiv.iiiivo//.o org/ awtpaba//222.. 09405
Adam Santoro, David Raposo, David G. T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter W. Battaglia, and Tim Lillicrap. A simple neural network module for relational reasoning, pp. 4967- 4976, 2017.
Marco Scutari. Learning bayesian networks with the bnlearn package. Journal of Statistical Software, Articles, 1-22, 2010. ISSN 1548-7660.
Bing Shuai, Zhen Zuo, Bing Wang, and Gang Wang. Dag-recurrent neural networks for scene labeling. In Proc. of Conference on Computer Vision and Pattern Recognition, CVPR, pp. 3620- 3629, 2016.
Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. In Proc. Advances in Neural Information Processing, NIPS, pp. 1257-1264, 2005.
Richard Socher, Cliff Chiung- Yu Lin, Andrew Y. Ng, and Christopher D. Manning. Parsing natural scenes and natural language with recursive neural networks. In Proc. of International Conference on Machine Learning, ICML, pp. 129-136, 2011.
Richard Socher, Brody Huval, Christopher D. Manning, and Andrew Y. N. Semantic composition- ality through recursive matrix-vector spaces. In Proc. of Joint Conference on Empirical Meth- ods in Natural Language Processing and Computational Natural Language Learning, EMNLP-
CoNLL, pp. 1201-1211,001
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng. and Christopher Potts. Recursive deep models for semantic compositionality over senti- ment treebank. In Proc. of Conference on Empirical Methods in Natural Language Processing, EMNLP, pp. 1631-1642, 2013.
Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proc. of Annual Meeting of the As- sociation for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, ACI., pp. 1556 1566, 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. Proc. of International Conference on Learning Representa- fions, ICLR, 2018
11

---

Published as a conference paper at ICLR 2021
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? Proc. of International Conference on Learning Representations, ICLR, 2019.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In Proc. of International Conference on Learning Representations, ICLR, 2020.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In Jennifer G. Dy and Andreas Krause (eds.), Proc. of International Conference on Machine Learning, ICML, volume 80 of Proceedings of Machine Learning Research, pp. 5694-5703. PMLR, 2018.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-VAE: A variational autoencoder for directed acyclic graphs. In Proc. of Annual Conference Neural Information Processing Systems, NeurlPS, pp. 1586-1598, 2019.
Xingxing Zhang, Liang Lu, and Mirella Lapata. Top-down tree long short-term memory networks. In Kevin Knight, Ani Nenkova, and Owen Rambow (eds.), Proc. of Conference the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL HLT, pp. 310-320, 2016.
Xiao-Dan Zhu, Parinaz Sobhani, and Hongyu Guo. Long short-term memory over recursive struc- tures. In Proc. of International Conference Machine Learning. ICML, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1604-1612. JMLR.org, 2015.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec, Modeling polypharmacy side effects with graph convolutional networks. Bioinform., 34(13)i447-ii66, 2018.
12

---

Published as a conference paper at ICLR 2021
A PROOFS
Proof of Theorem 7 Let (U1, U2...., Ud) be a longest path of the DAG. The number of batches must be at least d, because otherwise there exists a batch that contains at least two nodes on this path, violating Property (ii). On the other hand, given the partitioning, according to Property (iii,, one may trace a directed path, one node from each batch, starting from the last one. The longest path must be at least that long. In other words, the number of batches must be at most the number of nodes on the longest path. Hence, these two numbers are equal. The consequence stated by the theorem straightforwarlly follows.
Proof of Theorem 2 We first show that h invairant to the indexing of by double induction on l and v. The base case is l = 1 and v E Bo. In this case, m. = G h2)) ) = 0 is invairant to the indexing of v. Then, h1 = (hg. m..) is, too. In the induction, if for all L' < l and all v', and for is invairant to the indexing of v', then for ''
and v E B, m = ((M, u E P(e)),, 1(-1) and hi F² (h,, mx) are both invairant to the indexing of v. Thus, by induction, for all l' = l and all v, h is invairant to the indexing of v. Then, by an outer induction, for all and all v, h is invairant to the indexing of v.
= and v' E Bo U...U 1. he" U.
Therefore, hg = R(th,, é= 0, 1. LI, v E T}) is invairant to the indexing of the nodes in T and thus of the entire node set.
Proof of Corollary g The function Go is invariant to node indexing because it is weighted sum of the elements in its first argument, (h whereas the weights are parameterized by using the same parameter wz for these elements.
The function F is invariant to node indexing because its two arguments are clearly distinguished.
The function R is invariant to node indexing because the FC layer applies the pooling result of h for fixed set of v.
Proof of Theorem 4 Suppose two graphs G and G' have the same representation hg = hag Then, from the function Ir, they must have the same target set T and same node representations M for all nodes T and all layers f. In particular, for the last layer & T., from the functions FL and GP, each of these nodes, from the two graphs must have the same set of direct predecessors P(v), each element of which have the same representation h across graphs. By backward induction, the two graphs must have the same node set V and edge set E. Moreover, for each node V, the last-layer representation hn must be the same.
Furthermore, from the injection property of F`, if a node v shares the same node representation WC, across graphs, then past-layer representation h6-1 must also be the same across graphs. A backward reduction traces back to the initial representation h. which concludes that the two graphs must have the same set of input node features X.
B DATASET DETAILS
OGBG-CODE. The OGBG-CODE dataset was recently included in the Open Graph Benchmark (OGB) (uu et al. 2020, Section 6.3). It contains 452,741 Python method definitions extracted from thousands of popular Github repositories. The method definitions are represented as DAGs by aug- menting the abstract syntax trees with edges connecting the sequence of source code tokens. Hence, there are two types of edges. The min/avg/max numbers of nodes in the graphs are 11/125/36123 12,, respectively. We use the node features provided by the dataset, including node type, attributes, depth in the AST, and pre-order traversal index.
The task suggested by Hu et al. (020)) is to predict the sub-tokens forming the method name, also known "code summarization" The task is considered a proxy measure of how well model captures the code semantics (Allamanis et al., 2018). We additionally consider the task of predicting the length of the longest path in the graph. We treat it 275-way classification because the maximum length 275. The distribution of the lengths/classes is shown in Appendix To avoid triviality, for this task we remove the AST depth from the node feature set.
13

---

Published as a conference paper at ICLR 2021
We adopt OGB's project split, whose training set consists of Github projects not seen in the valida- tion and test sets. We also experiment with a subset of the data, OGBG-CODE-15 15, which contains only randomly chosen 15% of the OGBG-CODE training data. Validation and test sets remain the same.
further experiment with two DAG datasets, NA and BN, used by Zhang et al. (2019) for evaluating their model D-VAE To compare with the results reported in the referenced work, we focus on the predictive performance of the latent representations of the DAGs obtained from autoencoders. We adopt the given 90/10 splits.
In addition DGBG-CODER
Neural architectures (NA). This dataset is created in the context of neural architecture search. It contains 19,020 neural architectures generated from the ENAS software (Pham et al.) 2018)) Each neural architecture has layers (i.e., nodes) sampled from different types of components, plus an input and output layer. The input node vectors are one-hot encodings of the component types. The weight-sharing accuracy (Pham et al. 2018) proxy of the true aceuracy) on CIFAR-10 10 (Krizhevsky] (2009) is taken as performance measure. Details about the generation process can be found in Zhang et al. (2019 Appendix H).
Bayesian networks (BN). This dataset contains 200,000 random 8-node Bayesian networks gen- erated by using the package bnlearn (Scutari 2010). The Bayesian Information Criterion (BIC) score is used measure how well the DAG structure fits the Asia dataset (Lauritzen & Spiegelhalter 1988). The input node vectors are one-hot encodings of the node indices according to topological sort. See Zhang et al. (2019) Appendix I) for further details.
C BASELINE DETAILS
Baselines for OGBG-CODE. We use three basic measures to set up baseline performance, two for token prediction and one for the longest path task. (1) Node2Tokem: This method uses the attribute of the second node of the graph as prediction. We observe that the second node either contains the function name, if the token occurs in the vocabulary (which is not always the case because some function names consist of multiple words), or contains "None". (2) TargetInGraph: This method pretends that it knows the ground-truth tokens but predicts only those occurring in the graph. One would expect that a learning model may be able to outperform this method if learns the associations of tokens outside the current graph. (3) MajorityIn Valid: This method always predicts the majority length seen in the validation set.
Additionally, we compare with multiple GNN models. Some of them are the GNN implementations offered by OGB: GCN, GIN, GCN-VN, and GIN-VN. The latter two are extensions of the first two by including virtual node (i.e., an additional node that is connected to all nodes in the graph).
Note that the implementations do not strictly follow the architectures described in the original papers (Kipf & Welling 2017 Xu et al. 2019). In particular, edge types are incorporated and inverse edges are added for bidirectional message passing.
Since our model features attention mechanisms, we include GAT (ellikovii et al. 2018 and GG- NN (Li et al. 2016) for comparison. We also include two representative hierarchical pooling ap- proaches, which use attention determine node pooling: SAGPool (Lee al. 2019) and ASAP (Ranjan et al., 2020). Lastly, we compare with the encoder of D-VAE (Zhang et al. 2019 Appendix F)
Baselines for NA and BN. Over NA and BN, we consider D-VAE and the baselines in Zhang et al. (2019 Appendix J). S-VAE (Bowman et al. (016) applies a standard GRU-based RNN variational autoencoder to the topologically sorted node sequence, with node features augmented by the infor- mation of incoming edges, and decodes the graph by generating an adjacency matrix. GraphRNN You et al. 2018 by itself serves as a decoder, we pair it with S- S-V encoder. GCN uses GCN en- coder while takes the decoder of D- VAE. DeepGMG L et al. 2018) similarly uses a GNN-based encoder but employs its decoder (which is similar to the one in D-VAE). Note that all these baselines are autoencoders and our objective is to compare the performance of the latent representa- tions.
14

---

Published as a conference paper at ICLR 2021
D MODEL CONHIGURATIONS AND TRAINING
D.1 EXPERIMENT PROTOCOL AND HYPERPARAMETER TUNING
Our evaluation protocols and procedures closely follow those of of et al. (2020); Zhang al. (2019) For OGBG-CODE, we only changed the following. We used 5-fold cross validation due to the size of the dataset and the number of baselines for comparison. Since we compared with vast kinds of models in addition to the OGB baselines, we swept over large range of learning rates and, for each model, picked the best from the set fle-4, 5e-4, le-3, 15e-4, 2e-3, 5e-3, 1e-2, 15e-3} based on performance on DGBG-CODE-15. We stopped training when the validation metric did not improve further under a patience of 20 epochs, for all models but D-VAE and DAGNN. For the latter two, used patience of 10. Moreover, for these two models used gradient clipping (at 0.25) due to the recurrent layers and a batch size 80. Note that OGB uses 10-fold cross validation with fixed learning rate of le-3, fixed epoch number 30, and batch size 128.
For NA and BN, we followed the exact training settings of Zhang et al. (2019) Appendix K). For DAGNN, started the learning rate scheduler at 1e-3 (instead of le-4) and stopped at maximum number of epochs, 100 for NA and 50 for BN (instead of 300 and 100, respectively). We also trained a sparse Gaussian process (SGP) (Snelson & Ghahramani 2005) the predictive model, as described in Zhang et al. (2019 Appendix L), to evaluate the performance of the latent representa- tions. The prediction results were averaged over 10 folds.
For the Bayesian network learning experiment we similarly took over the settings of Zhang et al. 2019), running ten rounds of Bayesian optimization.
D.2 BASELINE MODELS
All models were implemented in PyTorch (Paszke et al.) 2019). For OGBG-CODE, we used the GCN and GIN models provided by the benchmark. We implemented GAT model as described in Veličković et al. (018)) and GG-NN ei al. (2016). We used the SAGPool implementation of com/ All these models were im- plemented using PyTorch Geometric (Fey & Lenssen 2019). We used the parameters suggested in OGB (e.g., 5 GNN layers, with embedding and hidden dimension 300), with the exception of ASAP where we used 3 instead of 5 layers due to memory constraints.
et al. (2019) and ASAP from the Pytorch Geometric Benchmark Suite /ttpp:///iithie
rustyyss/ pytchhh
Since the D-VAE implementation does not support topological batching do, and also because of other miscellancous restrictions (e.g., a single source node and target node), we reimplement D-VAE by using our DAGNN codebase. The reimplementation reproduces the results reported by Zhang et al. (2119). See Appendix F For more details.
D.3 DAGNN IMPLEMENTATION
For DAGNN, we used hidden dimension 300. As suggested by OGB, we used independent linear classifiers predict sub-tokens at each position of the sub-token sequence. Similarly, we used linear classifier to predict the length of the longest path.
For the NA and BN datasets, took the baseline implementations well training and evaluation procedures from Zhang et al. 2019). In particular, we used the corresponding configuration of D- VAE for the BN dataset. For DAGNN, decoder of D-VAE (by replacing the use of VAV encoder in part of the decoding process with our encoder). Additionally, and for the experiment over BN. Since it did not offer improvement in performance for the longest path length prediction and for the experiment over NA but consumed too much time, for these cases we used unidirectional processing.
used the same hidden dimension 501 and adapted the
used bidirectional processing for token prediction over OGBG-CODE
E DETAILS ON THE LONGEST PATH EXPERIMENT
We observe that for the MPNN baselines, the longest path results shown in Table [ are much worse on the 15% subset than on the full dataset. We speculate whether the poorer performance is caused
15

---

Published as a conference paper at ICLR 2021
20000
50000
33000
40000
2003
Figure 6: Distribution of the longest path lengths, for OGBG-CODE (left) and OGBG-CODE-15 (right). To improve readability, we ignored tiny amount of graphs whose longest path length 30. There are 58 such graphs in OGBG-CODE and 21 in OGBG-CODE-15.
by purely size training data, or additionally by the discrepancy data distributions. Figure shows that the data distributions rather similar. Hence, conclude that the degrading perfor- mance of MPNNs on a smaller training set is due to their low sample efficiency, in contrast to DAG architectures (D- DAE and DAGNN) that perform similarly both the full set and the subset.
F REIMPLEMENTATION OF D D-VAE
The original D-VAE implementation processes nodes sequentially and thus is time consuming. Therefore, we reimplement D-VAE by using our DAGNN codebase, particular supporting topo- logical batching. Table 5 shows that our reimplementation reproduces closely the results obtained by the original D-VAE implementation.
Table 5: Predictive performance of latent DAG representations for NA and BN. Comparison of the original implementation and our reimplementation.
NA
BN
Model
RMSE
Pearson's 's
RMSE
Pearson's
D- VAE (orig)
0.375
0.924=a.00
0.281 20004
0.964 0.977
D- VAE (ours)
0.375
0.925
0.21940008
G ADDITIONAL ABLATION RESULTS
As mentioend in the main text, bidirectional processing is optional; it does not necessarily improve over unidirectional. Indeed, Table 6 shows that bidirectional works better on TOK-15 and BN, but unidirectional works better LP-15 and NA. However, either way, DAGNN outperforms all baselines reported in Table and 2 with only one exception: on LP-15, D-VAE performs worse than unidirectional but better than bidirectional.
Table 6: Bidirectional vs. unidirectional processing.
TOK-15
LP-15
NA
BN
Bidirectional?
F1
Ace
RMSE
Pearson's 's r
RMSE
Pearson's
No
28. 28.44
99.85-10a2 99.50+aa2
0.264=00m
0.964=
0.146++uus
0.992+0001
Yes
29.11
0.324
0.945
0.122-+0.00
0.993
16


Reviews:
[{"review_id": "o5QcADzboLR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work considers DAGNN for learning representations for DAGs. Compared with message-passing neural network, particularly D-VAE, there are three subtle and notable differences motivated by the properties of DAG: (i) attention for node aggregation, (ii) multiple layers for expressivity, and (iii) topological batching for efficient training. Some theoretic guarantees are established (similar to those in D-VAE). Experiments show an improved performance, and ablation studies validate the proposed modifications. I recommend a weak acceptance based on the present version and am happy to improve my rating if authors address my concerns.\n\n1. For Eq. (3), authors claimed that 'An advantage is that DAGNN always uses more recent information to update node representations.' However, compared with the other modifications, I didn't see any place to validate this statement. Can the authors explain more here to validate it is indeed an advantage?\n\n2. Theorem 2 and Corollary 3 are highly related and are suggested to be combined as one. Indeed, I did not see why 'Corollary 3' is a corollary.\n\n3. 'Remark 2. Topological batching can be straightforwardly extended to multiple graphs for better parallel concurrency: one merges the Bi for the same i across graphs into a single batch.' Can author give more details here, when graphs have different lengths?\n\n4. Authors proposed a parallel strategy for an efficient training. However, compared with D-VAE which is a sequential execution, the training time seems to be very close. Why? and what if DAGNN does not use the parallelization?\n\n5. about the BN experiment: compared with RMSE, BIC is a more reasonable metric to evaluate the final performance of the obtained DAG, as a better RMSE may indicate spurious edges wrt. the true graph. Also, the authors use the BIC score as the criterion when finding an optimal DAG. So what are the BICs for the respective methods? How does it compare with the BIC of the true graph?\n\n6. Also in the BN experiment part, 'Even though the DAG structure characterizes the conditional independence of the variables, they play equal roles to the BIC score and thus it is possible that emphasis of the target nodes adversely affects the predictive performance. In this case, pooling over all nodes appears to correct the overemphasis.' What does it mean by 'target nodes'? Can you also give more details about this reasoning and if possible, can you try other BN problems to validate this reasoning?\n\n7. the overall writing is OK, but may be improved in several parts. For example, 1) the introduction part has many comparisons with other approaches when stating contributions; separating them into two parts may be more clear.  3) in appendix D, please use subsections for 'MODEL CONFIGURATIONS AND TRAINING' for an improved readability.\n\n\n*** after reading rebuttal *** All my concerns are addressed, and I decide to improve my evaluation.", "extra_scores": {}, "extra_text": {}}, {"review_id": "X3ogc_fl9kZ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper introduces a model, Directed Acyclic Graph Neural Network (DAGNN), which processes information according to the flow defined by partial order. DAGNN can be regarded as a special case of previous GNN models, but specific to directed acyclic graph structures. The authors prove that the model satisfies the properties desired by DAG-based graph representation learning.Then they study topology batching on the proposed model to maximize parallel concurrency in processing DAGs. A comprehensive empirical evaluation is conducted on datasets from three domains to verify its effectiveness.\n\n\nReasons for score: Given the ubiquity of directed acyclic graphs, DAG-based graph neural networks have potential impacts on various fields. The authors propose an elegant and effective deep learning framework to learn node and graph representations on DAGs. My major concerns are the clarity of the model design, additional ablation tests, and sensitivity studies (see cons below). \n\nPros: \n1) The problem is interesting. Directed acyclic graphs are very common in the real world. An efficient and powerful DAG-based graph neural network is expected to solve many unsolved problems in various domains.\n\n2) The paper is well written. The authors introduce the framework based on the existing message passing neural network, which makes it easy to follow. The authors also present how this work handles special characteristics of DAGs. The techniques of the model are clearly stated. In particular, the comparison with highly relevant previous work is well explained. \n\n3) The authors provide sufficient experimental results, including comparative studies on four datasets with the state-of-the-art benchmarks and ablation tests, which show the effectiveness of the proposed framework.\n \n4) This paper provides a theoretical analysis of properties of the proposed model, which demonstrates that graph representations extracted by the proposed model are  discriminative.  \n\nCons:\n1) The framework needs more explanation. The authors introduce a recurrent neural network (Eq. 7) for updating node representation layer by layer. The input and past states are defined by the node representation at the last layer and the aggregated information from its predecessor nodes (i.e., message). As the authors introduced, these two arguments are switched in existing work. It would be better to provide more details about the design. \n-  One question is, how will the roles of two arguments affect the performance of the model?\n\n2) Although the paper provides several ablation studies, I still suggest the authors to consider the following ablation studies to enhance the quality of the paper: \n\t- What is the performance of the proposed model by changing the type of attention mechanism? Will it be relatively stable when using dot product attention which involves fewer parameters?\n\t- If we change the recurrent architecture to a feedforward neural network, what is the performance of the proposed model? Recurrent models are usually relatively slow in the training process and sometimes unnecessary.\n\t- How much does Bidirectional processing in recurrent neural networks help in improving the performance?\nIf the author can explain the above problems, it will be beneficial for people to understand this model.\n\n3) No sensitivity analysis. The authors provide detailed model configurations, yet it is expected to see hyperparameter tuning results. For example, the proposed framework is a multi-layer graph neural network. It would be nice to test the sensitivity of the number of graph layers. Such knowledge of message-passing neural networks may not apply to the DAG-based framework. It would be better to provide some sensitivity studies or theoretical proof. \n\n4) A minor concern about the ablation study: why didn’t the authors report the results on the LP dataset?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9al1-eAgIC6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a graph neural network formulation specific for directed acyclic graphs. In this formulation, the aggregation function also considers the information about the current layer. The model considers nodes following a topological batching in order to have the information of the predecessors when calculating aggregation of a node.\nThe system has been compared with several competitors on three datasets. The results are good in terms of metrics and seem promising also in terms of training time.\n\nThe proposal is clearly defined, but I would be happy if the paper also contains a very simple example considering a small DAG and showing some steps of the computation.\n\nThe proofs seem to me correct and the datasets seem complex enough to make the tests significant. Graph Neural Networks have come to the fore in recent years as a promising approach to solve many tasks and this work opens a good line of research.\n\nOne possible cons is that it focuses only on directed graphs. But this can also be a pro. It is important to continue to test whether this choice will lead to a system that can achieve significantly better results than other systems that are more general and do not pose this limitation. To test this aspect, three datasets are not sufficient, but the results look promising.\n\nAs for the tests, unfortunately, I could not run the scripts. It seemed that I could not download/create the datasets.\n\nI have only minor issues to highlight in the paper.\nIn formula (1), L is not defined, its definition is given later.\nIn figure 1 there are strange lines that should be removed.\nOn page 7, TargetInVocab baseline is considered but in the paper I can find only TargetInGraph. What is this baseline?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a graph neural network architecture to learn representations for directed acyclic graphs. Specifically, the proposed method performs the aggregation of the representations from neighboring nodes in the topological order defined by the DAG, with a novel topological batching scheme, which allows to process the message passing operations in parallel. The authors propose theoretical analysis of the proposed methods, to show that it is invariant to node indexing and learns an injective mapping to discriminate between two different graphs. The proposed method is further experimentally validated on multiple tasks involving DAGs, and the results show that it outperforms existing GNNs, including existing methods that can capture DAGs such as D-VAE (encoder). 

The reviewers were unanimously positive about the paper. All reviewers find the performance improvements and time-efficiency obtained with the proposed method to be satisfactory or promising, and one of the reviewers (R4) mentions that the tackled problem is important and the paper is well-written. However, there were concerns regarding insufficient explanations, missing ablation studies, and missing details of some parts of the proposed method. Yet, most of the issues have been satisfactorily addressed during the interactive discussion period. I agree with the reviewers that the paper is tackling an important problem, find the paper well-written, and the proposed DAGNN as practically useful. Thus I recommend an acceptance. 

However, the contributions of the proposed work over D-VAE, which also deals with DAGs, should be better described, as also noted by R2. The DAGNN uses attention, and can stack multiple layers as it is a more general GNN framework while D-VAE is a generative model, but these seem like incremental differences over D-VAE, and it is not clear which contributes to DAGNN’s superior performance over D-VAE. Topological batching is a clear advantage of DAGNN over D-VAE, but the experimental results showing the advantage of it over D-VAE’s sequential training was missing in the original paper (while it was added later to the appendix). I suggest the authors to introduce D-VAE in the introduction, acknowledge that it also tackles DAGs, and clearly describe how the proposed method differs from D-VAE encoder in a separate section. Also, there needs to be an analysis on why the proposed DAGNN outperforms D-VAE, as well as time-efficiency comparison with the original D-VAE in the main text. 

Decision: Accept (Poster)