Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies positional encoding (PE) for Graph Neural Networks (GNN). A positional encoding can be seen as a computed feature for each node from characteristics of the graph. A well-known example of PE are the components of the eigenvectors of the Laplacian of the graph. Unfortunately, such a PE is not permutation equivariant. This is mainly due to the fact that eigenvectors are not uniquely defined.
This paper address this issue with some care (correcting some mistakes made in previous works).
Section 3 of the paper presents the main theoretical results of the paper. In particular, the authors introduce a notion of stability that is stronger than equivariance: if two input graphs are 'similar' then their outputs through a stable layer should also be 'similar' with a 'Lipschitz' constant. This notion is interesting. Then, the authors explain some errors made in the literature and address these issue by proposing a PE-stable layer that is shown to be PE-stable under some conditions on the spectrum of the Laplacian. Some other techniques to get PE-stable layers are provided in section 3.3
In Section 4, experimental results are provided with this new architecture for task 1: link prediction and task 2: domain-shift link prediction. These experiments demonstrate the effectiveness of PE-stable layers.
main_review: Strengths: the paper is well written and I liked the theoretical part (Section 3). The ideas are very natural and nicely presented. The notion of stability will likely be picked up in future works and the authors show how to construct PE-stable layers which can be useful.

Weakness: the evaluation in Section 4 is very disappointing. Equivariance is only useful for inductive task but the link prediction task considered by the authors is a transductive task. For task 1, I do not see why you would ask your algorithm to be equivariant as the learning algorithm is trained on one graph. In such a case, you can choose an ID for each node and use this ID to make your link prediction. Task 2 is better to test equivariant architecture. But for task 2, I do not understand why the authors look at the link prediction problem. For example, the PPI dataset is typically not used to do link prediction so why doing this here?
Indeed, the authors are aware of this weakness as they write: 'Both tasks may reflect the effectiveness of a model while Task 2 may better demonstrate the model’s generalization capability that strongly depends on permutation equivariance and stability.'
To validate their theoretical results, the authors should consider a task where equivariance is 'crucial'. The QAP problem studied in 'Expressive Power of Invariant and Equivariant Graph Neural Networks' by Azizian and Lelarge (ICLR 2021) is probably a good candidate.

summary_of_the_review: There is a mismatch between the theoretical part of the paper and the experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel GNN layer called PEG layer to address the issue that existing positional encoding are not generalized to unseen graph very well. PEG designs different operators for raw features and positional features separately, which is able to ensure permutation equivariance and rotation equivariance for each type of feature, respectively. The experimental results have also demonstrated the power of the proposed approach.
main_review: Strengths:
1.	The proposed approach is well motivated and mathematically rigorous.
2.	The writing is in general clear and well-reasoned.
3.	The experimental results have demonstrated the superiority of the proposed approach on multiple datasets.


Weaknesses:
1.	The stability definition needs better justified, as the left side can be arbitrarily small under some construction of \tilde{g}. A more reasonable treatment is to make it also lower bounded.
2.	It is expected to see a variety of tasks beyond link predict where PE is important.

summary_of_the_review: This paper provides a through discussion on limitations of existing PE approaches and proposes the criterions of PE-equivariance and PE-stable. Mathematically, this paper proves the proposed PEG layer is able to preserve permutation equivariance as well as to achieve PE-stability. The proposed technique is solid and novel. There are some minor concerns as raised in weaknesses, but overall it is a paper worth of accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the topic of equivariant and stable positional encodings (PEs) for graph neural networks. It goes along a recent line of research that develop PEs for GNNs to: i) disambiguate structurally different nodes using positions and ii) improve the GNN in consideration. 
This work formally studies the two conditions of equivariance and stability for graph PEs (Section 3.1). A new GNN layer is proposed (Section 3.2) based on modification of a GCN based layer with edge features that can satisfy the two conditions. Experiments are conducted on several small-scale link prediction datasets with performance improvements over baselines.

main_review: (a) -- Comments, with strengths:
- *Positioning*: The location of this work with respect to the literature is detailed and comprehensive as the limitations of existing works along this line is properly described. In particular, the discussion with Laplacian eigenvectors based PEs that could have ambiguities due to the sign and multiplicity is reviewed clearly and the work attempts to address the issues henceforth.
- *Writing*: The writing is easy to follow for readers aware with the research direction. Equivariance and stability of PEs to be used in GNNs is at the centre of the paper and their definitions, formalization and relevant conditions are clearly expressed.
- *Significance*: The contribution of the paper thus is helpful for the community given there are several papers recently that are attempting to use graph PEs to improve GNNs expressivity. In those works, the equivariance/stability issues of PEs were not explicitly addressed. The PEs were more like augmentations to GNNs in terms of supplying higher structural information when they learn on graphs; as nodes in graphs would not be canonically defined in terms of positions.
- *Empirical results/Experiments*: The focus in this work is only on link prediction tasks. Although I believe the work can be applied to general graph representation learning for other tasks as well. Experiments on the proposed model *compared to baselines* show the advantage of using the PE in the proposed model that uses these as edge weights. However, these models do not provide SOTA results and lag *behind the top scores* on the leaderboards of two OGB datasets considered [1]. In this respect, it may not be clear how the satisfiability of the two conditions leads to a powerful model, in practice.


