Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a transformer-like model that carries vectors on graph edges instead of the nodes, and updates the vectors through a new (triangular) formulation of self-attention. The Edge Transformer demonstrates better generalization than baselines on two relational tasks.
main_review: - Originality

Section 5 provides a useful summary of prior work involving edge vectors in transformers and GNNs. The proposed form of triangular attention appears to be both novel and well-motivated.


- Quality

The Edge Transformer (ET) is evaluated against two baseline models, Relation-aware Transformer (RT) and a basic Transformer, on two supervised tasks (CLUTRR and CFQ) as summarized in Table 1. The results in Figure 3 and Table 2 indicate that ET outperforms the baselines on these tasks. 

Section 4.1 adequately describes the CLUTRR (relational reasoning) task, and the process of applying ET to it, by embedding the edge labels to obtain the initial edge vectors, and retrieving the predicted class from the query edge output vector. But the corresponding details are missing for the RT baseline model. RT carries vectors on both nodes and edges, but updates only the node vectors. Line 162 notes that RT “can be conditioned on an arbitrary graph”, so perhaps its edge vectors are initialized in the same way as those of ET, and presumably RT’s node vectors are initialized to zero. But then what happens? Since RT never updates its edge vectors, and the query edge vector is initialized to some non-informative value, retrieving the predicted class from the unchanged query edge vector could only produce a fixed output. But Figure 3 clearly shows that RT performs better than chance. It appears that RT was somehow adapted to this task, but the paper does not explain how. Without understanding how the baseline model was actually used, we cannot evaluate the significance of the difference in performance between ET and RT on the CLUTRR task. In addition, since RT was not designed to update its edge vectors, a more appropriate baseline model for this task would probably be some GNN that was designed to carry edge vectors and update them in each round of message passing.

Section 4.2 describes the CFQ (dependency parsing) task, where the input is a sequence of word tokens, and the output is a label for each token pair. As with the CLUTRR task, no detailed description is provided for how the pairwise output labels are obtained from the baseline transformer, which carries no edge vectors. The results in Table 2 indicate that ET’s edge-based triangular attention delivers improved performance over standard transformer self-attention in this task.

The paper’s contribution would be strengthened by positive results on a third task. In particular, it seems important to know how well ET performs as a simple language model. It should be relatively straightforward to train ET on Wikitext and generate a training curve showing perplexity improvement over epochs. Alternatively, ET could be evaluated against GNNs on a task that requires reasoning over edge features.


- Clarity

As noted above, the paper is missing essential details about how the baseline models were applied to the tasks. Apart from this shortcoming, the paper is quite clear and well-written. Section 3 in particular is excellent. In section 4.3, the term ‘ablation’ would be more readily understood than ‘lesion’. 


- Significance

Given the successes of transformers in NLP and beyond, any fundamental improvement to the transformer architecture can lead to major benefits. 


- Conclusion

I view this as a potentially important work that currently lacks sufficient experimental support. I do not believe that novel advances such as triangular attention should be required to achieve SOTA results on major problems prior to publication, but I do believe that carefully described baselines are essential to any meaningful evaluation.
 
- POST-DISCUSSION UPDATE

To their credit, the authors have remained deeply engaged throughout the review process, and have greatly improved the work. I still have reservations about the CLUTRR task baseline, but this seems less important than the positive results on the newly added semantic parsing task.

If the original experimental section had not left out so many key details, I would have more confidence that the next, significantly revised version of the experimental section would cover all that is required. But I’m raising my rating by 2 points, and petitioning the authors to seek feedback from someone unfamiliar with the work to help bring the experimental section up to the same standard as Section 3. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose Edge Transformers to solve  CLUTRR relational reasoning challenge and Compositional Freebase Questions benchmark. The edge transformer is based on triangular attention which is weighted sum of the representations of all the triangular nodes. The proposed method can achieve better performance than the baselines of Transformer, LSTM, and GAT.
main_review: Overall, the proposed method is interesting. I didn't know other works focusing on weighted sum of the representations in triangular. However, this method is very close to combining GNN and Transformer. How about first use GAT to encode the graph and then run another transformer layer on all the nodes? I would like to see the performance of this baseline. I feel the authors overplay the model structure but ignore the simplest way to combine GAN and Transformer.

Other comments:
1. For dependency parsing tasks, it would be better to test the method on more benchmark datasets. Or reimplement some benchmark baselines with graph neural networks. Vanilla LSTM and Transformer are too weak baselines.
2. The intuitions section doesn't seem novel enough. The motivation is close to graph neural networks, which can also merge the information of the nodes with relation.s
limitations_and_societal_impact: A little bit overclaim the novelty of edge-transformer, but overlook related works on graph neural networks.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a variation of the Transformer architecture where attention happens between edges as opposed to nodes. As such, the input and output to the Edge Transformer are 3D $d \times n \times n$ tensors instead of 2D $d \times n$ tensors. This new architecture, together with its novel “triangular attention” mechanism, are introduced with the objective of favoring generalization in compositional reasoning. Two sets of experiments validate the architecture’s benefits over previous architectures.
main_review: The architecture and the proposed triangular attention appear to be a relatively natural variation of Transformers, but they are novel. They are well motivated by the problem of improving compositional generalization. The paper is very clear and has all the details needed to replicate the architecture. Overall, it is a welcome addition to the literature.

