Implicit degree bias in the link prediction task

## Abstract

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 validity of the link prediction benchmark itself has been rarely questioned.
Here, we show that the common edge sampling procedure in the link prediction task has an implicit bias toward high-degree nodes and produces a highly skewed evaluation that favors methods overly dependent on node degree, to the extent that a “null” link prediction method based solely on node degree can yield nearly optimal performance.
We propose a degree-corrected link prediction task that offers a more reasonable assessment that aligns better with the performance in 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.

## 1 Introduction

Standardized benchmarks such as ImageNet [, ] and SQuAD [, ] play a pivotal role in guiding the evolution of machine learning, creating a competitive environment that propels innovation by setting clear, measurable goals.
A core benchmark for graph machine learning is the link prediction task, the task of identifying missing edges in a graph, with diverse applications including the recommendations of friends and contents [, , , ], knowledge discoveries [, ], and drug development [, , , , , , ].
The link prediction benchmarks have been serving as a crucial benchmark that facilitates quantitative evaluations and drives the advancement of graph machine learning techniques [, , , , , , ].

Despite its significant role in graph machine learning, the link prediction benchmark itself has rarely been examined critically for its effectiveness, reliability, and potential biases.
A widely-used link prediction benchmark evaluates methods by their ability to classify pairs of nodes as either connected or unconnected [, , ].
The connected node pairs (i.e., edges) are randomly sampled from existing edges as the hidden positive set, and an equal number of node pairs are randomly chosen from unconnected node pairs.
Existing criticisms mainly consider the disconnect from real-world scenarios.
For instance, unconnected node pairs are far more common than connected node pairs because of the sparsity of edges in graphs [, ], which can lead to biased performance evaluations [, , , , ].
Additionally, while the link prediction benchmark tests methods by classifying a predefined set of potential edges, the practical link prediction task involves identifying the potential edges from the entire graph.
Despite the misalignment with real-world scenarios, high benchmark performance is often regarded as a testament to successful learning in graph machine learning [, , , , , , , , , ].

Here, we argue that the standard link prediction benchmark has a fundamental and severe bias that favors methods that exploit node degree information (i.e., the number of edges a node has).
The degree bias arises from the sampling of edges used for performance evaluations, i.e.,
when sampling an edge from a graph uniformly at random, a node with $k$ edges is $k$ times more likely to be selected than a node with a single edge ($k=1$).
Meanwhile, the negative set of edges is randomly sampled from unconnected node pairs, which do not have this degree bias.
As a result, we have a distinct and useful feature (degree) for the methods that can be leveraged without understanding any non-trivial structural features of the graph.
We show that this degree bias is so profound that a “null” link prediction method based solely on node degree can yield nearly optimal performance, questioning the usefulness of the link prediction benchmark even as a general objective for graph machine learning and raising awareness on the need for being more intentional and careful about what the evaluation tasks themselves actually evaluate.

To address this bias, we propose a degree-corrected link prediction benchmark that samples the unconnected node pairs with the same degree bias.
We demonstrate that the degree-corrected link prediction benchmark can better capture the performance of algorithms in the recommendation task.
Moreover, we show that the degree-corrected benchmark trains graph neural networks more effectively by reducing overfitting to node degrees, thereby improving the learning of community structure in graphs.

## 2 Design flaw of the link prediction benchmark

### Preliminary

We focus on the unweighted, undirected graph $G=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of nodes and $\mathcal{E}$ is the set of edges.
We assume that $G$ has no self-loops, no multiple edges, and is highly sparse ($|\mathcal{E}|\ll|\mathcal{V}|^{2}$), which is a common characteristic of real-world graphs [, ].
Degree $k_{i}$ of a node $i\in\mathcal{V}$ is the number of edges emanating from node $i$.
We use $\sim$ to denote proportional relationships.
We exclude node attributes from data, if present, to ensure consistency across all graph-based link prediction methods.

Figure: Figure 1: Illustration of the degree bias in the link prediction benchmark. A: A node with degree $k$ appears $k$ times in the edge list, making it $k$ times more likely to be sampled as a 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^{5}$ nodes and $M=10^{6}$ edges. The y-axis, “CCDF”, denotes the complementary cumulative distribution function, representing the probability that a 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 the expected AUC-ROC based on the “null” link prediction method that uses only the node degree information (Eq. (9)). D: AUC-ROC of 26 methods across 90 graphs. PA outperforms 54% of the method on average across 90 graphs and outperforms most other methods in the most heterogeneous graphs. E: AUC-ROC of the same methods for the degree-corrected benchmark, showing that nearly 86% of the methods perform better than PA on average.
Refer to caption: x1.png

### Link prediction benchmark

The standard procedure for link prediction benchmarks is outlined as follows [, , , , , , , , , ].
First, we randomly sample a fraction $\beta$ of edges from the edge set $\mathcal{E}$ as *positive edges*.
Second, we randomly sample an equal number of unconnected node pairs with replacement from the node set $\mathcal{V}$ as *negative edges*.
We resample the negative edges 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 $s_{ij}$ indicates a higher likelihood of an edge existing between the nodes.
Fourth, the effectiveness of a method is 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 negative edges [, , , , ] (Section 4), this outlined procedure has been widely used [, , , , , , , , , ].

### Sampling bias due to node degree

A well-known, counterintuitive fact about graphs is that a uniform random sampling of edges results in a *biased* selection of nodes in terms of degree [, , , , ].
The bias arises because a node with $k$ edges appears $k$ times in the edge list and thus $k$ times more likely to be chosen than a node with $k^{\prime}=1$ edge (e.g., node 1 and 4 in Fig. 1A).
Consequently, for a graph with degree distribution $p(k)$, the nodes in the positive edges have degree distribution $p_{\text{pos}}(k)$ proportional to $\sim k\cdot p(k)$.
By normalizing $k\cdot p(k)$, the degree distribution of the positive edges is given by

