# Improving Graph Neural Network Models in Link Prediction Task via A Policy-Based Training Method
## 2 Preliminary  
### Problem Definition  
A network dataset usually consists of the node set \(V\), the observed edge set \(E\), and the feature matrix \(X\) of nodes, which can be expressed as a simple undirected graph \(G=(V,E,X)\)[4]. The observed edge set \(E\) and unobserved edge set \(E_{u}\) constitute the universal set \(U\), i.e., \(U=E\cup\ E_{u}\). Some edges in the unobserved edge set \(E_{u}\) are missing edges that actually are existing edges. The unobserved edge set \(E_{u}\) consists of missing edges and non-existing edges. The link prediction task aims to find these missing edges in \(E_{u}\) based on the information contained by the structure and node features of \(G\)[4].  
In the network dataset, we cannot know which edges in \(E_{u}\) are missing edges [18]. Therefore, in this work, we divide the observed edge set \(E\) into three subsets: the set \(E_{train}^{pos}\) for training, the set \(E_{valid}^{pos}\) for validation and the set \(E_{test}^{pos}\) for testing. Here, \(E_{train}^{pos}\cup\ E_{valid}^{pos}\cup E_{test}^{pos}=E_{train}^{pos}\cap E_{ valid}^{pos}\cap E_{test}^{pos}=\varnothing\). The edges in set \(E_{train}^{pos}\) are used as the observed edges,and the edges in set \(U-E_{train}^{pos}\) are used as the unobserved edges. The edges in set \(E_{valid}^{pos}\) and \(E_{test}^{pos}\) are used as missing edges to evaluate the prediction performance of GNN models during and after training, respectively. Here, \(\left(E_{valid}^{pos}\cup E_{test}^{pos}\right)\subset\left(U-E_{train}^{pos}\right)\).  
In previous studies, edges in \(E_{train}^{pos}\) are used as positive samples, and edges in \(U-E_{train}^{pos}\) are randomly sampled as negative samples during the training process of GNN models. However, it is not possible to know in advance which edges in \(U-E_{train}^{pos}\) are missing edges. Choosing missing edges as negative samples results in false negative samples. In another scenario, some of the edges randomly sampled from \(U-E_{train}^{pos}\) can be easily distinguished from the edges in \(E_{train}^{pos}\) by GNN models. Choosing such easily distinguishable unobserved edges as negative samples results in easy negative samples. In more detail, several examples of false and easy negative samples are shown in Figure 1. In Figure 1d,e the edges \((v_{3},v_{7})\) and \((v_{1},v_{2})\) are missing edges in \(E_{valid}^{pos}\) and \(E_{test}^{pos}\), which are shown in Figure 1b,c, respectively. Whether the edge \((v_{3},v_{7})\) or \((v_{1},v_{2})\) is sampled as a negative sample, the sampled edge will conversely be regarded as a non-existing edge by GNN models, resulting in poor prediction performance of GNN models. In Figure 1f, if the edge \((v_{1},v_{6})\) can be easily distinguished from observed edges in \(E_{train}^{pos}\) shown in Figure 1a, choosing it as a negative sample contributes insufficiently to the prediction performance of GNN models. Considering the aforementioned two problems, the purpose of this work is to select high-quality negative samples from the \(U-E_{train}^{pos}\) to form the negative sample set \(E_{train}^{neg}\) for the training of GNN models.