Diversified and Adaptive Negative Sampling on Knowledge Graphs

A knowledge graph (KG) is defined by an entity (node) set $\mathcal{V}$, a relation set $\mathcal{R}$ and a ground-truth or positive triplet (edge) set $\mathcal{E}$. Given a triplet $\tau=\langle h,r,t\rangle$ for some $h,t\in\mathcal{V}$ and $r\in\mathcal{R}$, a typical KG model aims to learn a scoring function $\mathcal{F}(\tau)$ to estimate the probability that $\tau$ is a positive triplet, i.e., $\tau$ is a fact that should appear in the ground truth set $\mathcal{E}$.

Given the power of graph convolutional networks, in this paper, we adopt a multi-layer relational graph convolutional network (RGCN) [29] to serve as our base embedding model in Figure 1(a). The base model encodes the entities in layer $l+1$ into vectors $\mathbf{e}_{i}^{l+1}\in\mathbb{R}^{d^{l+1}}$ in a latent embedding space, by aggregating their embeddings $\mathbf{e}_{j}^{l}\in\mathbb{R}^{d^{l}}$ from the previous layer $l$, as follows.

where $\mathcal{N}_{i}^{r}$ is the set of neighbors of entity $i$ under relation $r$, $W_{r}^{l}$ is a trainable weight matrix for $r$, $W_{0}^{l}$ is an additional trainable weight matrix to capture the self-information of each entity in layer $l$, and ReLU is the activation function. Assuming a total of $L$ layers are stacked, the embeddings in the last layer are the output embeddings, which we simply write as $\mathbf{e}_{i}\in\mathbb{R}^{d},\forall i\in\mathcal{V}$.

To optimize the parameters, a set of training triplets $\mathcal{D}_{\text{tr}}$ that consists of both positive and negative triplets is used. As shown in Figure 1(d), our objective is to sample a set of high-quality negative triplets, which, together with positive triplets, will be used to minimize the following cross-entropy loss:

where $y_{\tau}=1$ if $\tau\in\mathcal{E}$, else $y_{\tau}=0$. We implement $\mathcal{F}$ using three popular decoders, namely, DistMult [44], ComplEx [36] and RotatE [34]. We provide the DistMult function below, and leave the details of ComplEx and RotatE to A.

where $\sigma$ is the sigmoid activation, $\mathbf{e}_{h},\mathbf{e}_{t}$ are the head, tail entity embeddings from RGCN, $\text{Diag}(\mathbf{e}_{r})\in\mathbb{R}^{d\times d}$ is diagonal matrix whose diagonal is $\mathbf{e}_{r}$, an $r$-specific trainable vector of the decoder. Therefore, the full set of training parameters of the base model is $\Theta=\{W_{r}^{l}:r\in\mathcal{R},l\leq L\}\cup\{W_{0}^{l}:l\leq L\}\cup\{\mathbf{e}_{r}:r\in\mathcal{R}\}.$

A common way to obtain a negative triplet is to replace the tail (or head) entity in a positive triplet by a randomly sampled entity. Beyond simple random sampling, generative adversarial nets (GAN) [10] such as KBGAN [3], IGAN [38], HeGAN [11] and GNDN [47], which learn the underlying sample distributions, have been shown to be effective in negative sampling on KG or other graph structures.

Formally, given a positive triplet $\langle h,r,t\rangle$, a generator $G$ aims to produce a “fake” tail entity $t^{\prime}$ to replace the real tail $t$, resulting in a negative triplet $\langle h,r,t^{\prime}\rangle$. More precisely, $G$ is a function that maps a noise $\epsilon$ (typically sampled from a prior distribution) to a vector $\mathbf{e}_{t^{\prime}}$ in the entity embedding space. Although we follow a similar process, distinct from existing GAN-based approaches, we propose an adaptive two-way generator, as shown in Figure 1(b). It not only diversifies the generation of fake entities, but also localizes the global generator model to adapt to fine-grained differences across entities.

