# ALPINE: Active Link Prediction Using Network Embedding
## 3 The ALPINE Framework
### The ALPINE Framework  
To tackle the problem of active network embedding for link prediction, we proposed ALPINE, a pool-based [14] active link prediction approach using network embedding and, to the best of our knowledge, the first method for this task. Our implementation and evaluation of ALPINE was based on CNE, but we stress that our arguments can be applied in principle to any other network embedding method of which the objective function can be expressed analytically. The framework works by finding an optimal network embedding for a given PON \(\mathcal{G}=(V,E,D)\), selecting one or a few candidate node pairs from the pool \(P\subseteq U\) with \(U=\binom{V}{2}\setminus(E\cup D)\) to query the connectivity according to a query strategy, updating the PON with the new knowledge provided by querying the oracle, and re-embedding the updated PON. The process iterates until a stopping criterion is met, e.g., the budget is exhausted or the predictions are sufficiently accurate.  
The PON can be embedded by the modified CNE, and the active learning query strategy, which evaluates the informativeness of the unlabeled node pairs, is the key to our pool-based active link prediction with network embedding. Defined by a _utility function_\(u_{\mathbf{A},\mathbf{X}}:V\times V\rightarrow\mathbb{R}\), the query strategy ranks the unobserved link statuses and selects the top ones for querying. The utility quantifies how useful knowing that link status is estimated to be for the purpose of increasing the link prediction accuracy for node pairs in \(T\). Specifically, each query strategy will select the next query for an appropriate \(u_{\mathbf{A},\mathbf{X}}\) as:  
\[\operatorname*{argmax}_{\{i,j\}\in P}\quad u_{\mathbf{A},\mathbf{X}}(i,j).\]  
In practice, not just the single best node pair (i.e., argmax) is selected at each iteration, but the \(s\) best ones, with \(s\) referred to as the step size.  
In summary, given a PON \(\mathcal{G}=(V,E,D)\), a network embedding model, a query strategy defined by its utility function \(u_{\mathbf{A},\mathbf{X}}\), a pool \(P\subseteq U\), a target set \(T\subseteq U\), a step size \(s\), and a budget \(k\) (number of link statuses in \(P\) that can be queried), ALPINE iteratively queries an oracle for the link status of \(s\) node pairs, selected as follows:  
* At iteration \(i=0\), initialize the pool as \(P_{0}=P\), and the set of node pairs with known link status as \(K_{0}=E\cup D\), and initialize \(\mathcal{G}_{0}=\mathcal{G}\) and \(\mathbf{A}_{0}=\mathbf{A}\);
* Then, repeat: 1. Compute the optimal embedding \(\mathbf{X}_{i}^{*}\) for \(\mathcal{G}_{i}\);
2. Find the set of queries \(Q_{i}\subseteq P_{i}\) of size \(|Q_{i}|=\min(s,k)\) with the largest utilities according to \(u_{\mathbf{A}_{i},\mathbf{X}_{i}^{*}}\) (and \(T\));
3. Query the oracle for the link statuses of node pairs in \(Q_{i}\), set \(P_{i+1}\gets P_{i}\setminus Q_{i}\), and set \(\mathcal{G}_{i+1}\) equal to \(\mathcal{G}_{i}\) with node pairs \(\{i,j\}\in Q_{i}\) added to the set of known linked or unlinked node pairs (depending on the query result), then set \(\mathbf{A}_{i+1}\) accordingly;Set \(k\gets k-|Q_{i}|\), and break if \(k\) is zero.  
In this formulation, ALPINE stops when the budget is used up. An optional criterion is surpassing a pre-defined accuracy threshold on \(T\).