PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphs
Authors: Zehao Dong
Muhan Zhang
Fuhai Li
Yixin Chen
Venue: ICLR 2022 Submitted (2022)
Keywords: DAG encoder
graph neural network
Transformer

Abstract: Optimization of directed acyclic graph (DAG) structures has many applications, such as neural architecture search (NAS) and probabilistic graphical model learning. Encoding DAGs into real vectors is a dominant component in most neural-network-based DAG optimization frameworks. Currently, most popular DAG encoders use an asynchronous message passing scheme which sequentially processes nodes according to the dependency between nodes in a DAG. That is, a node must not be processed until all its predecessors are processed. As a result, they are inherently not parallelizable. In this work, we propose a Parallelizable Attention-based Computation structure Encoder (PACE) that processes nodes simultaneously and encodes DAGs in parallel. We demonstrate the superiority of PACE through  encoder-dependent optimization subroutines that search the optimal DAG structure based on the learned DAG embeddings. Experiments show that PACE not only improves the effectiveness over previous sequential DAG encoders with a significantly boosted training and inference speed, but also generates smooth latent (DAG encoding) spaces that are beneficial to downstream optimization subroutines.

Under review as a conference paper at ICLR 2022
PACE: A PARALLELIZABLE COMPUTATION ENCODER FOR DIRECTED ACYCLIC GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Optimization of directed acyclic graph (DAG) structures has many applications, such as neural architecture search (NAS) and probabilistic graphical model learning. Encoding DAGs into real vectors is a dominant component in most neural-network- based DAG optimization frameworks. Currently, most popular DAG encoders use asynchronous message passing scheme which sequentially processes nodes according to the dependency between nodes in a DAG. That is, a node must not be processed until all its predecessors ently not parallelizable. In this work, we propose a Parallelizable Attention- based Computation structure Encoder (PACE) that processes nodes simultaneously and encodes DAGs in parallel. We demonstrate the superiority of PACE through encoder-dependent optimization subroutines that search the optimal DAG structure based on the learned DAG embeddings. Experiments show that PACE not only improves the effectiveness over previous sequential DAG encoders with signifi- cantly boosted training and inference speed, but also generates smooth latent (DAG encoding) spaces that are beneficial to downstream optimization subroutines.
processed. As result, they inher-
INTRODUCTION
Directed acyclic graphs (DAGs) ubiquitous in various real-world problems including neural architecture search (Elsken et al. 2019 Wen et al. (020)), source code modeling (Allamanis et al.) 2018), structure learning of Bayesian networks (Koller & Friedman [009] Zhang al. [2019). etc. One key challenge in DAG optimization problems is that it is not easy to use gradient strategies to quickly adjust the structure of DAG towards the right direction due to the absence of gradient information. Some earlier works propose to directly optimize the discrete DAG structure through black-box optimization techniques such as reinforcement learning (Zoph & Le 2016). evolutionary algorithms (Liu et al.) 2017), and Bayesian optimization (Kandasamy inherently less efficient. A more recent approach is to encode DAGs into some continuous space for searching, and various DAG encoders are developed. In general, these DAG encoding schemes fall into two categories: structure-aware encoding scheme (Ying et al. 2019 Wen et al. 2020 Shi et al. 2020) and computation-aware (performance-aware) encoding scheme (Zhang et al.
al. 2018), which are
2019 Thost &
Chen 2021 Ning et al. 2020).
Due the superior graph representation learning ability, graph neural networks (GNNs) have broadly achieved state-of-art performance on various graph learning tasks, such as node classification (Velick
ovic et al. 2018, (aamlton et al., 2017). graph classification (Xu et al. 2019) Zhang et al. 20118
Duvenaud et al. 2015), and link prediction (Zhang & Chen 2018 Zhang et al. (020). Basically,
GNNs follow the message passing scheme (Gilmer et al.) (017) where each node aggregates node
features from its one-hop neighborhood repeatedly to update its own feature, and this aggregation happens at nodes simultaneously. However, Thost Chen (202T) suggest that such a framework cannot exploit the inductive bias of the computation dependency defined by DAGs, thus failing to generate a smooth latent (DAG encoding) space beneficial to downstream optimization routines.
Hence, in order to model the dependency between nodes in DAGS, various GNNs specifically designed for encoding DAGs, such as D- VAE (Zhang et al. 2019) and DAGNN Thost & Chen 2021). are developed to inject the computation dependency between nodes into the representation learning process. Instead of updating node features simultaneously, these DAG encoders are constructed upon gated recurrent unit (GRU) and will not update the representation of node until all of

---

Under review as a conference paper at ICLR 2022
its predecessors are updated. One way to achieve this is to perform message passing sequentially following a topological ordering of the nodes. Such an asynchronous message passing scheme actually simulates how real computation is performed along the DAG-the message passing order respects the computation dependency defined by the DAG, thus better exploiting the inductive bias. However, one key limitation of such DAG encoders is that the encoding process is inherently sequential, precluding processing all nodes in parallel. Although DAGNN proposes a topological batching trick to accelerate the training speed by partitioning nodes into disjoint batches where nodes within a batch can be processed in parallel, the time complexity is still nower-boundee by the longest path in the DAG and the fundamental constraint of the sequential computation nature still remains.
Numerous efforts have been made to reduce the sequential computation cost in sequence modeling literature (Cho et al. 2014; Wu et al., 20T6). For instance, ConvS2S (Gehring et al. 2017) utilizes convolutional layers as building blocks to compute output representations at different positions, while Transformer (Vaswani et al. (2077) proposes to inject the position (order) information into the model through positional encoding, and then dependency between positions can be captured through the attention mechanism (Bahdanau et al. 2015; Gehring et al.] 2017) in parallel instead of resorting to recurrent neural networks (RNNs). However, the success of these techniques relies the inherent linear order of symbols in the input/output sequences that automatically characterizes the dependency between symbols. That is, the dependency between symbols is fully captured by their positions in the sequence. Such a condition is not satisfied by nodes in a DAG G = (V, F) since each node can have multiple predecessors instead of only one like in plain sequences, and the dependency between nodes forms (strong) partial order rather than a linear order. Thus, previous parallel sequence modeling methods would fail in the representation learning of DAGs.
In this paper, we propose a novel Parallelizable Attention-based Computation structure Encoder, PACE, to improve the computation efficiency over existing GRU-based DAG encoders. In order to borrow the power of Transformer for sequence modeling to DAG modeling problems, we need to design a positional encoding scheme specifically for DAGs which can fully capture the dependency between nodes in a DAG before applying the pairwise self-attention mechanism. To achieve this, we propose a GNN-based dag2seq framework which is proved to injectively map DAGs to sequences of node embeddings. This means, we are able to fully recover the DAG structure from these produced node embeddings, the same as the positional encoding in the original Transformer. After that, a Transformer encoder (with mask operation) is applied to the node embedding sequence to simultaneously learn representations for all nodes in the DAG through the self-attention mechanism. This way, PACE incorporates the relational inductive bias (Battaglia al., 2018 Xu et al. 2020) carried by DAG structures into the encoding process, while eschewing the recurrence in previous works thus greatly improving the parallelization and encoding efficiency.
To demonstrate the superiority of the proposed PACE model, we evaluate PACE against current state-of-art DAG encoders as well as other seneral-purpose graph encoders for undirected graphs. Experimental results show that PACE not only outperforms competitive baselines by generating smooth latent spaces that capture the similarity between DAGs thus facilitating the downstream search subroutines, but also significantly boosts the training and inference speed through parallelization.
2 BACKGROUNDS
2.1 PARALLELIZABLE SEQUENCE MODELS
Encoding the complexities and nuances of sequences plays central role in various machine learning tasks. including sentiment classification (Medhat et al., 2014). speech recognition (Abdel-Hamid et al. 2014), and other natural language processing (NLP) tasks (Khan et al. (016). For many years, sequential models, such as recurrent neural networks (RNNs) (Medsker & Jain 2001), were the primal way to solve the sequence encoding problem. These models are computationally expansive due to the sequential encoding process. Hence, many parallelizable sequence models are proposed, including Transformer /Vaswani et al. 2017). BERT (Devlin et al. 2019), etc. Our proposed PACE model is built upon the Transformer (encoder) architecture.
Transformer (Vaswani al. 2017) is arguably the earliest translation model that solves the sequence- to sequence task without using ecquence-aligned RNNs or convolutional architectures. Transformer relates information from different positions in the sequence through the (masked) self-attention mech-
2

