Handling Class Imbalance in Link Prediction using Learning to Rank
  Techniques
  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.
