Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: The authors tried to explore the key differences between two link prediction methods. However, some statements are not precise. 

The example the authors provided in the introduction is not correct. The GAE will also assign them different probabilities. When we use GAE to learn node embedding in the graphs, we usually have two different inputs: (A) nodes in the graph have input features (B) nodes in the graph do not have features and we assign each a one hot vector. For both two cases, each node in the graph in Figure 1 is unique node. Even node v2 and v3 play the same role in terms of graph structure, they still have different node embeddings considering the node features.

It is worthy to discuss that why node embeddings learning from exisiting method cannot help SEAL. It can be seen from the experimental results in two SEAL papers[1][2] that the node embedding does not help improve performance.

[1]Inductive Matrix Completion Based on Graph Neural Networks
[2]Link Prediction Based on Graph Neural Networks
review_title: The authors discusses the difference between node embedding based method and subgraph embedding based method for link prediction tasks. However, the conclusions are not helpful.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper provides theoretical analysis of graph neural networks for link prediction, following a number of recent papers that have developed the theoretical understanding of graph neural networks. For example, the work of Xu et al (ICLR 2019) draws on the Weisfeiler-Lehman graph isomorphism test to develop a theoretical framework in which to analyse the expressive power of Graph Neural Networks. In particular, they show that architectural features in common graph neural network models limit the expressivity with respect to problems of node and graph classification and show how one can construct graph neural networks whose expressivity matches the Weisfeiler-Lehmam test. In more recent work, Li et al (NeurIPS 2020) show that augmenting node features with a "distance encoding" enables a graph neural network to distinguish node sets in cases where the Weisfeiler-Lehman test fails. This submission is perhaps most closely related to this recent paper of Li et al.

In this work, the authors discuss how GAEs cannot always discriminate between links (node pairs), even when a GAE has maximal expressivity at the node level (it can generate representations which discriminate all non-isomorphic nodes). They provide an enhancement they call a "labelling trick" which can be used to enable GAEs to discriminate between node sets. With the labelleing trick, ach node in the GAE has an additional feature corresponding to a node set specific label. That is, when learning representations for a given node set S, this feature takes on a value which is dependent on the node set S and the graph structure. The authors show (Theorem 1) that this enhancement enables any maximally node expressive GNN (a GNN which can discriminate all non-isomorphic nodes) to discriminate between any pair of non-isomorphic node sets. The strong performance of SEAL, a recent SOTA method for link prediction, can be understood in the context of this result. 

As a second theoretical contribution, the authors define a "local-h isomorphism" concept, which they propose can be used to explain why practical GNN implementations perform well, despite theoretically requiring the number of layers to be proportional to the number of nodes in order to distinguish all nodes that 1-WL can discriminate (in the worst case).

**Positives**
Studying the expressive power of Graph Neural Network architectures is an important topic, as can be seen by the increasing number of papers in machine learning conferences over the past couple of years. The analysis in this paper extends the theory with respect to the link prediction problem and provides theoretical justification for the strong performance of SEAL on link prediction benchmarks. 

**Concerns**
However, I have some concerns regarding the novelty of the contribution and the significance of the main theoretical result (Theorem 1). 
1. The main methodological contribution in this paper is the concept of the labelling trick, which can be used to improve the representational power of GNNs and explain the strong performance of SEAL. This looks like a special case of the distance encoding method presented in Li et al (NeurIPS 2020). The authors cite this work but do not discuss how their labelling trick relates to the distance encoding. Li et al also provide an explanation of the strong performance of SEAL (as an instance of their distance encoding method) as well as using their analysis to motivate alternative models which give a small performance improvement over SEAL.
2. The main theoretical result (Theorem 1) assumes the existence of a GNN with maximum node expressivity, in the sense that it can discriminate all non-isomorphic nodes in a graph. By my understanding, this architecture does not exist. Indeed, I believe Theorem 3.7 of Li et al (NeurIPS 2020) shows that the distance encoding method (which seems to be closely related to the labelling trick) is not sufficient for this. In my view, a more useful theoretical result would be something along the lines of Theorem 3.3 of Li et al, which illustrates how the distance encoding method improves the representational power of GNNs for a large number of graphs where methods bounded by 1-WL would fail.
review_title: Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper focuses on the link prediction task for graph neural networks. More specifically, it compares GAE and SEAL by providing theoretical evidence why GAE is not able to learn structural link representations, which as a result leads to suboptimal performance in the link prediction task. The paper also introduces a labeling trick that can help GNNs to learn structural link representations. 

