Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: ---- Problem setting and contribution summary ----
The paper considers the problem of graph node classification in a semi-supervised learning setting. When classifying a node, the decision is based on the node’s features, as well as by a weighted combination of its neighbors (where the weights are computed using a learnt attention mechanism). The authors extend upon the recent Graph Attention Networks (GAT) paper by proposing a different way of computing the attention over the neighboring nodes. This new attention mechanism takes into account not just their feature similarity, but also extra structure information, which also enables their method to attend not only over direct neighbors, but also up to k-hop neighbors.

---- Overall opinion ----
While I believe the general idea indeed has merit and empirically shows great promise, I believe the paper in its current state is not ready for publication. However, I believe that a more thorough revision can lead to an a publication with potential impact on the applications side.

---- Pros ----
1. The paper is easy to read.
2. I really appreciated the good visualizations (Figures 2,3,4) that indeed help in understanding the method.
3. Really good empirical results on the 3 datasets that were presented.

---- Major issues ----
1. Motivation:  
I believe the paper is not well motivated from an applications perspective. In section 2.1., the authors did a good job explaining the limitations of current approaches on a generic graph structure, but this is only under the main assumption that a node should attend more to neighbors in its denser community than other neighbors that not connected so strongly (Fig 1). The issue that I have with this is that:
      a) Why should we take this assumption for granted? What are some concrete practical node classification problems where it is indeed better if a node attends to its neighbors in this way (as opposed to the GAT approach)?
      b) Even if the above is proven true, suppose node A in Fig. 1(a) attends with equal weights to all its 4 neighbors. That means node C (which is outside its densest community) gets 1/4, while the nodes inside the dense community get a total of ¾. That means node A puts most of its attention to the dense community anyway. In what conditions is it necessary to bias this attention even further?

2. Experiments: 
While the reported accuracies for the three datasets look good and also the authors have provided a link to their code (great to see that!), I believe the experimental section is missing an important amount of details for reproducibility purposes and also for explaining how certain parameters have been chosen:
    a) There are no details on the model size and training procedure (hidden units, optimizer, learning rate schedule). 
    b) Maybe I am missing this, but I don’t see any reference on what alpha and beta from equation (6) were used in the experiments. 
    c) What is the value of k in Table 2? How did you choose it? I believe Figure 5 shows test accuracies for different k, but I hope the authors did not choose k based on the test set performance. 
    d) How did you select the structural fingerprint to be 3?
     e) “...optimizing c through the learning process also gives very similar choice” → how did you optimize c exactly?
     f) Fig 5 a) Why does increasing the number of hops to 3 or 4 decrease the performance so much? Shouldn’t the attention weights learn to ignore the further neighbors, if they are not useful?  

	Another important question regarding experiments: since the ablation study shows that the optimal neighbor range is actually 2, a natural baseline to compare with would be something similar to GAT, where an attention weight is applied to all neighbors within two hops (basically skip the fingerprint step, and assume s_{ij} is 1 for all neighbors within 2 hops, and 0 otherwise).

	Also regarding experiments, these 3 datasets, although common across many recent graph node classification papers, they are known to be quite limited (small in size and not very representative of real world). Since GAT is your main competitor, why not also show experiments on the PPI dataset they also test?

3. Writing quality: 
While the language is clear and easy to follow, there are many grammatical mistakes throughout the paper (e.g. “benefitial”, subject-verb agreement).

---- More minor issues ----
    a) Section 2.1: One could argue that GAT also contains longer range node dependencies through the node embeddings it learns. Since the node embeddings is trained through gradient descent, and at each iteration the embedding of a node changes according to its neighbors, you could say that information does get propagated from the neighbor’s neighbors.
     b) Why do you need a LeakyRelu in Equation (5) ? Also, aren’t e_{ij} non-negative anyway (in which case LeakyRelu doesn’t change anything)?
     c) Why would a Sigmoid be a good choice for alpha and beta in Eq. (6)?
     d) Section 3: A bag of words is typically represented as a binary vector, which is also categorical.
     e) Please use \citet when specifically referring to the authors of a paper as part of your sentence (e.g. “Following Velickovic et. al., 2017 we….” as opposed to “Following (Velickovic et al., 2017), we....”).

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper extends the idea of self-attention in graph NNs, which is typically based on feature similarity between nodes, to include also structural similarity. This is done by computing for each node a value for each other node within its receptive field, calculated based on some distance metric from the node (either a Gaussian decay profile, or a learned weighting of number of hops distance, of based on fixed point of a random walk with restart). When evaluating the attention between two nodes, a function that compares the structural values between the two nodes (based on Jacard similarity) gives a score to the two nodes, which is further used for calculating the attention weight between them.

I found the idea to be elegant and well-explained, and overall the paper is well-written. 
Using the structural similarity makes a lot of sense, and the proposed method is both easy to implement, and flexible — the structural similarity profile can be learned, which seems important for getting this idea to work in practice.

I wonder what happens if one uses only the structural similarity for the attention (without the feature similarity). Are there datasets where this would be sufficient? Even a toy task which is constructed such that the structure is more informative than the features could be a nice way to further demonstrate the idea of the paper.

The experiments show a clear yet small advantage to the proposed method over the conventional attention method (GAT).

Overall, this seems to be a solid contribution (even if the empirical results are a bit incremental) and I recommend acceptance.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This work suggests a graph structure based methodology to augment the attention mechanism of graph neural networks.

The main idea is to explore the interaction  between different types of nodes of the local neighborhood of a root node. One component of this "fingerprinting" is a node weighting (closeness) that is computed using various methods proposed in the paper. The fingerprint is the vector of weights of all nodes in the local neighborhood. 

For computing a closeness metric, the paper suggests random walks with restart, which has generally been used for graph clustering. Once the relative closeness to a node in the neighborhood is measured, the symmetric "structural interaction" between the fingerprint of two nodes is given by the Jaccard similarity of their structural fingerprints (or a smooth alternative thereof).  This structural similarity will be then considered in a (multi-head) attention mechanism using learned transfer functions.

The efficacy of the proposed method is tested on the Cora, Citeseer and Pubmed node classification benchmarks and compares favorably to non-augmented graph neural networks, beating all baselines on those datasets. Also the results in the paper beat those of the GResNet on Cora, but not on PubMed and , which is a recent paper not cited by this work.

In general this work goes into the direction of adding hand-engineered features to DeepLearning approaches. I am not a big fan of these methods, especially without significant theoratical justification. The approach is well motivated but very heuristical. Still the results presents a significant improvement of SOTA on those benchmark and the paper presents ideas  that seem to be generally useful for processing large-scale, structure-rich graph date. Hence I am in the favor of acceptance of this paper.
review_title: Official Blind Review #4

Meta-review: This paper is consistently supported by all three reviewers during initial review and discussions. Thus an accept is recommended.
Decision: Accept (Poster)