Each pathway is implemented as a multi-layer perceptron (MLP). Taking $G_{E}$ as an example, its MLP is parameterized by $\Theta_{G_{E}}$ which consists of the weights and biases in each layer. Let $\mathbf{x}_{G_{E}}^{m+1}$ denote the activations of the $m$-th MLP layer, where the activations of the last MLP layer are simply the output embedding of $G_{E}$. The architecture of $G_{R}$ mirrors that of $G_{E}$.

Consider the pathway $G_{E}$ to generate a fake tail entity for a head entity $h$. We adapt the global model $G_{E}$ to suit the head entity $h$, by modulating the activations in each hidden layer of $G_{E}$:

where $\alpha_{h}^{m}$ and $\beta_{h}^{m}$ are vectors conditioned on the head entity $h$ and have the same dimension as the $m$-th layer of $G_{E}$. They are used to scale and shift the activations $\mathbf{x}_{G_{E}}^{m}$ of the $m$-th layer of $G_{E}$. That is, the global $G_{E}$ is adapted into a local model conditioned on $h$. More specifically, $\alpha_{h}^{m}$ and $\beta_{h}^{m}$ are output of the FiLM layer $F_{E}$ applied to the $m$-th layer of $G_{E}$, as follows.

Note that the head entity embedding $\mathbf{e}_{h}$ is the input to $F_{E}$, making the output adaptive to and conditioned on $h$. $F_{E}$ can be implemented as a MLP, parameterized by $\Theta_{F_{E},\alpha}^{m}$ and $\Theta_{F_{E},\beta}^{m}$ in the $m$-th layer of $G_{E}$. Similarly, the second pathway $G_{R}$ can be modulated by a FiLM layer $F_{R}$, whose input is $\mathbf{e}_{h}\otimes\mathbf{e}_{r}$, to generate a fake tail entity for a head entity $h$ and relation $r$. $F_{R}$ is parameterized by $\Theta_{F_{R},\alpha}^{m}$ and $\Theta_{F_{R},\beta}^{m}$ in the $m$-th layer of $G_{R}$, to output $\alpha_{h,r}^{m}$ and $\beta_{h,r}^{m}$ to scale and shift the activations in $G_{R}$.

To sum up, the trainable parameters in the adaptive two-way generator, $\Theta_{G}$, include the weights in the two global pathways and the FiLM layer weights for each layer in each pathway. Assuming a total of $M$ hidden layers in the global pathways, we would have $\Theta_{G}=\{\Theta_{G_{E}},\Theta_{G_{R}}\}\cup\{\Theta_{F_{E},\alpha}^{m},\Theta_{F_{E},\beta}^{m},\Theta_{F_{R},\alpha}^{m},\Theta_{F_{R},\beta}^{m}:m\leq M\}$.

As in a standard GAN architecture, a discriminator is needed to help the generator produce high-quality fake entities that mimic real entities. Specifically, the discriminator and the generator compete with each other in a minimax game, in which the generator aims to fool the discriminator by producing realistic looking entities, while the discriminator aims to beat the generator by distinguishing the real and fake entities. In our case, given the two-way generator, we further equip the discriminator with the ability to distinguish the fake entities generated by the two pathways, which can further differentiate and diversify the two pathways.

Concretely, as shown in Figure 1(c), the discriminator also has two pathways: $D_{\text{Adv}}$, an adversarial pathway to distinguish fake and real entities, and $D_{\text{Aux}}$, an auxiliary pathway to distinguish fake entities generated by $G_{E}$ and $G_{R}$. Taking the generation of tail entities as an example, given the real tail entity $t$ in a positive triplet, as well as the fake entities $t^{\prime}$ generated by $G_{E}$ and $t^{\prime\prime}$ generated by $G_{R}$, $D_{\text{Adv}}$ tries to distinguish $t$ from $t^{\prime}$ and $t^{\prime\prime}$, while $D_{\text{Aux}}$ tries to distinguish $t^{\prime}$ from $t^{\prime\prime}$. In other words, each of them involves a binary classification:

where $D_{\text{Adv}}$ and $D_{\text{Aux}}$ are implemented as a fully connected layer, and $\tilde{\mathbf{e}}_{i}=\textsc{\capitalisewords{{mlp}}}(\mathbf{e}_{i};\Theta_{D_{S}})$ is a shared hidden representation computed from the embedding $\mathbf{e}_{i}$ of a real or fake entity $i$. The shared hidden representation allows both $D_{\text{Adv}}$ and $D_{\text{Aux}}$ to benefit from each other during training as in Odena [23], as they collectively try to distinguish three different classes of samples ($t$, $t^{\prime}$, $t^{\prime\prime}$).

Note that $\hat{y}_{\text{Adv},i}$ (or $\hat{y}_{\text{Aux},i}$) is the predicted value of the ground-truth label $y_{\text{Adv},i}$ (or $y_{\text{Aux},i}$), such that $y_{\text{Adv},i}=1$ if $i$ is a real entity, else $y_{\text{Adv},i}=0$. Furthermore, for a fake entity $i$, we define $y_{\text{Aux},i}=1$ if $\mathbf{e}_{i}$ is generated via Eq. (4), or 0 if generated via Eq. (5). Subsequently, we employ a cross-entropy loss on the two discriminator pathways:

In summary, the set of trainable parameters of the two-way discriminator pathway includes the shared parameters and the weights of each classifier, i.e., $\Theta_{D}=\{\Theta_{D_{S}},\Theta_{D_{\text{Adv}}},\Theta_{D_{\text{Aux}}}\}.$

Lastly, we train the generator, discriminator, and base embedding model jointly. On the one hand, the generator aims to fool the adversarial pathway of the discriminator, making $D_{\text{Adv}}$ harder to distinguish real and fake entities, as below.

where $t$ is a real tail entity, and $t^{\prime},t^{\prime\prime}$ are fake tail entities from $G_{E}$ and $G_{R}$, respectively (again, we only illustrate the case where the tail entity in a positive triplet is replaced). The last term in Eq. (3.4) is a regularization term on the scaling and shifting factors to prevent overfitting as in Oreshkin et al. [24], and $\lambda$ is a hyper-parameter to control the strength of regularization. On the other hand, the goal of the discriminator is to overcome the generators by distinguishing fake and real entities, as well as fake entities from different generator pathways, as follows.

where $i$ can be either real or fake entity in the first term, but $i\neq t$ can only be a fake entity in the second term.

Following a typical adversarial training scheme in negative sampling on knowledge graphs in KBGAN [3], we alternate the model updating among the three parties, as follows. First, we train the generator by updating the generator parameters $\Theta_{G}$ with Eq. (3.4), while freezing the discriminator parameters $\Theta_{D}$ and the base model parameters $\Theta$. Next, we update $\Theta_{D}$ with Eq. (3.4), while freezing $\Theta_{G},\Theta$. Finally, we update $\Theta$ by minimizing the loss on the positive and negative triples in Eq. (2), while freezing the other two parameter sets. We repeat the three steps until the convergence of all parties are achieved.

(1) Negative samplers with the same RGCN backbone [29] and decoders. In other words, they are flexible “plug-ins” that only replace the sampling strategy for a fair comparison to our method DANS. They include Rand, which replaces the head or tail entity with a uniformly sampled random entity; Pop [20]: a variant of Rand that substitutes uniform sampling with popularity-weighted sampling; Self-adv [35]: a self-adversarial negative sampling methodology; MCNS [45]: a model which derives negative samples from a distribution that is positively but sub-linearly correlated with the positive distribution.