---

Under review as a conference paper at ICLR 2022
I-layer CINN
Canonical labeling
(start
24
Encoding
Readout
Concat Sort
(end)
Input dug2seq framework
Sequence
Masked Transformer
encoder blocks
Figure 1: Illustration of PACE. The input DAG is first injectively represented as sequence through the dag2seq framework, and then the sequence is fed into multiple stacked masked Transformer encoder blocks. The operations of nodes (i.e. node types) are visualized colors, and nodes in the sequence is sorted according to the canonical label generated in the dag2seq framework.
anism to encode/decode the representation of items in the input/output sequence, and incorporates the order of the items into the encoding/decoding process through a positional encoding mechanism. Briefly, the positional encoding mechanism is an injective function Spe N + IR that represents the positions (i.e. indices) of items in the sequence as d-dimensional vectors. Hence, consistently outputs unique encoding for each position in the sequence. The Transformer architecture is inher- ently parallelizable and could capture the long-term dependency with ease, thus is broadly applied to sequence modeling tasks in following works (Dai et al. 2019 Al-Rffou et al. 2019 Devlin et al. 2019; Lewis et al. 2020). Recently, Transformer has been widely used in image processing, and has achieved the state-of-art performance on various image learning tasks, including object detection (Carion et al. 2020) and image recognition Doooviiskki et al. 2020).
2.2 DAG ENCODING PROBLEM
directed acyclic graph (DAG) G is represented as a pair (V, E) with V = fvi, U2,.. Un denoting the set of nodes and E E X denoting the set of directed edges. A DAG often carries computation. We use to denote an (computational) operation dictionary. For instance, the operation dictionary O for NAS-Bench- 101 dataset contains five operations: "Input", "Output", "3 convolution", "1 x 1 convolution", " and "3 x 3 max-pool". Let G (V, E) be a DAG whose nodes represent operations in O. Then the DAG G represents computation structure in which dependencies between operations are determined by directed edges in E. Hence, isomorphic DAGs define the same computation structure. Then the objective of the DAG encoding problem develop encoders that can generate embeddings to distinguish the computation structures defined by DAGS in the encoding space.
DAGs = (V, show close relation with partial order. For any two nodes U; V, E V, let < be binary relation such that U; I vy if and only if there is directed path from v; to tj. then the binary relation < defines a partial order on the node set V. Based on the partial order, sequential DAG encoders, such as D-VAE (Zhang et al. 2019) and DAGNN (Thost & Chen 2021), use GRU (Cho) ct al. 2014) to recursively encode nodes in the input DAG, where node is not encoded until all of its predecessors (those nodes with a < relation with it) encoded. Because of the possibly very long dependency chains, these sequential DAG encoders inherently share the same limitations as RNNs, such the slow training and inference speed and the difficulty capture long-term dependencies.
To address these limitations, it intuitive to generalize Transformer to the DAG encoding problem, since Transformer brings undoubtedly huge improvement However, Figure 2 illustrates that it can be ambiguous how to represent DAGs as sequences due to the complex topological structure of DAGs. Let V O be the function mapping each node in G to an operation in O, and fpe be the original positional encoding function in Transformer, One intuitive way to linearize DAG into sequence also used in GRU-based DAG encoders. However, the topological orders of nodes in DAG are often not unique. For instance, graph G1 in Figure has two different topological orders: V1, 02, U3, U4, Ut and U2 11 U3, U4, Us hence resulting in two different node sequences Seg, and Seq,- Note that this does not hurt GRU-based DAG encoders as they are invariant which topological order is used.
the RNN- based sequence models.
sort its nodes with a topological order, which is
3

---

Under review as a conference paper at ICLR 2022
To avoid the ambiguity of topological order, another ap- proach is to sort nodes according to a canonical order (i.e.. node index in the canonical form of the DAG) as suggested by Niepert et al.] (2016). For example, let v1, 12, V3, U4, vl be the nodes sorted by a canonical or- der. Then, we can linearize a DAG into a sequence (o(v1), fee (vi)), (o(v2), fre (o.()))) fpe (V,),, simi- lar to how Transformer represents a sentence. Although canonical order guarantees the generated sequence is unique for the same DAG, different DAGs might have the same sequence. For instance, DAGs G1 and G2 in Figure 2 are not isomorphic, yet they will be represented as the same sequence Seqz- This is because the positional encoding func- tion fpe only captures node positions in the sequence but fails to encode the node dependencies, causing a significant structural information loss.
62
Sorted in camonical order
Sorted in topological order
Seq1
Sequ
Figure 2: Illustration of the ambiguity when applying sequence models (such as Transformer) the DAG encoding problem.
In summary, it is not straightforward to generalize Transformer to DAGs. We need to design smart linearization method for DAGs which guarantees that the same DAG is transformed to the same sequence, while different DAGs are always transformed to different sequences, in order achieve lossless transformation.
THE PACE MODEL
In this section, we describe the proposed Parallelizable Atention-based Computation structure Encoder (PACE). The key component of PACE is dag2seq framework, which leverages graph can- onization procedure and graph neural network to transform DAGs into sequences while preserving the distinctiveness of different DAGs, so that the DAG encoding problem can be addressed efficiently by applying Transformer to the sequences.
3.1 THE DAG2SEQ FRAMEWORK
Here we describe the proposed dag2seq framework. Let G E,) be a labeled DAG (node labels are operations in O), where V (1, 21, n) ( the finite set of nodes, F is the set of directed edges, and o: V - O is function that associates to each node an operation in O. We denote the canonical form of G as C(G) isomorphic labeled graph C(G)) that is unique representation of its isomorphism class. That is, all labeled graphs isomorphic to G will have the same canonical form C(G). Since G and C(G) are isomorphic, there exists bijection
(VC, F., 00), which assigns to each labeled graph G an
V - Vc (note that VC = f,,,2 n)) between the node sets such that of (T (+)) = oi)) for all i E V and (I()), (j)) E EC if and only if (i.j) E E. The graph canonization process assigns a new index π(i) to each node i. Based on the new indices (i), the proposed dag2seq computes the positional encoding of node j E V (denoted as p,) as follows
aj- = Agg(( (3), (6,5)
Pj (ommbine(T())...o
(2)
where functions Agg and Combine follow the same definition Graph Isomorphism Network
(GIN) (Xu et al.) 2019)). From Equations (I) and (2). we can see that dag2seq uses the canonical
indices as node features and applies one-layer injective GNN obtain the positional encoding of
each node. Note that (i, E is equivalent to (Ii)), T()) EC. Hence, Equations 1 and (
can also be interpreted as applying a lne-layer injective GNN on the canonical graph C(G) with the
true node indices of C(G) as node features. For notation convenience, we use π : VVC + V to
denote the inverse function of म. Then Theorem describes how dag2seq generates sequences that
uniquely represent DAGs.
Theorem 3.1 Let G E,E, be a labeled DAG, and P1, P1.PP......P P.. be the positional encod- ings generated by dag2seq. If functions Agg and Combine are injective, then the sequence px-) (o(T (2)).Pr-<()))..... (o( (n)) (n)+ injectively encodes the com- putation structures defined by DAGs.
4

---

Under review as a conference paper at ICLR 2022
We prove Theorem 3.1 in Appendix A The significance of Theorem 3.1 that it provides way to injectively encode DAGs into sequences which fully preserves the node type information as well as structure information of the original DAGs. In other words, two labeled DAGs will be encoded into the same sequence if and only if they are isomorphic (their computation structures are the same). Then advanced parallelizable encoders (such the Transformer encoder) for sequence modeling can be applied to the DAG encoding problem to improve the efficiency of the encoding process, thus facilitating the downstream DAG optimization problems. Intuitively, the canonical form provides a unified node indexing for isomorphic DAGs which initially may have different node orderings, while the one-layer injective GNN encodes the direct predecessors of each node into its positional encoding. Then it is not difficult to see that from the canonical indices of nodes and their direct predecessors as well as the node types we can fully recover the original DAG, The one-layer GNN is parallelizable, in contrast to the sequential GNNs used in previous works (Zhang et al. 2019 Thost & Chen, 2021).
is also worth discussing the complexity of graph canonization. The graph canonization problem is theoretically at least computationally hard as the graph isomorphism problem, which is in NP but not known to be solvable in polynomial time nor to be NP-complete. However, getting the canonical form of graphs is not too difficult in practice, thanks to the well-known graph canonization tools such as Nauty (McKay& & Piperno 2014). Empirically, such tools usually return the canonical form of a reasonable-sized graph in seconds. Theoretically, Nauty has an average time complexity of (n), and polynomial-time graph canonization algorithms also exist for graphs of bounded degrees. We also found in our experiments that graph canonization adds a negligible overhead.
3.2 THE TRANSFORMER IN PACE
With the dag2seq framework to injectively map DAGs to sequences, we next develop the attention- based parallelizable encoder which consists of K stacked Transformer (encoder) blocks.
For each item (i)), Ps 1(0) in the output sequence of dag2seq. o(T (()) provides the opera- tion information, while the positional encoding Pa- contains the structural information. Hence, PACE concatenates the trainable embedding of operation o(>==((i) and the positional encoding Pz-1(i) (1) as the embedding e, of item in the sequence.
= Concat(Emb((d) (()))((m=)))))))))))))))))))))))
Then the sequence é1, E2, ..., en is fed into the first Transformer encoder block. Each transformer encoder block performs the multi-head self-attention mechanism (Vaswani et al.) 2017) update the embedding of each item in the sequence. We provide details of the multi-heat self-attention mechanism in Appendix C
In the original transformer encoder blocks, the attention operations are not masked. In other words, for any two items and j in the sequence, the embedding of item will be used to update the embedding of item j. Such unmasked operation is reasonable as the positional encodings {Px-16)); Vi} have already encoded the partial order between nodes. However, due to the complex dependencies a DAG may encode, fully relying on the positional encodings to capture such dependencies might not be enough. Therefore, we introduce a masked attention operation that helps better capture the dependency between nodes in practice. The masked attention operation can be specified through binary mask matrix M as follows.
Ma False, there exists True, otherwise
i to in C(G)
(4)
In this mask matrix M, element Mr, True indicates that the effect of item in updating the embedding of item j will be masked out. When Mi, = True, there is no (directed) path from node i to node j in the canonical form CGG). In other words, we only allow j's predecessors in C(G) (or equivalently, π -j))'ss 's predecessors in G) to participate in the updating of j's embedding. Such masking operation has two benefits: 1) the structure information of the DAG is strengthened in the masked self-attention, and 2) the partial order between operations in the computation structure is exploited, which aligns with the logic of real computation in the sense that the operation at some node does not depend its successor operations. We also empirically verify the effectiveness of the masked attention operation in the ablation study. The mask matrix M can be efficienly computed through the DFS algorithm the Floyd algorithm, which we describe in Appendix B
5

