Link Prediction without Graph Neural Networks
Link prediction, which consists of predicting edges based on graph features,
is a fundamental task in many graph applications. As for several related
problems, Graph Neural Networks (GNNs), which are based on an attribute-centric
message-passing paradigm, have become the predominant framework for link
prediction. GNNs have consistently outperformed traditional topology-based
heuristics, but what contributes to their performance? Are there simpler
approaches that achieve comparable or better results? To answer these
questions, we first identify important limitations in how GNN-based link
prediction methods handle the intrinsic class imbalance of the problem -- due
to the graph sparsity -- in their training and evaluation. Moreover, we propose
Gelato, a novel topology-centric framework that applies a topological heuristic
to a graph enhanced by attribute information via graph learning. Our model is
trained end-to-end with an N-pair loss on an unbiased training set to address
class imbalance. Experiments show that Gelato is 145% more accurate, trains 11
times faster, infers 6,000 times faster, and has less than half of the
trainable parameters compared to state-of-the-art GNNs for link prediction.
Zexi Huang, Mert Kosan, Arlei Silva, Ambuj Singh
# Link Prediction without Graph Neural Networks

###### Abstract.

Link prediction, which consists of predicting edges based on graph features, is a fundamental task in many graph applications. As for several related problems, Graph Neural Networks (GNNs), which are based on an attribute-centric message-passing paradigm, have become the predominant framework for link prediction. GNNs have consistently outperformed traditional topology-based heuristics, but what contributes to their performance? Are there simpler approaches that achieve comparable or better results? To answer these questions, we first identify important limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem--due to the graph sparsity--in their training and evaluation. Moreover, we propose _Gelato_, a novel topology-centric framework that applies a topological heuristic to a graph enhanced by attribute information via graph learning. Our model is trained end-to-end with an N-pair loss on an unbiased training set to address class imbalance. Experiments show that Gelato is 145% more accurate, trains 11 times faster, infers 6,000 times faster, and has less than half of the trainable parameters compared to state-of-the-art GNNs for link prediction.

Link Prediction; Graph Neural Networks; Graph Learning; Topological Heuristics +
Footnote †: 10: 2018 Association for Computing Machinery.