(2) Other state-of-the-art baselines for knowledge graph embedding which may employ a variety of different backbones, heuristics and techniques that diverge from DANS, for a comprehensive comparison. They include SANS-RW [1]: a structure-aware model that selects negative samples at close proximity from positive nodes via random walks on the graph; NSCaching [48]: a model that employs importance sampling to sample more informative negative triplets; KBGAN [3]: a GAN-based model that learns to generate informative negative triplets; CAKE [22]: a framework which leverages extra information such as entity types to from factual triplets to sample negative triplets; SMiLE [25]: a framework which employs specific contextual information influenced by entity types to sample negative triplets.

Furthermore, we generate $N_{s}=20$ negative triplets for each positive triplet, out of which the first ten negative triplets are equally split between the two generator pathways, while the remaining ten negative triplets are obtained via uniform random sampling to further increase the diversity. In all cases, either the head or tail of the positive triplets are randomly replaced with negative entities, but not both. We set the output embedding dimension $d$ to 100 for all methods, except SANS-RW, where $d$ is set to the recommended 1,000 to achieve optimal performance. RGCN, RGCN-P, RGCN-Adv and RGCN-MCNS follow the same implementation and settings per the backbone of DANS.

In addition, the hyper-parameters related to negative sampling via Metr-opolis-Hastings in RGCN-MCNS have been copied from the original paper ’s link prediction experiments in Yang et al. [45]. To reduce the variance resulting from parameter initialization, the experimental results are calculated from an average of five runs with different seeds in all methods. Furthermore, every method is standardized to use the triplet loss in Eqs.(2). Other baseline settings have also been tuned according to the recommendations of the literature. Additional details can be found in C.

Table 2 reports quantitative comparison against the first category of baselines involving different negative samplers under the same backbone and decoder. Overall, our model DANS consistently leads to better performance for DistMult, RotatE and ComplEx decoders. This shows the robustness of our approach across various decoders. In general, DANS performs better than Rand and its variant Pop, showing that it is important to account for the informativeness of negative triples which are missing in random and popularity-weighted sampling. Since Self-Adv accounts for the informativeness by giving more weight to higher quality triplets, it generally outperforms Rand and Pop. It still lags behind DANS in most cases as it ignores the concepts of diversity and adaptiveness. The variant MCNS shows better performance than Rand and its variant Pop but loses to DANS  as MCNS was originally designed for homogeneous graphs.

Next, Table 3 compares DANS with the second category of baselines. Negative sampling in SANS-RW is not relation-aware and thus performs poorly on datasets with more variety of relations, namely, NELL-995 and UMLS. In addition, KBGAN fell short for the two bigger datasets WN18RR and NELL-995 as it ignores graph structure in the sampling process. Furthermore, its adversarial training process potentially suffers from instability and degeneracy. On the other hand, NSCaching employs a more streamlined importance sampling approach, contributing to its competitive performance despite not considering graph structure for negative sampling. As CAKE and SMiLE leverage on extra side information such as entity types to enhance its performances, their experimental results deteriorate as such information are not available in standard knowledge graph completion benchmarks in this paper.

Overall, DANS has obtained favourable performance, showing the importance of diversity and adaptiveness during negative sampling. We will conduct further ablation study in the next part to examine the contribution from each aspect. Finally, we have included the experimental results for dataset FB15k-237 which show favorable performance on ComplEx decoder in D.

In this part, we seek to investigate RQ1–RQ4 listed at the beginning of this section. All experiments in this part are conducted using the DistMult function as the decoder.

From the results, among the single pathways (either $G_{E}$ or $G_{R}$), there is no consistent winner and it depends on the dataset. However, it is clear that the use of both pathways in the generator ($G_{ER}$) outperforms using just a single pathway. Thus, this addresses RQ1 and shows that diversifying the negative triplets with the two-way generator can improve model performance and improve the overall informativeness of the negative triplets.

Furthermore, by comparing $G_{ER}$ (i.e., both pathways without FiLM) and the proposed model DANS (i.e., both pathways with FiLM), our model obtains a significant lead in performance. This addresses RQ2 and shows the effectiveness of our adaptive design using FiLM.