---

Under review as a conference paper at ICLR 2022
3.3 TRAINING METHODOLOGY
We design two ways to train the PACE model. One is by training a variational autoencoder (VAE) for DAGs that able to encode and decode/generate DAGs into and from a latent space, like D-V and DAGNN. On the other hand, since the proposed dag2seq transforms the DAG encoding problem to the sequence encoding problem, pre-training techniques in NLP are also suitable for training PACE.
Without loss of generality, we assume that there is single output node in each DAG that has no successor. If not, we can add a virtual output node and add directed edges from all nodes whose out-degree is 0 to the output node. When PACE is trained in VAE architecture, we use common trick in standard Transformers by assuming that there are at most N nodes in the input DAG. If a DAG has n < N nodes, we pad N -n end symbols the end of the sequence generated by dag2seq. Then PACE readouts the DAG encoding by concatenating the learned emheddings of the N symbols. When PACE is trained in a pre-training architecture, similar to the sentiment classification task in BERT, PACE takes the learned embedding of the output node as the DAG encoding.
Training PACE in VAE architecture. In the PACE-VAE architecture, we take PACE as the encoder, and connect the output of PACE with two fully connected (FC) layers to predict the mean and variance of the approximated posterior distribution in the evidence lower bound (ELBO) (Kingma) & Welling 2013). The decoder of PACE-VAF consists of K = 3 standard Transformer decoder blocks of dimension dg. Given the latent vector = to decode, the decoder uses an FC layer to reconstruct vector of dimension N x dæ, and the vector is then reshaped to a matrix Z of shape (N,, d which plays the same role as the "memory" matrix in a standard Transformer in NLP. Hence, the encoder-decoder attention layer in each Transformer decoder block takes the decoded matrix Z as the "Key" matrix and "Value" matrix, and uses the output from the previous self-attention layer as the "Query" matrix. Similar to the standard Transformer, during the generation, the decoder of PACE-VAE sequentially predicts nodes in G according to the learnt canonical order, and this process is ended until special symbol is predicted indicating the decoding process is completed. For each generated node i in the decoding process, we do a softmax to select the operation of the node, and use binary classifier to predict the existence of an edge between node and any node j << i. We describe more details of PACE- VAE and its parallelizable training framework in Appendix D
Training PACE in a pre-training architecture. After converting DAGS to sequences by the pro- posed dag2seq framework, PACE is essentially a sequence modeling encoder. Yan et al. (2020) validates that the pre-training architecture NLP that generates embeddings without using accuracies can better preserve the local structural relationship in the latent space. As such, PACE can also take the masked language modeling (MLM) (Devlin et al.) 2019) Yan et al.) (02T) objective for pre-training to capture the locality information of the computation structure defined by DAGs. For each input DAG, we randomly select 20% nodes for masking and prediction, where 80% of them are replaced with the [MASK] token and the remaining nodes are unchanged. The output embeddings are used to predict the original node operations o( o()- and we train PACE by minimizing the cross-entropy loss of the predicted node operations and the true node operations.
4 COMPARISON TO RELATED WORKS
Despite the great success of pureral-purpose GNNs in encoding undirected graphs, there have been relatively fewer GNN works proposed to capture the inductive bias encoded by the dependency between nodes in DAGs. S-VAE (Bowman et al. 2016) takes as input the sequence of node strings which consist of the node type as well as the adjacency vector of each node, and then applies a GRU-based RNN to the topologically sorted node sequence to encode a DAG. Following this idea, D-VAE (Zhang et al., 2019) proposes a DAG-style message passing framework that sequentially updates the DAG encoding following topological order of nodes. For each node a DAG, D-VAE takes gated summation aggregator to combine information from all its direct predeccessors, and then a GRU is used to update the node embedding based on the aggregated information and node type. Similar to the encoder of D-VAE, Thost & Chen (2021) propose DAGNN which also sequentially aggregates node features. It differs from D-V in the sense that the aggregator is constructed through the attention mechanism and it comes with layer notion in the DAG encoding process.
The proposed PACE model is closely related to these DAG encoders. However, there is a noticeable difference. Previous DAG encoders (i.e., S-VAR, D-VAE, DAGNN) share major limitation that

---

Under review as a conference paper at ICLR 2022
the sequential nature of the encoder precludes their parallelizabilityy. In constrast, PACE adopts dag2seq framework that encodes the dependencies between nodes in the positional embeddings, and then applies transformer to the node sequence to encode DAG parallelly.
EXPERIMENTS
In this section, we conduct experiments on popular DAG encoding datasets to validate the effec- tiveness and efficiency of the proposed PACE model against state-of-art DAG encoders and other veneral-purposs. (undirected) graph encoders.
5.1 DATASETS AND METRICS
NA and BN. The NA dataset consists of approximately 19K neural architectures generated by the software ENAS (Pham et 2018). Each architecture has its pre-computed weight-sharing (WS) accuracy on CIFAR-10 10 (Krizhevsky et al., 2009), and includes 8 nodes with the first node as the input node and the last node as the output node. The BN dataset consists of 200K Bayesian networks randomly generated by the brlearn package (Scutari) 2010). Each Bayesian network has 8 nodes and is associated with Bayesian Information Criterion (BIC) score that measures the architecture performance on the Asia (Lauritzen & Spiegelhalter 1988) dataset.
On NA and BN, following the experimental setting used in (Zhang et al. 2019 Thost Chen 2021h, the PACE model is evaluated under VAF architecture, and we take 90% NA/BN data as the training set and hold out the rest for testing. To make a fair comparison, we evaluate the quality of DAG encoders by measuring the prediction performance and the downstream search performance as suggested by Zhang et al. (2019). Briefly, a sparse Gaussian Process (SGP) regression model (Snelson & Ghahramani] 2005 is trained to predict the DAG performance from its encoding, and we use rooted mean square error (RMSE) and Pearson correlation (Pearson') 'r) as metrics to evaluate the prediction performance. When evaluating the downstream search performance, we perform Bayesian optimization (BO) in the DAG encoding space based on the SGP regression model, and compare the performance of the best searched architecture.
301) are two well- known neural architecture search (NAS) benchmark datasets. NAS101 (Ying et al. 2019) consists of approximately 420K neural architectures with pre-computed validation and test accuracies on CIFAR- 10, where each architecture has up to nodes and edges with the first node the input and the last node as output node. NAS301 (Siems et al. 2020) is surrogate benchmark for DARTS (Liu et al. 20186). Following Liu et al. (2018a): Yan et al. (202T), we randomly sample 1M neural architectures, where each architecture contains most 15 nodes.
NAS101 and NAS301. NASIO1 (NAS-Bench-10)) and NAS301
On NAS101 and NAS301, the PACE model is trained with the pre-training architecture using the MLM objective. Since better prediction performance of DAG encoders always facilitates the downstream search performance, we implement two popular BO-based downstream search methods, DNGO (Snoek et al. 2015) and DNGO-LS (Yan al., 2021), 1). and compare the downstream search performance of different encoders. For NAS 101, following the original work of Ying et al. (2019), we take regret as the metric evaluate the downstream performance, where the regret is the difference between the test accuracy of the (offline) optimal neural architecture and the test accuracy of the best searched neural architecture (after 20 rounds). For NAS301, since we do have an oracle for the optimal neural architecture, we use the test accuracy of the best searched neural architecture, instead.
5.2 BASELINES AND MODEL CONFIGURATION
On NA and BN, we compare PACE to all baselines used DAGNN: D-VAF, VAE Bowman et al. 2016), GCN (Zhang et al.) 2019). GraphRNN Youu et al. 2018 DeepGMG (Li et al. 2018). On NAS101 and NAS30I, we compare PACE with three undirected graph encoders: GIN (Xu et al. 2019), GAT /Velickovic et al. 2018), GCN (Kipf & Welling 2016). and current state-of-art DAG encoders: S- S-VAE, VAE, DAGNN.
The PACE model always uses Transformer encoder blocks to boost the training and inference speed. We use an embedding layer of dimension 64 to map node types to node type embeddings. The output dimension of the l-lyyer GNN in 2ag2seq framework is also 64. On NA and BN, we concatenate
7

