{'fraction_non_alphanumeric': 0.029486890541657276, 'fraction_numerical': 0.01254601457441214, 'mean_word_length': 4.8900442477876105, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Entity Aware Negative Sampling with Auxiliary Loss of False Negative Prediction for Knowledge Graph Embedding

Knowledge graph (KG) embedding is widely used in many downstream applications using KGs. Generally, since KGs contain only ground truth triples, it is necessary to construct arbitrary negative samples for representation learning of KGs. Recently, various methods for sampling high-quality negatives have been studied because the quality of negative triples has great effect on KG embedding. In this paper, we propose a novel method called Entity Aware Negative Sampling (EANS), which is able to sample negative entities resemble to positive one by adopting Gaussian distribution to the aligned entity index space. Additionally, we introduce auxiliary loss for false negative prediction that can alleviate the impact of the sampled false negative triples. The proposed method can generate high-quality negative samples regardless of negative sample size and effectively mitigate the influence of false negative samples. The experimental results on standard benchmarks show that our EANS outperforms existing the state-of-the-art methods of negative sampling on several knowledge graph embedding models. Moreover, the proposed method achieves competitive performance even when the number of negative samples is limited to only one.


Introduction
Knowledge graph (KG) is a multi-relational directed graph that contains various entities and their relationships.
Each edge of KG describes factual information, called a fact or triple. A fact as triple is composed of two entities and relation corresponding to their relationship and it is represented in the form of (head entity, relation, tail entity), which is denoted as (h, r, t), e.g. (Christopher Nolan, DirectorOf, Interstellar). Freebase (Bollacker et al., 2008), YAGO (Suchanek et al., 2007), and DBpedia (Auer et al., 2007)   scale knowledge graphs that contains real world information. Recently, KG is being actively used to inject structured knowledge into target system in various fields such as recommendation (Wang et al., 2019;Xu et al., 2020;Zhang et al., 2018), question answering (Huang et al., 2019;Saxena et al., 2020), and natural language generation (Liu et al., 2021;Wu et al., 2020). KGs are usually incomplete because there are inevitably missing links between entities. To predict these missing link in KGs, a lot of link prediction (a.k.a., knowledge graph embedding) models are trying to embed elements of KG to low dimensional vector space. Since KGs basically contain only true triples, most of the existing knowledge graph embedding model are trained in a contrastive learning manner that widens the gap of scores between true and false triples.
Obviously, the quality of negative samples is critical to learning knowledge graph embedding. Nevertheless, replacing head or tail entity of positive triple with random entity from the entire entities of KG for constructing negative samples is the most widely used because of its efficiency. Such a uniform random sampling method can be effective at the beginning of training. But as training progresses, the trivial negative samples lose their effectiveness and give zero loss to the training model . To resolve this problem, many studies have been proposed to construct more mean-ingful negatives.
To generate high-quality negative samples, we propose an entity aware negative sampling (EANS) method that exploits entity embeddings of the knowledge graph embedding model itself. EANS can generate high-quality negatives regardless of the negative sample size. The proposed method constructs negative samples based on the assumption that the negative triples which are corrupted by similar candidate entities to the original positive entity will be high-quality negative samples. EANS samples negative entities similar to positive one by utilizing the distribution of entity embeddings. The generated entity aware negative samples push the model to continuously learn effective representations.
While generating high-quality negative samples, it should be careful of the influence of false negatives. When corrupting positive triples using entities which are similar to the positive one, the possibility of generating false negative samples also increases. To alleviate the effect of false negative triples, we propose an auxiliary loss for false negative prediction. The proposed function can mitigate the effect of false negatives by calculating additional prediction scores and reducing the triple scores of false negatives.
We evaluate the proposed EANS method on several famous knowledge graph embedding models and two widely used benchmarks. Based on the experimental results, proposed method achieves remarkable improvements over baseline models. Moreover, it shows better performance than the existing negative sampling methods on several models. Our method also shows comparable performance while using much smaller number of negative samples. Especially EANS produces competitive performance to existing negative sampling methods even with only one negative sample.

Knowledge Graph Embedding Models
There are two main streams in the knowledge graph embedding, one for translational distance models and the other for semantic matching models. TransE (Bordes et al., 2013) is the first proposed translational distance based model. Various extensions of TransE, such as TransH (Wang et al., 2014), TransR (Lin et al., 2015) and TransD (Ji et al., 2015), increase their expressive power by projecting entity and relation vectors into various spaces. RESCAL (Nickel et al., 2011), DistMult (Yang et al., 2014), and ComplEx (Trouillon et al., 2016) is the most representative models of semantic matching based methods. RESCAL treats each relation as a matrix which capture latent semantics of entities. DistMult simplifies RESCAL by constraining relation matrices to diagonal matrices. ComplEx is an extension of DistMult that extend embedding vectors into complex space. Recently, more complex and sophisticated models (Dettmers et al., 2018;Vashishth et al., 2019;Sun et al., 2019;Lu et al., 2022;Vashishth et al., 2020) have been studied. Such methods introduce various technique and networks to model the scoring function and extend embeddings of KG's elements into various spaces.

Negative Sampling
To construct meaningful negative samples, Cai and Wang, 2017) proposed Generative Adversarial Network(GAN) (Goodfellow et al., 2014) based architecture to model the distribution of negative samples. However, these methods need much more additional parameters for extra generator and it could be hard to train GAN because of its instability and degeneracy . To address these problems, caching based method  have been proposed with fewer parameters compared to GAN-based methods to keep high-quality negative triples. (Ahrabian et al., 2020) suggested the method that utilize the structure of graph by choose negative samples from k-hop neighborhood in the graph. (Sun et al., 2019) proposed self-adversarial negative sampling, which give difference weights to each sampled negative according to its triple score. In recent, (Hajimoradlou and Kazemi, 2022) proposed different training procedure without negative sampling. Instead of using negative samples, they fully utilize regularization method to train knowledge graph embeddings.

