Implicit degree bias in the link prediction task
Authors: Rachith Aiyappa
Xin Wang
Munjung Kim
Ozgur Can Seckin
Yong-Yeol Ahn
Sadamori Kojaku
Venue: ICML 2025 poster (2025)
Keywords: link prediction
benchmark
bias
degree heterogeneity
Primary area: deep_learning->graph_neural_networks
TL;DR: We show that common link prediction benchmarks are biased by node degree, leading to misleading performance favoring methods which overfit to node degree. We propose a correction and highlight its advantages.

Abstract: Link prediction---a task of distinguishing actual hidden edges from random unconnected node pairs---is one of the quintessential tasks in graph machine learning. Despite being widely accepted as a universal benchmark and a downstream task for representation learning, the link prediction benchmark's validity has rarely been questioned. Here, we show that the common edge sampling procedure in the link prediction task has an implicit bias toward high-degree nodes. This produces a highly skewed evaluation that favors methods overly dependent on node degree. In fact  a ``null'' link prediction method based solely on node degree can yield nearly optimal performance in this setting. We propose a degree-corrected link prediction benchmark that offers a more reasonable assessment and better aligns with the performance on the recommendation task. Finally, we demonstrate that the degree-corrected benchmark can more effectively train graph machine-learning models by reducing overfitting to node degrees and facilitating the learning of relevant structures in graphs.