---

Under review as a conference paper at ICLR 2022
Table I: Predictive performance on NA and BN.
NA
BN
Evaluation Metric
RMSE
Pearson's 's f
RMSE
Pearson's '
PACE
0.254 + 0.002
0.964 + 0.001
0.115 + 0.004
0.994 + 0.001
DAGNN
0.264 + 0.004
0.964 + 0.001
0.122 + 0.004
0.991 + 0.000
D-VAE
0,384 = 0.002
0,920 = 0.001
0.281 + 0.004
0.964 = 0.001
S-VAE
0.478 0.002
0.873 1 0.001
0.499 0.006
0.873 1 0.002
GraphRNN
0.726 0.002
0.669 1 0.001
0.779
0.007
0.634 1 0.001
DeepGMG
0.478 0.002
0.873+ 0.001
0.843
0.007
0.555 + 0.003
GCN
0.832 0.001
0.527 + 0.001
0.599 0.006
0.809 + 0.002
Table 2: Downstream search performance on NA and BN.
Model
PACE
DAGNN
D-VAB
S-VAE
(NA) Test accuracy f
95.08
95.06
94.80
92.79
(BN) Optimized BIC score
-11107.29
-11107.29
11125.75
11125.77
the positional encoding and node type embedding as the node features fed into the first Transformer encoder block. On NAS101 and NAS301, we use the summation of positional encoding and node type embedding, instead. All the experiments are done on NVIDIA Tesla P100 12GB GPUs.
5.3 EXPERIMENTAL RESULTS
NA and BN. According Table 1 PACE achieves the smallest RMSE and the largest Pearson's r on both NA and BN, indicating that PACE generates the smoothest searching space that captures the locality of DAGs. Furthermore, we notice that the improvement is more significant on NA. One possible reason is that DAGs in NA always have a Hamiltonian path which introduces relatively long-term dependency between nodes. Since the attention mechanism in PACE could capture the long- term dependency better compared to RNN-based DAG encoders, PACE can preserve the similarity shows, PACE detects
of DAGs better in the learned DAG embeddings. Furthermore, as Table 2 architectures with the best performance on both NA and BN. Such observation indicates that the smooth DAG embedding space can facilitate the downstream searching subroutines. addition, we also visualize the optimal detected architectures in Appendix E Finally, in analogy to D-VAE, also compare the reconstruction accuracy and the generation performance (i.c., the proportions of valid/ unique/ novel architectures in the generated DAGs) of the tested DAG autoencoders. It turns out that PACE still achieves the best performance, and the results are presented in Appendix
NAS101 and NAS301. Table 3 presents the results on NAS1O1 and NAS301. PACE significantly
outperforms undirected graph encoders and other DAG encoders on each dataset and each searching method. Similar to PACE, DAGNN and GAT also use the attention mechanism to model the dependencies (relations) between nodes. However, the attention mechanism these encoders is only applied to nodes and their direct predecessors (DAGNN) or adjacent nodes (GAT), hence making hard to capture the long-term dependency between nodes. On the contrary, PACE allows all predecessor nodes to participate in the attention mechanism while encoding the neighbors through positional encoding, which enables PACE to learn long-term dependencies as well as short-term dependencies with case, thus capturing the similarity of computation structure defined by DAGs more efficiently and more effectively.
5.4 COMPUTATIONAL COST
A key advantage of PACE is the parallelizable DAG encoding process, so we compare the compu- tational cost PACE to GRU-based DAG encoders (D-VAE and DAGNN), We use a single GPU for each experiment, and Figure shows our results. On datasets NA and BN, PACE, D-VAE and DAGNN are all trained with the VAE architecture. As all models are trained the same manner, both the training and inference time can reflect the DAG encoding speed. Hence compare the average training time per epoch and the total required training epochs to reach optimal performance to evaluate the computational cost. Figure
(a) and (b) show that PACE requires significantly
8

---

