  Link prediction, as a fundamental task for graph neural networks (GNNs), has
boasted significant progress in varied domains. Its success is typically
influenced by the expressive power of node representation, but recent
developments reveal the inferior performance of low-degree nodes owing to their
sparse neighbor connections, known as the degree-based long-tailed problem.
Will the degree-based long-tailed distribution similarly constrain the efficacy
of GNNs on link prediction? Unexpectedly, our study reveals that only a mild
correlation exists between node degree and predictive accuracy, and more
importantly, the number of common neighbors between node pairs exhibits a
strong correlation with accuracy. Considering node pairs with less common
neighbors, i.e., tail node pairs, make up a substantial fraction of the dataset
but achieve worse performance, we propose that link prediction also faces the
long-tailed problem. Therefore, link prediction of GNNs is greatly hindered by
the tail node pairs. After knowing the weakness of link prediction, a natural
question is how can we eliminate the negative effects of the skewed long-tailed
distribution on common neighbors so as to improve the performance of link
prediction? Towards this end, we introduce our long-tailed framework (LTLP),
which is designed to enhance the performance of tail node pairs on link
prediction by increasing common neighbors. Two key modules in LTLP respectively
supplement high-quality edges for tail node pairs and enforce representational
alignment between head and tail node pairs within the same category, thereby
improving the performance of tail node pairs.
