# ALPINE: Active Link Prediction Using Network Embedding
## 2 Background
### Related Work  
Our work sits at the intersection of three topics: active learning, network embedding, and link prediction. There exists work on the combinations of any two, but not all three of them. Most prominently, link prediction is a commonly considered downstream task of network embedding [1], but active learning has not been studied in this context. Research on active network embedding has focused on node classification [13; 21; 22], but link prediction was not considered as a downstream task in this literature. Finally, active learning for link prediction is not new either [6; 7; 9], but so far, it has been studied in combination with more classical techniques than network embedding. Thus, to the best of our knowledge, the present paper is the first one studying the use of active learning for network embedding with link prediction as a downstream task. Given the promise network embedding methods have shown for link prediction, we believe this is an important gap to be filled. Work on active learning for graph-based problems has focused on node and graph classification, as well as on various tasks at the link level [14; 23]. The graph classification task considers data samples as graph objects, useful, e.g., for drug discovery and subgraph mining [24], while the node classification aims to label nodes in graphs [25; 26; 27; 28]. Active learning has also been used for predicting the sign (positive or negative) of edges in signed networks, where some of the edge labels are queried [6]. Similarly, given a graph, [PERSON] et al. [8] studied how edge flows can be predicted by actively querying a subset of the edge flow information, to help with sensor placement in water supply networks. All these methods are only laterally relevant to the present paper, in that their focus is not on link prediction. The methods most strongly related to our work are ActiveLink [7] and HALLP [9]. ActiveLink is designed for link prediction in knowledge graphs and has as its aim to speed up the training of the deep neural link predictors by actively selecting the training data [7]. More specifically, the method selects samples from the _multitriples_ constructed according to the training triples. As link prediction in a knowledge graph with only one relation (one predicate) is equivalent with link prediction in a standard graph as considered in this paper, ActiveLink appears to be a meaningful baseline for our paper. However, when applied to a standard graph in this way, ActiveLink would work by querying _all_ node pairs involving a set of selected nodes (or, in terms of the adjacency matrix, it would query entire rows or columns). Thus, this strategy would learn the entire neighborhood of the selected nodes, but very little about the rest of the network. While this strategy may be sensible in the case of a knowledge graph where information about one relation may also be informative about other relations, it is clearly not useful for standard graphs. This excludes ActiveLink as a reasonable baseline. HALLP, on the other hand, proposes an active learning method for link prediction in _standard_ networks [9], demonstrating a benefit over passive learning. However, both HALLP's link prediction method (based on a support vector machine [29]) and its active learning query strategy utilize a pre-determined set of features rather than a learned model such as a network embedding. The query strategy attempts to select node pairs for which the link prediction is most uncertain. Specifically, HALLP considers two link prediction models for calculating these uncertainties for the candidate node pairs, defining the utility of a candidate node pair as follows:  
\[u_{A}(i,j)=c_{1}u_{local}(i,j)+c_{2}u_{global}(i,j). \tag{2}\]  
Here, \(u_{local}(i,j)\) is the so-called local utility that measures the uncertainty of a linear SVM link prediction model, \(u_{global}(i,j)\) is the so-called global utility based on the hierarchical random graph link predictor [30], and \(c_{1}\) and \(c_{2}\) are two coefficients.