Under review as a conference paper at ICLR 2022
Table Experimental results NAS101 and NAS301.
NAS101 (Regret)
NAS301 (Ace)
Search Method
DNGO (%) |
DNGO-LS (%)
DNGO (%) f
DNGO-LS (%) f
PACR
0.391 + 0.241
0.278 + 0.178
94.507 + 0.165
94.547
0.145
DAGNN
0.445 + 0.224
0.448 = 0.127
94,445 + 0.219
94,433 = 0.156
D-VAE
0.439 0.203
0.430 + 0.222
94,453 + 0.148
94.428 0.131
S-VAE
0.458 0.175
0.451 0.225
94.332 0.183
94.371 = 0.203
0.593 0.177
0.518 + 0.201
94,451 + 0.224
94.411 + 0.198
GAT
0.597 0.269
0.509 + 0.187
94.430 + 0.171
94.421 = 0.202
GCN
0.627 + 0.161
0.538 + 0.233
94.448 + 0.149
94.404 = 0.160
(3)
(b)
Cc)
(c)
PACE
340
RACE
RACE
DARVN
60
80 8K 10A
MA00)
Figure 3: Computational cost.
less training time per epoch than D-VAE and DAGNN, while reaching optimal performance with fewer epochs on average. On NASIO1 and NAS301, as PACE uses a different training method (i.e., pre-training), we compare the overall training time and the average inference time per epoch to make a fair comparison. Figure 3 (c) and (d) indicate that PACE takes about average training time and roughly & average inference time compared to GRU-based DAG encoders (D- (D-VAE, DAGNN). Overall, PACE significantly reduces the computational cost against previous DAG encoders.
5.5 ABLATION STUDY
In the ablation study, demonstrate the effectiveness of proposed dag2seq (positional encoding) framework and the attention mask in PACE. From Table [ we have the following observations: 1) In general, PACE trained with attention mask outperforms the one without attention mask, indicating that the attention mask helps better capture the inductive bias of DAGs. Nevertheless, even without attention mask, PACE still performs relatively well because the dag2seq framework also captures the node dependencies. 2) We also find that the dag2seq framework is vital for the performance of PACE. Without 2sgq, PACE (without mask) almost completely fails at the NA dataset. This verifies the importance of 2ag2 for solving the ambiguity issue of DAG encoding illustrated in Figure
Table 4: Ablation study.
NA
BN
NAS101 (Regret)
NAS301 (Ace)
Model configuration
RMSE
Peanson's T
RMSE
Peurson's S
DNGO (%) DNGO-LS (%)
DNGO
DNGO-LS (600-LS(5)) (5)
Modell: dag2seg Mask
0.254
0.964
0.115
0.9942
0.391
0.278
94.507
94,547
Model2: dag2seg No Mask
0.255
0,967
0.119
0
0.179
0.368
94.501
94,505
Model3: dag2seq
0.498
94,401
CONCLUSION
In this paper, we have proposed PACE, novel DAG encoder based on Transformer. Unlike traditional RNN-based DAG encoders which sequentially encode DAG nodes, PACE is fully parallclizable, thus having a much better encoding speed. PACE incorporates the strong inductive bias through node-dependency-avv -wware positional encoding framework, dag2seq. and masked self-attention mech- anism. Experiments demonstrate that PACE not only generates smooth latent (DAG encoding) space beneficial to the downstream search, but also boosts the training and inference time significantly.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
The main theoretical contribution of our paper comes from Theorem 3.1 Clear explanations and complexity analysis provided in Section 3.1 while the complete proof of the Theorem is available in Appendix A Furthermore, our proposed DAG encoder, PACE, incorporates the mask operation in the multi-head self-attention mechanism, hence we describe algorithms to get the mask matrix in Appendix B and mathematically formulate the masked multi-head self-attention mechanism in Appendix In addition, as PACE can be trained in a novel VAE architecture that supports parallelizable training, we thoroughly explain the VAE architecture in Appendix [ All datasets (i.c. NA, BN, NAS101, NAS301) used our experiments are public and we provide clear explanations of these datasets in Section Our source code, which includes details of necessary data preprocessing. is provided in the supplementary materials, and we will make it public on Github in the future.
REFERENCES
Ossama Abdel-Hamid, Abdel-rahman Mohamed, Hui Jiang, Li Deng, Gerald Penn, and Dong Yu. Convolutional neural networks for speech recognition. IEEE/ACM Transactions on audio, speech, and language processing, 22(10):533--145 2014.
Rami AI-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3159-3166, 2019.
Miltiadis Allamanis, Earl Barr, Premkumar Devanbu, and Charles Sutton. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR), 51(4):1-37, 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. International Conference on Learning Representations (ICLR), 2015.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez- Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 10XXvv1806601 2018.
Samuel Bowman, Luke Vilnis, Oriol Vinyals, Andrew Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from continuous space. In Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning, pp. 10-21, 2016
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European Conference on Computer Vision, pp. 213-229. Springer, 2020.
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In EMNLP. 2014.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2978-2988, 2019.
Jacob Devlin, Ming-Wa Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long und Short Papers), pp. 4171-4186, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
10

---

Under review as a conference paper at ICLR 2022
David Duvenaud, Dougal Maclaurin, Jorge Squilera-Iparraguune Rafael Homee-Boomarreli. Timo- thy Hirzel, Alán Aspuru-Guss Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in Neural Information Processing Systems, 2015:2224-25 2232, 2015.
Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: A survey. J. Mach. Learn. Res., 20(55):1-21, 2019.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin. Convolutional sequence to sequence learning. In International Conference on Machine Learning, pp- 1243-1252.
PMLR, 2017.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning, pp. 1263-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL htttpps:://pocccecaiiiiee mewpeeedddd.nnn.nneeeereeeeeeeee neurips cc pctppappr///////1l...... 5dd9db5e033da httpa///wcccoooabaaaaaaaaaaaaaaa
pdf
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabás Póczos, and Eric P Xing. Neural architecture search with bayesian optimisation and optimal transport. NeurIPS, 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. Interna- tional Conference on Learning Representations (ICLR), 2017.
Wahab Khan, Ali Daud, Jamal Nasir, and Tehmina Amjad. A survey on the state-of the-art machine learning models in the context of nlp. Kuwait journal of Science, 43(4), 2016.
Diederik Kingma and Max Welling.
Auto-encoding variational bayes. arXiv preprint
1rXiv:1312.6114, 2013.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1XXi:1609 2016.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Steffen L Lauritzen and David Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157-194, 1988.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. Bart: Denoising requence-to-sequee pre-training for natural language generation, translation, and comprehension. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 7871-7880, 2020.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:/803.033 033340 2018.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei. Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European conference on computer vision (ECCV), pp. 19-34, 2018a.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hi- erarchical representations for efficient architecture search. arXiv preprint 2017.
11

---

Under review as a conference paper at ICLR 2022
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations, 2018b.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of symbolic computation, 60:94-112, 2014.
Walaa Medhat, Ahmed Hassan, and Hoda Korashy. Sentiment analysis algorithms and applications: A survey. Ain Shams engineering journal, 5(4):1093-1113, 2014.
Larry R Medsker and LC Jain. Recurrent neural networks. Design and Applications, 5:64-67, 2001.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-2023. PMLR, 2016.
Xuefei Ning, Yin Zheng, Tianchen Zhao, Yu Wang, and Huazhong Yang. A generic graph-based neural architecture encoding scheme for predictor-based nas. arXiv preprini urXiv:2004.014: 01899, 2020.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning, pp. 4095-41044 4104. PMLR, 2018.
Marco Scutari. Learning bayesian networks with the bnlearn package. Journal of Statistical Software, 35(i03), 2010.
Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang, Bridging the gap between sample-based and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems, 33, 2020.
Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter, Nas- bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008. 09777, 2020.
Edward Snelson and Zoubin Ghahramani. Sparse gaussian processes using pseudo-inputs. Advances in neural information processing systems, 18: 18:1757-1264, 2005.
Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pp. 2171-2180. PMLR, 2015.
Veronika Thost and Chen. Directed acyclic graph neural networks. ArXiv, abs/2101.009655, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pp. 6000-6010, 2017.
Petar Velickovic, Guillem Cucurull, A. Casanova, Adriana Romero, P. Lio', and Yoshua Bengio. Graph attention networks. ArXiv, 1bs/17100110033, 2018.
Wei Wen, Hanxiao Liu, Yiran Chen, Hai Li, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. In European Conference Computer Vision, pp. 660-676. Springer, 2020.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, al. Google's neural machine translation sys- tem: Bridging the gap between human and machine translation. arXiv preprint 10Xiv.1609.0874. 2016.
Keylu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? ICLR 2020, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https 7/openreviee www.ee..weeeeeeeeeeeeeeeeeeeeeee htt.eeeeeeooooommmorrrree A5km
12

---

