Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper aims to establish a new type of attention mechanism for GNNs. Authors propose an attention mechanism which can utilize structural interactions between nodes instead of focusing only on given node features. Given the new attention authors use it create Conjoint Graph Attention Networks to solve node classification and node clustering tasks. 

Authors first calculate an external ( w.r.t GNNs ) information matrix and propose two forms in this paper based on Matrix Factorization and Coefficient of Self-Expresiveness. The *Conjoint Attention* layer then calculates two types of attention, using external information matrix and using the node features ( any attention mechanism can be used here, authors use attention mechanism similar to GAT ). Two strategies are used to combine the different attentions calculated in previous step, Implicit and Explicit. Weighted aggregation is used to get the final node embeddings, with an addition of a correction factor. 

Experimentation is conducted of several publicly available datasets, and comparisons to several baselines are included which gives a good idea of the expressive power of the proposed attention mechanism. 
main_review: - Authors propose to use the structural graph properties in addition to node features, to calculate separate attention scores. The motivation behind this type of attention is well established. 
- Thorough experimental analysis is done to establish the advantage of using the proposed attention mechanism. 
- The writing of the paper is okay but can be improved by giving examples at several places. For instance, authors talk about " heterogeneous learnable factors either inside or outside GNNs " starting from Abstract of the paper but it is only introduced in the method section. Please provide simple examples in order to make the method more approachable. 

limitations_and_societal_impact: Questions and Comments
- In Section 3.2, please define the matrix V and how is it defined. 
- It is stated in the paper that external information matrix C can be calculated based on any interaction between nodes which is useful in node classification tasks which have some textual data available for each nodes. In such cases, I would assume that using conjoint attention principle to calculate an attention score between texts of two nodes will be useful in the final task. Would you consider including such an experiment in the paper?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose Graph ConJoint Attention Networks (CATs) as a mechanism for explicitly incorporating structural information in the GATs attention mechanism.

CATs separately learn an "enlightenment" attention matrix which exploits structural correlations between the vertices (based on the adjacency matrix).

Such a matrix is then recombined with the attention matrix computed by vanilla GATs, yielding updated attentional coefficients which empirically improve on GATs on several benchmark datasets, and can be proven (with small modifications) to satisfy the equivalence with the 1-WL test, which also answers a somewhat-open question on GATs' expressive power.
main_review: Overall, I found the work's theoretical contribution to be impressive, and the comparisons to baseline approaches to be relevant.

I believe that the work is worthy of acceptance, but I would like to see a few more experiments, comparisons and clarity improvements before giving a higher score.

Specifically, the proposed structural attention is one way of injecting structural information into the attentive mechanism, but is not the only one. Many prior works, that e.g. take the top/bottom-k eigenvectors of the Graph Laplacian, or a structural embedding vector such as DeepWalk/node2vec/struct2vec/LINE, could be meaningful baselines. This is especially given that recently a deep connection between such works and matrix factorisation has been uncovered (see NetMF; Qiu et al., 2017).

Could the authors compute these additional features, and include a GAT baseline that takes them in concatenated alongside the usual node features? This will strengthen the claim about the impact of the proposed CAT mechanism.

I found the paper at times very unclear and difficult to follow. The second sentence in the abstract for example:

"Different from previous graph attentions computing weights for feature aggregation solely bestowing layer-wise node features propagated inside GNN, CAs are capable of adaptively leveraging heterogeneous learnable factors either inside or outside of GNNs to compute attention scores."

It is very unclear what the authors want to say in this sentence, and in either case it would be better splitting it into multiple.

Lastly, I disagree with using the term "enlightenment" to refer to graph-structural features. They are very commonly used in many other established papers (e.g. see the ones I referred to above) and there is no need to overload a new term to illustrate the same (or very similar) concept.

I invite the authors to carefully rewrite some parts of the paper in light of the comment above, to make it easier to follow.

==== UPDATE Post-rebuttal: 
The authors have carefully responded to my comments and included new experiments that further elucidate the gains of their method. With faith that they will rewrite their paper to be more clear, and avoid overloading existing terms, I will upgrade my score to a 6.
limitations_and_societal_impact: No concerns here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents an extension of Graph Attention Networks (GAT) termed Conjoint Attention Networks (CAT). The attention mechanism presented in this paper combines the attention mechanism from GAT, computed from the node embeddings, with an extra attention mechanism that captures structural information too.
main_review: Strengths
+ The authors perform an experimental evaluation on a variety of graph datasets for two different tasks.
+ The authors do a theoretical analysis of their proposed method.

Weaknesses
- The main weakness of the paper is that it is not clear what is the motivation for CATs, and why the different methods for computing $\mathbf{C}_{ij}$ are chosen:

  - First of all, the authors mention that their attention mechanism can leverage “factors either inside or outside of GNNs” (Abstract, line 5). It isn’t clear what that means. What are factors inside the GNN? I assume deep node embeddings? What are the factors outside the GNN?

  - In the introduction (line 36), the authors mention that “previous graph attention mechanisms are incapable of learning effective attention scores when heterogeneous relevance is given”. What is “heterogeneous relevance”? It isn’t explained in the paper. Why are other attention mechanisms unable to learn effective attention scores? Why are CATs better in this aspect?

  - Again, in the introduction (line 41) the authors say that CATs are flexible to compute attention scores not only relying on the layer node features, but also leveraging “information possibly outside of the neural networks”. What is that information?

  - Section 3 should explain clearly what are CATs and their motivation. While the formulation of CATs is well explained, the choice of the conjoint attention scores $\mathbf{C}_{ij}$ and its motivation is unclear. In section 3.1 the authors explain that conjoint attentions can capture “enlightenment outside of GNNs”. Again, it isn’t clear what that means. The authors use the word “enlightenment” to refer to the information that the proposed attention mechanism can use, but it isn’t clear what that means.

  - In Equations (2) and (3) it seems that $C_{ij}$ is capturing structural information from the adjacency matrix of the graph, but that isn’t explained.

  - In the experiments the authors evaluate the MF and SC variants of their method, introduced in Equations (2) and (3), but they don’t explain much about their motivation. What is the difference between them? They seem to get similar experimental results, why?


