Md Kamrul Islam
email: kamrul.islam@loria.fr

Sabeur Aridhi
email: sabeur.aridhi@loria.fr

Malika Smail-Tabbone
email: malika.smail@loria.fr

Negative Sampling and Rule Mining for Explainable Link Prediction in Knowledge Graphs

Keywords: knowledge graph embedding, link prediction, negative sampling, rule mining, explainability

Several KG embedding methods were proposed to learn low dimensional vector representations of entities and relations of a KG. Such representations facilitate the link prediction task, in the service of inference and KG completion.

In this context, it is important to achieve both an efficient KG embedding and explainable predictions. During learning of efficient embeddings, sampling negative triples was highlighted as an important step as KGs only have observed positive triples. We propose an efficient simple negative sampling (SNS) method based on the assumption that the entities which are closer in the embedding space to the corrupted entity are able to provide high-quality negative triples. As for explainability, it actually constitutes a thriving research question especially when it comes to analyse KGs with their rich semantics rooted in description logics. Hence, we propose in this paper a new rule mining method on the basis of learned embeddings. We extensively evaluate our proposals through several experiments. We evaluate our SNS sampling method plugged to several KG embedding models through link prediction task performances on well-known datasets. Experimental results show that the SNS improves the prediction performance of KG embedding models, and outperforms the existing sampling methods. To assess the performance of our rule mining method with and without SNS, we mine and evaluate rules on three popular datasets.

Introduction

Today knowledge graphs are commonly adopted for knowledge representation. A knowledge graph (KG) is a graph-based representation of knowledge which models real-world entities and their relations in various domains [START_REF] Paulheim | Knowledge graph refinement: A survey of approaches and evaluation methods[END_REF]. Formally, a KG is represented as a collection of RDF triples, (head, relation, tail) where the head and the tail are two entities which are connected by a specific relation. KGs form building blocks for many applications, ranging from question answering to content-based recommendation. Large KGs contain millions of entities and billions of triples (e.g., FreeBase, DBPedia, YAGO). Despite of their huge size, KGs are often incomplete. For example, birth place of more than 70% of person entities in Freebase is missing [START_REF] Dong | Knowledge vault: A web-scale approach to probabilistic knowledge fusion[END_REF]. The incompleteness issue of KGs motivates researchers to study how to add or infer new triples in KGs. This task is known as link prediction in KGs.

In recent years, many embedding models have been proposed to learn vector representations (or embeddings) of entities and relations in KGs. These models perform the link prediction task based on the learned embeddings. The training of these models requires positive triples as well as negative (non-observed) triples. However, only positive triples are available in KGs. Importantly, the quality of negative triples does matter as it influences the overall results of the models [START_REF] Cai | KBGAN: Adversarial learning for knowledge graph embeddings[END_REF][START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF]. This brings the importance of sampling negative triples. However, this feature is not well covered in the literature. To the best of our knowledge, there exist some negative sampling methods such as uniform-random [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF], GANbased [START_REF] Cai | KBGAN: Adversarial learning for knowledge graph embeddings[END_REF][START_REF] Hu | A knowledge selective adversarial network for link prediction in knowledge graph[END_REF][START_REF] Wang | Incorporating GAN for negative sampling in knowledge representation learning[END_REF], NSCaching [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF],Self-adversarial [START_REF] Sun | Rotate: Knowledge graph embedding by relational rotation in complex space[END_REF], and SANS [START_REF] Ahrabian | Structure aware negative sampling in knowledge graphs[END_REF]. All these methods, except the first one, look for hard negatives for a positive triple. A negative triple, which is hard to differentiate from positive triples, is considered a hard negative [START_REF] Wang | Incorporating GAN for negative sampling in knowledge representation learning[END_REF]. However, each of them has its own pros-cons and the current state-of-art still lacks good negative sampling methods. We proposed a simple but efficient method called SNS to sample high-quality negative triples in KG [START_REF] Islam | Simple negative sampling for link prediction in knowledge graphs[END_REF] making a good balance between exploration and exploitation to improve the quality of negative triples. We design SNS as a general sampling method that can be plugged to any KG embedding model for link prediction.

We provide a thorough description of the method principles (Section 2.1).

Today, the major limitation of KG embedding-based link prediction methods is their lack of explainability, which limits their ability to be deployed in many real-world applications. This seems to be particularly absurd given the richness of the initial graph. Hence we propose a new rule mining method that utilizes the KG and its embedding and a strategy to use the rules to explain the embeddingbased link prediction (Section 3.1).

The rest of the paper is organized as follows. After introducing the SNS sampling method and its related works in Section 2, we present our rule mining method in Section 3. In Section 4, we present our experimental settings. In Section 5, we present the obtained results of the conducted experiments to evaluate our rule mining method in combination with the SNS sampling method.

The last section is devoted to the conclusions and the future directions.

The Simple Negative Sampling (SNS) method

In this section, we describe our SNS sampling method (Section 2.1) and related works (Section 2.2). We summarize the notations in Table 1 which are used throughout the paper.

The SNS method

For link prediction, KG embedding models are trained with positive and negative triples to learn embeddings of entities and relations. A good trade-off between exploration and exploitation is crucial in searching for a high-quality Inverse relation of a relation r negative triples [START_REF] Chen | Optimal contraction theorem for exploration-exploitation tradeoff in search and optimization[END_REF]. Exploration corresponds to the capacity of the sampling method to select high-quality negative triples from unexplored areas whereas exploitation favours the utilization of already known negative triples to sample other negatives. SNS is concerned with achieving a fair balance between exploration and exploitation in the quest for good negatives. We first briefly describe a classical KG embedding model, and then our proposed SNS negative sampling method. The architecture of a classical KG embedding model is given in Figure 1 which starts with initializing the embeddings of entities and relations randomly from uniform/Gaussian distributions [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF]. For the training of the model, a batch of positive train triples S m is fetched and a negative sampling method is then used to generate a batch of negative triples. In the architecture, we inject our SNS method (shaded by yellowish color in Figure 1) to generate the batch of negative triples, S ′ m for the batch of positive triples,S m . The batches of positive and negative triples are then used to learn the embeddings.

In this paper, we consider the pairwise training which is able to work under the 'open-world' assumption [START_REF] Nickel | A review of relational machine learning for knowledge graphs[END_REF]. In pairwise training, the model tries to assign more plausibility score to a positive triple than its corresponding negative triple.

The training objective is to optimize the embeddings of entities and relations for minimizing the total pairwise loss as designed in Equation 1.

min Θ ∀ (h,r,t)∈Sm,(h ′ ,r,t ′ )∈S ′ m L(f (h, r, t), f (h ′ , r, t ′ )) + λreg(Θ) (1)
Here, f is the scoring function of the embedding model, (h, r, t) ∈ S m is a positive triple and (h ′ , r, t ′ ) ∈ S ′ m is the corresponding negative triple. The pairwise loss for the positive and its negative triple is defined in Equation 2 [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF].

L(f (h, r, t), f (h ′ , r, t ′ )) = λ -f (h, r, t) + f (h ′ , r, t ′ ) + (2)
Here, λ is the margin and [.] + = max(0, .) is the hinge function. The embedding updating process is repeated for all batches of positive triples (shaded by dark gray color in Figure 1), and the whole training process (shaded by light gray color in Figure 1) is repeated for T times (or epochs). The model training process is similar to a traditional KG embedding model except we adapt our negative sampling method. We refer to [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF] for more details about the traditional KG embedding.

In the following, we describe our method for negative sample generation.

