Revisiting Virtual Nodes in Graph Neural Networks for Link Prediction
Authors: EunJeong Hwang
Veronika Thost
Shib Sankar Dasgupta
Tengfei Ma
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural network
link prediction
virtual node

Abstract: It is well known that the graph classification performance of graph neural networks often improves by adding an artificial virtual node to the graphs, which is connected to all nodes in the graph. Intuitively, the virtual node provides a shortcut for message passing between nodes along the graph edges. Surprisingly, the impact of virtual nodes with other problems is still an open research question. 

In this paper, we adapt the concept of virtual nodes to the link prediction scenario, where we usually have much larger, often dense, and more heterogeneous graphs. In particular, we use multiple virtual nodes per graph and graph-based clustering to determine the connections to the graph nodes. We also investigate alternative clustering approaches (e.g., random or more advanced) and compare to the original model with a single virtual node. We conducted extensive experiments over different datasets of the Open Graph Benchmark (OGB) and analyze the results in detail. We show that our virtual node extensions yield rather stable performance increases and allow standard graph neural networks to compete with complex state-of-the-art models, as well as with the models leading the OGB leaderboards.

Under review as a conference paper at ICLR 2022
REVISITING VIRTUAL NODES IN GRAPH NEURAL NETWORKS FOR LINK PREDICTION
Anonymous authors Paper under double-blind review
ABSTRACT
It is well known that the graph classification performance of graph neural networks often improves by adding an artificial virtual node the graphs, which is connected to all nodes in the graph. Intuitively, the virtual node provides a shortcut for message passing between nodes along the graph edges. Surprisingly, the impact of virtual nodes with other problems is still an open research question.
In this paper, we adapt the concept of virtual nodes to the link prediction scenario, where we usually have much larger, often dense, and more heterogeneous graphs. In particular, to determine the connections to the graph nodes. We also investigate alternative clustering approaches (e.g., random or more advanced) and compare to the original model with a single virtual node. We conducted extensive experiments over different datasets of the Open Graph Benchmark (OGB) and analyze the results in detail. We show that our virtual node extensions yield rather stable performance increases and allow standard graph neural networks to compete with complex state-of- titte-of-hheaaad fi-the-art art models, as well as with the models leading the OGB leaderboards.
multiple virtual nodes per graph and graph- based clustering
INTRODUCTION
Link prediction is an important task to complete graphs that are missing edges in various domains:
citation networks (Kipf & Welling, 2016), social networks (Adamic & Adar 2003). medical drug interaction graphs (Abbas et al. (022). or knowledge graphs (KGs) (Ji et al.) [021]. Numerous kinds of models have been proposed to solve the link prediction problem, ranging from KG-specific predictors (Ji et al., 2021) to graph neural networks (GNNs) (Kipf & Welling 2016 /Zhang & Chen 2018). Over dense biomedical networks, GNNs turned out to work especially well (Hu et al. 2000)).
In this work, we focus on graph neural networks for link prediction. Many of the popular GNNs are based on the message-passing scheme, which computes node embeddings based on iteratively aggregating the features of (usually direct/one-hop) neighbor nodes along the graph edges (Gilmer eet al. 2017). Interestingly, best performance is usually obtained by only considering two three hops of neighbors (i.c., 2-3 layers in the GNN). One main reason identified for this is pversmoothing, the problem that node representations become indistinguishable when the number of layers increases (Li wwweeeentialllggowiiiio
et al. 2018). The connected to capturing long-range dependencies (Alon & Yahav 2021). While it likely that link prediction most often depends on the local node neighborhood. it is not beyond imagination that there are critical long-range dependencies (e.g., complex chains of drug-drug drug-protein interactions). Hence, using a small number of layers to overcome the above problems results in under-reaching.
amount of information has also been suggested as one issue
There have been several recent proposals overcome under-reaching. On the one hand, several works propose techniques that allow for larger numbers of GNN layers (Xu et al. 2018) Wu et al.) 2019: (019:Li) Liu
al. 2020 Chen al., 2020), Sun et al., 2021 Zhou et al. 2020 et al. 2020a). However, although (Chen et al. 2020) show that smoo-hhgg happens particularly in dense graphs, the link prediction experiments in these works consider citation or recommendation networks, but not the especially dense biomedical ones. And our experiments over the latter suggest that the reported results are not generalizable to the more challenging biomedical data. On the other hand, there are approaches that adapt the pesssage-passingg scheme to consider neighbors beyond the one-hop neighborhood: based on graph diffusion (Atwood & Towsley 2016 Klicpera et al. 2019a] Abu-El- Aibu-Ei-Haij et al.
2019 Xu Ma et al. 2020 Klicpera et al. 2019b) and other theories (Morris et al.
et al. 2019a
2019 You

---

Under review as a conference paper at ICLR 2022
et al. 2019). However, most of these models are relatively complex and, in fact, in our experiments over the challenging graphs from the Open Graph Benchmark (OGB) (Hu et al. 2020). several ran out of memory. Moreover, the majority has not considered link prediction, while this problem was recently shown to be more difficult than node classification (Zhang et al. 2020).
In this paper, propose simple but elegant solu- tion to under-reaching based on the concept of virtual
nodes (Gilmer et al. 2017 Li et al. 2017 Pham et al. 2017; Ishiguro et al. 2019). Virtual nodes are well known to often improve the graph classifi- cation performance of graph neural networks, where an artificial virtual node is added to every graph and connected to all nodes in the graph. While the virtual nodes were originally thought as representations of the entire graph, they also provide shortcuts for mes- sage passing between nodes along the graph edges. Surprisingly, the impact of virtual nodes for the link prediction problem has not been investigated yet. The reason for this might be that the often very large and heterogeneous "network" graphs in link prediction are very different nature and require novel/adapted solutions (c.g., . protein interaction network may cas- ily contain millions of nodes, whereas a molecule be classified contains usually less than fifty).
Figure 1: We cluster graph nodes belonging together (gray shades) and connect them to common virtual node (blue). This eases information exchange and hence prediction of links between nodes not directly related (red).
We explore application and effects of virtual nodes in link prediction theoretically and empirically:
We propose to use multiple virtual nodes in the link prediction scenario and describe a praph-based technique to connect them to the graph nodes. Consider Figure II In a nutshell, we use graph clustering algorithm to determine groups of nodes in the graph that belong together and then connect these nodes to a common virtual node. this way, under-reaching decreased because clustered nodes can share information easily; at the same time, the nodes are spared of unnecessary information from unrelated nodes (i.e., in contrast to the single virtual node model).
We also investigate alternative methods to determine the virtual node connections (e.g., randomiza- tion in clustering) and compare to the original model with a single virtual node.
We theoretically investigate the benefit of using (multiple) virtual nodes in terms of two aspects: influence score and the expressiveness learning a structural link representation.
We conducted extensive experiments over challenging datasets of different type, provide ablation studies that confirm the superiority of our proposed techniques, analyze the results in detail, and provide first guidelines about how to use virtual nodes with different types data and GNNs. Most importantly, we show that our virtual node extensions most often yield rather stable perfor- mance increases and allow standard GNNs to compete with complex satte-of-the-eee models that also try to improve message passing, well with the models leading the OGB leaderboards.
2 RELATED WORK
We give an overview on approaches that are similar from technical perspective; for more detailed summary, see Appendix A For a more general overview of the large and diverse field of link prediction, we refer to good summaries in recent works (Martinez et al. 2016 Zhang et al. 2020).
Deeper GNNs. Several techniques address omor-smo and hence allow for constructing deeper GNNs to solve under-reaching. These models range from the simple but efficient message propagation in SGC (Wu et al. [2019] Liu et al. (020)) and APPNP (Klicpera et al., 2019a) and connections in JKNet (Xu et al. 2018), to more advanced proposals (Chen et al. 2020 Sun et al. 202 Zhou et al. 2020; Li et al. 2020a) such as the differentiable aggregation functions in DeeperGCN (Li et al. 2020a). However, although (Chen et al.) 2020) show that over omor-smoothing happens particularly in dense graphs, the experiments in most of these works consider citation or recommendation networks, but not the especially dense and important biomedical ones. And our experiments over the latter suggest that the reported results are not generalizable to the more challenging biomedical data.
2

