Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Since the publication of P-GNN (You et al., 2019), it has become clear to the graph ML community that node positional information can be effectively leveraged for link prediction and pairwise node classification tasks.
This paper introduces SMP, a novel stochastic message passing approach that preserves both permutation-equivariance (common to GNN models) and node proximities. Extensive experimental results show that SMP not only achieves competitive performance on many common graph ML datasets, but also succeeds to combine together the expressiveness of a standard GNN with P-GNN  (without incurring the scalability problem of P-GNN).

I thoroughly enjoyed reading this paper, both for the insights and the technical soundness. I have very few remarks about the paper, as I believe that i) SMP is an ingenious idea, ii) the experimental setting is adequate, iii) the quality of the writeup is high, iv) and the results appear to be reproducible.

If I had to nitpick, I'd say that part of Table 7 (currently in the Appendix) belongs to the main paper, as I was convinced about the superior runtime performance of SMP only after reading those numbers. If the avg running time for an SMP epoch was significantly larger than the one for GAT (for instance), I would have considered SMP yet another specialized model.
Instead, given that the GPU consumption (both in terms of computation and memory) is similar to any other GNN model, I believe SMP could be adopted as a more flexible graph ML method (which would avoid having to choose a method given the target task, e.g., node classification vs. link prediction).

One remark about L278: SMP cannot be considered anymore SotA for ogbl-ppa. The current SotA is more than 10 points above the performance achieved by SMP.
review_title: A significant improvement over P-GNN

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposed a proximity-aware graph neural network while maintaining the permutation equivariance property. The proposed model, dubbed as stochastic message passing (SMP), arguments the existing GNNs with stochastic node representations. The author proved the proposed method can model proximity-aware representations based on random projection theory. The experimental results show that the SMP can be used for multiple graphs and tasks. 

Although the proposed technique is relatively simple, the theorem shows that why such stochastic representations are beneficial for proximity-aware tasks. The experimental results also suggest that this simple technique is quite effective in many tasks. There are a few things that I'd like to comment on or ask listed below:

- Multiple tasks have been conducted to show the performance of the proposed model, but it is unclear which dataset or which task requires to be proximity-aware. It would be great if there's some quantitative metric that shows the importance of proximity in a given task. For example, the number of automorphic node pairs (within k-hop) and the ratio of label (dis)agreement would be a possible metric in node classification tasks. This will characterize the differences between datasets and highlight the contribution of the proposed method. Additionally, showing some examples of automorphic node pairs and the performance on these nodes could demonstrate the difference between models.

- Resampling random matrix at each epoch is emphasized multiple times in the manuscript, but without any empirical experiments. Would it be beneficial to resample this random matrix at every epoch? Although in theory, it would be possible to learn GNN that preserves node proximity, if a given task doesn't need to model proximity-aware representations, random resampling may hinder the convergence of the proposed method.

