摘要：

随着信息技术的飞速发展, 链路预测技术已经在多个领域得到了广泛的应用。目前的链路预测方法通常采用子图提取的方式, 其中一种基于线图转换(LGT)与图卷积神经网络(GCN)的模型在链路预测问题上取得了优异的效果, 但仍存在2个问题: 1)LGT的时间复杂度过高和转换后子图的规模过大导致其难以被广泛应用; 2)GCN忽略了节点间的高阶关系和局部聚类结构, 会对预测精度产生一定的影响。为解决上述问题, 提出一种基于超图卷积神经网络(HGCN)的链路预测方法HGLP。该方法使用对偶超图转换(DHT)替代LGT以做到在不损失任何结构信息的情况下提高系统的运行效率, 同时运用HGCN分别学习超图中超节点与超边的高阶特征以实现更高的预测精度。实验结果表明, 在曲线下面积(AUC)和平均准确率(AP)2个指标下, 所提出的方法在7种不同领域的真实图数据集中的表现不仅优于现有的链路预测方法, 而且内存占用更少、运行时间更短。

关键词: 链路预测, 超图, 超图神经网络, 对偶超图转换, 深度学习

Abstract:

With the rapid development of information technology, link prediction has been widely applied in various fields. Current link prediction methods are based on subgraph extraction. Models based on Line Graph Transformation (LGT) and Graph Convolutional Network (GCN) achieve excellent results in link prediction. However, two problems remain: 1) the high time complexity of the LGT and the large size of the line graph hinder its wide-spread application; 2) GCN ignores the high-order relationship and local clustering structure between nodes, thereby affecting prediction accuracy. To solve the above issues, this paper proposes a link prediction method based on Hypergraph Convolutional Network (HGCN), called HGLP. This method replaces LGT with Dual Hypergraph Transformation (DHT) to improve system efficiency without losing structural information and applies HGCN to learn the higher-order features of the hypernodes and hyperedges in the hypergraph to obtain higher prediction accuracy. Experimental results show that the proposed method outperforms state-of-the-art link prediction methods on seven real-world datasets from different domains, in terms of Area Under the Curve (AUC) and Average Precision (AP). Furthermore, the proposed method achieves shorter runtimes and less memory usage.

Key words: link prediction, hypergraph, Hypergraph Convolutional Network (HGCN), Dual Hypergraph Transformation (DHT), deep learning