$$ $\displaystyle p_{\text{pos}}(k)=\frac{1}{\sum_{\ell}\ell p(\ell)}k\cdot p(k)= \frac{1}{\langle k\rangle}k\cdot p(k),$ (1) $$

where $\langle k\rangle$ is the average degree of the graph.
On the other hand, the nodes in the negative edges are uniformly sampled from the node list (i.e., $\mathcal{V}$) and thereby have degree distribution $p_{\text{neg}}(k)$ identical to $p(k)$ (i.e., $p_{\text{neg}}(k)=p(k)$).

We demonstrate the degree bias using the Price graph of $N=10^{5}$ nodes and $M=10^{6}$ edges, with the power-law degree distribution approximating $p(k)\propto k^{-3}$ (Fig. 1B).
We sample $\beta=0.25$ of the edges uniformly at random from $\mathcal{E}$ as positive edges, together with the same number of unconnected node pairs by uniformly sampling nodes from $\mathcal{V}$.
The degree distributions for nodes in the positive and negative edges closely follow $p_{\text{pos}}(k)$ and $p_{\text{neg}}(k)$, respectively, demonstrating the sampling bias due to node degree.
We note that the degree bias is not specific to the Price graph but appears for any graph with non-uniform degree distribution.

### Impact of degree bias on the link prediction benchmark

We demonstrate the impact of degree bias on link prediction benchmark (Fig.1D).
We evaluated 26 link prediction methods across 90 graphs. These methods include 7 network topology-based methods (e.g., Common Neighbors (CN) []), 13 graph embedding methods (e.g., Laplacian EigenMap (EigenMap) []), 2 network models (e.g., Stochastic Block Model (e.g., SBM) []), and 4 graph neural networks (GNNs) (e.g., Graph Convolutional Network (GCN) []). Detailed descriptions of the methods and graphs are available in SI Section 1.
We set the fraction of test edges to $\beta=0.25$ and repeat the experiment 5 times.
We quantify the heterogeneity $\sigma$ of node degree by fitting a log-normal distribution to $p(k)$ and calculating its variance parameter $\sigma$. We will show that $\sigma$ is a good indicator of the impact of degree bias in Section 2.

We focus on the Preferential Attachment (PA) link prediction method, which calculates the prediction score $s_{ij}=k_{i}k_{j}$ using only node degrees.
Although PA is a crude method that neglects key predictive features such as the number of common neighbors and shortest distance [, , , , ], it still outperforms more than half of the advanced methods with an average AUC-ROC of 0.83 (ranked 13th out of 26 methods; see Fig. 2A).
PA performs better as the heterogeneity of node degrees increases.
The outperformance of PA is attributed to the 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.
As a result, the current benchmark design favors methods that make predictions based largely on node degrees.

### Theoretical analysis

Many empirical graphs exhibit heterogeneous degree distributions, with a few nodes having an exceptionally large degree and most having a small degree.
The heterogeneous degree distributions are often characterized by power-law degree distribution $p(k)\propto k^{-\alpha}$ with $\alpha\in(2,3]$ (i.e., scale-free networks) [, , , ] or log-normal distributions [, ].
While the power-law and log-normal distributions are both continuous, they are often used to characterize the discrete degree distribution and provide approximations [, , , , , ].
We show that the AUC-ROC for PA reaches the nearly maximum under log-normal distributions with heterogeneous node degrees. See SI Section 2.2 for the case of power-law distributions.

Let us consider a general degree distribution $p(k)$ without restricting ourselves to log-normal distributions.
The AUC-ROC has a probablistic interpretation []: it is the probability that the score $s^{+}$ for the positive edges is larger than the score $s^{-}$ for the negative edges.
Recalling that PA computes $s_{ij}=k_{i}k_{j}$, the AUC-ROC for PA is given by

$$ $\displaystyle\text{AUC-ROC}=P(s_{i^{-},j^{-}}\leq s_{i^{+},j^{+}})=P(k_{i^{-}} k_{j^{-}}\leq k_{i^{+}}k_{j^{+}}),$ (2) $$

where $i^{\pm}$ and $j^{\pm}$ represent the nodes of the positive and negative edges, respectively.
Now, let us assume that $p(k)$ follows the log-normal distribution, $\text{LogNorm}(k\mid\mu,\sigma^{2})$, given by []:

$$ $\displaystyle p(k)=\text{LogNorm}(k\mid\mu,\sigma^{2})=\frac{1}{\sqrt{2\pi} \sigma k}\exp\left[-\frac{(\ln k-\mu)^{2}}{2\sigma^{2}}\right],$ (3) $$

where $\mu$ and $\sigma$ are the parameters of the log-normal distribution.
The mean of the log-normal degree distribution is $\langle k\rangle=\exp(\mu+\sigma^{2}/2)$ [].
By substitutiong Eq. (3) into Eq. (1), we derive the
degree distribution of nodes in the positive edges as:

$$ $\displaystyle p_{\text{pos}}(k)$ $\displaystyle=\frac{k}{\langle k\rangle}\frac{1}{\sqrt{2\pi}\sigma k}\cdot\exp \left[-\frac{(\ln k-\mu)^{2}}{2\sigma^{2}}\right]$ $\displaystyle=\frac{1}{\sqrt{2\pi}\sigma k}\exp\left[-\frac{1}{2\sigma^{2}} \left((\ln k)^{2}-2\mu\ln k+\mu^{2}\right)+\ln k-\mu-\sigma^{2}/2\right]$ $\displaystyle=\frac{1}{\sqrt{2\pi}\sigma k}\exp\left[-\frac{1}{2\sigma^{2}} \left((\ln k)^{2}-2(\mu+\sigma^{2})\ln k+\mu^{2}+2\mu\sigma^{2}+\sigma^{4} \right)\right]$ $\displaystyle=\frac{1}{\sqrt{2\pi}\sigma k}\exp\left[-\frac{(\ln k-\mu-\sigma^ {2})^{2}}{2\sigma^{2}}\right]=\text{LogNorm}(k\mid\mu+\sigma^{2},\sigma^{2}).$ (4) $$