Step 1. Triple perturbation: SNS, like other sampling methods, begins with perturbing a positive triple to generate an initial negative triple set. In triple perturbation, the head/tail of the positive triple is corrupted by replacing head/tail with other entities in the entity set(E). At the same time, the negative set is checked to make sure that it does not include any positive triple. To illustrate, consider the positive triple q = (h, r, t) ∈ S. Corrupting the tail(t) gives the initial negative set q ′ 0 (t) = {(h, r, t ′ ) / ∈ Q|t ′ ∈ E}.

Step 2. Candidate set generation: Generally, the size of the set q ′ 0 (t) is large as KG contains large number of entities. Zhang et al. [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF] describe that only some of initial negatives of the set are of good-quality. As we need few negatives for each positive triple, we randomly sample N 1 triples from q ′ 0 (t) to generate candidate negative set q ′ 1 (t)(i.e. q ′ 1 (t) ⊆ q ′ 0 (t)) for user defined parameter N 1 . As the training progresses, it is hoped that the quality of the negative(s) for the following step would be better or comparable to that of the current step's negative(s). For this purpose, the sampled negatives from the current step are kept in a small structure named least recently selected(LRS). LRS[q ′ h , q ′ t ] stores sampled negatives where q ′ t and q ′ h are the sampled negatives by head and tail corruption respectively in the preceding step. The stored negatives are then utilized to sample high-quality negatives in the following step. The candidate negative set, q ′ 1 (t) is updated to include the LRS negative(s) as

q ′ 1 (t) := q ′ 1 (t) ∪ LRS[q ′ t ].
The use of LRS is intended to favour the exploitation behavior of the proposed SNS method. It assures that the quality of the current step's negative(s) is better than, or at least comparable to, the quality of the preceding step's negative(s).

Step 3. Sampling probability computation: In this step, we compute the sampling probability of each negative in the candidate negative set q ′ 1 (t). Negatives having a higher probability are assumed to be of higher quality. The probability is defined based on the distance of each negative. The distance for a negative triple, (h, r, t ′ i ) ∈ q ′ 1 (t) is computed as the Euclidean distance between the corrupted(t) and the new entities(t ′ i ) as Equation 3.

d(t, t ′ i ) = ||t -t ′ i || (3)
Here, t and t ′ i are embeddings of the entities t and t ′ i . The sampling probability of each candidate negative, (h, r, t ′ i ) ∈ q ′ 1 (t) is then computed using a softmax function as Equation 4.

P (h, r, t ′ i ) = exp( 1 d(t,t ′ i ) ) N1 j=1 exp( 1 d(t,t ′ j ) ) (4)
For a candidate negative triple with a lower distance, the softmax function returns a higher sampling probability.

Step 4. Negative triple sampling and LRS updating: The triples from the candidate negative set,q ′ 1 (t) are ranked in decreasing order of their probabilities and k negative(s) are sampled. A natural choice could be sampling top-k (k=1 for pairwise training, k > 1 for maximum likelihood training) negative(s). However, sampling the top-k ranked negative(s) may lead to two issues. Firstly, because the current candidate negative set also includes the least recently sampled (LRS) high-quality negatives, there is a high chance of repeated sampling of the same negative(s) (even in several successive steps).

This issue affects the exploration potential of SNS sampling. Secondly, the existence of false negative triples (that appear to be of high quality) cannot be overlooked [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF]. To tackle these issues, SNS randomly samples k negative triples from N 2 top ranked triples in q ′ t as q ′ t = {(h, r, t ′ )|rank (h,r,t ′ )≤N2 } for user-defined parameter N 2 where N 2 > k. SNS repeats the above described process (from initial negative set generation to k negative(s) sampling) for head(h) corruption to sample k negative(s) as q ′ h for the positive triple, q. The LRS[q ′ t , q ′ h ] is updated with the sampled 2k high-quality negative(s). Finally, we randomly sample k high-quality negative(s) as q ′ h,r,t from 2k negatives in q ′ h ∪ q ′ t . The sampled k negative(s), q ′ and the corresponding positive, q are then used to train the KG embedding model.

Related works

During the training of KG embedding-based model, high-quality negative triples, which are not readily available, have a significant contribution. One simple way to sample negative triples is based on 'closed-world' assumption where all non-observed triples are assumed to be false and can be used as negatives.

However, this assumption is not entirely true for KGs due to their incompleteness [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF]. Alternatively, most of the KG embedding models sample negatives from non-observed triples under 'open-world' assumption where a non-observed triple may be positive or negative. Generally, candidate negative triple set is generated by positive triple perturbation where head/tail entities are replaced with other possible entities [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF] and then negative triples are sampled from the set. 'Uniform-random' is the mostly used negative sampling method where negative triples are randomly sampled from a uniform distribution of candidate negatives [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF]. Though 'uniform-random' is simple, a sampled negative triple could be easily classified as negative. Consequently, 'uniform-random' method suffers from 'zero-loss'/'vanishing-gradient' problem [START_REF] Cai | KBGAN: Adversarial learning for knowledge graph embeddings[END_REF]. To avoid this problem, the generative property of GAN frameworks was recently proposed to generate high-quality negatives. The generator of GAN is trained to pick high-quality negative triples whereas the discriminator part is trained to learn embeddings. IGAN [START_REF] Wang | Incorporating GAN for negative sampling in knowledge representation learning[END_REF], KBGAN [START_REF] Cai | KBGAN: Adversarial learning for knowledge graph embeddings[END_REF], KSGAN [START_REF] Hu | A knowledge selective adversarial network for link prediction in knowledge graph[END_REF] are three GAN-based sampling methods for KGs. Compared to 'uniform-random' sampling, these methods improve the quality of negative triples but they increase the number of model parameters and take extra costs on training for parameter optimization [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF]. In addition, they suffer from instability and degeneracy problems because of adopting the complex reinforcement learning to train the generator [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF]. To avoid the excessive training time of GAN-based methods, Zhang et al. [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF] proposed a 'distilled' version of GAN-based methods, namely NSCaching which stores negatives with high scores in head and tail caches for each positive triple, and then samples negatives directly from the caches. With NSCaching sampling, KG embedding models show competitive link prediction performance. However, the memory requirement increases exponentially with the size of KGs. Also, the regular updating of caches increases the computational time. Thus, scalablity is a big issue for NSCaching and it is not recommended for large KGs. Self-adversarial [START_REF] Sun | Rotate: Knowledge graph embedding by relational rotation in complex space[END_REF] is another adversarial negative sampling method which computes high sampling probability for high triple scoring negatives. However, negatives with high scores may be positive though they are unobserved. This 'false-negative' case is over- looked in self-adversarial sampling. Apart from the above-mentioned sampling methods, the hard negative mining in contrastive learning motivates Ahrabian et al. [START_REF] Ahrabian | Structure aware negative sampling in knowledge graphs[END_REF] to study the neighborhood information of entities to sample negatives.

They develop SANS method based on an assumption that neighbor entities without direct relation are good candidates for generating negatives. However, the one-time generation of negatives prior to the start of the embedding learning process is expensive in terms of memory requirements, as it requires the whole adjacency matrix of a KG in main memory.

The rule mining method

In this section, we start with describing our rule mining method which learns rules from a knowledge graph and its embedding (Section 3.1) and the strategy of using learned rules in explaining predictions (Section 3.2). Then we describe related works (Section 3.3).

Rule Mining from a Knowledge Graph and its Embedding

To mine rules from a KG, we focus on different path types in a KG. Figure 2 illustrates four types of paths of length 2 in the 'Family' KG. We give more importance to shorter paths than longer ones. A path is a sequence of triples in which one common entity appears in between two consecutive triples. We compute the score of a path, P as the average score over all triples in a path, penalized by the path length. We define the path scoring function as

