Transformers over Directed Acyclic Graphs

Summary

The paper proposes an attention mechanism for directed acyclic graphs. Specifically the reachability to/from nodes is considered for a given node and the unreachable nodes are masked out. The authors use this attention mechanism in existing graph transformers for undirected graphs. Further the paper also proposes a new PE for directed graphs that considers the maximum depth of the node from the root nodes. The method is evaluated over source code and citation datasets and authors show it improves existing transformer performance.

Strengths

1. The method achieves state of the art results when induced in transformer architectures on datasets used 2. Method is claimed to be parallelizable and results in faster training compared to asynchronous methods

Weaknesses

1. Regarding limiting the receptive field of the transformer, the method selects nodes up to path length k. But a principle question arises about “How to select k?”. As of now it seems to be a heuristic or a dataset dependent parameter, which limits the novelty of the work as it is straightforward to apply attention in the top k hop reachable nodes in order to induce some notion of structure in the transformer. 2. Considering that the method only limits the attention to reachable nodes and uses topological depth as PE in existing methods the novelty and contribution seems limited. 3. The proposed attention mechanism that is restricted to reachable nodes, may suffer from learning issues when a node label depends on non-reachable nodes. For example if the label of a child node depends on sibling nodes but those are not reachable and the transformer used is of single layer. The same issue may arise with more layers etc. if there exists label dependence on farther non-reachable nodes. This is where the fundamental strength of the transformer lies over GNN that it doesn't need to wait over many layers for the information to be propagated. But with the proposed modification this property is lost. Missing Citations: 1. https://proceedings.mlr.press/v162/dong22b.html

Questions

1. Regarding limiting the receptive field of the transformer, the method selects nodes up to path length k. But a principle question arises about “How to select k?”. Can the authors comment on a more principled way of selecting k rather than keeping it a heuristic or a dataset dependent parameter? 2. In table 6, the results for the base transformer model and proposed method without DAGRA are the same in ogbg-code2. Is this because no PE is used and the rest of the architecture remains the same? 3. Do the authors see any issues in learning with the proposed attention mechanism that is restricted to reachable nodes? For example if the label of a child node depends on sibling nodes but those are not reachable and the transformer used is of single layer. The same issue may arise with more layers etc. if there exists label dependence on non-reachable nodes. This is where the fundamental strength of the transformer lies over GNN that it doesn't need to wait over many layers for the information to be propagated. But with the proposed modification this property is lost. Can the proposed framework be adapted to handle such cases?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

1 poor

Limitations

Limitations of the method have been addressed in the paper.

Summary

This paper adapts transformers to directed acyclic graphs. It restricts the receptive field of each node to its predecessor and successor nodes so that it faithfully captures the DAG structure. It also incorporates positional encodings based on the node depth. Extensive experiments show that it can improve performance of different kinds of baseline transformers.

Strengths

1. The proposed method is efficient and versatile. It can improve performance of a broad spectrum of transformers. 2. The problem of adapting transformers to DAGs is under-explored. 3. The analysis and experimental results regarding $k$ is surprising and inspiring.

Weaknesses

1. The datasets used in this paper are rather small. As efficiency and versatility are two key advantages claimed by the paper, can the authors include experimental results on larger graphs, like ogbn datasets?

Questions

1. The authors mentioned that they used the same hyperparameters as baseline transformers. Does this include learning rate, weight decay and dropout? If so, one only needs to integrate the proposed module without searching any hyperparameters (as long as $k$ is large enough) and can immediately facilitate an enhancement in performance. 2. See weakness 1.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Most limitations have been addressed.

Summary

The paper proposed a new approach for DAG representation learning using transformer. The representation learning on DGA is significant as DAG can be adapted into many real-world problems, which is also explained in the paper. In addition, the DAG can be formed into a sequence of nodes so that it is naturally to think about using transformers to model. The paper conducted comprehensive experiments to support its claim.

Strengths

The paper utilizes transformer to achieve representation learning on DAG, which is natural. Although transformer has been used on graphs, they are mostly for undirected graphs. The paper tells the story in an easy-to-read way. It also conducts extensive experiments to show the superior performance of the proposed model. The task the paper wants to solve is significant in that DAG can be naturally adapted to many real-world applications. This has also been discussed in the apper.

Weaknesses

(1) It seems that there is one paper that does the same thing [1]. I think this paper should at least be discussed in the paper. (2) I was wondering why some models in Table 2 and Table 2 are not present in Table 4 and Table 5, such as PNA, DGANN. (3) Will the choice of the root node affect the final results? [1] Dong et al., PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphs. 2022

Questions

See weakness.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations have been discussed by the paper.

