Year: 2021

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.

heading: 1 INTRODUCTION
text: 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., 2021), or knowledge graphs (KGs) (Ji et al., 2021). 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., 2020).
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 et al., 2017). Interestingly, best performance is usually obtained by only considering two to three hops of neighbors (i.e., 2-3 layers in the GNN). One main reason identified for this is over-smoothing, the problem that node representations become indistinguishable when the number of layers increases (Li et al., 2018). The exponentially-growing amount of information has also been suggested as one issue connected to capturing long-range dependencies (Alon & Yahav, 2021). While it is 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 or drug-protein interactions). Hence, using a small number of layers to overcome the above problems results in under-reaching.
There have been several recent proposals to 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; Liu et al., 2020; Chen et al., 2020; Sun et al., 2021; Zhou et al., 2020; Li et al., 2020a). However, although (Chen et al., 2020) show that over-smoothing 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 message-passing scheme to consider neighbors beyond the one-hop neighborhood: based on graph diffusion (Atwood & Towsley, 2016; Klicpera et al., 2019a; Abu-El-Haija et al., 2019; Xu et al., 2019a; Ma et al., 2020; Klicpera et al., 2019b) and other theories (Morris et al., 2019; You
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, we propose a simple but elegant solution 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 classification 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 message 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 of very different nature and require novel/adapted solutions (e.g., a protein interaction network may easily contain millions of nodes, whereas a molecule to be classified contains usually less than fifty).
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 graph-based technique to connect them to the graph nodes. Consider Figure 1. In a nutshell, we use a graph clustering algorithm to determine groups of nodes in the graph that belong together and then connect these nodes to a common virtual node. In this way, under-reaching is 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., randomization 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 in 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 of data and GNNs. • Most importantly, we show that our virtual node extensions most often yield rather stable performance increases and allow standard GNNs to compete with complex state-of-the-art models that also try to improve message passing, as well as with the models leading the OGB leaderboards.

heading: 2 RELATED WORK
text: We give an overview on approaches that are similar from a technical perspective; for a 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 (Martínez et al., 2016; Zhang et al., 2020).
Deeper GNNs. Several techniques address over-smoothing 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., 2020) 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., 2021; 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-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.
Beyond One-Hop Neighbors. Recently, graph diffusion methods are used in 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 extend the node features. APPNP (Klicpera et al., 2019a) applies personalized PageRank to propagate the node predictions generated by a neural network. Other models concatenate (Abu-El-Haija et al., 2019) or aggregate (Xu et al., 2019a; Ma et al., 2020) node embeddings in every layer using a diffusion-based transition matrix. The diffusion-based graph neural network (GDC) (Klicpera 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. (2019) 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 (Gilmer et al., 2017; Li et al., 2017; Pham et al., 2017; Ishiguro et al., 2019). Note that the original idea was to compute a 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 we could consider as “virtual”. Fey et al. (2020) propose a GNN for molecule graph classification which clusters certain nodes within a 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 et 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 are 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 a specific, new GNN but a new technique for augmenting existing graph neural networks.
Although it is a well-known trick, the advantage of using virtual nodes has never been theoretically investigated nor fully understood. We focus on 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 to improve the representation of the link instead of the graph (nodes). We analyze theoretically and empirically how they improve GNN performance.

heading: 3 PRELIMINARIES
text: Link Prediction. We consider an undirected graphG = (V,E) with nodes V and edgesE ⊆ V ×V . 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 a node v ∈ V , Nv 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. (2017). These networks compute for every v ∈ V a node representation h`v at layer ` ∈ [1, 2, . . . , k], by aggregating its neighbor nodes based on a generic aggregation function and then combine the obtained vector with h`−1v as below; h 0 v are the initial node features.
h`v = COMBINE ` ( h`−1v , AGGREGATE ` ( {h`−1u | u ∈ Nv} )) (1)
Link prediction with GNNs is usually done by combining (e.g., concatenating) the final representations hLu , h L v , of the nodes u, v under consideration and passing them through several feed-forward layers with a final sigmoid function for scoring. We follow this approach.
We further use [1, n] to denote an interval [1,2,. . . , n].

heading: 4 VIRTUAL NODES IN GRAPH NEURAL NETWORKS FOR LINK PREDICTION
text: 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, we propose approaches that fit these scenarios.

