Analysis of the Impact of Negative Sampling on Link Prediction in Knowledge Graphs

Knowledge graphs are large, useful, but incomplete knowledge repositories. They encode knowledge through entities and relations which define each other through the connective structure of the graph. This has inspired methods for the joint embedding of entities and relations in continuous low-dimensional vector spaces, that can be used to induce new edges in the graph, i.e., link prediction in knowledge graphs. Learning these representations relies on contrasting positive instances with negative ones. Knowledge graphs include only positive relation instances, leaving the door open for a variety of methods for selecting negative examples. In this paper we present an empirical study on the impact of negative sampling on the learned embeddings, assessed through the task of link prediction. We use state-of-the-art knowledge graph embeddings -- \rescal , TransE, DistMult and ComplEX -- and evaluate on benchmark datasets -- FB15k and WN18. We compare well known methods for negative sampling and additionally propose embedding based sampling methods. We note a marked difference in the impact of these sampling methods on the two datasets, with the"traditional"corrupting positives method leading to best results on WN18, while embedding based methods benefiting the task on FB15k.


INTRODUCTION
Much of human knowledge can be formalized in terms of real world entities, abstract concepts, categories and the relations between them. A graph structure -a knowledge graph (KG) -is a natural candidate for representing this. NELL [5], Freebase [3] and  [25] are examples of large knowledge graphs that contain millions of entities and facts. Facts are represented as triples, each consisting of two entities connected by a binary relation, e.g., (concept:city:London, relation:country capital, concept:country:UK). Here entities such as London and UK are represented as nodes and the relation country capital is represented as a binary link that connects these nodes. e same two nodes may be connected by more than one type of relation, making the KG a multi-graph. KGs have found applications in question answering systems [15], evaluating trustworthiness of web content [8], and web search [7].
Although KGs such as Freebase consist of millions of entities and billions of facts, they are still incomplete [28] which limits their application. However, it is possible to infer new (missing) facts from known facts. Recently, latent factor models that capture global pa erns from the KG have received considerable a ention. ey learn a representation of the graph in a continuous vector space by inducing embeddings that capture the graph structure.
Predicting new edges to automatically add new facts to a KG helps bypass the text analysis stage and bootstrap new knowledge based on what is already captured in the KG. Similar to other problems in processing natural language, such as parsing, data consists (almost) exclusively of positive instances. A solution to this issue is using implicit negative evidence, whereby instances that have not been observed are considered negatives, and are used for contrastive estimation [23], where the aim is to rank observed instances higher than negative (unobserved) ones. Negative instances can be generated using a variety of methods.
In this article we present the results of our investigation on the impact of several negative sampling methods on state-of-the-art knowledge graph embedding models. Additionally we propose two negative sampling strategies for ne tuning the model. Understanding the impact of negative instance sampling will have at least two uses: providing the basis for choosing the negative sampling method to build the best model for a given method, and allowing us to place in the right context results reported in the literature that were produced while using di erent negative sampling methods.

LINK PREDICTION IN KNOWLEDGE GRAPHS
Knowledge graphs KG = (E, R) contain knowledge in the form of relation triples (s, r, t), where s, t ∈ E are entities, and r ∈ R is a relation. ese knowledge graphs are not complete, and additional links (facts) can be inferred, based on the idea that similar nodes have similar relations -e.g. all countries have a capital city. e KG can be encoded using di erent modeling techniques, which results in encodings for both the entities and the relations.
ese methods learn a model for the processed KG as a large set of parameters, induced based on optimizing a loss function with respect to positive and negative instances of links representing di erent relations. Methods such as R [21] and Neural Tensor Networks [24] learn millions of parameters that makes them more exible, enabling them to model well a variety of relations, but at the cost of increased computational complexity and potential over ing. TransE [4], DistMult [29] learn simpler models (with far fewer parameters) and are easier to train but are unable to model certain types of relations such as many-to-one (TransE) and asymmetric relations (DistMult). Recent work such as [20] achieve the modeling power of R with a smaller number of parameters by compressing the tensor product. Complex valued embeddings (ComplEx) [27] extend the DistMult to model antisymmetric relations by using complex valued embeddings. [12] showed that most latent factor models can be modi ed to learn from paths rather than individual triples which improves performance. Recurrent Neural Networks that learn path representations have also been used for link prediction [6,18]. All these models require negative samples during training.
We focus our analysis on four state-of-the-art methods with respect to link prediction in knowledge graphs: ComplEx, DistMult, R , TransE. ComplEx performs as well as the Holographic Embedding (HolE) model, so HolE was not included 1 .

