  In this work, we propose a novel link prediction model and further boost it
by studying graph incompleteness. First, we introduce MPNN-then-SF, an
innovative architecture leveraging structural feature (SF) to guide MPNN's
representation pooling, with its implementation, namely Neural Common Neighbor
(NCN). NCN exhibits superior expressiveness and scalability compared with
existing models, which can be classified into two categories: SF-then-MPNN,
augmenting MPNN's input with SF, and SF-and-MPNN, decoupling SF and MPNN.
Second, we investigate the impact of graph incompleteness -- the phenomenon
that some links are unobserved in the input graph -- on SF, like the common
neighbor. Through dataset visualization, we observe that incompleteness reduces
common neighbors and induces distribution shifts, significantly affecting model
performance. To address this issue, we propose to use a link prediction model
to complete the common neighbor structure. Combining this method with NCN, we
propose Neural Common Neighbor with Completion (NCNC). NCN and NCNC outperform
recent strong baselines by large margins, and NCNC further surpasses
state-of-the-art models in standard link prediction benchmarks. Our code is
available at https://github.com/GraphPKU/NeuralCommonNeighbor.