Method
In this section, we introduce our proposed entity aware negative sampling (EANS) method. The proposed method consists of two parts. One is selecting a negative entity by re-ordering entire entities to create entity aware negative triples, and the other is calculating an additional loss to mitigate the influence of false negatives. The remainder of this section gives details of each part. Entire process of proposed method are summarized in Algorithm 1. Given a KG, let E be the entire entities set, R be the relation set, and G be all truth triple sets. A triple score f (h, r, t) is calculated by an adopted specific knowledge graph embedding model.
In the general uniform random negative sampling method, a negative triple, (h , r, t) or (h, r, t ), can be constructed by corrupting the entities of an observed positive triple (h, r, t), where h , t ∈ E. When corrupting the entities, random entities are extracted from uniformly weighted E. Since the most of the entities in E are not highly related to the each positive triple (h, r, t), it is hard to expect sampling high-quality entities through the uniform random sampling method.
In order to sample meaningful entities, we design EANS to select negative entities that are highly related to the positive one. The key intuition of our method is that two entities which have similar embedding vectors can be high-quality negative sample to each other. Therefore, it is possible to construct high-quality negative samples by corrupting with entities that have similar embedding vectors to positive entity.
The simplest way to find entities similar to the positive entity is calculating the distances between the embedding vectors of the positive entity and entire entities in E at every training step and searching the nearest neighbors. However, this method consumes a large computational resource and the cost will increases dramatically in proportion to the size of embedding dimension d and entities set E.
Instead of applying the nearest neighbor searching for negative entity selection at every step, we design entity clustering based sampling method. First, our method groups similar entities in advance and samples negative entities based on the clusters. This method can be implemented through the Kmeans (Lloyd, 1982) clustering algorithm. Each entity representation e i of i-th entity for K-means clustering is constructed by concatenating all entity specific parameters, where W l are entity specific parameters in model and ; denotes concatenating operation. For example, entity representation of TransD (Ji et al., 2015) consists of entity specific embedding and entity transfer vector, and can be represented as . Given a positive entity, a negative entity is chosen based on the cluster to which the positive entity belongs. The important point of selecting a negative entity is that it is not only selected from the same cluster positive entity belong to, but also selected from the outside of the corresponding cluster. The more details of the method are described in section 3.1.2.
Since clustering algorithm is adopted to the entities which are on training for knowledge graph embedding, the entity embeddings will continuously change as learning goes on. Therefore, cluster labels of entities should be constantly updated. However, executing clustering algorithm in every training step is also intractable. Fortunately, clustering algorithm does not need to be executed every training step for negative sampling. In our experiments, it shows sufficient performance even if the cluster labels were only updated every one to three epoch.