Equation (4) indicates that the degree distribution for nodes in the positive edges also follows a log-normal distribution, parameterized by $\mu+\sigma^{2}$ and $\sigma$.

We derive the AUC-ROC for PA by leveraging a unique characteristic of log-normal distributions, i.e., the logarithm $\ln k$ of log-normally-distributed degree $k$ follows a normal distribution with mean $\mu$ and variance $\sigma^{2}$, i.e.,

$$ $\displaystyle P(\ln k)=\text{Norm}(k\mid\mu,\sigma^{2}),\;\text{where}\;\; \text{Norm}(k\mid\mu,\sigma^{2})=\frac{1}{\sqrt{2\pi}\sigma}\exp\left[-\frac{( k-\mu)^{2}}{2\sigma^{2}}\right].$ (5) $$

We assume no degree assortativity in the graph, where $P(k^{+}_{i},k^{+}_{j})=P(k_{i})P(k_{j})$. Although empirical graphs often exhibit degree assortativity, our results indicate that it does not significantly impact the AUC-ROC (SI Section 2.1).
For the negative edges, the distribution for $\ln s_{i^{-},j^{-}}=\ln k^{-}_{i}+\ln k^{-}_{j}$ follows a normal distribution with mean $2\mu$ and variance $2\sigma^{2}$, as the sum of independent normal variables also forms a normal distribution with additive means and variances [], i.e.,

$$ $\displaystyle P(\ln s_{i^{-},j^{-}})=\text{Norm}\left(\ln s_{i^{-},j^{-}}\mid 2 \mu,2\sigma^{2}\right).$ (6) $$

For the positive edges, the degree distribution also follows a log-normal distribution (Eq. (4)). Thus, the distribution for $\ln s_{i^{+},j^{+}}=\ln k^{+}_{i}+\ln k^{+}_{j}$ is given by

$$ $\displaystyle P(\ln s_{i^{+},j^{+}})=\text{Norm}\left(\ln s_{i^{+},j^{+}}\mid 2 \mu+2\sigma^{2},2\sigma^{2}\right).$ (7) $$

By using Eqs. (2), (6), and (7), we have

$$ AUC-ROC $\displaystyle=P(\ln s^{-}<\ln s^{+})$ $\displaystyle=\int_{-\infty}^{\infty}\text{Norm}(x^{-}\mid 2\mu,2\sigma^{2}) \left[1-\int^{x^{-}}_{-\infty}\text{Norm}(x^{+}\mid 2\mu+2\sigma^{2},2\sigma^{ 2})\text{d}x^{+}\right]\text{d}x^{-}$ $\displaystyle=1-\int_{-\infty}^{\infty}\text{Norm}(x^{-}\mid 2\mu,2\sigma^{2}) \int^{x^{-}}_{-\infty}\text{Norm}(x^{+}\mid 2\mu+2\sigma^{2},2\sigma^{2})\text {d}x^{+}\text{d}x^{-}$ (8) $$

We reparameterize Eq. (8) by using $z^{\pm}=\frac{x^{\pm}-2\mu}{\sqrt{2}\sigma}$. Noting that $\text{Norm}(x^{-}\mid 2\mu,2\sigma^{2})\cdot\sqrt{2}\sigma=\text{Norm}(z^{-}
\mid 0,1)$ and ${\rm d}x^{\pm}=(\sqrt{2}\sigma){\rm d}z^{\pm}$, we have

$$ $\displaystyle P(\ln s^{-}<\ln s^{+})$ $\displaystyle=1-\int_{-\infty}^{\infty}(2\sigma^{2})\text{Norm}(x^{-}\mid 2\mu ,2\sigma^{2})\int^{x^{-}}_{-\infty}\text{Norm}(x^{+}\mid 2\mu+2\sigma^{2},2 \sigma^{2})\cdot\text{d}z^{+}\text{d}z^{-}$ $\displaystyle=1-\int_{-\infty}^{\infty}\text{Norm}\left(z^{-}\mid 0,1\right) \int^{z^{-}}_{-\infty}\text{Norm}\left(z^{+}-\sqrt{2}\sigma\mid 0,1\right) \text{d}z^{+}\text{d}z^{-}$ $\displaystyle=1-\int_{-\infty}^{\infty}\text{Norm}(z^{-}\mid 0,1)\Phi\left(z^{ -}-\sqrt{2}\sigma\right)\rm{d}z,$ (9) $$

where $\Phi(z^{-})$ is the cumulative distribution function for the standard normal distribution, i.e., $\Phi(z^{-})=\int_{\infty}^{z^{-}}\text{Norm}(y\mid 0,1){\rm d}y$.
Equation (9) suggests the key behavior of AUC-ROC for PA.
The AUC-ROC for PA is an increasing function of the parameter $\sigma$ of the log-normal distribution (Fig. 1C).
The parameter $\sigma$ of the log-normal distribution controls the spread of the distribution, with larger $\sigma$ resulting in a more fat-tailed distribution.
While our assumptions about the log-normal degree distribution and degree assortativity may not always align with real-world data, Eq. (9) still effectively captures the AUC-ROC behavior for PA (Fig. 1C). Further analysis of power-law distributions is described in SI Section 2.2.

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 benchmark is an effective objective of graph machine learning.

## 3 The degree-corrected link prediction benchmark

Figure: Algorithm 1 Degree-corrected link prediction benchmark