---

Under review as a conference paper at ICLR 2022
Beyond One-Hop Neighbors. Recently, graph diffusion methods used in various ways to determine the message targets and thus extend standard message passing beyond the one-hop neigh- borhood. AAwoodd & Towsley (2016) use k-hop random walks to extend the node features. APPNP (Klicpera et al. 2019a) applies personalized PageRank to propagate the node predictions generated by neural network. Other models concatenate (Abu-El-Haija et al., (019) or aggregate (Xu et al.) 2019a Ma et al., 2020) node embeddings in every layer using a diffusion-bart
transition matrix. The diffusion-based graph neural network (GDC) (Kliepera et al. 2019b) aggregates information from multiple neighborhood hops at each layer by sparsifying a generalized form of graph diffusion.
Subsequent works use diffusion methods on multiple scales (Liao et al., 2019 Luan et al. 2019]
Xhonneux et al., 2020) and attention (Wang et al. 2020). Morris et al. (201)) take higher-order graph structures at multiple scales into account during message passing based on the k-dimensional Weisfeiler and Leman graph algorithm. All the above approaches are relatively complex, many terminated with memory errors in our experiments, and few have been evaluated for link prediction.
Virtual Nodes. To the best of our knowledge, virtual nodes have only been considered in the context of graph classification so far, where a single virtual node (also called supernode) is added to the graph to be classified and connected to all graph nodes (Gimmer et al. 2017 Li et al. 2017: Pham et al., 2017] Ishiguro et al., (211)). Note that the original idea was to compute graph embedding in parallel with the node embeddings and even connected the virtual node only in one direction (i.e, via edges from the graph nodes) instead of bidirectionally (Li et al. 2017).
There are some GNNs which point out special nodes that could consider as "virtual". Fey iet al. (2020) propose a GNN for molecule graph classification which clusters certain nodes within molecule using a structure-based, molecule-specific algorithm and then applies message passing
within and between these clusters. The graph-partition based message passing from Liao et al. (2018) also used clustering, but it just divides the original messages into inter- and intra-cluster. Our approach creates new "paths" in the graph and we theoretically demonstrate its expressiveness. P-GNN (You jet al., 2019) assigns nodes to random clusters ("anchor-sets") and then creates a message for each node for every anchor-set, while ignoring the message passing from original direct neighbors. Our virtual nodes represent an alternative means to aggregate messages from multiple graph nodes which not necessarily direct neighbors. We also explore the idea of similar random assignments in our context, but show that more elaborate techniques generally work better. Most importantly, we do not propose specific, new GNN but new technique for augmenting existing graph neural networks.
Although it a well- knlwn trick, the advantage of using virtual nodes has never been theoretically in- vestigated nor fully understood. We focus link prediction and considerably extend the virtual node technique. There are commonalities in the advantages of using virtual nodes for graph classification and link prediction, but their role in link prediction is improve the representation of the link instead of the graph (nodes). We analyze theoretically and empirically how they improve GNN performance.
3 PRELIMINARIES
Link Prediction. We consider an undirected graph G = (V, with nodes V and edges E VV.. Note that this basic choice is only for ease of presentation. All our techniques work for directed graphs and, with simple adaptation, also for graphs with labelled edges. We assume V to be ordered and may refer to a node by its index in V. For node v E A. denotes the set of its neighbors. Given two nodes, the link prediction task is to predict whether there is a link between them.
Message-Passing Graph Neural Networks. In this paper, we usually use the term graph neural networks (GNNs) to denote GNNs that use message passing as described by Gilmer et al. (017). These networks compute for every V V a node representation h layer ? 11, RJ. by aggregating its neighbor nodes based on generic aggregation function and then combine the obtained vector with h as below; N. are the initial node features.
h COMBINE' (N.-1, ( AGGREGATEE (1 | N.)))
(1)
Link prediction with GNNs is usually done by combining (e.g., concatenating) the final representations h/, he,, of the nodes u, e under consideration and passing them through several ferd-forward layers with a final sigmoid function for scoring. We follow this approach.
We further use [1, n] to denote interval [1,2.... n].
3

---

Under review as a conference paper at ICLR 2022
4 VIRTUAL NODES IN GRAPH NEURAL NETWORKS FOR LINK PREDICTION
So far, virtual nodes have been only used for graph classification. Link prediction scenarios are different in that the graphs are usually very large, heterogeneous, sometimes dense, and the task is to predict a relationship that might strongly be influenced depending on surrounding relations. In the following, propose approaches that fit these scenarios.
4.1 MULTIPLE VIRTUAL NODES
Our main goal of using virtual nodes is to provide shortcut for sharing information between the graph nodes. However, the amount of information in graph with possibly millions of nodes enormous, and likely too much to be captured in a single virtual node embedding. Further, not all information is equally relevant all nodes. Therefore we suggest to use multiple virtual nodes S = {si, $2 ..... Sp 1 each being connected to a subset of graph nodes, as determined by an assignment : V - [1, nl; considered as hyperparameter. We propose different methods to obtain a:
Random (GNN-RM). Most simple, we can determine a fixed randomly once with initialization.
Increased Randomness (GNN-RMF). Similarly random assignment, but initialized with every forward pass. In this way, a single bad assignment does not determine the overall performance.
Clustering (GNN-CM). Many types of graph data incorporate certain cluster structure (e.g.. collaboration or social networks) that reflects which nodes belong closely together. We propose to connect such nodes cluster to a common virtual node, such that the structure inherent to the given graph is reflected in virtual node assignment More precisely, during initialization, use a generic clustering algorithm which, given a number m, creates a set C' = {C₁, C2...... ..... Cm of clusters (i.e., sets of graph nodes) by computing assignment p V + [1, m]. assigning each graph node to a cluster. We then obtain a by choosing m = n and o = p.
In this work, we decided for the METIS clustering (Karypis & Kumar 1998) which turned out to provide a good trade off between quality and efficiency. Nevertheless, our idea is generic and can be applied with arbitrary algorithms. We will show ablation experiments for alternatives (e.g., Graclus (Dhillon et al.) 2007) and Diffpool (Ying et al. 20185)).
Advanced Clustering (GNN-CM*). Not every type of graph data contains inherent cluster structure or one that is sufficiently expressed. Furthermore, using a fixed clustering, we obtain a deterministic algorithm again taking the risk that we completely rely on single, possibly not ideal, virtual node assignment there may be critical long range dependencies that go beyond clusters. For these cases, we propose an alternative approach, which breaks up the determinism by extending the above clustering as follows. We choose a relatively large m, with >>> n, and apply the above clustering algorithm, during initialization. Then, each epoch, we randomly guess an assignment
a': ml] + [1, ni of clusters to virtual nodes and define (n) == o (p(r))). Note that this approach is inspired by Chiang et al. (2019). who apply a similar technique is to create batches based on clusters. Further note that we determine o' with every epoch instead of every forward pass since the the computation takes quite some time on large datasets and we observed that this yields good results.
4.2 THE MODEL
We integrate the multiple virtual nodes into generic cessage-passingg graph neural network by extending the approach from Hu et al. (2020) to the setting with multiple virtual nodes, by computing node representations hy for node v V at layer E' as follows:
h
5; = COMBINE' VN (hE-1, AGGREGATE (1A5-1 1 V, =
(2)
h = COMBINE' (n5-1 + AGGREGATE'S ((NC | (uEN)))
(3)
Note that the highlighted adaptation of the standard GNN processing from Equation ① is only minor but powerful. In our implementation, COMBINE is addition combined with linear layers and layer normalization, and we use sum for AGGREGATE VN-
Since notation V is standard for nodes, use for the set of virtual nodes. Think of "supermodes".
4

---

Under review as a conference paper at ICLR 2022
4.3 ANALYSIS: VIRTUAL NODES CHANGE INFLUENCE
Influence Score. Following (Xu et al. 2018 Kliepera et al. 2019a). we measure the sensitivity (also, influence) of node a to a node y by the influence score (x. y)
e Oh akd is a vector of all ones, For k-layer GNN, the influence score is known to be proportional in expectation to the k-step random walk distribution from z to y
he is the embedding of x at the 4 layer, see Equations ①1 and (3)
[[I v)) & Prw (x - y, = Σ II
(4)
FR t= deg(ot)
(vg, 04y ..., eft are the nodes the path r from x == ug to to = off. R² the set of paths of length In what follows, we will exploit this relationship and argument in terms of the probability Prw-
Virtual Nodes. For simplicity, consider the influence score an m-regular graph; there we have Prw y, k) | I
m We hypothesize that we can come to similar conclusions in general graph with average degree m. Consider the message passing between two distant nodes x and y. (I) In case the shortest path from Prus (z + y; k) is obviously zero. we then consider virtual nodes the GNN layer (even with only one), can pass messages from to y through the virtual nodes and obtain nonzero probability. (II) Consider the case where there is a shortest path of length & between x and y. By adding a virtual node in one GNN layer, the probability changes to:
y is of length >> k, a k-layer GNN cannot capture it, and the probability
| (m 1)*
Pnp (r + k) = Prw (2 + y. k) + Prw + s,
+,, v)
+
(5)
(m + 1)[VI'
Compared to the original probability, we get the following impact ratio for using virtual nodes:
m (m 1)& +
m
ir
(6)
(m + 1)]
When m is large enough, ir can be approximated by 1 of virtual nodes grows when increases. Our experiments confirm this theoretical observation.
A-1 V
Here, we see that the impact
Multiple Virtual Nodes. In view of multiple virtual nodes, the above analysis gets even more appealing. We continue along these lines and assume there is a shortest path of length < k between and y. x and y connect to the same virtual node s. then Equation (5) changes as follows:
|
ss Pro (Ic + y, (m + 1)
(m + 1)|Cal
Since the set C. of nodes connecting to 8 much smaller than V, the impact of multiple virtual nodes is greater than that of single virtual node. On the other hand, if x and y do not connect to the same virtual node, the probability just slightly decreases from R8" m=
[A*
(m+1yr
In Appendix B we further show that using multiple virtual nodes is related to (but not equal to) the labeling trick (Zhang et al. 2020) and distance encoding (Li et al. 2020b), and it can theoretically improve the expressiveness learning structural link representations (see Theorem and Figure 4(b)).
5 EVALUATION
We conducted extensive experiments and ablation studies to empirically investigate:
How does the existing approach with one virtual node perform in link prediction?
Do multiple virtual nodes improve performance, how do our proposed approaches compare?
particular, are approaches based on the graph structure better?
How exactly do virtual nodes support link prediction? When do they help particularly?
SSee Theorem in (Xu et al. 2018 Note that the theorem makes some simplifying assumptions (e.g.. on
the shape of GNN).
5

---

Under review as a conference paper at ICLR 2022
Table 1: Data, All graphs are undirected, have edge features, and all but ddi have node features.
#Nodes
#Edges
Average Node Deg.
Average Clust. Coeff.
MaxSCC Ratio
Graph Diameter
ddi 4,267
1,334,889
500.5
0.514
1.000
5
ppa10
509,860
11,217,535
8.3
0.019
0.983
29
pubmed 19,717
88,648
4.5
0.046
0,992
20
collab
235,868
1,285,465
8.2
0.729
0.987
23
Table 2: GCN, SAGE, and GIN with different virtual node configurations over different graph-data types/amounts; (second) best results are (light) gray
overall best bold, second best underlined.
ddi Hits @ 20
ppal0 Hits@ 100
collab 50
pubmed Hits 20
GCN
0.4076 + 0.1073
0.1313 = 0.0084
0.4955 = 0.0064
0.9675 + 0.0143
VN
0.6217 0.1241
0.1258 = 0.0082
0.5049 = 0.0088
0.9579 + 0.0214
RM
=55322#0112
0.1205 = 0.0059
0.5083 0.0109
0.9522 : 0.0110
RM
0.5830 + 0.0855
0.1116 + 0.0094
0.5046 + 0.0049
0.8100 + 0.0781
CM
0.6105 0.1563
0.1299 + 0.0050
0.5181 0.0076
0.9575 0.0230
CM+
0.6033 + 0.1759
0.1399 + 0.0071
0.5128 + 0.0129
0.9189 + 0.0514
SAGE
0.6173 + 0.1068
0.1024 +: 0.0050
0.5662 +: 0.0149
0.9779 0.0105
VN
0.6491 + 0.1360
0.0853 + 0.0154
0.5875 + 0.0091
0.9659 + 0.0333
RM
0.7068 = 0.1174
0.1131 = 0.0039
0.5830 = 0.0087
0.9433 0.0208
RM
0.7564 + 0.1055
0.1105 = 0.0023
0.6067 = 0.0063
0.9800 + 0.0087
CM
0.7621 0.1157
0.1077 = 0.0150
0.6056 + 0.0105
0.9834 0.0068
CM+
0.8251 + 0.0678
0.0963 = 0.0099
0.5940 0.0262
0.9754 + 0.0139
GIN
0.4321
0.1353
0.1139 = 0.0058
0.5768 0.0179
0.9234 0.0166
VN
0.5260 + 0.1227
0.1316 = 0.0049
0.5863 - 0.0254
0.9790 + 0,0070
RM
0.5084 0.1324
0.1337 # 0.0045
0.5412 + 0.0174
0.9604 0.0158
RM
0.5310 + 0.1453
0.1269 + 0.0026
0.5335 + 0.0087
0.7986 + 0.0993
CM
0.5664 + 0.0860
0,1349 = 0.0034
0.5821 - 0.0081
0.9125 + 0.0378
CM+
0.4339 + 0.1855
0.0069 0.1591
0.5557 0.0026
0.9037 0.0262
Datasets. We focused on challenging data from the OGB: ddi. drug-drug interaction network; ppal0, subset of the protein proteen association network ppa containing only 10% of the train edges (but full valid/test); and collab, an author collaboration network. To learn more about smaller data of similar type, we also tested on the citation networks pubmed (Yang et al. (016). Since the datasets are not only very different in type but also in various other critical graph parameters and this reflected in the performance the models, we show relevant statistics in Table i The datasets vary strongly in size with ddi being smallest among the biomedical; on the other hand, ddi is very dense. The clustering coefficient intuitively reflects the "cliquishness" of the graph 's subgraphs. The large diameters suggest that the data suits testing under-reaching. Appendix C gives further details and describes datsets we consider in additional experiments in the appendix.
Baselines For competitive comparison, considered important baselines (described in Section 2):
The deep GNNs SGC, APPNP, DeeperGCN, and two variants of JKNet.
Approaches extending message passing: P-GNN, APPNP, GCN-GDC. SAGE-GDC, GIN-GDC.
The popular GNNs GCN (Kipf & Welling, 2017), SAGE (Hamilton et al. 2017). and GIN (Xu et al. 2019b), which then extend with (multiple) virtual nodes.
Seee Tables 2 and 3 in Hu et al. 2020 We computed the numbers for ppal0 10 (which focus on due to lack of resources), and pubmed using the techniques.

---

Under review as a conference paper at ICLR 2022
Table 3: Comparison to SOTA; top: state of the art (two best per dataset) according to OGB leaderboard (10/3/21), leaderboard results are marked by "; middle: models with similar goal to our approach ("-": ran out of memory); bottom: best of virtual-node augmented GNNs we tested.
ddi
collab Hits Hits@50
Hits 20
SAGE tattr
0.8781 0.0474
n/a
SAGE +dist."
0.8239 + 0.0437
n/a 0.6548 + 0.0000
Adamic Adar+*
0.1861 = 0.0000
SEAL*
0.3056 + 0.0386
0.6474 + 0.0043
DeeperGCN
n/a 0.6056 + 0.0869
0.6187 + 0.0045
GCN+JKNet"
n/a 0.4635 + 0.0197
SGC
0.0676 + 0.0586
P-GNN
0.1050 = 0.0000
APPNP
0.1492 = 0.0298
0.3185 + 0.0205
GCN-GDC
0.2550 + 0.1242
SAGE-GDC
0.3141 0.1254
GIN-GDC
0.2180 + 0.0786
SAGE
0.6173 = 0.1068
0.5516 + 0.0171
SAGE-CM+/M
0.8251 + 0.0678
0.6017 + 0.0137
5.1 RESULTS
Overall Impact of Virtual Nodes, Tables 2. 7 S (Appendix). We compare to GCN, SAGE, and GIN. The common approach of using a single virtual node (GNN-VN) yields good improvements over ddi, slight improvements over collab, but no definitive ones over ppal 0; over pubmed, it works very well for GIN. The numbers for GNN-RM and GNN-RM reflect the randomness of their connections to the virtual nodes, there is no clear trend. Nevertheless, they clearly outperform the original models, with only few exceptions. The increased randomness by re-assigning the virtual nodes with every forward pass (GNN-RM*) seemingly suits SAGE but not the others. As expected, over the small pubmed/cora, which also have no cluster structure, the results are not consistent or convincing overall; virtual nodes only yield improvement sometimes, and none for GCN. Yet, on the more challenging datasets, multiple virtual nodes turn out to be an efficient means to boost the link prediction performance of GNNs if they are applied correctly. Our virtual node connections based on the graph structure (GNN-CM) yield consistently good improvements over ddi and col lab, and mostly help on the challenging ppal0 0 dataset. On col collab, we did further experiments using GAT (Veličković et al. (017) and also observe a clear performance gain: 0.4745 vs. 0.5876 (GAT-CM). GNN-CM and GNN-CM* are not always the best ones, but yield reliably good results, in contrast to the other models with virtual nodes (see variability of gray shades). Interestingly, the advanced clustering yields especially good performance over ppa 0/ppa, while its results on the other datasets are not convincing. Generally, the improvements of the virtual node models are strongest on ddi. For an in-depth result analysis see Section 5.2
Comparison to Related Works and SOTA, Table 3, Most deep GNNs as well as the models that use complex message-passe paaaggggassingggeeo techniques perform disappointing and, overall, much worse than the standard GNNs. We did thorough hyperparameter tuning for these models and it is hard to explain. However, most of the original evaluations focus on node or graph classification and consider very different types of data often the standard citation networks (Lu & Getoor 2003) and, in fact, collab we see the best numbers. For a more detailed discussion of P-GNN see Appendix H Even if we assume that these numbers can be improved, the models do not seem apt for link prediction; in particular, the complex ones: many do not run at all on realistic link prediction data but yield memory errors. Further, our virtual node extensions make standard GNNs competitive to the models on the leaderboard. In particular, their performance is much more stable. The results of the best models from the leaderboard vary strongly with the different datasets, or have not been reported at all. None of these models can be called "good" overall, given the numbers in the sometimes even missing. rest of the table; in fact, SEAL and Adamic Adar perform rather bad on the very dense ddi.
7

---

Under review as a conference paper at ICLR 2022
0.55
0.8
10
Hits@22
Hits@
0.6
0.5
0.4
GCN
10a
(6L)
0.2
0.45
GCN-CM
2
4
8
10
2
4
6
8
10
(CI-CM(4))
# Layers
Layers
collab
Figure 2: Performance depending on layers: @its@k and time per epoch (sec.); ddi (left), collab.
Impact of Virtual Nodes on Number of GNN Layers and Efficiency, Figure For the virtual nodes models, the scores increase with the number of layers for longer time, GCN drops earlier. On ddi, GCN- VN and -CM reach their best scores at 6 and 8 layers, respectively, which is remarkable for that very dense dataset, which is prone to over-smoothing. On collab it is the other way around. The figure also gives idea about the runtime increase with using virtual nodes. compares the 6-layer models, and shows the 4-layer GCN-CM which obtains performance similar to the 6-layer GCN-VN.
GCN-CM SAGE-CM
Hits@20
0.8
0.6
0.4
4
8
32
64
Impact of Virtual Node Number, Figure 3 First, consider the configurations of the best models for the overall results in T which provided in Table/Gjin the appendix. Here,
Hits@50
0.6
we see that the chosen numbers of virtual nodes are indeed random for the "random" models, but GNN-CM consistently uses high number of virtual nodes, which also suits it better according to our theoretical analysis in Section 4.3 In line with this, the more detailed analysis varying the numbers of virtual nodes, yields best results (also terms of standard deviations) for SAGE-CM at rather high values. For GCN, we do not see a clear trend, but (second) best performance with 64 virtual nodes. Note that there is trade off between number of virtual nodes and intra-cluster test edges, discussed in Section 5.2
0.55
0.5
2
4
8
32
64
Virtual Nodes
Figure 3: Impact of virtual node
number; ddi (top) and collab.
Using Virtual Nodes Only at the Last GNN Layer, Table Alon & Yahav 202 show that using a fully connected adjacency matrix at the last layer of a standard GNN helps to better capture information over long ranges. We therefore investigated if it is a better architectural choice to virtual nodes only at the last layer. However, we see that this can lead to extreme performance drops.
Impact of Clustering Algorithm, Table (Appendix). Our architecture is generic in the clustering algorithm, and we investigated the effects of varying that. Graclus is similar in nature to METIS in that it also creates partitions based on the adjacency matrix, but it took much longer run. Diffpool considers the node features and yields improvements for GCN, but does not scale to larger datasets. Over ddi, there is no clear winner and, given its efficiency, METIS turns out to be good solution.
Table 4: Comparison of using the virtual nodes at every and only at the last layer; Hits @ 20, ddi.
GCN
SAGE
GIN
w/o virtual nodes
0.5062 + 0.2186
0.6128 0.2122
0.4829 + 0.
VN
0.5932 = 0.2390
0.7160 + 0.1457
0.6523 = 0.0446
.VNOL
0.6180 = 0.0088
0.5167 = 0.1364
0.6472 = 0.0542
-CM
0.6322 + 0.1565
0.8819
+ 0.0341
0.6544
+ 0.0960
-CMor.
0.6338 + 0.1188
0.6151 + 0.1545
0.4420 + 0.1694
8

---

Under review as a conference paper at ICLR 2022
5.2 DISCUSSION AND CONCLUSIONS
The results show that our approach with multiple virtual nodes based on graph-based clustering yields performance increases for various GNNs and types of data, but there are clear differences.
Dense Graphs with Medium/High Clustering Coefficient. Over dd1, we see strongest improve- ments for all virtual-node models. This can be explained by our proposed theory, showing that a very large node degree m increases the impact of the virtual node(s), and thus decreases the negative impact of the (too) many other neighbors (see Equation (6 Furthermore, the empirical results
confirm our proposed theory regarding multiple virtual nodes (see Equation 77). We see particularly good numbers for GNN-CM, which exploits the clustering inherent in the given graph. GNN-CM + which considers this given clustering only on lower level, shown to perform worse than GNN-CM overall. In fact, we computed the percentage of test edges that occur in the "virtual node cluster" (see Table I1 in the appendix) and it shows that the numbers for the advanced clustering are very similar to the random one, meaning the randomly merged smaller clusters break the data's structure too much. Interestingly, the experiments show that, even with the dense data that is prone to over-smoothing, virtual nodes make the GNNs score higher with more than the standard 2-3 layers; hence virtual nodes seem to alleviate over- smoothing to some extent, an interesting question for future work.
Graphs with Large Problem Radius and Low Clustering Coefficient. Over ppa10, 0, all GNNs use an unusually high number of layers, which hints at a large problem radius (e.g., GCN, which performs especially well, uses 7 layers). Given the very low clustering of the data in addition, ppal represents a special challenge. With the multiple virtual nodes, GNN-CM performs again better than GNN-VN. On the other hand, it does not perform much better than the random models on data without cluster structure. This can be explained by its choice of number of virtual nodes, which is consistently high, but then there are less test edges within a virtual node cluster (see appendix Table TTP. We hence see here that the positive effect of having many virtual nodes (recall Equation 7 cancel out the benefits of clustering. Our advanced clustering, which merges some local clustering with randomness, is able to achieve best results with GCN and GIN (with SAGE, all models perform rather bad over ppa10). This can be explained by the fact that it randomly merges some local clusters with each epoch anew and hence allows more messages to pass across "virtual node clusters". We also did some experiments over the very large ppa, which is denser than ppal0, 0, and see a similar trend.
Sparse Graphs with Low to High Clustering Coefficient. We tested three citation/colllboratioo networks of different sizes. Note that, over this data, the problem radius is usually assumed to be rather small (Alon& & Yahav 2021), although the graph diameters are large. We investigated virtual nodes to augment link prediction in large and complex graphs; but we also want to provide insight into the behavior on smaller data. Over pubmed (similarly on cora as shown in the appendix), virtual nodes do not provide any improvement for GCN. For GIN, single virtual node yields good increases; overall, it usually outperforms the settings with multiple virtual nodes. We hypothesize that this is mainly due to the small graph size and sparsity. In fact, on the larger and denser collab, GNN-CM performs very good for all GNNs. The trends in the models' performance and the corresponding explanations are similar to those for ddi but much less expressed, probably due to the much smaller node degrees. Yet, the performance is much more stable, possibly because it is larger and not as dense.
Conclusions. We summarize our main findings to provide first guidelines for applying virtual nodes:
Small + Sparse Graphs: A single virtual node is likely to boost performance of GIN, and virtual nodes should help with SAGE, but probably not with GCN.
Large + Sparse Graphs: If there is cluster structure, GNN-CM should yield stable performance increases. If the problem radius is large or there is few cluster structure, GNN-CM+ is worth a try.
Dense Graphs Clustering: Multiple virtual nodes (i.e., GNN-CM) likely increase performance.
CONCLUSIONS
We propose simple but elegant graph neural network extension using multiple virtual nodes that may considerably increase link prediction performance. We also advance research by providing theoretical justifications the very first about applying virtual nodes at all and by showing their positive impact in various experiments. Future work includes the design of more advanced and scalable architectures, and it would be interesting to further investigate the huge performance increases on dense graphs.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Khushnood Abbas, Alireza Abbasi, Shi Dong, Ling Niu, Laihang Yu, Bolun Chen, Shi-Min Cai, and Qambar Hasan. Application of network link prediction in drug discovery. BMC bioinformatics, 22 (1):1-21, 2021.
Sami Abu-EI-Haale Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard. Kristina Lerman, Hrayr Hanutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional ar- chitectures via sparsified neighborhood mixing. In Kamalika Chaudhuri and Ruslan Salakhutdinoy (eds.), Proc. ICML, volume 97 of Proceedings of Machine Learning Research, pp. 21-29. PMLR, 2019. URL /tL/http://prroeedinng
mlr
hai ja1 9a. html
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social Networks, 25(3):211-234 2003. ISSN 0378-8733.
doi: http:///oo.arg///oo0000002577110 www www.sciennedirect
/RL|https
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. Proc. of ICLR, 2021.
James Atwood and Don Towsley. Diffussion-convllttional neural networks. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gameet (eds.), Proc. of NIPS, volume 29. Curran Asso- ciates, Inc., 2016. URL https::/ppocceediiiiie neuriss. ctc.ips.cccppe/e wttpp//aee///////1eeee.e.e wwwpeeeeeeeaaaap..ppppp pdf
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Hal Daumé III and Aarti Singh (eds.), Proc. of ICML, volume 119 of Proceedings of Machine Learning Research, pp. 1725-1735. PMLR, 2020. URL http:
//proceedings... mlr press /v11//1111/// 1 cwwn20v. html
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis (eds.), Proc. of KDD, pp. 257-266. ACM, 2019. doi: 10.114//3992500333002.. URL https::/doi..orrt 1145/3292500 233229220003330225
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(11) 1)): 1944-1957, 2007. doi: 10.1 1..109/T/AMM..00..11....
Matthias Fey, Gan Yuen, and Frank Weichert. Hierarchical inter- inter-message passing for learning molecular graphs arXiv preprini arXiv:2006. /2179, 2020.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee whye Teh (eds.). Proc. of ICML, volume 70 of Proceedings of Machine Learning Research, pp. 1262-1272 PMLR, 06-11 Aug 2017. URL httpa:::/ppoceeednng/e
mlr www.ppresssvvee.. hatpsss/vv0/// /tt////0//g///// httpggimmerrr 17.. htmll
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wal- lach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gamett (eds.), Proc. of NIPS, pp. 1024-1034, 2017. URL https::/ meepeeddddinnnnninppssss neurips cc/ccc//paae http:/aap//211//aaaaa 5dd9bbbee33ddasscfff5aaa33333333 /twpe/////aaaaa//aaaaaaaaaaaeeee Abw.beeeaa-bssttt..ttte.
Weihua Hu, Matthias Fey, Marinka Zimik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Proc. of NewrIPS, 2020.
Katsuhiko Ishiguro, Shin-ichi Maeda, and Masanori Koyama. Graph warp module: auxiliary module for boosting the power of graph neural networks. CoRR, abs/1902.01020, 2019. URI.
lttt:://aae /ttp///aavvvv///////a orgg abs/ 1902..12 01020
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, 2021.
10

---

Under review as a conference paper at ICLR 2022
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20:359-392, 1998.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. arXiv preprint arXiv:1611.07530 2016.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networs. In Proc. of ICLR. OpenReview.net, 2017. URL SJU4ayYg1
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proc. of ICLR. OpenReview.net, 2019a. URL
https://openreviie wwtp:ooommiitttiiiiiiieeo.. 2A9Ym
Johannes Klicpera, Stefan Weilsenberger, and Stephan Günnemann. Diffusion improves graph learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'AchheBuc,, Emily B. Fox, and Roman Garnett (eds.), Proc. of NeurlPS, pp. 13333- 13345, 2019b. URL
23639777622211677666114446111133 -aba:a/ae461111--ttaaatttt....
Boling Li, Yingce Xia, Shufang Xie, Lijun Wu, and Tao Qin. Distance-enhanceed graph neural network for link prediction. URL htt.s: www. www.:dropbo..com///3/ prtopoxx.com/sssssfffffvvtvts
DEGNN win.Predcciinon. pdf 2d1=0#
Guohao Li, Chenxin Xiong, Ali K. Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. CoRR, abs/2006.07739, 2020a. URL htttt::tttatiiiii/ wwwp/aa////////o//ee///////eeae/ abs abs/2006//006/ 07739
Junying Li, Deng Cai, and Xiaofei He. grapeege for drug discovery. CoRR, abs/1709.03741, 2017. URL http:: http:///aaaxiiv.orra//////////// 03741
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Proc. of NeurlPS, 33, 2020b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proc. of AAAI, volume 32, 2018.
Renjie Liao, Mare Brockschmidt, Daniel Tarlow, Alexander L Gaunt, Raquel Urtasun, and Richard Zemel. Graph partition neural networks for semi-supervised classification. arXiv preprint 2018
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In Proc. of ICLR. OpenReview.ner, 2019, URL https
//openreview http:///wwee.eeeooommmoee/eeeeae
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash (eds.), Proc. of KDD, pp. 338-348. ACM, 2020. doi: 10. 00,1145/3399486.340333
URL htRpst:::: //to::///ooo.oo otg.///o..og/.////////////////// o00 11..o...111119999 htt.//3333446.343337774 3403076
Qing Lu and Lise Getoor. Link-based classification. In Proc. of ICML, 2003. URL https .
//lings. www..us.............e........... edu http://sstte/eeeaaaa////////////
Sitao Luan, Mingde Zhao, Xiao-War Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Proc. of NeurIPS, volume 32, Curran Asso- ciates, Inc., 2019. URL https::/ppoocceeinnggggg////// wtwpeeediiiinnn..niieeeeee neuripa. httpppppp..pppppp//////////
pdf
Zheng Ma. Junyu Xuan, Yu Guang Wang, Ming Li, and Pietro Liò. Path integral based convolution and pooling for graph neural networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Proc. of NeurIPS, 2020. URL httpp://proceeiigg beSS2255dbee225e3111335d33222223 absteaddda.....ttaattattt....... html

---

Under review as a conference paper at ICLR 2022
Victor Martinez, Fernando Berzal, and Waan-Carlos Cubero. A survey of link prediction in complex networks. ACM computing surveys (CSUR), 49(4):1-33, 2016.
Christopher Morris, Martin Ritzert, Matthias Fey, William I.. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proc. of AAAL, pp. 4602 4609. AAAI Press, 2019. doi: 10. 1..00///aii333311.333000 https: //ooi org 10. 609 aaai. v33101 33014602
URL
Trang Pham, Truyen Tran, Khanh Hoa Dam, and Svetha Venkatesh. Graph classificattin via deep learning with virtual nodes. CoRR,
2017. httphttt//arxxx.orr/g/////// abs/
1708.043 04357
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. arXiv preprint arXiv:1910.00452, 2019.
Ke Sun, Zhouchen Lin, and Zhanxing Zhu. Adagen: Adaboosting graph convolutional networks into deep models. 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Direct multi-hop attention based graph neural network. CoRR, abs/2009. 14332, 2020. URL /ttttp::/atxiv..o///aea
14332
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proc. of ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019. URL http:://poceeedinnnne
mlr. wwwpppewweee.p wul 9e html
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In Hal Daumé III and Aarti Singh (eds.), Proc. of /CML, volume 119, pp. 10432-10441. PMLR, 2020. URL http::/proceediinn www.nn..........mm..............
ptees/vvl19) http:a/eeweeee//////oooooeeeeee.
Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. In Sarit Kraus (ed.), Pruc. of ISCAL, pp. 1928- 1934. orcai.org, 2019a. doi: 10.24963/jccai201199 ijcai. 2019/267
URL URI/htpps::/dds..oo///0....
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proc. of ICML,, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In Proc. of ICLR. OpenReview.net, 2019b. URL URLhtttps//opperreiiie net/
(forum?id=ryGs61A555
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Proc. of ICML, pp. 40-48. PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Yike Guo and Faisal Farooq (eds.), Proc. of KDD, pp. 974-983, ACM, 2018a. doi: 10.1145522198199221999 URL
hittps://do bro...org/11 11.00.115550 3219999999919999
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchh and Roman Garnett (eds.), Proc. of NeurIPS, pp. 1880548155 2018b. URL URU/fccpps:/pprcceeiings wwwp:/iiiiininnnninnneneeee
.tml
12

---

Under review as a conference paper at ICLR 2022
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proc. of ICML, volume 97 Proceedings of Ma- chine Learning Research, pp. 7134-7143. PMLR, 2019. / mll press/v97/you 9b.ttml
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proc. of NIPS, pp. 5171-5181, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang. and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint orXiv:2010.16103 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Proc. of NeurlPS, 2020. URL http:////ppoeeecinng.enrrrsssss. cc http//pppe/////////eeee //ash// 33ddbaalseeePaaattoPoooooooaaaad
13

---

Under review as a conference paper at ICLR 2022
(a) Without Virtual Nodes
With Virtual Nodes
Figure 4: Example of using two virtual nodes improve expressiveness. In Figure 4(a) typical message-passing GNN (see Section 3) computes the same representation for 222 and Uy, and we cannot discriminate the node pairs 22) and (v), U3) if we just use the node representation for link prediction, as is usual. In Figure (b)) by adding two virtual nodes 81 and 82, 1/ and Va have clearly different features (because they connect to different virtual nodes with different labels) and different representations after GNN embedding, so (U1, U2) and (U1, v3) can be easily discriminated.
A ADDITIONAL DETAILS ON RELATED WORKS
Deeper GNNs. We mention simpler approaches in the Section 2 More advanced proposals are, for
example, based on special features and connections (Chen et 2020), community- baasdd normaliza-
tion of node representations using random clustering (Zhou et al. (2220), boosting techniques (Sun)
al. 202T). or differentiable aggregation functions in DeeperGCN (Li et al. 2020a).
Beyond One-Hop Neighbors. Graph diffusion methods (i.e., in graph theory, techniques for spreading information between nodes) are used various ways to determine the message targets and thus extend standard message passing beyond the one-hop neighborhood. (Atwood & Towsley 2016) use k-hop random walks to aggregate node features and extend the latter by the aggregated ones. APPNP (Klicpera et al. 2019a) applies personalized PageRank to propagate the node predictions generated by neural network. Other models aggregate node embeddings in every layer, GraphHeat (Xu al. 2019a) using the heat kernel, PAN (Ma al. 2020) the transition matrix of maximal entropy random walks, and PinSage (Ying et al. 2018a) using random walks. (Abu-El-Haija et al.) 2019) propose to concatenate embeddings aggregated using the transition matrices of k-hop random walks before applying one-hop neighbor aggregation. The diffusion- based graph neural network (GDC) (Klicpera et al. 2019b) aggregates information from multiple neighborhood hops each layer by sparsifying generalized form of graph diffusion. Subsequent works use diffusion methods on multiple scales (Liao et al. 2019 Luan al. 2019 Xhonneux et al. (020). Recently, (Wang al. 2020) integrated attention with diffusion-based message propagation.
Position Encodings. Our approach provides kind of positional embedding (Srinivasan Ribeiro 2019) and hence has some commonalities with models extending nodes with positional encodings,
e.g., Li et al.).
B ADDITIONAL THEORETICAL RESULTS: STRUCTURAL LINK REPRESENTATION
Adding structure-related features such distance encoding (Li et 2020b) has been demonstrated to make graph representation learning more powerful. For link prediction, (Zhang et al. (0200) propose the labeling trick extending distance encoding and making GNNs learn better link representations.
14

---

Under review as a conference paper at ICLR 2022
We first recall the definitions from (Zhagg et al. 2020 introducing the concept of labeling trick. Consider an undirected graph G as described in Section In addition, the tensor A E I x contains all node and edge features (if available). The diagonal components Au, denote the node features, while the off-diagonal components A,,,, denote the edge features of edge (u, v). The labeling trick uses target node set S S V and a labeling function to label all nodes in the node set V and stack the labels with A. A valid labeling trick must meet two conditions: (1) the nodes in S have different labels from the rest of the nodes, (2) the labeling function must be permutation invariant.
Let us recall our method using multiple virtual nodes. Assume we have multiple virtual nodes S = {si..... Sm Yu V. we have the additional features for the node [(u]S) (h(s1). h/ (mmm)) ("( (( sm)), where r(u[s,) = 1 if u is connected to the virtual node St, and 7(u w/) = O otherwise. h(s;) is the node representation of virtual node 8,, and initialized by one-hot vectors so that each virtual node has different labels.
Our labeling strategy is not a valid labeling trick by the definition of (Zhang et al., 2020 First, is not a subset of V, and we use addition instead of concatenation. Even if we extend V to V VUS. our labeling strategy still does not fit the permutation-invarian requirement. Nevertheless, it can achieve similar effects in learning structural link representations.
Theorem 1.
In any non-attributed graphs with n nodes, if the degree of each node in the graph is Lsc between and Ollog 2n (n:) for any constant > 0, given virtual nodes which evenly divide the node set into yn clusters, then there exists ( ((m ())(== -))²) many pairs of non-isomorphic links (u. w). (v, w), such that an h-layer I-WL-GND (see defimitions in (Li et al. (020bb) and (Zhang) el al. 2020;; one well-known example GIN (Xu el al., (201bb) gives u, u the same representation, while using virtual nodes can give v different representations.
The proof can be separated into two steps. The first step is to prove that there exists n/o(n" 1) = w(n") many nodes that are locally h-isomorphic.. This step is same as the proof of Theorem in (Zhang et al. 2020). so we omit the details here. After getting these locally isomorphic nodes, we denote the set of these nodes as Vi The second step is to find the non-isomorphic links.
Proof.
Step Let us partition Vi. = U.=I VÚ where V; is the subset of nodes connected to virtual node 8;- To be simple, we call each V/: cluster, and the sizes of different clusters are assumed to be the same Consider two nodes u E V; and v E V, from different clusters. Since both of them in Viso. so they have identical h--hop neighborhood structures, and h-layer 1-WL-GNN will give them the same representations. Then let us select another node w in Vi, h-layer 1-WL-GNN will also make (u, w) and (v. w) have the same representation.
[Vi =
|Vioo//
However, we use virtual nodes to label nodes and give them additional features, because u, w are in the same cluster while u, w belong to different clusters, (u, w) will have different representation from (v, w). Now let us count the number of such non-isomorphic link pairs Y, we can have:
( Viiso -1 m
Vieol
2)
Y
II 1
MIIK, -IIVI = =m(m= - 1)
Taking Visol ((n") into the above in-equation, we get
1 Y 2 2 m(m - 1)w
n2 ( 1)²) = w (m 1)2( m 1)2)
Example (Power of Using Multiple Virtual Nodes). In Figure we show two cases with and without virtual nodes. Consider the nodes 02, with the same local structure, which means they can get the same node representations by using 1-WL-GNN. So we cannot discriminate the links U2) and (01, va) if we just use I-WL-GNN and concatenate the node representations for link prediction. However, if we add 2 virtual nodes and add extra features to each node. U1 and U2 get new feature (1, 0), v3 get new feature (0, 1). So it is easy to see (2)) and (01, 03) now have different representations.
C ADDITIONAL DETAILS ON THE DATA
See Table for the datasets consider additionally in the appendix.
15

---

Under review as a conference paper at ICLR 2022
Table 5: Data from additional experiments. All graphs are undirected, and have edge but node features.
#Nodes
#Edges
Average Node Deg.
Average Clust. Coeff.
MaxSCC Ratio
Graph Diameter
ppa
576,289
30,326,273
73.7 3.9
0.223
0.999 0,906
29
cora
2,708
10,556
0.192
20
The datasets vary strongly in the number of nodes and edges with cora pubmed ddi col lab < ppal0 < ppa. Yet, ddi shows a challenging average node degree and hence is very dense. The average clustering coefficient intuitively reflects the extent which direct neighbors of node are themselves direct neighbors, and thus measures the "cliquishness" of the graph's 's subgraphs. Here, we have ppal0 pubmed cora < ppa ddi < collab. Finally, the graph diameter varies similarly, and again shows that ppa represents a special challenge. The diameter does not necessarily reflect the problem depth directly, but shows which maximal problem depth can be expected. In particular, the depths here hint at much larger numbers of GNN layers than the 2-3 layers we usually use, hence the data might suit testing under-reaching.
D MODEL CONFIGURATIONS AND TRAINING
We trained all models for 80 runs using the Bayesian optimization provided by wand and the following hyperparameters.
hidden dimension
32, 64, 128, 256
learning rate
0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001 0, 0.3, 0.6 1-7
dropout
# of layers
of virtual nodes (random)
1-10
# of virtual nodes
1,2,4,8,16,32,64
SGC- K
2-7
APPNP
0.05, 0.1, 0.2, 0.3
GNN-GDC
64, 128
GNN-GDC- a
0.05, 0.1, 0.2, 0.3
Please note that we considered the wide ranges of values only in order to find a good general setting. For practical usage hidden dimension of 256, learning rate of 0.0001, and dropout of 0.3 should work well; only on the small graphs dropout of 0 might work better. As usual, the number of layers depends the type of data; however, that the virtual nodes make it possible use more that then the usual 2-3 layers. Generally, higher numbers of virtual nodes work better, in line with our theoretical results.
Also note that we used less virtual nodes in the selection for the models (-RM, -RMF) since especially -RM was very slow and preliminary results showed that larger numbers did not change the results greatly probbbly due to the randomness. We used maximally 64 virtual nodes due to memory issues with larger numbers (e-g., 128), especially on the larger datasets. We report the specific numbers of GNN layers and virtual nodes used by the trained models from Tables g and 3 in Tablelō) For the first clustering in G we created 150 clusters on cora and pubmed, 200 clusters on ddi and collab, and 1000 ppal0.
We tuned all models for 80 runs, and thereafter ran the models with the best 3 configurations for runs and chose the best of these model as the final model (configuration).
We trained as suggested by the OGB (e.g., the splits, negative sampling) but used batch size of 212 and sometimes adapted the number of runs due to lack of resources; used for the experiments on collat ab and ppal0 in T However, we ran several our models for 10 runs as required for results the OGB leaderboards and the numbers are comparable (see Table I0
inttps://wandee ai/site
16

---

Under review as a conference paper at ICLR 2022
Table 6: Numbers of GNN layers and virtual nodes used by the trained models from Table
ddi
Ppal0
collab
pubmed
#Lay
#VNs
#Lay
#VNs
#Lay
#VNs
#Lay
#VNs
GCN
2
0
7
0
2
0
2
0
VN
2
7
1
1
5
1
RM
1
7
7
2
7
7
4
3
RMM F
2
9
6
9
3
2
5
8
CM
4
64
6
64
6
32
6
2
CM+
3
64
5
32
7
8
5
4
SAGE
2
0
4
0
5
0
2
0
VN
4
RM
4
10
5
6
7
4
7
3
RM
4
3
6
9
7
3
4
10
CM
3
8
64
32
4
16
CM+
3
16
6
4
6
2
7
8
GIN
6
0
2
0
2
0
5
0
VN
5
7
4
1
6
1
RM
2
5
6
8
3
7
5
10
RMM
1
4
4
7
3
9
5
7
CM
4
64
4
64
3
64
7
4
CM+ 5
1
6
16
4
16
4
1
Table 7: Results on ppa: OGB leaderboard compared to our best models. The GCN-VN result is only intermediary (tuned for smaller number of runs), but shown to confirm the positive trend.
Hits @ 100
SAGE +attr."
n/a
SAGE +dist.*
n/a 0.3245 + 0.0000
Adamic Adar*
SEAL"
0.4880 = 0.0316
GCN
0.1867 = 0.0132
SAGE*
0.1655 0.0240
GIN
0.2749 + 0.0082
GCN-VN
0.1991 + 0.0062
GCN-CM
0.2388 = 0.0047
GIN-CM+
0.2556 + 0.0079
We used 500 epochs with patience of 30. Furthermore, for collab, used the validation edges during testing (OGB contains both settings, with and without them).
E ADDITIONAL EXPERIMENTAL RESULTS
E. RESULTS ON ppa
The ppa dataset is challenging in both its size and density. Since we were missing the resources to run experiments for all baselines on this dataset, we compare our best models (trained only on ppal0, did not do additional hyperparameter tuning) to the OGB leaderboard in Table 7 For GCN, we see that our virtual node approach is able to improve the results considerably - even if only trained on 10% the data.
17

---

Under review as a conference paper at ICLR 2022
Table 8: Additional results small datasets.
cora Hits @ 10 runs
pubmed Hits 20 10 runs
GCN
0.9507 + 0.0309
0.9675 + 0.0143
-VN
0.9211 + 0.0324
0.9579 + 0.0214
RM
0.8818 + 0.0472
0.9522 + 0.0110
RM-f
0.8858 = 0.0653
0.8100 = 1.0781
CM
0,9100 = 0.0477
0.9575 0.0230
CM+
0.8239 + 0.1254
0.9189 + 0.0514
SAGE
0.8911 = 0.0768
0.9779 + 0.0105
VN
0,9167 = 0.0689
0.9659 + 0.0333
RM
0.8672 + 0.0446
0.9433 + 0.0208
RM-f
0.9116 + 0.0771
0.9800 + 0.0087
CM
0,9234 = 0.0487
0.9834 0.0068
CM+
0.8057 + 0.0609
0.9754 0.0139
GIN
0.8473 + 0,0828
0.9234 + 0.0166
VN
0.8939 + 0.0344
0.9790 + 0.0070
RM
0.7744 + 0.0799
0.9604 0.0158
RM-f
0.8505 = 0.0836
0.7986 + 0.0993
CM
0.8748 1 0.0380
0.9125 1 0.0378
CM+
0.8419 + 0.0600
0.9037 + 0.0262
10a
(LL)
GCN-NN (2L)
GCN-NN (6L)
10
GCN-CM (2T.)
GCN-CM (4T.)
ddi
Figure 5: Performance depending on layers: time per epoch (sec.); ddi. We observe from Figure that we get better @0 for the virtual nodes models already at 2 layers than for GCN 6 layers (its best score), hence we also compare these models. Here we see that a single virtual node can have positive impact the same time both prediction scores and efficiency. The clustering takes more time.
E.2 RESULTS ON cora
We ran the models also on the small cora data, yet the results confirm our expectation, that virtual nodes for link prediction should be used in challenging graphs. In contrast, for cora, we get already good scores with a regular GCN. See Table
E.3
RUNTIME
We show the runtimes on ddi in Figure 5 Here we see that single virtual node can have a positive impact at the same time on both prediction scores and efficiency, while the clustering takes more time.
E.4 COMPARISON OF CLUSTERING ALGORITHM
See Table and analysis in the main paper.
18

---

Under review as a conference paper at ICLR 2022
Table 9: Comparison of clustering algorithms determine virtual node connections; Hits 20, ddi.
See analysis in the main paper.
GCN
SAGE
GIN
CM yattis
0.6322
0.1565
0.8819 + 0.0341
0.6544 + 0.0960
CM metis
0.6554
0.1543
0.8041 + 0.1058
0.5962 = 0.1575
CM graccuus
0.6324
0.1048
0.5406 = 0.3769
0.7299 + 0.0604
Cidiffoool
0.7392 0.0381
0.7556 = 0.1252
0.5436 + 0.1572
Table 10: Result averaged over 10 runs, 3 run averages for comparison. We that the results relatively stable. Due to the randomness the random models, we did not spend the resources to compute the results for those.
collab
Hits @50
runs
3 runs
SAGE +attr."
n/a
n/a
SAGE +dist."
n/a 0.0000
n/a
Adamic Adar*
0.6417
n/a
SEAL*
0.6364
0.0071
n/a
DeeperGCN GCN+JKNet*
0.6187 0.0045
n/a
n/a
n/a
GCN
0.4714 + 0.0145
n/a 0.4955 + 0.0064
GCN
0,4921 + 0.0102
-VN
0.5077 0.0079 n/a
0.5049 = 0.0088
-RM
0,5083 = 0.0109
-RM-f
0.5046 = 0.0049
CM
0.5195 + 0.0050
0,5181 = 0.0076
CM+
0.5163 0.0063
0.5128 + 0.0129
SAGE*
0.5463 0.0112
n/a 0.5662 + 0.0149
SAGE
0.5516 + 0.0171
VN
0.5901 + 0.0063 n/a
0.5875 + 0.0091
RM
0.5830 = 0.0087
RRM-
n/a 0.6017 = 0.0137
0.6067 + 0.0063
CM
0.6056 = 0.0105
CM+
0.5965 + 0.0099
0.5940 = 0.0262
GIN
0.5696 + 0.0133
0.5768 = 0.0179
-VN
0.5736 + 0.0164
0.5863 0.0254
RM
n/a n/a 0.5742 0.0124
0.5412 - 0.0174
RM-F
0,5335 = 0.0087
CM
0.5821 0.0081
CM+
0.5371 + 0.0207
0.5557 = 0.0026
E.5
ADDITIONAL RUNS FOR collab
Table 10 compares several 10-run averages over collab to the 3-run averages. The numbers are stable.
F CLUSTER ANALYSIS
We computed additional statistics about our "virtual node clusters" (i.e., a cluster represents a set of nodes connected the same virtual node). Our hypotheses that our proposed clustering based
19

---

Under review as a conference paper at ICLR 2022
Table 11: Percentage of intra-cluster test edges, using numbers of virtual nodes between 8 and 64. For RM and CM we average over 10 different seeds but drop standard deviation (which is negligible) for readability. The numbers in brackets with -CM+ are the numbers of original METIS clusters which are then merged into "virtual node clusters"; we see great sensitivity for them. We highlight our proposed graph-base based clustering models we used in the experiments.
ddi
16
32
64
CM
49.37
30.33
17.43
03.81
04.08
RM IM/RM RM
25.03
12.50
06.26
03.11
01.57
CM+ (200)
25.31
12.95
06.82
03.61
02.13
RMF
94.36
73.75
47.48
27.16
14.60
CM (200)
94.65
73.51
47.85
27.06
14.89
CM graetus
100.0
100.0
100.0
99.95
99.73
co lab
16
32
64
CM
81.01
75.85
68.29
59.92
52.10
RM RM
25.05
12.50
06.22
03.14
01.52
CM+ (200)
58.97
52.38
48.90
47.12
46.31
CM+ (1000)
53.33
45.63
41.62
39.69
38.68
RM
94.35
73.76
47.51
27.21
14.25
CM+ (100)
95.50
86.10
73.14
61.84
56.39
CM+ (200)
96.68
85.83
71.55
59.88
53.01
CM+ (1000)
96.42
82.39
67.36
54.70
47.09
Ppal0
4
16
32
64
CM
79.95
73.87
70.37
64.97
58.97
RM/ RM
25.01
12.51
06.25
03.12
01.57
CM+ (1000)
51.58
43.55
39.24
37.43
36.34
RM
94.39
73.69
47.51
27.18
14.61
CM (200)
96.94
86.19
72.78
62.59
56.12
CM+ (1000)
96.36
83.07
66.03
53.56
45.06
the graph structure better reflects the distribution of test edges than, for example, random clustering. We report the results in Table 11 For the -RMF and -CM+ models we report two numbers. The upper shows the average number of intra-cluster test edges over 10 runs. The numbers in the lower part distinguish the actual edges and reflect how many different test edges occur in a cluster the 10 runs. These numbers hence represent lower and upper bounds respectively.
As expected, the numbers for -CM are in between those bounds. For ddi, we see that the -CM+ and -RM numbers are very similar, while the ones for -CM+ are much better over lab and ppal0. 0.
G INVESTIGATION OF NODE EMBEDDINGS
We also investigated the embeddings of the virtual nodes and compared them to the ones of the regular grapoh nodes, but could not derive many conclusions. The main finding is that the virtual node embeddings are much more diverse than the mean of the embeddings in corresponding cluster would have expected them to be similar.
20

---

Under review as a conference paper at ICLR 2022
H DETAILS ABOUT P-GNN
The model closest to our approach is the position-aware graph neural network (P-GNN) (You et al. 2019). assigns nodes random subsets of nodes called "anchor-sets", and then learns non-linear aggregation scheme that combines node feature information from each anchor-set and weighs it by the distance between the node and the anchor-set. That is, creates a message for each node for every anchor-set, instead of for each direct neighbor.
We ran experiments with P-GNN but did not obtain conclusive results. It did not run on the larger datasets. For ddi, we considered the number of anchor nodes hyperparameter since the fixed choice of 64 from the experiments of (You al. 2019) did not yield good results. However, larger numbers such as 128 or 512 resulted in very large runtimes (9 hrs / epoch). The result in Table is an intermediate best value after 50 runs. We contacted the authors and they indeed mentioned that the model is not very scalable and suggested to use just the anchor-set distance additional features, instead overtaking the adapted message passing as well. We did not do this extra experiment since the SAGE +dist model, whose numbers we report, follows similar approach.
21


Reviews:
[{"review_id": "zd6euABqVN", "reviewer": "Reviewer_gjKs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- 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.\n- The authors show the relationship between the proposed method and the distance encoding and labeling trick, which are popular techniques for link prediction.\n- The authors theoretically analyze the effectiveness of virtual nodes in terms of influence scores.\n\nWeakness of the paper:\n- 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.\n- 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. \n", "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.  \n\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZiphfzrB2bU", "reviewer": "Reviewer_RCd9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. 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.\n2. The paper theoretically analyses the effect of virtual nodes on influence distributions \n\nConcerns:\n\nI'm particularly interested in how to decide the number of virtual nodes because it is important for practical use.\nIn Table 6 in the appendix, GNN-CM uses a high number of virtual nodes, but in Figure 3 the trend seems different.\nIn Figure 3, on ddi, GNN-CM with 2 virtual nodes works the best.\nIs there any practical guidance?\n\nBy 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_paper": "This paper analyses the roles of virtual nodes in the link prediction problem. \nExtensive experiments are conducted to support the claims and show that virtual nodes can improve the link prediction performance of GNN.", "summary_of_the_review": "A good paper with theoretical analysis and extensive experiments", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "HqLbDl2CbCn", "reviewer": "Reviewer_CjZq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1.\tBy the authors’ claim, this is the first work to employ virtual nodes to improve the link prediction tasks.\n2.\tVirtual 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.\nWeakness/concerns:\n1.\tThe 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? \n2.\tThe 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.\n3.\tAs 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.\n4.\tThe proposed method seems to rely heavily on sophisticated hyperparameter searching. (as shown in Appendix D)\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0qpr_79Cu72", "reviewer": "Reviewer_mmjp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nHowever, 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.\n\n\n----------post rebuttal----------\n\nAfter 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_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. \n\n", "summary_of_the_review": "Contribution is limited, as explained in the main review, and I think it is not enough to be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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