Entity Index Re-Ordering for Gaussian
Sampling in Entity Index Space The K-means clustering algorithm does not guarantee that the numbers of data points in each cluster are evenly divided. If the size of the cluster becomes extremely small, the same entity is used too repeatedly as a negative, which adversely affects learning of models.  To avoid this situation, our method choose negative samples by using index of entity embedding. Commonly, when implementing the negative sampling, one random integer value is uniformly sampled from [0, size_of _entities). After then, the entity embedding with this value as an index is fetched. We modify the process by replacing uniform distribution with Gaussian distribution.
We implement our sampling method to sample a random entity index x from a Gaussian distribution with variance is σ and mean is the index of the positive entity x as µ, .i.e. x ∼ N (µ, σ). If the indices of entities with similar embeddings are arranged to be closed, we can draw entity aware random samples from the process. It can be calculated by multiplying the standard normal distribution N (0, 1) by σ and adding x as follows, where σ is hyperparameters that controls the variance of distribution. For given positive triple (h i , r, t j ), negative samples constructed with corrupted entity, (h i , r, t j ) or (h i , r, t j ). We can control the quality of negative samples through σ. If with a smaller value of σ, more hard negatives will be sampled. On the other hand, if one use a higher value of σ, more diverse negative entities will be extracted. Figure 1 shows the overview of EANS.
To get arranged entity indices, entity embeddings have to be re-ordered based on the clustering result. When entity clustering has done, an arbitrary cluster is randomly selected among K clusters, and the index from 0 to (N − 1) is assigned to the entities in this cluster, where N is the size of the cluster. After then, by calculating the distances between the centroid of the current selected cluster and the remaining clusters, take the nearest cluster as the next cluster to assign indices. All entities of the newly selected cluster be assigned to from N to (2N − 1)-th indices. Repeat this process until all indices of entities are assigned. This re-ordering operation also repeatedly performed according to the changing entity clusters.
For convenience in implementation, we introduce virtual entity indices in the process of entity re-ordering and negative sampling. When the entity cluster labels are updated, only the order of virtual indices and index mapping table are updated. The index mapping table that map the virtual indices and the real entity indices. When negative sampling, a negative entity is selected by using virtual entity indices. All forward operations of model are performed by using the parameters with the real indices connected to the virtual indices of the negatives. An example of entity index re-ordering with virtual index is depicted in Figure 2.

False Negative Prediction Loss
Since the EANS generates negative triples using entities similar to a given positive entity, the probability of generating false negative samples can also be increased. To remedy the false negative problem, we introduce a novel scoring function to measure the plausibility of a triple whether it is false negative or not. We assume the positive entity and the false negative entity has a substitutable relationship. The proposed false negative prediction infers whether the given negative entity can be substituted for the positive entity.
The substitution prediction can be learned together with the original loss function of knowledge graph embedding training. We do not train additional models to learn the substitution score of entities. Instead of using extra model or lots of parameters, we add only a special relation , r sub , called "substitution" is added to the relations set R. The relation r sub will be used in calculation of substitution scores for negative entities. This special relation will be trained together with other elements in KG.
In general, many knowledge graph embedding models learn parameters using a logsigmoid loss function. Given a positive triple (h, r, t) and negative triples (h i , r, t i ), the loss L KG (θ) can be expressed as follows, where γ is fixed margin and σ is sigmoid function. Generally, when generating negative triples (h i , r, t i ), some triples that already observed in the training set are filtered out so that prevent to generate false negative triples. However, we do not filter the false negative triples can be seen in training, but rather try to learn the pattern of false negative triples through them. We modify loss function using substitution scores which manipulate negative scores. The modified loss function can be formulated as, where f θ (t, r sub , t i ) is substitution score for each negative sample, λ 1 is a hyperparameter for downweighting value and y i is label, 1 if the tirple is false negative and 0 otherwise. If corrupted entity is h i , use f θ (h i , r sub , h i ) for substitution score instead.
In the modified loss, the negative scores are reduced by the substitution scores of between positive and corrupted entities. As a result, negative triples with a high substitution scores have a reduced triple scores and the effect of the negative samples on the loss are decreased. In the false negative triples, the substitution score f θ (t i , r sub , t i ) must be high because the positive entity t and negative entity t can be seen substitutable. On the other hand, the influence of substitution scores of true negative samples should be minimized so that the true negatives can contribute to learning. For this, we define an auxiliary loss for substitution score prediction and train it together with the modified loss function L KG . The loss for learning the substitution score, L SU B , is also defined by using the logsigmoid loss function, written as, where λ 2 is hyperparameter. However, following this equation, the substitution scores are trained only increasing way, thus it is not possible to calculate the correct scores. Instead of using negative samples like the original knowledge graph embedding loss, we penalize the substitution score by using an additional regularization term. The modified substitution loss with regularization term can  be formalized as, By regularizing all negative samples, we can make substitution scores of true negative converge to 0. Through this, we can keep the effect of true negative triples and prevent entire substitution scores getting larger. We can effectively avoid the situation of using negative samples again in substitution loss to predict false negative samples by using regularization.
The final loss L is sum of L KG and L SU B as follows, and embedding model are trained to optimize this loss function. We just modify objective loss function for models and do not manipulate any scoring functions. In the experiment results, we figure out that the substitution loss contributes to the training of the knowledge graph embedding.

