Handling Class Imbalance in Link Prediction using Learning to Rank Techniques
This addresses the class imbalance issue in link prediction for network analysis, offering a scalable method that integrates topology and features, though it is incremental as it adapts existing ranking techniques.
The paper tackles link prediction in networks by recasting it as a learning-to-rank problem to handle class imbalance, using techniques like ListNet during training, and shows improved performance on co-authorship, citation, and metabolic networks.
We consider the link prediction problem in a partially observed network, where the objective is to make predictions in the unobserved portion of the network. Many existing methods reduce link prediction to binary classification problem. However, the dominance of absent links in real world networks makes misclassification error a poor performance metric. Instead, researchers have argued for using ranking performance measures, like AUC, AP and NDCG, for evaluation. Our main contribution is to recast the link prediction problem as a learning to rank problem and use effective learning to rank techniques directly during training. This is in contrast to existing work that uses ranking measures only during evaluation. Our approach is able to deal with the class imbalance problem by using effective, scalable learning to rank techniques during training. Furthermore, our approach allows us to combine network topology and node features. As a demonstration of our general approach, we develop a link prediction method by optimizing the cross-entropy surrogate, originally used in the popular ListNet ranking algorithm. We conduct extensive experiments on publicly available co-authorship, citation and metabolic networks to demonstrate the merits of our method.