Implicit Degree Bias in the Link Prediction Task
Rachith Aiyappa'
Xin Wang? ?
Munjung Kim
Ozgur Can Seckin' Yong-Yee Yeol Ahn
Sadamori Kojaku"
Abstract
2013; Sun et al., 2019), and drug development (Wang et al.,
2015; Crichton al., 2018; You al., 2019; Ali al.,
Link prediction- the task of distinguishing ac- tual hidden edges from random unconnected node pairs-is a quintessential task in graph machine learning. Despite being widely accepted as uni- versal benchmark and downstream task for rep- resentation learning. its validity is seldom ques- tioned. Here, show that the common edge sampling procedure in link prediction introduces an implicit bias toward high-degree nodes and produces a skewed evaluation that favors methods overly reliant on node degree, to the extent that a "null" method based solely on node degree can nearly match optimal performance. To address this, propose degree-corrected link predic- tion task that offers a more accurate assessment that aligns better with performance in recommen- dation tasks. Finally, we demonstrate that this degree-corrected benchmark can more effectively train graph machine- learning models by reduc- ing overfitting to node degrees and facilitating the learning of relevant structures in graphs.
2019; Breit et al., 2020; Yue et al., 2020; Abbas et al., 2021). Link prediction benchmarks have been essential for quanti- tative evaluations, advancing graph machine learning tech- niques (Liben-Nowell & Kleinberg, 2003; Narayanan et al., 2011: Ali et al., 2019; Ghasemian et al., 2020; Mara et al., 2020; Breit al., 2020; Yue et al., 2020).
Despite its significant role in graph machine learning, the link prediction benchmark itself is rarely scrutinized for ef- fectiveness, reliability, and bias. Typically, it evaluates meth- ods based on their ability to classify node pairs as connected or unconnected (Kunegis & Lommatzsch, 2009; Ghasemian et al., 2020; Mara et al., 2020). Connected pairs (edges) are randomly sampled from existing edges as the hidden posi- tive set, while an equal number of unconnected node pairs are sampled randomly. Criticisms often highlight its discon- nect from real-world scenarios. For instance, unconnected pairs vastly outnumber connected ones because of the graph sparsity (Barabási & Pósfai, 2016; Newman, 2018), leading to biased performance evaluations (Yang et al., 2015; Wang et al., 2021; Huang al., 2023; Li et al., 2024a; Menand & Seshadhri, 2024). Additionally, the benchmark tests predefined set of edges, while real-world tasks involve iden- tifying potential edges across the entire graph. Despite this misalignment, high benchmark performance is often seen as a marker of successful learning in graph machine learn- ing (Ou et al., 2016; Grover & Leskovec, 2016; Goyal & Ferrara, 2018: Crichton al., 2018; Zhang & Chen, 201 8;; Ali et al., 2019; Breit al., 2020; Ghasemian al., 2020; Yue et al., 2020; Cai et al., 2021).
1. Introduction
Standardized benchmarks like ImageNet (Deng et al., 2009;
Krizhevsky et al., 2012) and SQuAD (Rajpurkar et al., 2016; 2018) play pivotal role in driving progress in machine learning by fostering competition through setting clear, mea- surable goals. In graph machine learning, core benchmark is link prediction, which involves identifying missing edges in a graph, with diverse applications including the recom- mendations of friends and contents (Huang et al., 2005; Kunegis & Lommatzsch, 2009; Menon Elkan, 2011; Wang et al., 2014), knowledge discoveries (Bordes et al.,
Here, we argue that the standard link prediction benchmark has a fundamental and severe bias favoring methods that exploit node degree (the number of edges a node has). This bias arises from the edge sampling process: node with k edges is l times more likely to be selected than node with single edge (k 1). Meanwhile, the negative set is randomly sampled from unconnected pairs, without this degree bias. This creates a distinct feature (degree) that methods can exploit without understanding any non-trivial structural features of the graph. We show that this degree bias is so profound that a "null" method based solely on node degree can achieve near-optimal performance, ques- tioning the benchmark's 's usefulness general objective in
"Equal contribution 'Center for Complex Networks and Sys- tems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University. Bloomington, IN, USA "School of Systems Science and Industrial Engineering, Binghamton Uni- versity, Binghamton, NY, USA. Correspondence to: Sadamori Kojaku <skojaku @ binghamton.cdu>.
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Implicit Degree Bias in the Link Prediction Task
graph machine learning and highlighting the need for being more intentional and careful about what the evaluation tasks
2.3. Sampling bias due to node degree
A well-known, counterintuitive fact about graphs is that uniform random sampling of edges introduces a degree bias in node selection (Feld, 1991; Barthélemy et al., 2004; Christakis & Fowler, 2010; Kojaku et al., 2021a;b). The bias arises because a node with & edges appears k times in the edge list and thus &o times more likely to be chosen than a node with k' = 1 edge (e.g., node I and in Fig. LA), Consequently, for a graph with degree distribution p(k), the nodes in the positive edges have degree distribution P (k) proportional to k. p(k). By normalizing k -p(k), the degree distribution of the positive edges is given by
themselves actually evaluate.
To address this bias, we propose a degree-corrected link prediction benchmark that samples unconnected node pairs with the same degree bias. This benchmark more accurately reflects the performance of algorithms in recommendation tasks. Moreover, it trains graph neural networks more ef- fectively by reducing overfitting to node degrees, thereby improving the learning of community structure in graphs.
2. Design flaw of the link prediction benchmark
Ppus (A) = Ee Eeep(e) k. p(k) = k p(k),
(I)
(k)
2.1. Preliminary
where (k) is the average degree. By contrast, nodes in the negative edges are uniformly sampled from the node-set V.
We focus on unweighted, undirected graph G = (V, where V is the set of nodes and E is the set of edges. We assume that G has no self-loops, no multiple edges, and is highly sparse (EE) < [V|²), a common characteristic of real- world graphs (Barabási & Pósfai, 2016; Newman, 2018). Degree k of a node i E V is the number of edges connected to it. We use ~ to denote proportional relationships. Node attributes, if present, are excluded to maintain consistency across all link prediction methods.
resulting in a degree distribution Pneg(k) identical to p(k)
(i.c., Paeg (A: = =.())).
We demonstrate the degree bias using the Price graph with N 100 nodes and M 10 edges, which follows power-law degree distribution p(k) x k-3 (Fig. IB). We uniformly sample 8 = 0.25 of the edges from E as posi- tive edges, together with an equal number of unconnected node pairs sampled uniformly from V. The degree distribu- tions for nodes in the positive and negative edges align with Ppes (k) and Pneg (k), respectively, confirming the sampling bias due to node degree. This degree bias is not specific to the Price graph but occurs in any graph with non-uniform degree distribution.
2.2. Link prediction benchmark
The standard link prediction benchmark procedure is as fol- lows (Kunegis& & Lommatzsch, 2009; Grover & Leskovec, 2016; Ou et al., 2016; Zhang& & Chen, 2018; Crichton et al., 2018; Goyal & Ferrara, 2018; Ali et al., 2019; Breit et al.,
2020; Yue et al., 2020; Cai et al., 2021). First, a fraction 3 of edges is randomly sampled from the edge set E as positive edges. Second, an equal number of unconnected node pairs is randomly sampled with replacement from the node-set V as negative edges. Negative edges are resampled if they form a loop or are already in the positive or test edges. Third, each node pair (i,j) is scored by a link prediction method, where a higher score 8ij indicates a greater likelihood of an edge. Fourth, the method's effectiveness evaluated using the Area Under the Receiver Operating Characteristic Curve (AUC-ROC), which represents the probability that the method gives a higher score to a positive edge than a negative edge. While alternative benchmark designs use different evaluation metrics or sampling strategies for neg- ative edges (Yang et al., 2015; Wang et al., 2021; Wang & Derr, 2022; Huang et al., 2023; Russo et al., 2024; He et al., 2024; Li et al., 2024a; Menand & Seshadhri, 2024) (Sec- tion 4). this outlined procedure is widely adopted (Kunegis & Lommatzsch, 2009; Grover & Leskovee, 2016; Ou et al., 2016; Goyal& & Ferrara, 2018; Zhang& & Chen, 2018; Crich- ton et al., 2018; Ali et al., 2019; Breit et al., 2020; Yue et al., 2020: Ghasemian et al., 2020).
2.4. Impact of degree bias on the link prediction benchmark
We demonstrate the impact of degree bias on link prediction benchmarks (Fig. ID) by evaluating 29 link prediction meth- ods across 95 graphs from various domains, including so- cial, technological, informational, biological, and transporta- tion graphs. These methods include network topology- based methods (e.g., Common Neighbors (CN) (Liben- Nowell & Kleinberg, 2003)), 13 graph embedding methods (e.g., Laplacian EigenMap (EigenMap) (Belkin & Niyogi, 2003)), 2 network models (c.g.. Stochastic Block Model (e.g., SEM) (Fortunato, 2010)), and 4 graph neural networks (GNNs) (e.g., Graph Convolutional Network (GCN) (Kipf & Welling, 2017)). Detailed method and graph descriptions are available in Appendix A. We set the test edge fraction to B = 0.25 and repeat the experiment 5 times. We quantify the heterogeneity a of node degree by fitting log-normal distribution to p(k) and calculating its variance parameter a. We will show that a is a reliable indicator of the impact of degree bias in Section 2.5.
We focus on the Preferential Attachment (PA) link predic-
2

---

Implicit Degree Bias in the Link Prediction Task
10%
A
B
1.0-
C
10-1
AUC-ROC
0.9
CCDF
Negative edge
0.8
10
Positive edge
Pposlk]
0.7
Expected Empirical
10
Pnog(k)
10
10a
0.5
0
1.5
2.0
Nodes
Edges
Degree,
Degree heterogeneity, 0
Original
Degree corrected
D
1.0
E
0.8
0.8
AUC-ROC
0.6
0.6
6
0.4-
0.4
PA
Other methods
0.2
0.2
25
50
75
100
25
50
75
100
Degree heterogeneity, O (percentile)
Figure 1. Illustration the degree bias the link prediction benchmark. A: A node with degree appears times edge list, making it & times more likely to be sampled as positive edge than a node with degree 1. B: The degree distribution of the nodes in the positive and negative edges sampled from a Price graph of N 10 nodes and M 10 edges. The y-axis, "CCDF", denotes the complementary cumulative distribution function, representing the probability that node's degree is at least k. Dashed lines illustrate the relationship described by Eq. 1. C: The AUC-ROC score for the Preferential Attachment (PA) method on empirical graphs, with the dashed line indicating Eq. 4. D: AUC-ROC of 29 methods across 95 graphs. E: AUC-ROC of the methods for the degree-corrected benchmark.
tion method, which calculates the prediction score Sty ky using only node degrees. PA crude method that neglects key predictive features like common neighbors and shortest distance (Li et al., 2024a; Menand & Seshadhri, 2024; Lichtnwalter & Chawla, 2012; Zhang & Chen, 2018; Mao et al., 2024). However, it still outperforms most ad- vanced methods with an average AUC-ROC of 0.84 (ranked 13th out of 29 methods; see Fig. 2A). PA performs better the heterogeneity of node degrees increases. This out- performance is due to degree bias, where the positive edges are more likely to be formed by nodes with high degree and thereby are easily distinguishable from the negative edges. Thus, the current benchmark design favors methods that make predictions based largely on node degrees. This spurious performance
k- with a E (2, (i.e., scale-free networks) (Albert & Barabási, 2002; Barabási & Bonabeau, 2003; Holme, 2019; Voitalov al., 2019) log-normal distributions (Broido & Clauset, 2019; Artico et al., 2020). While the power-law and log-normal distributions are both continuous, they are often used to approximate discrete degree distribution (Johnson et al., 1995; Redner, 2005; Radicchi et al., 2008; Clauset et al., 2009; Broido & Clauset, 2019; Artico al., 2020). We show that the AUC-ROC for PA reaches near-maximum under log- log-nommal distributions with heterogeneous node degrees. See Appendix E.3 for the case of power-law distri- butions.
Let us consider a general degree distribution p(k) without restricting ourselves to log-normal distributions. The AUC- ROC has probabilistic interpretation (Hand, 2009): is the probability that the score s for positive edges is larger than the score s for negative edges. Recalling that PA computes Siz = kg the AUC-ROC for PA is given by
is evident when using Hits@ K (Appendix E.6), indicating that the issue stems from the benchmark design rather than evaluation metrics. This spu- rious performance of PA also persists for larger-scale graphs (Appendix E.4).
AUC-ROC P(s--j- S S(tj+t= P(k-kk-- S (k-kgt))
kyt). (2)
2.5. Theoretical analysis
Many empirical graphs exhibit heterogeneous degree distri- butions, with a few nodes having exceptionally large degrees and most having small ones. These distributions are of- ten characterized by plw degree distribution p(k) x
where j and j represent the nodes of the positive and negative edges, respectively. We define the degree bias by Eq 2. The AUC-ROC represents the discrepancy between the distributions of the prediction scores h; ky for nega-
3

---

Implicit Degree Bias in the Link Prediction Task
tive edges and the scores ki+ kiz+ for positive edges. If the positive edges have higher scores than the negative edges, the AUC-ROC approaches 1, indicating that node degree alone can effectively predict the positive edges. Conversely, if the positive and negative edges have similar scores, the AUC-ROC nears 0.5, indicating node degree alone is insuf- ficient for the prediction.
and negative edges, i.e., Pneg(k) + Ppos (k). To mitigate the mismatch, we introduce the degree-corrected link pre- diction benchmark that samples negative edges with the same degree bias as positive edges (See Algorithm 1 in Appendix). Specifically, we create a list of nodes where each node with degree k appears k times. Then, we sample negative edges by uniformly sampling two nodes from this list with replacement until the sampled node pairs are not connected and not in the test edge set. Crucially, nodes with degree k are k times more likely to be sampled than nodes with degree 1, mirroring the degree bias of the posi- tive edges. Consequently, the positive and negative edges in the degree- benchmark are indistinguishable based on node degrees. A Python package for the degree-corrected benchmark will be made available on GitHub.
Now, let us assume that p(k) follows the log-normal distri- bution, LogNorm(k: [4, )²), given by (Hand, 2009):
pkk)= LogNormmk p. 0²)
1
(In k 1)2
exp
(3)
V2Tak
20
where l and a are the parameters of the log-normal dis- tribution. The mean of the log-normal degree distribution is (k) exp(# + o² /2) (Hand, 2009). By leveraging unique characteristic of log-normal distributions, we obtain the AUC-ROC for PA analytically as follows. The detailed derivation is provided in Appendix B.
3.1. Comparison of the benchmark evaluations
We reevaluated the methods using the degree-corrected link prediction benchmark. maintaining the same parameters as in the original benchmark. The results show signif- icant drop in the performance of PA, with most methods having AUC-ROC scores close to 0.5 for most networks (Fig. IE). We find qualitatively the same results when using the Hits K score (Appendix E.6).
P(nn < Insst = + (o).
where + is the cumulative distribution function for the stan- dard normal distribution. We have assumed no degree as- P(k) P(ky)-
sortativity in the graph, where P(k,t, ,(k)t ) Although empirical graphs often exhibit degree assortativity, our results indicate that it does not significantly impact the AUC-ROC (Appendix E.2).
We note that our aim is not to completely eliminate degree as predictive feature but rather to remove the bias introduced by negative edge sampling. The degree can remain mean- ingful predictor after correction if it genuinely correlates with the likelihood of edges between nodes. "biokg drug' marks this point well; it has the strongest rich-club structure of all graphs (including non-OGB graphs), where 94% of edges connect the top 10% highest- nodes. In other OGB graphs, this figure is below 27%. Even after correc- tion, degree remains meaningful predictor for biokg drug (AUC-ROC of 0.9) because high-degree nodes are inher- ently more likely to be connected in this graph.
Equation 4 suggests the key behavior of AUC-ROC for PA. The AUC-ROC for PA is increasing function of the parameter a of the log-normal distribution (Fig. IC). The parameter a of the log-normal distribution controls the spread of the distribution, with larger a resulting in a more fat- tailed distribution. While our assumptions about the log- for-normal degree distribution and degree assortativity may not always align with real-world data, Eq. 4 still ef- fectively captures the AUC-ROC behavior for PA (Fig. IC). Further analysis of power-law distributions is described in Appendix E.3. We also identified a similar degree bias in a triplet sampling method (Rendle et al., 2009), which sam- ples triplets (i, j') by sampling an edge (i. and then sampling a node j' uniformly random (Appendix C).
The degree-corrected benchmark has some agreement with the original benchmark in terms of the ranking of the meth- ods (Fig. 2A). For example, they rank GAT and LRW as top performers, while NB, SGTAdjNee and SGTAd are consistently ranked lower. On the other hand, the degree- corrected benchmark ranks PA as the lowest performer, with its average AUC-ROC dropping from 0.83 to 0.54, placing it last out of 29 methods. Other methods such as LP I, GIN also experience a substantial drop in their rankings from 4nd to 12th and 10th to 21th, respectively (Fig. 2A). On the other hand, GCN, GraphSAGE, node2vec. DeepWalk 1k, and Ei EigenMap increase their rankings substantially (Fig. 2A). (See Appendix E.1 for the ranking of methods by HeaRT benchmark (Li et al., 2024a).)
This theoretical result highlights the significant issue with the current link prediction benchmark: a high benchmark performance can be achieved by only learning node degrees, posing the question of whether the link prediction bench- mark is an effective objective of graph machine learning.
3. The degree-corrected link prediction benchmark
The link prediction benchmark yields biased evaluations due to mismatched degree distributions between positive
4

---

Implicit Degree Bias in the Link Prediction Task
Original
Degree-corrected
Graph
LRW
GAT
Rank correlation (Rank-biased Overiag
1.0
SBM
LARPSSAGE
Doge2vec
MLP
RA
SEPpWaik
0-S0M
0.8
27%
1%
44%
adamicAdar
8 SBM
GIN
10 RA
GraphSwot
GCN
12
0.6
14 Elgenmap
MLP-deg
M
CN
Buddy
17 VN ML
0.4
Linearlassifter
MN-NL
F2STAP
nodezves
21 GIN
76
UinegrCaassffier
FastRP
23 Buddy
VN-A
DeepWa
Exe-A
26 VVLL
25
VNL
28 MeL-ddg
0.0
PA
Original
HeaRT
Degree-corretted
Figure 2. Comparative analysis link prediction and recommendation benchmarks. A: Ranking changes for link prediction methods between original and degree-corrected benchmarks. Red and blue lines indicate methods with ranking shifts greater than places. B: Ranking of methods by the degree-corrected benchmark is more aligned with that of the recommendation task than that of the original benchmark and the HeaRT benchmark. RBO (rank-biased overlap) measures the similarity between link prediction and recommendation task rankings.
3.2. The degree-corrected benchmark aligns better with recommendation tasks
ating all node pairs is computationally challenging. We chose LRW because it is among the best performing meth- ods in the retrieval task. The effectiveness of the recom- mendations is measured using the Normalized Discounted Cumulative Gain at K (NDCG@K) (Järvelin & Kekäläinen, 2002). We perform this task five times and average the NDCG@K K scores across different runs. We note that our results are consistent for different candidate set sizes (refer to Appendix E.5).
Link prediction serves as a computationally efficient proxy for evaluating and training recommendation systems ( (Yang et al., 2015; Wang et al., 2021; Huang et al., 2023; Li et al., 2024a; Menand & Seshadhri, 2024). In the recommen- dation task, directly optimizing recommendation metries such as Hits@ K requires ranking all possible node pairs for each node, which is computationally infeasible for large networks. In contrast, link prediction evaluates on a fixed set of candidate pairs, making it (M) (where M is the number of edges) and thus practical for both evaluation and training. This computational advantage has made link pre- diction benchmarks de facto standard for developing and training recommendation models. However, this practice is only valid if link prediction performance correlates with recommendation performance. It is thus crucial that link prediction benchmark accurately mirrors the performance in recommendation tasks.
For each graph, we evaluate the alignment between the rank- ings based on the recommendation task and those based on the link prediction benchmarks using Rank Biased Overlap (RBO) (Wehber et al., 2010). RBO is ranking similarity metric with larger weights on the top performers in the two rankings. A larger RBO score indicates that the top perform- ers in the two rankings are more similar. The weights on the top performer are controlled by the parameter E (0, 1). While we set p = 0.5 in our experiment, we confirmed that our results are robust to the choice of p (Appendix E.5).
Recommendation systems typically involve two steps: re- trieval and ranking. First, the retriever selects smaller candidate set from the entire node set, after which the ranker orders these candidates. In our experiments, we adopt two-stage retrieval pipeline to reflect this practice. Initially, a retriever selects the top candidate neighbors per node us- ing its similarity function. Then, a ranking model ranks these candidates. Both the retriever and the ranker are based on the same similarity function for the embedding- and topology-baad models, but for pairwise link prediction models (i.e., BUDDY and MLP), we use the local random walk (LRW) to retrieve the candidate sets because enumer-
Our results from 95 graphs show that the degree-corrected benchmark achieves higher RBO scores than the original benchmark. For reference, we also tested the HeaRT bench- mark (Li et al., 2024a), which is a recent link prediction benchmark that mitigates the distance-basee bias. The re- sults show that HeaRT achieves substantially lower RBO scores than both the original and degree-corrected bench- marks. We find consistent results for different values of K and parameter p of the RBO (Appendix E.5). These results indicate that the degree-corrected benchmark more accu- rately mirrors the performance in recommendation tasks, providing a more reliable measure of the effectiveness of
5

---

Implicit Degree Bias in the Link Prediction Task
methods in practical applications.
imum community size M'in 100 and Mmma 1000. We obtained qualitatively similar results for different values of the parameters of the LFR benchmark (Appendix E.8).
3.3. Degree-corrected benchmark facilitates the learning of community structure
We train GNNs using either the original or the degree- corrected link prediction benchmarks to minimize binary entropy loss in classifying the positive and negative edges. Using the trained GNNs, we generate node embeddings and apply the K-means clustering algorithm detect commu- nities, where K is set the number of true communities. Although the number K of communities is often unknown, we use the ground-truth number to eliminate noise from estimating K and to concentrate on evaluating the quality of the learned node embeddings, a standard practice in bench- marking node embeddings for the community detection task (Tandon et al., 2021; Kojaku et al., 2024; Kovács et al., 2024). We measure the performance of GNNs by compar- ing the detected communities against the true communities using the adjusted element-centric similarity (Gates et al., 2019; Kojaku et al., 2024; Kováes et al., 2024), where higher scores indicate a higher similarity between the node parti- tions for the true and detected communities. We observe qualitatively similar results for partition similarities based the normalized mutual information (Appendix E.7).
The link prediction benchmark a common unsupervised learning objective for GNNs (Tang et al., 2015; Hamilton et al., 2017; Kawamoto et al., 2018; Kojaku et al., 202 The degree bias implies that GNNs trained using the original link prediction benchmark tend to overfit to node degrees because they can easily differentiate between positive and negative edges based on node degrees. We show that the degree-come cegree-crrected benchmark effectively prevents overfitting to node degrees and improves the learning of salient graph structures.
We evaluate GNNs on the common unsupervised task of community detection in graphs (Fortunato, 2010; Fortunato & Hric, 2016; Fortunato & Newman, 2022). The com- munity detection task identifies densely connected groups (i.e., communities) in graph. Community detection and link prediction tasks are intimately related (Clauset et al., 2008; Peixoto, 2018; Ghasemian et al., 2020). Two nodes will likely have edges if they belong to the same commu- nity. By training graph machine learning model (e.g., GNNs) to learn a node embedding to predict links, nodes in the same community are mapped to be close to each other in the embedding space (Kojaku al., 2024). Com- munities often correspond to functional units (e.g., social circles with similar opinions and protein complexes) in the graph, and detecting communities is crucial task in many graph applications (Fortunato, 2010; Peixoto, 2013; Fortunato & Hric, 2016; Peixoto, 2018; Fortunato & New- man, 2022). Specificallyy, we test the GNNs by using the (LFR) community detec- tion benchmark (Lancichinettii et al., 2008), a standard benchmark for community detection (Fortunato, 2010; For- tunato & Hric, 2016; Tandon et al., 2021; Kojaku et al., 2024). The LFR benchmark generates synthetic graphs with predefined communities as follows. Each node / is assigned a degree K; from a power-law distribution p(k) ~ km with maximum degree kmax. A smaller T1 indicates higher likelihood of large degree nodes, which results in more heterogeneous degree distribution. Nodes are randomly grouped into L communities, with community sizes (i.e., the number of nodes in community) following another power- law distribution p(n) ~ n nm bounded between Ammin and Tmax Edges are then formed such that each node connects to fraction - a of its k; edges within its community and the remaining fraction y to nodes in other communities. We generate 10 graphs for j E {0.05, 0.1, 0.15, ... 0.95, 1) using the following parameter values: the number of nodes
All GNNs, except for GIN, perform well when μ S 0.5, where communities are distinct and easily identifiable, but their performance declines as μ increases (Fig. 3A). Across a broad range of μ.. degree-corrected GNNs, particularly GIN, GCN, and GraphSAGE, outperform original GNNs in identifying communities, as shown by the area under the performance curve (Fig. 3B). The advantage of degree- corrected benchmarks becomes more evident with more heterogeneous degree distribution (Fig. 3C and D). This indicates that degree correction effectively reduces overfit- ting to node degrees, enhancing the learning of community structures in graphs.
Lancichinetti- Coeiihinetti-FFottuatt---
4. Discussion
We showed that common link prediction benchmarks are bi- ased due to node degree in edge sampling, favoring methods that overfit to node degree. This bias distorts model evalu- ations and leads to suboptimal node embeddings (Fig. 2B, Fig. 3B). The degree bias we focused on is artifactual, i.e., it not present in the actual network data but arises in the set of sampled positive and negative edges due to the biased sampling algorithm. We have shown that this artifactual bias significantly distorts the evaluation of link prediction models (Fig. 2B) and can be leveraged by these models to optimize their objective functions, leading to suboptimal learning of node embeddings (Fig. 3B).
N = 3, 000, the degree exponent E [2.5,,3, 3}, the average degree (k) = 25, the maximum degree Kmax = 1000, the community-sin size exponent T2 = 3. the minimum and max-
To better understand the contribution of degree bias, we de- composed AUC-ROC scores into contributions from differ-
6

---

Implicit Degree Bias in the Link Prediction Task
Power-law exponent of degree distribution, = 3.0
Traind the orginal benchrais
Community detectionn performenos
GAT GCN GraphSace GN
8.5
[Element-co simiarty)
0.5
perfommnnce
(Area the performance
Triined with the gr beedhwookk GAT GCN GraphsAGE CIN
0.4
-0.2
0.1
Original
Degree-comected
0.0
0.0
0.2
0.4
0
0.8
1/0
GCN
GIN
GraphSAGE
Mixing rate, f
Power-law exponent of degree distribution, 71 = 2.5
Community delectioon perfommencs
1-0-
(Area under the curve)
(Elemert contre sintarity)
Average perforannce
0.64
0.2
0.2-
0.1
2000
Degree corrected
1.0
GCN
GIN
GrophSAGE
Mixing rate, J
Figure The degree-corrected benchmark improves GNNs learning community structure the LFR graphs. The graphs consist 3, 000 nodes with average degree of 25. A: The performance of community detection for the LFR graphs with a power-law degree distribution with 71 = 3.0 as a function of mixing μ.. B: The average performance (by the area under the performance curve). C, D: The same plots for LFR graphs with fatter pawer-law degrec distribution with 2.5. The error bars represent the 95% confidence interval estimated by bootstrap of 1,000 repetitions.
ent node degree groups (Appendix D). Our analysis revealed that in networks with high degree heterogeneity (a >> 1.3), a single combination highh-eeeee-- positive edges and low- the evaluation, account-
(I) Distance bias arises because nodes connected by negative edges are generally farther apart than those linked by posi- tive edges (Li et al., 2024a), making them easily distinguish- able by distance. We observed that correcting for degree bias consistently reduces distance bias; the degree-corrected benchmark showed more negative edges connected by paths of length 2 compared the standard benchmark across all networks. While our degree correction naturally mitigates distance bias, distance debiasing does not address degree bias. This is evidenced by the strong performance of PA, purely degree-based predictor, even after distance-bias correction (Appendix 1) This asymmetry likely arises because node distances are inherently influenced by degree heterogeneity. In networks with high degree heterogeneity, high-degree nodes act as hubs, creating short paths between many node pairs. Correcting for degree bias naturally re- duces the effect of these hub-mediated short paths. However, correcting for distance alone does not address the underlying degree heterogeneity, which continues influence network structure and link prediction performance.
degree negative edges- ing for over 80% of the overall AUC-ROC score. This simple degree-based methods perform well: the benchmark's 's evaluation is largely deter- mined by cases that can be easily classified using degree alone. Indeed, our logistic regression analysis shows that in heterogeneous networks, the degree product becomes overwhelmingly important, with coefficient more than twice as large as other structural features (Appendix D). These results highlight how the sampling procedure inadver- tently creates shortcut that allows methods to achieve high performance without learning meaningful graph structures.
finding explains why
To address the degree bias, we proposed a degree-corrected benchmark that aligns the degree distributions of sampled edges. Our benchmark not only provided accurate evalua- tions but also improved GNN training by reducing overfit- ting degree and enhancing community detection.
(2) Study (Huang al., 2023) highlighted an issue arising from the substantial down-sampling of negative edges to match the number of positive edges. They proposed an "un- biased testing" approach for link prediction by evaluating methods on all possible negative pairs rather than just a sampled subset. However, we note that the concept of "bias"
While our focus is on degree bias, we acknowledge other bi- ases identified by previous studies (Lichtnwalter & Chawla, 2012; Zhang& & Chen, 2018; Mao et al., 2024; Li et al., 2024a). We highlight some of these biases to underscore the uniqueness of degree bias.

---

Implicit Degree Bias in the Link Prediction Task
in their work differs from the sampling bias address. The degree bias we focus on stems from positive edge sampling, not negative edges. Sampling all negative edges does not resolve this degree bias at all because the node frequency in all negative edges still matches that of uniformly sampled negative edges.
other non-trivial graph structures, such as centrality, could be tested through network dismantling benchmarks (Osat et al., 2023). Third, our degree correction method addresses one form of bias; it may potentially introduce new biases, although we could not identify any clear example of such biases. As a precaution, we investigated whether our debias- ing method can exacerbate certain other biases identified in the literature, such as the distance bias Li et al. (2024a), and found no evidence of this. In fact, find that our method mitigates the distance bias and not vice versa. Fourth, our analysis focuses on the transductive setting, where link pre- diction occurs between nodes in the training graph. We note that degree bias likely persists inductively since new nodes with more connections are still more likely to be selected in edge sampling, mirroring the bias in the transductive set- ting. Fourth, our study focuses exclusively on unipartite networks, and while the findings reveal meaningful insights about degree bias and henchmarking in this setting, their applicability to bipartite or heterogeneous graphs remains unclear and is an important avenue for future investigation.
(3) Our degree-corrected sampling may increase the fre- quency of high-degree nodes, but as these appear in neg- ative examples, models are penalized for overfitting them. This encourages learning more nuanced features, improving the capture of network structures like communities (Fig. 3). This approach parallels techniques in stock market analy- sis (MacMahon& & Garlaschelli, 2015), community detec- tion (Newman, 2006), and node embedding (Kojaku et al., 2021b), where filtering dominant patterns reveals finer struc- tural relationships.
In summary, our findings add a new direction to the ongoing examination of the link prediction task by demonstrating that node degree-a local and notably simpler attribute than distance-is is often sufficient for differentiating the positive and negative edges. Crucially, the degree bias arises in any non-regular graph, regardless of the structure of the graph, because the bias stems not from the graph structure but from the edge sampling algorithm used in the link prediction benchmark. More broadly, edge sampling the source of the degree bias-is is a general technique for evaluating and training graph machine learning. For instance, mini-batch training (Hamilton et al., 2017; Hu et al., 2020b), which sam- ples subsets of edges for efficient GNN training, may also exhibit bias due node degrees, leading to skewed training sets. Given the widespread use of edge sampling across var- ious graph machine-learning tasks, our findings have broad implications beyond link prediction benchmarks, extending to range of benchmarks and training frameworks.
Despite these limitations, our results suggest that sampling graph data is highly non-trivial task more than the com- monly considered. Because sampling edges from graph is integral to evaluating and training graph machine learn- ing methods, our results underline the importance of careful sampling to ensure the effectiveness of evaluations and train- ing of graph machine learning methods.
Software and Data
4.1. Source data and code
The source data, code, and workflow for our experiments are available on GitHub at
https://githut cwm/ jakuu/ winorrected-ln--peeeeee wraninkkppeiiiittoonn www.oonnnnnnnnnr..eee..mmm
Our study has several limitations. First, we did not explore the reasons behind the varying performance of different link prediction methods. Degree heterogeneity can negatively impact GNNs (Liu et al., 2021; Kang et al., 2022; Subramo- nian et al., 2024b; Wang et al., 2024; Liu et al., 2023; Sub- ramonian et al., 2024a; Arun et al., 2023; Li et al., 2024b). Small-degree nodes tend to have poor representation quality due to limited neighborhood information (Liu et al., 2021; Wang et al., 2024), and large-degree nodes benefit from reinforced structural inequality (Subramonian et al., 2024b; Liu et al., 2023; Li et al., 2024b). This hows well a method represents low-degree nodes could be one reason for the differences in performance. It is important to note that there is no single link prediction method that is universally effec- tive for all graphs because the performance of link prediction methods depends on the assumptions on the graph structure to make the predictions (Ghasemian et al., 2020). Second, we focus on community structure to test the effectiveness of the proposed benchmark as training framework. However,
Acknowledgments
We acknowledge NVIDIA Corporation for their GPU re- sources and express our gratitude to Kaleb Smith from the NVIDIA SAE-Higher Education Research team for his help of GPU optimization. This work was supported by the Air Force Office of Scientific Research under Grant No. FA9550-19-
and F-A9550-2511-0097. J.Y. acknowl- edges Global Humanities and Social Sciences Convergence Research Program through the National Research Founda- tion of Korea (NRF), funded by the Ministry of Education (2024S1 22024$1ACCSS ASC3A02042671),
Impact Statement
Our findings indicate that the standard benchmark promotes link prediction algorithms that enhance the "rich-get-richer"
8

---

Implicit Degree Bias in the Link Prediction Task
effect, where well-connected nodes tend gain even more connections. This effect, known as preferential attachment, is common in various societal contexts. For instance, popu- lar individuals often gain more friends, widely shared con- tent spreads further, and frequently cited papers are more likely to attract additional citations. While preferential at- tachment can benefit distributing resources and recogni- tion, it also presents significant disadvantages. For example, preferential attachment can disproportionately favor well- connected individuals in professional networks and hinder scientific progress by undervaluing innovative papers from less-known researchers (Chu & Evans, 2021). Our analysis indicates that the recommendation algorithms trained using the existing benchmark may exacerbate social inequalities by reinforcing the preferential attachment mechanism. Our new benchmark directly addresses these concerns by negat- ing the degree bias, promoting fairer algorithm evaluations, and supporting the development of fairness-awan machine learning methods.
Artico, I., Smolyarenko. I., Vinciotti, V., and Wit, E. C. How rare are power-law networks really? Proceedings of the Royal Society A, 476(2241)2201907722, 2020.
Arun, A., Aanegola, A., Agrawal, A., Narayanam, R., and Kumaraguru, CAFIN: Centrality Aware Fairness In- ducing IN-Processing for Unsupervised Representation Learning Graphs. In ECAI 2023, pp. 101-108. IOS Press, 2023.
Barabási, A.-L. and Bonabeau, E. Scale-free networks. Scientific american, 288(5):60-69, 2003.
Barabási, A.-L. and Pósfai, M. Network Science. Cam- bridge University Press, Cambridge, United Kingdom, 1st edition edition, 2016. ISBN 978-1-107-07626-6
Barthélemy, M., Barrat, A., Pastor-Satorras, R., and Vespig- nani, A. Velocity and hierarchical spread of epidemic outbreaks in scale-fre free networks. Physical Review letters, 1781711 2004.
References
Belkin, M. and Niyogi, Laplacian Eigenmaps for Di- mensionality Reduction and Data Representation. Neural Computation, 10000011133396616 2003. ISSN 0899-76677.
Graph-Tool: Efficent Network Analysis with Python. http://graah--ooolkkkweeddddd
GitHub changyaochen/rbo. https: / com/ changyaochen/ rbo. [Accessed 26-2442024
Bishop, C. M. Pattern recognition and machine learning. Springer google schola, 2:1 2:1122-1128, 2006.
Abbas, K., Abbasi, A., Dong, S., Niu, L., Yu, L., Chen, B.,
Bordes, A., Usunier, N., Garcia-Duran A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. Advances in Neural Information Processing Systems, 26, 2013.
Cai, S.-M., and Hasan, Q. Application of network link prediction in drug discovery. BMC Bioinformatics, 22: 1-21, 2021.
Abboud, R., Ceylan, I. I., Grohe, M., and Lukasiewicz, T. The Surprising Power of Graph Neural Net- works with Random Node Initialization. In Inter- national Joint Conference on Artificial Intelligence, stw.ppssssmmmnnscccoloooo oxt/Co:ppsID::2223..4
Breit, A., Ott, S., Agibetov, A., and Samwald, M. Open- BioLink: a benchmarking framework for large-scale biomedical link prediction. Bioinformatics, 36( 36(13)44097- 4098, 2020.
2020. URL
Broido, A. D. and Clauset, A. Scale-free networks are rare. Nature communications, 10(1):1017, 2019.
Abraham, L. fastnode2vee, 2020. URL https:// github. www loui wwwoaaaaaaaaamoooooaaaaa wwwpraaaaaaatttteee222222 fastnode2vec.
Cai, L., Li, J., Wang. J., and Ji. S. Line graph neural net- works for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5103-511 2021.
Adamic, L. A. and Adar, E. Friends and neighbors on the web. Social Networks, 25(3):211-230 2003.
Albert, R. and Barabási, A.LL. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Chamberlain, B. P., Shirobokov, S., Rossi, E.,, Frasca, F,, Markovich, T., Hammerla, N. Y., Bronstein, M. M., and Hansmire, M. Graph Neural Networks for Link Prediction with Subgraph Sketching. International Conference on Learning Representations, 2023, URL httpps://pperree//// http///ppnneeeeeeeeeeeeeeoo net forum? i id=m1odFOAo2QU.
Ali, M., Hoyt, C. T., Domingo-Fermández D., Lehmann, J., and Jabeen, H. BioKEEN: a library for learning and eval- uating biological knowledge graph embeddings. Bioin- formatics, (5(18):3538-3544 2019.
The Eleventh
Alstott, J., Bullmore, E.,, and Plenz, D. powerlaw: a Python package for analysis of heavy-tailed distributions. PloS ONE, (1)e87777 2014.
Chen, H., Sultan, S. F., Tian, Y., Chen, M., and Skiena, S. Fast and accurate network embeddings via very sparse random projection. In Proceedings of the 28th ACM

---

Implicit Degree Bias in the Link Prediction Task
International Conference information and knowledge management, pp. 2019.
Ghasemian, A., Hosseinmardi, H., Galstyan, A., Airoldi, E. M., and Clauset, A. Stacking models for nearly optimal link prediction in complex networks. Proceedings of the National Academy of Sciences, 117(38):23393-2344 2020.
Christakis, N. A. and Fowler, J. H. Social network sensors for early detection of contagious outbreaks. PloS ONE, 5 2010.
Goyal, P. and Ferrara, E. Graph embedding techniques, applications, and performance: A survey. Knowledge- Based Systems, 151:78-94, 2018.
Chu, J. S. and Evans, J. A. Slowed canonical progress in large fields of science. Proceedings of the National Academy of Sciences, 118(41):a2021636111 2021.
Grover, A. and Leskovec, Node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on KDD, KDD '16 pp. 855-864, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 978-1-4503-4232222
Clauset, A., Moore, C., and Newman, M. E. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191) 910--1011 2008.
Clauset, A., Shalizi, C. R., and Newman, M. E. Power- law distributions in empirical data, SIAM review, 51(4): 661-703, 2009.
Hamilton, W., Ying, Z., and Leskovec, Inductive repre-
sentation learning on large graphs. Advances Neural Information Processing Systems, 30, 2017.
Crichton, G., Guo, Y., Pyysalo, S., and Korhonen, A. Neural networks for link prediction in realistic biomed- ical graphs: multi-dimensional evaluation of graph embedding- approaches. BMC Bioinformatics, 19: 1-11, 2018.
Hand, D. J. Mcasuring classifier performance: coherent alternative to the area under the ROC curve. Machine learning. 77(1):103-11) 123, 2009.
He, X., Ghasemian, A., Lee, E., Schwarze, A. C.,, Clauset, A., and Mucha, P. J. Link prediction accuracy on real- world networks under non-uniform missing- edge patterns. Plos one, 19(7)=0306883, 2024.
Deng, J., Dong, W., Socher, R., Li, L.-J., K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255 IEEE, 2009.
Holme, P. Rare and everywhere: Perspectives on scale-free networks. Nature communications, 10( 10(1):0016, 2019.
Erkol, S.. Castellano, C., and Radicchi, F. Systematic com- parison between methods for the detection of influential spreaders in complex networks. Scientific Reports, 9(I): 15095, 2019.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 2020a.
Feld, S. L. Why your friends have more friends than you do. American journal of sociology, 9666):1444-1477, 1991.
Fey, M. and Lenssen, E. Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Hu, 7., Dong, Y., Wang. K., and Sun, Y. Heterogeneous graph transformer. In Proceedings of the Web Conference 2020, pp. 2704-2710, 2020b.
Huang, Z., Li, X., and Chen, H. Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, pp. 141-142, 2005.
Fortunato, S. Community Detection in Graphs. Physics Reports, 486(3):75-174, 2010. ISSN 0370-1573.
Fortunato, S. and Hric, D. Community Detection in Net- works: A User Guide. Physics Reports, 659:1 44, 2016.
Huang. Z., Kosan, M., Silva, A., and Singh, A. Link pre- diction without graph neural networks. arXiv preprint MrXiv:2305.13633 2023.
ISSN 0370-1573.
Fortunato, S. and Newman, M. E.
Years of Network Community Detection. Nature Physics, 18(8):848 850, 2022. ISSN 1745-2481.
Ito, T., Shimbo, M., Kudo, T., and Matsumoto, Y. Ap- plication of kernels to link analysis. In Proceedings of the eleventh ACM SIGKDD International Conference Knowledge discovery in data mining, pp. 586-592, 2005.
Gates, A. J., Wood. I. B., Hetrick, W. P., and Ahn, Y-Y.. Cemment-Centric Clustering Comparison Unifies Overlaps and Hierarchy. Scientific Reports, 91):85544 2019. ISSN 2045-2322.
Jacob, R., Harikrishman, K., Misra, R., and Ambika, G. Measure for degree heterogeneity in complex networks
10

---

Implicit Degree Bias in the Link Prediction Task
Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Järvelin, K. and Kekäläinen, J. Cumulated gain-based evalu- ation of IR techniques. ACM Transactions on Information Systems (TOIS), 20( 4224))4224446, 2002.
and its application to recurrence network analysis. Royal Society open science, 4(1): 2017.
Zdeborová, L.,, and Zhang, P. Spectral Redemption in Clustering Sparse Networks. Proceedings of the National Academy of Sciences, 110(52))20935 20940, 2013.
Kunegis, J. and Lommatzsch, A. Learning spectral graph transformations for link prediction. In Proceedings of the 26th Annual International Conference on Machine Learning, pp- 561-568, 2009.
Johnson, N. L., Kotz, S., and Balakrishnan, N. Continuous univariate distributions, volume 2, volume 289. John wiley & sons, 1995.
Lancichinetti, A. and Fortunato, S. Community detection algorithmss comparative analysis. Physical Review E, 80(5):066 17, 2009.
Kang, J., Zhu, Y., Xia, Y., Luo, J., and Tong, H. Rawlsgen: Towards rawlsian difference principle graph convolu- tional network. In Proceedings of the ACM Web Confer- ence 2022, pp. 1214-1225, 2022.
Lancichinetti, A., Fortunato, S., and Radiechi, F. Benchmark Graphs for Testing Community Detection Algorithms. Physical Review E, 78(4))046110, 2008.
Karrer, B. and Newman, M. E. J. Stochastic Blockmodels and Community Structure in Networks. Physical Review E, 83(1):016107, 2011.
Li, J., Shomer, H., Mao, H., Zeng. S., Ma, Y., Shah, N., Tang, J., and Yin, D. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. Advances in Neural Information Processing Systems, 36, 2024a.
Kawamoto, T., Tsubaki, M., and Obuchi, T. Mean-field theory of graph neural networks in graph partitioning. Advances in Neural Information Processing Systems, 31, 2018.
Li, Y., Yang, Y., Cao. J., Liu, S., Tang, H., and Xu, G. Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing Approach. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1701-1712, 2024b.
Kipf, T. N. and Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR), 2017.
Kojaku, S., Hébert- DDffreseD,eeeee, L.,, Mones, E., Lehmann, S., and Ahn, Y.-Y. The Effectiveness of Backward Contact Tracing in Networks. Nature Physics, 775))652-6553 2021a. ISSN 1745-2481.
Liben- Nowell, D. and Kleinberg, J. The Link Pre- diction Problem for Social Networks. In Proceed- ings of the Twelfth International Conference Infor- mation and Knowledge Management, CIKM '03, pp. 556-559, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581137234 doi: 10. 1145/956863 956972. URL https: 1145/956888 956972.
Kojaku, S., Yoon, J., Constantino, I., and Ahn, Y.-Y. Residual2Vec: Debiasing graph embedding with random graphs. Advances in Neural Information Processing Sys- tems, 14:24150-22165 2021b.
Lichtnwalter, R. and Chawla, N. V. Link prediction: fair and effective evaluation. In 2012 IEEE/ACM International Conference Advances in Social Networks Analysis and Mining, pp. 376-383, IEEE, 2012.
Kojaku, S., Radicchi, F., Ahn, Y.-Y,, and Fortunato, S. Net- work community detection via neural embeddings. Na- ture Communications, 15(1):9446, 2024.
Lin, 7., Yin, Y., Liu, I.., and Wang, D. SciSciNet: A large- scale open data lake for the science of science research. Scientific Data, 10(1):315, 2023.
Kondor, R. I. and Lafferty, J. Diffusion kernels on graphs and other discrete structures. In Proceedings of the 19th International Conference on Machine Learning, volume 2002, pp. 315-322, 2002.
Liu, W. and Lü, L. Link prediction based on local random walk. Europhysics Letters, 89(5),88007, 2010.
Kovács, B., Kojaku, S., Palla, G., and Fortunato, S. Iterative embedding and reweighting of complex networks reveals community structure. Scientific Reports. 14(1):17184, 2024.
Liu, Z., Nguyen, T.-K., and Fang. Y. Tail-GNN: Tail- Node Graph Neural Networks. In Proceedings of the 27th ACM SIGKDD Conference covery & Data Mining, KDD '21, pp. 1109-1119, New York, NY, USA, 2021. Association for Comput- ing Machinery. ISBN 9781450383325. doi: 10.1145/ 3447548.3467276. URL https: /ttp//ooogg////// (11.344444484777744..
Knowledge Dis-
Krizhevsky, A., Sutskever, I., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems, 25, 2012.

---

Implicit Degree Bias in the Link Prediction Task
Liu, Z.,, Nguyen, T.-K., and Fang, Y. On generalized degree fairness in graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4525 4533, 2023.
Newman, M. E. Modularity and community structure in net- works. Proceedings of the national academy of sciences, 103(23):8577-8882, 2006.
Newman, M. E. Network structure from rich but noisy data. Nature Physics, 14(6):542-545, 2018.
Lü, L., Jin, C.-H., and Zhou, T. Similarity index based on local paths for link prediction of complex networks. Phys.
Rev. E, 80:046122, Oct 2009. doi: 10.1 10.1103/PhysRevE.80 046122. URL https:tttt///ccttc mink.apss wtwps.oog//oo/0...../ 1103/Physse
Osat, S., Papadopoulos, F., Teixeira, A. S., and Radicchi, F. Embedding aided network dismantling, Physical Review Research, 5(1) 2023.
80 046122..
MacMahon, M. and Garlaschelli, D. Community De- tection for Correlation Matrices. Phys. Rev. X, 5:021006, Apr 2015. doi: 10.1103/Phy.Rwwx55 021006. URL https://link aps ops.oor//oi//0 1103/PhysReve 5. 021006.
Ou, M., Cui, P., Pei, J., Zhang, Z., and Zhu, W. Asymmetric transitivity preserving graph embedding, In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge discovery and data mining, pp. 1105-1114, 2016.
Mao, H., Li, Shomer, Li, B., Fan, W., Ma. Y. Zhao, T., Shah, N., and Tang, Revisiting Link Prediction: a data perspective. In The Twelfth International Conference on Learning Representations, 2024. URL https: /// openreview net forum//ormmm 200-8802xmurrr
Patent, U. S. and Office, T. USPTO citation network. 2023.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V.,
Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Mara, A. C., Lijffijt, J., and De Bie, T. Benchmarking network embedding models for link prediction: Are we making progress? In 2020 IEEE 7th International con- ference on data science and advanced analytics (DSAA), pp. 138-147. IEEE, 2020.
Peixoto, T. P. Parsimonious Module Inference in Large Networks. Physical Review Letters, 110(14):44870,, 2013.
Mason, S. J. and Graham, N. E. Areas beneath the rela- tive operating characteristics (ROC) and relative oper- ating levels (ROL) curves: Statistical significance and interpretation. Quarterly Journal of the Royal Meteoro- logical Society: A Journal of the Atmospheric Sciences, Applied Meteorology and Physical Oceanography, 128 (584):2445-2166, 2002.
Peixoto, T. Reconstructing networks with unknown and heterogeneous errors. Physical Review X, 8(4):041011, 2018.
Peixoto, T. P. The Netzschleuder network catalogue and repository. URL https://hetworks. skewed. de, 2020.
Perozzi, B., AI-Rfou, R., and Skiena, S. DeepWalk: On- line Learning of Social Representations. In Proceedings of the 20th ACM SIGKDD International Conference on
Menand, N. and Seshadhri, C. Link prediction using low- dimensional node embeddings: The measurement prob- lem. Proceedings of the National Academy of Sciences, 121(8):c2312527) 121, 2024.
KDD, KDD '14, pp. 701-710, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 978- 1-4503-2956-9.
Menon, A. K. and Elkan, C. Link prediction via matrix fac- torization. In Machine Learning and Knowledge Discov- ery in Databases: European Conference. ECML PKDD 201 Athens, Greece, September 5-9, 2011, Proceedings, Part II 22, pp. 437-452. Springer, 2011.
Radicchi, F., Fortunato, S., and Castellano, C. Universality of citation distributions: Toward an objective measure of scientific impact. Proceedings of the National Academy of Sciences, (1144)::1228-1727777 2008
Nadakuditi, R. R. and Newman, M. E. J. Graph Spectra and the Detectability of Community Structure in Networks. Physical Review Letters, 188110) 2012.
Rajpurkar, P., Zhang. J., Lopyrev, K., and Liang, SQuAD: 100,000+ Questions for Machine Comprehension of Text. In Su, J., Duh, K., and Carreras, X. (eds.), Proceed- ings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383-2392, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10. 10.18653//1/DI6-1112 1264. URL https: / /aaclantholgyy.... http:/lgyy.ogoo11oo11111111 ( 6-124
Narayanan, A., Shi, F.,, and Rubinstein, B. I. Link pre- diction by dc-anonymization: How we won the kaggle social network challenge. In The 201 International Joint Conference on Neural Networks, pp. 1825-1834 IEEE, 2011.
12

