# ALPINE: Active Link Prediction Using Network Embedding
## 1 Introduction
_Partially observed networks_: To solve this problem, a distinction should be made between node pairs that are known to be unlinked and node pairs for which the link status is not known. In other words, the network should be represented as a partially observed network, with three node pair statuses: linked, unlinked, and unknown. The node pairs with unknown status are then the candidates for querying, and if the result of a query indicates that they are not linked, actual information is added. This contrasts with much of the state-of-the-art in network embedding research, where unlinked and unknown statuses are not distinguished. Thus, the active learning strategies proposed will need to build on a network embedding method that naturally handles partially observed networks. Given such a method, we then need an active learning query strategy for identifying the unknown candidate link statuses with the highest utility. After querying the oracle for the label of the selected link status, we can use it as additional information to retrain the network embedding model. In this way, more and more informative links and non-links become available for training the model, maximally improving the model's link prediction ability with a limited number of queries. _The ALPINE framework_: We proposed the ALPINE (Active Link Prediction usIng Network Embedding) framework, the first method using active learning for link prediction based on network embedding, and developed different query strategies for ALPINE to quantify the utilities of the candidates. Our proposed query strategies included simple heuristics, as well as principled approaches inspired by the active learning and experimental design literature. ALPINE was based on a network embedding model called Conditional Network Embedding (CNE) [10], whose objective function is expressed analytically. There are two reasons why we chose to build our work on CNE. The first is that, as we will show, CNE can be easily adapted to work for partially observed networks, as opposed to other popular network embedding methods (including those based on random walks). The second reason is that CNE is an analytical approach (not relying on random walks or sampling strategies), and thus allowed us to derive mathematically principled active learning query strategies. Yet, we note that ALPINE can be applied also to other existing or future network embedding methods with these properties. _Illustrative example_: To illustrate the idea of ALPINE, we give an example on the [PERSON] network [11]. The network originally had 65 nodes and 223 _ally_ links, but we only took its largest connected component of 59 characters and 218 connections. Note that enemy relation was not considered. We assumed that the network was partially observed: the links and non-links for all characters except \"[PERSON]\" (the cyan star) were assumed to be fully known, and for [PERSON], only his relationship with \"[PERSON]\" (the green plus) was observed as linked and with \"[PERSON]\" (the red x) as unlinked. The goal was to predict the status of the unobserved node pairs, i.e., whether the other nodes (the circles) were allies of \"[PERSON]\". Suppose we have a budget to query five unobserved relationships. We thus want to select the five most informative ones. ALPINE can quantify the informativeness of the unknown link statuses, using different query strategies. Shown in Table 1 are the top five queries selected by strategies **max-deg. **, **max-prob. **, and **max-ent. **, which are defined in Section 4. Nodes mentioned in the table are highlighted with character names in Figure 1. Strategy **max-deg. ** suggests to query the relationships among [PERSON] and the high-degree nodes--those who are known to have many allies. Strategy **max-prob. ** selects nodes that are highly likely to be [PERSON]'s friends based on the observed part of the network. Finally, **max-ent. ** proposes to query the most uncertain relationships.