Under review as a conference paper at ICLR 2022
Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representa- tion learning help neural architecture search? Advances in Neural Information Processing Systems, 33, 2020.
Shen Yan, Kaigiang Song, Fei Liu, and Mi Zhang. Cate: Computation-aware neural architecture encoding with transformers. arXiv preprint arXiv:2102.07108, 2021.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pp. 7105-7114, PMLR, 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning, pp.
PMLR, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1rXiv:1611.03584 2016.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5171-5181, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning archi- tecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Muhan Zhang, Shali Jiang. Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: variational autoencoder for directed acyclic graphs. Advances in neural information processing systems, 32, 2019.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010.16103. 2020.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint 11101116,, 2016.
13

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM 3.1
Let Ge = (V1 Ei, 01) and G2 = (V2, E2, 02) be two labelled graphs, then G₁ and G2 are isomorphic (i.e.G, and G2 represent the same computation structure.) if and only if their canonical form are identical, i.e. C(G1) = C(G2). Note that it means equality between the canonical forms, not isomorphism. Let C(Gi) = (v, EP, ,of) and C(G2) (V2 ET, oo then there exists bijections m Vi VIC and m2 1/2 V/2, and use #1 VVC Ví and 22 VV2 V/2 denote their inverse functions. Hence, we have C(G1) 2(G2) if and only if (1) (1) of (i) for Vi; and (2) (i.5) E Ef + (i,5) E E for Vi,j.
Next, we will prove Theorem (()= (r)1())) (o)=) (2)))))))())))...))))))))))))))) (o(T (xz). (x))). (x)+ can guarantee the distinctness of canonical forms C(G). For the notation convenience, let function f(r(j), (I()), (i.j) E E}) = Combine(x()) (j) Agg(T(() (i,j) E)) be the composition of function Agg and Combine, then it is injective if and only if both Agg and Combine are injective. Forthermore, we use Seq, to denote
by equivelantly showing that the sequence
the sequence ( (1)). (1)) (TT (2)), Px. (2))) (oI (x))) Pxj (m))) and Seq, to denote the sequence (0
(00mm((11)))))))))((()) (1)). Pm.))))) (02(mz (2)), Pm. (9)) (02 (n)). P Pn))()))
So far, we know C(G₁) # C(G22 + there (1) exist such that of + of (1), or (2) exist i such that (i.5) E Eी but (1,j) & E (equivalently, (1,5) & Ef but (i.j) E E
Now, let's prove C(G1) # C(G2) = Seq, # Seq2-
(1) For the first case, T2, T2 are the bijections that map G1 and G2 to their canonical forms, then we have:
01 ( (F (1))
= of)
02 (2( (i)) = of (π2(Tū (1))
= (
Since (f) * (i). then we get 01 (T * 02 (i)) indicating that Seq, * Seq2-
(2) For the second case, according to the definition of canonical form, we know that ( (i).
( गi (i)) E E + (i,5) E E (similarly, TT), (i)) E Eg + (i.5) E Es), )
As such, we get:
(a) ()) = [(mi(Ti 1 (i),
E F1))
(s. E Ef1)
Pag (0) = f(T2(TT5 (i)), (+), (T)), (i)) E Ex))
= (s, E E
Then, since (i,5) E Ef but (i,j) & ES, we have (s, E EF} + (s. E E Since function f is injective, then we have (x) 7 P=z'())) Hence, Seq, 7 Seq,
In the end, let's prove the other direction, i.e. Seq, * Seq, = ((G)) # C(G2). When Sey, # Se42 there must (1) exist i such that 01 ( (i)) + 02 (2 (i)) (2) exist j such that Pr)'()) # P=5 '1)
(1) For the first case, previous analysis, we have
of (i) = ( (I (1)) (i) 02( (i))
Hence, we can get (1) A of which indicates C(Gi) + C(G2).
(2) For the second case, according previous analysis, we know that:
P '1) = f(j. {s, (s. E Ef))
Paz' = SÚ. (s. () E Eg))
14

---

Under review as a conference paper at ICLR 2022
Since f is injective, ()) * ())' implies that {s, (s. E Ef) + (s. E which indicates that there exists such that (i,j) E E but (i,j) & Ey (or (i,J) $ E but (i,j) E E Henceforth, we get C(G1) + C(G2).
B MASK MATRIX
Here provide two potential ways to get the mask matrix in PACE. Following the same notation as the main paper, we use C(G) = (VC, EC ,0²) to denote the canonical form of the input DAG G.
DFS Algorithm This algorithm takes the canonical form C(G) as input and performs the DFS algorithm on the graph explore all the nodes of the graph. Before we start the deep first search, we traverse all edges in E to find the direct-successors of each node i, and then put them in set Si)). perform the DFS to get dependent set (i, and we have Mi,5 False Then, for each node and only if j E D(i).
Algorithm DFS Algorithm
1: Initialization: D(1) i Visited False for i VC]; source (start) node T = [i] (T is
stack).
2: Visited[i = True
3: while [ >
4: = T
5: delete j from
6: for & in S(j) do
7:
Visited = Flase then
8:
put & in D(i)
9:
Visited[k] True put k in T
11: end if
end for
13:
end while
Floyd Algorithm The Floyd algorithm is originally proposed for finding shortest paths in directed weighted graphs. Here, we initialize the edge weights to he 1, and implement the Floyd algorithm to find the distance dist(i. j) (i.e. length of the shortest directed path) between each node pair i, in C(G). Then we have Mi, False if and only if dist(i, 0.
Algorithm 2 Floyd Algorithm
Initialization: dist(i,j) if (i,J) EC else 2: for E Vc do for jorjer Vc do
4:
for k lorkel VC do if disl(jj,k) disl(j, dist(i, k) then dist(i,k) = dist(j,ū) i) + kist(i,k)
6:
end if 8: end for
end for
10: end for
C MULTI-HEAD SELF-ATTENTION MECHANISM
Here we introduce the multi-head (masked) self-attention attention mechanism in the Transformer encoder blocks of PACE. For notation convenience, of the kth Transformer encoder block, and use Hg to denote the input (i.e. the representation of the sequence generated by dag2seq) to the first Transformer encoder block. Furthermore, denote the
H₃ denote the output representation
15

---

Under review as a conference paper at ICLR 2022
number of heads in the self-attention mechanism as h, and the embedding dimension (of each item in the sequence) as Then the Transformer encoder blocks update representation Hş as following.
H softmax (K2))) VV
for j 1.2...h
(5)
d
Hk+1 = feed forward H
(6)
where Q HaW
K.9" Kg = H&W k.k- V = =H are the query matrix, key matrix, value matrix, respectively (i.e. W W W W are trainable parameter matrices); represents the concatenation operation; Ferd-forward is one-layer MI.. When we introduce the mask operation into the Transformer encoder block. let M be the mask matrix from the Floyd algorithm or the BFS algorithm, then we use following equation to replace equation 5 in the Transformer encoder block.
H softmax (K() + -o
VV2 for j = 1,2,..h
(7)
d
D MORE DETAILS ABOUT PACE IN THE VAE ARCHITECTURE
In the section, we describe the decoder of PACE-VAL VAE. Figure Iillustrates the overall architecture. In the main paper, we have introduced how PACE maps input DAGs to the latent space, here we focus on the decoder of PACE-VAE.
Nede reprocatatiincc
P1
12
1/4
Transforecr
Kry asiiss reatis
rellpee
Mansy nurs (NAA)
PACE
Concatmate
Node Excholding
MLP
GAN
Node oper
Input DAG
Encoder
Latent space
Learat casenical order:
start mobbl
Decoder
Figure 4: The illustration of PACE in the VAE architecture (PACE-VAE)
Similar to PACE, the decoder is constructed upon the Transformer decoder block. Each Transformer decoder block consists of a masked multi-head self-attention layer (i.e. Eugtion 7), multi-head attention layer (i.c. Equation except that the key matrix and value matrix are computed from points in the latent space), and a feed-forward layer (i.c. Equation 6). The decoder takes MLP as the embedding layer to generate node type embeddings as PACE. In analogous to the dag2seq framework in PACE, the decoder also uses GNN generate the positional encoding based on the learnt canonical order of nodes. Then the node embeddings and positional encodings are concatenated and then fed into multiple consecutive Transformer decoder blocks predict the node representations, which is used to predict the node types and the existence of edges. In analogous to the standard Transformer decoder, the decoder performs the shift right trick (i.e. the ith outputed node representation corresponds to the i 1th node in the sequence) and adds start symbol node (i.c. the black node Figure 4 at the beginning of the node sequence. Specifically, the canonical label of the start symbol node is different from any possible canonical label in the dag2seq framework to distinguish it's position. For instance, DAG in the searching space contains at most N nodes, then the canonical order of the start symbol node can be 0 or N + 1. Let denote the output representation of node i in the sequence, then it is used to predict the type of node i + in the sequence through MLP. Similarly, for any j < i, predict the existence an directed edge from node j + 1 to node + in the sequence. Note that the canonical order can be generated from the topological sort by breaking ties using canonicalization
another MLP, which takes the concatenation of o, and o; input, to
16

---

Under review as a conference paper at ICLR 2022
tools, such Nauty. Thus, for each node i in the sequence, any dependent node of this node must be arranged in a prior position in the sequence (i.e. j < i). In the end, based on these predictions (node representations),
perform the teacher forcing to train the VAE.
E VISUALIZATION OF DETECTED OPTIMAL ARCHITECTURES ON NA AND BN
NA
BN
DONVS
BIC: -11107.29
acc:
Figure 5: Best architectures on NA and BN detected by PACE.
In this section, visualize the optimal architectures detected by Bayesian optimization (over the latent DAG encoding space generated by PACE) on datasets NA and BN. Figure illlsstraee our results. On dataset BN, find that the detected optimal Bayesian network structure is almost the same as the ground truth (Figure 2 of (Lauritzen & Spiegelhalter (988). In the ground truth, there is another directed edge from node A (visit to Asia ?) node (Tuberculosis).
F RECONSTRUCTION ACCURACY AND GENERATION PERFORMANCE COMPARISON
Table 5: Recon. accuracy, valid prior, uniqueness, novelty and overall (ave) performance %
NA
BN
Methods
Accuracy
Unique
Novel
Overall
Accuracy
Unique
Novel
Overall
PACE
99.97
98.16
57.77
100.00
88.98
99.99
99.96
45.10
98.50
85.88
DAGNN
99.97
99. 98
37.36
100.00
84.33
99.96
99.89
37.61
98. 16
83.91
D-VA
99.96
100.00
37.26
100.00
84.31
99.94
98.84
38.98
98.01
83.94
S-VAE
99.98
100.00
37.03
99
84.25
99.99
100.00
35.51
99.70
83.80
GraphRNN
99.84
29.77
100.00
82.37
100.00
98.57
80.65
GCN
5.42
99.37
41.48
100.00
61.57
99.07
99.89
30.53
98.26
81.94
Models parameterized with neural networks contribute to the inductive biases of the deep generative models (Zhang et al., 2016 Keskar et al.) (207)). thus the quality of the DAG encoder can be characterized by the reconstruction accuracy (Accuracy) and the generation performance (i.e. the proportions of valid/ unique/ novel architectures generated DAGs.) of the corresponding VAE.
The reconstruction accuracy, prior validity, uniqueness and novelty are calculated in the same way as Zhang et al. (2019). Empirical results are presented in Table and we take the average these four measurements to characterize the overall performance of the deep generative model (i.e. VAE), which also measures quality of the DAG encoder. We find that PACE performs similarly well in reconstruction accuracy, prior validity and novelty with D-VAE DAGNN and S- S-VAE, while significantly improving the uniqueness. Hence, PACE achieves the best overall performance and generates more diverse DAG architectures.
17


Reviews:
[{"review_id": "OUe-E6-2c6P", "reviewer": "Reviewer_1m8b", "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": "### Strengths\nThe objective of the paper is clearly motivated and a need for a parallelizable architecture is apparent. The introduction and background sections make the paper more accessible for researchers not focused on DAG modelling. Furthermore, the main aspect of the proposed method, the dag2seq framework, does not depend on any specific architecture, but instead provides an algorithm to transform a DAG into a sequence-like input. This is favourable since future work can improve/replace the network architecture while maintaining the dag2seq framework, giving this work a potentially higher impact than a specialized architecture. The usage of isomorphism classes is well justified and has no obvious drawbacks. The application of the Transformer architecture for encoding and decoding of the graphs seems a suitable choice as well. The experimental results confirm the benefit of the architecture not only in efficiency, but also in performance.\n\n### Weaknesses\n- The explanation of the used GNN in Section 3.1 is not fully stand-alone and misses out details. The text can benefit from extended it or referring to an appendix section that clarifies:\n\t- The explicit definition of the used aggregation and combination function;\n\t- Whether embeddings are used to map $\\pi(i)$ to a feature space, and how those are learned;\n\t- An example of two graphs being mapped to the same isomorphism class.\n- While transforming a DAG into a sequence of positional encodings is beneficial in having more flexibility in the architecture choice, it does not incorporate an inductive bias of the graph adjacency matrix as the message passing methods do. This also becomes apparent from the fact that an explicit masking strategy for introducing back some graph structure helps in its prediction. Similarly, as in NLP, relying on positional encodings can have a considerable impact on learning with data sparsity - on small datasets, the message passing algorithms (D-VAE/DAGNN) might outperform PACE. Thus, an experiment on e.g. the BN dataset with different training set sizes (e.g. 2k, 5k, 10k, 20k) is necessary to validate/analyze this aspect of the proposed architecture.\n- Section 5.2 misses out a discussion of how the hyperparameters, especially network sizes, have been chosen across baselines to ensure a fair comparison. Was this done on number of parameters, computation time, etc.? Or how is a fair comparison ensured otherwise?\n- Regarding the last aspect, the training time of PACE on the BN dataset in comparison to the asynchronous message passing algorithms is not as much lower as the text might suggest (35mins per epoch compared to 45/50mins). Does the Transformer architecture in PACE have more parameters than DAGNN/D-VAE? Can DAGNN/D-VAE benefit by having more parameters for the given datasets?\n- A drawback of the dag2seq encoding method is that finding the canonical form of a graph can be a computationally-expensive pre-processing step. Thus, it is unclear whether PACE can actually encode an unseen graph, including the required pre-processing step, faster than an asynchronous message passing method at inference. Figure 3 seems to not include such a time comparison.\n\n__Post-rebuttal update__: I appreciate the authors' rebuttal, and most of my questions have been sufficiently answered. I think the paper will significantly improve by incorporating these changes. In light of the fair concerns of other reviewers and the missing update of the main text, I will stay with my initial score, which was already weakly positive.", "summary_of_the_paper": "This paper proposes an encoder architecture for directed acyclic graphs which is parallelizable in computation and thus more efficient than asynchronous message passing alternatives. The model is based on representing the graph in its canonical form, i.e. a unique representation of its isomorphism class, which is transformed into a positional encoding and combined with a Transformer-based encoder. In experiments on neural architecture searches and Bayesian networks, the proposed architecture outperforms related methods.", "summary_of_the_review": "The proposed method shows favorable benefits compared to previous work. Overall, the strengths outweigh the drawbacks. Thus, my current recommendation is \"Weak Accept\".", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EA18qLoJ5ad", "reviewer": "Reviewer_d1eo", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nPositive points:\n1.\tWell-structured presentation with good figure illustration of the core problem and proposed framework.\n2.\tAccelerating the encoding of DAGs is of great importance and the proposed solution seems to be novel with convincing results.\n\nConcerns:\n1.\tNot enough technical motivations for creating such a structure. I can understand why the structure could make it parallelizable, however, why we choose such as combination of the dag2set + masted transformer is still not well-presented. \n2.\tDataset with larger graphs (graph with more nodes) is needed to demonstrate the performance. Also, better downstream tasks should be added for validating the proposed method: (1) it’s better to combine the proposed method with advanced NAS baselines, the BO-based method is well-recognized in the AutoML domain but not for the latest NAS community. (2) it’s better to conduct other task for validating the graph encoding model such as protein classification, computer program encoding, etc. NAS task itself could be of too much variance to validate the performance.\n3.\tRMSE and Pearson correlation may not be good metric for validating the performance even compared to non-parametric ranking metrics such as Kendall Tau ranking coefficients.\n4.\tThough comparing the training speed is good to show the general speed of learning the models, but I don’t think it’s good to show the benefit of parallel encoding of the nodes compared to using the inference speed.\n", "summary_of_the_paper": "The paper presents a new architecture for encoding the directed acyclic graphs into embedding vectors to benefit the downstream applications. The proposed architecture breaks the limitation of sequentially encoding the nodes of a DAG, and could parallelly encode the nodes of each graph so that the learning and inference speed could be much improved. The proposed method is validated on encoding neural architectures collected in the NAS benchmarks and shows better effectiveness and efficiency compared to existing graph encoding methods.", "summary_of_the_review": "Based on the above concern described above, I currently tend to weakly reject the paper but would like to hear more feedback from the author and discussion from other reviewers towards the final decision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9OjiYs8GZJo", "reviewer": "Reviewer_rAFV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have enjoyed reading this paper; it was well-written, to-the-point and it clearly highlighted what it brings to the table compared to prior art. The empirical performance which was provided also seemed convincing to me. While the novelty is somewhat limited (the paper essentially proposes a novel, specialised, PE for Transformers), I think that the area of application (DAGs) is interesting and prevalent enough for such a study to be warranted and useful.\n\nHowever I also found that the paper has several shortcomings, in terms of the extents of its evaluation, contrasting with relevant prior work, and possible discussions on the model's limitations. I would invite the authors to carefully address the following, after which I would be happy to support the paper's acceptance:\n\n- Foremost, PACE's contribution is centered on a DAG-friendly positional representation for Transformers. In doing so, however, based on the writeup and references, the authors seem unaware of the flurry of recent work on Graph Transformers, which generalise both the Transformer and its positional encoding to the (general) graph domain. Important references that the authors should discuss include: (Dwivedi and Bresson, AAAI'21 DLG), SAN (Kreuzer et al., NeurIPS'21), Graphormer (Ying et al., NeurIPS'21), GraphiT (Mialon et al., 2021). While some of the above have only recently been published, they have been available on the arXiv for a significant time prior to the ICLR deadline. Properly contrasting PACE against such proposals is, in my opinion, crucial to confirm that a DAG-specific PE is even necessary compared to the more generic ones.\n- The authors position most of their evaluation setup based on DAGNN's, and they focus primarily on evaluating it in the self-supervised setting (e.g. with a VAE pipeline). However, DAGNN also evaluates their work on the ogbg-code benchmark, which seems to be missing from this paper. As ASTs are a standard application area for DAG-based processing, it would be very useful to show PACE's performance in this case.\n- Lastly, and somewhat relatedly, even if we are able to fully parallelise the dataflow over a DAG-specific GNN, I would assume that for some tasks the complexity of covering the entire DAG's diameter may be unavoidable. For example, any dynamic programming task over a DAG that requires spreading information from a source vertex (e.g. finding shortest path lengths from a given source vertex). I would like to see some discussion from the authors regarding this.", "summary_of_the_paper": "The authors propose PACE, a Transformer-based architecture for directed acyclic graphs (DAGs). By providing a DAG-specific positional encoding (using canonicalisation and GINs), the claim is that a fully-connected self-attentional model can be executed over such an input, ameliorating the requirement of following the DAG's topological structure in an RNN-like fashion. The proposed model is evaluated over neural architecture search datasets, showing improvements over relevant baselines.", "summary_of_the_review": "In general I believe the idea is worthy of publication. However the concerns I presented, especially the fact the evaluation does not completely match DAGNN's and the relevant graph Transformer literature is not compared against, means the paper could benefit from another iteration of improvements. If the authors satisfactorily update the paper in response to my comments, I will back the paper for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5j7uq4a1MWD", "reviewer": "Reviewer_vSGS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The PACE approach proposed by the authors appears to roughly consist of the following steps:\n- Solve a graph canonicalization problem using an external solver, to obtain a canonical node ordering.\n- Sort the nodes into that particular ordering.\n- Apply a graph neural network to the raw node indices of this node ordering for a single step. Use the resulting node embeddings as \"positional embeddings\".\n- Construct an attention mask such that each node can only attend to its predecessors.\n- Run a transformer on the new sequence using this attention mask.\n\nMy main concern with the paper is that the authors motivate their approach as a way to encode long-range dependencies in DAGs in parallel, but do not have any discussion of prior work on encoding directed-but-not-necessarily-acyclic graphs, or prior work on applying transformers to graphs. These seem like very important baselines to consider, but the authors only compare with RNN models for DAGs and a selection of undirected GNN models. Notably missing baselines and citations of related work include:\n\n- GNN models that utilize directed edges, such as\n  - Gated Graph Neural Networks [(Li et al, 2016)](https://arxiv.org/abs/1511.05493)\n  - the directed variant of Message Passing Neural Networks [(Gilmer et al. 2017)](https://arxiv.org/abs/1704.01212)\n  - some of the other approaches discussed in [\"Relational inductive biases, deep learning, and graph networks\" (Battaglia et al., 2018)](https://arxiv.org/pdf/1806.01261.pdf)\n- A variety of adaptations of parallel Transformer methods to directed and undirected graphs, such as\n  - Transformers with relative attention [(Shaw et al. 2018)](https://arxiv.org/abs/1803.02155)\n  - the Graph Relational Embedding Attention Transformer model [(Hellendoorn et al. 2020)](https://openreview.net/forum?id=B1lnbRNtwr)\n  - the Code Transformer model [(Zügner et al. 2021)](https://arxiv.org/abs/2103.11318)\n  - Graphormer [(Ying et al. 2021)](https://arxiv.org/abs/2106.05234)\n\nAlthough some of these are application specific, most are quite general, and could easily be adapted for the neural architecture search tasks considered here. I also don't see any particular reason to believe the particular choices made here for PACE would lead to better performance than these prior approaches, especially the models that are based on a Transformer backbone. Also, the Transformer-based methods should already be similarly parallelizable to the PACE method, which was one of the main stated benefits of PACE over the RNN-based methods. (If some of these methods are added, I would be willing to raise my score.)\n\nAnother piece of related work is [\"Novel positional encodings to enable tree-based transformers\" (Shiv & Quark, 2019)](https://proceedings.neurips.cc/paper/2019/file/6e0917469214d8fbd8c517dcdc6b8dcf-Paper.pdf) which proposes a set of positional encodings for trees. This doesn't target DAGs, but is closely related to PACE in terms of defining a new positional encoding and so I think it should be discussed.\n\nThe authors describe a few techniques for training the PACE architecture before fine-tuning it on a classification task: it can be trained as a VAE over graphs, or using a mask-based objective similar to BERT. Somewhat confusingly, they the VAE \"training\" but the BERT version \"pretraining\". But as far as I can understand it, both methods are interchangeable unsupervised training objectives, which could either be used as training or as a pretraining step before fine-tuning. Am I missing something? I'm also not sure if there is a fine-tuning step for any of the experiments or not.\n\nFor the experimental results, there were a few things that weren't clear to me:\n- It wasn't clear what objective was used to train all of the baselines for each of the methods. Were all of them trained according to a BERT-like objective or a VAE objective, according to the task?\n- The paper states that \"a sparse Gaussian Process (SGP) regression model is trained to predict the DAG performance from its encoding\" for the NA and BN tasks. Is this possible for all of the baselines? If not, how were the baselines trained?\n- On NAS101 and NAS301, what is the actual training procedure? Is there some downstream neural network that outputs an accuracy estimate as a regression problem? Or is the model used as a generative model in some way?\n\nI think there should be at least one experiment where the methods are all trained with a single objective and then evaluated on that objective, to determine how easily the models can learn. As it is, it seems like the models are trained using an unsupervised objective and then evaluated with some downstream task without being trained directly on that task? Although perhaps the NAS101 and NAS301 tasks involve fine tuning, it is very difficult to tell from the paper.\n\nSomething else that is likely worth discussion: At least for training the VAE, the canonical ordering appears to be used both for computing positional embeddings as well as for determining the decoding order. It seems important to disentangle these two properties, since the ordering of the output can have a significant impact on the accuracy of sequence models (see for instance [Vinyals et al. (2016)](https://arxiv.org/pdf/1511.06391.pdf)). For the \"no dag2seq\" ablation experiment, was the canonical ordering still used for decoding, or was it removed from both the encoding and the decoding? It would be good to have results for both conditions, to determine whether the drop in accuracy is because of the input encoding or because of the output order. (Also, what happens in the \"Mask & no dag2seq\" setting)?\n\nMinor comment:\n- On page 4, it states that the Agg and Combine functions are the same as in the GIN paper. However, there are multiple different things called \"Aggregate\" in the the GIN paper, and it is ambiguous which one you mean. Also, in GIN the inputs are vectors, not integers. It would be better to write out exactly what definitions you mean. (I think there is also a typo, in that the Agg function should take a set, like $Agg(\\\\{\\pi(i) | (i,j) \\in E \\\\})$, but it is written as taking two arguments instead.)\n\n---\n\n**Edit (Nov 23):** I have raised my score from 3 to 5 in light of the new experimental results, which address my main concern with the original paper. See my comment below.\n", "summary_of_the_paper": "This paper introduces PACE, a method for converting a labeled directed acyclic graph into a sequence so that it can be fed to a Transformer architecture, along with a small modification to the Transformer to incorporate DAG structure. The authors cast their approach as a parallelizable alternative to some existing methods for encoding DAGs, which include GRU based approaches and undirected GNN based approaches, and show that their method outperforms those techniques on neural architecture search tasks. (However, the authors do not discuss or compare with existing methods for encoding of directed but not-necessarily-acyclic graphs, including other parallelizable approaches using Transformers.)\n\n*Edit: Comparisons to other methods have been added in replies to other reviewers, although the paper has not been updated.*", "summary_of_the_review": "The paper misses a significant body of related work on directed graphs and graph adaptations of Transformers, which would be necessary for a fair evaluation of their approach. The specific architecture choice seem fine but not especially novel or well motivated, and there are many missing details regarding the experimental results.\n\n**Edit (Nov 23):** The authors have provided experimental results for other Transformer-based graph models, and PACE still shows strong performance on their tasks. Many of my questions about missing details have been answered in the discussion, although it is difficult to evaluate this fully without a revised version of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your first (hopefully of many!) submissions to ICLR.
This work describes a method for allowing nodes to be processed concurrently instead of sequentially, allowing for a reduction in computation time.
The reviewers identified a number of concerns about the paper (lack of citations and baselines, an additional experiments demonstrating scale, and a number of clarifications and motivation in the text). The authors addressed the majority of these concerns due the rebuttal. I'm afraid a promise of a revised manuscript is not a sufficient substitute for the reviewers seeing a revised manuscript, and due the nature of the feedback, a revision is needed, which the reviewers have not seen to check their concerns are fully addressed. Therefore, at this stage, unfortunately, I recommend rejection.
Decision: Reject