---

Implicit Degree Bias in the Link Prediction Task
Rajpurkar, P., Jia, R., and Liang, P. Know What You Don't Know: Unanswerable Questions for SQuAD. In Gurevych, I. and Miyao, Y. (eds.), Proceedings of the 56th Annual Meeting of the Association for Computa- fional Linguistics ( (Volume 2: Short Papers), pp. 784-789, Melbourne, Australia, July 2018. Association for Compu- tational Linguisties. doi: 10. 186538v66vv 1/6633/11/18-2122/ URL https: / /awpaaaannnnncooccaaaaaaaaaaaeta wtt/
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., and Mei, Q. LINE: Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web, WWW '1, pp. 1067-1077, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee. ISBN 978-
1-4503-3469-3.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liö, P., and Bengio, Y. Graph Attention Networks. International Conference on Learning Representations, 2018. URL https: http:///pppeeiieieeeeeeeeee net. forum? id=rJXMpikCZ, accepted as poster.
Redner, S. Citation statistics from 110 years of physical review. Physics today. 58(6):49-54, 2005.
Rehurek, R. and Sojka, P. Gensim-python framework for vector space modelling. NLP Centre, Masaryk University, Czech Republic, 3(2), 2011.
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, i., Feng, Y., Moore, E. W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A.. Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F. van Mulbregt, P., and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
Rendle, S., Freudenthaler, C., Gantner, 7., and Schmidt- Thieme, L. BPR: Bayesian Personalized Rank- ing from Implicit Feedback. ArXiv, abs/1205.2618, 2009. URL https:/ /api. wapp.semaanttt.... iistantcccchl.r.....
Russo, M., Sawischa, S. F., and Vidal, M.-E. Tracing the Im- pact of Bias in Link Prediction. In Proceedings of the 39th ACM/SIGAPP Symposium on Applied Computing, SAC '24, pp. 1626-1633, New York. NY, USA, 2024. Associa- tion for Computing Machinery. ISBN 9798400702433. doi: 10. 10.11445/6005088836333377 URL ptttts::/doo 3639912.
Voitalov, I., Van Der Hoom, P., Van Der Hofstad, R., and Krioukov, D. Scale-free networks well done. Physical Review Research, 1(3):033034, 2019.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on data mining (SDM), pp. 333-341, SIAM, 2021.
Wang, P., Xu, B., Wu, Y., and Zhou, X. Link prediction in social networks: the state-of-the-arr Science China Information Sciences, pp. 1-38, 2014.
Subramonian, A., Kang, J., and Sun, Y. Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks. In The eighth Annual Conference on Neural Information Processing Systems, 2024a. URL wwt.h:tt//////tt httttp::///peenrevieee net/ forum? id=1mAaewThez.
Wang, S.-M., Lee, H.-K., Kweon, Y.-S., Lee, C. T., and Lee, K.-U, Overactive bladder successfully treated with duloxetine in a female adolescent. Clinical Psychophar- macology and Neuroscience, 13(2):212, 2015.
Wang, Y. and Derr, T. Degree- Related Bias in Link Predic- tion. In 2022 IEEE International Conference on Data Mining Workshops (ICDMW), pp. 757-758, 2022. doi: (000//CCDWW500002222222..00
Subramonian, A., Sagun, L., and Sun, Y. Networked in- equality: preferential attachment bias in graph neural network link prediction. In Proceedings of the 41st In- ternational Conference on Machine Learning, 1CML'24. JMLR.org, 2024b.
Wang, Y., Zhao, T., Zhao. Y., Liu, Y., Cheng, X., Shah, N., and Derr, T. A Topological Perspective Demystifying GNN-Based Link Prediction Performance. In The Twelfth International Conference on Learning Representations, 2024. URL https: http///peeeeeeeeeeee http:/iwwweeeeeeeeeeeeeeeeeeeeee net//orunt i id=apA655Xx2e.
Sun, Z., Deng, Z..H., Nie, J..Y., and Tang. J. RotatE: Knowl- edge Graph Embedding by Relational Rotation in Com- plex Space. In International Conference on Learning Representations, 2019, http:: // hpwp//eeee.eeeeeeeee/eepe net/
Wang, Z., Zhou, Y., Hong, L., Zou, Y., Su, H., and Chen, S. Pairwise learning for neural link prediction. arXiv preprint arXiv:21 2021.
Tandon, A., Albeshri, A., Thayananthan, V., Alhalabi, W., Radicchi, F., and Fortunato, S. Community Detection in Networks Using Graph Embeddings. Physical Review E, 103(2):022316, 2021.
Webber, W., Moffat, A., and Zobel, J. A Similarity Measure for Indefinite Rankings. ACM Trans. Inf.
13

---

Implicit Degree Bias in the Link Prediction Task
Syst, 28(4), nov 2010. ISSN 1046-8188. doi: 10.
1145/1852102.18521066 URL https: httpps://doi.ooo / 10. 10.1145/182202.185222
Xu, K., Hu, w., Leskovee, J., and Jegelka, How Powerful Graph Neural Networks? In International Conference Learning Representations, 2019. URL https:// 61A5Km.
httet//oooooiiudddmoo opeatevieew.net//oouuudd-/--- openreview.eoo httpeeiiwwweeeeeeeeeeeeeeeeeeeee
Yang. Y., Lichtenwalter, R. N., and Chawla, N. Evaluat- ing link prediction methods. Knowledge and Information Systems, 45:751-782, 2015.
You, J., McLeod, R. D., and Hu, P. Predicting drug-target interaction network using deep learning model. Compu- tational biology and chemistry, 80:90-101, 2019.
Yue, X., Wang. Z., Huang. J.. Parthasarathy, S., Moosav- inasab, S., Huang, Y., Lin, S. M., Zhang, W., Zhang, P., and Sun, Graph embedding on biomedical networks: methods, applications and evaluations. Bioinformatics, 124-11124 2020.
Zhang, M. and Chen, Y. Link prediction based on graph neu- ral networks. Advances in Neural Information Processing Systems, 31, 2018.
Zhou, T., Ren, J., Medo, M., and Zhang, Y.-C. Bipartite net- work projection and personal recommendation. Physical Review E, 76(4))046115 2007.
Zhou, T., Lü, I.,, and Zhang, Y.C.. Predicting missing links via local information. The European Physical Journal B, 7 71:623-630, 2009.
14

