  Link prediction is a crucial problem in graph-structured data. Due to the
recent success of graph neural networks (GNNs), a variety of GNN-based models
were proposed to tackle the link prediction task. Specifically, GNNs leverage
the message passing paradigm to obtain node representation, which relies on
link connectivity. However, in a link prediction task, links in the training
set are always present while ones in the testing set are not yet formed,
resulting in a discrepancy of the connectivity pattern and bias of the learned
representation. It leads to a problem of dataset shift which degrades the model
performance. In this paper, we first identify the dataset shift problem in the
link prediction task and provide theoretical analyses on how existing link
prediction methods are vulnerable to it. We then propose FakeEdge, a
model-agnostic technique, to address the problem by mitigating the graph
topological gap between training and testing sets. Extensive experiments
demonstrate the applicability and superiority of FakeEdge on multiple datasets
across various domains.
