# ALPINE: Active Link Prediction Using Network Embedding
## 4 Query Strategies for ALPINE
### Variance Reduction
#### 4.3.3 Prediction Variance Reduction with V-Optimality  
V-optimality aims to select training data so as to minimize the variance of a set of predictions obtained from the learned model [15; 33; 34]. The definition naturally fits the active network embedding for link prediction problem definition, where we only care about the predictions of the target node pairs in \(T\). Therefore, the goal of the **v-opt. ** strategy is to minimize the link prediction variance for the target set \(T\). With CNE, the link prediction function \(g\) follows naturally from the model \(P_{ij}^{*}\triangleq g(\mathbf{x}_{i}^{*},\mathbf{x}_{j}^{*})=P(a_{ij}=1|\mathbf{X}^{*})\). What the V-optimality utility function quantifies is then the estimated reduction that a candidate link status in the pool can have on all the target prediction variance--\(\text{Var}(P_{ij}^{*})\) for \((i,j)\in T\). The challenge to be addressed is thus the computation of the reduction in the variance \(\text{Var}(P_{ij}^{*})\). We outline how this can be performed in two steps:  
1. First, generate the expression of the prediction variance;
2. Then, define the query strategy as the utility function that quantifies the variance reduction. The prediction variance \(\text{Var}(P_{ij}^{*})\) can be computed using the first-order analysis (details in Appendix B) and decomposed into contributions from both end nodes, as in Equation (9):  
\[\text{Var}(P_{ij}^{*}) =\text{Var}_{\mathbf{x}_{i}^{*}}(P_{ij}^{*})+\text{Var}_{\mathbf{x}_{j}^ {*}}(P_{ij}^{*})+2\text{Cov}_{\mathbf{x}_{i}^{*},\mathbf{x}_{j}^{*}}(P_{ij}^{*}). \tag{9}\]Then, the bounds on the parameter variance can be used to bound the variance on the estimated probabilities--\(\text{Var}_{\mathbf{x}_{j}^{*}}(P_{ij}^{*})\)--as in Equation (10):  
\[\text{Var}_{\mathbf{x}_{i}^{*}}(P_{ij}^{*})\geq\Big{[}\gamma P_{ij}^{*}(1-P_{ij}^{*} )\Big{]}^{2}(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*})^{T}\mathcal{I}(\mathbf{x}_{i}^{*})^{-1} (\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*}), \tag{10}\]  
and similarly for \(\text{Var}_{\mathbf{x}_{j}^{*}}(P_{ij}^{*})\). Now, we can quantify the reduction caused by knowing the link status of a candidate node pair. As discussed before, knowing the link status of a node pair \(\{i,j\}\in P\), represented by Equation (5), leads to a reduction of the bounds \(\mathcal{I}(\mathbf{x}_{i}^{*})^{-1}\) and \(\mathcal{I}(\mathbf{x}_{j}^{*})^{-1}\), thus on \(\text{Var}_{\mathbf{x}_{i}^{*}}(P_{ij}^{*})\) and \(\text{Var}_{\mathbf{x}_{j}^{*}}(P_{ij}^{*})\), and on \(\text{Var}(P_{ij}^{*})\) due to Equation (9). The last term \(\text{Cov}_{\mathbf{x}_{i}^{*}\mathbf{x}_{j}^{*}}(P_{ij}^{*})\) in Equation (9) does not result in any variance change, so it can be ignored. Putting things together allows defining the V-optimality utility function for **v-opt. ** and proves a theorem for computing it. **Definition 2**. : _The V-optimality utility function \(u_{\mathbf{A},\mathbf{X}^{*}}\) evaluated at \(\{i,j\}\in P\) quantifies the reduction in the bound on the sum of the variances \(\text{Var}(P_{kl}^{*})\) (see Equations (9) and (10)) of all \(P_{kl}^{*}\) for \(\{k,l\}\in T\), achieved by querying \(\{i,j\}\)._  
**Theorem 1**.