ACM ISBN 978-1-4509-30XXXX-X/18/06...$15.00 [https://doi.org/10.1145/300XXXXXXXXX](https://doi.org/10.1145/300XXXXXXXXX)

2

## 1. Introduction

Machine learning on graphs supports various structured-data applications including social network analysis [38; 60; 73], recommender systems [30; 76; 50], natural language processing [62; 85; 81], and physics modeling [15; 29; 64]. Among the graph-related tasks, one could argue that link prediction [43; 46] is the most fundamental one. This is because link prediction not only has many concrete applications [37; 41; 58] but can also be considered an (implicit or explicit) step of the graph-based machine learning pipeline [45; 47; 78]--as the observed graph is usually noisy and/or incomplete.

In recent years, Graph Neural Networks (GNNs) [24; 35; 74] have emerged as the predominant paradigm for machine learning on graphs. Similar to their great success in node classification [36; 79; 95] and graph classification [51; 86; 90], GNNs have been shown to achieve state-of-the-art link prediction performance [58; 89; 88]. Compared to classical approaches that rely on expert-designed heuristics to extract topological information (e.g., Common Neighbors [52], Adamic-Adar [1], Preferential Attachment [4]), GNNs have the potential to discover new heuristics via supervised learning and the natural advantage of incorporating node attributes.

However, there is little understanding of what factors contribute to the success of GNNs in link prediction, and whether simpler alternatives can achieve comparable performance--as recently found for node classification [26]. GNN-based methods approach link prediction as a binary classification problem. Yet different from other classification problems, link prediction deals with extremely class-imbalanced data due to the sparsity of real-world graphs. We argue that class imbalance should be accounted for in both training and evaluation of link prediction. In addition, GNNs combine topological and attribute information by learning topology-smoothened attributes (embeddings) via message-passing [39]. This attribute-centric mechanism has been proven effective for tasks _on_ the topology such as node classification [44], but link prediction is a task _for_ the topology, which naturally motivates topology-centric paradigms (see Figure 1).

The goal of this paper is to address the key issues raised above. We first show that the evaluation of GNN-based link prediction pictures an overly optimistic view of model performance compared to the (more realistic) imbalanced setting. Class imbalance also prevents the generalization of these models due to bias in their training. Instead, we propose the use of the N-pair loss with an unbiased set of training edges to account for class imbalance. Moreover, we present _Gelato_, a novel framework that combines topological and attribute information for link prediction. As a simpler alternative
to GNNs, our model applies topology-centric graph learning to incorporate node attributes directly into the graph structure, which is given as input to a topological heuristic, Autocovariance, for link prediction. Extensive experiments demonstrate that our model significantly outperforms state-of-the-art GNN-based methods in both accuracy and scalability.

To summarize, our contributions are:

* We scrutinize the training and evaluation of supervised link prediction methods and identify their limitations in handling class imbalance.
* We propose a simple, effective, and efficient framework to combine topological and attribute information for link prediction without using GNNs.
* We introduce an N-pair link prediction loss combined with an unbiased set of training edges that we show to be more effective at addressing class imbalance.

## 2. Limitations in Supervised Link Prediction Evaluation and Training

Supervised link prediction is often formulated as a binary classification problem, where the positive (or negative) class includes node pairs connected (or not connected) by a link. A key difference between link prediction and typical classification problems (e.g., node classification) is that the two classes in link prediction are _extremely_ imbalanced, since most real-world graphs of interest are sparse (see Table 1). However, we find that class imbalance is not properly addressed in both evaluation and training of existing supervised link prediction approaches, as discussed below.

**Link prediction evaluation.** Area Under the Receiver Operating Characteristic Curve (AUC) and Average Precision (AP) are the two most popular evaluation metrics for supervised link prediction [8, 11, 13, 34, 55, 89, 91, 97]. We first argue that, as in other imbalanced classification problems [16, 63], AUC is not an effective evaluation metric for link prediction as it is biased towards the majority class (non-edges). On the other hand, AP and other rank-based metrics such as Hits@\(k-\)used in Open Graph Benchmark (OGB) [25]--are effective for imbalanced classification _if evaluated on a test set that follows the original class distribution_. Yet, existing link prediction methods [8, 34, 55, 89, 97] compute AP on a test set that contains all positive test pairs and only an equal number of random negative pairs. Similarly, OGB computes Hits@\(k\) against a very small subset of random negative pairs. We term these approaches _biased testing_ as they highly overestimate the ratio of positive pairs in the graph. Evaluation metrics based on these biased test sets provide an overly optimistic measurement of the actual performance in _unbiased testing_, where every negative pair is included in the test set. In fact, in real applications where test positive edges are not known a priori, it is impossible to construct those biased test sets to begin with. Below, we also present an illustrative example of the misleading performance evaluation based on _biased testing_.

_Example:_ Consider a graph with 10k nodes, 100k edges, and 99.9M disconnected (or negative) pairs. A (bad) model that ranks 1M false positives higher than the true edges achieves 0.99 AUC and 0.95 in AP under _biased testing_ with equal negative samples. (Detailed computation in Appendix A.)

The above discussion motivates a more representative evaluation setting for supervised link prediction. Specifically, we argue for the use of rank-based evaluation metrics--AP, Precision@\(k\)[43], and Hits@\(k\)[5]--with _unbiased testing_, where positive edges are ranked against all negative pairs. These metrics have been widely applied in related problems, such as unsupervised link prediction [27, 43, 53, 92], knowledge graph completion [5, 72, 82], and information retrieval [66], where class imbalance is also significant. In our experiments, we will illustrate how these evaluation metrics combined with _unbiased testing_ provide a drastically different and more informative performance evaluation compared to existing approaches.

**Link prediction training.** Following the formulation of supervised link prediction as binary classification, most existing models adopt the binary cross entropy loss to optimize their parameters [11, 13, 34, 88, 89, 91, 97]. To deal with class imbalance, these approaches downsample the negative pairs to match the number of positive pairs in the training set (_biased training_). We highlight two drawbacks of _biased training_: (1) it induces the model to overestimate the probability of positive pairs, and (2) it discards potentially useful evidence from most negative pairs. Notice that the first drawback is often hidden by _biased testing_. Instead, this paper proposes the use of _unbiased training_, where the ratio of negative pairs in the training set is the same as in the input graph. To train our model in this highly imbalanced setting, we apply the N-pair loss for link prediction instead of the cross entropy loss (Section 3.3).

## 3. Method

**Notation and problem.** Consider an attributed graph \(G=(V,E,X)\), where \(V\) is the set of \(n\) nodes, \(E\) is the set of \(m\) edges (links), and \(X=(x_{1},...,x_{n})^{T}\in\mathbb{R}^{n\times r}\) collects \(r\)-dimensional node attributes. The topological (structural) information of the graph is represented by its adjacency matrix \(A\in\mathbb{R}^{n\times n}\), with \(A_{uv}>0\) if an edge of weight

Figure 1. GNN incorporates topology into attributes via message-passing, which is effective for tasks _on_ the topology. Link prediction, however, is a task _for_ the topology, which motivates the design of Gelato—a novel framework that leverages graph learning to incorporate attributes into topology.
\(A_{uw}\) connects nodes \(u\) and \(v\) and \(A_{uw}=0\), otherwise. The (weighted) degree of node \(u\) is given as \(d_{u}=\sum_{\theta}A_{uw}\) and the corresponding degree vector (matrix) is denoted as \(d\in\mathbb{R}^{n}\) (\(D\in\mathbb{R}^{n\times n}\)). The volume of the graph is \(\operatorname{vol}(G)=\sum_{u}d_{u}\). Our goal is to infer missing links in \(G\) based on its topological and attribute information, \(A\) and \(X\).

**Model overview.** Figure 2 provides an overview of our link prediction model. It starts with a topology-centric graph learning phase that incorporates node attribute information directly into the graph structure via a Multi-layer Perceptron (MLP). We then apply a topological heuristic, Autocovariance (AC), to the attribute-enhanced graph to obtain a pairwise score matrix. Node pairs with the highest scores are predicted as (positive) links. The scores for training pairs are collected to compute an N-pair loss. Finally, the loss is used to train the MLP parameters in an end-to-end manner. We named our model Gelato (Graph enhancement for link prediction with autocovariance). Gelato represents a paradigm shift in supervised link prediction by combining a graph encoding of attributes with a topological heuristic instead of relying on increasingly popular GNN-based embeddings.

### Graph learning

The goal of graph learning is to generate an enhanced graph that incorporates node attribute information into the topology. This can be considered as the "dual" operation of message-passing in GNNs, which incorporates topological information into attributes (embeddings). We argue that graph learning is the more suitable scheme to combine attributes and topology for link prediction, since link prediction is a task for the topology itself (as opposed to other applications such as node classification).

Specifically, our first step of graph learning is to augment the original edges with a set of node pairs based on their (untrained) attribute similarity (i.e., adding an \(\epsilon\)-neighborhood graph):

\[\widetilde{E}=E+\{(u,v)\mid s(x_{u},x_{v})>\epsilon_{\eta}\} \tag{1}\]

where \(s(\cdot)\) can be any similarity function (we use cosine in our experiments) and \(\epsilon_{\eta}\) is a threshold that determines the number of added pairs as a ratio \(\eta\) of the original number of edges \(m\).

A simple MLP then maps the pairwise node attributes into a trained edge weight for every edge in \(\widetilde{E}\):

\[w_{uw}=\operatorname{MLP}([x_{u};x_{v}];\theta) \tag{2}\]

where \([x_{u};x_{v}]\) denotes the concatenation of \(x_{u}\) and \(x_{v}\) and \(\theta\) contains the trainable parameters. For undirected graphs, we instead use the following permutation invariant operator (Garno et al., 2016):

\[w_{uw}=\operatorname{MLP}([x_{u}+x_{v};|x_{u}-x_{v}|];\theta) \tag{3}\]

The final edge weights of the enhanced graph are a weighted combination of the topological weights, the untrained weights, and the trained weights:

\[\widetilde{A}_{uw}=\alpha A_{uw}+(1-\alpha)(\beta w_{uw}+(1-\beta)s(x_{u},x_{v })) \tag{4}\]

where \(\alpha\) and \(\beta\) are hyperparameters. The enhanced adjacency matrix \(\widetilde{A}\) is then fed into a topological heuristic for link prediction introduced in the next section. Note that the MLP is not trained directly to predict the links, but instead trained end-to-end to enhance the input graph given to the topological heuristic. Also note that the MLP can be easily replaced by a more powerful model such as a GNN, but the goal of this paper is to demonstrate the general effectiveness of our framework and we will show that even a simple MLP leads to significant improvement over the base heuristic.

### Topological heuristic

Assuming that the learned adjacency matrix \(\widetilde{A}\) incorporates structural and attribute information, Gelato applies a topological heuristic to \(\widetilde{A}\). Specifically, we adopt Autocovariance, which has been shown to achieve state-of-the-art link prediction results for non-attributed graphs (Kal
heuristics implicitly use information from all edges and non-edges. Also, _unbiased training_ can be combined with adversarial negative sampling methods (Kumar et al., 2017; Zhang et al., 2017) from the knowledge graph embedding literature to increase the quality of contrasted negative pairs.

**Complexity analysis.** The only trainable component in our model is the graph learning MLP with \(O(rh+lh^{2})\) parameters--where \(r\) is the number of node features, \(l\) is the number of hidden layers, and \(h\) is the number of neurons per layer. Notice that the number of parameters is independent of the graph size. Constructing the \(\epsilon\)-neighborhood graph based on cosine similarity can be done efficiently using hashing and pruning (Kumar et al., 2017; Zhang et al., 2017). Computing the enhanced adjacency matrix with the MLP takes \(O((1+\eta)mr)\) time per epoch--where \(m=|E|\) and \(\eta\) is the ratio of edges added to \(E\) from the \(\epsilon\)-neighborhood graph. We apply sparse matrix multiplication to compute \(k\) entries of the \(t\)-step AC in \(O(\max(k,(1+\eta)mt))\) time. Note that unlike recent GNN-based approaches (Zhu et al., 2017; Zhang et al., 2017; Zhang et al., 2017) that generate distinctive subgraphs for each link (e.g., via the labeling trick), enclosing subgraphs for links in Gelato share the same information (i.e., learned edge weights), which significantly reduces the computational cost. Our experiments will demonstrate Gelato's efficiency in training and inference.

## 4. Experiments

We provide empirical evidence for our claims regarding supervised link prediction and demonstrate the accuracy and efficiency of Gelato. Our implementation is anonymously available at [https://anonymous.4open.science/r/Gelato/](https://anonymous.4open.science/r/Gelato/).

### Experiment settings

**Datasets.** Our method is evaluated on five attributed graphs commonly used as link prediction benchmark (Kumar et al., 2017; Zhang et al., 2017; Zhang et al., 2017; Zhang et al., 2017; Zhang et al., 2017; Zhang et al., 2017). Table 1 shows dataset statistics--see Appendix B for dataset details.

**Baselines.** For GNN-based link prediction, we include six state-of-the-art methods published in the past two years: LGCN (Kumar et al., 2017), TLC-GNN (Kumar et al., 2017), Neo-GNN (Kumar et al., 2017), NBFNet (Kumar et al., 2017), BScNets (Kumar et al., 2017), and WalkPool (Zhang et al., 2017), as well as three pioneering works--GAE (Kumar et al., 2017), SEAL (Kumar et al., 2017), and HGCN (Kumar et al., 2017). For topological link prediction heuristics, we consider Common Neighbors (CN) (Zhu et al., 2017), Adamic Adar (AA) (Beng et al., 2016), Resource Allocation (RA) (Kumar et al., 2017), and Autocovariance (AC) (Kumar et al., 2017)--the base heuristic in our model. To demonstrate the superiority of the proposed end-to-end model, we also include an MLP trained directly for link prediction, the cosine similarity (Cos) between node attributes, and AC on top of the respective weighted/augmented graphs (i.e., two-stage approaches where the MLP is trained separately for link prediction rather than trained end-to-end) as baselines.

**Hyperparameters.** For Gelato, we tune the proportion of added edges \(\eta\) from {0.0, 0.25, 0.5, 0.75, 1.0}, the topological weight \(\alpha\) from {0.0, 0.25, 0.5, 0.75}, and the trained weight \(\beta\) from {0.25, 0.5, 0.75}, 1.0}, with a sensitivity analysis included in Section 4.6. All other settings are fixed across datasets: MLP with one hidden layer of 128 neurons, AC scaling parameter \(t=3\), Adam optimizer (Kingmaa et al., 2014) with a learning rate of 0.001, a dropout rate of 0.5, and _unbiased training_ without downsampling. For baselines, we use the same hyperparameters as in their papers.

**Data splits for unbiased training and unbiased testing.** Following (Kumar et al., 2017; Zhang et al., 2017; Zhang et al., 2017; Zhang et al., 2017; Zhang et al., 2017), we adopt 85%/5%/10% ratios for training, validation, and testing. Specifically, for _unbiased training_ and _testing_, we first randomly (with seed 0) divide the (positive) edges \(E\) of the original graph into \(E^{+}_{train}\), \(E^{+}_{valid}\), and \(E^{+}_{test}\) for training, validation, and testing based on the selected ratios. Then, we set the negative pairs in these three sets as (1) \(E^{-}_{train}=E^{-}+E^{+}_{valid}+E^{+}_{test}\), (2) \(E^{-}_{valid}=E^{-}+E^{+}_{test}\), and (3) \(E^{-}_{test}=E^{-}\), where \(E^{-}\) is the set of all negative pairs (excluding self-loops) in the original graph. Notice that the validation and testing _positive_ edges are included in the _negative_ training set, and the testing _positive_ edges are included

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & \#Nodes & \#Edges & \#Attrs & Avg. degree & Density \\ \hline Cora & 2,708 & 5,278 & 1,433 & 3.90 & 0.14\% \\ CiteSeer & 3,327 & 4,552 & 3,703 & 2.74 & 0.08\% \\ PubMed & 19,717 & 44,324 & 500 & 4.50 & 0.02\% \\ Photo & 7,650 & 119,081 & 745 & 31.13 & 0.41\% \\ Computers & 13,752 & 245,861 & 767 & 35.76 & 0.26\% \\ \hline \hline \end{tabular}
\end{table}
Table 1. A summary of dataset statistics.

Figure 2. Gelato applies graph learning to incorporate attribute information into the topology via an MLP. The learned graph is given to a topological heuristic that predicts edges between node pairs with high Autocovariance similarity. The parameters of the MLP are optimized end-to-end using the N-pair loss. Experiments show that Gelato outperforms state-of-the-art GNN-based link prediction methods.
in the _negative_ validation set. These inclusions simulate the real-world scenario where the testing edges (and the validation edges) are unobserved during validation (training).

**Evaluation metrics.** We adopt Precision@\(k\) (\(prec@k\))--proportion of positive edges among the top \(k\) of all testing pairs, Hits@\(k\) (\(hits@k\))--ratio of positive edges individually ranked above \(k\)th place against all negative pairs, and Average Precision (AP)--area under the precision-recall curve, as evaluation metrics. We report results from 10 runs with random seeds ranging from 1 to 10.

More detailed experiment settings can be found in Appendix C.

### Link prediction performance

Table 2 summarizes the link prediction performance in terms of the mean and standard deviation of Average Precision (AP) for all methods. Figure 3 and Figure 4 show results based on \(prec@k\) (\(k\) as a ratio of test edges) and \(hits@k\) (\(k\) as the rank) for varying \(k\).

First, we want to highlight the drastically different performance of GNN-based methods compared to those found in the original papers [13; 55; 81; 88; 91; 97] and reproduced in Appendix D. While they achieve AUC/AP scores of often higher than 90% under _biased testing_, here we see most of them underperform even the simplest topological heuristics such as Common Neighbors under _unbiased testing_. These results support our arguments from Section 2 that evaluation metrics based on _biased testing_ can produce misleading results compared to _unbiased testing_. The overall best performing GNN model is Neo-GNN, which directly generalizes the pairwise topological heuristics. Yet still, it consistently underperforms AC, a random-walk based heuristic that needs neither node attributes nor supervision/training.

We then look at two-stage combinations of AC and models for attribute information. We observe noticeable performance gains from combining attribute cosine similarity and AC in Cora and CiteSeer but not for other datasets. Other two-stage approaches achieve similar or worse performance.

Finally, Gelato significantly outperforms the best GNN-based model with an average relative gain of **145.2%** and AC with a gain of **52.6%** in terms of AP--similar results were obtained for \(prec@k\) and \(hits@k\). This validates our hypothesis that a simple MLP can effectively incorporate node attribute information into the topology when our model is trained end-to-end. Next, we will provide insights behind these improvements and demonstrate the efficiency of Gelato on training and inference.

### Visualizing Gelato predictions

To better understand the performance of Gelato, we visualize its learned graph, prediction scores, and predicted edges in comparison with AC and the best GNN-based baseline (Neo-GNN) in Figure 5.

Figure 4(a) shows the input adjacency matrix for the subgraph of Photo containing the top 160 nodes belonging to the first class sorted in decreasing order of their (within-class) degree. Figure 4(b) illustrates the enhanced adjacency matrix learned by Gelato's MLP. Comparing it with the Euclidean distance between node attributes in Figure 4(c), we see that our enhanced adjacency matrix effectively incorporates attribute information. More specifically, we notice the down-weighting of the edges connecting the high-degree nodes with larger attribute distances (matrix entries 0-40 and especially 0-10) and the up-weighting of those connecting medium-degree nodes with smaller attribute distances (40-80). In Figure 4(d) and Figure 4(e), we see the corresponding AC scores based on the input and the enhanced adjacency matrix (Gelato). Since AC captures the degree distribution of nodes [27], the vanilla AC scores greatly favor high-degree nodes (0-40). By comparison, thanks to the down-weighting, Gelato assigns relatively lower scores to edges connecting them to low-degree nodes (60-160), while still capturing the edge density between high-degree nodes (0-40). The immediate result of this is the significantly improved precision as shown in Figure 4(h) compared to Figure 4(g). Gelato covers as many positive edges in the high-degree region as AC while making far fewer wrong predictions for connections involving low-degree nodes.

The prediction probabilities and predicted edges for Neo-GNN are shown in Figure 4(f) and Figure 4(i), respectively. Note that while it predicts edges connecting high-degree node pairs (0-40) with high probability, similar values are assigned to many low-degree pairs (80-160) as well. Most of those predictions are wrong, both in the low-degree region of Figure 4(i) and also in other low-degree parts of the graph that are not shown here. This analysis supports our claim that Gelato is more effective at combining node attributes and the graph topology, enabling state-of-the-art link prediction.

### Loss and training setting

In this section, we demonstrate the advantages of the proposed N-pair loss and _unbiased training_ for supervised link prediction. Figure 6 shows the training and validation losses and \(prec@100\)% (our validation metric) in training Gelato based on the cross entropy (CE) and N-pair (NP) losses under _biased_ and _unbiased training_ respectively. The final test AP scores are shown in the titles.

In the first column (CE with _biased training_), different from the training, both loss and precision for (unbiased) validation decrease. This leads to even worse test performance compared to the untrained base model (i.e., AC). In other words, albeit being the most popular loss function for supervised link prediction, CE with _biased training_ does not generalize to _unbiased testing_. On the contrary, as shown in the second column, the proposed NP loss with _biased training_--equivalent to the pairwise logistic loss [7]--is a more effective proxy for _unbiased testing_ metrics.

The right two columns show results with _unbiased training_, which is better for CE as more negative pairs are present in the training set (with the original class ratio). On the other hand, NP is more consistent with unbiased evaluation metrics, leading to 8.5% better performance. This is because, unlike CE, which optimizes positive and negative pairs independently, NP contrasts negative pairs against positive ones, giving higher importance to negative pairs that are more likely to be false positives.

### Ablation study

We have demonstrated the superiority of Gelato over its individual components and two-stage approaches in Table 2 and analyzed the effect of losses and training settings in Section 4.4. Here, we collect the results with the same hyperparameter setting as Gelato and present a comprehensive ablation study in Table 3. Specifically,
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & & Cora & CiteSeer & PubMed & Photo & Computers \\ \hline \multirow{8}{*}{GNN} & GAE & 0.27 \(\pm\) 0.02 & 0.66 \(\pm\) 0.11 & 0.26 \(\pm\) 0.03 & 0.28 \(\pm\) 0.02 & 0.30 \(\pm\) 0.02 \\  & SEAL & 1.89 \(\pm\) 0.74 & 0.91 \(\pm\) 0.66 & *** & 10.49 \(\pm\) 0.86 & 6.84\({}^{*}\) \\  & HGCN & 0.82 \(\pm\) 0.03 & 0.74 \(\pm\) 0.10 & 0.35 \(\pm\) 0.01 & 2.11 \(\pm\) 0.10 & 2.30 \(\pm\) 0.14 \\  & LGCN & 1.14 \(\pm\) 0.04 & 0.86 \(\pm\) 0.09 & 0.44 \(\pm\) 0.01 & 3.53 \(\pm\) 0.05 & 1.96 \(\pm\) 0.03 \\  & TLC-GNN & 0.29 \(\pm\) 0.09 & 0.35 \(\pm\) 0.18 & OOM & 1.77 \(\pm\) 0.11 & OOM \\  & Neo-GNN & 2.05 \(\pm\) 0.61 & 1.61 \(\pm\) 0.36 & 1.21 \(\pm\) 0.14 & 10.83 \(\pm\) 1.53 & 6.75\({}^{*}\) \\  & NBFNet & 1.36 \(\pm\) 0.17 & 0.77 \(\pm\) 0.22 & *** & 11.99 \(\pm\) 1.60 & *** \\  & BScNets & 0.32 \(\pm\) 0.08 & 0.20 \(\pm\) 0.06 & 0.22 \(\pm\) 0.08 & 2.47 \(\pm\) 0.18 & 1.45 \(\pm\) 0.10 \\  & WalkPool & 2.04 \(\pm\) 0.07 & 1.39 \(\pm\) 0.11 & 1.31\({}^{*}\) & OOM & OOM \\ \hline \multirow{8}{*}{Topological} & CN & 1.10 \(\pm\) 0.00 & 0.74 \(\pm\) 0.00 & 0.36 \(\pm\) 0.00 & 7.73 \(\pm\) 0.00 & 5.09 \(\pm\) 0.00 \\  & AA & 2.07 \(\pm\) 0.00 & 1.24 \(\pm\) 0.00 & 0.45 \(\pm\) 0.00 & 9.67 \(\pm\) 0.00 & 6.52 \(\pm\) 0.00 \\ \cline{1-1}  & RA & 2.02 \(\pm\) 0.00 & 1.19 \(\pm\) 0.00 & 0.33 \(\pm\) 0.00 & 10.77 \(\pm\) 0.00 & 7.71 \(\pm\) 0.00 \\ \cline{1-1}  & AC & 2.43 \(\pm\) 0.00 & 2.65 \(\pm\) 0.00 & 2.50 \(\pm\) 0.00 & 16.63 \(\pm\) 0.00 & 11.64 \(\pm\) 0.00 \\ \hline \multirow{8}{*}{Attributes + Topology} & MLP & 0.30 \(\pm\) 0.05 & 0.44 \(\pm\) 0.09 & 0.14 \(\pm\) 0.06 & 1.01 \(\pm\) 0.26 & 0.41 \(\pm\) 0.23 \\  & Cos & 0.42 \(\pm\) 0.00 & 1.89 \(\pm\) 0.00 & 0.07 \(\pm\) 0.00 & 0.11 \(\pm\) 0.00 & 0.07 \(\pm\) 0.00 \\ \cline{1-1}  & MLP+AC & 3.24 \(\pm\) 0.03 & 1.95 \(\pm\) 0.05 & 2.61 \(\pm\) 0.06 & 15.99 \(\pm\) 0.21 & 11.25 \(\pm\) 0.13 \\ \cline{1-1}  & Cos+AC & 3.60 \(\pm\) 0.00 & 4.46 \(\pm\) 0.00 & 0.51 \(\pm\) 0.00 & 10.01 \(\pm\) 0.00 & 5.20 \(\pm\) 0.00 \\ \cline{1-1}  & MLP+Cos+AC & 3.39 \(\pm\) 0.06 & 4.15 \(\pm\) 0.14 & 0.55 \(\pm\) 0.03 & 10.88 \(\pm\) 0.09 & 5.75 \(\pm\) 0.11 \\ \hline \multicolumn{1}{c}{Gelato} & **3.90 \(\pm\) 0.03** & **4.55 \(\pm\) 0.02** & **2.88 \(\pm\) 0.09** & **25.68 \(\pm\) 0.53** & **18.77 \(\pm\) 0.19** \\ \hline \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory. & & & & \\ \multicolumn{1}{c}{\({}^{*}\) Run only once as each run takes \(-\)100 hrs;} & *** Each run takes \(>\)1000 hrs; & OOM: Out Of Memory.
Figure 5: Illustration of the link prediction process of Gelato, AC, and the best GNN-based approach, Neo-GNN, on a subgraph of Photo. Gelato effectively incorporates node attributes into the graph structure and leverages topological heuristics to enable state-of-the-art link prediction.
_Gelato_\(-MLP\) (\(AC\)) represents Gelato without the MLP (Autocovariance) component, i.e., only using Autocovariance (MLP) for link prediction. _Gelato_\(-NP\) (\(UT\)) replaces the proposed N-pair loss (_unbiased training_) with the cross entropy loss (_biased training_) applied by the baselines. Finally, _Gelato_\(-NP\)+\(UT\) replaces both the loss and the training setting.

We observe that removing either MLP or Autocovariance leads to inferior performance, as the corresponding attribute or topology information would be missing. Further, to address the class imbalance problem of link prediction, both the N-pair loss and _unbiased training_ are crucial for effective training of Gelato.

While all supervised baselines originally adopt _biased training_, we also implement the same _unbiased training_ (and N-pair loss) as Gelato for those that are scalable in Appendix E\(-\)results are consistent with the ones discussed in Section 4.2.

### Sensitivity analysis

The selected hyperparameters of Gelato for each dataset are recorded in Table 4, and a sensitivity analysis of \(\eta\), \(\alpha\), and \(\beta\) are shown in Figure 7 and Figure 8 respectively for Photo and Cora.

For most datasets, we find that simply setting \(\beta=1.0\) and \(\eta=\alpha=0.0\) leads to the best performance, corresponding to the scenario where no edges based on cosine similarity are added and the edge weights are completely learned by the MLP. For Cora and CiteSeer, however, we first notice that adding edges based on untrained cosine similarity alone leads to improved performance (see Table 2), which motivates us to set \(\eta=0.5/0.75\). In addition, we find that a large trainable weight \(\beta\) leads to overfitting of the model as the number of node attributes is large while the number of (positive) edges is small for Cora and CiteSeer (see Table 1). We address this by decreasing the relative importance of trained edge weights (\(\beta=0.25/0.5\)) and increasing that of the topological edge weights (\(\alpha=0.5\)), which leads to better generalization and improved performance. Based on our experiments, these hyperparameters can be easily tuned using simple hyperparameter search techniques, such as line search, using a small validation set.

### Running time comparison

We compare Gelato with other supervised link prediction methods in terms of running time for Photo (see details in Appendix F). As the only method that applies _unbiased training_\(-\)with more negative samples\(-\)Gelato shows a competitive training speed that is 11\(\times\) faster than the best performing GNN-based method, Neo-GNN. In terms of inference time, Gelato is much faster than most baselines with a 6,000\(\times\) speedup compared to Neo-GNN. We further observe more significant efficiency gains for Gelato over Neo-GNN for larger datasets\(-\)e.g., 14\(\times\) (training) and 25,000\(\times\) (testing) for Computers.

## 5. Related Work

**Topological heuristics for link prediction.** The early link prediction literature focuses on topology-based heuristics. This includes approaches based on local (e.g., Common Neighbors (Srivastava et al., 2014), Adamic

Figure 6. Training of Gelato based on different losses and training settings for Photo with test AP (mean \(\pm\) std) shown in the titles. Compared with the cross entropy loss, the N-pair loss with _unbiased training_ is a more consistent proxy for _unbiased testing_ metrics and leads to better peak performance.

Figure 7. Performance of Gelato with different values of \(\eta\).
Adar [(1)], and Resource Allocation [(96)]) and higher-order (e.g., Katz [(32)], PageRank [(54)], and SimRank [(31)]) information. More recently, random-walk based graph embedding methods, which learn vector representations for nodes [(22; 27; 57)], have achieved promising results in graph machine learning tasks. Popular embedding approaches, such as DeepWalk [(57)] and node2vec [(22)], have been shown to implicitly approximate the Pointwise Mutual Information similarity [(59)], which can also be used as a link prediction heuristic. This has motivated the investigation of other similarity metrics such as Autocovariance [(17; 27; 28)]. However, these heuristics are unsupervised and cannot take advantage of data beyond the topology.

**Graph Neural Networks for link prediction.** GNN-based link prediction addresses the limitations of topological heuristics by training a neural network to combine topological and attribute information and potentially learn new heuristics. GAE [(34)] combines a graph convolution network [(35)] and an inner product decoder based on node embeddings for link prediction. SEAL [(89)] models link prediction as a binary subgraph classification problem (edge/non-edge), and follow-up work (e.g., SHHF [(42)], WalkPool [(55)]) investigates different pooling strategies. Other recent approaches for GNN-based link prediction include learning representations in hyperbolic space (e.g., HGCN [(11)], LGCN [(91)]), generalizing topological heuristics (e.g., Neo-GNN [(88)], NBFNet [(97)]), and incorporating additional topological features (e.g., TLC-GNN [(81)], BScNets [(13)]). Motivated by the growing popularity of GNNs for link prediction, this work investigates key questions regarding their training, evaluation, and ability to learn effective topological heuristics directly from data. We propose Gelato, which is simpler, more accurate, and faster than the state-of-the-art GNN-based link prediction methods.

**Graph learning.** Gelato learns a graph that combines topological and attribute information. Our goal differs from generative models [(23; 40; 87)], which learn to sample from a distribution over graphs. Graph learning also enables the application of GNNs when the graph is unavailable, noisy, or incomplete (for a recent survey, see [(93)]). LDS [(19)] and GAug [(94)] jointly learn a probability distribution over edges and GNN parameters. IDGL [(14)] and EGLN [(83)] alternate between optimizing the graph and embeddings for node/graph classification and collaborative filtering. [(69)] proposes two-stage link prediction by augmenting the graph as a preprocessing step. In comparison, Gelato effectively learns a graph in an end-to-end manner by minimizing the loss of a topological heuristic.

## 6. Conclusion

This work sheds light on key limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem and presents more effective and efficient ways to combine attributes and topology. Our findings might open new research directions on machine learning for graph data, including a better understanding of the advantages of increasingly popular and sophisticated deep learning models compared to more traditional and simpler graph-based solutions.

###### Acknowledgements.

 This work is partially funded by NSF via grant IIS 1817046 and DTRA via grant HDTRA1-19-1-0017.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & Cora & CiteSeer & PubMed & Photo & Computers \\ \hline \(\eta\) & 0.5 & 0.75 & 0.0 & 0.0 & 0.0 \\ \(\alpha\) & 0.5 & 0.5 & 0.0 & 0.0 & 0.0 \\ \(\beta\) & 0.25 & 0.5 & 1.0 & 1.0 & 1.0 \\ \hline \hline \end{tabular}
\end{table}
Table 4. Selected hyperparameters of Gelato.

Figure 8. Performance of Gelato with different \(\alpha\) and \(\beta\).

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & Cora & CiteSeer & PubMed & Photo & Computers \\ \hline _Gelato–MLP_ & 2.43 \(\pm\) 0.00 & 2.65 \(\pm\) 0.00 & 2.50 \(\pm\) 0.00 & 16.63 \(\pm\) 0.00 & 11.64 \(\pm\) 0.00 \\ _Gelato–AC_ & 1.94 \(\pm\) 0.18 & 3.91 \(\pm\) 0.37 & 0.83 \(\pm\) 0.05 & 7.45 \(\pm\) 0.44 & 4.09 \(\pm\) 0.16 \\ _Gelato–NP+UT_ & 2.98 \(\pm\) 0.20 & 1.96 \(\pm\) 0.11 & 2.35 \(\pm\) 0.24 & 14.87 \(\pm\) 1.41 & 9.77 \(\pm\) 2.67 \\ _Gelato–NP_ & 1.96 \(\pm\) 0.01 & 1.77 \(\pm\) 0.20 & 2.32 \(\pm\) 0.16 & 19.63 \(\pm\) 0.38 & 9.84 \(\pm\) 4.42 \\ _Gelato–UT_ & 3.07 \(\pm\) 0.01 & 1.95 \(\pm\) 0.05 & 2.52 \(\pm\) 0.09 & 23.66 \(\pm\) 1.01 & 11.59 \(\pm\) 0.35 \\ _Gelato_ & **3.90 \(\pm\) 0.03** & **4.55 \(\pm\) 0.02** & **2.88 \(\pm\) 0.09** & **25.68 \(\pm\) 0.53** & **18.77 \(\pm\) 0.19** \\ \hline \hline \end{tabular}
\end{table}
Table 3. Results of the ablation study based on AP scores. Each component of Gelato plays an important role in enabling state-of-the-art link prediction performance.