---

Implicit Degree Bias in the Link Prediction Task
A. Data and link prediction methods
A.I. Network data
The corpus of networks used in this work comprises networks with the number of nodes in the range [102, .10) and edges in the range [102,10%], 10 We also considered networks from the OGB benchmark (Hu et al., 2020a). This includes social, technological, information, biological, and transportation (spatial) networks. For simplicity in our analysis, we consider these networks to be unweighted, undirected, and without self-loops, though the message of our work holds without these constraints. The largest networks in our corpus (number of nodes >> 10 are sourced from Netzschleuder (Peixoto, 2020), and the remaining networks are obtained from the authors of Ref. (Erkol et al., 2019). See Table 2 for details.
A.2. Link prediction algorithms
We use 29 link prediction algorithms categorized into four groups: topology-based, graph embedding, network model, and graph neural networks (see Table 1).
1. TOPOLOGY-BASEE PREDICTORS
Topology-basd baaoggyybbdddppooo predictors calculate the prediction score st using the structural features of two nodes. The topology- based predictors employed in our study include Preferential Attachment (PA) (Barabási & Pósfai, 2016), Common Neighbors (CN) (Liben-Nowell & Kleinberg, 2003), Adamic-Adar (AA) (Adamic & Adar, 2003), Jaccard Index (JI) (Liben-Nowell & Kleinberg, 2003), Resource Allocation (RA) (Zhou et al., 2007; 2009), Local Random Walk (LRW) (Liu & Lü, 2010), Local Path Index TLPT) (Lü et al., 2009). For LRW and LPI, we set the hyperparameter = 0.001 as per previous studies (Lü et al., 2009; Liu & Lü, 2010). The other methods do not require hyperparameters.
We implemented two multilayer perceptrons (MLPs) that takes features of two nodes and predict whether they are connected by an edge or not. The first MLP (MLP-deg) takes only the degree features as input, igg, degree product k,ky, degree sum k + kj. minimum degree min(k,, k;)) and maximum degree max(k,, k2). The second MLP (MLP-topo) takes AA, JI, RA, and LRW as input. The MLP consists of two hidden layers coupled with LeakyReLU activation function, and we used held-out validation to tune the number of dimensions in each hidden layer (32, 64) and dropout rate (0.2, 0.5) with the validation set consisting of 10% of the edges. We used the Adam optimizer at a learning rate of 0.001.
As simpler baseline, we also implemented a logistic regression model (Linear) that takes the concatenation of the node features as input and predict whether they are connected by an edge or not. The input features are RA, JT, and LRW, and AA, and PA. In order to reduce the collinearity between the input features, we performed feature orthogonalization by regressing RA, JI, and LRW, AA on PA and taking the residuals as new features. This means that after orthogonalization, we input the residuals of RA, JI, and LRW, AA on PA, as well as the raw PA features to the logistic regression model. To further reduce the collinearity, we employed the ridge regression implemented in seikit-learn (Pedregosa et al., 2011), 1), with the regularization parameter set to the default value.
A.2.2. GRAPH EMBEDDINGS
Graph embedding maps a graph into a vector space, with each node represented by a point in this space. The prediction score 8ty is given by the dot product गř. v between any two node vectors. We tested a variety of graph embedding methods including Laplacian EigenMap (BigenMap) (Belkin & Niyogi, 2003), Spectral Modularity (Mod) (Nadakuditi & Newman, 2012), Non-backtracking Embedding (NB) (Krzakala et al., 2013), FastRP (FastRP) (Chen et al., 2019), Exponential Kernel on Adjacency Matrix (Exp-A) (Kondor & Lafferty, 2002; Kunegis & Lommatzsch, 2009), Exponential Kernel on Laplacian (Exp-L) (Kondor& & Lafferty, 2002; Kunegis & Lommatzsch, 2009), Exponential Kernel on Normalized Laplacian (Exp-NL) (Kondor& & Lafferty, 2002; Kunegis & Lommatzsch, 2009), Von Neumann Kernel on Adjacency Matrix (vN-A) (Ito et al., 2005; Kunegis & Lommatzsch, 2009), Von Neumann Kernel on Laplacian (vN-L.) (Ito et al., 2005; Kunegis & Lommatzsch, 2009), and Von Neumann Kernel on Normalized Laplacian (vN-NL) (Ito et al., 2005; Kunegis & Lommatzsch, 2009), node2vee (node2vec) (Grover & Leskovec, 2016). DeepWalk (Deepwalk) (Perozzi et al., 2014), and LINE (LI (Tang et al., 2015). We tested a variety of graph embedding methods including Laplacian EigenMap (EigenMap) (Belkin & Niyogi, 2003), Spectral Modularity (Mod) (Nadakuditi & Newman, 2012), Non-backtracking Embedding (NB) (Krzakala et al., 2013), FastRP (FastRP) (Chen et al., 2019), Exponential Kernel on Adjacency Matrix (Exp-A) (Kondor& & Lafferty, 2002; Kunegis & Lommatzsch, 2009), Exponential Kernel on Laplacian (Exp-L) (Kondor & Lafferty, 2002; Kunegis& & Lommatzsch, 2009), Exponential Kernel on Normalized Laplacian (Exp-NI.) (Kondor &
15

---

Implicit Degree Bias in the Link Prediction Task
Lafferty, 2002; Kunegis & Lommatzsch, 2009), Von Neumann Kernel on Adjacency Matrix (vN-A) (Ito et al., 2005; Kunegis & Lommatzsch, 2009), Von Neumann Kernel on Laplacian (vN-L.) (Ito al., 2005; Kunegis & Lommatzsch, 2009), and Von Neumann Kernel on Normalized Laplacian (vN-NIJ (Ito et al., 2005; Kunegis & Lommatzsch, 2009), node2vec (node2ved) 2vec) (Grover & Leskovec, 2016), WeepWalk (DeepWalk) (Perozzi et al., 2014), and LINE (LINE) (Tang et al., 2015). For all methods, we set the number of embedding dimensions to 128. For LINE, node2vec, and DeepWa 1 k, we set the number of walkers to 40 and the number of the walk length to 80 following Ref. (Kojaku et al., 2024). We used the default hyperparameters used the original papers unless otherwise specified.
A.2.3. GRAPH NEURAL NETWORKS
Graph neural networks (GNNs) learn the vector representation, Ti for each node of the network by using neural networks. The prediction score $tj is given by the dot product 17, ūły between any two node vectors. We also explore several graph neural network (GNN) architectures for link prediction, leveraging the PyToorch Geometric library (Fey & Lenssen, 2019). The GNN methods we employ include: Graph Convolutional Network (GCN) (Kipf & Welling, 2017), Graph SAGE (GraphSAGE) (Hamilton et al., 2017), Graph Attention Network (GAT) (Veličković et al., 2018), and Graph Isomorphism Network (GIN) (Xu et al., 2019). We used held-out validation to tune the number of hidden layers (1 or 2) and the number of dimensions in each hidden layer (64, 128, or 256) with the validation set consisting of 10% of the edges. We use ReLu activation and dropout rate of 0.2. The node features are the 64 principal eigenvectors of the adjacency matrix, and we extend the feature vector by adding 64-dimensional vector with each element being generated from an independent Gaussian distribution with mean 0 and standard deviation 1 by following Ref. (Sato et al., 2021; Abboud et al., 2020). We train GNNs on the link prediction task for 250 epochs with a dropout rate of 0.2, using the Adam optimizer at a learning rate of 0.01. We use the "LinkNeighhorl.oadee Loader from Py ToTcch Geometric to generate training mini-batches, This loader samples both positive and negative edges, along with 30 immediate neighbors and secondary neighbors sampled by random walks for each node involved in these edges (Hamilton al., 2017). The batch size is set 5000.
We also tested BUDDY GNN, which achieves competitive performance the link prediction task (Chamberlain et al., 2023), We employed hyperparameter tuning for the number of hidden channels (256 or 1024), and the feature dropout rate (0.05 or 0.2) with the validation set consisting of 10% of the edges. We set the number of hops to 2 because it consistently achieved a better performance. For other hyperparameters, we used the default values used in the original implementation.
A.2.4. NEWORK MODELS
We use two stochastic block models (SBM) (Fortunato, 2010; Fortunato & Hric, 2016; Fortunato Newman, 2022; Peixoto, 2013) and the degree-correced SBM (Karrer & Newman, 2011; Peixoto, 2013; Gra). These models estimate the probability P(i,j) that edge exists between two nodes, which serves the prediction score 8ij. We fit the SBMs using the graph tool package (Gra). We select the number of blocks that minimize the description length and use default settings for other parameters.
A.3. Pseudo-code for the degree-corrected link prediction benchmark
The pseudo-code for the degree-corrected link prediction benchmark is shown in Table. 1.
Algorithm Degree-corrected link prediction benchmark
Input: Graph G)V,E), Sampling fraction 3 [0. 1] for positive edges
Output: Set of negative edges Eneg and set of positive edges Epos Generate Epos by randomly sampling a 3 fraction of edges in E Initialize Eneg f-
Create node list L where each node i with degree k; appears k; times while EEegl < 1ppcsl do Randomly select two nodes i from L with replacement
if (i,j) & E and (i,j) & Eneg and 4 then Eneg + Eneg U (i,j))
end if end while
return Eneg, Epos
16