P ath score, P S(P ) = 1 l 1+α l i=1 f (h i , r i , t i ) ( 6
)
where f is the embedding scoring function, l is the length of the path, α is the penalizing factor and 0 ≤ α ≤ 1. α = 0 means we consider all paths equally whatever their length whereas larger values give more importance to shorter paths.

In the following we describe the procedure for rule mining which starts with graph generation, proceeds with triple sampling and ends with mining rules.

Bidirectional graph generation

To facilitate the search of the diverse paths to be used in in the rule bodies, we generate a bidirectional graph, G. To do so, we first generate a graph from KG training triples. For each triple (h, r, t) ∈ G, we add an inverse relation, i.e.

G ← G ∪ (t, r -1 , h) if there is no relation from t to h. In this way we make the graph bidirectional so that for every triple the tail is accessible from head as well as the head is accessible from tail. This transformation helps us to extract diverse path types (examples in Figures 2b-2c).

For simplicity, we illustrate the procedure of mining rules for a specific relation, r in Figure 3. We describe the process in the following sub-sections.

Sampling triples

Real-world KGs contain millions of triples for a relation and it is intractable to process such a huge number of triples for rule mining. We assume that mining rules from a portion of the entire triple set well reflect the rules over the entire triple set for a relation. To mine rules, we randomly select a portion of the triple set from the whole triple set of a relation.

Initial rule set mining

The initial rule set mining procedure for a relation, r is illustrated in Figure 3.

In the following, we describe each step in details.

Step 1 (Fetch a triple): We consider the triples to arrive sequentially from the sampled triple set. The procedure starts with fetching the arrived triple (h,r,t). Note that only one triple is fetched at a time and the next triple is fetched after complete processing of the current triple.

Step 2 (Extracting path chunk): After fetching the triple, the relation, r from h to t and its inverse(r -1 ) (if it exists) are removed temporarily from the graph. Then a set of simple paths up to a length, MaxL from h to t are extracted.

Here, MaxL is the predefined maximum body length, or simply maximum rule length. A simple path is a directed path from h to t with no repeated entities.

After extracting the path set, the removed relations between h and t are added again to make the graph in its original form.

Step 3 (Computing path scores and ranks): The scores of all extracted paths are computed using the paths scoring function in Equation 6. Note that a path may contain the inverse relation of the form (h i , r -1 i , t i ). In this case, the triple score is computed as f (t i , r i , h i ). This computation allows us to include all the cases in Figure 2.

The paths are then ranked in decreasing order of their scores. Better ranking of a path means better chance that the path will generate a good rule.

Step 4 (Defining rules from paths): In this step, a path is transformed into a rule by replacing the entities of triples with variables. If the head and tail of a triple (h i , r i , t i ) are replaced with variables e i-1 and e i then the triple is transformed into the body relation in the form r i (e i-1 , e i ). An inverse relation

