Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a framework that utilizes Random Walk Positional Embeddings (RWPE) as extra features to boost the performance of GNNs. In particular, positional embeddings are updated as a separate forward network in each layer. The framework has demonstrated improved quality by injecting its positional embeddings and feed-forward structures in several GNNs.

main_review: The paper discusses the important topic of how to better utilize the structure information in message-passing-based graph neural networks. The proposed structure and way to generate positional embeddings demonstrated good results on several datasets, however, it still lacks a thorough justification of where the improvement comes from and how each component contributes to the final quality.

## Pros
The paper tackles the problem of injecting positional embeddings in GNNs, which is an important topic of effectively utilizing structure information. The separate feed-forward network of RWPE demonstrates improved accuracies and can be a simple add-on to multiple GNN structures. 

## Cons
1. The paper proposes two major components: random walk position embeddings and a standalone feed-forward network to update the embeddings. While I think these two strategies are a good add-on to many basic GNN structures, I do feel there are some points that the first part is of limited novelty, and some points are not properly justified in the arguments and experiments.
The added LapEig makes the two options of LapEig and RWPE vague in their motivations. In fact, the trace loss: Tr(p^T\Delta p) is enforcing the positional embeddings to resemble LapEig. While the authors claim that RWPE is better, I was wondering why having the positional embeddings in the “final” layer would contribute to a better output. If that would be the case, would simply appending these embeddings to the final layer give similar quality?
2. The RWPE itself is not novel, as the authors have also pointed that the idea is inherited from a previous. However, the feed-forward network's effectiveness is not properly proved. Specifically, it is not clear whether the gain attributes to the specific structure instead of the added parameters of the feedforward network. That is, suppose, we have the newly added position embeddings, but without the p_i^{l+1} updating mechanism, will we still have the boost of quality? Moreover, the added positional embeddings are also adding more capacity to the network.
Minor:
Typo: Proposed Architecture: first sentence: make easy -> make it easy
Why the edge dimension in Equation (2) is of dimension d?
The argument of flipping signs in LapPE is not the full story of Laplacian decomposition. In fact, the eigen-vectors of the same eigen-values can be any bases in that subspace (instead of different signs/directions).

summary_of_the_review: The paper discusses new position embeddings and the feed-forward networks. However, the novelty of the first part is limited and the effectiveness of the second part is not properly justified.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors mainly focus on the node positinal embedding for GNN. The proposed positional embedding is geneal and can be applied to many GNNs.
main_review: Strengths:

1. consider postional embedding in GNNs, the proposed framework is very general and can be directly used in many existing GNNs.

2. The design is simple, insert the positional embedding to current existing message passing function. And also update the positional embedding as well e.g., in Eq.(9). Some method like Lapalacian or Random Walk are used to initilize the positional embedding.

3. The results are good in the experiements.

Weaknesses:

1. My big concern is that the motivation of positional embedding is not very strong. For example, Eq.(7) can do the similar thing as Eq.(9), just using the vector concatenation. As claimed in the paper, the main different is that the Eq.(9) use the tanh function. Does that mean the Tanh is key for the positional embedding? Experiments on different activation function may be more convicing.

2. The author claim that "PE as eigenvectors are defined up to ±1, leading to 2k number of possible sign values". However,  the use of the tanh activation function to allow positive and negative values for the positional coordinates. Will the positive and negative sign also casue the same issue?

3. Some other baselines can be comapred, like 
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International
Conference on Machine Learning, pp. 7134–7143. PMLR, 2019.

summary_of_the_review: In summary, I think the proposed method is this work is very practical. It seems that using a simple positional embedding help a lot. However, it seems that the motivation is not very strong, like how to explain this positional embedding.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces the idea of learning positional representations to enrich node representations of graph neural networks(GNN) to improve the representation power of message-passing graph neural networks(MPNNs) while keeping in linear complexity. 
main_review: **Strengths**

* The problem of message passing neural networks(MPNNs) lacking positional information of nodes is well-motivated by molecules.
* The Proposal is understandable & straightforward, with an affordable memory cost.
* Well written and provides detailed related works.

The idea of decoupling structural and positional encodings in MPNNs while keeping in linear complexity is very simple yet a clear idea to me.  Also, the motivation of this paper is elucidated via molecules where learned node embeddings do not differentiate between positions. Finally, the related works section is well written and explains the problems in the GNN domain clearly.