- There was a bug in the official release of the P-GNN paper, which has been recently fixed (please check the GitHub pull request history at https://github.com/JiaxuanYou/P-GNN/pull/12). I wonder which codebase the authors used for the experiments. / It would be also good if there's some comment on what makes P-GNN memory hunger. Is it because of improper implementation or because of some inherent limitations?

review_title: Review...

final_score: rating: 7: Good paper, accept
review_content: The authors propose to add random node features to the input of message passing graph neural networks for them to become proximity-aware. The paper provides exhaustive theoretical and empirical analysis of this idea, highlighting the advantageous properties.

Strengths:
- The paper is well written.
- The authors substantiate their claims with proofs and experiments.
- The method and proofs seem to be mathematically sound.
- Including the experiments in the appendix, the empirical analysis is very exhaustive and seems to be reproducible.
- The method is simple but effective, which is good. It also does not lead to a significant computational overhead but fits nicely into the existing message passing framework with linear time complexity (in number of edges).
- The paper provides a formal framework and analysis for a trick that has already been used successfully in practice.

Comments and Questions:
- The work of Sato et al. [1] seems to be closer to this work than the authors let know. I would welcome a more in-depth discussion than given in related work, even if the paper is only on arxiv.
- Definition 4 should go to the main text, as it is crucial for understanding.
- The proof of Theorem 1 shows the result only for graphs with 2 connected components. I think the theorem also holds for connected graphs (with the right automorphisms), which is important. If it wouldn't, the result would not always be relevant for practice. I think the current way of proving the theorem lacks that insight and discussion. Isn't it possible to prove the theorem for all graphs with a certain automorphism, regardless of number of connected components?
- Can the authors verify the suspicion that the non-linear variants overfit (line 270) by presenting the results on training data?
- It might be of interest to the authors that the idea was already used in a practical graph matching method by [2] (page 5, last paragraph), although without any theoretical analysis. It is nice to have a formal framework that justifies the application of this trick.
- In general, GNNs to solve matching tasks are a very fitting application for the proposed method, which the authors do not consider. They often rely on comparing distance measures in both domains, thus need proximity awareness. 

Typos:
- Line 87: "computationally expansive" -> expensive
- Line 607: "computationally expansive" -> expensive

All in all, there is not much to complain about. The paper achieves what it sets out to do in providing an exhaustive theoretical and empirical analysis of a simple but effective idea. The method itself is straight-forward and also not entirely novel. However, the formal framework and analysis is a contribution that is of interest to the community. Due to the shown properties and the high efficiency of the approach, the paper can have significant impact on future GNN architectures in practice. I therefore recommend to accept the paper.

[1] Sato et al., Random features strengthen graph neural networks. arXiv:2002.03155 

[2] Fey et al., Deep Graph Matching Consensus, ICLR 2020
review_title: A well-rounded analysis of a simple method.

final_score: rating: 3: Clear rejection
review_content: While the paper is easy to follow, I found all the results in this paper trivial and already-known.

Pros:
1. The paper is well-written and easy to follow.

Cons:
1. The entire Section 3 is not novel. It is a mixture of the preliminaries of GNNs and the trivial results of Corollary 1 and Theorem 1. Moreover, Theorem 1 is not rigorous. What if walk-based proximity is just a constant function? What if a given graph does not contain any automorphism?
2. “Preserve walk-based similarity” is not rigorously defined. It seems that it just means all nodes have different embeddings.
3. The proposed model is not permutation-equivariant after adding Gaussian noise. It is trivial that the model becomes permutation-equivariant when the Gaussian noise is ignored (because the model just reduces to an ordinary GNN).
4. The claim that SMP preserves walk-based proximity is trivial and just relies on the fact that randomly-sampled vectors from a Gaussian distribution are different from each other.
5. The idea of using node identifiers (essentially equivalent to the Gaussian noise) to make GNNs position-aware is not new. In fact, this idea is clearly mentioned in the P-GNN paper already (Section 6.2 of [1] “for inductive tasks, augmenting node attributes with one-hot identifiers restricts a model’s generalization ability”).
6. In Section 5.3, it is unclear why the OGB node classification datasets are not used.

[1] https://arxiv.org/abs/1906.04817

review_title: Methods are known, results are trivial.

Meta-review: This work proposes a modification of a GNN architecture by feeding random node features to bootstrap the message propagation. This enables the discriminability of automorphic node pairs with a lightweight, simple change. Experiments are reported showing improvements over baselines. 
Reviewers had mixed impressions of this work. On one hand, they found the proposed model principled and with strong empirical performance. On the other hand, they perceived a general lack of novelty and a somewhat misleading theoretical analysis. After careful review, the AC ultimately believes that this work does require an extra iteration that further solidifies the contributions and aligns the theoretical analysis with the empirical performance. In particular, the use of random initialization is folklore in the GNN literature, especially with regards to spectral methods (e.g. power iterations are typically initialized using a random vector, and these constitute the simplest forms of linear GNNs). The authors are encouraged to address these comparisons with further detail, as well as the excellent feedback given by the reviewers. 
Decision: Reject