R
e R model [21,22] weighs the interaction of all pairwise latent factors between the source and target entity for predicting a relation. It represents every entity as a d dimensional vector (x ∈ R d ), and every relation as a d × d matrix W ∈ R d ×d .
is model represents the triple (s, r, t) as a score given by s c (s, r , t) = x T s W r x t ese vectors and matrices are learned using a loss function that contrasts the score of a correct triple to incorrect ones. Commonly used loss functions include cross-entropy loss [26], binary negative log likelihood [27], and max-margin loss [12,20] which we use here: is the set of incorrect targets. Similar triples are used where the relation and target are shared, but the source entity is incorrect.

TransE
TransE [4] interprets relations as a translation operation from the source to the target mediated by the relation. More speci cally, it embeds a triple spatially such that the source vector can travel to the target vector through the relation vector, i.e., x s + x r ≈ x t . e scoring function s c (s, r , t) for TransE is given by 1 And also because HolE is very similar to ComplEx. is was veri ed through personal correspondence with an author of the ComplEx paper.
where x s , x r , x t are d dimensional vectors, and d(x) is either the L 1 or L 2 -norm of x. We use TransE with L 2 -norm. For learning embeddings, we use max-margin loss (1). Compared to R , TransE has much fewer parameters, but it is more limited in the variety of relations it can model, as the translation operation assumes 1 : 1 relations.

DistMult
DistMult [29] is a special case of the R model, where the relation matrix is assumed to be diagonal. is results in a sparse relation matrix and consequently fewer parameters. However this simplicity results in the reduction of modeling power. e DistMult model is symmetric and hence can only model symmetric relations. However, DistMult performs well on FB15K benchmark dataset, since the test data contains only a few instances of asymmetric triples. e DistMult scoring function is given by x t is can also be wri en as a three way inner product As before we use the margin loss (1) for learning these vectors.

ComplEx
e ComplEx model [27] performs sparse tensor factorization of the KG in the complex domain. Nodes and relations are modeled by d dimensional vectors with a real and imaginary part (Re(x), Im(x)).
is allows ComplEx to model anti-symmetric relations since the three way dot product (inner product) in the complex domain is not symmetric. ComplEx can be seen as DistMult with complex embeddings. e score function of ComplEx is given by: [27] trained ComplEx with negative log-likelihood. To maintain the same experimental conditions for assessing the e cacy of negative sampling, we train ComplEx with max margin loss (1).

NEGATIVE SAMPLING
Knowledge Graphs capture knowledge as <entity, relation, entity> triples, with entities mapped to nodes, and relations to edges. KGs contain only positive instances. While one-class classi cation solutions have been around for some time [17], for inducing KG embeddings, using negative instances leads to be er models.
Negative instances are not marked in a knowledge graph. e task of link prediction has much in common with other tasks in NLP where (most of) the observed data consists of positive instances. [23] proposed contrastive estimation, whereby instances that were produced by perturbing the observed ones (and that themselves have not been observed) will serve as negative instances, and the aim is to rank observed instances higher than the unobserved ("negative") ones. In neural probabilistic language models, negative sampling was rst proposed in [1] as importance sampling. A sampling solution that was more stable than importance sampling was introduced by [16], who built upon the noise-contrastive estimation [10]. In these approaches negative samples are drawn from a non-parametric noise distribution.
For knowledge graphs in particular there are many di erent ways to produce negative instances based on the graph structure. We present an overview of techniques for producing negative instances from a knowledge graph, and we evaluate their impact on knowledge graph completion, or link prediction.
3.1 Random sampling : R e simplest form of sampling negative instances is to assume a closed world hypothesis and consider any triple that does not appear in the KG as a negative instance. Let , · · · , N } denote the complete knowledge graph, where i = 1 represents the presence of a triple (s i , r i , t i ) (a positive instance) and i = 0 represents absence. According to the closed world assumption, the set of negatives K − is given by Since the KG is incomplete this set contains positive triples not present in the KG. Furthermore this set might be very large because the incorrect facts (O(N 2 )) far outnumber the correct ones.
A simple solution to the scalability problem is randomly sampling a small number of samples from K − . Given a positive triple (s, r, t) we generate n s negative triples by sampling n s target entities from the entity set E. Since the sampling is random, we do not check whether the sampled triples are present in the train and development set, because the probability they are present in K + is negligible. e same procedure is used to generate negative source entities. e negatives produced by random sampling may not be very useful: for the positive triple (Tom Cruise, starred in, Top Gun), negative targets such as London or Mount Everest seem irrelevant. Relevant negative targets should include entities that are movies, such as Terminator, Inception. To obtain such negatives it is necessary to constrain the set of entities from which samples are drawn. We explore such constraints in the following sections.