Summary

The paper proposing a new Transformer-based graph neural network for directed graphs (DAGs) that restricts the receptive field size of self-attention and adds depth-based node embeddings to improve learning from DAGs. The resulted model is more efficient than previous Graph Transformer models and at the same time more effective in different DAG tasks as shown in many experiments.

Strengths

1. The problem of learning from DAGs is interesting and important. Improving Transformers for this problem is a reasonable direction. 2. The introduced improvements are simple, but effective. 3. Computational complexity analysis in Section 3.5 is a nice addition. 4. Experiments are overall convincing. 5. The paper is easy to follow and presented well.

Weaknesses

While I enjoyed reading the paper, the paper needs to address the following weaknesses: 1. The paper is missing related works [A, B], which seem to be doing exactly the same as DAGNN by proposing what they call GatedGNN. Therefore, citing DAGNN but not citing A/B can be misleading for readers. 2. Papers [C, D] are also related and it would be nice to discuss them as well. Given their recent appearance it's not necessary to empirically compare to them (although it would make the paper stronger), but they should be discussed. In particular, [C] is solving the same ogbg-code2 task, but achieves much better performance, can the authors discuss why? [D] is proposing a Transformer-based [40] graph model for DAGs and also add node depth-based PE embeddings similar to those in this submission + degree-based embeddings based on [40] (which could further improve the results in this submission). Given these papers, L122: "to the best of our knowledge, transformers have not been studied particularly in the context of DAGs" should be rephrased. 3. The DAGRA component of the method does not seem to leverage two important sources of information: (1) the direction of edges -- node predecessors and successors are treated equally based on L163-164; (2) the shortest path distance between nodes -- the mask is equal to 0 or −∞ in L203. Even though the DAGPE embeddings can help to recover this information, leveraging (1) and (2) seems very natural and could improve results by better distinguishing certain DAG structures. In related papers using Transformers for undirected/directed graphs, (1) and (2) are leveraged. For example, in [C] the forward and backward edges are treated separately, and in [40], [C], the shortest path distance is used in masking. 3. Section 3.3's conclusion is not very clear. Is this section trying to say that all nodes will eventually communicate with each other if enough layers and/or large k are used? Please elaborate/rephrase. 4. Results on ogbg-code2 in Table 6 are a bit confusing, because at first it looks like DAG+TF/SAT are using DAGPE, but from the text it sounds like DAGPE is not used. I think it would be more clear to report both results, with DAGPE and without it, even if the latter is better so that the Table does not have blank entries. **Minor issues:** - "partial order" - wouldn't it be more appropriate to use "topological order" that is often used in DAG context (e.g. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.topological_sort.html and [A, B])? "partial order" seems to be more relevant to sets. - In Tables, bolding results per pair makes sense, but baseline's top performance should be highlighted too. Also, the overall top performance across all rows can be underlined (or highlighted in some other way). - In Fig. 3, it's hard to conclude that DAG+Nodeformer separate classes better, so I don't think this visualization is helpful in the main text. - All equations should be numbered so that reviewers and readers can refer to them easily. - L130: "in more important fields than" - it's a quite subjective statement - L154: "[a] given node’s predecessors" - L169: "regular transformers (e.g., Eq. 2)" - Eq. 1? - L168: "still very different" - please elaborate how is it different given that k=∞ is the best *References:* - [A] Graph HyperNetworks for Neural Architecture Search. ICLR 2019. - [B] Parameter Prediction for Unseen Deep Architectures. NeurIPS 2021. - [C] Can We Scale Transformers to Predict Parameters of Diverse ImageNet Models? ICML 2023. - [D] Transformers Meet Directed Graphs. ICML 2023.

Questions

See Weaknesses above. I'm looking forward to the author's response and will be willing to update my score.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are discussed, which is appreciated. L344 says that "we found only a limited number of DAG datasets", so one suggestion would be to use a dataset of DAGs introduced in [B].

Response to Rebuttal

Thanks to the authors for the clarifications and it helps my understanding of the proposed method and contributions. I will think through the discussed points in detail and consider my review in light of the responses. Many Thanks

Please read and respond to rebuttal

Dear reviewers, Please read and respond to the rebuttal as soon as possible. Thanks

Response to rebuttal

Thanks for the rebuttal, most of my concerns have been addressed.

Response to author

Thank the author for clarifying my concerns. a. I still think that it's a bit weired if baselines in Table 2, 4 and 5 are different. Although this is a minor issue, I would recommend the author to make it equivalent for fair comparison and statement in the paper. b. For the source node, how is it specified in the dataset, by random? I would also suggest the author to clarify this in their paper.