Additional Questions:
* In Section 5.4 the authors say that the “external enlightenment C” is learnable, and that it can be simultaneously learned during the training of CATs. But why is it learnable? Does it have any learning parameters? Why can’t it be computed before training?
* In Figure 3, it appears that the value of $\lambda$ doesn’t have an effect, why is that the case? It isn’t explained. What should be the behaviour of $\mathbf{C}_{ij}$ as $\lambda$ increases (or decreases)?
* What are the different attention factors compared in Figure 2? What is the difference between SC and I-SC?

To summarize, the method seems to perform well, and the authors do a good evaluation in different datasets, but it is not clear why this method should work better than GATs. The authors keep mentioning "enlightenment", a concept that is not explained. The clarity of the paper and the quality of the explanations should improve in order to be accepted.


### Post Rebuttal:
The authors have answered my questions and have agreed to improve the clarity of the paper, which was my main concern. Because of that, I raise my score to a 7, assuming that the authors will improve the clarity of the paper in its final version.

limitations_and_societal_impact: This paper doesn’t seem to have any obvious societal impact. The authors address the limitations of their method in the Appendix.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new technique for augmenting Graph Attentions with information other than node feature embedding in GNNs. The Conjoint Attentions (CAs) proposed in this paper parametrize the similarity hints between nodes, such as adjacency matrix, in the form of matrix factorization, and modify the attention weight \alpha calculated by ordinary graph attention.
This paper shows that CAs (with additional learnable parameters to the self-link terms) have theoretically higher expressive power than existing GNNs such as GAT.
Experimental results show that the proposed CAs have higher generalization performance than several existing GNNs on five representative datasets.

main_review: ## Originality: 
Traditional graph Attentions are solely controlled by the similarity of node feature embedding. As far as I know, this paper is the first attempt to identify this problem: a unique and valuable problem proposal. 
Also, the idea of adding a new control term to the existing attention in the form of Eqs.(7-9) is new, at least in my knowledge of GNN research. I find it interesting 

However, it is a pity that only the adjacency matrix is studied as enlightenment. ``A'' could be said to be information inside the graph data, depending on how a reader looks at it. I think the paper would be strengthened more if there were examples of information that is clearly outside the graph data.

## Quality: 
I could not find any technically obvious mistakes in this paper. However, I need to confess I cannot follow the proofs of theorems. 

Many related studies often include Graph Isomorphism Network (GIN[33]) as one of the most expressive GNNs for comparison. In my experience, GIN does not necessarily have the numerically highest generalization performance, but additional comparisons are definitely desirable to support the high expressive power shown in Section 4. 
Notice: I believe that the value of this paper would not change significantly even if CATs do not perform better than GIN. 

## Clarity: 
I could not understand the main ideas of this paper on the first reading. 
One reason is that (i)  concrete examples of ``other possible enlightenment'' (first appear in introduction L32) and (ii) explanation of how they help attention are not explained even roughly until section 3 (L115, 147). 
Ideally, I would like the introduction to be augmented so that the readers can have some intuitions about the outline of the proposed method at the introduction stage (I don't mean that it should be shown in equations explicitly). It is difficult for me to understand the intention of the equations at the first sight unless some intuitions are provided beforehand. 

In Figure 3, I'm happy to see that the result is robust to hyperparameter \lambda choices. 
But I think this figure can be moved to an appendix. As a reader, I can read as much information in the text of L308-312 alone as in figure 3. I would like to see additional experiments and/or discussion to limitation, future works in the main manuscript instead. 

## Significance: 
The experimental results show high test generalization performance of the proposed CAs, as expected from the theoretical conclusions, and I think these results support the claims of the paper well. 
As mentioned in the Originality section, I think the paper would be more significant if there are additional examples that incorporate information from outside the graph. However, I think it is an important finding that just using the adjacency matrix to control attention in this way can improve GNN performance.

Section 4 proves that the expressive power is stronger than GAT, etc... This increases the significance of the paper.

The formulation of the proposed CA is simple enough to be fully understood when looking at Eqs. (5-9), which I think adds to the value of this paper.

## after feedbacks
I found the author feedback informative, yielding better understanding. I keep the original positive score. 
limitations_and_societal_impact: I felt that there was not much discussion about the limitation of the proposed method (though some are discussed in the appendix). Personally, I'm interested in the following questions: 
- Is there any other typical and useful outside enlightenment other than the adjacency matrix?
- If there are multiple enlightenments, how should we weigh them? Which one should be selected?
- If the enlightenment is adversarial (e.g., false or noisy), how can we detect or mitigate the performance degradation?
review_title: null

Meta-review: There is general consensus among the reviewers that the paper should be accepted.

The authors made extensive effort to answer reviewer comments and provide additional empirical results.

We expect the authors to implements all clarity improvements, as requested by the reviewers.

Figure 1 looks pixelized, it should be converted to vector graphics.
Decision: Accept (Poster)