Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work added a model into GNN to improve link prediction. The connection is a weighted combination of the model's output and GNN's output in the scoring function (scoring a predicted link).  The paper claims that this model computes the number of overlapped neighbors. Experiments show the combination improves the performance.
main_review: Originality: It is an incremental approach with lots of things that are not clearly explained.

- Eq.(8) aggregates features of neighbors but why it can "count the number of overlapped neighbors"?
- What is "overlapped neighbors"?  It seems to be a pair-wise concept that measures the relationship between two nodes (overlapped neighbors of the two nodes). However, I am not seeing any pair-wise measurement in the equations.
- Why choose the number of overlapped neighbors, when there has been multiple kinds of heuristics-based measurements (as discussed in Section 3.2)? 
- There should be more essential methods to make a GNN model be aware of overlapped neighbors/subgraph.  Creating two models and connecting at the last layer is probably the most trivial idea. I suggest the authors to incorporate the overlapping subgraph into the convolutional operation in Eq.(10).
- Even though the models could be connected and jointly trained, it is not clear whether the model parameters are shared. Is \Theta in Eq.(9) used in Eq.(10)?

Quality: I have serious concern about the motivation of the work and thus feel the quality of the proposed method and experimental results is questionable.

Clarity: The incremental idea is not hard to follow.

Significance: Very little impact. There was not theoretical analysis that proved that the structural information about overlapping neighbors would be hardly learned by the existing GNN.

*** The authors have clarified all of the points with either new results or explanations in the multi-rounds discussion. No matter the work is accepted or further reviewed, the authors are highly encouraged to add the new results and explanations into the paper. ***

limitations_and_societal_impact: Not included or discussed in the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes to use simple functions learned from the adjacency matrix of a graph to boost the performance of GNNs. This overcomes the problem of using traditional heuristics which are effective but must be computed manually. The proposed approach is simple and the experiments over the quite challenging datasets of the OGB show that it is rather effective. I have some concerns regarding the latter which is why my current score is only slightly below the threshold, but maybe the authors can resolve those.
main_review: (+)

- The proposed approach is simple but effective which is quite nice. It is so simple that I wonder if there is existing work which the authors and I are missing, but maybe the other reviewers can confirm that this is not the case.

- Generally, the paper is well-written and I have few to criticise. The approach is described in detail, related work is covered, and the experiments are overall thorough. In particular, the latter show that their learned functions correlate with well-known traditional heuristics.

(-)

- To me, it is not clear why the authors use a GNN for learning from the features. In particular, they argument a lot that GNNs fail to learn the structure (which is a strong claim btw), so why use a GNN at all and not a simple MLP?

- The SAGE number reported in the table is worse than the one reported in the OGB paper. Did you try with the parameters they use there? There is further GraphSAGE+anchor distance on the leaderboard, whose ogbl-ddi score (0.8239) is considerably better than the one for NeoGNN. And it is quite related given that it also considers a structural feature.

- 260: "Neo-GNNs (w/o GCN) still show the state-of-the-art performances compared to baselines except OGB-DDI. Note that Neo-GNNs (w/o GCN) only use graph structures and outperform other GNNs whereas other GNNs use both input features and graph structures.." -- To the best of my knowledge, it is the DDI dataset that does not contain node features, but uses randomly initialized ones. In this regard, I wonder about the conclusion of the authors. To me it seems that the other GNNs obviously manage to use the structure to make something out of the random initial features.

- I do not think it is fair to fix the numbers of GNN layers to 3. Especially over these OGB datasets, my personal experience shows that they work often better with several more layers. And at least JK-Net should be able to achieve good scores (while others might suffer from over-smoothing). Did you get similar scores with more layers?

-------------------------------
Questions & Smaller Comments
-------------------------------

- Figure 2: Did you check if the trends are similar on the other datasets?
- Which L is used in Figure 2b?
- 107: s does not necessarily have to be a similarity function 
- 166: Do you really count the number of neighbours here?
- 169ff: Is this just additional information or important in some regard. To me, the remark is somehow confusing.
- 199: You mean multiple edge types? (edges of course)
- I think the LINK model from Zheleva and Getoor ("To join or not to join: The illusion of privacy in social networks with mixed public and private user profiles", 2009) would be worth mentioning as related work.