**Weaknesses**
* I would expect more experiments on different domains (such as recommendation systems), not just for the molecular domain. 
Introduced PosLoss does not introduce an important change to results at all. Thus, the existence of this newly introduced loss seems questionable.
* Claim that achieving SOTA results for the ZINC dataset(12K graphs) seems questionable because [1] achieves a 0.074 MAE score. 
* For the large-scale graph dataset( around 430K graphs), OGBG-MOLPCBA, which is bigger in the number of graphs and more complicated in terms of learning, the benefits are questionable. It seems the choice of aggregation outweighs the effect of positional encoding[2,3]. 


My main concern is that the paper claims it is doing more than the listed contributions. First of all, introducing loss for positional encodings seems not working at all. Second, the claim is that achieving SOTA results for the ZINC dataset(12K graphs) seemed false to me as there is a recent paper [1] achieving 0.074 mean-absolute error with edge features. Also, doing more experiments on different domains, I think, is needed to show that this works. Idea working on the molecular domain only does not imply that this idea works well. Experimenting on domains like knowledge graphs would be nice to see its results since the position of nodes also plays a significant role in that domain.

Finally, the most important thing for me is the benefit of learning decoupled positional embeddings in graph neural networks. Graph neural network architectures such as Directional Graph Networks[2] and PHC-GNN[3] seem to outperform the proposed model on the OGBG-MOLPCBA dataset. Even leveraging LSPE on Principal Neighborhood Aggregation[4] gives incremental results. What if we add more aggregators to PNA or use different domains like in PHC-GNN? I would expect a discussion on why these methods outperform the proposed plan as I believe it is important to tell readers why these methods outperform yours. Overall, it is a good paper with a simple idea, but I would expect more reasoning on why this method can fail and more experiments on different domains.

[1]Bodnar, Cristian, et al. "Weisfeiler and Lehman go cellular: Cw networks." arXiv preprint arXiv:2106.12575 (2021).

[2] Beaini, Dominique et al. “Directional Graph Networks.” ICML (2021).

[3] Le, Tuan, et al. "Parameterized hypercomplex graph neural networks for graph classification." arXiv preprint arXiv:2103.16584 (2021).

[4] Corso, Gabriele, et al. "Principal neighborhood aggregation for graph nets." arXiv preprint arXiv:2004.05718 (2020).
summary_of_the_review: Overall, this paper tries to alleviate a significant problem in MPNNs. Still, limited experiments in a single domain and counter-intuitive results for OGBG-MOLPCBA and ZINC datasets make this paper’s contributions questionable.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes to use a separate positional representation with its own loss function for graph representation learning and achieve impressive empirical results.
main_review: Pros:
- The idea of disentangling the positional representation is novel.
- The empirical results are really impressive.
- The paper is well-organized and the writing is good.

