Given an edge-incomplete graph, how can we accurately find the missing links?
The link prediction in edge-incomplete graphs aims to discover the missing
relations between entities when their relationships are represented as a graph.
Edge-incomplete graphs are prevalent in real-world due to practical
limitations, such as not checking all users when adding friends in a social
network. Addressing the problem is crucial for various tasks, including
recommending friends in social networks and finding references in citation
networks. However, previous approaches rely heavily on the given
edge-incomplete (observed) graph, making it challenging to consider the missing
(unobserved) links during training. In this paper, we propose PULL
(PU-Learning-based Link predictor), an accurate link prediction method based on
the positive-unlabeled (PU) learning. PULL treats the observed edges in the
training graph as positive examples, and the unconnected node pairs as
unlabeled ones. PULL effectively prevents the link predictor from overfitting
to the observed graph by proposing latent variables for every edge, and
leveraging the expected graph structure with respect to the variables.
Extensive experiments on five real-world datasets show that PULL consistently
outperforms the baselines for predicting links in edge-incomplete graphs.

提出了一种基于正无标号（PU）学习的准确链接预测方法 PULL（PU-Learning-based Link predictor），它通过为每个边引入潜在变量并利用相对于这些变量的预期图结构，有效地防止链接预测器过度拟合观察到的图，在边不完整的图中预测链接的性能优于基线模型。