The link prediction benchmark yields biased evaluations due to mismatched degree distributions between positive and negative edges, i.e., $p_{\text{neg}}(k)\neq p_{\text{pos}}(k)$.
To mitigate the mismatch, we introduce *the degree-corrected link prediction benchmark* that samples negative edges with the same degree bias as positive edges (Algorithm 1).
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 positive edges.
Consequently, the positive and negative edges in the degree-corrected benchmark are indistinguishable based on node degrees.
A Python package for the degree-corrected benchmark is available at [https://github.com/skojaku/degree-corrected-link-prediction-benchmark](https://github.com/skojaku/degree-corrected-link-prediction-benchmark).

### Comparison of the benchmark evaluations

We reevaluated the methods with the degree-corrected link prediction benchmark (Fig. 1E).
We use the same parameters in the original link prediction benchmark for all methods.
There is some agreement between the original and degree-corrected benchmarks (Fig. 2A).
For example, they rank GAT and LRW as top performers, whileNB, SGTAdjNeu, and SGTAdjExp 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 26 methods.
The AUC-ROC near 0.5 for PA suggests that it performs as random guessing, confirming that the degree-corrected benchmark successfully makes the degree distributions of positive and negative edges indistinguishable.
Other methods such as LPI, GIN also experience a substantial drop in their rankings from 2nd to 10th and 9th to 20th, respectively (Fig. 2A).
On the other hand, GCN, node2vec, DeepWalk, and EigenMap increase their rankings substantially from 14th to 2nd, 17th to 5th, 21th to 7th, and 20th to 12th, respectively (Fig. 2A).

Figure: Figure 2: Comparative analysis of link prediction and recommendation benchmarks. A: Rank changes across the original and degree-corrected link prediction benchmarks. The red and blue lines indicate the methods that change their rankings more than 8 places from the original one. We compute the ranking of the methods based on the AUC-ROC of the link prediction benchmark and compare it against the ranking based on the link retrieval task. B: The degree-corrected benchmark ranks link prediction methods more similarly with the recommendation task than the original benchmark. The RBO (rank-biased overlap) represents the similarity between the ranking of the link prediction methods and that based on the recommendation task.
Refer to caption: x2.png

### The degree-corrected benchmark aligns better with recommendation tasks

Link prediction methods are often used in recommendation tasks [, , , , ].
However, there are key differences between standard link prediction benchmarks and recommendation tasks [, , ].
In the link prediction benchmark, a set of potential edges is provided, and the goal is to determine the existence of these edges.
In contrast, recommendation tasks require identifying potential edges from the entire graph without a preset list of candidate edges.
This makes recommendation tasks more challenging due to the large number of unconnected nodes that could be just as likely to have an edge as connected nodes.
For example, a link prediction task in a social network involves predicting friendships from a given list of potential friends.
On the other hand, recommendation tasks must evaluate all potential unlisted friendships, including absent but equally probable friendships as existing ones.
Nevertheless, given the common use of link prediction in recommendation tasks, it is crucial that the link prediction benchmarks accurately reflect the performance in the recommendation tasks.

We assess how well the link prediction benchmark provides coherent performance assessment with the recommendation task as follows.
In the common recommendation task [], the method recommends, for each node $i$, its top $C=50$ nodes $j$ based on the highest scores $s_{ij}$.
We note that our results are consistent regardless of the chosen $C$ value (refer to SI Section 2.3).
The effectiveness of the recommendations is then measured using the vertex-centric max precision recall at $C$ (VCMPR@C) defined as the higher of the precision and recall scores at $C$ [].
The VCMPR@C is designed to evaluate recommendation methods and addresses the excessive penalty on the precision scores at $C$ for small-degree nodes, which often have low precision due to their limited number of edges.
We perform this task five times and average the VCMPR@C scores across different runs.

For each graph, we evaluate the alignment between the rankings based on the recommendation task and those based on the link prediction benchmarks using Rank Biased Overlap (RBO) [].
RBO is a ranking similarity metric with larger weights on the top performers in the two rankings.
A larger RBO score indicates that the top performers in the two rankings are more similar.
The weights on the top performer are controlled by the parameter $p\in(0,1)$.
While we set $p=0.5$ in our experiment, we confirmed that our results are robust to the choice of $p$ (SI Section 2.3).

Our results from 90 graphs show that the degree-corrected benchmark achieves higher RBO scores than the original benchmark. We find consistent results for different values of $C$ and parameter $p$ of the RBO (SI Section 2.3).
These results indicate that the degree-corrected benchmark more accurately mirrors the performance in recommendation tasks, providing a more reliable measure of the effectiveness of methods in practical applications.

### Degree-corrected benchmark facilitates the learning of community structure

Figure: Figure 3: The degree-corrected benchmark improves GNNs in learning community structure in the LFR graphs. The LFR graphs consist of $3,000$ nodes with the average degree of $25$. A: The performance of community detection for the LFR graphs with a power-law degree distribution with $\tau_{1}=3.0$ as a function of $\mu$. B: The average performance (by the area under the performance curve) shows that the methods trained with the degree-corrected training set outperform their counterparts trained with the traditional link prediction training set. C, D: The same plots for LFR graphs with a fatter power-law degree distribution with $\tau_{1}=2.5$. The error bars represent the 95% confidence interval estimated by a bootstrap of 1,000 repetitions.
Refer to caption: x3.png

The link prediction benchmark is a common unsupervised learning objective for GNNs [, , , ].
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-corrected 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 [, , ].
The community detection task identifies densely connected groups (i.e., communities) in a graph.
Communities often correspond to functional units (e.g., social circles with similar opinions and protein complexes) in the graph, and detecting communities is a crucial task in many graph applications [, , , , ].
Specifically, we test the GNNs by using the Lancichinetti-Fortunato-Radicchi (LFR) community detection benchmark [], a standard benchmark for community detection [, , , ].
The LFR benchmark generates synthetic graphs with predefined communities as follows.
Each node $i$ is assigned a degree $k_{i}$ from a power-law distribution $p(k)\sim k^{-\tau_{1}}$, with maximum degree $k_{\text{max}}$.
Nodes are randomly grouped into $L$ communities, with community sizes (i.e., the number of nodes in a community) following another power-law distribution $p(n)\sim n^{-\tau_{2}}$ bounded between $n_{\text{min}}$ and $n_{\text{max}}$.
Edges are then formed such that each node $i$ connects to a fraction $1-\mu$ of its $k_{i}$ edges within its community and the remaining fraction $\mu$ to nodes in other communities.
We generate 10 graphs for $\mu\in\{0.05,0.1,0.15,\ldots,0.95,1\}$ using the following parameter values: the number of nodes $N=3,000$, the degree exponent $\tau_{1}\in\{2.5,3\}$, the average degree $\langle k\rangle=25$, the maximum degree $k_{\text{max}}=1000$, the community-size exponent $\tau_{2}=3$, the minimum and maximum community size $n_{\text{min}}=100$ and $n_{\text{max}}=1000$. We obtained qualitatively similar results for different values of the parameters of the LFR benchmark (SI Section 2.5).

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 to detect communities, where $K$ is set to 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 benchmarking node embeddings for the community detection task [, , ].
We measure the performance of GNNs by comparing the detected communities against the true communities using the adjusted element-centric similarity [, , ], where higher scores indicate a higher similarity between the node partitions for the true and detected communities.
We observe qualitatively similar results for partition similarities based on the normalized mutual information (SI Section 2.4).

All GNNs, except for GIN, perform well when $\mu\leq 0.5$, where communities are distinct and easily identifiable, but their performance declines as $\mu$ increases (Fig. 3A).
Across a broad range of $\mu$, 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 a more heterogeneous degree distribution (Fig. 3C and D).
This indicates that degree correction effectively reduces overfitting to node degrees, enhancing the learning of community structures in graphs.

## 4 Discussion

We showed that the common link prediction benchmark suffered from a sampling bias arising from node degree and could mislead performance evaluations by favoring methods that overfit to node degree.
To address this issue, we proposed a degree-corrected benchmark that corrected the discrepancy between the degree distributions of the connected and unconnected node pairs sampled for performance evaluation.
This new benchmark provided more accurate evaluations that aligned better with the performance for recommendation tasks and also improved training for GNNs by reducing the overfitting to node degree and facilitating the learning of communities in the graph.

While we focused on node degree, other features can also effectively distinguish between positive and negative edges [, , , ].
Previous studies showed that nodes in the negative edge set tend to be distant from each other, making them easily identifiable by computing the distance between nodes [, ].
Our findings add a new direction to the important examination of the fundamental graph machine-learning task by demonstrating that node degree, a simpler structural attribute, is sufficient, in many cases, for differentiating the positive and negative edges.
We note that the degree bias partially accounts for the distance discrepancy in the positive and negative edges because a high degree heterogeneity can induce loops of short length in the graph [].
Crucially, the degree bias stems from the degree distribution rather than the connections between nodes and thus is present in any non-regular graph.
More broadly, the degree bias is manifested through the edge sampling process, a general technique for evaluating and training graph machine learning.
For instance, mini-batch training [, ], which samples subsets of edges for efficient GNN training, may also exhibit bias due to node degrees, leading to skewed training sets.
Given the widespread use of edge sampling across various graph machine-learning tasks, our findings have broad implications beyond link prediction benchmarks, extending to a range of benchmarks and training frameworks.

Our study has several limitations.
First, we employed standard hyperparameters (e.g., embedding dimensions, GNN layers) across all link prediction methods, achieving reasonable performance in link prediction and community detection tasks. Given the extensive variety of methods and hyperparameters, we did not optimize hyperparameters for specific tasks. Although fine-tuning could potentially enhance performance [], our primary goal was to evaluate the effectiveness of link prediction benchmarks, not to compare the difference in performances between different link prediction methods.
Second, we did not explore the reasons behind the varying performance of different link prediction methods.
It is important to note that there is no single link prediction method that is universally effective for all graphs because the performance of link prediction methods depends on the assumptions on the graph structure to make the predictions [].
Future studies will explore an in-depth examination of the link prediction methods on specific graphs.
Third, we focus on community structure to test the effectiveness of the proposed benchmark as a training framework.
However, other non-trivial graph structures, such as centrality, could be tested through network dismantling benchmarks [].

Even with the aforementioned limitations, our results suggest that sampling graph data is a highly non-trivial task than commonly considered.
Because sampling edges from a graph is integral to evaluating and training graph machine learning methods, our results underline the importance of careful sampling to ensure the effectiveness of evaluations and training of graph machine learning methods.

## 5 Broader Impacts

Our findings indicate that the standard benchmark promotes link prediction algorithms that enhance the “rich-get-richer” effect, where well-connected nodes tend to gain even more connections. This effect, known as *preferential attachment*, is common in various societal contexts.
For instance, popular individuals often gain more friends, widely shared content spreads further, and frequently cited papers are more likely to attract additional citations.
While preferential attachment can benefit distributing resources and recognition, 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 with less citations [].
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 negating the degree bias, promoting fairer algorithm evaluations, and supporting the development of fairness-aware machine learning methods.

### Code and Data Availability

We provide the code to reproduce the results in this study at [https://github.com/skojaku/degree-corrected-link-prediction-benchmark](https://github.com/skojaku/degree-corrected-link-prediction-benchmark).
The network data used in this study is available at [https://figshare.com/projects/Implicit_degree_bias_in_the_link_prediction_task/205432](https://figshare.com/projects/Implicit_degree_bias_in_the_link_prediction_task/205432).

## Acknowledgments and Disclosure of Funding

R.A., M.K., O.C.S., S.K., and Y.Y.A. acknowledge the support by the Air Force Office of Scientific Research under award number FA9550-19-1-0391.
The authors acknowledge the computing resources at Binghamton University and Indiana University and thank NVIDIA Corporation for their GPU resources.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1) What is the motivation for the proposed unbiased degree distribution?

2) What other similar sources of bias could affect link prediction performance? Could the proposed approach be generalized?

3) Why state-of-the-art link prediction algorithms were not considered in the experiments?
soundness: 2
strengths: - The paper addresses an important issue in the evaluation of link prediction methods.
- The paper is clear and easy to follow.
- The paper applies multiple datasets and methods to support its hypothesis.
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 lower-degree nodes compared with the positive ones. This issue is analyzed both empirically and theoretically. To address the issue, the paper proposes a degree-correlated sampling procedure that generates negative pairs that have similar degrees as positive ones. Using this new benchmark provides a different ranking of link prediction approaches, most notably with preferential attachment achieving significantly worse results compared with GNN-based methods.
weaknesses: - The definition of unbiased distribution used in the paper needs better justification
- The focus on node degree is a bit narrow given all the possible structural properties that might be biased in negative samples
- The paper does not consider state-of-the-art link prediction methods like BUDDY and NCN.