(h i , r -1 i , t i ) is transformed in the form r i (e i , e i-1
Usually the decay rate is 0 < γ < 1. Small value of γ means potential rules will be alive for longer period before dying if they don't last for long time. Generally, the number of paths between two entities is high in a dense KG and low in a sparse KG. Hence, we argue that the possibility of the presence of noisy rules for a relation is high in a dense KG and low in a sparse KG. We recommend setting a high decay rate for a dense KG and a low decay rate for a sparse KG. All potential rules with negative energies are identified as noisy rules and immediately removed from memory.

Final rule set generation

The above rule mining processes (Section 3.

Abduction for Explainable Link Prediction

Once the rules are learned, they can be exploited to provide plausible explanations to support certain predictions. We propose a procedure inspired by abductive reasoning over the rules to infer the best explanation(s) for a prediction. Indeed abductive reasoning using a body->head rule allows us to infer (or at least assume) that body is satisfied whenever head is observed. Hence given a prediction as an observation, we look for rules whose head corresponds to the prediction. Each rule instantiation (using the bidirectional graph paths) constitutes then a plausible explanation for the prediction. Thus we have a way to further rank the top-k predictions based on their explainability.

Related works

Inducing first-order logical rules from a logical program (knowledge base containing facts and rules) in ILP (Inductive Logic programming) or multi- relational learning constituted seminal and important works in symbolic AI [START_REF] Muggleton | Inverse entailment and progol[END_REF][START_REF] Dehaspe | Discovery of frequent datalog patterns[END_REF]. The main limitation of such methods is their lack of scalability on large knowledge bases and their main strength is their high human-readability. In parallel, pattern mining algorithms were designed to extract association rules between frequent itemsets found in a binary data table [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF][START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF][START_REF] Ng | Exploratory mining and pruning optimizations of constrained associations rules[END_REF]. In both cases, the achieved rule set constitute a good synthetic description of the data.

Each rule can be evaluated using certain metrics and can also be exploited in prediction (or classification) mode using a deductive reasoning schema (i.e., If the left (body) part of a rule is true Then infer That the right (head) part of the rule is true).

With the generalization of KGs and KG embeddings, two approaches aim at mining rules from learned embeddings: (1) EmbedRule [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF] and (2) RLvLR (Rule Learning via Learning Representations) [START_REF] Omran | An embedding-based approach to rule learning in knowledge graphs[END_REF]. Our work differs from theirs in several points. Firstly, both existing methods mine rules based on closed path (CP) pattern, whereas our method considers more path patterns for mining better rules. Secondly, our method is able to detect and remove noisy rules early enough to reduce memory and computational time requirements. Finally, the existing methods only consider relation embedding for mining rules, thus losing the entity embedding information as the validity of a triple depends on both entity and relation embeddings. In contrast, our method utilizes the triple scoring function of an embedding method to define the path scoring function so as to exploit both entity and relation embeddings in mining high-quality rules.

Experimental settings

Experimental configuration

To evaluate the efficiency of SNS sampling, we plug it to a KG embedding model. The main focus of this paper is negative sampling for KGs. For evaluation, we choose TransH [START_REF] Wang | Knowledge graph embedding by translating on hyperplanes[END_REF] to represent translational models and DistMult [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF] to represent semantic matching models as they are popular baselines for link prediction task in KGs [START_REF] Wang | Knowledge graph embedding: A survey of approaches and applications[END_REF]. For details about the models, we refer to the original papers. The scoring functions of the models are given in Table 2. Each model is evaluated for four existing sampling methods (i.e. uniform-random, GANbased, NSCaching, self-adversarial) and for the proposed SNS methods. We do not include SANS in the experiment due to its excessive memory requirement.

For GAN-based method, we choose KBGAN as it is the only GAN-based sampling which has publicly available implementation (to best of our knowledge).

We refer to the original articles for details about the sampling methods.

Model

Embeddings Scoring function,f (h, r, t)

TransH [21] h d , t d , r d , w d r ||(h -w T r hw r ) + r -(t -w T r tw r )|| 2 2 DistMult [19] h d , t d , r d h T diag(r)t
To evaluate our rule mining method, we used the embeddings learned by DistMult with SNS and DistMult with random sampling. The source code of this paper can be found in our public GitLab repository2 . In the repository, we provide instructions to execute the whole pipeline on the KGs mentioned as well as on a new KG.

Datasets

In the experiments, we use six widely used benchmark KG datasets, i.e., FB15K, FB15K-237, WN18, WN18RR, YAGO3-10, Family for link prediction task [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF][START_REF] Cai | KBGAN: Adversarial learning for knowledge graph embeddings[END_REF][START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF]. WN18 is derived from the WordNet which is a large semantic lexicon for the English language. FB15K is a subset of triples from Freebase KG which is a large collaborative general knowledge base. WN18RR and FB15K-237 datasets are derived from WN18 and FB15K respectively after removing the inverse-duplicate relations. The YAGO3-10 dataset is extracted from the open source YAGO knowledge base considering the entities with at least 10 relations.

The last KG is Family KG, where the relations are family relationships among people [START_REF] Kok | Statistical predicate invention[END_REF][START_REF] Sadeghian | Drum: end-to-end differentiable rule mining on knowledge graphs[END_REF]. This KG is used to assess the rule mining method as the relationships in Family are easily interpretable. The KG datasets come with train/valid/test splits. To evaluate the performance of any sampling method, we plug it to a KG embedding model for link prediction task. The performance is defined with two widely used metrics: Hit@z, and mean reciprocal rank (MRR) [START_REF] Wang | A survey on knowledge graph embeddings for link prediction[END_REF]. The metrics are defined based on the rank of the positive test triple. Hit@z is defined as the average number of times a positive test triple is among the z highest ranked triples; whereas MRR is the average reciprocal rank of the positive test triple [START_REF] Rossi | Knowledge graph embeddings: Are relation-learning models learning relations?[END_REF]. The range of both scores is 0 to 1. The higher value of MRR demonstrates the better ranking of positive test triples and better ranking provides better prediction performance. Also, higher Hit@z score indicates better performance. To illustrate, consider the positive test triple q = (h, r, t) ∈ D. A set of negative triples q ′ t = {(h, r, t ′ ) / ∈ Q|t ′ ∈ E} is generated by simple triple perturbation (replacing tail with other entities) [START_REF] Bordes | Translating embeddings for modeling multi-relational data[END_REF][START_REF] Ji | Knowledge graph embedding via dynamic mapping matrix[END_REF] confirming that no positive triple exists in q ′ t . The triples in q ∪ q ′ t are then ranked in decreasing order of their scores (computed by embedding-based scoring functions in Table 2). The rank of the positive test triple q in q ∪ q ′ t is defined as rank t q . Based on the rank of each positive test triple q, the performance metrics are defined in Equations 8 and 9.

Hit t @z = 1 |D| q∈D hit t q , hit t q =      1, if rank t q ≤ z 0, otherwise (8)
M RR t = 1 |D| q∈D 1 rank t q (9)
The whole evaluation process is also repeated by corrupting the head entity of each positive triple as well and Hit h @z, M RR h are computed. The final Hit@z, M RR metrics are the average of head and tails metrics i.e. Hit@z = (Hit t @z +Hit h @z)/2 and M RR = (M RR t +M RR h )/2. We re-scale the Hit@z score from the range 0-1 to 0-100 to facilitate the comparisons. As suggested by the most of the literature for link prediction in KGs, we consider z ∈ {1, 3, 10}.

Evaluation metrics for the rule mining method

To assess the quality of learned rules, we rely on two common statistical measures standard confidence (SC) and head coverage (HC) [START_REF] Omran | An embedding-based approach to rule learning in knowledge graphs[END_REF]. Both measures are defined based on the support of a rule in the following form.

Rule : r 1 (e, e 1 ) ∧ r 2 (e 1 , e 2 ) ∧ .... ∧ r n (e n-1 , e n ) -→ r(e, e n )

The support of a rule is defined as the number of triples instantiating the rule [START_REF] Omran | An embedding-based approach to rule learning in knowledge graphs[END_REF].

Support(Rule) = #(e, e n ) : body(Rule) ∩ head(Rule) (10)
SC is defined as the ratio of support and the number of entity pairs instantiating the body. The HC is the ratio of support and the number of entity pairs instantiating the head.

SC(Rule) = Support(Rule) #(e, e ′ ) : body(Rule) (11)
HC(Rule) = Support(Rule) #(e, e ′ ) : head(Rule) (12)

Configuration of rule-based explanation of predictions

As for explainable link prediction we need a metric to measure the potential of explanation of the rule set. We consider a positive test triple with a hit@10 score of 1 as a correct prediction. We aim to explain such predictions that are made by the embedding-based method. For each predicted triple, we identify the rules which make the prediction true through abduction-based instantiation (Section 3.2). The authors of the literature rule mining methods use precision metric to assess prediction performance [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF][START_REF] Ho | Rule learning from knowledge graphs guided by embedding models[END_REF]. Considering the incompleteness of a KG, we argue that precision could be a misleading metric as an unobserved triple is not necessarily false. Instead, we compute the recall score to evaluate the performance of our rule mining method. We define a true positive prediction as a test triple explained at least by one rule and the number of positives is the number of triples in the test set.

Results and discussion

We describe the link prediction performance of embedding-based methods with SNS sampling in Section 5.1 to assess the impact of SNS in improving embedding quality. In Section 5.2, we describe the performance of our rule mining method with its sensitivity to parameters. Finally, we explain a few embedding-based predictions with the help of mined rules in Section 5.3.

Link prediction performance

The proposed SNS method is implemented in Python with the well-known PyTorch and run on a 'NVIDIA A100-PCIE-40GB' GPU. For all of the experiments, we set the training epochs to 200, the embedding dimension to 100, the learning rate to 0.0001, and the margin value to 4.0. For the embedding optimization task, we use the popular Adam optimizer [START_REF] Kingma | A method for stochastic optimization[END_REF]. For all the datasets, the link prediction performance of embedding models with SNS sampling is computed and compared to other sampling methods. Then, for the WN18RR dataset, we do further analyses including parameter sensitivity and performance evolution with the number of epochs.

Prediction Performance: We train the KG embedding models from scratch for each sampling method, Random-uniform, KBGAN, NSCaching, SNS, selfadversarial (Self-Adv). For parameter setting, we follow the recommendations from the original papers ( [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF] for NSCaching, [START_REF] Cai | KBGAN: Adversarial learning for knowledge graph embeddings[END_REF] for KBGAN, [START_REF] Sun | Rotate: Knowledge graph embedding by relational rotation in complex space[END_REF] for Self-Adv).

Table 4 shows the prediction metrics. With respect to most of the prediction metrics in most of the KG datasets, the proposed SNS clearly outperforms all other negative sampling methods when they are plugged into the translational model (TransH). When injected into the TransH, SNS improves hit@k scores by 2-5 percent compared to the second best sampling method in the WordNet KGs (WN18RR, WN18). SNS sampling produces the best results for the FB15K, Family datasets, with Hit@k scores improving by 5-8% when compared to the second best sample methods. For the YAGO 3-10 dataset, SNS also remains best or second best in almost all metrics. The most suitable reason for this success could be a good balance between exploration and exploitation. When the sampling methods are used with DistMult model, the hit@10 and hit@3 scores drop in all datasets. The metrics could be improved by training the model for more epochs. However, we are comparing different sampling strategies rather than different prediction models. SNS with the DistMult method shows a similar trend of improved prediction performance.

In this section, we provide a visualization of the closeness of the original and Overall, the minimum median illustrates that the selected entities for negative sample generation are closer to the original entities in SNS than other sampling methods. The selection of close entities in SNS leads to the generation of hard negative triples and improves the prediction performance in turn, as seen in Table 4.

In the following, we describe further analyses of prediction by TransH with different sampling methods in the second smallest KG dataset, WN18RR.

Change in prediction performance for different epoch numbers:

We present the MRR and Hit@10 scores of an embedding model in Figure 5 with remain the highest among all sampling methods in the subsequent epochs, despite the fact that the improvement rate is not constant. The 'uniform-random' method has the lowest MRR because it does not manage to pick high-quality negatives. These improvements in rank are reflected in Hit@10 scores curves where SNS has the highest Hit@10 scores in later half of training epochs. These improvements in performance prove that our sampling method is able to provide better ranks of test triples than the state-of-art sampling methods.

Parameter sensitivity analysis: SNS sampling method has two parameters, N 1 and N 2 . To describe the changes in performance for different values of these parameters, we record Hit@10 and MRR scores for different values of N 1 with fixed N 2 = 5 which are plotted in Figure 6. As the value of N 1 increases, more initial negative triples are explored and the SNS sampling gets tion effect leading to drops in MRR and Hit@10 metrics. With N 2 =1, we see lowest prediction performance for SNS. As the value of N 2 increases, SNS gets better exploration and the best balance between exploration and exploitation is found for N 2 =5 where the highest prediction metrics are recorded. However as the value of N 2 increases, the chance of sampling of known high-quality triple decreases (poor exploitation) and the chance of sampling less good-quality negative increases. As a result, the performance drops as seen in Figure 7 where both hit@10 and MRR drop for N 2 > 5.

Memory and computational efficiency Undoubtedly, random-uniform is the simplest, fastest, most memory efficient sampling method as it does not learn or store any parameter. GAN-based sampling makes the prediction model more complex, increases the number of training parameters, and makes the model harder to train due to use of reinforcement learning [START_REF] Zhang | Nscaching: simple and efficient negative sampling for knowledge graph embedding[END_REF]. As a consequence, KBGAN needs extra memory and computational cost to store and optimize the parameters. Self-adversarial sampling is simpler and more memory efficient Examples of negative triples: In this section, we tabulate the sampled negative triples by different sampling methods with TransH for five randomly selected positive triples from the WN18RR KG dataset. From Table 5, the sampled negative triples by the 'random' method are almost unrelated to the positive triple. For example, the method generates (pakistan,has part,deposit) which is totally unrelated to the positive triple (pakistan,has part,tirich mir) (at least seen with an open eye). Compared to other methods, SNS samples more semantically related negative triples, which is different from type relatedness.

For example, SNS replaces 'tirich mir' with 'amazon' which generates better negative triple than replacing 'tirich mir' with 'malevolence' by NSCaching or 'tirich mir' with 'chute' by KBGAN, or 'tirich mir' with 'deposit' by the 'random' sampling method. The empirical results show an improvement in negative triple quality. As we deliberately limit the strength of sampled negative triples by N 1 , some unrelated negative triples may remain. A small number of weak negative triples can even help the model's training by introducing a penalty in loss that reduces over-fitting.

Relation-wise performance in WN18RR dataset: To go beyond aggregated performance values, we intend to see the prediction performance on individual relation types in the WN18RR dataset. We choose TransH as the embedding method because it is seen from Table 4 that TransH with SNS shows better prediction performance (in terms of hit@10 and hit@3 than DistMult with random sampling. We train TransH with different sampling methods and record the MRR and Hit@10 metrics for each relation type for each sampling prediction performance scores are higher for relations with a higher number of facts. We see the best MRR and hit@10 scores for the SNS method in almost 70% and 50% of the relations, respectively, which means that our sampling method ranks the triple better than other sampling methods. The performance metrics are poor in most of the relations with a low number of facts (similar to, member of domain usage, member of domain region). The embedding quality of the relations suffers as a result of a lack of adequate triples, and the prediction performance of the relations drops as a consequences. The performance scores of other sampling methods are high in some particular relations. For example, KBGAN shows remarkable performance in also see, similar to and verb group relations while the performance is poor for the hypernym relation. NSCaching is the second-best option in most cases.

Rule performance

The proposed rule mining method is implemented in Python with well-known PyTorch and run on a Intel(R) Core(TM) i7-1.90GHz CPU machine. We use the embeddings learned by an embedding method with SNS sampling strategy in rule mining task. To learn embeddings, we choose DistMult embedding method We describe performance of our rule mining method in terms of prediction recall and quality metrics.

Noisy rule identification:

While the existing embedding-based rule mining methods identify noisy rules based on the quality metrics at the end of the mining process (depending on thresholds on quality metrics), our method is able to identify them early. In Table 10, we tabulate the top-5 ranked mined rules for the 'Father' relation in Family KG. Looking at the head coverage and standard confidence scores, we find that our method is able to compute low/better ranks for high-quality rules.

Scalability:

To assess the behaviour of our rule mining method for different KGs with different scales of connectivity, we illustrate the computational time for mining length-2 rules for the Family, WN18RR and FB15K-237 KGs in Figure 10.

Among the three KGs, WN18RR is the most sparse (average node degree<5.0) whereas the other two are denser. As expected, we see that the average rule mining time grows as node degree increases because the number of paths between a pair of nodes is usually higher in a dense graph.

Parameter sensitivity:

We assess parameter's sensitivity of our rule mining method, we implement the method on the WN18RR and Family KGs to learn length-3 rules. In learning embedding, we choose our SNS sampling method. There are four parameters in our rule mining method and they are sampling rate, top-k paths, decay rate, and rule length.

Sampling rate: To assess how the rule mining method behaves, we illustrate computational time and performance metrics (recall, HC, SC) for different sampling rates in Figure 11. As expected, the computational time increases with increasing the sampling rate in Figure 11a for both datasets. The chance of generating more rules for a high sampling rate is high, and consequently the recall score is improved in Figure 11c. The rule mining time grows faster for the dense Family KG than the sparse WN18RR as the number of paths grows more quickly for the denser Family KG. The recall scores for WN18RR improved as we have more rules for higher sampling rate (Figure 11b). On the other hand, the recall scores for Family KG remain nearly very close for different sampling rate. The most suitable reason is that the high-quality embeddings help the proposed rule mining method in extracting high-quality rules frequently, even with low sampling rate. More rules including low-quality rules are mined for higher sampling rate which causes the overall quality metrics to be dropped for higher sampling rate. This situation is seen for both of the KGs. We see the sampling rate has impact on computational time as well as prediction and quality metrics. Undoubtedly, choosing a good sampling rate is a challenging but important task.

Top-k: We evaluate the total number of mined rules and the recall, HC, and SC of rules for different top-k values to describe the sensitivity of the "topk" parameter in our rule mining method. Figure 12a shows that the number of mined rules increases with increasing top-k for WN18RR and Family KGs.

Consideration of more paths between a pair of nodes, including high-quality and low-quality paths, is the most possible reason behind this rising trend in the number of rules. This assumption is further supported by the quality metrics in Figure 12b where both HC and SC drop as the top-k increases for both KGs.

Decay rate: To assess the sensitivity of our rule mining method to the "decay rate" parameter, we evaluate the total number of mined rules, recall, and quality metrics of our rule mining method for different decay rates. As the decay rate increases, the energy of an unobserved rule drops faster, and as a result, it lives for a low period in the system. For this reason, we see that the total number of mined rules in Figure 13a falls and consequently the recall scores dropped for higher decay rate. In contrast, the rule quality scores increases for both KGs as only high-quality rules are extracted those happen very frequently for higher decay rate.

Maximum rule-length: Finally, we assess the sensitivity of the proposed rule mining method to "maximum rule length" parameter in terms of computational time, total number of rules, recall and quality metrics. The number of paths between a pair of nodes in a graph increases quickly as the maximum allowable path length increases. This results in rising computational time exponentially for mining rules as seen in Fig 14a . As the number of possible paths between a pair of nodes increases with increasing path length, the total number of rules also increases for higher rule length for both KGs in Fig 14b . As more rules are mined, the recall increases and quality metrics drops in Figure 14c.

Illustration of Explainable link prediction in FB15K-237

In this section, we take advantage from mined rules to explain the link prediction by embedding-based method. We consider the test triples which have hit@10 score 1 as correctly predicted triples. For a correctly predicted triple, we find the most suitable path that hits a rule from mined rule set. We give preference to shorter paths in case of occurring multiple paths.

We illustrate the link prediction explanation based on the mined length-2 rules in FB15K-237 KG. Note that the entities in this KG come with Free- base identifier and Freebase KG is no more maintained. We map the Freebase identifier to Wikidata identifier using Freebase data dump [START_REF]Freebase data dumps[END_REF] and then the description of the entities are extracted from Wikidata using the Wikidata identifier. For illustration, we consider few triples with the '/film/film/language' relation from FB15K-237 KG which are correctly predicted by embedding-based method. The heads of these triples are film names and the tails are languages of films. For example, (Contact,../film/language, English) is interpreted as "The language of the film 'Contact' is 'English'".

Conclusion and Perspectives

In this paper, we propose a simple and efficient negative sampling method for knowledge graph embedding. The method is general and can be plugged to any knowledge graph embedding method. The method is able to generate high-quality negative triples and takes low computational time and memory while anticipating the 'vanishing-gradient' problem. Experimentally, we evaluate our method on six knowledge graph datasets for link prediction task and also describe its parameter sensitivity. The results show that the proposed SNS sampling brings consistent improvements in prediction performance. We also propose a new embedding-based rule mining method that is memory efficient and able to mine a diverse set of rule patterns. We take advantage of the rule mining method to explain the link prediction in order to minimize the 'explainability' limitation of embedding-based link prediction methods to some extent.

To explain link prediction, the proposed rule mining method may be used in conjunction with any knowledge graph embedding method.

The poor performance of the studied methods on YAGO3-10 leaves the future work to explore other embedding models in the literature on this dataset. Another perspective of this study is to plug SNS to a recently published approach, TransO, leveraging ontology information for learning better embeddings [START_REF] Li | Transo: a knowledge-driven representation learning method with ontology information constraints[END_REF].

Such improved embeddings may also be helpful for learning better rules. As SNS uses only entity embeddings for sampling negative examples, it should also be usable in dynamic graph embedding approaches [START_REF] Xue | Dynamic network embedding survey[END_REF]. Implementing both our methods in a distributed environment to improve computational efficiency is another promising research direction. We also leave designing a good strategy for sampling the triples for our proposed rule mining method to future exploration, which can help to learn high quality rules with low sampling rate.

Figure 1 :

 1 Figure 1: Architecture of a classical KG embedding model with SNS sampling

  (a) start@head-closed@tail/ closed path (b) Cycle (c) start@head-closed@middle (d) start@middle-closed@tail

Figure 2 :

 2 Figure 2: Different types of paths for defining length-2 rules

Figure 3 :

 3 Figure 3: Rule mining for a target relation, r

). Step 5 (

 5 Update rule set): If a high-quality rule, 'Rule' does not exist in initial rule set, Rule set of a relation then its is added by initializing its structure as follows Rule.count = 1 Rule.energy = 1.0 + γ The 'count' variable of the rule represents the number of occurrences of the rule and the energy variable takes the full energy and an additional decay rate (γ) as initial energy. The rule is then added to the initial rule set, Rule set i.e. Rule set ← Rule set ∪ Rule. In case the rule 'Rule' already exists in the Rule set, then its count and energy values are updated as Rule set[Rule].count = Rule set[Rule].count + 1 Rule set[Rule].energy = 1.0 + γ We define the top-k ranked extracted rules as high-quality rules where k is an user-defined parameter. Step 6 (Identify and remove noisy rules): The rules which are not useful in mining high-quality rules for a relation are identified as noisy and removed immediately. This removal reduces unnecessary memory and computing time consumption. In our method, a rule falls in one of three statutes. A 'potential' rule has positive energy but count below 2. A 'stable' rule has count above 1, and a noisy rule has count below 2 and negative energy. A 'potential' rule may become 'stable' or 'noisy' later. Every time a triple is fetched from the sampled triple set, the energy of each potential rule, 'Rule' from the Rule set is decreased by the decay rate γ as Rule set[Rule].energy = Rule set[Rule].energy -γ

  new entities in positives and their corresponding negatives in the second smallest KG dataset, WN18RR. Different negative sampling methods with TransH are used to learn embeddings. For the visualization, the negatives in the final epoch (i.e. epoch number 200) are analyzed. In Figure 4, we show the distribution of distances between the original and the new entities for different sampling methods. The box for SNS sampling shows the minimum median distance.

Figure 4 :

 4 Figure 4: The distribution of distances between the original and the new entities in the positives and their corresponding negative triples in the WN18RR dataset: The embeddings of entities and relations are learned by TransH with different sampling methods.

( a )

 a Epoch number vs MRR (b) Epoch number vs Hit@10

Figure 5 :Figure 6 :Figure 7 .N 2 .Figure 7 :

 56727 Figure 5: Prediction scores of TransH with different samplings in different epochs

  than GAN-based sampling as it does not require to train a generator module like GAN-based sampling. NSCaching stores set of high-quality negative triples in each positive triple cache which makes it worst memory efficient. In addition, the method takes additional time to update the cache periodically. The proposed SNS sampling method does not increase the training parameter like GAN-based method. It memorizes only the least recently sampled negative triple which takes very small amount of memory. Thus, intuitively SNS sampling is more memory efficient than GAN-based sampling and NSCaching. The method does not use complex learning method like GAN-based method or does not take extra cache updating time like NSCaching. It takes very small amount of time to update the LRS structure. Considering the training time of each sampling method with the TransH embedding model, we see that the training time increases as the number of training samples increases, as expected. We also find 7-40% and 3-14% improvement in training time for SNS when it is compared to KBGAN and NSCaching respectively.

Figure 8 :

 8 Figure 8: Identification of noisy rules for "brother" relations in the Family KG

Fig- ure 8 5 . 2 . 2 .

 8522 shows the amount of identified noisy rules with different amounts of processed triples for 'brother' relation in Family KG. The early identification of noisy rules in our method reduces resource memory consumption as well as processing time. Mining out-of closed path rule: While existing embedding-based rule mining methods mine rules based on closed paths, our method is able to mine rules which do not follow closed path property. Below the examples of two mined rules out-of closed paths for 'aunt'

Figure 9 :

 9 Figure 9: Change in prediction performance and quality with different percentages of mined rules of length-2 in the Family KG

Figure 10 :

 10 Figure 10: Graph complexity vs. computational time in different KGs for mining length-2 rules: The number on the horizontal axis in () denotes the average node degree. The computational time in the vertical axis is the average computational time over all relations in a KG.

( a )

 a Sampling rate vs time (b) Sampling rate vs #Rule (c) Sampling rate vs metrics

Figure 11 :

 11 Figure 11: Sensitivity to sampling rate in the WN18RR KG

Figure 12 :

 12 Figure 12: Sensitivity to top-k: The default parameters setting are used (i.e. max. length=3, decay rate=0.1, sampling rate=0.5) except top-k varies from 2 to 7 with an interval 1.

( a )

 a Decay rate vs #rule (b) Decay rate vs metrics

Figure 13 :

 13 Figure 13: Sensitivity to decay rate: The default parameters setting are used (i.e. max. rule length=3, sampling top-k=5) except decay rates are from {0.02, 0.04, 0.07, 0.1, 0.13, 0.16, 0.2, 0.3}.

Figure 14 :

 14 Figure 14: Sensitivity to maximum rule length: The default parameters setting are used (i.e. decay rate=0.1, sampling rate=0.5, top-k=5) except rule length varies from 2 to 5 with an interval 1.

  Fig 15 shows four such triples with their corresponding paths in the KG and in identified rules. The examples explain which paths help the target triple to be true. For instance, the prediction of the triple (Contact,../film/language,English) (in Fig15a) could be explained as "'Jena Malone' is awarded for the 'Contact' film and the dubbing language of 'Jena Malone' is English." These two facts trigger the target triple, (Contact,../film/language, English) to be predicted as true.

Figure 15 :

 15 Figure 15: A few examples of correctly predicted triples in FB15K-237 KG by embeddingbased method with their triggered paths identified by mined rules. The relation in the KG is longer in length, describing its hierarchy. Due to space constraints, we only include the lower part of the hierarchy and replace the higher parts with dots in describing a relation.

Table 1 :

 1 Summary of notations

	Symbol Meaning	Symbol Meaning
	E	Set of all entities	Θ	Set of all parameters an embedding method
	R	Set of all relations	T	Number of epochs
	S	Set of positive training triples k	Number of sampled negative(s) for a positive
	D	Set of positive test triples	f	Scoring function of an embedding method
	Q	Set of positive triples	G	A bidirectional knowledge graph
	d	Embedding dimension size	H	Head/target relation of a rule
	m	Batch size	B i	i-th body body relation of a rule
	S m	A batch of positive triples	e i	Entity variable of a rule
	S m	A batch of negative triples	r -1

  H is the head/target relation from e 0 to e n and B 1 , B 2 , ...., B n are the sequence of body relations. In the rule body, B i (e i-1 , e i ) is either a relation (i.e. (e i-1 , r i , e i )) or its inverse (i.e. (e i-1 , r -1i , e i )).

	body relations B 1 , B 2 , ...., B n in the following form
	B 1 (e 0 , e 1 ) ∧ B 2 (e 1 , e 2 ) ∧ ...... ∧ B n (e n-1 , e n )-> H(e 0 , e n )	(5)
	where e i is an entity variable,
	The existing
	embedding-based rule mining methods only handle the first type i.e. 'closed-
	path' (Figure 2a) and the rest three types (Figures 2b,2c,2d) are not handled.
	We focus on mining rules that consist of a head relation H and a sequence of

  Algorithm 2: Learn rule: Learning rules for a relation

		Input: Target relation (r), Bidirectional Knowledge graph (G), Triple set (Tr) with r,
		Decay rate (γ) , Sampling rate (β), Top-k
		Output: Rule set
	1 T ′ r ← Randomly sample (|Tr| * β) triples from Tr
	2 foreach (h,r,t)∈ T ′ r do
	3	Paths, Ranks =Extract paths(G,(h,r,t),L)	// Call Algorithm 1 to extract paths
		/* If a path exists then update its info, otherwise add the path to
		PathMetaInfo if it is ranked in top-k */
	4	foreach P∈Paths do
	5	Rule=Transform path to rule(P) // replace entities with literals
	9	else
		/* add a new rule	*/

6 if Rule∈ Rule set then 7 Rule set[Rule].Count← Rule set[Rule].Count + 1 // increment counter 8 Rule set[Rule].Energy← 1 + γ // reset energy to full and additional γ 10 if Ranks[Rule]≤top-k then 11 Rule.Count← 1 12 Rule.Energy← 1 + γ 13 Rule set[Rule]← Rule set ∪ Rule /* Identify the noisy rules */ 14 foreach Rule∈Rule set do 15 Rule.Energy←Rule.Energy -γ 16 if Rule.Energy ≤ 0 & Rule.Count≤ 1 then 17 Rule set=Rule set -Rule // remove the noisy rule /* generate the final rule set by removing potential rules */ 18 foreach Rule∈Rule set do 19 if Rule.Count≤ 1 then 20 Rule set=Rule set -Rule // remove the potential rule

Table 2 :

 2 Scoring functions of KG embedding models: wr is the normal vector of the hyperplane for the relation r, diag(r) is the diagonal matrix for the relation r, and ||.|| 2 represents l 2 norm.

  Table 3 presents characteristics of the used datasets in terms of number of entities, number of relations, number of facts and number of triples in the training, test and validation sets.

Table 3 :

 3 The experimental KG datasets

	KG datasets	#Entity	#Relation	#Facts	#Training	#Validation	#Test
	WN18RR	40,943	11	93,003	86,835	3,034	3,134
	WN18	40,943	18	151,442	141,442	5,000	5,000
	FB15K-237	14,541	237	310,116	272,115	17,535	20,466
	FB15K	14,951	1,345	592,213	483,142	50,000	59,071
	YAGO3-10	113,273	37	1,089,040	1,079,040	5,000	5,000
	Family	3,007	12	28,356	25,517	1,410	1,429
	4.3. Evaluation metrics
	4.3.1. Evaluation metrics for the SNS method

Table 4 :

 4 Link prediction(LP) results: MRR, and Hit@z of different negative sampling(NS) methods. The best and second best metrics are marked in bold and underline faces.

	LP models	NS methods	MRR	WN18RR hit@10 hit@3	hit@1	MRR	WN18 hit@10 hit@3	hit@1
		Random	0.1520	32.27	23.72	0.11	0.3199	79.43	64.25	11.85
	TransH	NSCaching KBGAN	0.1713 0.1708	40.68 40.08	31.43 29.35	0.93 0.10	0.4171 0.4183	88.65 87.34	74.05 73.67	17.48 18.09
		Self-Adv	0.1709	41.18	31.16	0.89	0.4191	89.48	75.84	7.08
		SNS	0.1852 43.04	33.82	1.80	0.448	91.47	79.30	19.28
		Random	0.1918	32.16	23.88	14.22	0.3453	52.82	37.33	25.75
	DistMult	NSCaching KBGAN	0.2262 0.2285	37.37 33.42	29.11 27.23	17.84 17.34	0.3772 0.3791	56.85 57.28	42.18 41.97	29.04 28.39
		Self-Adv	0.2279	36.23	26.34	17.05	0.3940 58.43	41.31	31.29
		SNS	0.2333 37.83	25.12	18.49	0.3931	56.46	42.13	31.38
				FB15K237			FB15K
		Random	0.1988	36.68	22.50	11.50	0.3115	52.88	36.68	19.58
	TransH	NSCaching KBGAN	0.2476 0.2162	40.39 40.58	26.59 23.52	17.33 15.23	0.3926 0.3228	61.22 53.67	44.99 38.34	25.50 20.52
		Self-Adv	0.2350	41.01	26.49	14.73	0.3883	61.09	44.05	25.74
		SNS	0.2514 42.90	29.44	15.18	0.4360 66.72	51.52	30.58
		Random	0.1918	31.82	20.71	12.96	0.2188	33.25	21.84	12.95
	DistMult	NSCaching KBGAN	0.2205 0.2282	34.87 36.23	25.69 27.23	15.72 13.02	0.2327 0.2203	39.89 35.54	27.41 23.12	16.19 15.92
		Self-Adv	0.2400	37.09	25.82	17.34	0.2493	39.80	28.38	18.53
		SNS	0.2471 38.18	26.97	17.80	0.2937 45.62	32.66	20.79
				YAGO3-10			Family
		Random	0.0850	18.96	9.05	1.24	0.3164	88.77	48.67	3.43
	TransH	NSCaching KBGAN	0.1431 0.1467	26.76 26.08	15.97 16.03	7.49 8.34	0.3434 0.3742	90.34 90.21	55.04 57.12	4.65 8.63
		Self-Adv	0.1443	26.46	17.34	9.92	0.3510	89.58	56.36	8.08
		SNS	0.1488 26.72	16.23	8.87	0.4146 92.97	62.39	13.12
		Random	0.0533	10.59	5.44	2.35	0.5002	77.36	60.14	37.45
	DistMult	NSCaching KBGAN	0.0875 14.22 0.0712 13.98	8.86 7.79	5.64 3.19	0.5274 78.55 0.5120 78.01	61.34 60.75	38.07 38.01
		Self-Adv	0.0868	16.04	8.74	5.07	0.5122	78.59	60.95	38.33
		SNS	0.0804	16.72	8.39	4.98	0.5190	79.32	61.02	37.98
	different sampling methods from epoch 10 to 200 with a 10 epochs interval to
	demonstrate how prediction performance varies as the number of training epochs
	grows. SNS has a similar MRR score (approximately 0.02) to other sampling
	methods at the start of epoch 10, with the exception of KBGAN, which has the

Table 5 :

 5 A few examples of sampled negative triples by different sampling methods in the WN18RR dataset. The entity in boldface is the one resulting from entity corruption.

	Positive triple	Negative triples by SNS
		(point,derivationally related form,clinch)
		(carelessness,verb group,play)
		(worry,hypernym,announce)
		(akee,member meronym,tree)
		(pakistan,has part,amazon)
		Negative triples by NSCaching
	1. (point,derivationally related form,arrow) (rio grande,derivationally related form,point)
	2. (meet,verb group,play)	(meet,verb group,wheeler peak)
	3. (worry,hypernym,mind)	(worry,hypernym,seal)
	4. (forest,member meronym,tree)	(disjoin,member meronym,tree)
	5. (pakistan,has part,tirich mir)	(pakistan,has part,malevolence)
		Negative triples by KBGAN
		(point,derivationally related form,wilt)
		(frequency,verb group,play)
		(worry,hypernym,traversal)
		(pan,member meronym,tree)
		(pakistan,has part,chute)
		Negative triples by Uniform-random
		(point,derivationally related form,colored)
		(cranium,verb group,play)
		(bladder fern,hypernym,mind)
		(forest,member meronym,barrow)
		(pakistan,has part,deposit)
		Negative triples by Self-Adv
		(roping,derivationally related form,arrow)
		(meet,verb group,convenience food)
		(worry,hypernym,behave)
		(forest,member meronym,bryaceae)
		(theism, has part, tirich mir)
	method. The metrics of the 11 relations in the WN18RR dataset are shown
	in Table 6. We see that two relations (hypernym, derivationally related form)
	cover about 75% of the total facts in the training set. From the table, the

Table 6 :

 6 Relation-wise performance in WN18RR dataset: MRR, MR and Hit@10 percentage. Number beside a relation denotes the percentage of facts covered by the relation in the test set. The best metrics for each relation are highlighted in bold face.

	Relations	SNS	KBGAN	NSCaching	Random
		MRR	hit@10	MRR	hit@10 MRR hit@10	MRR	hit@10
	hypernym(39.92%)	0.092	17.92	0.04	8.18	0.0701	14.26	0.0357	11.28
	derivationally related form(34.27%) 0.3971	95.44	0.4051	94.41	0.3899 95.53	0.3755	73.69
	instance hypernym(3.89%)	0.0718 15.57	0.0452	12.3	0.0439	9.84	0.0461	11.48
	also see(1.79%)	0.0978	26.79	0.261	71.43 0.0903	21.43	0.0766	25.0
	member meronym(8.07%)	0.023	6.32	0.0218	5.93	0.0134	3.56	0.012	4.74
	synset domain topic of(3.64%)	0.0412	8.77	0.0465 14.04 0.0375	7.89	0.0374	7.02
	has part(5.49%)	0.0336	8.14	0.0243	8.14	0.0197	4.65	0.019	3.49
	member of domain usage(0.77%)	0.0021	0.00	0.0015	0	0.0029	0.00	0.0093	4.17
	member of domain region(0.83%)	0.0046	0.00	0.004	0.00	0.0026	0.00	0.0034	0.0
	verb group(1.24%)	0.1998 69.23 0.3571 97.44 0.1497	48.72	0.1888	61.54
	similar to(0.09%)	0.0001	0.00	0.2407 66.67 0.0002	0.00	0.0008	0.00

Table 9 :

 9 Relation-wise performance of mined length-2 rules in the WN18RR dataset: The embeddings are learned by DistMult with SNS sampling. The parameters for rule mining methods are set to default values except the maximum rule length is set to 2. Relations with recall scores above the average(0.184) are marked in boldface.

	Relations	#Rule Recall	HC	SC
	hypernym	9	0.089 0.045 0.009
	derivationally related form	12	0.224 0.087 0.019
	instance hypernym	5	0.197 0.017 0.028
	also see	7	0.214 0.048 0.040
	member meronym	6	0.099 0.013 0.016
	synset domain topic of	15	0.447 0.143 0.032
	has part	10	0.238 0.057 0.023
	member of domain usage	2	0.042 0.131 0.043
	member of domain region	2	0.00	0.142 0.015
	verb group	8	0.487 0.006 0.087
	similar to	0	0.000	0.00	0.00
	(a) Prediction performance			Rule quality

Table 10 :

 10 Top-5 rules of length-3 for the 'father' relationship: ranks are computed in decreasing order of rule support values.

	Rank	Rules

https://gitlab.inria.fr/kislam/kglp

Prediction performance:

We compute the prediction performance of our rule mining method based on learned embeddings by our SNS and random sampling strategies. Table 7 tabulates the recall scores with their average, minimum and maximum numbers for Family, WN18RR and FB15K-237 KGs. And Table 8 tabulates the quality metrics scores with their average, minimum and maximum numbers for the same datasets. Overall, our the proposed rule mining method mines more rules when embeddings are learned DistMult with SNS than DistMult with random sampling. But, we see no significant different between the performance scores of mined rule sets. We see that the average number of mined rules per relation is highest for the densest FB15K-237 and lowest for the sparest WN18RR KGs. This is expected because the higher average node degree of a graph leads to generating more paths between pair of nodes and thus more rules to describe the relationship between the pair of nodes. The high number of rules for Family and FB15K-237 KGs give high recall scores in these two KGs. Looking at the minimum recall scores, we see the datasets except Family give a minimum scores of 0.0. Investigating the relation-wise recall, we find that the quality of learned rules for a relation with low number of training set is very low and even no rule is generated for few such relations (e.g. similar to relation in WN18RR, /baseball/.../baseball team stats/season in FB15K-237). This situation affects the performance scores as well as the overall ruleset quality of a relation. In Table 8, we see the worst rule quality metrics for WN18RR. The average node degree of WN18RR is low which causes less number of paths between two entities to generate rules. This is most possible reason is that our method mines lowquality length-2 rules for WN18RR.

We try to investigate how the quality of embeddings affects the quality of mined ruleset as well as the prediction performance in WN18RR datasets. We 9. The rules for a relation are ranked in decreasing order of their support scores. As lowranked rules are not considered, triggering rules for a few triples will be missing.

As a result, it is seen in Figure 9a that the recall scores for both sampling methods drop as the number of rules drops. In contrast, as low-quality rules are removed, the average rule quality scores in Figure 9b improve.