# ALPINE: Active Link Prediction Using Network Embedding
## 2 Background
### Network Embedding and Link Prediction  
The confluence of neural network research and network data science has led to numerous network embedding methods being proposed in the past few years. Given a (undirected) network \(\mathcal{G}=(V,E)\) with nodes \(V\) and edges \(E\subseteq{V\choose 2}\), the goal of a network embedding model is to find a mapping \(f:V\rightarrow\mathbb{R}^{d}\) from nodes to \(d\)-dimensional real vectors. The embedding of a network is denoted as \(\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}]^{T}\in\mathbb{R}^{n\times d}\). In short, network embedding methods aim to find embeddings such that first-order [10] or sometimes higher order [18; 19] proximity information between nodes is well approximated by some distance measure between the embeddings of the nodes. In this way, they aim to facilitate a variety of downstream network tasks, including graph visualization, node classification, and link prediction.  
For the link prediction task, a network embedding model uses a function \(g:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}\) evaluated on \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) to compute the probability of nodes \(i\) and \(j\) being linked. In practice, \(g\) can be found by training a classifier (e.g., logistic regression) on a set of linked and unlinked node pairs, while it can also follow directly from the network embedding model. The method CNE, on which most of the contributions in the present paper were based, belongs to the latter type. With \(\mathbf{A}\in\{0,1\}^{n\times n}\) the adjacency matrix of a network \(\mathcal{G}=(V,E)\) (i.e., \(a_{ij}=1\) if \(\{i,j\}\in E\) and zero otherwise), the goal of CNE is to find an embedding, denoted as \(\mathbf{X}^{*}\), that maximizes the probability of the network given that embedding [10]:  
\[P(\mathcal{G}|\mathbf{X})=\prod_{\{i,j\}\in E}P(a_{ij}=1|\mathbf{X})\cdot\prod_{\{k,j \}\in E}P(a_{kl}=0|\mathbf{X}), \tag{1}\]  
where \(P(a_{ij}=1|\mathbf{X})=g(\mathbf{x}_{i},\mathbf{x}_{j})\) for a suitably defined \(g\) (see [10] for details).  
A problem with all existing network embedding methods we are aware of is that they treat _unobserved_ link statuses in the same way they treat _unlinked_ statuses. For example, in methods based on a skip gram with negative sampling, such as DeepWalk [18] and node2 vec [19], the random walks for determining node similarities traverse via known links, avoiding the unobserved node pairs and thus treating them in the same way as the unlinked ones. Similarly, the more recently introduced Graph Convolutional Networks (GCNs) [20] allow nodes to recursively aggregate information from their neighbors, again without distinguishing unobserved from unlinked node pair statuses. We argue that this makes existing methods suboptimal for link prediction in the practically common situation when networks are only partially observed. This has gone largely unnoticed in the literature, probably because partially observed networks do not tend to be used in the empirical evaluation setups in the papers where these methods were introduced.  
The failure to recognize the crucial distinction between unobserved and unlinked node pair statuses has also precluded research on active learning in this context. Indeed, the pool will be a subset of the set of unobserved node pairs, and an unlinked result of a query will add value to the embedding algorithm only if the unobserved status was not already treated as unlinked. Thus, in order to do active network embedding for link prediction, it is essential to distinguish the two links' status.  
While CNE was not originally introduced for embedding partially observed networks, it is easily adapted for this purpose (this is not the case, e.g., for skip gram-based methodsbased on random walks). We will show how this is performed in Section 3.1. This is an important factor contributing to our choice for using this model in this paper.