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.
翻译:根据观察到的图表(称为链接预测)推断缺失的链接或探测虚假的链接,是图表数据分析的一个长期挑战。随着最近深层学习的进展,图形神经网络被用于连接预测,并取得了最新业绩。然而,为此目的开发的现有方法通常是有区别的,即围绕两个相邻节点计算地方子图特征,并从子图分类的角度预测它们之间的潜在联系。在这种形式主义中,为子图分类选择包含子图和超强结构特征,严重影响了方法的性能。为了克服这一局限性,本文提议根据网络重建理论(称为GreagLP),采用一种全新的和完全不同的联系预测算法。而不用抽样抽样正负联系,并用超自然理论计算其附下的子图特征,而利用深层学习模型的特征能力自动提取图表的结构模式,以便在假设基于真实世界的图表并非本地孤立的情况下进行联系。此外,GreamLP在高端模型连接模式上探索高端连接模式,以便利用网络重建理论结构结构结构结构结构结构结构结构,而用所有通用的直径直图进行对比。