(b) -- Other comments/concerns:
- In page 6, "We implement g in our model PEGN with further simplification". => Does this mean the paper does not present a GNN 'g' which is PE-equivariance and PE-stable in general? Are the results of satisfying the two conditions *tied* to the instantiation of g_PEG only? [Since, g_PEG seems a modification of the GCN with edge weights that are supplied with positional features of source and destination nodes.] 
- In page 2, the paper claims "The key idea is to use separate channels to update the original node features and positional features." However, to the best of my understanding of the paper, I feel this is not (necessarily) enforced. For instance, the Eqn. 6 does *not update positional features*.
- In page 2, the paper states "PEG achieves comparable performance with strong baselines based on DE". I could not find comparisons on the datasets where PEG is compared against DE.
- During the discussion of non-uniqueness of LE as PE used in previous works, I believe simply using absolute signs of the eigenvectors would guarantee permutation equivariance; although I understand the stability issues. 
- The title of the paper says ".... More Powerful Graph Neural Networks". I feel this addition of power is not discussed in the paper. I understand that its necessary to sort (and get rid of) the issues of Z_LE while using them as PE. But is the power being added just because of the equivariance/stability conditions met? This is also reflected in the experiments where the scores on the 2 OGB datasets do not compare to SOTA results. In other words, I am still unable to ascertain to myself whether the performance boost (compared to baselines) comes from i) simply the PE variants used (as they may be bringing other higher structural information to the GNN used). or ii) the addressal of the issues of equivariance and instability with the PEs? To this end, a fair study of two model versions where one version has the issues of instability and the other does not have, leaving all other settings intact for the two versions, would help addressing this question!



(c) Minor comments: 
* Page 8; under the heading "Implementation details": typo constant feature (P) ==> constant feature (C)?
* The comparison of the results on the datasets with other GNN SOTA is not presented?
* In the experiment tables, the mean and s.d. is reported. How are these reported on? How many runs? These details can help reproducibility.



References:  
[1] OGB link property prediction leaderboards: https://ogb.stanford.edu/docs/leader_linkprop/  
[2] Srinivasan, B. and Ribeiro, B., 2019. On the equivalence between positional node embeddings and structural graph representations. arXiv preprint arXiv:1910.00452.


summary_of_the_review: Overall, I feel this work is interesting and important in this direction of *designing PEs for GNNs* that do not have any issues violating the beauty of using GNNs in the first place; and critical for link prediction tasks as known from the literature [2]. However, it seems the empirical results may not be adequate to reflect on the technical contributions of the paper. In summary, my evaluation of ‘correctness’ and ‘technical novelty and significance’ measures of this paper are positive, while the evaluation of ‘empirical significance’ does not seem to align to the technical contribution.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper focuses on tasks of a set of nodes handled by graph neural networks (GNNs), which generally requires random feature (RF) or positional encoding (PE) to recognize the node identity. When RF is hard to converge and PE is less generalizable and stable to unseen graphs, authors propose a new architecture name PEG, processing node features and PE in different channels. Rigorous theoretical analysis shows PEG is permutation invariant to node features and rotation equivariant to PE, and its stability is guaranteed. Extensive experiments on link prediction (the task on node pairs) demonstrate the advantage of PEG.
main_review: I appreciate the reasonable motivation and rigorous analysis in the paper. I only have some comments on it.

1) The analysis of matching is limited to graphs of the same size. Is there any possibility to generalize to different sizes? How does it consistent with experiments where two graphs are of different sizes?
2) The idea actually smartly borrows from SE(3)-transformer (or etc) with positional encoding (PE) to replace the physical coordinate. The inner product in eq (6) makes it only rotation equivariant while it is easy to use L2 distance (or etc) to make it also translation equivariant.
3) Do authors have any intuitive interpretation on PE, why do we need it to be rotation (or translation) equivariant? Some examples would help the audience further to understand the significance.
summary_of_the_review: I am generally satisfied with the content of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a novel PEG layer to account for positional encodings in graph neural networks and state some necessary conditions for its stability and permutation equivariance while providing theoretical insights for the same. They show that their proposed layer is PE-equivariant under some conditions (theorem 3.6) and also derive the value of the constant C for equation 1 to guarantee PE-stability. Extensive experiments done for the task of link prediction clearly show that the proposed layer is indeed useful and the only subpar baseline method is SEAL (which outperforms PEG in some cases). The authors have also performed experiments to vividly show the generalization ability of their layer using the task of domain-shift link prediction, which are indeed interesting. The simplicity of their approach complemented with a reasonable runtime further adds to the overall utility of this work. The tweak used in section 4.1 for training on graphs where the union of link sets for training, validation and testing cover the entire graph is also useful and can also be leveraged in other methods having explicit positional encodings for GNNs.