-------------------------------
edit: I adapted the score based on the responses in the rebuttal
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a neighborhood-overlap-aware GNN for link prediction. Traditional GNNs cannot detect the overlap of two nodes when combining the two embeddings as a link representation, which is crucial for link prediction since many successful heuristics such as common neighbor relies on such overlap measure. SEAL leveraging a distance-based node labeling solves this problem (detecting overlap and correlation between two nodes), yet requires extracting a subgraph for each target link thus is computationally more expensive than traditional GNNs. This paper tackles the problem by explicitly combining a learnable overlap measurement function (to simulate overlap-based heuristics) and a traditional GNN (to learn node features), and achieves highly competitive performance with SEAL and outperforms heuristic methods.
main_review: Originality: The proposed method can learn node overlapping, which is not feasible in traditional GNNs. It also avoids SEAL's subgraph extraction step, thus is more efficient. The combination of a learnable neighborhood overlap function and a GNN is novel, and works well on the link prediction problem over several OGB datasets.

Quality: The paper is technically sound. The techniques are simple and effective.

Clarity: The paper is generally well written. However, there are several mistakes and inaccuracies in the statements. 1) "SEAL requires inefficient computational cost to manually measure the relative distance for each target node pair and still shows limited performance compared to heuristic methods". This is not true. SEAL outperforms almost all heuristics in its original paper, and the bottleneck of SEAL's computation is applying a GNN independently to each extracted subgraph. The distance calculation is negligible. 2) "However, there is a limitation of the expressive power that is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. That is, some subgraphs are indistinguishable if they are symmetric or isomorphic" This is wrong. We **want** isomorphic subgraphs to be indistinguishable by GNNs. However, some non-isomorphic graphs indistinguishable by 1-WL are also indistinguishable by GNNs lead to the expressivity bottleneck. 3) "Random walk-based embedding methods such as Deepwalk [37], LINE [38], and node2vec [39] ..." LINE is not based on random walk, but first and second-order neighborhood. 4) "Note that conventional GNNs cannot compute this score due to two reasons: the normalized adjacency matrix and the low dimension of hidden representations." This is not true. Conventional GNNs cannot compute the overlap because they independently learn two nodes' neighborhood without modeling their correlations. See [1]. You may perform an experiment replacing the normalized adjacency matrix with unnormalized one in conventional GNNs and increase the hidden representations to verify whether the statement is correct. 5) Eq (8) is not an "aggregation" of neighbor features (although it looks like). It is simply lifting the node features to the corresponding edges. I would not call this an aggregation.

Significance: This paper illustrates the importance of detecting overlap in link prediction, which is significant.

[1] Zhang, M., Li, P., Xia, Y., Wang, K., & Jin, L. (2020). Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010.16103.
limitations_and_societal_impact: One potential concern is that overlap-based heuristics are only one specific type of successful heuristics for link prediction. There are other types of heuristics such as PPR, preferential attachment, etc, which are not based on overlaps. The proposed method generally cannot learn such heuristics in my opinion. I suggest doing another set of experiments on the traditional link prediction datasets used in the SEAL paper to demonstrate the limitation of the proposed method for learning general heuristics. It may be the case that the OGB datasets happen to be very suitable for overlap-based heuristics. I suggest pointing out when the proposed method works well and when it does not.

I give a weak accept conditioned that the authors can address the "Clarity" in the main review and discuss the limitation of the proposed method. I will increase my score accordingly if the authors well address these concerns.
review_title: null

Meta-review: The paper proposes a novel GNN architecture for link prediction based on neighbourhood overlap. 
The authors provided a detailed rebuttal including additional experimental results requested by the reviewers. There has been an extensive follow-up discussion. While doubts remain about clarity of the presentation, the AC believe this can be improved in the final version according to the discussion with the reviewers and their recommendations. We recommend accepting the paper.  
Decision: Accept (Poster)