  Many real-world problems can be formalized as predicting links in a partially
observed network. Examples include Facebook friendship suggestions,
consumer-product recommendations, and the identification of hidden interactions
between actors in a crime network. Several link prediction algorithms, notably
those recently introduced using network embedding, are capable of doing this by
just relying on the observed part of the network. Often, the link status of a
node pair can be queried, which can be used as additional information by the
link prediction algorithm. Unfortunately, such queries can be expensive or
time-consuming, mandating the careful consideration of which node pairs to
query. In this paper we estimate the improvement in link prediction accuracy
after querying any particular node pair, to use in an active learning setup.
Specifically, we propose ALPINE (Active Link Prediction usIng Network
Embedding), the first method to achieve this for link prediction based on
network embedding. To this end, we generalized the notion of V-optimality from
experimental design to this setting, as well as more basic active learning
heuristics originally developed in standard classification settings. Empirical
results on real data show that ALPINE is scalable, and boosts link prediction
accuracy with far fewer queries.