Experiments
To evaluate our method, we compare the performances of five different knowledge graph embedding models on two benchmark datasets which are widely used in link prediction problem. All models and algorithms are implemented through PyTorch framework and run on a single NVIDIA V100 GPU machine with 32GB RAM. 1

Hyperparameter Settings
We use Adam (Kingma and Ba, 2014) to optimize the experimental models and methods. The hyperparameters are validated in the following range,   (Dettmers et al., 2018), [ † † ] are from , and the other results are taken from the corresponding papers. Bold numbers represent the best and underlined numbers represent the second best.

Datasets and Evaluation Metrics
We evaluate on two datasets, FB15K-237 (Toutanova and Chen, 2015) and WN18RR (Dettmers et al., 2018). FB15K-237 and WN18RR are subsets of FB15K (Bordes et al., 2013;Bollacker et al., 2008) and WN18 (Bordes et al., 2013;Miller, 1995), respectively. In FB15K-237 and WN18RR, some relations that can be easily inferred from inverse-relation have been removed. Since these datasets contain more realistic and refined triples than original datasets, the performance of the model on these datasets can be compared more meaningful. Some statistics of datasets are summarized in Table 1.
In evaluating our methods, we use the standard evaluation metrics mean rank(MR), mean reciprocal rank(MRR), and hits at N(Hit@N). We measure the evaluation metric for all results with filtered setting which is same as (Bordes et al., 2013).

Main Results
We apply our EANS to five different models and compare them with several state-of-the-art negative sampling methods. The models used for compar- ison are TransE (Bordes et al., 2013), TransD (Ji et al., 2015), DistMult (Yang et al., 2014), Com-plEx (Trouillon et al., 2016), and RotatE (Sun et al., 2019). We compare the performances of the models with KB-GAN (Cai and Wang, 2017), NS-Caching , self-adversarial sampling (Sun et al., 2019), SANS (Ahrabian et al., 2020) and our EANS methods. Our EANS method can be used with self-adversarial negative sampling together, and the performances are also confirmed through experiments. Table 2 shows the results of our experiments.
EANS always outperforms all the state-of-theart methods when combined with translational models(TransE, TransD). RotatE with EANS also achieves the best performance on both two datasets. We find that our methods when combined with semantic matching score models(DistMult, Com-plEx) are not the best in MRR, but the second best performance. The reason why our mehtods show those difference may be because the entity clustering process in EANS is based on distance metric.