---

Implicit Degree Bias in the Link Prediction Task
Table 1. Link prediction algorithms. "pyg" refers to PyTorch Geometric.
Algorithm
Reference
Nocation
Preferential attachment
(Bumhdiii Posfai 2016)
ourselves
PA
Common neighboes
(Liben Nowell & Kleinberg, 2003)
ourselves
CN
Topology
Adami:Adar
(Adamic & 2003)
based
Resource allocation
index
(2hou et al, 2007;
(oweenNNwelll Kleinherp, 2007)
ourselves
ourselies
C1
RA
Kandoca
Ld, 2010)
Path
2009)
curselves
MI P-ddg
cursetvos
HLD deg
MI P-opp
curselves
MtP-topo
Laplscian FigenMap
(Relkin & Niyogi, 2003)
curselves
RigenMag
Spectral modularity
(Nadakuddi Newman, 2012)
our survel
Hod
Non-tacktsskking embedding
(Kozakala 2013)
curselves
FasRP
(Chen et al., 20199
ourselves
Fasta2
Adjccency marrix the exponenial Laplacian
(Kondor & Lafterty 2002),
ourselves
Exp
Lommarrach,
(Kondor Lallerty, 2002).
ourselves
Exp-L
Graph embedkinn
wf the expanential kernel
(Kunegas Lommazzsch, 2009)
Normalized Leplacian
(Kondor Luffery. (Kunegis Lommatzech, 2009)
the expunential kernel
Adjacency marri the Neumean
(Kendor & Laflerty, 2002).
ourselves
VW-2
(Kunegis Lommarzsch,
Laplacian
et 2005).
ourselves
vW-
wi the von Neumaan kernel Neumann kernel
(Kunegis & Lommazzsch, 2009)
Nocmalized Laplacian Neumaan
2005),
oursetves
(Kunegis Lommarzsch, 2009)
LINE
(Tuag et al., 2015)
gensim (Rchwrck & Sojka, 2011).
LINE
(Almismm 2020)
DespWalk
al.,
gensim (Rehurek Sojka, 2011),
DoopWalk
gensim (Ahmalam, 2020)
node2vve
(Grover & Loskowee, 2016)
pensim (Rehunck & Sojka, 2011).
node2vec
gensim (Abraham,
Graph
Graph Convelutional Network
(Kipf Welling, 2017)
Pyg (Fey Lenssen, 2019)
GCN
neural
Graph SAGE Graph Network
(Hamilton et al,, 2017)
(Pey Lenssen, 2019)
GraphsaGE
(Velikkoid (Nu al., 2019)
GIN
pyy (Fey Lenssen, 2019)
GIN
BL DDY GNN
(Chamberiain et al., 2023)
(Chamberiain al., 2022)
BUDDY
Network model
Stochastie block model
(Fortanato, Fortunato
graph tool (Cira)
(Fortanato (Kamer & Newman, 2011: Peisoto, 2013: Gm)
3)
Degres curvected stochustic block model
graph uol (Gra)
dc3BB
17

---

Implicit Degree Bias in the Link Prediction Task
A.4. Additional analysis methods
We use the following additional analysis methods in this paper. We fit log-normal distribution the degree distribution of the graphs by using the moment method implemented in the scipy. stats lognorm package (Virtanen et al., 2020). We fit powerlaw distribution to the degree distribution of the graphs by using the maximum likelihood method implemented in the powerlaw package (Alstott et al., 2014). We compute the RBO score by using the rbo package (rbo).
B. AUC-ROC for the preferential attachment method
Let us first derive the degree distribution of nodes in the positive edges. By substituting Eq. into Eq. I in the main text, we derive the degree distribution of nodes in the positive edges
(In k - 11)21
Pous (1:) = (k) 2ark
exp
20²
2g² ((In R:)² - -2 + +²² + Innk 1 11 0²
exp
V
20² (1n)))2 - 2(μ + (22) + 1² 22u + +44)
exp
V2takk
k - 02)
exp
(4)
V2
202
This is the probability density function of log-normal distribution with mean μ o² and variance o², i.e.
Ppos (k) = LogNorm(k + 10+00,0% o²)))).
(5)
Equation 5 indicates that the degree distribution for nodes in the positive edges also follows log-normal distribution, parameterized by + o² and
We derive the AUC-ROC for PA by leveraging unique characteristic of log-normal distributions, i.e., the logarithm In k of log-normally-distiibuueed degree k follows a normal distribution with mean μ and variance o², i.e.,
(k 11)²
P(In k) Norm(k: [s, o²); where Norm(k: (2,
exp
(6)
V2Ta
2x
We assume no degree assortativity in the graph, where P(k ,(kt, P(k:) Although empirical graphs often exhibit degree assortativity, our results indicate that it does not significantly impact the AUC-ROC (Appendix E.2). For the negative edges, the distribution for In S,- = In k, + In kj follows normal distribution with mean 2μx and variance 2o², as the sum of independent normal variables also forms normal distribution with additive means and variances (Bishop, 2006), i.e.,
P(nns-- .-) = Norm 8:- 20..
For the positive edges, the degree distribution also follows a log-normal distribution (Eq. 5). Thus, the distribution for In Syt .+ In k,t + k5 is given by
p(nsstttt) Norm (Instt 1p + 20 2222)
(8)
Thus, we have
AUC-ROC P(Ins < <
Norm(x 202) 1
Norm(x*
12p + 20 20 ydx 2d dr
1
Norm(s 2|,, 202)
Norm(x
12 + 20 20 )d dr
18

---

Implicit Degree Bias in the Link Prediction Task
We reparameterize Eq. 9 by using 2² x² =²_20 dr (v we have
Noting that Norm x
202, -20 = Norm
0, 1) and
V20
/ Norm(a
P(Ins& < <lnst)=1 =1
Norm x
2,,, 20,2
2/1 + 20 20²2 dr
00
Norm
(2 10,1)
22 Norm ( -vo 10,1) d=+d2=
Norm 10, (2- v20 dz
(10)
where ( is the cumulative distribution function for the standard normal distribution, i.e., +b2-) S Norm(y 0, 1)dy. We recognize that
Norm - | 1) (5- v20) dz EEz- [ (2 v20)
(11)
Here, R.g- denotes the expectation normally distributed rndom variable The cumulative distribution function t can be expressed using another normally distributed random variable as:
- Ply < /20 2 = P = 220 x-).
(12)
Applying the law of total probability (P(A) = P(A X)), we have:
Eg
② (2 - v20) = =B,-
-g- Ply - = /20 |= Ply = > V20).
(13)
Since y and = are both normally distributed, their difference y 2 is normally distributed with mean 0 and variance 2. Thus,
22o 4 (g)
Ply x- > V20) ④
(14)
V2
Substituting this into Eq. 10, we have:
P(s =
(15)
C. AUC-ROC for asymmetric degree-proportiionl sampling
We analyze the behavior of AUC-ROC for PA when link prediction evaluated using an asymmetric negative sampling scheme. In this set up, method is evaluated by set of triplets (i, jtj "t.j"""" ( where (i.j+) is sampled from the observed edges, and j is sampled uniformly at random over nodes. This setup is used in Bayesian Personalized Ranking (BPR), where training triples are drawn uniformly from the observed interaction set (Rendle et al., 2009). We focus on the performance of PA under this sampling scheme and prove that, as the degree distribution becomes increasingly skewed, the AUC-ROC of PA approaches 1, as is the case the uniform sampling negative edges.
Let us first recall that the degree of node jr in the negative edges follows the original degree distribution p(k) because node j- is selected uniformly random from all nodes. Conversely, nodes and j+ have degrees following Ppe (k) (Eq. 1) due to the friendship paradox (Section 2.3). Specifically, node with degree k appears & times among observed edges, and as result, its degree distribution is proportional to kp(k), and hence aligns with Ppos(k).
We are interested the AUC-ROC of PA for the positive and negative edges as (it,it) and (i-,j_).ie.. i.e.
P(s < s) P(log k; + +log k, log ki + k.g..
(16)
19

---

Implicit Degree Bias in the Link Prediction Task
0.9
0.8
AUC-ROC
0.7
0.6
0.5
Expected Empirical
0.4
0.0
0.5
1.0
1.5
2.0
2.5
Degree heterogeneity,
Figure 4. AUC-ROC for PA under the asymmetric negative sampling.
Assuming that p(k) is log-normal distribution, the sum log ki + 1o- involves two normally distributed random variables, log k;- and log ky-, with means μ and μ o², respectively, and each with variance a². Consequently, their sum is also normally distributed with mean 2/ + o² and variance 20². Denoting by x = log kę= + log ky2, we have:
1 I
P(s <+t)=
Norm(x 2 0², 200)
Norm(x* 12 + 20 20 )dx
dx
Norm(x 2 + 202)
12p + 20 202 202 dr. Norm (x:
By reparameterizing x² by using 2 (2u+o0) V2a
have
P(s <st)=11 =1
Norm (2 (=- 00,1)
Norm
x
v2 10, d de
Norm 10, 1) =
dz
(17)
V2
By taking the same derivation steps in Eqs. 11-15, we have:
P(s <st) +
0
(18)
Since 4 is monotonically increasing function, the AUC-ROC is also an increasing function of a. The rate of increase is less than the AUC-ROC for the uniform sampling of negative edges (Eq. 15). This can be understood by noting that one endpoint node i the negative edges in the asymmetric sampling is sampled from the observed edges, which is more likely have higher degree than that of the negative edges sampled uniformly at random.
Empirical validation of Eq. 18 confirmed that the AUC-ROC for PA under the asymmetric negative sampling closely follows that for empirically measured AUC-ROC (Fig. 4).
D. Decomposition analysis of AUC-ROC scores
key concern with the standard benchmark is that link prediction methods may overfit to nodes with high degrees. To investigate this systematically, we developed a decomposition analysis of the AUC-ROC scores that reveals how different
20

---

Implicit Degree Bias in the Link Prediction Task
A
B
1.0
Negative Edge Sampler
Uniformity of P(i e 92 JP E ge) (Nornalized Entropy)
1.-
Proportion of high-degree positive and small-degree negative edges
Uniform
HeaRT
0.8
0.8
Degree blased
P(s 99 9P'P
0.6
0.4
0.4
Negative Edges
Uniform
0.2
HeaRT
0.2-
Degree biased
0.0
0.s
1.5
2.0
0.0
10 Degree heterogeneity (a)
1.5
2.0
Degree heterogeneity (a)
Decomposition of the AUC-ROC score by degree combinations. Each dot represents graph. Uniformity of P(i g P(j E 9p.) quantified by the normalized entropy, H. B: Probability P(i 9f P(j E 92 that the positive edges are sampled from the high-degree node group of and the negative edges are sampled from the low-degree node group 92
Figure 5.
groups nodes contribute to the overall performance metrics.
The AUC-ROC score- the probability that positive sample has higher score than a negative sample-can can be decomposed into conditional scores by partitioning the evaluation edges into groups. Specifically, if we partition edges into groups ø1 and 92, the AUC-ROC score can be written as:
2 P(st s ge E 97) P(j (e)
ME--ERE 1=1==1
(19)
where o and sj are the scores of the positive and negative edges given by link prediction method, respectively, and gi and 9r are the positive and negative edges in the f-th group, respectively. Probability P(s > si ge E gr) represents the conditional AUC-ROC score for positive edge sampled from 9f and negative edge sampled from Fe. Probability P(i E 9, P(j 95) represents the probability that a positive edge is sampled from 9, and negative edge is sampled from 9gr We note that P(i E g, PPj E -p.) is determined by the sampling of positive and negative edges and independent of the link prediction methods.
Based on this decomposition, we investigate the impact of edges of different node degrees on the overall AUC-ROC scores. Specifically, we partition edges into two equal-sized groups based the degree product k,k, of their endpoint nodes, with 91 having 2 2 median and 92 having median. We tested multiple definitions of including degree sum (kç + kz), minimum degree (min(k;, kj)), and maximum degree (max (h;, k;)) finding consistent results across all definitions.
To measure how uniformly different groups contribute to the AUC-ROC score, we use normalized entropy:
2 Σ
H
Σ P gf) E 97) P(i E Ptj E 97)/ log
(20)
The entropy is bounded between 0 and where 0 indicates that the AUC-ROC score is determined by single group pair and indicates that the AUC-ROC score is evenly distributed across all group pairs.
We observe that the standard benchmark exhibits notable disparity compared to HeaRT and degree-corrected benchmark, indicating that the contribution to the AUC-ROC score in the standard benchmark can be heavily skewed toward certain combinations node degrees (Fig. 5A). This disparity becomes even more pronounced in networks with high degree heterogeneity (H 0.5 and a > 1.5). This disparity caused by a single group mair-positvve edges from high-degree
21

---

Implicit Degree Bias in the Link Prediction Task
Table Mean absolute coefficients from logistic regression analysis across different graphs. Features were orthogonalized climinate collinearity, and coefficients were normalized by the feature L2 norm. Larger coefficients indicate greater importance in link prediction.
Mean Absolute Coefficient
Topological Feature
All Graphs
Graphs with Graphs with > 1.5
Random walk
11.52
10.68
9.01
Degree product
8.79
17.19
28.00
Resource allocation
2.81
4.53
6.88
Adamic-Adar
1.35
2.35
2.89
Jaccard index
0.89
1.06
0.17
nodes and negative edges from low-degree nodes with P(i E P() ) 0.7 for a > 1.5 (Fig. 5B). This means that for highly heterogeneous networks, more than 70% of the AUC-ROC score is determined by cases that can be easily classified using degree alone. The regree-corrected benchmark achieves high uniformity (H ~ 1) across group pairs (Fig. 5A), indicating that the contribution to the AUC-ROC score is approximately evenly distributed across different degree groups.
To validate these findings further, we performed additional experiments using logistic regression to analyze the importance of features. The model was trained with resource allocation, Jaccard index, Adamic Adar, local random walk, and degree product. To ensure a fair comparison, we orthogonalized the non-degree features with respect the degree to eliminate collinearity effects. Additionally, we use ridge regularization further mitigate the effect of collinearity. We use the seikit-leam package (Pedregosa et al., 2011) to perform the logistic regression with the default ridge regularization strength. To make the regression coefficients comparable, we normalize the features by their 1.2 norm before training the model. The results showed that in networks with high degree heterogeneity (a > 1), the degree product emerges as significantly important, with its coefficient 1.73 3 times as large as the second most important feature (Table. 2).
This dominance of degree- prediction is particularly concerning because it indicates that learning- baaeed methods can achieve high benehmark performance by primarily exploiting degree information rather than learning more complex structural patterns. This "shorteut" is precisely what our degree-corrected benchmark aims to prevent.
These results provide strong quantitative support for our argument that the standard benchmark's s evaluation is dominated by easily classified degree-basen based cases, potentially leading to suboptimal model training. The degree- correctd benchmark successfully addresses this issue by ensuring more uniform contributions from different degree groups, leading to a more meaningful evaluation of link prediction methods.
E. Robustness analysis
E.1. Method ranking by HeaRT benchmark
The ranking of methods by the HcaRT benchmark is shown in Fig. 6. The results show that PA achieves the highest AUC-ROC scores among all methods in the HeaRT benchmark, contrasting sharply with its lowest performance in the degree-corrected benchmark. This indicates that degree bias may not be reduced by HeaRT, which reduces the distance-based bias.
E.2. Impact of degree assortativity on the AUC-ROC for PA
We have assumed that the graph has no degree assortativity, meaning that P(k,k) = P(k)) Although this assumption may not always hold, it provides a good approximation for the AUC-ROC behavior for PA. Although the assortativity varies across graphs, the AUC-ROC for PA still closely follows Eq. (9) in the main text (Fig. 7).
E.3. AUC-ROC for PA for scale-free networks
We have assumed that the graph exhibits the heterogeneous degree distributions characterized by the log-normal distribution. An alternative model of the degree distribution is the powerlaw distribution (Barabási & Bonabeau, 2003). Here, we show that our results also hold for the powerlaw degree distribution, i.e., the AUC-ROC for increases as the degree
22

---

Implicit Degree Bias in the Link Prediction Task
A
Original
HeaRT
B
HeaRT
Degree-corrected
LRW
MLP-deg
MLP-deg
GAT
dcSBM
PA
PA
GCN
SBM
GIN
GIN
GraphSAGE
LP
Buddy
Buddy
LRW
GAT
SBM
SBM
node2vec
RA
6 dCSBM
dcSBM
dcSBM
MLP-topo
7 LPI
LP
DeepWalk
adamicAdar
8 GraphSAGE
GraphSAGE
CN
CN
MLP-topo
GIN 10
10 GCN
GCN
GraphSAGE
GAT
GAT
11
GCN
LinearClassifler
LinearClassinie
12 LPI
LINE
13 adamicAdar
adamicAdar
13 Eigenmap
MLP-deg
14 LRW
LRW
adamicAdar
15
15 MLP-topo
MLP-topo 15
15 LINE
PA
Mod
Mod 6
16 CN
Buddy
Exp
EXP A 17
17 VN-N NL
LinearClassifier
VN-A 18
18 EXp-NL
vN-Ni
LINE
LINE 19
19 FastRP
Exp-NL
20
20 Mod
node2vec
RA 21
21 GIN
Mod
22 vN-L
vN-L 22
22 LinearClassifier 23 Buddy
FastRP
23 Exp-L
Exp-1 23
Eigenmap 24
24 EXP-NL
Exp NL
24 vN A
DeepWaik
25 vN-NL
vN-NL 25
Exp-A
Exp-A 26
26 node2vec
node2vec
vÑ-A 27
27 FastRP
FastR
EXD-L
vN-L 28
28 DeepWalk
DeepWalk
MLP-deg
Exp-L 29
29 Eigenmap
Eigenmap
Figure 6. Comparison of the AUC-ROC scores between the original. degree-corrected, and the HeaRT benchmarks.
heterogeneity increases.
We compute the AUC-ROC for PA for graphs with powerlaw degree distribution. Computing AUC-ROC ((j S k2+ ky+) is not trivial because involves multiplicative convolution of two probability distributions, which are hard to compute for the power law degree distribution. To circumvent this problem, we consider the lower-bound by focusing on k S hūt and k-- I kyt, which the subset of all combinations of (k; kigt hg ky leading kü k5- S k kyt.
i.e.
P(k-- <++) P(ky- < kigt kkt) P(k-- ky- < ket kxt
(21)
Assuming that the graph has degree assortativity (i.e., k(k, (kk)), obtain the lower bound for the AUC-ROC:
2
P(k-- < k++) P(k-- < )
Σ Poeg (k)
Ppos (2)
(22)
t=k
Now, let compute the lower bound by assuming that the degree distribution follows power-law (Clauset et al., 2009):
p(k)
kmin) kmii)) k (k 2 kmin), where Ç(a,, kimin)
Σ
(23)
Eim Rusin
where Ç is the Hurwitz zeta function, and kimin is the minimum degree. By substituting Eq. (1) in the main text into Eq. 23, we have Ppos = ko a++1 /Ç(a- 1, kmin). By noting that Ee p(f) = {(a, k)/{(a,, kmin) (Clauset et al., 2009). we have
[ C(a, ((a 1, Kmin)
P(k- ket)
Σ
k k- - 1,k)
(24)
k=kmn
Numerical calculation shows that the lower bound P(k-- < ket ja approaches as 2 (Fig. 7). Additional validation using the Price network with N = 10a nodes and M = 10 edges, where p(k) x --a confirms that PA achieves higher AUC-ROC than the lower-bound and reaches near- maximal AUC-ROC scores for RJ 2.
We can also compute the AUC score using the Mann- Witt-hhitney U statistic (Fig. 8). Let us take a graph with the set of nodes given by V. We sample nodes i.j with degrees k k2 forming the positive set of edges from Pposs and nodes m, n with
23

---

Implicit Degree Bias in the Link Prediction Task
1.00 - A
B
Price Graph
0.9
0.95
Lower bound
0.90
0.8
AUC-ROC
0.85
Degree assortativity
AUC-ROC
0.7
-0.4
0.80
0.6
- 0.2
0.75
0.0
0.5
0.2
0.70
0.4
0.4
0.65
0.6
0.3
2
3
0.5
1.0
1.5
2.0
Degree heterogeneity, O
Power-law exponent, a
Figure 7. The AUC-ROC for FA as function of degree heterogeneity. A: The AUC-ROC for the empirical graphs and that expected by node degree (Eq. (9) main text). colors represent the degree assortativity. Lower bound for AUC-ROC for the powerlaw degree distributions. The dashed line represents the lower bound for the AUC-ROC for the powerlaw distribution. The blue line represents the AUC-ROC for PA for Price graph
10* nodes and 102 edges.
degrees k k, forming the negative set of edges from Pneg. Then P(K kj >> k, Vi,j, E V is the AUC score and is given by ningg where U is the Mann-Whin Mann-Whitney U statistic and n1, f2 sizes of the positive and negative edge sets respectively (Mason & Graham, 2002). We sample the random variables K k,t using the "Power function from the powerlaw package (Alstott et al., 2014) with degree exponent since Ppos (k) k (a-1), Similarly, we sample kn kn with degree exponent since Peeg (k) k- Fig. 8 aligns with findings in Fig. 7B, i.e., PA reaches near maximal AUC-ROC scores + 2.
E.4. Analysis of large-seale networks
To test whether the degree bias persists in large-scale real-world networks, analyzed two large-scale citation networks, ie., the Science of Science (SciSci) citation network (Lin et al., 2023), which represents citations between more than 95M publications across all sciences, and the USPTO citation network (Patent & Office, 2023), consisting of more than 7M patents in the US.
We followed the same procedure as our main analysis to test for degree bias, measuring the AUC-ROC score of the preferential attachment model. The results strongly supported our theoretical predictions: PA achieved an AUC-ROC score of 0.9452 for SciSci and 0.881 for USPTO, closely matching our thcoretical predictions of 0.9479 and 0.918, respectively, With the Pngree-correeter benchmark, the AUC-ROC scores for PA decrease for both graphs, e.g., 0.5018 for SciSci and 0.4818 for the USPTO.
While we do not run other link prediction methods on these networks due to computational constraints, these results provide strong evidence that our findings about degree bias are not limited to smaller networks but represent a fundamental characteristic of the standard link prediction benchmark.
E.5. Parameter sensitivity in the analysis of performance alignment with the recommendation task
Normalized Discounted Cumulative Gain (NDCG) is a widely used metric in information retrieval and recommendation systems that evaluates the quality ranked lists by considering both the relevance of items and their positions in the ranking. Unlike metrics such as precision recall that treat all positions equally, NDCG applies logarithmic discount factor that
24

---

Implicit Degree Bias in the Link Prediction Task
1.0
0.8
0.6
AUC
0.4
0.2
0.0
2.5
3.0
3.5
4.0
4.5
5.0
a
Figure 8. The influence of degree hetcrogeneity the performance of the preferential attachment (PA) link prediction model in graphs with power law degree distribution. The degree heterogeneity is governed by the power law exponent a. As increases, the heterogeneity decreases. PA reaches ke k,t km, kn The dots indicate the average AUC score obtained via the Mann- Mann-Whing Whitney U statistic. Standard mean errors are smaller than the dots.
maximal AUC-ROC scores (1) 2. For each a, we generate batches, each with 5000 samples of
penalizes relevant items appearing lower in the ranking, reflecting the diminishing probability that users will examine items further down list. Formally, for ranked list of items, NDCG@K K is computed by first calculating the Discounted Cumulative Gain (DCG) to position K:
Yg
NDCG@K K for node i
(25)
log (i
where Yú is the indicator function of node j is connected with in the test data (Y = 1), and otherwise Yú, 0. This value is then normalized by dividing by the DCG of the ideal ranking (IDCG), where all relevant items are placed the top positions:
NDCG@K = DCG@K
(26)
IDCG@K
In our link prediction evaluation, use NDCG@ @ 100 to assess how well different methods rank true connections among their top 100 predictions.
We compute the similarity of two rankings with rank-biased overlap (RBO) (Webher et al., 2010). RBO assesses the similarity of two rankings by examining the overlap of top-performing methods. Define Uk,1 as the set of methods ranked in the top k positions in ranking and UR,2 similarly for ranking 2. Then, RBO computes a weighted average of the similarity of the top methods by
Uk n Un
RBO(S,
(27)
k
where controls the importance of the performer, with smaller p value placing more weight on the top performer. We use = 0.5 for the results in the main text. We find consistent results across different values (Fig. 9A and B). Additionally, we find consistent results for a different number of recommendations K (Fig. 9C and D).
We also compute the vertex-centree max precision recall at K (VCMPR @ K) metrie (Menand & Seshadhri. 2024) to evaluate the performance of the link prediction methods. This metric proposed for evaluating link prediction methods in
25

---

Implicit Degree Bias in the Link Prediction Task
NDCG@100
A
p 0.25
B
P 0.9
Rank correlation (Rank--bissed Overlag)
1.0
0.9
601
0.8
27%
196
44%
9%
67%
0.7
0.6
0.6
0.4-
0.4
0.2-
0.3
0.0
Original
HeaRT
Degree-corrctted
Original
HeaRT
Degree-corrected
P 0.5
C
NDCG@10
D
NDCG@50
ation (Rank-biased Overfap)
1.0
0.8
33%
3%
27%
19
0.6-
0.4
0.2
0.2-
0.0-
0.0
Original
HeaRT
Degree-corrected
Original
HeaRT
Bogree-correctee
Figure 9. RBO for different p values and different numbers K of recommendations.
recommendation settings. The VCMPR@ K for a node i and recommended node set V, is defined as
VCMPR@* @ K for node i = Ejey, Yo
(28)
max(C, (C, m;)'
where m, is the number of true connections in the test data, i.e., m, = E, Y.j. We compute the average (CMPR&K for all nodes as the performance of the link prediction method for the graph. We observed that the degree-corrected benchmark provides method rankings more similar to those of the recommendation task measured by VCMPR @ K than the standard and HearT benchmarks (Fig. 10).
E.6. Evaluation of the link prediction performance using Hits @ K
@its@ K is another common metric used to evaluate link prediction methods alongside AUC-ROC. We investigated whether degree bias affects Hits@ K scores and our bias correction improves the correlation between Hits@ K and actual link prediction performance. To compute Hits@K K, we first ranked all test data edges by their predicted scores descending order. We then counted the number of positive edges among the top edges. This count was normalized by the maximum possible value (K) to indicate how close the method came to perfect prediction.
Our analysis revealed that the @its@ K scores for PA are consistently high across most networks, with only a few exceptions in networks with very low degree heterogeneity (Fig. 11A-D). The supriously high performance of PA remains consistent regardless of the K value used.
When we applied the same analysis to the degree-correcte benchmark, we found that the Hits K scores for PA span the range between 0 to 1.0 (Fig. 1)E-H), This indicates that the degree correction effectively mitigates spurious results and
26

---

Implicit Degree Bias in the Link Prediction Task
0.5
=
A
VCMPR@10 10
B
VCMPR@50
C
VCMPR@100
Rark corre ation (Hank-- bann--iiased Overleg)
1.0
0.8
0.8
0.6
0.6-
0.-
0.2
300
0.0
Original
HeaRT
Degree-correctdd
Original
HeaRT
Degree-comeeted
Original
HeaFT
Degree-coriected
Figure 10. VCMPR for different K recommendations.
prevents inflation of performance metrics due degree bias.
We then compared the Hits K scores with the actual link prediction performance, measured by NDCG@ 100, using RBO scores, Our results show that the RBO scores for the degree-correcter benchmark tend to be higher than those for the standard benchmark (Fig. 1 I1I-L... This suggests that the degree-corrected benchmark provides a more accurate assessment of link prediction performance.
In summary, whether using AUC-ROC ranking-baac based metrics like Hits K, the underlying data used for evaluation is crucial. Our findings reveal systemic problem: the data itself, when not properly corrected, has bias that skews results in way that is difficult to mitigate through metric selection alone. These results highlight the importance of addressing degree bias in link prediction evaluations, regardless of the metric used, and emphasize the need for careful evaluation methods in graph-based recommendation systems to ensure benchmark performance accurately reflects real-world performance.
E.7. Evaluation of the community detection performance using the normalized mutual information
Normalized Mutual Information (NMI) is standard metric for assessing community detection methods (Lancichinetti & Fortunato, 2009; Fortunato & Hric, 2016). NMI quantifies the similarity between actual and predicted community assignments, where a score of zero indicates no similarity. We note that NMI has a bias favoring partitions with small communities (Gates et al., 2019), and thus, we used the element-centric similarity that does not have this bias in our main experiment. We note that NMI has a bias favoring partitions with small communities (Gates al., 2019), and thus, we used the element-centric similarity that does not have this bias in main experiment. Nevertheless, NMI in Fig. 12 for comparison. As with the element-centric similarity, our results show that the degree-corrected GNNs perform on par or better than the original GNNs.
include the results for
E.8. Sensitivity to the choice of the LFR benchmark parameters
We tested the robustness of the results by using different parameter values for the LFR benchmark. First, we confirmed the consistent results when varying the average degree (k) from 25 to 50 (Fig. 13), the maximum community size and degree from 1000 to 500 (Fig. 14).
F. GNNs trained with the HeaRT benchmark
We compared our degree-corrected benchmark with the distance-aware HeaRT benchmark (Li al., 2024a). We trained the GNNs using the negative samples generated by the HeaRT benchmark. Due to the computational expense of the negative sampling process of HeaRT, we selectively choose the LFR graphs with small mixing rate (μx = 0.1-0.20), where communities are well-separated. If the benchmark facilitates the GNN's learning of communities in networks, the be at least as high as the original benchmark. Failure to do so indicates that the benchmark is not effective as training method for learning community structure.
performance of community detection must
The results when training GNNs on the HeaRT benchmark showed notably lower performance compared to both the standard
27

---

Implicit Degree Bias in the Link Prediction Task
Uniform sampling
Hits@
Ho
Ho
Hits@ 100
1.0
1.0
1.0
1.0
0.8
Hits@K (Normalized)
0.4
0.4
0.4
0.2
0.2
25
100
0.2
100
0.2
Degree-corrected sampling
Ho
F
Hits@20
Hits@500
H
Hits@100
1.0
1.0
1.0
1.0
0.8
10:00 RHISSRICR
0,8
0.8
0.8
0.6-
0.2
0.2
25
100
0.2
75
100
0.2
50
100
Graphs
Hits@ 10
Hits@220
K
Hits@50
L
Hits@ 100
correlation (Rank biased Overlap)
corelation Overtap)
Rank correlation (Rank-biesed Overlap)
Rank correlation (Rank bissed Overlap)
1.0
0.8
0.6
0.6
0.4
0
0.2
0.2
0.0
0.0
0.0-
0.0
Original
Degres-corrected
Original
Degree-corrected
Original
Degree corrected
Original
Degree-corected
Figure 11. Link prediction performance using Hits@ A-D @K score for the PA model for the standard benehmark. E-H Hit score for the PA model for the dogree-corrected benchmark. I-L The RBO score between the Hits K scores and the the recommendation performance measured by NDCG@ 100.
28

---

Implicit Degree Bias in the Link Prediction Task
Power-law exponent of degree distribution, = 3.0
Community detection performance
1.0
original benchmark
Average performance (Area under the performance curve)
0.6
GAT
0.8
GCN
0.5
GraphSAGE
GIN
0.6
(NMI)
Trained with the biased-aligned benchmark
0.3
GAT
GCN
0.2
0.2
GraphSAGE
Original Degree-corrected
GIN
0.1
0.0
0.2
0.4
0.6
0.8
1.0
GAT
GCN
GraphSAGE
Mixing rate, μ
Power-law exponent of degree distribution, 71 2.5
Community detection performance
1.0
Average performance (Area under the performance curve)
0.6
0.8
0.6
0.4
(NMI)
0.3
0.2
0.2
Original Degres-corrected
0.1
0.0
0.0
0.2
0.6 Mixing rate, μ.
0.4
0.8
1.0
GAT
GCN
GIN
GraphSAGE
Figure 12, Performance of the GNNs on the LFR benchmark measured by NMI.
29

---

0.6 Implicit Degree Bias in the Link Prediction Task
Power-law exponent of degree distribution, = 3.0
A
Community detection performance
1.0
original benchmark
Average performance (Area under the performance curve)
0.7
GAT
(Element Element-centric oit-ceetric similarity)
0.8
GCN
GraphSAGE
GIN
0.5
0.6
Trained with the biased-aligned benchmark
0.4
GAT
GCN
0.3
0.2
GraphSAGE
Original Degree-corrected
GIN
0.2
0.0
0.2
0.4
0.6
0.8
1.0
GAT
GCN
GIN
GraphSAGE
Mixing rate, p
Power-law exponent of degree distribution, 71 2.5
D
Community detection performance (Element- Cement-centric cot-oentiic similarity)
1.0
Average performance (Area under the performance curve)
0.7
bodGoo
0.8
0.6
0.5
0.6
0.4
0.3
0.2
0.2
Original Degree-corrected
0.1
0.0
0.2
0.4
0.8
1.0
GAT
GCN
GIN
GraphSAGE
Mixing rate, μ.
Figure 13. Performance of the GNNs on the LFR benchmark measured by NMI when varying the average degree (k) from 25 to 50.
and degree-corrected benchmarks.
For comparison, the performance of GNNs trained on both the standard and degree-corrected benchmarks exceeded 0.2 within this range of mixing rates.
G. Correlation between AUC-ROC and other network statistics
Figure 15A shows the correlation between AUC-ROC and other network statistics. We observed that the AUC-ROC of PA strongly correlated with the degree heterogeneity in terms of the variance of the log-normal distribution of node degrees, more than other network statistics.
Figure 15B shows the correlation between AUC-ROC and the models that outperform PA on the standard benchmark. We observed that these models exhibit substantially weaker correlations between their AUC-ROC and degree heterogeneity, suggesting that their performance not strongly tied to degree heterogeneity.
30

---

Implicit Degree Bias in the Link Prediction Task
Power-law exponent of degree distribution, 71 = 3.0
A
B
Trained with
Community detection performance
1.0
original benchmark
Average performance (Area under the performance curve)
Original Degree-corrected
GAT
0.55
Elemeentcenttr citt-centicc similarity)
GCN
GraphSAGE
GIN
0.6
0.45
Trained with
bissed-aligned benchmark
0.40
GAT
GCN
0.35
0.2
GraphSAGE
GIN
0.30
0.0
0.0
0.2
0.4
0.6
0.8
1.0
GAT
GCN
GIN
GraphSAGE
Mixing rate, μ
Power-law exponent of degree distribution, = 2.5
D
Community detection performance (Element- ment-centric similarit)
1.0
Average performance (Area under the performance curve)
0.6
Original Degree-corrected
0.5
0.6
0.4
0.2
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
GAT
GCN
GIN
GraphSAGE
Mixing rate, μl
Figure 14. Performance of the GNNs on the LFR benchmark measured by NMI when varying the maximum community size and degree from 1000 500.
Table 3. Performance of GNNs trained using the HeaRT benchmark for networks with different mixing rates
Mixing rate
GAT
GCN
GIN
GraphSAGE
0.10
0,00668
0.04247
0.00603
-0.00063
0.15
0.01600
0.01383
0.02049
-0.00004
0.20
0.00951
0.01670
0.00955
-0.00023
31

---

Implicit Degree Bias in the Link Prediction Task
Pearsonr correlation between AUC-ROC of PA ~ network statistics
A
0.8
uniform
Pearsonr Correlation
0.8
B
0.6
degreeBlased
0.6
Correlation
0.4
0.4-
0.2
0.0
0.0
0.2
localPathindex
SBM
GAT
dcSBM-
GraphSAGE:
meeteeentalAttaccmmnttt
localRandomWalk
0.4
lognorm sigma
globalirrnsitivityy
localTransitivityy
degreeAssortativity
maxDegree-
Figure Correlation between AUC-ROC and other network statistics.
32

---

Implicit Degree Bias in the Link Prediction Task
Table 4. Network data tested in this study. We consider social, technological, information, biological, and transportation (spatial) networks. For simplicity in analysis, consider these networks be unweighted, undirected, and without self-loops. Variance referes the variance of the node degrees. Assortativity refers to the degree assortativity, and Heterogeneity refers to the degree heterogeneity computed by (Jacob al., 2017).
Network
Nodes
Edges
Max. Degree
Variance
Assortativity
Heterogeneity
Political books
105
441
25
29.69
-0.128
0.43
College football
115
613
12
0.78
0.162
0.20
High school 2011
126
1709
55
153.71
0.083
0.62
Food web bay wet
128
2075
110
249.17
-0.112
0.62
Food web bay dry
128
2106
110
249.85
-0.104
0.63
Radoslaw email
167
3250
139
993.84
-0,295
0.62
Highschool 2012
180
2220
56
120.37
0.046
0,51
Little Rock Lake
183
2434
105
433.29
-0,266
0,54
Jazz
2742
303.12
0.020
0.55
C. Elegans
297
2148
134
167.56
-0.163
0.38
Network science
34
15.42
-0.082
0,23
Dublin social
410
2765
50
70.51
0.226
0.29
Airport
2980
499.03
-02668
0.35
Caltech
762
16651
248
1365.76
-0,666
0,42
Reed
18812
313
1254.53
0.023
0.38
Political blogs
1222
16714
351
1474.67
-0.211
0,34
Haverford
1446
59589
375
3687.70
0.067
0,41
Simmons
1510
32984
300
1288.53
-0.062
0.32
Swarthmore
1657
61049
S77
3472.20
0.061
0.37
Petster
1788
12476
272
440.86
-0.089
0.24
UC Irvine
1893
13835
255
599.57
-0.188
0.24
Yeast
2224
6609
64
63.67
00.05
0.15
Amherst
2235
90954
467
4007.71
0.058
0.35
Bowdoin
2250
84386
670
3206.35
0.056
0.33
Hamilton
2312
96393
602
3940.69
0.031
0.34
Adolescent health
2539
10455
27
18.59
0,251
0.10
Trinity
2613
111996
404
3742.49
0.072
0.32
USFCA
2672
65244
405
2041.31
0.092
0,27
Japanese book
2698
7995
725
608.58
-0,559
0.17
Williams
2788
112985
3901.94
0.040
0.32
Open flights
2905
15645
242
485.44
0.049
0.21
Oberlin
2920
89912
478
2838.11
0.050
0.28
Wellesley
2970
94899
746
3079.68
0.064
0,29
Smith
2970
97133
2432.51
0.044
0.28
Vassar
3068
119161
482
3453.23
0.101
0.30
Middlebury
3069
124607
473
3865.24
0.078
0.30
33

---

Implicit Degree Bias in the Link Prediction Task
Table (Continued) Network data tested in this study.
Network
Nodes
Edges
Max. Degree
Variance
Assortativity
Heterogeneity
Pepperdine
3440
152003
674
5695.91
0.055
0.31
Colgate
3482
155043
773
4009.14
0.067
0.29
Santa
3578
151747
1129
4933.35
0.071
0.29
Wesleyan
3591
138034
549
3548.92
0.095
0.28
Mich
3745
81901
419
1997.51
0.142
0.24
Bitcoin alpha
3775
14120
511
402.89
-0.169
0.17
Bucknell
3824
158863
506
3498.69
0.094
0.27
Brandeis
3887
137561
1972
4646.98
-0.026
0.27
Howard
4047
204850
1215
8506.41
0.058
0.32
Rice
4083
184826
581
5669.22
0.065
0.29
GR-QC 1993-2003
4158
13422
81
74.41
0.639
0.12
Tennis
4338
81 866565
451
4573.31
0.003
0.26
Rochester
4561
161403
1224
3632.47
0.025
0.25
Lehigh
5073
198346
973
4073.33
0.035
0.24
JohnsHopkins
5157
186572
4761.94
0.080
0.25
HT09
5352
18481
1287
1333.44
-0.431
0.14
Wake
5366
279186
7469.92
0.071
0.27
Hep-Th 1995-99
5835
13815
50
20.77
0.185
0.08
Bitcoin OTC
5875
21489
795
531.22
-0.165
Reactome
5973
145778
855
4612.48
0,241
0.21
Jung
6120
50290
5655
16029.25
-0.233
0.16
Gnutella Aug 08 2002
6299
20776
97
72.95
0.036
0.11
American
6370
217654
930
3847.11
0.066
0.22
MIT
6402
251230
708
6241.81
0.120
0.24
JDK
6434
53658
5923
16112.86
-0.223
0.16
William
6472
266378
1124
5164.22
0.052
0.23
U Chicago
6561
208088
1624
4093.91
0.018
0.22
Princeton
6575
293307
628
6164.10
0.091
0.24
Carnegie
6621
249959
840
5674.47
0.122
0.24
Tufts
6672
249722
827
4525.50
0.118
0,22
UC
6810
155320
660
2297.32
0.125
0.19
Wikipodia elections
7066
100736
1065
3332.59
-0.083
0.21
English book
7377
44205
2568
3699.80
-0.237
0.16
Gnutella Aug 09 2002
8104
26008
102
66.74
0.033
0.09
34

---

Implicit Degree Bias in the Link Prediction Task
Table (Continued) Network data tested in this study.
Network
Nodes
Edges
Max. Degree
Variance
Assortativity
Heterogeneity
French book
8308
23832
1891
1217.86
-0.233
Hep-Th 1993-2003
8638
24806
65
41,61
0.239
0.08
Gnutella Aug 2002
8717
31525
115
51.87
0.052
0.09
Gnutella Aug 0S 2002
8842
31837
88
54.66
0,015
0.09
PGP
10680
24316
205
0.238
0.09
Gnutella Aug (4 2002
10876
39994
103
48.65
-0.013
0.08
Hep-Ph 1993-2003
11204
117619
491
2307.04 04
0.630
0.16
Spanish book 1
11558
43050
2986
3353.23
-0.282
0.12
DBLP citations
12495
49563
709
284.34
-0.046
0.10
Spanish book 2
12643
55019
5169
6953.72
-0.290
0.11
Cond-Mat 1995-99
13861
44619
107
45.70
0.157
0.07
Astrophysics
14845
119652
360
472.92
0.228
0.11
Astrophysics
17903
196972
504
961.58
0.201
0.11
Cond-Mat 1993-2003
21363
91286
279
119.00
0.125
0.07
Gnutella Aug 25 2002
22663
54693
66
28.58
-0.173
0.04
Internet
22963
48436
2390
1085.20
-0.198
0.08
Thesaurus
23132
297094
1062
1993.31
-0.048
0.12
Cora
23166
89157
377
123.05
-0.055
0.07
AS Caida
26475
53381
2628
1113.83
-0.195
0.08
Gnutella Aug 24 2002
26498
65359
355
35.03
-0.008
0.04
ogbl-collab
232865
961883
382
178.857773
0.269877
1.134311
ogbl-ddi
4267
1067911
2234
716801.815422
0.037832
0.730724
protthi
11034
884042
2551
62766.451816
-0.027401
1.112268
ogbl-biokg- bruug-drug
7313
137027
652
15456.62724 622212
0.079466
1.577354
ogbl-bioke function
44635
1180424
17690
61471.922776
-0.128156
1.770447
35


Reviews:
[{"review_id": "TcHDWIVpWn", "reviewer": "Reviewer_vU2g", "summary": "This paper is focused on the link prediction task and it shows how the sampling procedure applied in the evaluation of link prediction methods is biased towards high degree nodes. More specifically, the selection of random negative pairs to be distinguished against positive pairs leads to negative pairs connecting low degree nodes. This issue is analyzed both empirically and theoretically. To address the issue, the paper proposes a degree-correlated sampling procedure that generated negative pairs that have similar degrees as the positive ones. Using this new benchmark, they show that preferential attachment achieves higher performance than predicted using the standard sampling procedure.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and for pointing out the important distinction between retrieval and ranking in recommendation systems!\n\n > ### Response to \"Claim and Evidence\" section\n\nIn response to the reviewer's comment along with the comment from reviewer 9kyj, we have now used NDCG@K as our main evaluation metric for the retrieval task. The findings are consistent, i.e., degree-correction yields 44% graphs above RBO >0.6, for HeaRT and original yield 1% and 27% of graphs above RBO >0.6, respectively, which is in line with our previous result for VCMPR@C. \n\nAdditionally, we have reworked the paragraph to make clear the two-step retrieval pipeline suggested by the reviewer as follows:\n\n- Recommendation systems typically involve two steps: retrieval and ranking. First, the retriever selects a smaller candidate set from the entire node set, after which the ranker orders these candidates. In our experiments, we adopt a two-stage retrieval pipeline to reflect this practice. Initially, a retriever selects the top candidate neighbors per node using its similarity function. Then, a ranking model ranks these candidates. Both the retriever and the ranker are based on the same similarity function for the embedding- and topology-based models, but for pairwise link prediction models (i.e., BUDDY and MLP), we use the local random walk (LRW) to retrieve the candidate sets because enumerating all node pairs is computationally challenging. We chose LRW because it is among the best performing methods in the retrieval task.\n\nThis makes clear that we are using a two-step retrieval pipeline, which wasn't clear form the previous version of the manuscript.\n\n> ### In section 3.3, the claims around Hits@K are kinda misleading\n\nWe thank the reviewer for raising this important point. Let us clarify the intent of our original statement regarding Hits@K:\n\n-  Text in the previous version of the manuscript: *\"In the recommendation task, directly optimizing recommendation metrics such as Hits@K requires ranking all possible node pairs for each node, which is computationally infeasible for large networks\"*.\n\nWe understand that this sentence may have been interpreted as referring to inference, particularly in the context of a typical two-step retrieval-then-ranking pipeline. However, our statement refers specifically to the **training cost** of directly optimizing Hits@K-style objectives, which require full pairwise rankings and are thus infeasible at scale.\n\nThe distinction between training and inference is crucial here. While SEAL, BUDDY, and similar models use a two-step retrieval-then-ranking strategy during inference, they are not trained using candidate sets. Rather, **they are trained via binary classification over uniformly sampled connected and disconnected node pairs, which is precisely the set up of the standard link prediction benchmark**.\n\nWhile one may consider training a ranking model using a pre-trained retriever, this introduces a dependency on the retriever. If the retriever fails to retrieve true neighbors, then even a strong ranking model cannot recover. This is why we believe evaluating retrievers directly on recommendation metrics is essential; retrieval is the first step in the pipeline, and its quality bounds the overall system performance.\n\nWe appreciate the reviewer's thoughtful feedback, which prompted us to clarify this key distinction. We hope this response strengthens the overall clarity of the paper.", "claims_and_evidence": "In section 3.3, the claims around Hits@K are kinda misleading. In recommendation systems, usually the whole workflow is done in a couple steps, essentially retrieval and ranking, where retrieval systems are usually nearest neighbor-based (any LP method with dot-product decoder) and ranking systems are usually pairwise methods (e.g., subgraph LP method such as SEAL). And the authors claim around Hits score is sort of putting a retrieval metric under the ranking, as in a nearest neighbor-based system, it's quite intuitive to calculate the similarity of 1 user against all items and get the top K, and that's also where metrics such as Recall@K and Hits@K are used. On the other hand, like the author said, it's hard for ranking methods to calculate the similarity between all pairs due to the high complexity. But in reality, they never need to, as they usually have a much smaller candidate set, i.e., the top K output by the retrieval system.\n\nConsidering that the recommendation task is the most relevant real world application to the task of LP, I'd suggest the authors to re-work on section 3.2, and also corresponding evaluations.", "methods_and_evaluation_criteria": "there's no proposed method", "theoretical_claims": "seems correct to me", "experimental_designs_or_analyses": "see my comment above", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "s1. Having a good set of benchmark is very critical for the healthy development of the field, and the authors pointed out some fetal problems of existing benchmarks.\n\ns2. The main hypothesis of the paper is supported by empirical and theoretical results.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qbuhfkRvpe", "reviewer": "Reviewer_9kyj", "summary": "This paper argues that the existing benchmark for link prediction inevitably involves implicit degree bias during the positive and negative edges sampling since both sampling distributions are theoretically proven to be inconsistent. Consequentially, existing link prediction methods implicitly overvalue the characteristic of degree, in particular for graphs with high heterogeneity. To solve this issue, the degree-corrected link prediction benchmark is proposed, which samples negative edges with a similar distribution as the positives. Extensive experiments and analysis show that the proposed benchmark facilitates the capability of capturing comprehensive graph structures (i.e., community structure) instead of node degree simply and boosts strong baselines (e.g., GAT) as a result.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and meticulous review and many constructive comments!\n\n> ### Alignment is only evaluated between AUC-ROC and VCMPR, ...while neglecting the ranking ability (i.e., NDCG)\n\nWe agree with the point and now use NDCG@k as our evaluation metric and report VCMPR@C results in Appendix. The findings are consistent, i.e., degree-correction yields 44% graphs above RBO >0.6, for HeaRT and original yield 1% and 27% of graphs above RBO >0.6, respectively.\n\n> ### The algorithms used for evaluations seem only to be link prediction methods rather than specific graph recommendation methods.\n\nLink prediction and recommendation are closely intertwined, and the distinction between them is not clear-cut. Both tasks rely on similar modeling techniques. For example, BPR trains recommendation models using triplets (user, positive item, negative item). BPR models learn ranking from pairwise comparisons of positive edges and negative edges, which is effectively the link prediction task we focused on. OGB datasets also follow a retrieval-style classification evaluation (e.g., ogbl-collab and ogbl-ddi). Thus, we believe that evaluating link prediction models in retrieval-like settings, as we do, is appropriate.\n\n> ### Whether the proposed benchmark works on bipartite ... remains unclear.\n\nAll graphs in our experiments are unipartite. This choice aligns with existing benchmarks such as ogbl-citation2 and ogbl-ddi, and with prior work on link prediction [Li et al. 2024a, Huang et al. 2023, Mao et al. 2023, Menand & Seshadhri 2024]. We agree that assessing benchmark behavior in bipartite graphs is important. However, our goal is to establish and validate the benchmark in the unipartite setting as a first stepping stone on this issue. To clarify this point, we added new text to mention this future work.\n\n> ### It seems to be adding extra bias among negative edges and ignoring the existing bias among positive edges.\n\nIn link prediction, positive edges reflect the observed reality of the graph. They are the ground truth and must remain unchanged. Negative edges, by contrast, are synthetic. They are created for training and evaluation, and their distribution is not fixed.\n\nAn intuitive analogy is a clinical trial. Positive edges are like actual outcomes observed in patients who received the treatment. We shouldn't bias these empirical evidence. Negative edges, on the other hand, are like control groups, which are constructed to serve as a comparison baseline. These can be designed in various ways (e.g., random, matched by age or condition), depending on the study goals.\n\nIf the control group is systematically different---say, composed of less healthy individuals---the evaluation of the treatment will be skewed. Likewise, in link prediction, if negative edges are sampled without considering node degree, they form an unfair comparison group (Appendix D), leading to benchmarks that reward models for exploiting degree imbalance rather than learning meaningful graph structure.\n\n> ### two more heuristic benchmarks ...  pairwise BPR[1].\n\nWe have extended our analysis to include BPR-style asymmetric sampling (Appendix C). While this changes the sampling distribution, we confirmed that it does not eliminate the influence of node degree on evaluation metrics such as AUC-ROC.\n\n> ### no related work or discussion on data augmentation and hard negative sampling\n\nWe respectfully disagree with labeling our method as data augmentation. Unlike augmentation,  our method cannot generate new positives, nor does it expand the dataset; its goal is not diversity, but distributional alignment for fair evaluation and learning.\n\nWe clarify how our method differs from hard negative mining. Hard negatives are typically model-dependent: they are selected dynamically based on how difficult they are for a given model to classify (see Zhang & Stratos, ACL 2021; Xuan et al., ECCV 2020). In contrast, the degree bias we address is model-agnostic. It arises from the statistical distributional mismatch between the positive and negative edges before training. \n\n> ### How do you tell different results on the figure by the certain variable (e.g., <k>=25/50)?\n\nEach curve is not a function of the variable but shows the results for a method in a different graph configuration. Figs. 3, 13, 14 together show the consistency of the performance gains across different settings.\n\n> ### Open question\n\nDegree is indeed a valuable signal. Our goal is not to discard degree, but to prevent its overemphasis caused by biased negative sampling, which inflates the performance of degree-based methods like PA.\n\nbiokg_drug exemplified this point, which has a strong rich-club structure—94% of edges connect the top 10% highest-degree nodes. Even with degree correction, PA still achieves an AUC-ROC of 0.9, confirming that degree remains predictive when appropriate.\n\nThanks again for your thoughtful and constructive comments which have improved our manuscript!", "claims_and_evidence": "One of the significant claims, that the proposed degree-corrected benchmark aligns better with recommendation tasks, is not convincing as follows:\n1.\tAlignment is only evaluated between AUC-ROC and VCMPR, the classification ability of recommenders, while neglecting the ranking ability (i.e., NDCG), another significant metric for recommenders.\n2.\tThe algorithms used for evaluations seem only to be link prediction methods rather than specific graph recommendation methods.\n3.\tThe graphs used for evaluations are also unknown, which may not be the typical user-item bipartite graph as well. Whether the proposed benchmark works on bipartite as well as its evidence (e.g., relation between bipartite and unipartite, analyses on the sparsity, etc) remains unclear.\nTo sum up, the evaluation setting for this claim is not convincing to argue that the proposed benchmark can be reliable in recommendation tasks/settings. Whereas, this claim would rather show an alignment and consistency between two evaluation metrics using the proposed benchmark.", "methods_and_evaluation_criteria": "1.\tThe motivation of the proposed benchmark is insufficient. First, the authors argue that implicit degree bias exists in positive sampling and straightforwardly force the negative sampling to adhere to the same distribution without explanation. It seems to be adding extra bias among negative edges and ignoring the existing bias among positive edges. Second, two more heuristic benchmarks based on the proposed one are neglected: one is to force the positive sampling to adhere to the uniform distribution, and the other is to trade off two distinct distributions by fixing one node on the positive edge as an anchor and uniformly sampling another node to form the negative edge (e.g., pairwise BPR[1]).\n2.\tRegarding the proposed negative sampling benchmark, it seems to implement the data augmentation on the negative edge candidate sets, duplicating those negative edges by the degree of end nodes. It serves as the hard negative sampling since high-degree nodes that used to form positive edges are more likely to form negative edges than before. However, no related work or discussion on data augmentation and hard negative sampling were discussed in this paper. Moreover, the methods used for evaluations are outdated. Therefore, it is doubtful whether the proposed benchmark is crucial for learning comprehensive graph structure and gaining substantial ranking changes for the latest link prediction methods compared with other benchmarks.\n\n[1]: Rendle, S., Freudenthaler, C., Gantner, Z., & Schmidt-Thieme, L. (2009). BPR: Bayesian Personalized Ranking from Implicit Feedback. UAI", "theoretical_claims": "All proofs for theoretical claims appear to be correct.", "experimental_designs_or_analyses": "All experimental designs and analyses have been carefully checked.", "relation_to_broader_scientific_literature": "While this paper refers to broader scientific literature on the domain of link prediction and sampling bias, the key contributions of this paper, which disclose the implicit degree bias and propose a corresponding new benchmark as a solution, should be innovative.", "essential_references_not_discussed": "To the best of my knowledge, most of the essential references have been discussed, despite those related to the questions below.", "other_strengths_and_weaknesses": "Strengths:\n1.\tThis paper discloses a critical issue in the link prediction task. The analysis and solutions should have a broad influence on the certain domain and pave the way for future studies.\n2.\tThe fundamental proofs are firm and reasonable.\n3.\tThis paper also clearly points out the limitations for further research.\n\nWeaknesses:\nThe presentation and architecture of this paper need to be improved:\n1.\tSubfigures should be carefully cropped and put in an appropriate position to ensure clarity and illustration.\n2.\tThe order of the different sections in the appendix needs to be reorganized to retain contextual coherence.\n3.\tSection 4 (Discussion) can be split into different subsections to make it more readable.", "other_comments_or_suggestions": "1.\tSection 4, paragraph 2, “To better [understand] the contribution…”\n2.\tAppendix B, equation 10, “\\Phi(z^-)=\\int^{z^-}_{[-]\\infty}…”\n3.\tAppendix D.5, equation 17, “…\\frac{…}{[min](C,m_i)}”\n4.\tAppendix D.5, equation 18, “RBO([U_{k,1},U_{k,2}],p):=…”", "questions_for_authors": "1.\tIn Appendix D.8., extra experimental results for the LFR benchmark, varying the average degree <k>, community size, and degree, should be shown in Figures 11 and 12. How do you tell different results on the figure by the certain variable (e.g., <k>=25/50)?\n2.\tOpen question: Is it possible that degree bias is one of the key features for graph learning and how to manipulate it properly matters indeed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zaASya5XJx", "reviewer": "Reviewer_2ZUx", "summary": "Observing existing link prediction models often sample partial negative edges for evaluation; this paper hypothesized that this sampled evaluation includes degree bias and would cause the link predictor model to over-fit to capture node degree signal in making a prediction. After empirical and theoretical analysis, this paper successfully demonstrates the degree of bias, proposes a degree unbiased negative sampling method, and demonstrates that the newly proposed benchmark would result in different rankings for some link prediction models and better align with recommender systems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, thank you for your time and for providing constructive comments on our manuscript!\n\n### > many recent works have come up with more advanced negative sampling strategy, and therefore, I am not sure whether the discovered bias would appear in other places, such as [1] Li, Juanhui, et al. \"Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking.\" Advances in Neural Information Processing Systems 36 (2023): 3853-3866.\n\nHeaRT benchmark is in fact precisely the benchmark proposed by the paper suggested by the reviewer.\nWe identified that the HeaRT benchmark in fact deviates from the retrieval tasks, and, when used as an unsupervised training objective, undermines the learning of communitiy structure, even if the communities are well separated.\nFrom theoretical standpoint, our method is more advanced, as it is grounded on the theoretical understanding of the degree bias, which is different from the HeaRT benchmark, which is a heuristic based on empirical observation of different bias.\nFrom empirical standpoint, the simplicity is the strength of our method, as it is computationally cheap, easy to implement. And being simple does not mean that it is less effective than more complex ones; in fact, we have demonstrated that it is more effective in terms of the alignment with retrieval tasks, and learning of community structure, than the HeaRT benchmark.\n\n> ### The paper does not test advanced ML models (e.g., BUDDY, NCN). How do these models relate to degree distribution and the proposed benchmark?\n\nWe have in fact included BUDDY in our experiments in our previous version of the manuscript. We emphasize that the degree bias is not specific to specific models, but a fundamental issue that is present in the training data. Since it is not agnostic to the model, the degree bias affects all models equally.\n\n> ### What is the goal of Sec 3.3? Is it about degree prediction or structure modeling? Clarify the intended contribution and application relevance.\n\nWe appreciate the request for clarification. The goal of Section 3.3 is to demonstrate that correcting degree bias enables models to capture more meaningful graph structure beyond node degrees.\nThis matters because link prediction is often used as a convenient unsupervised training objective for learning node representations.\nWe use community structure as a test case because it reflects higher-order organization not reducible to degree. The results show that models trained under our benchmark recover community assignments more accurately, highlighting the benchmark's value for representation learning.\n\n> ### Figure D discusses PA's advantage due to degree, but what about models that outperform PA? Do they also capture degree?\n\nOur intention is not to claim that PA is the top-performing model. We use PA as a controlled baseline because it relies solely on degree, making it ideal for isolating the effect of degree bias. It is expected that methods leveraging additional structural signals, e.g., distance and subgraph similarity, can outperform PA. However, we observe that many such \"advanced\" models fail to do so consistently, especially under standard benchmarks (Figure 2a). This is precisely the issue we aim to highlight.\n\n>###  How does degree bias behave under inductive link prediction where network growth may deviate from expected behavior?\n\nWe thank the reviewer for this question. We have, in fact, discussed this point in our discussion. To clarify, we explain this point in detail below.\n\nIn transductive settings, link prediction occurs between nodes in the training graph, while inductive settings involve predicting links for new nodes or unseen graphs. Inductive link prediction often uses similar approaches to transductive ones, such as classifying edges as positive or negative or retrieving the top-k most likely edges.\nImportantly, the degree bias persists in the inductive setting. For example, when sampling edges from new nodes uniformly at random, a node with $k$ new edges is $k$ times more likely to be selected than a node with $1$ new edge, mirroring the degree bias in the transductive setting.\n\nTransductive link prediction is as equally important as inductive ones and should not be neglected; for example, in citation networks, predicting missing citations between existing papers (transductive) is just as crucial as predicting citations for newly published papers (inductive), as it helps discover missing knowledge connections, assess research impact accurately, and maintain citation quality control.", "claims_and_evidence": "1. One concern here is the investigated bias is discovered based on the basic negative sampling strategy. However, many recent works have come up with more advanced negative sampling strategy and therefore, I am not sure whether the discovered bias would appear in other places, such as [1]\n\n[1] Li, Juanhui, et al. \"Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking.\" Advances in Neural Information Processing Systems 36 (2023): 3853-3866.", "methods_and_evaluation_criteria": "I have checked the designed method, especially the experiment, to discover the link prediction bias and can confirm it makes sense to me.", "theoretical_claims": "I have checked the theoretical claim.", "experimental_designs_or_analyses": "1. Although their described setup was once the most widely used, more recent works have proposed many different link prediction negative sampling strategies, and I am not very sure whether the discovered negative bias would also exist in these new methods.\n\n2. Throughout the analysis, the paper does not leverage any advanced machine learning model for link prediction, such as the more recently proposed BUDDY [1] and NCN [2]. Since both explicitly model the structures into the link prediction decision-making, it will be interesting to see how their performance relates to the degree distribution. \n\n[1] Chamberlain, Benjamin Paul, et al. \"Graph neural networks for link prediction with subgraph sketching.\" arXiv preprint arXiv:2209.15486 (2022). \n\n[2] Wang, Xiyuan, Haotong Yang, and Muhan Zhang. \"Neural common neighbor with completion for link prediction.\" arXiv preprint arXiv:2302.00890 (2023).", "relation_to_broader_scientific_literature": "This paper discloses the link prediction bias in a new degree-related way. \n\nAlthough the link prediction itself is a very long-standing problem, the discovered degree bias is a fresh perspective and may inform several implications related to link prediction, such as recommender systems where many negative sampling techniques are used.", "essential_references_not_discussed": "This paper has comprehensively reviewed existing works addressing link prediction bias.", "other_strengths_and_weaknesses": "Strengths:\n(1) This paper investigates a widely used technique for evaluating link prediction performance. The sampling bias discovered in this technique has never been systematically investigated before.\n\n(2) This paper provides a rigorous justification, not only in terms of theoretical analysis (e.g., derived the relationship between the degree distribution and the PA link prediction AUCROC) but also empirically analyzed the performance.\n\n(3) this paper also demonstrates several implications of using degree-corrected benchmarks, one for aligning with recommendation tasks (which is more aligned with real-world applications) and one for learning community structure.\n\nWeakness:\n(1) Throughout the analysis, the paper does not leverage any advanced machine learning model for link prediction, such as the more recently proposed BUDDY [1] and NCN [2]. Since both explicitly model the structures into the link prediction decision-making, it will be interesting to see how their performance relates to the degree distribution.\n\n[1] Chamberlain, Benjamin Paul, et al. \"Graph neural networks for link prediction with subgraph sketching.\" arXiv preprint arXiv:2209.15486 (2022). [2] Wang, Xiyuan, Haotong Yang, and Muhan Zhang. \"Neural common neighbor with completion for link prediction.\" arXiv preprint arXiv:2302.00890 (2023).\n\n(2) The motivation of the section 3.3 is unclear. If it aims to show that the proposed benchmark captures a lower node degree, would it be better to directly demonstrate that the learned node embedding can lead to better degree prediction performance? If it is to show the benchmark capture more salient graph structures, I wonder if there is any application where the link prediction performance requires capturing the substructures.", "other_comments_or_suggestions": "See the questions below.", "questions_for_authors": "(1) In Figure D, the author attributes the advantages of the PA model over others to its explicit ability to capture degree signals. However, I’m curious about models that outperform PA. What are these models, and do they also capture degree signals? It might be better to analyze those better than PA and derive insights on whether they can capture degree signals.\n\n(2) What about testing in the inductive setting, where the growth of the network might deviate from its expected behavior?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RKgHvqJcxf", "reviewer": "Reviewer_C2zd", "summary": "This paper studies the degree bias when benchmarking link prediction methods. Since most graphs follow a power-law distribution, the connected edges are very likely to be formed by two nodes with high degrees. However, the negative edges are often sampled by node, which results in a set of edges formed by nodes with lower degrees. This can cause an unfair benchmark such that LP methods only favoring node degree can achieve much better performance compared to others capturing predictive structural features like common neighbors, shortest-paths. Then the paper proposes a degree-corrected benchmark method and shows that it can provide a more robust evaluation benchmark for LP tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and constructive feedback! We also appreciate your remarks on the clarity of our analysis and writing. We have addressed each point raised as follow.\n\n## Dataset statistics\nWe agree that including all graph dataset statistics improves clarity. We have added a summary table in Appendix A listing the number of nodes, edges, average degree, and density for each dataset used in our experiments.\n\n## DDI and PPI networks\nWe would like to clarify that both the DDI and PPI networks from the OGB benchmark were already included in the original submission. We have revised the manuscript to make this more explicit by providing the tables. \n\n## Broader practical use cases\nThank you for raising this point. While we do not make new claims about specific downstream applications in this version, we have a sentence in the discussion section noting that the broader applicability of degree-corrected edge sampling. As mentioned, given the widespread use of edge sampling across graph machine learning tasks, we believe our findings have implications that extend beyond LP evaluation, potentially informing the design of benchmarks and training protocols more broadly.\n\nThank you again for taking the time to review our work!", "claims_and_evidence": "Yes. The claims made in the submission are clear and supported by evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Didn't check the correctness of the proofs. The theoretical claims are straightforward to understand.", "experimental_designs_or_analyses": "- It would be better to list all the graph datasets and their statistics in the appendix. It would be easier for readers to know what datasets are included in the experiments.", "relation_to_broader_scientific_literature": "- It suggests a more fair way to evaluate LP methods, which may encourage the development of modern LP methods to have a more practical impact on real-world problems.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strength:\n- The study of LP method benchmarking is meaningful, which can encourage to focus on LP methods that are better at capturing nuanced graph structures rather than naive node degrees.\n\n- The analysis of the paper is easy to understand. The writing is clear.\n\n- The empirical results support the assumptions and claims in the paper.\n\nWeakness:\n- The authors can discuss more about the practical use cases where degree-corrected benchmark aligns, beyond just recommendation task.\n\n- Two OGB datasets, DDI and PPA, can also be included in the discussion. These two datasets are highly dense and have high average node degree. It would be interesting to know whether the proposed benchmark can also reflect the nature of these graphs well.", "other_comments_or_suggestions": "Again, it would be better to list all the graph datasets and their statistics in the appendix. It would be easier for readers to know what datasets are included in the experiments.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses link prediction problem an argues that a common link sampling procedure used in evaluations is prone to produce biased results toward high degree nodes. The authors analyze this problem both empirically and theoretically. They also propose a degree-corrected link prediction benchmark and show that it provides a more robust evaluation framework for link prediction task. The reviewers raised several issues, including  the evaluation metric, which the authors addressed in their rebuttal. Overall, the consensus is that the paper presents a solid and interesting contribution and should be accepted to the conference.
Decision: Accept (poster)