Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper discusses how to introduce some form on non-local structural information into the node representations by collating cluster similarity information from a topological subspace clustering with a classical spatial graph convolution. Both information are mediated by attentional mechanisms which also take care of mixing the topological and convolutional contributions.

On the positive side, the proposed approach seems to work well empirically, although results are limited to 3 standard benchmarks on node classifications. The community is trying to surpass the use of those 3 datasets, due to both their simplistic nature (see ogb.stanford.edu for challenging node classification benchmarks) and pitfalls in their evaluation (https://arxiv.org/pdf/1811.05868.pdf). 

The paper also provides a theoretical proof of the representation power of the proposed JAT, following the consolidated approach started in the GIN paper. I am not particularly fond of these proofs as they are mostly technically correct but poorly original exercises showing that the proposed method is more or less 1-WL equivalent. In the paper, such proofs are leveraged to show a class of substructures on which the vanilla JAT model fails, providing a correction that solves the issue. Which would be fine, apart from the fact that the proposed work-around (i.e. considering neighbourhood size of each node) is standard practice in node classification tasks, where node degree is added as a node feature in input to the model (with excellent accuracy boosts). 

This brings me to the big issue in the paper: originality is minor. The work is heavily based on the GAT model extended, again by a fairly standard attention-based approach, with the topological clustering information. This latter aspect is allegedly the novel part of the work, but the paper does not analyse the implications of adding such topological information in full depth. The paper is very generic in referring to it as an enabler for considering higher order structural information, without providing any insight onto the nature of such added information. To me, the introduction of subspace clustering information is somehow pushing some spectral information into the spatial convolution-based approach by GAT. In this sense, I see the proposed JAT as an attempt to trade between spatial and spectral features. In the literature there are works providing evidence on how mixing the efficient, but local, approach of spatial convolutions with the global information from spectral methods typically yields to increased predictive accuracies (see papers.nips.cc/paper/9490-diffusion-improves-graph-learning.pdf). I would have liked to read in the paper a discussion placing the proposed approach in this recent interesting literature, e.g. leveraging diffusion information (as in the paper above or https://ecai2020.eu/papers/1339_paper.pdf) or very related subspace clustering methods (https://ieeexplore.ieee.org/document/9181470).  Instead, the discussion of GNN background (Section 1) and related methods (Section 2.) is quite shallow. This is a pity (and the second major issue in the paper) and it reduces considerably the impact of the work, especially considering the scope of the ICLR conference. 

There is a third issue which relates to some limitations of the approach which are more or less obfuscated in the paper. The work focuses on node classification tasks, ie. where data comprises a single network. Why is this? Is it because the method cannot handle a dataset of graphs of varying topology (e.g. as in graph classification)? Similarly, why (in Section 2.1) the model is restricted to work with only binary node features? Is this limitation purely notational or does it affect the model? The manuscript should be very clear in stating the limitations of the proposed approach, if any, and what bit of the model is possibly introducing such constraints.

In the empirical analysis, Figure 2.c should also report the confidence intervals, as I am not convinced that the difference “with and without ad” is statistically significant. 

The denominator in (5) can be simplified as it is a summation over two elements.   

=========== POST REBUTTAL

I have really appreciated the effort placed by the Authors in their rebuttal. Here follows some considerations following rebuttal:
* The empirical analysis has been strenghtened with the inclusion of the OGB benchmark as it provides a view of the empirical performance of JAT in the context of a challenging dataset within a standardised setup. At the same time, OGB allows direct comparison with leaderboards and results in literature that highlight how JAT performance are not (as claimed) state-of-the-art. In this sense, it is still quite unclear if there is any practical advantage with respect to GAT.
* The revised paper version places the work much better in the context of recent related literature.
* Also considering the point above, the novelty of the work is still borderline to me.

In summary, the work has good potential, but it is not yet ready, hence my decision to stay on the reject side. The contained originality can be made up in a future submission by providing convincing state-of-the-art performance results on challenging benchmarks, showing substantial differences from related models such as GAT. 
review_title: Introduce subspace clustering information into a graph-attention network to capture non-local information into the node embeddings

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose Graph Joint Attention Networks (JATs) as a mechanism for explicitly incorporating structural information in the GATs attention mechanism. 

JATs separately learn a "structural" attention matrix which:

(a) exploits structural correlations between vertices;
(b) forces diagonal entries to be zero to avoid trivial solutions (clever!);
(c) is regularised using the L_1 norm, to promote sparsity.

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.

Overall, I found the work's theoretical contribution to be impressive. However I cannot recommend acceptance in the current form based on the theory alone, and in particular, the following three major points should be addressed by the authors before the paper is ready:

- The authors only evaluate their work on the Cora/Citeseer/Pubmed citation networks, which are known to be oversaturated and unreliable as graph representation learning benchmarks (see e.g. "Pitfalls of Graph Neural Network Evaluation" from Shchur et al.) and should be avoided as centerpieces of evaluation. I would like to see experimental results on either OGB (Hu et al., NeurIPS'20) or Benchmarking-GNNs (Dwivedi et al.), which are two established datasets that have been around for long enough by now, and are easily accessible via existing graph learning libraries.
- The proposed structural learning work is one way of injecting structural information into the attentive mechanism, but is not the only one. Actually, taking either:
top/bottom-k eigenvectors of the Graph Laplacian, or
a structural embedding method such as DeepWalk/node2vec/struct2vec/LINE, 
as additional structural features to be concatenated with node features, could yield a similar effect of exploiting structural similarities without necessitating the need for two attentional mechanisms or additional learning objectives. Also it might be interesting to contrast the method proposed here with MoNet (already cited), which only performs attention on structural features -- maybe MoNet coefficients could serve as a possible replacement for the C matrix. Could the authors compare with some of the above, either theoretically or empirically?
- Lastly, and in relation to the previous point, I found the following claim by the authors:
"First, there are no appropriate attention mechanisms which can automatically identify the relative significance between the latent structure and node features while computing the attention scores."
to be very strong and unlikely to be correct, especially in light of the discussion mentioned above. Also the phrase "latent structure" is only used there and not properly defined elsewhere, so it is unclear what the authors are referring to.

I am willing to increase my score if the above were appropriately addressed. Besides this, there are a few other points that could also be quite useful to consider:

- The paper follows the theoretical assumptions of the GIN paper (countable feature-spaces), and it could be interesting to also look at uncountable feature-spaces (eg real numbered features) where many of the theoretical results don't hold. See Corso, Cavalleri et al. (NeurIPS'20) "Principal Neighbourhood Aggregation for Graph Nets" for an overview.
- I'm a bit concerned about the method's scalability. It seems that solving the optimisation task on C may easily invoke quadratic memory even if the underlying graph is sparse? Have the authors managed to reduce this constraint somehow, given that their method successfully ran on Pubmed? Further, some proposed approaches above (e.g. DeepWalk features or using MoNet attention to compute C) could be more scalable alternatives. Could the authors comment on this?
- Finally, isomorphism-style setups are concerned with distinguishing entire (sub)graphs, and hence might be more directly amenable to graph classification style tasks. The authors may wish to consider some classification tasks (maybe even synthetically constructed) in order to solidify the predictive power argument of their method.

==================== Post-rebuttal update:

I would like to thank the authors for providing a detailed reply, which partially addresses some of my concerns. However, there are several issues in the reply and updated manuscript as provided by the authors:

- The results on OGBN-arXiv are definitely useful, but there is no GAT-based baseline, which corresponds to the JAT's main comparison point. Therefore it is not possible to make strong claims about the method's effectiveness based on the following baseline choice alone.
- The discussion of alternate structural learning approaches is not sufficiently detailed, and has no empirical backing to the authors' proposal. More experimentation is needed, in my opinion, to fully back the authors' claim of: "However, these methods may not appropriately determine which part, i.e., structure or node features is more important in the embedding space."
- Lastly, I do not find that the authors have appropriately toned down their claims in the Introduction. Most critically, the authors write: "The experimental results show that JATs achieve the state-of-the-art performance". A lookup of the OGBN-arXiv publicly available leaderboard demonstrates that this is not the case: https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-arxiv

Having state-of-the-art is not the most important thing, but it should not be claimed when it's not achieved.

Overall I think the JAT paper has a lot of potential. For now I choose to retain my 'weak reject' recommendation, and hope the authors will take my comments into account for subsequent submissions.
review_title: Improved expressivity on structural GATs, lacking experimental protocol

final_score: rating: 7: Good paper, accept
review_content: Overall Comments:
Creating aggregation weight over neighbor nodes lies at the key part of graph neural networks. Generally the weights can be generated by the node structure or feature similarity. The node structure similarity provides a way to measure the correlation of a pair of nodes with a complete graph. While attention weight usually focuses on the local neighborhood, which can be easily biased by the node popularity [1, 2]. If a neighbor node with large degree, it potentially tends to have a large embedding norm. However, from complete view of graph structure, this neighbor might be a noisy node. With a given complete graph structure, we can downgrade the influence of structure bias. From this point of view, it's interesting to study whether the attention and structure weights can be complementary to each other. The key idea of this work is very easy to follow. The proposed strategy is to unify the weights generated by graph structure and node feature. Theoretical analysis shows the expressive power of  the proposed strategy. The experimental results for node classification also demonstrates its superiority comparing with state-of-the-art baselines.

Presentation:
The presentation of this work is very clear and organized very well.

Questions:
1. The coefficient matrix C is learned by recovering the adjacent matrix A. To some extent, it tells the correlation between a pair of nodes. Can we replace it with another correlation matrix, such as Jaccard similarity matrix where each element stands for the node similarity measured by Jaccard equation or Personalized PageRank diffusion matrix? That'd be interesting to see the influence coming from the coefficient matrix obtained by different methods.

2. In Section 2.1, what is the role of the multiset M_i? It's a little difficult to understand without any background introduction in this subsection. Maybe more justification about the notations are needed to show its connection to next section.

References:

[1] Gong, Chengyue, Di He, Xu Tan, Tao Qin, Liwei Wang, and Tie-Yan Liu. Frage: Frequency-agnostic word representation. In Advances in neural information processing systems, pp. 1334-1345. 2018.

[2] Armandpour, Mohammadreza, Patrick Ding, Jianhua Huang, and Xia Hu. "Robust negative sampling for network embedding." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 3191-3198. 2019.
review_title: An interesting and good paper

final_score: rating: 5: Marginally below acceptance threshold
review_content: ---- Summary

This paper proposes Graph Joint Attention Networks (JAT), which augment Graph Attention Networks (GAT) by introducing structural attention coefficients, which are combined with the feature based attention coefficients computed by GAT. The authors present two ways of incorporating the structural coefficients, namely Implicit direction and Explicit direction. The authors evaluate their proposed technique in the Cora, Citeseer and Pubmed datasets, where they improve the performance of other GNN approaches.

---- Pros
* The paper presents an interesting approach to introduce structural information when computing the attention coefficients in an attention-based GNN.
* Good analysis of the expressive power of JAT
* The method presented in the paper achieves state of the art results in the datasets it is evaluated with.

--- Cons
* The empirical evaluation is a bit limited, since it evaluates only with Cora, Citesser and Pubmed which have been shown to be not entirely appropriate to evaluate GNNs, in favour of better benchmarks like the ones proposed in [1] and [2].
* It isn’t very clear exactly how the minimization of Equation 2 is done. Is it solved once for each graph or is it solved at every training iteration? The authors say that “JATs can optimize Eq. (2) together with the training of the neural architecture.” so it isn’t clear how it is done. If A is always the same for each dataset (Cora, Citeseer and Pubmed are one single graph each) why not minimize it just once before training? 
* The authors don’t mention the complexity of their approach. If JAT were to be applied to a different graph structure all the time, so A is different for each sample in a dataset consisting of multiple graphs, what would be the complexity of the method considering it has to minimize Equation 2 to obtain the matrix of coefficients C?
* The experimental section lacks some ablation studies. For example, what if only the structural attention coefficients are used? What happens if noise is included in the adjacency matrix? What if structural coefficients are all constant? Then the model should be empirically equivalent to GAT.

---- Questions
* For very different values of $\beta$ (ranging from 0.01 to 100), JAT seems to achieve very similar performance, a behaviour consistent across datasets. Any idea why that is the case?
* The implicit direction mechanism is a bit unclear in the paper. What are $r_s$ and $r_f$ in Eq 6? They have not been introduced before and it isn’t clear where do the indexes $f$ and $s$ come from. I think Eq 5 would be a bit clearer if written like $$ r_i = \frac{exp(g_i)} {\sum_{k \in \\{s,f\\}} exp(g_k)}, i \in \\{s, f\\} $$ Although it is still a bit confusing, using $i$ as an index when it has been previously used to denote node indexes is confusing. 
* $g_s$ and $g_f$ are global parameters, meaning that each node structural and feature coefficients are weighted in the same way. Why not learn these parameters for each node, so that some nodes can rely more on features and other nodes can rely more on structure?
* Could JAT work in the inductive case where the training and testing structures are different?

---- Minor Comments

The font-size in the plots in Figure 2 should be increased, it would be very difficult to read if the paper was printed. 

---- Reason for score

The paper proposes an interesting technique to use the graph structure as well as the nodes features to compute attention coefficients, however the experiments are a bit limited, using only three small datasets and limited ablation studies. Additionally, some of the details of the paper are not clear. For these reasons, I consider the paper to be marginally below the acceptance threshold.

------------ Post rebuttal update

I appreciate the rebuttal made by the authors, as they have clarified my questions about the paper. It is also good that a new dataset and additional ablation experiments have been added to the paper, however, the empirical section still needs to be improved in my opinion. 
For example, more datasets and stronger baselines could be used, and I believe the authors could do it if they had more time. Therefore, even though I mantain my score, I encourage the authors to strengthen the empirical evaluation for future submissions.

---- References

[1] Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., & Bresson, X. (2020). Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982.

[2] Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., ... & Leskovec, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687.

review_title: Interesting idea, limited experiments

Meta-review: One referee recommends acceptance, while three referees recommend rejection. All referees agree that augmenting GAT with structural information is an interesting direction to explore; however, they raised concerns about the empirical validation of the method, the related work covered, as well as the discussion of insights such as the method's limitations. The rebuttal addresses R2's concerns by better positioning the work w.r.t the literature and by discussing the method's potential limitations. The rebuttal also covers R1 and R3's comments on scalability and complexity of the proposed approach. However, the rebuttal only partially addresses the evaluation concerns of the reviewers. After discussion, all reviewers agree that further work should be devoted to remedy this. I agree with their assessment and hence must reject. In particular, I would strongly recommend following the referees' suggestions and consider incorporating experiments on additional OGB datasets, including a GAT-based comparison to those (and on OGB-arxiv), and eventually toning down their claims.
Decision: Reject