Given the recent upsurge in the amount of work done to incorporate positional encodings in GNNs, work such as this that addresses the shortcomings of previous methods and also provides a theoretical framework was necessary. 

Small typo on page 4 and 5 - “features” spelled as “feautures” .

main_review: Strengths: 

1) Lemma 3.4, where the authors theoretically show the particular PE design (of matrix B) violates PE-stability is very useful. Theorem 3.7 where the authors have explicitly derived the value of the constant C for equation 1 is particularly relevant (although the bound can be made tighter).

2) The authors have also put some effort into pointing out the generalizations to other methods. Further, they provide some guarantees for PE methods that follow the optimization objective in equation 7 and show their PE equivariance.

3) Figures 2 and 3 have interesting observations on real world data.

4) I found the Domain-shift link prediction experiments to be very practical and highly interesting. 

5) The design choice for the PEG layer in equation 6 is sufficiently simple and easy to compute. The conditions in equation 4 and 5 are very sound. Table 2 shows that the proposed method is also substantially faster than the best performing baseline SEAL.


Weaknesses (and questions for authors): 

1) “A GNN layer is expected to be permutation equivariant and stable. These two properties, if satisfied, guarantee that the GNN layer is transferrable and have better generalization performance” - the authors do provide an intuition in subsequent lines and experiments to support their claim in section 4.3, but are there any relevant works that they can direct to? Can, or more concretely, does it hold for any other type of generalization?

2) Can the experiments be done on a wider category of tasks? Although the authors do mention it as a future work, it will be quite interesting to see some evaluation on at least one of: node / graph classification / community detection tasks as well.

3) Can the authors also consider at least one more recent and strong baseline, such as [1]? The evaluation is quite thorough and I understand that it might be difficult to perform these experiments, but it will be quite interesting to see the outcomes, since at least one of the recent methods, ie SEAL, is performing very competitively (and [1] has been shown to outperform SEAL in some cases).

4) Can the authors provide more intuition on why they arrived at the proposed choice in Equation 6? Also, is there any other reason for choosing GCN apart from its simplicity and ease of incorporating the permutation equivariance? 

5) The zig-zag patterns in figure 4 are very interesting. I understand that it may or may not be trivial, but it will be helpful if the authors can provide some more intuition for such behavior apart from what is stated in section H.4 .

6) Can the authors elaborate the related works section 1.1 a bit more? Particularly, more details on the methods that propose an explicit use of PE techniques such as [2] and [3] might be helpful.

7) Although intuitively sound, as I have mentioned in the strengths subsection above, it will be great if the authors can provide some reference or more conclusive evidence to this statement - “Inspired by the stability of the eigenspace, the idea to achieve PE-stability is to make the GNN layer invariant to the selection of bases of the eigenspace for the positional features” on the second last paragraph on page 5.

[1] S. Abu-El-Haija, B. Perozzi, R. Al-Rfou, and A. A. Alemi, “Watch your step: Learning node embeddings via graph attention,” in Advances in Neural Information Processing Systems, 2018

[2] Srinivasan, Balasubramaniam, and Bruno Ribeiro. "On the equivalence between positional node embeddings and structural graph representations." arXiv preprint arXiv:1910.00452 (2019)

[3] Dwivedi, Vijay Prakash, and Xavier Bresson. "A generalization of transformer networks to graphs." arXiv preprint arXiv:2012.09699 (2020).
summary_of_the_review: Overall the paper is very well written, has some interesting theoretical insights and very practical results. It will be very helpful if the authors can further address some of the  questions and weaknesses as pointed out in the previous subsection of this review. I believe that the authors should at least perform more diverse experiments to completely support their arguments regarding generalization and higher stability. After addressing these minor pointers, I believe that the contributions will be worth presenting at the conference. I additionally support the simplicity of the proposed approach, both analytically and computationally.
review_title: null

Meta-review: This work studies the question of increasing the expressive power of GNNs by adding positional encodings while preserving equivariance and stability to graph perturbations. 
Reviewers were generally positive about this work, highlighting its judicious problem setup, identifying the right notion of stability and how it should drive the design of positional encodings. Despite some concerns about the discrepancy between the theoretical results and the empirical evaluation, the consensus was ultimately that this work is an interesting contribution, and therefore the AC recommends acceptance.
Decision: Accept (Poster)