Corrupting positive instances : C
We use a method described in [24] that generates negative instances by corrupting positive instances: for every relation r , Socher et al. [24] collect the sets S = {s |(s, r, * ) ∈ K + } and T = {t |( * , r, t) ∈ K + }, and produce sets of corrupted triples During training K + consists of triples from training and development set. We sample a number n s of negative samples from S and T . Such a method produces negative instances that are closer to the positive ones than those produced through random sampling.
An issue with this method is that for relations with very few positive instances, there will not be a large enough pool of source and target candidates to corrupt the positive instances. e data analysis shows that this is an issue for the FB15k dataset. For relations where not enough corrupted negative instances can be produced, we supplement this set with randomly produced negative samples.

Typed Sampling : T
Knowledge graphs such as FreeBase and NELL [5] have strongly typed relations. For example, a relation born in holds between entities of type person and entities of type cit . Relevant negative candidates (sources or targets) can be mined by constraining the entities to belong to the same type as that of the source (or target).
is can help bypass the problem mentioned for the corrupt method, when some relations in the dataset have very few instances.
For every relation r : S → T , if S r,t = {s |s has type S t } and T r,t = {t |t has type T t }, with S t and R t the domain and range respectively of r , negative instances will consist of triples (s , r, t), s ∈ S and (s, r , t ), t ∈ T , such that (s , r , t) R and (s, r , t ) K + . We then sample n s number of negative samples from these triples.
If an entity has more than one type (e.g. Albert Einstein has types person, scientist), we include it in S r,t (or T r,t ) if one of its types matches S t (or T t ). We obtain category data for the Freebase dataset from Freebase relation metadata released in [9], and the entity type by mapping the Freebase entity identi er to the Freebase category.
is results in 101,353 instances of the category relation which is used in the training stage to produce typed negative samples. Domain and range types for Freebase relations are provided by Freebase itself. A few examples of entities and types are included in Table 1.
We do not use typed sampling for Wordnet. e hypernym/hyponym relations are the de facto type relations in WordNet, but are hierarchical rather than a mapping onto a given small set of predetermined types as in Freebase.

Relational Sampling : REL
Although typed or corrupt relation sampling can generate relevant negative candidates, due to the incompleteness of the KG, some of these candidates could be unknown positives. If we assume that source target pairs participate in only one relation, then sampling targets (sources) that are connected to the current source (target) through relations other than the current relation can yield true negatives. is is a common procedure in multi-class learning.
More formally, for positive triple (s, r , t) the negative candidate source set is S − = {s |(s, r , t ), ∀ r ∈ R, r r } and target set As before, a er computing S and T we lter out positive triples from train and development set and sample a number n s of negative samples.

Nearest Neighbor sampling : NN
Most negative sampling methods generate negative samples based on either the closed world assumption, functional constraints such as type constraints, and triple perturbation [19]. We introduce a negative sampling method which uses a pre-trained embedding model for generating negative samples. We name this pre-trained embedding model the 'negative sampling model'. We use the negative sampling model to generate negative targets (sources) that are Source Type Source Relation Target  Target Type  f ilm  star wars episode IV produced b  eor e lucas  f ilm producer  person alexandre dumas people pro f ession writer pro f ession academic post pro f essor pro f ession people albert einstein award winner For a positive triple (s, r , t), with x t the vector representation of t obtained from the negative sampling model, the set of negative samples are the top n s nearest neighbors of x t (that are not positive) obtained from the negative sampling model. e negative sampling model may be di erent than the model that is being trained. We use the R model trained with 100 typed (T) negative samples as a negative sampling model for the FB15K dataset. Note that the R model parameters are frozen (not updated), it is simply used for generating negatives that are used for training another model. Algorithm 1 describes the procedure for a single triple. In practice we use a batch of triples and the nearest neighbor search is performed using the Ball Tree algorithm which is built only once since the negative sampling model is not updated.