heading: 4.1 MULTIPLE VIRTUAL NODES
text: Our main goal of using virtual nodes is to provide a shortcut for sharing information between the graph nodes. However, the amount of information in a graph with possibly millions of nodes is enormous, and likely too much to be captured in a single virtual node embedding. Further, not all information is equally relevant to all nodes. Therefore we suggest to use multiple virtual nodes S = {s1, s2 . . . , sn}1 each being connected to a subset of graph nodes, as determined by an assignment σ : V → [1, n]; n is considered as hyperparameter. We propose different methods to obtain σ:
Random (GNN-RM). Most simple, we can determine a fixed σ randomly once with initialization.
Increased Randomness (GNN-RMF ). Similarly a 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 a certain cluster structure (e.g., collaboration or social networks) that reflects which nodes belong closely together. We propose to connect such nodes in a cluster to a common virtual node, such that the structure inherent to the given graph is reflected in our virtual node assignment σ. More precisely, during initialization, we use a generic clustering algorithm which, given a number m, creates a set C = {C1, C2 . . . , Cm} of clusters (i.e., sets of graph nodes) by computing an assignment ρ : V → [1,m], assigning each graph node to a cluster. We then obtain σ by choosing m = n and σ = ρ.
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., 2018b)).
Advanced Clustering (GNN-CM+). Not every type of graph data contains an 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 a 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 m n, and apply the above clustering algorithm, during initialization. Then, in each epoch, we randomly guess an assignment σ′ : [1,m]→ [1, n] of clusters to virtual nodes and define σ(n) := σ′(ρ(n)). 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 σ′ 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.