Detailed comments:

First, I need to disclose that I reviewed this paper earlier, and the authors have improved the paper significantly based on previous reviews. Still, there are some points that I believe could be better addressed:

1) Unbiased distribution: based on the paper, the unbiased degree distribution for disconnected test pairs (no class) should be the same as the one for connected test pairs (yes class). I am still not convinced why that should be the case and how the degree can still be a useful feature in this setting (as mentioned in the paper). For instance, if the proposed sampling algorithm is applied to a Barabasi-Albert graph, how would link prediction algorithms perform? Shouldn't the PA algorithm perform well in this case even if samples are unbiased?

2) Other types of bias: the paper focuses on degree bias but one could expect any connectivity-based metric to also produce a similar bias. The authors also mention shortest paths but there could be many others.

3) Link prediction methods: the proposed link prediction methods are not state-of-the-art, as shown in the papers below:

Chamberlain et al. Graph Neural Networks for Link Prediction with Subgraph Sketching.

Wang et al. Neural Common Neighbor with Completion for Link Prediction.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
questions: (1) In addition to the PA model that only belongs to the heuristic-based method, I am wondering whether we can design a more explicit method using degree, for example, designing an MLP based on only the node degree and train the model for link prediction compared with designing an MLP not based on degree and train the model for link prediction, and compare their performance. Experimenting with this way could further demonstrate such a degree of bias, which could also be captured by the learning-based method.

