# ALPINE: Active Link Prediction Using Network Embedding
## 4 Query Strategies for ALPINE
### Variance Reduction
#### 4.3.2 Parameter Variance Reduction with D-Optimality  
D-optimality stands for the determinant optimality, with which we want to minimize the estimator variance, or equivalently maximize the determinant of the Fisher information, through querying the labels of the candidate node pairs [15; 32]. The estimated parameter in CNE is the embedding \(\mathbf{X}\). The utility of each candidate node pair \(\{i,j\}\) is determined by the estimated variance _reduction_ it causes on the estimator--in particular the embeddings of both nodes \(i\) and \(j\). As those estimated variances are lower bounded by the inverse of their Fisher information, the **d-opt.** strategy seeks to minimize the bounds by maximizing the Fisher information.  
Intuitively, the determinant of the Fisher information measures the curvature of the likelihood with respect to the estimator. A large curvature means a small variance as \(\text{Var}(\mathbf{x}_{i})\succeq\mathcal{I}(\mathbf{x}_{i})^{-1}\), corresponding to a large value of D-optimality. The smaller the bound of the parameter variance, or equivalently the more information, the more stable the embedding, and thus, the more accurate the link predictions. This motivates the **d-opt.** strategy.  
The estimated information increase of knowing a candidate link status, which we also called the informativeness of that link status, can thus be quantified by the changes in the determinants of the Fisher information matrices of the embeddings of both nodes. Querying the link status of node pair \(\{i,j\}\in P\) will reduce the variance matrix bounds \(\mathcal{I}(\mathbf{x}_{i}^{*})^{-1}\) and \(\mathcal{I}(\mathbf{x}_{j}^{*})^{-1}\), as it creates additional information on their optimal values. For \(\mathbf{x}_{i}^{*}\), its new Fisher information assuming \(\{i,j\}\in P\) has a known status, is denoted as \(\mathcal{I}^{j}(\mathbf{x}_{i}^{*})\) in Equation (5), and similarly for \(\mathbf{x}_{j}^{*}\) leading to \(\mathcal{I}^{i}(\mathbf{x}_{j}^{*})\). Using Equation (4), it is easy to see that \(\mathcal{I}^{j}(\mathbf{x}_{i}^{*})\) can be calculated as an additive update to \(\mathcal{I}(\mathbf{x}_{i}^{*})\):  
\[\mathcal{I}^{j}(\mathbf{x}_{i}^{*})=\mathcal{I}(\mathbf{x}_{i}^{*})+\gamma^{2}P_{ij}^{ *}(1-P_{ij}^{*})(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*})(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*}) ^{\top}. \tag{5}\]  
That estimated information increase is caused by the difference of determinants between the old and the new Fisher information of \(\mathbf{x}_{i}^{*}\) (and similarly for \(\mathbf{x}_{j}^{*}\)), shown in Equation (6). As it is a rank one update in Equation (5), we can apply the matrix determinant lemma [38] and write this amount of information change as in Equation (7):  
\[u_{\mathbf{x}_{i}^{*}}(i,j) =\det\Bigl{[}\mathcal{I}^{j}(\mathbf{x}_{i}^{*})\Bigr{]}-\det[ \mathcal{I}(\mathbf{x}_{i}^{*})], \tag{6}\] \[=\gamma^{2}P_{ij}^{*}(1-P_{ij}^{*})(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*} )^{\top}\mathcal{I}(\mathbf{x}_{i}^{*})^{-1}(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*})\det[ \mathcal{I}(\mathbf{x}_{i}^{*})]. \tag{7}\]  
Combining the information change from both nodes, the utility function of **d-opt.** for a node pair \(\{i,j\}\in P\) is formally defined as:  
\[u_{\mathbf{A},\mathbf{X}^{*}}(i,j) =u_{\mathbf{x}_{i}^{*}}(i,j)+u_{\mathbf{x}_{j}^{*}}(i,j). \tag{8}\]  
Finally, using Equation (7), the estimated information increase caused by knowing the status of \(\{i,j\}\in P\) proves to be always positive and equal to:  
\[u_{\mathbf{A},\mathbf{X}^{*}}(i,j)=\] \[\gamma^{2}P_{ij}^{*}(1-P_{ij}^{*})(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*} )^{\top}\Bigl{[}\det[\mathcal{I}(\mathbf{x}_{i}^{*})]\mathcal{I}(\mathbf{x}_{i}^{*})^ {-1}+\det\Bigl{[}\mathcal{I}(\mathbf{x}_{j}^{*})\Bigr{]}\mathcal{I}(\mathbf{x}_{j}^{*} )^{-1}\Bigr{]}(\mathbf{x}_{i}^{*}-\mathbf{x}_{j}^{*}).\]