Algorithm 1: Algorithm 1 Nearest Neighbor Sampling
Input : Triple (s,r,t), Entity Set E, Positive source and targets P s and P t , Negative Sampling Embedding Model f n , Number of negative samples n s Output : Set of n s negative samples N s ← E\P s , N t ← E\P t ; X s n ← f (N s ), X t n ← f (N t ) ; Initialize the K ball tree with X s n and X t n ; x t ← f n (t) ; x s ← f n (s) ; S ← nearest neighbors(x s ,num=n s ); T ← nearest neighbors(x t ,num=n s ); return S,T Nearest neighbor sampling is computationally expensive compared to the methods discussed in previous sections. is is because a search over all entities needs to be performed for source and target entities for every triple. erefore we use a model trained using typed negative sampling methods for Freebase and corrupted sampling for Wordnet to initialize the parameters and then ne tune the model using nearest neighbor sampling for 5 epochs.
3.6 Near Miss sampling : nmiss e nearest neighbor sampler generates negatives that are similar to positives in vector space. Some of those negatives may be ranked higher than the positives. Exposing such highly ranked negatives to the classi er can help the model learn a be er discriminator. We name this se ing as near miss sampling, because the generated negatives are top ranked candidates which makes it di cult for the model to classify them as negatives (near misses). To generate highly ranked negatives, we collect the top n s targets (sources) closest to the predicted target (source) vector. Like the nearest neighbor sampler, we use the negative sampling model for obtaining the predicted vector and entity embeddings. e negative sampling model is not updated.
Given a positive triple (s, r , t) we obtain the predicted vector t = x T s W r where x s , W r are entity and relation embeddings of source s and relation r obtained using the negative sampling model. Note that t may not be the same as x t , the target entity representation. e set of (target) negative samples are the top n s nearest neighbors of the predicted vector t . Algorithm 2 describes the procedure for a single triple, in practice we use a batch and the Ball Tree is built only once.
; Initialize the K ball tree with X s n and X t n ; x s ← f n (s), x t ← f n (r ), W r ← f n (r ) ; s ← x T s W r , t ← W r x t ; S ← nearest neighbors( s ,num=n s ); T ← nearest neighbors( t ,num=n s ); return S,T Like nearest neighbor sampling, near miss sampling is also computationally expensive, so instead of learning from randomly initialized parameters we tune a pre-trained model for 5 epochs.

DATA
We evaluate the impact of negative sampling on the Freebase dataset (FB15k) and on the WordNet dataset (WN18) introduced by [4].
ey are very di erent in coverage -FB15k contains mostly named entities connected through strongly typed relations, while WN18 contains mostly common nouns connected through lexical and semantic relations. Dataset details are included in Table 2   is disparity is also re ected in the distribution of node degrees -12% of the entities have degree equal or less than 10 (appear in at most 10 instances). e average degree of a node in FB15k is approximately 13.2 overall, and 32.4 on the training data. e distribution of relations and node degrees is presented in Figure 1. e type of relations included in Freebase connect named entities. ey are extrinsic relations, in that they do not hold based on the intrinsic properties of the connected entities, but are due to external circumstances. For example, the people profession relation connecting people and their professions are not determined by intrinsic properties of people and professions. Relations in FreeBase are strongly typed -the domain and range of the relations are types, e.g. the country capital relation connects countries and cities.