heading: 4.2 THE MODEL
text: We integrate the multiple virtual nodes into a generic message-passing graph neural network by extending the approach from Hu et al. (2020) to the setting with multiple virtual nodes, by computing node representations h`v for a node v ∈ V at layer ` as follows:
h`si = COMBINE ` VN ( h`−1si , AGGREGATE ` VN ( {h`−1u | u ∈ V, σ(u) = i} )) (2)
h`v = COMBINE ` ( h`−1v +h ` sσ(v) , AGGREGATE` ( {h`−1u | u ∈ Nv} )) (3)
Note that the highlighted adaptation of the standard GNN processing from Equation (1) is only minor – but powerful. In our implementation, COMBINE`VN is addition combined with linear layers and layer normalization, and we use sum for AGGREGATE`VN .
1Since notation V is standard for nodes, we use S for the set of virtual nodes. Think of “supernodes”.

heading: 4.3 ANALYSIS: VIRTUAL NODES CHANGE INFLUENCE
text: Influence Score. Following (Xu et al., 2018; Klicpera et al., 2019a), we measure the sensitivity (also, influence) of a node x to a node y by the influence score I(x, y) = eT ∂h k x
∂h0y ; e is a vector of all ones,
hkx is the embedding of x at the k th layer, see Equations (1) and (3). For a k-layer GNN, the influence score is known to be proportional in expectation to the k-step random walk distribution from x to y:2
E[I(x, y)] ∝ Prw(x→ y, k) = ∑ r∈Rk k∏ `=1
1
deg(v`r) , (4)
(v0r , v 1 r , ..., v k r ) are the nodes in the path r from x := v 0 r to y := v k r , R k is the set of paths of length k. In what follows, we will exploit this relationship and argument in terms of the probability Prw.
Virtual Nodes. For simplicity, consider the influence score in an m-regular graph; there we have Prw(x→ y, k) = |R k| mk
. We hypothesize that we can come to similar conclusions in a general graph with average degree m. Consider the message passing between two distant nodes x and y. (I) In case the shortest path from x to y is of length > k, a k-layer GNN cannot capture it, and the probability Prw(x→ y, k) is obviously zero. If we then consider virtual nodes in the GNN layer (even with only one), we can pass messages from x to y through the virtual nodes and obtain a nonzero probability. (II) Consider the case where there is a shortest path of length ≤ k between x and y. By adding a virtual node s in one GNN layer, the probability changes to:
P srw(x→ y, k) = Prw(x→ y, k) + Prw(x→ s, s→ y) = |Rk|
(m+ 1)k +
1
(m+ 1)|V | . (5)
Compared to the original probability, we get the following impact ratio for using virtual nodes:
ir = mk
(m+ 1)k +
mk
(m+ 1)|V ||Rk| . (6)
Whenm is large enough, ir can be approximated by ir ' ( 1 + m k−1
|V ||Rk|
) . Here, we see that the impact
of virtual nodes grows when m increases. Our experiments confirm this theoretical observation.
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 x and y. If x and y connect to the same virtual node s, then Equation (5) changes as follows:
P srw(x→ y, k) = |Rk|
(m+ 1)k +
1
(m+ 1)|Cs| . (7)
Since the set Cs of nodes connecting to s is much smaller than V , the impact of multiple virtual nodes is greater than that of a 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 |R
k| mk to |R k| (m+1)k .
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 in learning structural link representations (see Theorem 1 and Figure 4(b)).

heading: 5 EVALUATION
text: 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? • In particular, are approaches based on the graph structure better? • How exactly do virtual nodes support link prediction? When do they help particularly?
2See Theorem 1 in (Xu et al., 2018). Note that the theorem makes some simplifying assumptions (e.g., on the shape of GNN).
types/amounts; (second) best results are (light) gray , overall best bold, second best underlined.
ddi ppa10 collab pubmed Hits@20 Hits@100 Hits@50 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 0.5532 ± 0.1262 0.1205 ± 0.0059 0.5083 ± 0.0109 0.9522 ± 0.0110 - RMF 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 - RMF 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 - RMF 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.1591 ± 0.0069 0.5557 ± 0.0026 0.9037 ± 0.0262
Datasets. We focused on challenging data from the OGB: ddi, a drug-drug interaction network; ppa10, a subset of the protein-protein 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., 2016). Since the datasets are not only very different in type but also in various other critical graph parameters and this is reflected in the performance of the models, we show relevant statistics in Table 1.3 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 a competitive comparison, we 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 we then extend with (multiple) virtual nodes.
3See Tables 2 and 3 in (Hu et al., 2020). We computed the numbers for ppa10 (which we focus on due to a lack of resources), and pubmed using the same techniques.

heading: 5.1 RESULTS
text: Overall Impact of Virtual Nodes, Tables 2, 7, 8 (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 ppa10; over pubmed, it works very well for GIN. The numbers for GNN-RM and GNN-RMF 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-RMF ) 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 collab, and mostly help on the challenging ppa10 dataset. On collab, we did further experiments using GAT (Veličković et al., 2017) 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 ppa10/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-passing 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, on 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.
Impact of Virtual Nodes on Number of GNN Layers and Efficiency, Figure 2. For the virtual nodes models, the scores increase with the number of layers for a 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 an idea about the runtime increase with using virtual nodes. It compares the 6-layer models, and shows the 4-layer GCN-CM which obtains performance similar to the 6-layer GCN-VN.
Impact of Virtual Node Number, Figure 3. First, consider the configurations of the best models for the overall results in Table 2, which are provided in Table 6 in the appendix. Here, we see that the chosen numbers of virtual nodes are indeed random for the “random” models, but GNN-CM consistently uses a 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 in 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 a trade off between number of virtual nodes and intra-cluster test edges, discussed in Section 5.2.
Using Virtual Nodes Only at the Last GNN Layer, Table 4. Alon & Yahav (2021) 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 use virtual nodes only at the last layer. However, we see that this can lead to extreme performance drops.
Impact of Clustering Algorithm, Table 9 (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 to 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 a good solution.

heading: 5.2 DISCUSSION AND CONCLUSIONS
text: 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 ddi, we see strongest improvements 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 (7)). 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 a lower level, is 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 11 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, 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, ppa10 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 11). 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 ppa10, and see a similar trend.
Sparse Graphs with Low to High Clustering Coefficient. We tested on three citation/collaboration 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, a 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.

heading: 6 CONCLUSIONS
text: We propose a 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.

heading: A ADDITIONAL DETAILS ON RELATED WORKS
text: Deeper GNNs. We mention simpler approaches in the Section 2. More advanced proposals are, for example, based on special features and connections (Chen et al., 2020), community-based normalization of node representations using random clustering (Zhou et al., 2020), boosting techniques (Sun et al., 2021), 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 in 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 a neural network. Other models aggregate node embeddings in every layer, GraphHeat (Xu et al., 2019a) using the heat kernel, PAN (Ma et 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 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). Recently, (Wang et al., 2020) integrated attention with diffusion-based message propagation.
Position Encodings. Our approach provides a kind of positional embedding (Srinivasan & Ribeiro, 2019) and hence has some commonalities with models extending nodes with positional encodings, e.g., (Li et al.).

heading: B ADDITIONAL THEORETICAL RESULTS: STRUCTURAL LINK REPRESENTATION
text: Adding structure-related features such as a distance encoding (Li et al., 2020b) has been demonstrated to make graph representation learning more powerful. For link prediction, (Zhang et al., 2020) propose the labeling trick extending distance encoding and making GNNs learn better link representations.
We first recall the definitions from (Zhang et al., 2020) introducing the concept of labeling trick. Consider an undirected graph G as described in Section 3. In addition, the tensor A ∈ Rn×n×k contains all node and edge features (if available). The diagonal components Av,v,: denote the node features, while the off-diagonal components Au,v,: denote the edge features of edge (u, v). The labeling trick uses a target node set 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 = {s1, ..., sm}. ∀u ∈ V , we have the additional features for the node l(u|S) = (h(s1), ..., h(sm))
T(γ(u|s1), ..., γ(u|sm)), where γ(u|si) = 1 if u is connected to the virtual node si, and γ(u|vi) = 0 otherwise. h(si) is the node representation of virtual node si, and is 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, S is not a subset of V , and we use addition instead of concatenation. Even if we extend V to V ∪ S, our labeling strategy still does not fit the permutation-invariant 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 between 1 and O(log 1− 2h (n)) for any constant > 0, given m virtual nodes which evenly divide the
node set into m clusters, then there exists ω ( (m− 1)2(n m − 1) 3 )
many pairs of non-isomorphic links (u,w), (v, w), such that an h-layer 1-WL-GNN (see definitions in (Li et al., 2020b) and (Zhang et al., 2020); one well-known example is GIN (Xu et al., 2019b)) gives u, v the same representation, while using m virtual nodes can give u, v different representations.
Proof. The proof can be separated into two steps. The first step is to prove that there exists n/o(n1− ) = ω(n ) many nodes that are locally h-isomorphic. This step is same as the proof of Theorem 2 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 Viso. The second step is to find the non-isomorphic links.
Step 2. Let us partition Viso = ∪i=1Vi where Vi is the subset of nodes connected to virtual node si. To be simple, we call each Vi a cluster, and the sizes of different clusters are assumed to be the same |Vi| = |Viso|/m. Consider two nodes u ∈ Vi and v ∈ Vj from different clusters. Since both of them are 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.
However, if we use virtual nodes to label nodes and give them additional features, because u,w are in the same cluster while v, 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:
Y ≥ m∏
i,j=1,j 6=i
|Vi||Vi − 1||Vj | = 1
2 m(m− 1) (( |Viso| m − 1 )( |Viso| m )2)
Taking |Viso| = ω(n ) into the above in-equation, we get
Y ≥ 1 2 m(m− 1)ω
( ( n
m − 1)3
) = ω ( (m− 1)2(n
m − 1)3 ) Example (Power of Using Multiple Virtual Nodes). In Figure 4, we show two cases with and without virtual nodes. Consider the nodes v2, v3 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 (v1, v2) and (v1, v3) if we just use 1-WL-GNN and concatenate the node representations for link prediction. However, if we add 2 virtual nodes and add extra features to each node. v1 and v2 get a new feature (1, 0), v3 get new feature (0, 1). So it is easy to see (v1, v2) and (v1, v3) now have different representations.

heading: C ADDITIONAL DETAILS ON THE DATA
text: See Table 5 for the datasets we consider additionally in the appendix.

heading: D MODEL CONFIGURATIONS AND TRAINING
text: We trained all models for 80 runs using the Bayesian optimization provided by wandb4 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 dropout 0, 0.3, 0.6 # of layers 1-7 # 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 - k 64, 128 GNN-GDC - α 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 a hidden dimension of 256, learning rate of 0.0001, and dropout of 0.3 should work well; only on the small graphs a dropout of 0 might work better. As usual, the number of layers depends on the type of data; however, note that the virtual nodes make it possible to 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 -RMF was very slow and preliminary results showed that larger numbers did not change the results greatly – probably 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 2, 8, and 3 in Table 6. For the first clustering in GNN-CM+, we created 150 clusters on cora and pubmed, 200 clusters on ddi and collab, and 1000 on ppa10.
We tuned all models for 80 runs, and thereafter ran the models with the best 3 configurations for 3 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 a batch size of 212 and sometimes adapted the number of runs due to lack of resources; we used 3 for the experiments on collab and ppa10 in Table 2. However, we ran several of our models for 10 runs as required for results on the OGB leaderboards and the numbers are comparable (see Table 10).
4https://wandb.ai/site
We used 500 epochs with a patience of 30. Furthermore, for collab, we used the validation edges during testing (OGB contains both settings, with and without them).

heading: E ADDITIONAL EXPERIMENTAL RESULTS
text: E.1 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 ppa10, we 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% on the data.
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 8.
E.3 RUNTIME
We show the runtimes on ddi in Figure 5. Here we see that a 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 ALGORITHMS
See Table 9 and analysis in the main paper.
E.5 ADDITIONAL RUNS FOR collab
Table 10 compares several 10-run averages over collab to the 3-run averages. The numbers are stable.

heading: F CLUSTER ANALYSIS
text: We computed additional statistics about our “virtual node clusters” (i.e., a cluster represents a set of nodes connected to the same virtual node). Our hypotheses was that our proposed clustering based on
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 one 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 over 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 -RMF numbers are very similar, while the ones for -CM+ are much better over collab and ppa10.
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 we 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 – we would have expected them to be similar.

heading: H DETAILS ABOUT P-GNN
text: The model closest to our approach is the position-aware graph neural network (P-GNN) (You et al., 2019). It assigns nodes to random subsets of nodes called “anchor-sets”, and then learns a 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, it 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 as hyperparameter since the fixed choice of 64 from the experiments of (You et 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 3 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 as additional features, instead of overtaking the adapted message passing as well. We did not do this extra experiment since the SAGE +dist model, whose numbers we report, follows a similar approach.

Review summaries:
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.    

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.