Small-Sized Negative Sampling Result
We evaluate our method with extremely reduced the negative samples. Table 3 shows the performance when EANS negative sample size is applied as 1. Even though only one negative is used, they EANS is only different about 1-2% on Hit@10 from the best performance of the other state-of-the-art methods. Especially, ComplEx in WN18RR, the performance of only-one-negative setting is only 0.1% different on Hit@10 from the best performance. The results of other scoring function models with small negative samples are reported in Appendix.
We also apply small negative samples to the selfadversarial negative sampling, which is one of the most effective sampling methods. Figure 3 shows the results of TransE and ComplEx with negative sample size n ∈ {1, 4, 8, 16}. In the results, performances of self-adversarial sampling drastically decrease as the negative sample size goes down, but EANS usually does not.  Step Uniform EANS pos.

Quality of Negative Samples from EANS
We compare the negative triple scores calculated by TransE in the training process on the FB15K-237 dataset using EANS and uniform sampling. We check the scores of negative samples in each 1k, 10k, and 100k training step. Table 4 shows the average scores of the positive and negative triples in 1,000 mini-batches calculated by TransE.
As training progresses, the average score of negative triples in the uniform sampling method gradually decreases, and gap between positives and negatives increases. Although the scale of the scores calculated by both methods is similar, the average of negative scores by EANS is higher than the uniform sampling method's scores. It can be seen that EANS generates a large number of high-quality negative samples than uniform negative sampling.
Additionally, we check the distribution of negative scores for each positive sample by applying the softmax function. The scores are averaged in a batch and sorted in descending order. Through Figure 4, we can find that density of the uniform sampling method is skewed to a few top ranked negative samples over time. When training reaches 100K, the only top-64 negative samples account for more than 80% of the total weight, while the distribution of EANS is quite even.

Effectiveness of Substitution Scores for False Negative Prediction
With trained TransE on the FB15K-237, we divide the negative samples into three groups according to their truth values, and check the substitution score distribution in each group. The histogram of substitution scores in each group is depicted in Figure  5. We find that proposed substitution scores can be used to discriminate the true and false negatives. Although the false negative triples which can be observed in evaluation sets are not used in training, they also have high substitution scores. This result shows that the learned substitution relation can infer the substitution relationship between entities which has not seen on training. Additionally, we do ablation test to check whether false negative prediction is helpful for learning. We evaluate EANS combined with Ro-tatE, which showed the best performance among the various models. The two parts of EANS, that extracting entity aware negative from Gaussian distribution and predicting false negatives with substitution loss are separatly adopted. Table 5 shows that separated methods can not produce good performance as performance of whole EANS method. The part using Gaussian sampling (Gauss.) improves performance on FB15K-237, but not on WN18RR. On the other hand, the part using substitution loss (Subs.) shows good performance on WN18RR, but not on FB15K-237.

Conclusions
We propose a novel negative sampling method, EANS, which can sample high-quality negatives based on the given positive entity. The proposed method samples hard negative entities by utilizing entity clustering and Gaussian distribution, and effectively suppresses the influence of false negatives by optimizing the additional false negative prediction loss. Through various analyses, we confirm that each component of EANS contributes to generate high-quality negative samples. Our experimental results show that the performances of proposed EANS combined with several knowledge graph embedding models outperform existing the state-of-the-art negative sampling methods on two standard benchmarks. Moreover, EANS also achieves competitive performance even when the size of the negative sample used for learning is limited to only one.
The biggest limitation of EANS is that a clustering algorithm must be applied to align entire entities. In EANS, it is necessary to cluster and re-order all entity embeddings every 1-3 epochs using the clustering algorithm. Without clustering process, entity aware negatives cannot be sampled. In this paper, we applied the K-means algorithm with complexity dependent on the size of entities set and entity embedding dimension. Even if entity clustering is applied intermittently in EANS, if the size of entities set increases dramatically or the size of entity embedding dimension becomes extremely large, the entity clustering process may become a bottleneck. Therefore, a more efficient entity alignment method may be needed to apply to large scale KG.
In the future, we plan to study methods to estimate entity distribution more efficiently and effectively to overcome this limitation. 5e-5 5e-5 0.001 0.001 5e-5 γ 9.

A.3 Results of Different Small Negative Sample Sizes
We report MRR and Hits@10 results of 4 different negative sample sizes n ∈ {1, 4, 8, 16} to various knowledge graph embedding models with EANS. Table 9 and Table 10 show the results on FB15K-237 and WN18RR, respectively. Through both results, we confirm that EANS works well even when the negative sample size is extremely reduced.