Machine learning on graphs supports various structured-data applications including social network analysis [42,64,74], recommender systems [33,52,77], natural language processing [66,72,86], and physics modeling [17,32,68]. Among the graph-related tasks, one could argue that link prediction, which consists of predicting missing or future links [47,50], is the most fundamental one. This is because link prediction not only has many concrete applications [45,62] but can also be considered an (implicit or explicit) step of the graph-based machine learning pipeline [2,49,80]-as the observed graph is usually noisy and/or incomplete.
Graph Neural Networks (GNNs) [26,40,76] have emerged as the predominant paradigm for machine learning on graphs. Similar to their great success in node classification [41,81,96] and graph classification [28,53,87,91], GNNs have been shown to achieve state-of-the-art link prediction performance [10,46,59,79,89,90]. Compared to classical approaches that rely on expert-designed heuristics to extract topological information (e.g., Common Neighbors [55], Adamic-Adar [1], Preferential Attachment [4]), GNNs can naturally incorporate attributes and are believed to be able to learn new effective heuristics directly from data via supervised learning.
However, we argue that the evaluation of GNN-based link prediction methods paints an overly optimistic view of their model performance. Most real graphs are sparse and have a modular structure [3,54]. In Cora and Citeseer (citation networks), less than 0.2% of the node pairs are links/positive (see Table 1) and modules arise around research topics. Yet GNN-based link prediction methods are evaluated on an artificially balanced test set that includes every positive pair but only a small sample of the negative ones chosen uniformly at random [27]. Due to modularity, the majority of negative pairs sampled are expected to be relatively far from each other (i.e. across different modules) compared to positive pairs. As a consequence, performance metrics reported for this balanced setting, which we call biased testing, differ widely from the ones observed for the more challenging unbiased testing, where the test set includes every disconnected pair of nodes. In particular, we have found that unsupervised topological heuristics are more competitive in the unbiased setting, often outperforming recent GNN-based link prediction methods. This finding has motivated us to rethink the design of link prediction methods for sparse graphs.
A key hypothesis of our work is that effective unbiased link prediction in sparse graphs requires a similarity metric that can distinguish positive pairs from hard negative ones. More specifically, link prediction should be seen as a "needle in the haystack" type of problem, where extreme class imbalance makes even the most similar pairs still more likely to be negative. Existing GNN-based approaches fail in this sparse regime due to (1) their use of a binary classification loss that is highly sensitive to class imbalance; (2) their biased training that mimics biased testing; (3) their inability to learn effective topological heuristics directly from data.
The goal of this paper is to address the key limitations of GNNs for link prediction mentioned above. We present Gelato, a novel similarity-based framework for link prediction that combines a topological heuristic and graph learning to leverage both topological and attribute information. Gelato applies a ranking-based N-pair loss and partitioning-based negative sampling to select hard training node pairs. Extensive experiments demonstrate that our model significantly outperforms state-of-the-art GNNs in both accuracy and scalability. Figure 1 provides an overview of our approach.
To summarize, our contributions are: (1) We scrutinize the evaluation of supervised link prediction methods and identify their limitations in handling class imbalance; (2) we propose a simple, effective, and efficient framework to combine topological and attribute information for link prediction in an innovative fashion;
(3) we introduce an N-pair link prediction loss that we show to be more effective at addressing class imbalance; and (4) we propose an efficient partitioning-based negative sampling scheme that improves link prediction generalization in the sparse setting.
Supervised link prediction is often formulated as binary classification, where the positive (or negative) class includes node pairs connected (or not connected) by a link. A key difference between link prediction and other classification problems is that the two classes in link prediction are extremely imbalanced as most graphs of interest are sparse-e.g. the datasets from Table 1 are significantly more imbalanced than those in [75]. However, the class imbalance is not properly addressed in the evaluation of existing approaches.
Existing link prediction methods [8,11,14,39,59,83,90,92,99] are evaluated on a test set containing all positive test pairs and only an equal number of random negative pairs. Similarly, the Open Graph Benchmark (OGB) ranks predicted links against a very small sample of random negative pairs. We term these approaches biased testing as they highly overestimate the ratio of positive pairs in the graph. This issue is exacerbated in most real graphs, where community structure [56] causes random negative pairs to be particularly easy to identify [43]-they likely involve members of different communities. Evaluation metrics based on biased testing provide an overly optimistic assessment of the performance in unbiased testing, where every negative pair is included in the test set. In fact, in real applications where positive test edges are not known a priori, it is impossible to construct those biased test sets to begin with.
Regarding evaluation metrics, 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,14,39,59,83,90,92,99]. We first argue that, as in other imbalanced classification problems [18,67], 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 rankbased metrics such as Hits@𝑘-used in OGB [27]-are effective for imbalanced classification but only if evaluated on an unbiased test.
Example: Consider an instance of Stochastic Block Model (SBM) [35] with 10 blocks of size 1k, intra-block density 0.9, and interblock density 0.1. The number of inter-block negative pairs is 10 × 1k × (10 -1) × 1k × (1 -0.1)/2 = 40.5M, while the number of intra-block negative pairs, which have high topological similarities like the ground-truth positive pairs and are much harder to contrast against, is 10 × 1k × 1k × (1 -0.9)/2 = 0.5M. Biased testing would select less than 0.5M/(0.5M + 40.5M) < 2% of the test negative pairs among the (hard) intra-block ones. In this scenario, even a random classifier is expected to obtain 50% precision. However, the expected precision drops to less than 22% (9M positive pairs vs. 41M negative pairs) under unbiased testing.
We will formalize the argument used in the example above by performing link prediction on a generic instance of the SBM with intra-block density 𝑝, inter-block density 𝑞, where 𝑝 > 𝑞, and 𝑘 blocks of size 𝑛. In particular, we will consider an instance of SBM corresponding to the expected node pattern given the parameters, where a node is connected to (𝑛 -1)𝑝 other nodes within its block and (𝑛𝑘 -𝑛)𝑞 nodes outside its block. In this setting, the optimal link prediction algorithm can only distinguish potential links within or across blocks-as pairs within each set are connected with probability 𝑝 and 𝑞, respectively.
The ratio 𝛼 between inter-cluster and intra-cluster negative node pairs in the SBM is such that:
The above lemma follows directly from the definition of the SBM and shows that the set of negative pairs is dominated by (easy) inter-cluster pairs as 𝑝 increases compared to 𝑞. Theorem 2.1. In the unbiased setting, the optimal accuracy link prediction method based on binary classification for the SBM predicts no links if 𝑝 < 0.5.
The proof is given in the Appendix B. Intuitively, even if the classifier has access to the SBM block structure, most within-block pairs are disconnected and thus the accuracy is maximized if no links are predicted. On the other hand, if 𝑝 > 𝑞, an effective link prediction method should be able to leverage the SBM block structure to predict within block links. This motivates our formulation of link prediction as a "needle in the haystack" type of problem, where even the top candidate links (i.e., within-block pairs) are still more likely to be negative due to the sparsity of the graph. Lemma 2. In the biased setting, there exist non-trivial link prediction methods with optimal accuracy based on binary classification for the SBM with 𝑝 < 0.5.
The proof is given in the Appendix C. The idea is that in the biased setting, a link prediction method that predicts within-block pairs as links can outperform the trivial classifier described in Theorem 2.1. This illustrates how biased testing, which is applied by recent work on supervised link prediction, can be misleading for sparse graphs. More specifically, a model trained under the biased setting might perform poorly if evaluated in the, more realistic, unbiased setting due to possibly unforeseen distribution shifts across the settings. This is a key motivation for our work.
The above discussion motivates a more representative evaluation setting for supervised link prediction. We argue for the use of rankbased evaluation metrics-AP, Precision@𝑘 [47], and Hits@𝑘 [5]with unbiased testing, where positive edges are ranked against hard negative node pairs. These metrics have been widely applied in related problems, such as unsupervised link prediction [30,47,57,93], knowledge graph completion [5,73,84], and information retrieval [69], 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.
The limitations of supervised link prediction methods, including GNNs, to handle unbiased testing in sparse graphs motivate the design of a novel link prediction approach. First, preliminary results (see Table 2) have shown that topological heuristics are not impacted by class imbalance. That is because these heuristics are sensitive to small differences in structural similarity between positive and hard negative pairs while not relying on any learning-and thus not being affected by biased training. However, local structure proximity heuristics, such as Common Neighbors, are known to be less efficient in highly sparse scenarios observed in many realworld applications [48]-Table 1 shows the sparsity of our datasets. Further, unlike GNNs, topological heuristics are unable to leverage attribute information. Our approach addresses these limitations by integrating supervision into a powerful topological heuristic to leverage attribute data via graph learning.
Notation and problem. Consider an attributed graph 𝐺 = (𝑉 , 𝐸, 𝑋 ), where 𝑉 is the set of 𝑛 nodes, 𝐸 is the set of 𝑚 edges (links), and 𝑋 = (𝑥 1 , ..., 𝑥 𝑛 ) 𝑇 ∈ R 𝑛×𝑟 collects 𝑟 -dimensional node attributes. The topological (structural) information of the graph is represented by its adjacency matrix 𝐴 ∈ R 𝑛×𝑛 , with 𝐴 𝑢𝑣 > 0 if an edge of weight 𝐴 𝑢𝑣 connects nodes 𝑢 and 𝑣 and 𝐴 𝑢𝑣 = 0, otherwise. The (weighted) degree of node 𝑢 is given as 𝑑 𝑢 = 𝑣 𝐴 𝑢𝑣 and the corresponding degree vector (matrix) is denoted as 𝑑 ∈ R 𝑛 (𝐷 ∈ R 𝑛×𝑛 ). The volume of the graph is vol(𝐺) = 𝑢 𝑑 𝑢 . Our goal is to infer missing links in 𝐺 based on its topological and attribute information, 𝐴 and 𝑋 .
Model overview. Figure 1 provides an overview of our model. It starts by selecting training node pairs using a novel partitioningbased negative sampling scheme. Next, a topology-centric graph learning phase 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 attributeenhanced graph to obtain a pairwise score matrix. Node pairs with the highest scores are predicted as 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 name our model Gelato (Graph enhancement for link prediction with autocovariance). Gelato represents a different paradigm in supervised link prediction combining a graph encoding of attributes with a topological heuristic instead of relying on node embeddings. While the building blocks of Gelato have been proposed by previous work, our paper is the first to apply these building blocks to address challenges in supervised link prediction for sparse graphs.
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 propose graph learning as a more suitable scheme to combine attributes and topology for link prediction since it does not rely on the GNN to learn a topological heuristic, which we have verified empirically to be a challenge.
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 𝜖-neighborhood graph):
where 𝑠 (•) can be any similarity function (we use cosine in our experiments) and 𝜖 𝜂 is a threshold that determines the number of added pairs as a ratio 𝜂 of the original number of edges 𝑚.
A simple MLP then maps the pairwise node attributes into a trained edge weight for every edge in 𝐸:
where [𝑥 𝑢 ; 𝑥 𝑣 ] denotes the concatenation of 𝑥 𝑢 and 𝑥 𝑣 and 𝜃 contains the trainable parameters. For undirected graphs, we instead use the following permutation invariant operator [13]:
The final weights of the enhanced graph are a combination of the topological, untrained, and trained weights:
where 𝛼 and 𝛽 are hyperparameters. The enhanced adjacency matrix 𝐴 is then fed into a topological heuristic for link prediction introduced in the next section. 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. Further, 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.
Assuming that the learned adjacency matrix 𝐴 incorporates structural and attribute information, Gelato applies a topological heuristic to 𝐴. Specifically, we generalize Autocovariance, which has been shown to be effective for non-attributed graphs [30], to the attributed setting. Autocovariance is a random-walk-based similarity metric. Intuitively, it measures the difference between the co-visiting probabilities for a pair of nodes in a truncated walk
Autocovariance R w uv u v MLP(θ) a b Graph learning Topological heuristic N-pair loss Link ranking Sec. 3.1 Sec. 3.2 Sec. 3.3 L(θ) Eq. 8 R(a,b) ✗ ✗ ✗ ✗ ✓ Negative sampling Sec. 3.4
Figure 1: Gelato applies graph learning to incorporate attribute information into the topology. 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 over node pairs selected via a partitioning-based negative sampling scheme. Experiments show that Gelato outperforms state-of-the-art GNN-based link prediction methods.
and in an infinitely long walk. Given the enhanced graph 𝐺, the Autocovariance similarity matrix 𝑅 ∈ R 𝑛×𝑛 is given as
where 𝑡 ∈ N 0 is the scaling parameter of the truncated walk. Each entry 𝑅 𝑢𝑣 represents a similarity score for node pair (𝑢, 𝑣), and top similarity pairs are predicted as links. Note that 𝑅 𝑢𝑣 only depends on the 𝑡-hop enclosing subgraph of (𝑢, 𝑣) and can be easily differentiated with respect to the edge weights in the subgraph. Gelato could be applied with any differentiable topological heuristics or even a combination of them. In our experiments (Section 4.3), we will show that Autocovariance alone enables state-of-the-art link prediction without requiring any learning.
Autocovariance versus other heuristics. Following [48], we show that local structural heuristics commonly employed by GNNs, such as Common Neighbors, exhibit reduced efficacy in sparse networks with less informative neighborhood structures. This observation motivates our selection of Autocovariance as our topological heuristic, given its ability to capture global structural patterns through random walks. Further, the parameter 𝑡 in Autocovariance offers adaptability to varying network sparsity levels [48], ranging from denser (lower 𝑡 values) to sparser (higher 𝑡 values) networks.
Autocovariance distinguishes negative pairs. Autocovariance can be seen as a general case of the Modularity metric 𝑄 [19]:
in which 𝑚 = vol(𝐺)/2, 𝑑 𝑖 and 𝑑 𝑗 are the degrees of nodes 𝑖 and 𝑗, and 𝑠 𝑖 𝑠 𝑗 is a product that indicates whether both nodes are in the same partition. More specifically, for 𝑡 = 1, Autocovariance expresses the graph partitioning resulting in the optimal Modularity value, which captures the relationship between the expected number of edges between two partitions compared to the probability of any random edge in the graph. This key property directly applies to our scenario, enabling Gelato to distinguish between hard (same partitions) and easy (different partitions) negative pairs and motivating us to adopt Autocovariance as our graph heuristic. Further, as 𝑡 increases, Autocovariance expresses growing coarser partitions We represent sparse tensors (1 and 2) as matrices with blank entries and dense tensors (3 and 4) as color-filled matrices. We extract from the enhanced transition matrix (1) a slice 𝑃 0 (2) given a batch of node indices 𝑉 𝑏𝑎𝑡𝑐ℎ . Instead of a matrix exponentiation, we compute 𝑃 0 ( 𝐷 -1 𝐴) repeatedly for 𝑡 times to obtain 𝑃 𝑘 (3), a dense tensor. Finally, we use 𝑃 𝑘 to obtain the autocovariance 𝑅 (4) for nodes in the batch. This is implemented efficiently using dense-sparse tensor multiplication.
until approximating spectral clustering (for 𝑡 → ∞), being flexible regarding partition sizes according to different domains. Scaling up Gelato with batching and sparse operations. Naively implementing Gelato using dense tensors is infeasible, due to the quadratic VRAM requirement (𝑅 ∈ R |𝑉 | × |𝑉 | ). To address this limitation, we propose storing 𝐴 as a sparse matrix. Then, instead of directly computing ( 𝐷 -1 𝐴) 𝑡 from Equation 5(resulting on a dense |𝑉 | × |𝑉 | matrix), we compute
where 𝑃 0 = ( 𝐷 -1 𝐴) 𝑖 𝑗 , for all 𝑖 ∈ 𝑉 𝑏𝑎𝑡𝑐ℎ , where 𝑉 𝑏𝑎𝑡𝑐ℎ consists of the nodes in the current batch. This operation substitution allows us to compute a sequence of 𝑡 multiplications between a dense
Supervised link prediction methods rely on the cross entropy loss (CE) to optimize model parameters. However, CE is known to be sensitive to class imbalance [7]. Instead, Gelato leverages the N-pair loss [71] that is inspired by the metric learning and learning-torank literature [9,51,65,78] to train the parameters of our graph learning model from highly imbalanced unbiased training data.
The N-pair loss (NP) contrasts each positive training edge (𝑢, 𝑣) against a set of negative pairs 𝑁 (𝑢, 𝑣). It is computed as follows:
Intuitively, 𝐿(𝜃 ) is minimized when each positive edge (𝑢, 𝑣) has a much higher similarity than its contrasted negative pairs: 𝑅 𝑢𝑣 ≫ 𝑅 𝑝𝑞 , ∀(𝑝, 𝑞) ∈ 𝑁 (𝑢, 𝑣). Compared to CE, NP is more sensitive to negative pairs that have comparable similarities to those of positive pairs-they are more likely to be false positives. While NP achieves good performance in our experiments, alternative losses from the learning-to-rank literature [6,23,82] could also be applied.
Supervised methods for link prediction sample a small number of negative pairs uniformly at random but most of these pairs are expected to be easy (see Section 2). To minimize distribution shifts between training and test, negative samples 𝑁 (𝑢, 𝑣) should ideally be generated using unbiased training (see additional example in Appendix A). This means that 𝑁 (𝑢, 𝑣) is a random subset of all disconnected pairs in the training graph, and |𝑁 (𝑢, 𝑣)| is proportional to the ratio of negative pairs. In this way, we enforce 𝑁 (𝑢, 𝑣) to include hard negative pairs. However, due to graph sparsity (see Table 1), this approach does not scale to large graphs as the total number of negative pairs would be 𝑂 (|𝑉 | 2 -|𝐸|). Considering Lemma 3 (see proof in the Appendix D), we argue that it is unlikely for an inter-block pair to be ranked within the top Autocovariance pairs, implying that removing these pairs from training would not affect the results. To efficiently generate a small number of hard negative pairs, we propose a novel negative sampling scheme for link prediction based on graph partitioning [16,21]. The idea is to select negative samples inside partitions (or communities) as they are expected to have similarity values comparable to positive pairs. We adopt METIS [36] as our graph partitioning method due to its scalability and its flexibility to generate partitions of a size given as a parameter. METIS' partitions are expected to be densely connected inside and sparsely connected across (partitions). We apply METIS to obtain 𝑘 partitions in which ∀𝑖 ∈ {1, 2, ..., 𝑘 } : 𝐺 𝑖 = (𝑉 𝑖 , 𝐸 𝑖 , 𝑋 𝑖 ), 𝑉 𝑖 ⊂ 𝑉 , 𝐸 𝑖 ⊂ 𝐸, 𝑋 𝑖 ⊂ 𝑋 , such that 𝑉 = 𝑘 𝑖=1 𝑉 𝑖 and |𝑉 𝑖 | ≈ |𝑉 |/𝑘. Then, we apply unbiased training only within each partition, reducing the number of sampled negative pairs to
Following Lemma 4 (see proof on Appendix E), the choice of the value of 𝑘 should consider a trade-off between training speed and link prediction performance (see Appendix 4.3). Further, the algorithm proposed by [56] could be adopted to find the optimal value of 𝑘 that maximizes the Modularity gain while obtaining the minimal training time. In the remainder of the paper, we refer to this approach as partitioned training. We claim that this procedure filters (easy) pairs consisting of nodes that would be too far away in the network topology from training while maintaining the more informative (hard) pairs that are closer and topologically similar, according to METIS. We include in the Appendix 4.3 (See Figure 5) a performance comparison between Gelato trained using unbiased training against partitioned training.
In this section, we provide empirical evidence supporting our claims about supervised link prediction, demonstrate the accuracy and efficiency of Gelato, and present ablation studies. The implementation is available on Anonymous GitHubfoot_0 .
Datasets. Our method is evaluated on five attributed graphs commonly used for link prediction [11,14,27,59,83,92,99]. Table 1 shows dataset statistics. Baselines. For GNN-based link prediction, we include four stateof-the-art methods published in the past two years: Neo-GNN [89], BUDDY [10], and NCN / NCNC [79], as well as the pioneering work-SEAL [90]. For topological link prediction heuristics, we consider Common Neighbors (CN) [55], Adamic Adar (AA) [1], Personalized PageRank (PPR) [58], and Autocovariance (AC) [30]the base heuristic in our model. For comparison with older baselines, please refer to an earlier preprint version of our paper [29].
Hyperparameters. For Gelato, we tune the proportion of added edges 𝜂 from {0.0, 0.25, 0.5, 0.75, 1.0}, the topological weight 𝛼 from {0.0, 0.25, 0.5, 0.75}, and the trained weight 𝛽 from {0.25, 0.5, 0.75, 1.0}. All other settings are fixed across datasets: MLP with one hidden layer of 128 neurons, AC scaling parameter 𝑡 = 3, Adam optimizer [38] with a learning rate of 0.001, a dropout rate of 0.5, and unbiased training without downsampling. To maintain fairness in our results, we also tuned the baselines and exposed our procedures in detail in Appendix F. For all models, including Gelato, the tuning process is done in all datasets, except for ogbl-collab. Data splits for unbiased training and unbiased testing. Following [11,14,39,59,90,92], we adopt 85%/5%/10% ratios for training, validation, and testing. Specifically, for unbiased training and unbiased testing, we first randomly divide the (positive) edges 𝐸 of the original graph into 𝐸 + 𝑡𝑟𝑎𝑖𝑛 , 𝐸 + 𝑣𝑎𝑙𝑖𝑑 , and 𝐸 + 𝑡𝑒𝑠𝑡 for training, validation, and testing based on the selected ratios. Then, we set the negative pairs in these three sets as (1) 𝐸 - 𝑡𝑟𝑎𝑖𝑛 = 𝐸 -+ 𝐸 + 𝑣𝑎𝑙𝑖𝑑 + 𝐸 + 𝑡𝑒𝑠𝑡 , (2) 𝐸 - 𝑣𝑎𝑙𝑖𝑑 = 𝐸 -+ 𝐸 + 𝑡𝑒𝑠𝑡 , and (3) 𝐸 - 𝑡𝑒𝑠𝑡 = 𝐸 -, where 𝐸 -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 in the negative validation set. This setting simulates the real-world scenario where the test edges (and the validation edges) are unobserved during validation (training). For negative sampling, we repeat the dividing procedure above for each generated partition 𝐺 𝑖 . The final sets are unions of individual sets for each partition: 𝐸
, and 𝐸
𝑡𝑒𝑠𝑡 𝑖 . We notice that these splits do not leak training data to the test, as both positive and negative test pairs are disconnected during training. Evaluation metrics. We adopt ℎ𝑖𝑡𝑠@𝑘 -the ratio of positive edges individually ranked above 𝑘th place against all negative pairs-as our evaluation metric since it represents a good notion of class distinction under heavily imbalanced scenarios in information retrieval, compatible with the intuition of link prediction as a similarity-based ranking task.
This section provides empirical evidence for some of the claims made regarding limitations in the evaluation of supervised link prediction methods (see Section 2). It also demonstrates the effectiveness of Gelato to distinguish true links from hard negative node pairs in sparse graphs.
Negative sampling for harder pairs. Based on the hardness of negative pairs, the easiest scenario is the biased testing, followed by unbiased testing and partitioned testing-i.e. only negative pairs from inside partitions are sampled. This can be verified by Figure 3, which compares the predicted scores of NCN against the similarities computed by Gelato on the test set of CiteSeer. Biased testing, the easiest and most unrealistic scenario, shows a good separation between positive and negative pairs both in NCN and Gelato. For unbiased testing, which is more realistic, Gelato is better at distinguishing positive and negative pairs. Finally, partitioned testing presents a particular challenge but Gelato still ranks most positive pairs above negative ones. Other GNN-based link prediction approaches have shown similar behaviors to NCN. Similarity-based link prediction. Figure 3 shows densities normalized by the size of positive and negative sets, respectively. However, in real-world sparse graphs, the number of negative pairs is much larger than that of positive ones. The results show that for unbiased and partitioned testing, ranking positive pairs over hard negative pairs is especially challenging due to their overwhelming number, i.e. positive pairs are "needles in a haystack". This provides evidence that classifiers, such as GNNs for link prediction, are not suitable for finding decision boundaries in these extremely imbalanced settings, which motivates the design of Gelato as a similarity ranking model trained using an N-pair loss.
Table 2 summarizes the link prediction performance in terms of the mean and standard deviation of ℎ𝑖𝑡𝑠@1000 for all methods. We show the same results for varying values of 𝑘 in Figure 4. First, we want to highlight the drastically different performance of GNN-based methods compared to those found in the original papers [10,79,89,90]. Some of them underperform even the simplest topological heuristics such as Common Neighbors under unbiased testing. Moreover, Autocovariance, which is the base topological heuristic applied by Gelato and does not account for node attributes, outperforms all the GNN-based baselines for the majority of the datasets. 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 NCNC, which generalizes a pairwise topological heuristic (Common Neighbors) using message-passing. NCNC only outperforms Gelato on OGBL-ddi, which is consistent with previous results [48] showing that local structural heuristics are effective for very dense networks (see Table 1). Moreover, OGBL-ddi is the only dataset considered that does not contain natural node features, which explains why our approach achieves the same performance as AC. Gelato also remains superior for different values of ℎ𝑖𝑡𝑠@𝐾, especially for Cora, CiteSeer and OGBL-collab, and being remains competitive for OGBL-ddi being competitive as shown in Figure 4. This characteristic is especially relevant in real-world scenarios where robustness is desired, mainly in more conservative regimes with lower values of 𝑘. Overall, Gelato outperforms the best GNN-based method by 138%, 125%, 156%, and 11% for Cora, Citeseer, Pubmed, and OGBL-collab, respectively. Further, Gelato outperforms its base topological heuristic (Autocovariance) by 48%, 39%, 10%, and 139% for Cora, Citeseer, Pubmed, and OGBL-collab, respectively. Unbiased Training vs. Partitioned Training. Figure 5 compares partitioned and unbiased training on CiteSeer using hits@K for varying 𝐾. Results show minimal performance differences, even in extreme partitioning scenarios, while partitioned sampling achieves a significant speedup-training up to 6x faster and scaling with the number of partitions. Unbiased training requires 𝑂 (𝑉 2 -𝐸) for sparse graphs due to extensive negative sampling, whereas partitioned sampling reduces this to 𝑂 (
, where (𝑉 𝑖 , 𝐸 𝑖 ) are nodes and edges within partition 𝑖. Experiments confirm that performance is largely insensitive to different values of 𝑝.
Here, we collect the results with the same hyperparameter setting as Gelato and present an ablation study in Table 3. 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.
10 -3 10 -1 10 1 10 3 Similarity 0.0 0.2 0.4 0.6 0.8 Density Gelato -Biased 10 -5 10 -3 10 -1 10 1 Similarity 0.0 0.2 0.4 0.6 0.8 Density Gelato -Unbiased 10 -5 10 -4 10 -3 10 -2 10 -1 10 0 10 1 10 2 Similarity 0.0 0.2 0.4 0.6 0.8 Density Gelato -Partitioned 10 -2 10 -1 10 0 10 1 10 2 Score 0.0 0.5 1.0 1.5 2.0 2.5 3.0 Density NCN -Biased 10 -4 10 -3 10 -2 10 -1 10 0 10 1 Score 0.0 0.5 1.0 1.5 2.0 Density NCN -Unbiased 10 -3 10 -2 10 -1 10 0 10 1 Score 0 5 10 15 20 Density NCN -Partitioned Positive Negative 0 200 400 600 800 1000 K 0 5 10 15 Hits@K Cora 0 200 400 600 800 1000 K 0 5 10 15 20 Hits@K CiteSeer 0 200 400 600 800 1000 K 0 5 10 15 20 25 30 Hits@K OGBL-Collab 0 200 400 600 800 1000 K 0.0 0.2 0.4 0.6 0.8 Hits@K OGBL-DDI Gelato NCN NCNC BUDDY SEAL NeoGNN
Figure 4: Link prediction comparison in terms of ℎ𝑖𝑡𝑠@𝑘 varying 𝑘 using Cora, CiteSeer, OGBL-DDI and OGBL-Collab. All datasets were split using unbiased sampling, except OGBL-Collab, which was split using partitioned sampling. Gelato outperforms the baselines across different values of 𝑘 and remains competitive on OGBL-DDI, a dataset in which all methods struggle. Table 2: Link prediction performance comparison (mean ± std hits@1000) for all datasets considered. Gelato consistently outperforms GNN-based methods, topological heuristics, and two-stage approaches combining attributes/topology. For Cora, CiteSeer, ogbl-ddi and PubMed results we used unbiased training, while for ogbl-collab partitioned sampling is used, for scalability reasons. The top three models are colored by First, Second and Third.
Cora CiteSeer PubMed ogbl-ddi ogbl-collab GNN SEAL 0.0 * 7.25 * *** 0.75 * 25.9 * Neo-GNN 6.96 ± 4.24 5.42 ± 0.13 1.63 ± 0.32 0.76 * 0.85 * BUDDY 4.81 ± 0.72 5.86 ± 0.34 OOM 0.74 ± 0.01 27.66 ± 0.24 NCN 4.11 ± 1.22 7.84 ± 1.13 0.06 ± 0.1 0.82 ± 0.02 7.16 ± 1.42 NCNC 6.58 ± 0.58 8.72 ± 2.08 1.04 ± 0.09 0.89 ± 0.09 0.44 ± 0.37 Topological Heuristics CN 4.17 ± 0.00 4.4 ± 0.00 0.36 ± 0.00 0.8 ± 0.00 2.4 ± 0.00 AA 6.64 ± 0.00 4.4 ± 0.00 1.13 ± 0.00 0.79 ± 0.00 4.88 ± 0.00 PPR 9.30 ± 0.00 6.59 ± 0.00 0.32 ± 0.00 0.08 ± 0.00 1.24 ± 0.00 AC 11.20 ± 0.00 14.29 ± 0.00 3.81 ± 0.00 0.78 ± 0.00 12.89 ± 0.00 Gelato 16.62 ± 0.31 19.78 ± 0.23 4.18 ± 0.19 0.78 ± 0.00 30.92 * * Run only once as each run takes >24 hrs; *** Each run takes >1000 hrs; OOM: Out Of Memory.
0 200 400 600 800 1000 K 0 5 10 15 20 Hits@K CiteSeer -Unbiased vs. Partitioned 50 Partitions Unbiased 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 the effective training of Gelato.
We also present results for Gelato using different ranking-based loss functions. We choose between Precision@k, pairwise hinge, pairwise exponential, and pairwise logistic losses as candidates for replacing the N-pair loss based on [12]. The results are shown in Table 4, demonstrating that there is no clear winner considering the ℎ𝑖𝑡𝑠@1000 metric in the two datasets used (Cora and CiteSeer).
We analyze hyperparameter sensitivity and its impact on performance. Figure 6 shows that optimal 𝛼 and 𝛽 values depend on dataset characteristics, though performance varies smoothly for Cora and CiteSeer, easing tuning. Figure 7 highlights diminishing returns from increasing 𝜂, as performance plateaus. 0.00 0.25 0.50 0.75 1.00 η 14 15 16 17 hits@1000 Cora 0.00 0.25 0.50 0.75 1.00 η 12 14 16 18 hits@1000 CiteSeer 3.0 3.2 3.4 3.6 3.8 AP 2.0 2.5 3.0 3.5 AP Figure 7: Performance of Gelato with different values of 𝜂, using 𝑇 = 3.
We represent hits@1000 in green and AP in blue.
An earlier preprint version of our paper is available at arXiv [29].
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 [55], Adamic Adar [1], and Resource Allocation [98]) and higher-order (e.g., Katz [37], PageRank [58], and SimRank [34]) information. More recently, random-walk based graph embedding methods, which learn vector representations for nodes [24,30,61], have achieved promising results in graph machine learning tasks. Popular embedding approaches, such as DeepWalk [61] and node2vec [24], have been shown to implicitly approximate the Pointwise Mutual Information similarity [63], which can also be used as a link prediction heuristic. This has motivated the investigation of other similarity metrics such as Autocovariance [19,30,31]. 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. These works often assume that links are correlated with homophily in node attributes [20,97], as also is the case for this paper. GAE [39] combines a graph convolution network [40] and an inner product decoder based on node embeddings. SEAL [90] models link prediction as a binary subgraph classification problem (edge/non-edge), and follow-up work (e.g., SHHF [46], WalkPool [59]) investigates different pooling strategies. Other recent approaches for GNN-based link prediction include learning representations in hyperbolic space (e.g., HGCN [11],
LGCN [92]), generalizing topological heuristics (e.g., Neo-GNN [89], NBFNet [99]), and incorporating additional topological features (e.g., TLC-GNN [83], BScNets [14]). ELPH and BUDDY [10] apply hashing to efficiently approximate subgraph-based link prediction models, such as SEAL, using a message-passing neural network (MPNN) with distance-based structural features. NCNC [79] combines the Common Neighbors heuristic with an MPNN achieving state-of-the-art results. 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 most 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 [25,44,88], 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 [94]. LDS [22] and GAug [95] jointly learn a probability distribution over edges and GNN parameters. IDGL [15] and EGLN [85] alternate between optimizing the graph and embeddings for node/graph classification and collaborative filtering. [70] 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.
This work exposes key limitations in evaluating supervised link prediction methods due to the widespread use of biased testing.
These limitations led to a consensus in the graph machine learning community that (1) GNNs are superior for link prediction, casting topological heuristics obsolete; and (2) link prediction is now an easy task due to deep learning advances. We challenge both assumptions, demonstrating that link prediction in sparse graphs remains a hard problem when evaluated properly. GNNs struggle with link prediction in sparse graphs due to extreme class imbalance, motivating Gelato, our novel link prediction framework. Gelato is a similarity-based method that combines graph learning and autocovariance to leverage attribute and topological information. Gelato employs an N-pair loss instead of cross-entropy to address the class imbalance and introduces a partitioning-based negative sampling scheme for efficient hard negative pair sampling. Through extensive experiments, we demonstrate superior accuracy and scalability of Gelato when compared to state-of-the-art GNN-based solutions across various datasets.
Example: Consider a graph with 10𝐾 nodes, 100𝐾 edges, and 99.9𝑀 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. Figures 8a and 8b show the receiver operating characteristic (ROC) and precision-recall (PR) curves for the model under biased testing with equal number of negative samples. Due to the downsampling, only 100k (out of 99.9M) negative pairs are included in the test set, among which only 100k/99.9M × 1M ≈ 1k pairs are ranked higher than the positive edges. In the ROC curve, this means that once the false positive rate reaches 1k/100k = 0.01, the true positive rate would reach 1.0, leading to an AUC score of 0.99. Similarly, in the PR curve, when the recall reaches 1.0, the precision is 100k/(1k + 100k) ≈ 0.99, leading to an overall AP score of ∼0. 95. By comparison, as shown in Figure 8c, when the recall reaches 1.0, the precision under unbiased testing is only 100k/(1M + 100k) ≈ 0.09, leading to an AP score of ∼0.05. This demonstrates that evaluation metrics based on biased testing provide an overly optimistic measurement of link prediction model performance compared to the more realistic unbiased testing setting.
There are only three classifiers that we need to consider in this setting, assuming that the classifier can recover the block structure:
(1) It predicts every disconnected pair as a link;
(2) It predicts every disconnected pair as a non-link;
(3) It predicts within-block pairs as links and across-block pairs as non-links.
The classifier 1 cannot be optimal for sparse graphs-i.e., density lower than .5-and thus we will focus on classifiers 2 and 3. We will compute the expected number of True Positives (TP), False Positives (FP), False Negatives (FN), and True Negatives (TN) per node for each of them:
We will consider the same classifiers 2 and 3 from the proof of Theorem 2.1. Moreover, we will assume that the number of sampled negative pairs is the same as the number of positive pairs (i.e., balanced sampling).
By definition, the accuracy of classifier 2 is 0.5, as all predictions for negative pairs will be correct and all those for positive pairs will be incorrect. Thus, we only have to show that there exists an SBM instance for which classifier 3 achieves better accuracy than 2.
The accuracy of classifier 3 is computed as 𝑎 1 + 𝑎 2 /2, where: It follows that, as 𝑞 → 0, classifier 3 can achieve an accuracy higher than 0.5.
Let us initially consider Autocovariance with 𝑡 = 1 computed in the Stochastic Block Model described in Lemma 3. We will adopt the entry-wise notation of the original Autocovariance definition presented in Section 3.2, using lower-case letters to represent individual entries in matrices and vectors, and for the sake of consistency with the Modularity definition, we adopt vol(𝐺) = 2𝑚. We first obtain the shortened form of Autocovariance for 𝑡 = 1:
We can obtain the expected expression value for the case where (𝑖, 𝑗) is an intra-cluster pair (E[𝑅 𝑖𝑛𝑡𝑟𝑎 ]):
Likewise, we follow the same procedure for the case where (𝑖, 𝑗) is an inter-cluster pair (E[𝑅 𝑖𝑛𝑡𝑒𝑟 ]):
-𝑑 𝑖 𝑑 𝑗 2𝑚 )(1 -𝑝) + (0 -𝑑 𝑖 𝑑 𝑗 2𝑚 )𝑝) (13) = 1 2𝑚 (1 -𝑝 -𝑑 𝑖 𝑑 𝑗 2𝑚 ) (14) = 1 2𝑚 (𝑞 -𝑑 𝑖 𝑑 𝑗 2𝑚 ). (15) Due to the reversible property of Markov chains, this holds for larger values of 𝑡. Since 𝑝 > 𝑞 =⇒ E[𝑅 𝑖𝑛𝑡𝑟𝑎 ] > E[𝑅 𝑖𝑛𝑡𝑒𝑟 ]. E Proof of Lemma 4 From Appendix D, we have E[𝑅 𝑖𝑛𝑡𝑟𝑎 ] = 1 2𝑚 (𝑝 -𝑑 𝑖 𝑑 𝑗 2𝑚 ) is solely dependent on the value of 𝑝, since all the other terms are constants. We will denominate 𝑉 𝑖𝑘 and 𝐸 + 𝑖𝑘 the number of nodes and positive pairs in the 𝑖-th partition of our graph partitioned in 𝑘 partitions. Considering the estimate 𝑝 = |𝐸 + 𝑖𝑘 | /|𝑉 𝑖𝑘 | 2 , for simplicity, the number of positive pairs we can lose by increasing 𝑘 to 𝑘 + 1 is at most |𝐸 + 𝑖𝑘+1 | ≥ |𝐸 + 𝑖𝑘 | -(|𝑉 𝑖𝑘 | 2 -|𝑉 𝑖𝑘+1 | 2 ), if we consider the extreme scenario in which every pair lost was positive. With this estimate, we can compare with the actual 𝑝 estimate: |𝐸 + 𝑖𝑘+1 | |𝑉 𝑖𝑘+1 | 2 ≥ |𝐸 + 𝑖𝑘 | -(|𝑉 𝑖𝑘 | 2 -|𝑉 𝑖𝑘+1 | 2 ) |𝑉 𝑖𝑘+1 | 2 (16)
It follows that, since the number of pairs drops faster than the number of positive edges for a given partition, E[𝑅 𝑖𝑛𝑡𝑟𝑎 ] increases when 𝑘 increases.
Positive masking. To ensure generalizability under unbiased training, we employ a trick similar to negative injection [90]. Training positive edges are divided into batches, and for each batch 𝐸 𝑏 , only the residual edges 𝐸 -𝐸 𝑏 are used as structural input to the model. This simulates testing, where edge predictions are made without leveraging their own connectivity. We term this positive masking. Implementation details. Self-loops are added to isolated nodes in the enhanced adjacency matrix to ensure valid transition probabilities for computing Autocovariance. Gelato similarity scores are standardized as in [30] before loss computation. We train the model using gradient descent with pytorch [60] and skip parameter updates for batches with invalid gradients (e.g., with cross-entropy loss). Models are selected based on 𝑝𝑟𝑒𝑐@100% on the (unbiased) validation set. Maximum epochs are set to 100 for Cora/CiteSeer and 250 for OGBL-DDI/OGBL-Collab. For partitioned testing, we use METIS [36] for its scalability and balanced partitions.
https://anonymous.4open.science/r/Gelato/