WN18
is dataset consists of a subset of relations from the WordNet lexical database 3 , split into training, development and testing: 141442/ 5000/ 5000. ere are 18 relations. ere is less variation in the number of instances per relation compared to the FB15k, as can be seen in Figure 2. ere is one relation with less than 100 instances (similar to), while the most frequent relations (hypernym, hyponym) have approximately 35,000. is translates into sparser adjacency matrices for factorization, compared to Freebase.
WordNet contains lexical and semantic relations. Lexical relations -such as derivationally related form connect lemmas from di erent parts of speech that are morphologically connected. e semantic relations cover is a relations (hypernym / hyponym, instance hypernym/hyponym), three types of part of relations (member, substance and part). e semantic relations in WordNet are intrinsic, as they re ect or arise from intrinsic properties of the connected entities. For example, a cat is a animal, and cat has part paws not because of external circumstances, but because of what a cat is. Compared to FreeBase, WordNet relations are not typedthere is no clear domain and range for the WordNet relations.

EXPERIMENTS 5.1 Implementation
For fair comparison we reimplemented R , TransE, DistMult, ComplEx using PyTorch, and tested them using the same experimental se ing: same loss (max-margin loss), embedding size (100), and data. We use the Adam [13] SGD optimizer for training because it addresses the problem of decreasing learning rate in AdaGrad. We ensure that entity embeddings for all the models have unit norm. We performed exhaustive randomized grid search [2] for the L 2 regularizer on the validation set for all models and we tuned the  Table 3: Parameter values training duration using early stopping. e learning rate (lr ) and λ (the L 2 norm coe cient) are presented in Table 3. e code is available in Github 4 . e di erent methods for negative sampling described in Section 3 were used to produce negative instances for training. In FB15K some relations do not have enough sources or targets to generate negative triples by corrupting positive triples. If the number of generated triples are less than the required (n s ), we complete the set of negative samples with randomly generated triples.
For the nearest neighbor and near miss se ings, we used the best performing model for initializing the parameters, and used the R model tuned on typed negative samples (100 negative samples) as the negative sampling model for FB15K and R trained by corrupting positive samples (100 negative samples) for WN18.

Test data
e test data is the same across all experiments. e negative instances for the test data were generated as described in [4] corrupting positive instances using all entities of the dictionary instead of the correct source and target, without sampling.
Also following the procedure of [4], we use the ltered se ing: the negative samples added to the training data are ltered with respect to the test data to avoid (known) false negatives in training.

Evaluation metrics
For evaluation we use the mean reciprocal rank (MRR) and hits@K that are commonly used for link prediction.
For a list of N answers for link prediction, the mean reciprocal rank (MRR) and hits@k are de ned as: where rank i is the rank of the positive instance i predicted by the model with respect to the negative samples. For FB15k we use hits@10, for WN18, hits@1. 4 h ps://github.com/bhushank/kge-rl