Strong points:
1. The paper is clear, easy to understand, and the definitions and theorems provide good reference and proofs.
2. A deeper understanding of the link prediction task is indeed needed as a lot of GNN works are mostly using classification as the downstream task.
3. It provides good argument and clear example why some GNN models would not work well in link prediction by showing that individually learning node representations cannot handle the case where two nodes appear in topologically identical neighborhoods in the graph. It also provides insights as to how to mitigate such issues.

Weak points:
1. The comparison is oversimplified and overly generalized. The paper mostly compares GAE and SEAL, but there are much more GNN models that should be compared.
2. The sheer separation of GAE and SEAL model is not convincing. GAE and SEAL are both GNN models which follow the message passing and aggregation approaches. There's no clear argument or theoretical explanation how these two are fundamentally different. 
3. There are a lot of existing work that considers position in encoding nodes (such as position aware gnn [2]) and should be able to learn expressive structural link representations. The paper does not compare with them.
4. The experiment does not cover the most recent models. In addition, more benchmark datasets should be used. For example, FB15K (this is a widely used knowledge graph link prediction benchmark dataset), PPI, WN18, etc. Since previous work on gnn link prediction uses  
those dataset, I'm expecting to see a more comprehensive comparison using those datasets. More dataset can be found here: https://paperswithcode.com/task/link-prediction
5. The paper should also consider comparing with knowledge graph embedding models which are focusing on the link prediction task. There are also existing work that combine the idea of knowledge graph embedding with GNN models in link prediction [1].

Other comments:
1. In def 5, gnn does not always have an invariant function mapping, depending on the message passing operations used e.g. in the graph sage paper, there are comparison using lstm message passing operator, which is not permutation invariant.
2. Section 3.1 mentions that the paper uses GAE to denote the general class of GNN-based link prediction regardless of the choice of GNN and aggregation function. However, research has shown that the specific choices of message passing operations and aggregations have significant impact on the expressiveness of GNN [3]
3. Section 3.3 mentions that GAE cannot learn structural link representations, but from the example in fig1, it seems like this is caused by the graph isomorphism issue. there are existing work that can mitigate this issue, for example position-aware graph neural network [2].


Reference:
1. Schlichtkrull, Michael, et al. "Modeling relational data with graph convolutional networks." European Semantic Web Conference. Springer, Cham, 2018. 
2. You, Jiaxuan, Rex Ying, and Jure Leskovec. "Position-aware graph neural networks." arXiv preprint arXiv:1906.04817 (2019).
3. Xu, Keyulu, et al. "How powerful are graph neural networks?." arXiv preprint arXiv:1810.00826 (2018).
review_title: Need more experiment and comparison to support the argument

final_score: rating: 3: Clear rejection
review_content: Summary:

The paper presents results of two popular classes of methods for graph neural networks.  Namely, GAE and SEAL.  The paper show results on the Open Graph Benchmark of several existing methods, and concludes that GAE cannot learn structural link representations while SEAL can. 

The paper is descriptive in its presentation, and does a good work on detailing the ideas behind GAE and SEAL.  However, I felt the lack of a contribution on the paper.  As it stands, it reads more as a tutorial and presents key insights of existing methods.

Pros:
- Clear explanations of existing work.

Cons:
- No clear contribution over explaining existing approaches.
- Experiments show existing results on OGB.
- No results on the mentioned labeling trick are given.

Comments:
- In Fig. 1 you mentioned that $v_2$ and $v_3$ will get the same representation through a GAE.  Did you train one and observed it?  It will be more conclusive if you show the results and the embeddings to validate your observation.

- Your labeling trick depends on the set of nodes $S$ used.  However, how do you select such sets to produce the labeling? Are you sampling all possible subsets $S$?  Since this seems to be a form of contribution, it should be clear how to use it in any scenario.

- In your experiments, due to the way the paper presents the label trick as the novelty, I was expecting to see the boost of performance of such trick on the existing architectures.  However, Section 7 presents results of existing approaches on the OGB.

Minor comments:
- "Following (Srinivasan & Ribeiro, 2020; Li et al., 2020)" should be a textual citation

Overall rating:
Due to the main problems stated, I cannot recommend the paper for publication at ICLR.  The manuscript reads more like a tutorial, which may be of interest for readers finding a summary of the advances.  However, as a paper advancing the field of graph neural networks I feel it lacking.
review_title: Interesting summary of the field, but not enough contribution for the conference

Meta-review: The authors study the expressive power of Graph Neural Network architectures for the link prediction problem and provides theoretical justification for the strong performance of SEAL on link prediction benchmarks. However, The reviewers think the paper needs to improve in several aspects before it can be published: 1. More clearly explain the theoretical analysis and contribution. 2. Extensive and in-depth discussion of the similarities with and difference to the work of Li et al. to show the novelty of current work. 
Decision: Reject