Next, we investigate the impact of adaptive regularization controlled by $\lambda$ in Figure 2(c). Generally, having such a regularization (i.e., $\lambda>0$) avoids excessive scaling and shifting from the FiLM layer, and thus reduces overfitting to individual entities or relations. In particular, the MRR performance improves as $\lambda$ increases and achieves the most optimal performance for all three datasets when $\lambda$ is around 1e-4. As the optimal values of $N_{s}$ and $\lambda$ are largely stable across the three datasets, our model is not sensitive to these hyperparameter settings, and potentially requires less effort in hyperparameter tuning. We also note that the performance on the UMLS datasets tends to be more sensitive to changes in both parameters. This could be because UMLS is a smaller dataset than the other two, containing only 5,216 positive triplets in training and this increases the risk of overfitting to certain settings in general.

Note that the ablation study has demonstrated improved model performance with the two-way generator, FiLM layers and provided direct evidence on the importance of diverse pathways and FiLM in the model architecture. However, it is not immediately clear if having two pathways and FiLM layers in the generator would indeed produce diverse and adaptive examples in their embedding space. Instead, as asked in RQ4, can we observe some generated examples on their diversity and adaptiveness?

To demonstrate the notion of diversity in RQ4, we present a few case studies of how DANS can produce more diverse examples than uniform random sampling (RNS) or popularity-weight random sampling (PNS). In Figures 4 and 4 we visualize the positive and negative tail entities w.r.t. a given relation and all its head entities on each dataset. More specifically, each point represents one tail entity, which can be a positive (real) tail entity, or a negative tail entity. The negative entity can be generated by one of the pathways $G_{E}$ or $G_{R}$ of the generator, or randomly sampled by RNS or PNS. The high-dimensional embedding space is projected onto a Cartesian plane using the $t$-SNE algorithm [37]. In Figure 4, we compare the diversity of negative entities generated by DANS with that of RNS-based negative entities. For our case study, we select one relation for each dataset, namely, $\mathtt{hasPart}$ on WN18RR, $\mathtt{animalType}$ on NELL-995 and $\mathtt{isA}$ on UMLS, so that all the positive and negative tail entities for a common relation (and the same original head entities) can be contrasted in one visualization. The results show that DANS could provide more diverse negative entities for model training, where those generated by $G_{E}$ and $G_{R}$ occupy different subspaces from the positive entities. In contrast, RNS lacks diversity and samples negative entities in the same subspace as positive entities. This could even potentially contribute to false negative triplets as they are not well separated from the real ones. Similarly, in Figure 4, we compare the negative entities generated from $G_{E}$ and $G_{R}$ in DANS against the output of PNS, which replaces uniform negative sampling with popularity-weighted sampling. The results again echoed that DANS has produced more diverse negative entities in different subspaces as the positive entities, whereas PNS samples negative entities that mostly overlap with the positive triplets with less diversity.

On the other hand, to demonstrate the notion of adaptiveness, we compare two different relations from each dataset to visualize its differences with and without FiLM layers. For example, Figure 5 visualizes the impact of adaptiveness for relations $\mathtt{DomainRegion}$ and $\mathtt{DomainUsage}$ in the WN18RR dataset. “Positive1” and “Positive2” denote the existing positive entities of each of the two relations, respectively; “Fake1” and “Fake2” denote the corresponding negative samples produced from the generators for each of the two relations, respsectively. As shown in Figure 5(a), without FiLM layers, “Fake1” and “Fake2” both spread across the plane without any clear association to the corresponding “Positive1” and “Positive2”, and thus offering less discriminative power to improve the learning of each relation. In contrast, in Figure 5(b), after FiLM layers are added, we can clearly visualize that “Fake1” and “Fake2” are adapted to “Positive1” and “Positive2” as they move closer to each of their respective positive samples, improving the discriminative power of learning. This demonstrates that the global generators are adapted into local models conditioned on individual input (entity or relation) when FiLM layers are present. Similar patterns can be observed in NELL-995 and UMLS datasets, which are presented in E.