(2) Since we will split the original edges into training/validation/testing and we will remove testing edges in both message-passing and setup of supervision edges for training, so we also change our graph and I am wondering whether such graph change would cause the heterogeneity also change? Since following the same logic, for high-degree nodes, their neighboring edges are more easily selected as testing edges and removed

(3) 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.

(4) There are some other references discussing the degree-related bias:
 [1] Wang, Yu, and Tyler Derr. "Degree-related bias in link prediction." 2022 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 2022.
 [2] Subramonian, Arjun, Jian Kang, and Yizhou Sun. "Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks." arXiv preprint arXiv:2404.03139 (2024).

(5) I am wondering, specifically for large-scale networks, such as the ones with nodes beyond 100,000 nodes, what would the conclusion be? I noticed from Table 2,3,4, currently the most large network is Collab (232865), which is still far less than the number of nodes in the real-world large social network. I am wondering, for those networks, whether the observed degree bias still exists. Since, for small-scale networks, we can very easily conduct full negative edge analysis rather than sample negative edges, it is essential to analyze the large-scale social network.
soundness: 3
strengths: (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.

(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.

(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.
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.
weaknesses: (1) When empirically demonstrating the relationship between the degree bias and link prediction performance, this paper only leverages the preferential attachment model, which might limit the generalizability of some observations drawn in the Figure. See Question 1 for more details.

(2) 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. Furthermore, the largest graph used in this paper only has up to 100,000 nodes. It might be better to include a further larger graph such as citation2. Moreover, it would be more important to investigate the degree of bias for very large networks since, on small networks, it is very easy to conduct full negative edge link prediction. See question (5) for more suggestions.

[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).
[3] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." Advances in neural information processing systems 33 (2020): 22118-22133.

(3) 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.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Q1. Can the authors clarify the hyperparameter choices for GNNs? Specifically, were parameters optimized for each benchmark setting, and if so, did tuning impact performance rankings? If no such tuning was done, I'm skeptical about the validity of the results.

Q2. What about testing in the inductive setting, where the growth of the network might deviate from its expected behavior?

Q3. Given that the degree-corrected benchmark produces substantial performance shifts, can the authors clarify how this effect arises purely from changing the negative edge sampling process?

Q4. How does the degree-corrected benchmark compare to alternative methods for addressing biases, such as distance-aware benchmarks or methods using degree-aware sampling? Although this is mentioned in the Discussions section, no result has been presented to back this up.

Q5. Could the authors provide additional evidence on the potential overfitting to large-degree nodes within the degree-corrected benchmark? Quantifying this effect with metrics like clustering or centrality could clarify the approach’s limitations.

Q6. Why is Section 2.5 (assuming no degree assortativity) relevant here, given that real-world graphs often exhibit assortative mixing? How does this assumption affect the applicability of your results to real-world graphs?

Q7. Upon simple searches online, I could find other works that alleviate the degree-induced or centrality-induced in GNNs. How do you think this benchmark will complement it? [1] [2]

Q8. I think this sort of study in the Knowledge Graph datasets would be a significant contribution, too, since link prediction is much more prevalent and often complex tasks (such as complex query answering) can be broken down into multiple link prediction tasks naively. The effects, I'm assuming, might be much more profound there. There are similar studies in that domain [3] [4].

[1] Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. 2022. RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network. In Proceedings of the ACM Web Conference 2022 (WWW '22).

[2] Arun, Arvindh, et al. "CAFIN: Centrality Aware Fairness Inducing IN-Processing for Unsupervised Representation Learning on Graphs." ECAI 2023.

[3] Kamigaito, Hidetaka, and Katsuhiko Hayashi. "Comprehensive analysis of negative sampling in knowledge graph representation learning." International Conference on Machine Learning. PMLR, 2022.

[4] Madushanka, Tiroshan, and Ryutaro Ichise. "Negative Sampling in Knowledge Graph Representation Learning: A Review." arXiv preprint arXiv:2402.19195 (2024).
soundness: 3
strengths: 1. Originality: This work identifies and addresses an under-examined issue in graph machine learning benchmarks - implicit degree bias in sampling in the "standard" link prediction benchmark. By identifying and correcting this bias, the authors contribute a novel perspective on the evaluation methodologies that underpin graph-based tasks. This originality lies in highlighting how benchmark designs can inadvertently favor certain features, like node degree, thus affecting model evaluation in unintended ways. The proposed degree-corrected benchmark, although quite simple, offers an approach for mitigating this bias.

2. Quality: The paper provides a thorough analysis of degree bias, including both theoretical insights (in a specific setting) and empirical validation. The experiments span a range of datasets and link prediction methods, offering a well-rounded evaluation of the proposed benchmark's effectiveness.

3. Clarity: The paper generally communicates its objectives, findings, and implications well, especially in its discussion of degree bias and its impact on link prediction tasks. The premise is clear from the very start and is easy to read and follow, although some figures are quite hard to follow. The discussion section is well written and properly acknowledges pitfalls and potential scope in the future.

4. Significance: This work has some implications for the evaluations in this field. With the potential bias identified, newer methods that do not evaluate in any already special configurations of the link prediction benchmarks can adopt this.
summary: This work highlights how the "standard" setup for link prediction task in graph machine learning suffers from a sampling degree bias. This bias, as shown, disproportionately affects nodes with high degrees, making node degree a dominant factor in determining link presence, irrespective of actual structural features. The authors validate their claims through empirical evaluation of a wide range of datasets and some theoretical analysis on networks with a log-normal degree distribution. They show that a naive method that just considers the degree of nodes to make a prediction performs really well in the old setup and incrementally proposes a modification to the existing setup to counter this sampling bias.
weaknesses: Let me preface by appreciating the thorough limitations discussed in the Discussion section. Although they are acknowledged and defended to some extent, I still feel that some of the explanations are not convincing enough, and hence, you might find me mentioning a couple of them down below.

W1. The authors overgeneralize the impact of their proposed benchmark. While the described setup was the most followed one, in recent times, other works tend to adopt different sampling schemes and experimental setups [3] [4]. While this work touches on an important issue with the legacy benchmarks, I wonder how relevant they are currently.

W2. Despite highlighting degree bias, the paper fails to thoroughly compare with recent works that address similar benchmarking biases. Relevant works, such as those by [1] [2], which tackle degree-related bias, are absent. This lack of engagement with the broader literature makes the contribution feel isolated rather than a comprehensive advancement in benchmark design.

W3. Hyperparameter tuning for GNNs is missing, which is paramount while benchmarking multiple methods. While the authors mention standard settings, there is no indication that they optimized parameters for the degree-corrected benchmark. I find the results brittle as it is common knowledge that most of the GNN-based methods are very sensitive to the hyperparameters, which, when properly tuned, could result in a completely different set of results. Another weakness on the same line of reasoning is that while the authors test on 96 graphs, most of their discussions are centered around the insights from artificial datasets, rendering the depth of the dataset choices valuable only to some extent.

W4. The choice of only four GNNs among 26 total methods seems outdated, as classical link prediction methods are now less commonly used. Incorporating a more diverse set of GNN models would better reflect the benchmark’s utility in current graph machine learning applications. Graph Transformers and their variants, which are often the most commonly used ones in practice now, are completely missing from the evaluations.

[1] Mayra Russo, Sammy Fabian Sawischa, and Maria-Esther Vidal. 2024. Tracing the Impact of Bias in Link Prediction. In Proceedings of the 39th ACM/SIGAPP Symposium on Applied Computing (SAC '24).

[2] Y. Wang and T. Derr, "Degree-Related Bias in Link Prediction," 2022 IEEE International Conference on Data Mining Workshops (ICDMW)

[3] Wang, Y., Hu, X., Gan, Q., Huang, X., Qiu, X., & Wipf, D. (2024). Efficient Link Prediction via GNN Layers Induced by Negative Sampling. IEEE Transactions on Knowledge and Data Engineering.

[4] Nguyen, Trung-Kien, and Yuan Fang. "Diffusion-based Negative Sampling on Graphs for Link Prediction." Proceedings of the ACM on Web Conference 2024.

---

confidence: 5
contribution: 2
initial_rating: 5
presentation: 3
questions: Xie He et a. [1] showed that one must consider the data collection process and application domain for link prediction. Are you suggesting that the degree-corrected sampling benchmark should be used for all graphs regardless of the application domain or the data collection process?

[1] Xie He et al. (2024). Link prediction accuracy on real-world networks under non-uniform missing-edge patterns. PLoS One, 18;19(7):e0306883. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0306883
soundness: 3
strengths: The paper talks about an important problem and is well-written. The proposed solution is reasonable for graphs with no attributes.
summary: Real-world graphs are sparse and have a heavy-tailed degree distribution. Thus, when measuring performance on link prediction, one should not randomly sample a bunch of edges (positive examples) and non-edges (negative examples). The paper presents a degree-corrected link prediction benchmark, where the non-edge samples have the same degree bias as edges.  The paper shows how the degree-corrected sampling learns better community structure.
weaknesses: The problem highlighted is well-known. For example, here are two recent works:

[1] Xie He et al. (2024). Link prediction accuracy on real-world networks under non-uniform missing-edge patterns. PLoS One, 18;19(7):e0306883. https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0306883

[2] Ayan Chatterjee et al. (2023). Improving the generalizability of protein-ligand binding predictions with AI-Bind. Nature Communications, 14, Article number: 1989. https://doi.org/10.1038/s41467-023-37572-z

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. Any intuition on how the degree-corrected benchmark would perform on directed or weighted graphs?
2. Elaborating on how the degree-corrected benchmark might be integrated into existing graph machine learning frameworks and evaluation pipelines would benefit the paper.
soundness: 3
strengths: 1. The paper is well-structured and clearly articulates the problem, proposed solution, and implications.
2. The figures and their captions do very well to illustrate the problem and approach
3. The findings have broad implications for graph machine learning, and could potentially influence future benchmark designs and model evaluations.
summary: This paper critically examines the standard link prediction benchmark in graph machine learning, revealing an inherent degree bias that favors methods overly dependent on node degree. The authors propose a degree-corrected link prediction task to address this bias, demonstrating its improved alignment with real-world recommendation tasks and its ability to train graph machine learning models more effectively.
weaknesses: 1. The paper focuses primarily on undirected, unweighted graphs. It's unclear how the findings generalize to other graph types (e.g., directed, weighted). (see Q1)
2. The practical implications for existing graph machine learning models and their reported performances are not extensively discussed.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: (1) Section 3.2 provides a vague and unclear intuition about recommendation tasks. I strongly recommend revising this section, possibly incorporating some of the information already included in the appendix. Specifically, authors should include a clear definition of the recommendation task objective, metrics used for evaluation, and an explanation of why alignment between link prediction and recommendation is important. For instance, I wonder why not directly using link recommendation instead of a new link prediction benchmark if already the first one is less biased?   
Additionally, as a minor comment, the results presented in Figure 2B are not easy to interpret. In particular, I do not understand why using a different color for grey and orange distributions and which part of the graph highlights the alignment with recommendation tasks. Improving the clarity with a more detailed caption and/or adding labels to the picture is important for understanding the results more deeply. Moreover, the figure should be clearly referenced in the corresponding paragraph where it is discussed.

(2) Section 3.3 demonstrates notable improvements in community learning when degree-corrected sampling is applied during GNN training, suggesting that node degree overfitting is the primary factor in performance loss for community detection. However, other factors may also contribute to this improvement. For example, as mentioned in the final discussion, correcting for degree bias also reduces distance bias, making link prediction more challenging by removing easily distinguishable negative examples and thereby promoting more robust structure learning. Authors should explore more in depth this possibility, proving evidence that reduction in node degree overfitting, beyond the elimination of other possible biases, is the main reason for enhanced community learning. At this purpose, adding in Figure 3 the results with a "distance-unbiased" benchmark can be an important comparison, or alternatively, explaining why the use of the degree-corrected benchmark should be preferred to reduce distance bias (e.g., computationally faster?).

(3) Related to the previous question, Section 3.3 mentions that GNNs are trained using either the original and degree-corrected link prediction benchmarks and tested on community detection. Have you also evaluated how link prediction performance is affected —across both the standard and degree-corrected benchmarks— when training is conducted without the bias?

(4) Figures 3B and 3D show an overall improvement in learning community structure when using the degree-corrected benchmark. However, the performance gain with GAT appears minimal. Do you have any insights or hypotheses as to why this might be the case?

(5) Given that in the degree-corrected benchmark, negative sampling follows the same degree bias as positive edges, can you provide any theoretical guarantee, empirical evidence, or link to other works, showing that the pairs involving low-degree nodes (mostly neglected during sampling) have a minor impact on prediction accuracy?
soundness: 3
strengths: The paper provides a detailed analysis of the standard benchmark for link prediction, revealing a bias in positive edge sampling that can lead to misleading experimental outcomes. The proposed solution is very straightforward, not very original, but effective across the experiments. While the exploration of biases in link prediction is not a new concept, the paper's contribution to improving current benchmarks for more reliable and fair results represents a valuable advancement. The clarity of the paper is generally good, particularly in the introductory sections, while there is room for improvement in the description of experiments. I have also appreciated the theoretical analyses and the amount of supplementary results reported, which ensure the overall quality of the work.
summary: The paper illustrates the presence of an implicit bias toward high-degree nodes in the usual link prediction benchmark for graphs, potentially favoring prediction methods based on node degree (e.g. preferential attachment).

Then, authors propose a straightforward yet effective idea to address this issue by sampling negative edges with the same biased distribution as positive ones. This novel benchmark is shown to align better with link recommendation tasks. Moreover, the degree-corrected benchmark allows for training unsupervised GNN models that better capture graph structure.
weaknesses: I have noticed two main weaknesses. First, aspects of the exposition lack clarity. Specifically, in Section 3.2, where authors explore the alignment with recommendation tasks, the task description is somewhat vague, and the section would benefit from a substantial revision to improve coherence and integration with the rest of the paper. Second, the impact of biased negative sampling during GNN training seems underexplored in the experiments. In fact, Section 3.3 demonstrates a positive effect when graph models are trained with bias-corrected sampling, suggesting that improved community learning is due to the reduced overfitting to node degrees. However, other factors could also contribute to this improvement. To clarify the sources of enhancement in community detection with degree-corrected sampling, authors should include additional experiments or more detailed discussions. I elaborate further on these issues and other minor concerns in the question box below.

Meta-review: This paper discusses an important problem of how link prediction evaluation is defined in the context of graph representation learning research.  The authors note that common methods for evaluating link prediction settings are flawed because the asymmetry between degree-biased positive sampling and random negative sampling biases towards high degree nodes, which results in a skewed evaluation which favors methods which rely on node degree.  The authors propose a degree-corrected benchmark in response.

This paper was evaluated as borderline, and unfortunately leaned towards rejection over the course of discussion.  The paper is also fortunate to have several diligent reviewers who gave very detailed feedback and engaged with the authors throughout the period.  There were a few key issues which were raised during the rebuttal and discussion period:

- The authors' focus on degree bias is a good one, but not a new one.  Several prior works have mentioned similar challenges as discussed with multiple reviewers (hFyf, CfDu), and the authors also missed a very relevant graph link prediction benchmark from NeurIPS'23 at the time of submission, as well as another paper from ICDM'20 which hindered the positioning of this work and made the value-add less clear.

- Some reviewers still lack clarity on exactly what the ideal unbiased distribution of pairs of a link prediction benchmark should have is, despite multiple iterations of reading and reviewing this paper (hFyf)

- Several reviewers raised questions around the applicability and relevance of the benchmark to other types of bias (hFyf, CfDu), which may be influenced as the degree is corrected.

I encourage the authors to fold this feedback into the revision.  In particular, the better clarity around positioning of this work wrt existing graph benchmarks focusing on this topic as well as the previous citations would be important for a fresh reader of the paper.

Decision: Reject