Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyses the roles of virtual nodes in the link prediction problem. 
Extensive experiments are conducted to support the claims and show that virtual nodes can improve the link prediction performance of GNN.
main_review: Strengths:

1. I agree with the paper that virtual nodes lack a better understanding. It is good to see that extensive experiments are conducted to evaluate several virtual node strategies and GNN-CM can improve performance in many cases.
2. The paper theoretically analyses the effect of virtual nodes on influence distributions 

Concerns:

I'm particularly interested in how to decide the number of virtual nodes because it is important for practical use.
In Table 6 in the appendix, GNN-CM uses a high number of virtual nodes, but in Figure 3 the trend seems different.
In Figure 3, on ddi, GNN-CM with 2 virtual nodes works the best.
Is there any practical guidance?

By the way, some sentences need to be checked. For example, at the beginning of section 4, "......a relationship that might strongly influenced depend on surrounding relations"
summary_of_the_review: A good paper with theoretical analysis and extensive experiments
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper investigates using virtual nodes in graph neural networks for link prediction. Specifically, the authors use a graph clustering algorithm to determine groups of nodes in the graph and adopt multiple virtual nodes in the graph for the link prediction senario. They also theoretically investigate the effect of using virtual nodes for link prediction. Experiments conducted on six datasets  provide insights and guidelines about using virtual nodes for link prediction.  


main_review: Strengths
- Unlike most of the proposed methods for GNN focusing on node classification or graph-level tasks, the idea of ​​applying the concept of virtual nodes to link prediction is novel and interesting.
- The authors show the relationship between the proposed method and the distance encoding and labeling trick, which are popular techniques for link prediction.
- The authors theoretically analyze the effectiveness of virtual nodes in terms of influence scores.

Weakness of the paper:
- The motivation of using virtual nodes for link prediction is not clear. The authors only argue that the fact that virtual nodes have not been studied in link prediction is because the large and heterogeneous graphs in link prediction are of very different nature, but do not clearly explain why virtual nodes are important for link prediction.
- Even though the authors provide first guidelines about using virtual nodes for link prediction, experimental results are marginal or even worse compared to the results of GNNs w/o virtual nodes. Even in the ddi dataset, which showed great improvement, there is little difference from the model using distance encoding. The authors should show a more significant performance improvement or clearly show problems that using virtual nodes only addresses. 

summary_of_the_review: I feel that the paper gives an interesting direction to consider virtual nodes for link prediction, but the motivation is unclear and experimental results are insufficient.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors revisited the commonly used trick of virtual nodes in graph learning. The authors proposed the multiple virtual nodes usage under the link prediction scenario and provided both theoretical and empirical supports for it. For theoretical analysis, the authors consider the influence score for m-regular graph and expressiveness of link representation (by concatenating representation of two nodes) in a special case and non-attributed graphs. For empirical analysis, the authors compare the performance of multiple virtual nodes setting to only one node setting with different GNN strategies and different datasets. They finally conclude that the virtual nodes can stably improve base GNN performance on some challenging link prediction tasks.
main_review: Strength:
1.	By the authors’ claim, this is the first work to employ virtual nodes to improve the link prediction tasks.
2.	Virtual nodes are well motivated to capture long-distance / under-reaching messages between nodes. The authors provide both theoretical and empirical analysis for the virtual node setting.
Weakness/concerns:
1.	The theoretical analysis is limited to regular graph for influence score and non-attribute graph for expressiveness of link representation. Could them be generalized to more applicable graphs? 
2.	The authors concatenate node representation as link representation. In this way, the expressiveness of link representation is highly related to the expressiveness of node representation. Therefore, it seems powerful GNNs for node representation or node classification can be directly used for link representation or link prediction. But it seems that P-GNN conflicts with this claim as the performance of P-GNN is really bad though the authors mention some concerns about it in supplements.
3.	As the experimental results show, virtual nodes do not always benefit the link prediction, such as on Cora and Pubmed. Although the authors give some analysis, readers may still be confused about in what situations virtual nodes are recommended and vice versa. I would appreciate if the authors can give a table to further explain on it, especially clarify ambiguous expression in the article. For example, what “cora/pubmed have no cluster structure” means, when both Cora and Pubmed have clearly defined classes and previous works have shown that their data points have underlying clusters.
4.	The proposed method seems to rely heavily on sophisticated hyperparameter searching. (as shown in Appendix D)

summary_of_the_review: The authors present much interesting and insightful analysis for virtual nodes on both theoretical and empirical sides. But there are also many concerns on both two sides which should be well addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to enhance the link prediction performance of GNNs by adding multiple virtual nodes. The vortual nodes are designed in different ways, and the experiments analyze the influence of adding virtual nodes from different perspectives. 


main_review: Overall, the paper is well written and the proposed methods are clearly explained and are easy to understand. And the experiments covers several different perspectives of the influence of the virtual nodes. Everything is clearly introduced and I do not have any question regarding the proposed model.

However, the contribution of the paper is mainly from the relatively narrow engineering perspective (a technique to improve the performance) without much conceptual or theoretical insights. It analyze the very specific problem of adding virtual nodes to enhance the link prediction performance. Besides, the designs of different virtual nodes are a little bit ad-hoc. Therefore, the studies on problem of whether virtual nodes will help link prediction seem not systematic enough.


----------post rebuttal----------

After rebuttal, the authors explained the rationale behind using virtual nodes for link prediction to some extend. Although there is still large sapce for improvement on the analysis proposed in the paper, the attempt on analyzing virtual nodes' influence on link prediction may catch some attention and interests from the community. Therefore, I think the paper can be rated as 'marginally above the threshold'.
summary_of_the_review: Contribution is limited, as explained in the main review, and I think it is not enough to be accepted.
review_title: null

Meta-review: This paper considers GNNs for link-prediction (predicting which links are likely to appear next). An idea that has been used before is to add virtual nodes to improve the ``under-reaching” problem in shallow GNNs; this paper considers this systematically in the context of link prediction. Specifically, one approach developed is to cluster the graph into clusters C(i), I = 1, 2, …, k for some k and to add a virtual node u(i) for each index i, which is made adjacent to each node in C(i). This can ease information exchange, particularly in message-passing GNNs. 

Link prediction is an important problem. However, there seem to be at least three issues with this work: the performance gains obtained are not strong enough, it is not conceptually clear why virtual nodes should help with link prediction, and the analysis is quite a bit about repeating existing analyses on nodes alone. I recommend the authors to address these issues thoroughly in the next version of the paper.
Decision: Reject