直接优化AUC进行网络链接预测

Network Link Prediction Based on Direct Optimization of AUC

快速扩展的互联网形成了具有高维、稀疏和冗余特性的复杂网络.因此需要有效的技术从这些复杂网络数据中提取出最为重要的信息进行链接预测,以便为用户服务.本文提出一种基于AUC(Area under Curve)优化的链接预测算法.在该算法中,将AUC作为优化的目标函数,将链接预测问题转化为二分分类问题.将顶点之间是否存在链接作为它所在的类的标号.通过优化AUC来进行二分分类,使用铰链函数按随机次梯度下降算法迭代更新权重矩阵.最后在一些来自不同领域的真实网络上对本算法进行了测试.实验结果表明,本算法与其他算法的结果相比可以实现更高质量的预测.

With the fast development of the Internet, high-dimensional, sparse and redundant data appear in the complex networks. It requires effective link prediction techniques to extract the most basic and relevant information for online user services. In this paper, we propose a link prediction algorithm based on direct optimization of AUC （ Area under Curve ）. In the algorithm, AUC is treated as the objective function of optimization, and link prediction is transformed as a problem of binary classification, where class label of each node pair is determined by whether there exists a direct link between them. Then the binary classification problem can be solved by AUC optimization. We use the hinge function as the loss function, and iteratively update the weight matrix based on the stochastic gradient sub-descent method. We test our method on several real-world heterogeneous information networks, which are chosen from different domains and have diversity in structure and relationship types. The empirical results show that our algorithm can achieve higher quality prediction compared with the results of other algorithms.