超图环境下链路预测问题的探究  

Exploration of Link Prediction Via Hypergraph

作　　者：佘美富 王逸伟 张建章 詹秀秀 刘闯[1] SHE Meifu;WANG Yiwei;ZHANG Jianzhang;ZHAN Xiuxiu;LIU Chuang(Alibaba Research Center for Complexity Sciences,Hangzhou Normal University,Hangzhou 311121,China;Data Space Research Institute of Hefei Comprehensive National Science Center,Hefei 230088,China)

机构地区：[1]杭州师范大学阿里巴巴复杂科学研究中心,杭州311121 [2]合肥综合性国家科学中心数据空间研究院,合肥230088

出　　处：《西南大学学报（自然科学版）》2023年第8期61-75,共15页Journal of Southwest University(Natural Science Edition)

基　　金：浙江省自然科学基金项目(LQ22F030008).

摘　　要：超图作为图的扩展,可以表示多种实体间的关系,使得其表达能力大大强于图,该优势吸引人们的关注并日益成为研究热点.链路预测作为图数据挖掘中的常见任务,也在超图上扩展为超链路预测.超链路预测通过已知超边或节点的属性来估计新超边出现的可能性,但是由于超边内节点数量的任意性,其可能的超边由O(n^(2))暴增至O(2^(n)),这大大增加了算法的复杂度.本文使用下采样方法以减少候选超边集的大小,将图上的带重启的随机游走算法扩展到超图上.还将图上的其他指标,如CN、CE、Jaccard等,扩展到超图进行比较.结果表明,带重启的随机游走指标在精确率和召回率上要明显优于其他指标,并且观察到演化良好的超图其超边内部的联系强度随节点数的增加而增加,由此可知超链路预测的主要难点在于对小尺寸超边的预测.As an extension of graphs,hypergraphs can represent relationships between multiple entities,making their expressive power much stronger than that of graphs,which has attracted attention and become a research hotspot.Link prediction,a common task in graph data mining,has also been extended as hyperlink prediction on hypergraphs.Hyperlink prediction estimates the likelihood of new hyperedges appearing based on known attributes of hyperedges or nodes,but due to the arbitrary number of nodes in hyperedges,the possible hyperedges can exponentially increase from O(n^(2))to O(2^(n)),greatly increasing the complexity of the algorithm.In this paper,we use a down-sampling method to reduce the size of the candidate hyperedge set and extend the graph s random walk with restart algorithm to hypergraphs.In addition,we extend other metrics on the graph,such as CN,CE,and Jaccard index,to hypergraphs.The results show that the metric is significantly better than other metrics in precision and recall,and we observe that the internal connectivity of hyperedges in well-evolved hypergraphs increases with the number of nodes,indicating that the main difficulty in hyperlinks prediction lies in predicting small hyperedges.

关 键 词：超图 链路预测 超链路预测 带重启的随机游走 有限集合 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O158[自动化与计算机技术—计算机科学与技术]