Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper proposes a new GNN model to address the common issue “oversmoothing”, namely, Graph Entities with Step Mixture via random walk (GESM). Basically, it integrates both mixture of various steps through random walk, and graph attention network, and demonstrates that it can overcome the SOTA on popular benchmarks.

Detailed comments: 

* The oversmoothing problem has been mentioned many times in this paper, yet little has been demonstrated through experiments that the new model can solve the oversmoothing issue. It would be great to show the performance improvement while oversmoothing is mitigated.

* The proposed idea is very similar to the following paper: “Revisiting Graph Neural Networks: All We Have is Low-Pass Filters”. Both use low-pass filtering (via transition matrix) to propagate the information on the graph. I suggest a detailed discussion with this work.

* The major concern of this work is the weak novelty. It combines GAT with multiple random walk under the GNN framework. While this is working well on most GNN datasets, it is not very new by itself.

* Some experimental results are comparable to existing methods, as shown in Table 2 and 3. Maybe the time complexity is the major contribution of this paper. A head-to-head running time comparison with SOTA in Table 4 will be helpful.

* Fewer methods are compared in Table 3 than in Table 2. Can authors add more in Table 3 to give a better demonstration?

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper presents two models, namely GSM and GESM, to tackle the problem of transductive and inductive node classification. GSM is operating on asymmetric transition matrices and works by stacking propagation layers of different locality, where the final prediction is based on all propagation steps (JK concatenation style). GESM builds upon GSM and introduces a multi-headed attention layer applied on the initial feature matrix to guide the propagation layers. The models are evaluated on four common benchmark datasets and achieve state-of-the-art performance, especially when the training label rate is reduced.

Overall, the paper is well-written and its presentation is mostly clear and comprehensible (see below). The quantitative evaluation looks good to me, especially since an ablation study shows the contributions of all of the proposed features.

However, there are a few weak points which should explain my overall score:

1. The proposed GSM model is not new and only re-uses building blocks from the related work. [1] shows that removing non-linearities is an effective procedure for node classification. [2] investigates the massively stacking of propagations. The procedure of feature concatenation from different locality has been studied in [3]. Applying asymmetric normalization is a standard aggregation scheme for GNNs, e.g., in [4].

2. The GESM model is not fully understandable since it is missing a formal description for computing $\alpha$. It is only said that $\alpha$ is computed using the concatenation of features from the central node and its neighbors. Can you elaborate how exactly you compute $\alpha$, especially since the concatenation of neighboring features results in a non-permutation invariant architecture? In addition, in contrast to the reported results in Tables 3 and 4, Figure 4 indicates that the benefits of GESM are negligible.

3. The final prediction layer with weight matrix W_1 operates on all propagation layers, resulting in a parameter complexity of $O(s  h c)$, where $c$ is the number of classes. With $s=30$ and $h=512$, this results in 15.360  c parameters (!!!), whereas GCN [5] only uses 16  c parameters. Hence, I do not think it is fair to promote your model as efficient as vanilla GCN. In addition, the final matrix multiplication results in a computational complexity of $O(n  s^2  h^2  c)$ which does not nearly match your reported complexity.
Furthermore, I do wonder why your model is not heavily overfitting with such an amount of parameters. For example, this is the reason [3] does evaluate its model on a larger training split instead of a smaller one.

4. As your work is quite similar to [1, 2], it would be beneficial to also include the respective results of those methods in Tables 2 and 3. In addition, their differences and similarities should be discussed in detail.

5. Since the used benchmark datasets are already reasonably explored, authors are advised to include evaluation on other datasets as well, e.g., from [6].

6. The transition matrix $P$ is missing self-loops to match with the results of Figure 1. Since you already define $P$ analogously to $\hat{\tilde{A}}$, you should focus on one notation for consistency reasons.

[1] Wu et al.: Simplifying Graph Convolutional Networks
[2] Klicpera et al.: Predict then Propagate: Graph Neural Networks meet Personalized PageRank
[3] Xu et al.: Representation Learning on Graphs with Jumping Knowledge Networks
[4] Hamilton et al.: Inductive Representation Learning on Large Graphs
[5] Kipf and Welling: Semi-Supervised Classification with Graph Convolutional Networks
[6] Shchur et al.: Pitfalls of Graph Neural Network Evaluation

----------------------------
Update after the rebuttal: The authors have addressed several issues and improved their manuscript. I greatly appreciate the effort and the new experimental results. However, the main weak point that the novelty of the approach is limited remains valid of course. Therefore, I am still more inclined to rejecting the paper. I have raised my score from "1: Reject" to "3: Weak Reject".

I have raised my score from "5: Weak Reject" to "6: Weak Accept".
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The paper presents a graph neural network model that aims at improving the feature aggregation scheme to better handle distant nodes, therefore mitigating the “smoothing” problem of classic averaging.

I find the paper clearly motivated and easy to follow, although some sentences could be streamlined and some repetitions could be removed. For instance last paragraph in page 3, this should be clear already and should be restated.

One thing that is not clear is how does the model cope with the increase in feature dimensionality due to the concatenation over different steps. Isn’t this leading to overfitting? Did the authors experiment with other schemes such as averaging or gating? If so it would be nice to see the results for each of the configurations as it is not clear to me what should be chosen a-priori.

Experiments are nicely executed and the proposed approach is compared against a rich array of other models. Results are state-of-the-art and also the analysis of the model is interesting, i.e. it doesn’t diverge when increasing # steps at test time.
How does the attention vector look like? Does it tend to peak at a given k, or is it more uniformly distributed? 

How does the model compare to having k GAT layers, each constrained to use neighboring nodes at step k as input for the attention computation? Did the authors experiment on this?

Overall I like the work but find the novelty quite limited, more effort could have been put into motivating the soundness of the use of multiple random walks. Perhaps some theory could be developed to make the paper stronger.
review_title: Official Blind Review #1

Meta-review: Two reviewers are concerned about this paper while the other one is slightly positive. A reject is recommended.
Decision: Reject