  Inferring missing links or detecting spurious ones based on observed graphs,
known as link prediction, is a long-standing challenge in graph data analysis.
With the recent advances in deep learning, graph neural networks have been used
for link prediction and have achieved state-of-the-art performance.
Nevertheless, existing methods developed for this purpose are typically
discriminative, computing features of local subgraphs around two neighboring
nodes and predicting potential links between them from the perspective of
subgraph classification. In this formalism, the selection of enclosing
subgraphs and heuristic structural features for subgraph classification
significantly affects the performance of the methods. To overcome this
limitation, this paper proposes a novel and radically different link prediction
algorithm based on the network reconstruction theory, called GraphLP. Instead
of sampling positive and negative links and heuristically computing the
features of their enclosing subgraphs, GraphLP utilizes the feature learning
ability of deep-learning models to automatically extract the structural
patterns of graphs for link prediction under the assumption that real-world
graphs are not locally isolated. Moreover, GraphLP explores high-order
connectivity patterns to utilize the hierarchical organizational structures of
graphs for link prediction. Our experimental results on all common benchmark
datasets from different applications demonstrate that the proposed method
consistently outperforms other state-of-the-art methods. Unlike the
discriminative neural network models used for link prediction, GraphLP is
generative, which provides a new paradigm for neural-network-based link
prediction.