Some details are lacking in the experiments section, especially with respect to the dependency parsing task (the main reference  being an unspecified paper): Is the task semantic parsing or some variation of it? What are examples of input and output? Why is this task supposed to measure compositional generalization? Expanding on these points would help.

In general, the set of experiments is fairly limited and does not appear to provide enough evidence that the Edge Transformer could be more suitable than the ordinary Transformer for solving more complex tasks (especially due to the significant computational increase). The computational disadvantage of the Edge Transformer is acknowledged in Section 6, where the authors also provide ideas on how this issue could be addressed in tasks like language modeling. Additional experiments would be very welcome, but they do not necessarily fall within the scope of this paper.

limitations_and_societal_impact: Limitations have been addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Paper presents edge transformer, a novel transformer architecture that takes edge information, i.e. binary relation among tokens/entities as input. To further reduce the computational overhead, the authors observed that there is no need to attend on unrelated edges and therefore introduce triangular attention to replace vanilla attention. Experiments on two datasets (CLUTRR and CFQ) demonstrates the effectiveness of the proposed method.
main_review: [Strengths]

[+] The paper is overall clear and well-written. The research problem here falls in the interest of the NeurIPS community and may have the potential impact on larger groups than NLP.

[+] The proposed improvement on transformers is well-motivated. I like the example in canonical deductive reasoning and I agree with this intuition. The method is technically sound and I cannot find any issues.

[+] The experiments can be limited but the superior results over other baselines are impressive. 

[Weaknesses]

Having said those above, I do have some concerns given its current presentations and I feel this paper can be somehow premature for publishing:

[-] It is still unclear which part of this method contributes the most to the performances. The authors are suggested to conduct a comprehensive ablation study on their model. At least there are two factors to test on:

1. (major) vanilla transformer with relational input embedding (10)
2. (minor) triangular attention vs. vanilla self-attention

I'm particularly interested in the results of 1. Please try to include them in the rebuttal.

[-] I'm not that familiar with NLP datasets&benchmarks that focus on systematic generalization. But it seems that the two datasets in this paper do not even have a compositional generalization split and therefore the results could be less convincing given the authors' claim on improving compositionally. I will recommend including some results on the following datasets:

**SCAN** https://arxiv.org/abs/1711.00350

**COGS** https://arxiv.org/abs/2010.05465

**SyGNS** https://arxiv.org/abs/2106.01077

[-] There are more and more papers today that try to explain how transformers tackle the difficult downstream tasks by visualizing the attention matrix (ex. https://arxiv.org/abs/2104.14294). Given the illustration in sec. 2, I find it could be necessary to visualize the resulting attention over all the edges. The authors could try to answer this question in their inspection: Do the proposed transformers attend to the expected edges among input tokens? 

[Suggestions]

I'll be willing to increase my score if the following points can be addressed in a rebuttal:

- ablation study on input embedding and the proposed attention mechanism.
- results of at least one aforementioned dataset.
- visualization on the attention matrix and some explanations.
limitations_and_societal_impact: The authors addressed the limitations properly.
review_title: null

Meta-review: This paper proposes 'Edge Transformer' which is a Transformer architecture that assigns an embedding to the edge between two tokens. A 'triangular attention' is used to update the edge embeddings, which basically computes, for edge a-b, a weighted combination of the product of edge embeddings a-n * n-b for each intermediary node n (N^3). The authors test this method on systematic generalization datasets such as CLUTTR (link prediction) and on a subtask derived from CFQ (dependency label prediction).

--

The paper was generally found clear, although some concerns about the experimental setup need to be addressed in the revision. A reviewer found improvements over baselines for systematic generalization to be "impressive". There has been an extensive back-and-forth between reviewers and authors on the validity of the baselines for the task considered. I thank both reviewers and authors for their fruitful exchange. The authors provided new positive results for the baselines suggested by reviewers. Initial concerns rotated around the synthetic nature of the task considered: the authors improved on this point by providing new results on the full semantic parsing task of CFQ by testing on each MCD split: the Edge Transformers outperforms carefully tuned previous (non pre-trained) transformers for this task. These results must still be taken with a grain of salt, given that pre-trained models achieve better results. However, these results strengthen the paper considerably. One suggestion I can think of in this respect is whether the authors could try to start from a pre-trained T5 model, add parameters for their edge attention, and fine-tune everything on the downstream CFQ task. This could maybe give a better idea on whether this model holds promise in the general setting, e.g. gains can be obtained without retraining the all model from scratch. If the potential impact of novel attention mechanism can extend to a large set of tasks, still major concerns rotate around the computational complexity of this approach (N^3) which makes it hardly applicable in general.

Overall, the reader might be left to wonder whether this method is applicable or is beneficial when it comes to large-scale pre-training of Transformer architectures. Nevertheless, provided that the authors integrate all the precious reviewers' feedback and the new experimental results in the final version of the paper, reviewers and myself agree that this paper can make an interesting addition to the conference.
Decision: Accept (Poster)