Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: 
Positive points:
1.	Well-structured presentation with good figure illustration of the core problem and proposed framework.
2.	Accelerating the encoding of DAGs is of great importance and the proposed solution seems to be novel with convincing results.

Concerns:
1.	Not 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. 
2.	Dataset 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.
3.	RMSE 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.
4.	Though 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.

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

However 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:

- 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.
- 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.
- 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: ### Strengths
The 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.

### Weaknesses
- 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:
	- The explicit definition of the used aggregation and combination function;
	- Whether embeddings are used to map $\pi(i)$ to a feature space, and how those are learned;
	- An example of two graphs being mapped to the same isomorphism class.
- 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.
- 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?
- 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?
- 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.

__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_review: The proposed method shows favorable benefits compared to previous work. Overall, the strengths outweigh the drawbacks. Thus, my current recommendation is "Weak Accept".
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.)

*Edit: Comparisons to other methods have been added in replies to other reviewers, although the paper has not been updated.*
main_review: The PACE approach proposed by the authors appears to roughly consist of the following steps:
- Solve a graph canonicalization problem using an external solver, to obtain a canonical node ordering.
- Sort the nodes into that particular ordering.
- 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".
- Construct an attention mask such that each node can only attend to its predecessors.
- Run a transformer on the new sequence using this attention mask.

My 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:

- GNN models that utilize directed edges, such as
  - Gated Graph Neural Networks [(Li et al, 2016)](https://arxiv.org/abs/1511.05493)
  - the directed variant of Message Passing Neural Networks [(Gilmer et al. 2017)](https://arxiv.org/abs/1704.01212)
  - 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)
- A variety of adaptations of parallel Transformer methods to directed and undirected graphs, such as
  - Transformers with relative attention [(Shaw et al. 2018)](https://arxiv.org/abs/1803.02155)
  - the Graph Relational Embedding Attention Transformer model [(Hellendoorn et al. 2020)](https://openreview.net/forum?id=B1lnbRNtwr)
  - the Code Transformer model [(Zügner et al. 2021)](https://arxiv.org/abs/2103.11318)
  - Graphormer [(Ying et al. 2021)](https://arxiv.org/abs/2106.05234)

Although 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.)

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

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

For the experimental results, there were a few things that weren't clear to me:
- 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?
- 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?
- 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?

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

Something 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)?

Minor comment:
- 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.)

---

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

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.

**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.
review_title: null

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