Network link prediction based on direct optimization of area under curve

摘要

With the rapid development of the Internet, high-dimensional, sparse, and redundant data often appear in complex networks. These data require 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 a direct optimization of the AUC (area under the curve). In the proposed algorithm, the AUC is treated as the objective function for optimization, and link prediction is transformed into a binary classification problem, where the class label of each node pair is determined by whether there exists a direct link between them. The binary classification problem can then 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 that are chosen from different domains and are diverse in structure and relationship type. The empirical results show that our algorithm can achieve higher quality prediction results than those of other algorithms.