Results
We present the results of link prediction on FB15k and WN18 in terms of MRR in Figures 3 and 4 for n s ∈ {1, 2, 5, 10, 20, 50, 100} for each positive instance. e results show that the di erent sampling methods have different e ects on the two datasets. Since link prediction is based exclusively on the embedding of the graphs, di erences in performance are caused by the di erent structure (e.g. di erent node degrees which are re ected in the sparsity of the relation adjacency matrices) and the di erent nature of the relations -typed and extrinsic in FB15k, not typed and (mostly) intrinsic in WordNet.
As suggested by work on learning statistical models through noise contrastive estimation [11], selecting di cult negative instances produces be er models: near miss sampling leads to be er results on FB15k for most embeddings methods. e reason embedding based sampling works well on FreeBase is primarily because the negative samples generated by the pre-trained embedding model are very close to the discriminator boundary. For example, the near miss sampling involves generating negative target entities that are highly ranked by the embedding model. ese entities are likely to be highly ranked by the model that is being trained. erefore providing these entities as negatives allows the system to learn a model that ranks them below the positive target using the max-margin loss. Note that the samples generated by the embedding model are close to each other in vector space due to the ability of the embedding model to cluster entities. erefore almost all the generated negative samples are close to the discriminator boundary. We treated the negative sampling model (pre-trained model) as a hyper parameter. We found that the RESCAL model worked best. We speculate that this might be due to the superior ability of RESCAL model to cluster similar entities.
Corrupting positive instances, the method most frequently used for link prediction, is the least competitive on FB15k, but ts Word-Net well, particularly for R . DistMult is not very sensitive to the type of negative sampling on WN18, except for the nearest neighbor method with which it does not perform well.
To understand why corrupting positive instances works best on WordNet, we look at the data and the graph statistics. e WN18 dataset has 18 relations while with FB15k has about 1495 relations. Due to per relation data sparsity in FB15K, see Fig. 1 and 2, negative sampling using corrupted triples works poorly for FB15K, as it o en has to fall back on random sampling when not enough positive instances with a shared source/target are available for "corruption". Corrupt sampling works be er in an instance rich environment.
Apart from data sparsity, the nature of WordNet and Freebase relations may also a ect the performance of negative sampling methods. WordNet relations have open ended ranges and domains while Freebase relations have typed ranges and domains. Embedding based methods, such as the near miss sampling method we implemented, work on the basis of clustering similar entities, and do not function well for WordNet where the relations do not have domains and ranges that re ect conceptual/semantic clusters.
We have discussed the di erences in performance of sampling methods for the two KGs used. ere are also di erences with respect to the link prediction methods. Random sampling works best for TransE. is may be surprising at rst, but is understandable considering that the theoretical model behind TransE assumes 1 : 1 relations. Providing it with negative entities that are close (using typed, corrupted or embedding methods) does not result in improvement because the negative entities generated using typed, corrupt or embeddings are close to each other in vector space and the model will ultimately be unable to distinguish between them. is is not the case when doing random sampling, when TransE is not perturbed by too close negatives. ComplEx and DistMult perform well with both near miss and nearest neighbour sampling on FB15k. R performs best with near miss sampling on this data, and with corrupting positive samples for WordNet. For middle-range n s relational sampling performs best.
As described in Section 4, the training data for both methods varies quite a bit in terms of the frequency of the relations covered. Freebase is more extreme, in that approximately 39% of the relations have at most 10 positive instances to train on. We analyzed the e ects of negative sampling on di erent slices of the data, split by the order of magnitude (oom) of the frequency of the relations in the training data. More precisely, we group relations into sets G n indexed by the order of magnitude n: G n = {r |10 n < f req(n, training data) <= 10 (n+1) } 5 . Freebase has 5 slices (0..4) and WordNet 4 (1..4). e results (as MRR and hits@K) for slices representing relations with OOM 2 or more closely mirror the overall results. e results for the low frequency relations are shown in Figures 5 and 6. e hits@K score are similar to the MRR ones, so we do not include them 6 .
While the results on the low frequency relations cannot be analyzed separately from the other relations because the embeddings process relies on processing and inducing jointly all relation and 5 We include relations that have only one instance in G 0 . 6 e complete set of plots accompanies the code and will be shared.
Yang et al. [29] Negative  Table 4: SotA results using a max-margin loss function and corrupting positive instances vs. the best performing negative sampling.
entity representations, we can note that the performance on link prediction for these relations with very few instances varies much with the negative sampling method. Overall, the best results are obtained with the same sampling method as for their more populous counterparts, but for speci c ranges of the number of generated negative samples other methods would work best (e.g. nearest neighbor and relational sampling for WordNet data). e reported experiments were performed using the max margin loss function. In Table 4 we include the state of the art results on DistMult, R and TransE obtained with a max margin loss function reported in [29] and corrupting tripes, to compare with the results obtained with the best negative sampling method for the dataset. Slight di erences in the learning rate and λ account for the di erences in performance when using corrupt positive instances as negative samples for the WN18 dataset.
Recently, [27] used the log-likelihood objective, which leads to improvements over the published results for the methods they compared (TransE, ComplEx, HolE, DistMult). We plan to analyze the negative sampling methods while using this new loss function.

CONCLUSION
We report an analysis of the impact of six negative sampling methods on the performance of link prediction in knowledge graphs, for four methods for graph embedding -ComplEx, DistMult, R , TransE. e analysis is performed with respect to two datasets -a subset of Freebase (FB15k) and a subset of WordNet (WN18) -that are very di erent in the type of knowledge they cover.
e results indicate that di erent approaches to negative sampling work best for the two resources. sampling worked best for Freebase with most of the graph embedding methods, while corrupting positive triples leads to best results on WordNet. e newly proposed near miss and nearest neighbor negative sampling work best for Freebase, for three out of the four graph embeddings methods. From analysis of datasets, we further concluded that embedding based negative sampling is very useful for combating data sparsity, while corrupt sampling works best in the data rich scenario. e nature of the relations in these graphs (