Concerns:
- The design of this method is complicated and may introduce more parameters. This may cause problems that the model may tend to overfit the data and make it unclear if the improvement comes from the increase of the number of parameters (I wonder why the #Param does not increase so much as listed in the tables as the sizes of A_i's in (14) all double?).
- How the positional encoding proposed in the paper compares to relative positional encoding in GNN, e.g., that used in Graphormer (Ying et al. 2021)? And is it possible to further boost the performance by combining it?
summary_of_the_review: The proposed method has strong motivation and empirical results and I vote for an acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is concerning the Positional Encoding (PE) for GNNs. 
PE augments the typical GNNs to distinguish isomorphic nodes. However, existing PE models such as Laplacian eigenvectors require huge computational resources.
This manuscript proposes LSPE that augments the input to the nodes AND the embedding vectors with PE elements. 
The LSPE models iteratively updates the embedding for PEs, in addition to the node feature embeddings. 
The update formula of the PE embedding is similar to those of the node feature embedding, thus the computational requirements of the LSPE does not . 
The manuscript tests two ways of PEs, one is based on the Laplacian, and the other is based on the random-walk. The manuscript also proposes the PE=only loss to foster the training. 
Experimental results shows that the propose LSPE can improve the graph regression of the ZINC dataset greatly, and also can achieve some improvements in graph classification tasks on the MOLTOX21 and the MOLPCBA datasets.  

main_review: (Sorry, I re-organized the review to meet the guideline)

### points 
(+) motivation sounds reasonable

(+) easy read, appendix full of useful information and explanations

(+) technical contents including formulations are easy to follow

(-) Significance of experimental improvements: are they really significant? 

(-) Initialize of PE and the LSPE architecture, which item is important? 

### comments

The manuscript is easy-to-read. I feel no difficulty in understanding the discussions in the manuscript. 
Also, the appendix provides many useful material to readers, an additional plus (excepting the Section C.2. it is quite complicated lines of equations). 
I am rather new to the PEs for GNNs, but the manuscript helps me understanding the current PE research status and how we can place this work in that context. 

I like the idea of allowing PE to be updated through layers. As the manuscript claims, the PE is an important cue to distinguish isomorphism in graphs, but the initial injection of PEs like in Eqs(4-6) is not powerful enough to obtain good embedding features. 
The proposed formulation Eqs.(7-9) are clear to understand. 

The discussions in Appendix A is powerful enough for me to feel "in practice" the RWPE will work fine, though the proposed RWPE(+LSPE) has no theoretical guarantee to distinguish isomorph nodes. 

My main concern is related to the experimental results. 

Tables 1,2: 
I agree that the LSPE works fine to reduce the regression MAEs on the ZINC dataset. 
However, the improvements in the remaining MOLTOX21 and the MOPCBA datasets seems marginal. 
Considering the standard deviations (thank you authors to provide the s.d. !!), I'm not sure whether these improvements are statistically significant. 
Given the current manuscript, I need to judge that the proposed LSPE is successful in show solid improvements against the existing PE works in the minority (1 out of 3) of datasets. 

Some ideas: 
One is to conduct statistical tests on the current scores. If the LSPE obtains small p-values in the MOL datasets, then, it is great! 
Another is to test more diverse datasets. If the LSPE is really powerful (I believe so), the LSPE will achieve clear score improvements in many additional datasets. 

Perhaps adding extra metrics to support the efficacy of the LSPE may improve the impression of the manuscript. 
For example, report memory/space usages of the proposed model. 
One important motivation for this research is a computational difficulty of stronger GNNs (than 1-WL). 
Then it may be beneficial to show that the existing approach actually does not work with larger graphs. 

Table 3:
The results in the Table 3 indicates that the choice of the initial PE (LapPE, RWPE) is much important than the LSPE updates. 
Perhaps it may be straightforward to emphasize the importance of the PE Initialization, not the LSPE architecture? 
In my understanding, the current manuscript weighs more on the LSPE (e.g. the subsection "contribution" in Sec. 1 and Fig 1). 

summary_of_the_review: I find the proposed idea reasonable and straightforward (in a positive manner). But I'm not fully sure the experimental results well support the claims. I also have a concern that the most influential time is the PE init., not the PE embed. update formulation. 


============================================

After author feedbacks:

I feel the answers from the authors are largely satisfactory. 

Other reviewers raise a concern about the novelty of the proposed methods. I agree that the novelty is minor. 

However, the experimental results and the statistical test reports indicate the strongness of the proposed framework in practice. 
Additional experiments on other domains are a positive surprise. 
Therefore I modify the review score one step upward.
review_title: null

Meta-review: This work adds the positional encoding (akin to those in transformers, but adapted) to GNNs.
In their reviews, reviewers raised a number of concerns about this work, in particular, lack of novelty, lack of ablations to demonstrate the claims of the paper, lack of comparison to previous work (e.g., position-aware GNNS, Graphormer and GraphiT which would appear very related to this work), lack of motivation (e.g., the introduced positional loss do not actually improve performance), and whether the experimental results were really significant.
During the rebuttal, the authors replied to the reviews, to address. the concerns that they could. Of the reviewers, unfortunately only one reviewer elected to respond to the authors. It is disappointing that the four other reviewers did not respond and overall the reviewers did not discuss this paper further.

The authors chose to highlight privately to the AC that two reviewers who scored the paper unfavourably did not respond. The authors then argued this should be taken into account in the score (presumably to make acceptance more likely)--however, two favourable reviewers also did not respond (not highlighted by the authors). I understand this kind of private request to the AC to dismiss unfavourable reviews (especially if they do not respond) is becoming common--I find it unhelpful--I can see who and who has not responded.

Nonetheless, looking at the responses to the original concerns of the reviewers highlighted above, I believe the authors have adequately addressed the concerns of the reviewers. Therefore i recommend acceptance but only as a poster.
Decision: Accept (Poster)