# ALPINE: Active Link Prediction Using Network Embedding
## 5 Experiments and Discussion
### The Benefit of Partial Network Embedding  
An important hypothesis underlying this work is that distinguishing an \"observed unlinked\" status of a node pair from an \"unknown/unobserved\" status, as opposed to treating both as absent, which is commonly performed, will enhance the performance of network embedding. We now empirically investigated this hypothesis by comparing CNE with its variant that performs partial network embedding: (1) the original CNE defined by its objective function in Equation (1), which does not make this distinction, and (2) the modified version that optimizes Equation (3), which we called CNE_K (i.e., CNE for the Knowns), which does make the distinction. Specifically, we compared the model fitting time and the link prediction accuracy for both:  
1. CNE: fit the entire network where the unobserved link status is treated as unlinked;
2. CNE_K: fit the model only for the observed linked and unlinked node pairs.  
**Setup**: To construct a PON, we first initialized the observed information by randomly sampling a node pair set \(K_{0}=E\cup D\) that contained a proportion \(r_{0}\) of the complete information. The complete information means the total number of links in the complete graph for a given number of nodes. For example, \(r_{0}=10\%\) means that 10% of the network link statuses are observed as either linked or unlinked: if the network has \(n\) nodes, \(|K_{0}|=10\%\times\frac{n(n-1)}{2}\). The observed \(K_{0}\) is guaranteed connected as this is a common assumption for network embedding methods. Then, we embedded the same PON using both CNE and CNE_K on a machine with an Intel Core i7 CPU 4.20 GHz and 32 GB RAM.  
**Results:** From the results shown in Figure 2, we see that CNE_K was not only more time efficient, but also provided more accurate link predictions. The ratio \(r_{0}\) of observed information varied for datasets because the larger the network, the more time consuming the computations are. The time differences for a small observed part were enough to highlight the time efficiency of CNE_K. The two measures examined were: AUC_U--the prediction AUC score for all unobserved node pairs \((i,j)\in U\) containing \(1-r_{0}\) network information; and t(s)--the model fitting time in seconds. Both values are averaged--for each \(r_{0}\) averaged over 10 different PONs and each PON with 10 different embeddings (i.e., CNE has local optima) for the first four datasets--while it is \(5\times 5\) for the fifth and sixth and \(3\times 3\) for the last dataset.  
It is not surprising that the fitting time of CNE_K was almost always shorter than the original CNE as CNE_K only fits the observed information. One exception was the Polbooks network, on which both methods used similar amounts of time, because the network size was not large. However, as the network size increased, CNE_K showed increasing time efficiency. Especially for the Blog network: with \(r_{0}=0.05\%\), CNE_K was 76 times faster than CNE. CNE_K thus enabled network embedding to scale more easily to large networks.  
In addition to time efficiency, CNE_K always achieved a higher AUC than CNE, since CNE will try to model the absence of an edge even where there might actually be an (unobserved) edge. In other words, CNE was trained on data with a substantial amount of label noise: 0 labels (absent edge) that actually must be a 1 (present edge), while CNE_K only used those labels that were known to be correct. Partial network embedding for the knowns is especially useful in settings where only a small part of a large network is observed and the goal is to predict the unobserved links.