# ALPINE: Active Link Prediction Using Network Embedding
## 5 Experiments and Discussion
### Quantitative Evaluation of ALPINE
#### 5.3.1 Case 1: \(P=U\) and \(T=U\)  
In the first case, we had the pool of all unobserved link statuses and wanted to predict all the unknowns. Shown in Figure 4 are the results, in which each row represents a dataset with its step size and each column corresponds to one \(r_{0}\) value. For every individual subplot, the \(AUC\_U\) is the AUC score for all the initially unobserved link statuses--those not included in \(K_{0}\). The budget \(k\) was set to 10 steps, i.e., \(k=10s\), resulting in 10 iterations.  
Iteration 0 was the initial performance before the active learning, so there were always \(\frac{k}{s}+1\) scores. In other words, given the budget \(k=10s\), even for \(r_{0}=80\%\), we did not query the entire pool and reached only 90% of the network information. The AUC scores were averaged over several different random PONs, and each PON defined by a \(K_{0}\) was initialized with different random embeddings (\(10\times 10\) for the first four networks and \(5\times 5\) for the last and largest one). Each random strategy score was further averaged over three runs.  
In general, the active learning strategies outperformed the **rand.** strategy. We saw that when the observed part was relatively small--3% or 10%-- the degree-related strategies that did not depend on the embedding usually performed very well, and the random  
Figure 4: ALPINE: \(P=U\) and \(T=U\). Row 1: Polbooks (\(s=54\)); Row 2: C. elegans (\(s=439\)); Row 3: USAir (\(s=549\)); Row 4: MP_cc (\(s=1604\)); Row 5: Polblogs_cc (\(s=7460\)).  
strategy was not always the worst. As more information was observed when \(r_{0}\) increased (see the plots from the left to the right in each row), we did not only see that the active learning strategies, such as **v-opt.** and **max-ent.**, began to dominate and passive learning became the worst, but also the increase of the starting _AUC_U._ Zooming in to individual subplots, we saw that ALPINE boosted link prediction accuracy with far fewer queries for the active learning strategies, compared to passive learning. Overall, when the observed information was very limited, the embedding-independent strategies **page-rank.** and **max-deg.** outperformed the others; while for sufficiently enough information, **v-opt.** and **max-ent.** were the better choices. We speculated that this was the case as the embedding must be of sufficient quality for the embedding-dependent strategies to work, which requires a certain minimum amount of data. Worth noticing is that **d-opt.** showed similar performance across different values of \(r_{0}\), which will be discussed further in Section 5.4.  
As for the HALLP strategy, which aimed to query the most uncertain node-pairs and thus was similar in spirit to **max-ent.**, the performance was very variable. In some cases, it performed quite well, as shown in the top right subplot, beating **v-opt.** in the first few iterations, while on the MP_cc network, it was one of the worst strategies. In addition to that, the runtime of HALLP was much longer than that of the other strategies; thus, some of the subplots do not have the HALLP result. The runtime analysis for one iteration of the query process on a server with an Intel Xeon Gold CPU 3.00 GHz and 256 GB RAM is shown in Table 4 below. The results were averaged in the same way as in Figure 4 for the four values of \(r_{0}\) and then further averaged over the \(r_{0}\) values. Across different datasets, HALLP was by far the most computationally expensive strategy as it had to run two link predictors.