To train knowledge graph embedding models, negative training examples have to be generated arti cially. A few attempts were already made in the past to improve negative sampling by exploiting schematic domain and range constraints. However, such approaches did not exploit the full range of schematic axioms. To remedy this situation, we introduce a new type of conditional constraints based on OWL restrictions. Additionally, we investigate two alternative views on how constraints might be used to generate false triples|an open world view and a closed world view|and perform empirical evaluations for both of them. Our results indicate that in the closed world view, even a limited number of OWL constraints can improve link prediction performance. Also, for regular constraints, both open world and closed world views offer signi cant improvements with respect to baseline negative sampling techniques.
With the advent of Big Data, dealing with data heterogeneity has become a
pressing issue. By linking data with its contextual characteristics, knowledge
graphs (KGs) are able to consolidate multiple sources with diverse schemas,
making them queryable through a uniform interface. When data is made
available in this fashion, it becomes open to consumption by all manner of intelligent
agents. The Semantic Web (SW), which includes most of the larger, publicly
available KGs, such as DBpedia, YAGO, and WordNet in its Linked Open Data
(LOD) cloud1, was developed with precisely this vision of intelligent, automatic
consumption [
Two primary alternatives exist to decrease the amount of missing information
inside KGs. On the one hand, logic-based reasoners (inference engines) can be
used to infer new facts inside the KG via deductive entailment [
Concerning statistical approaches, the family of latent feature models
assumes that the existential values of all potential facts inside the KG are
conditionally independent given certain global latent features. This class of models
has also been called the class of KG embedding techniques [
When KG embeddings are used for graph completion this is called link prediction. To perform link prediction, embedding models require a sense of falseness. Most KGs adhere to the SW's open world assumption (OWA), which states that any uncertainty with respect to the truth of a fact does not imply its falsity. Per this assumption, except where logical contradiction is concerned, or negation is explicitly invoked, conclusively negative facts do not exist. Yet, to gain insight into the boundary between fact and ction, embedding models need to be supplied with plausible counterfactuals. The process by which these are generated is called negative sampling.
Many negative sampling strategies have built on the standard approach involving the random corruption of positive examples. A few attempts were even made to exploit the constraints inside the KG to minimise the number of useless negatives. However, these attempts focused on the relation-speci c RDFS domain and range constraints. Our own work builds on this by exploring the possibility of exploiting conditional constraints based on OWL restrictions. Specifically, our contributions are the following: { We provide closed-world interpretations of open world OWL restrictions and integrate these into a negative sampling scheme to improve link prediction performance. { We contrast an open world interpretation of constraint-based negative sampling with a closed world interpretation and suggest a way to modulate between them. { We evaluate our proposed enhancements on two datasets (AIFB and MU
TAG) that come supplied with elaborate schemas. 2
The most basic form of negative sampling takes a hard-line stance on the closed
world assumption (CWA): All triples not observed to be true are false. Because
the KG is incomplete, such an assumption is always necessarily incorrect|and
therefore ine ective. Better alternatives are to perturb existing triples (by
replacing either the head or the tail with another entity) or to assume a locally
closed world in which any valid triple entails a whole set of false triples with
the same subject and relationship but with di erent objects [
Various extensions have been proposed to improve on this basic
perturbation scheme. The most basic of these was suggested by Bordes et al. when they
introduced their TransE embedding model: using so-called ltered negative
samples [
We conclude by mentioning a few approaches that tried to enhance negative
sampling speci cally by exploiting type information [
To perform graph completion, we focus on link prediction. The objective of
link prediction is to estimate the degree of certainty with which an arbitrary
link between two nodes might be said to exist. For the formal speci cation of
the problem we follow Nickel et al. [
8i; k; j; (ei; rk; ej ) 2 O =) ei 2= C; ej 2= C 8(ei; rk; ej ) 2 O; (ei; rk; ej ) 2 O+ 8(ei; rk; ej ) 2 O; (ei; rk; ej ) 2 O () yikj = 1 =) yikj = 0 (1) (2) (3) (4) (5) 4
In this section we rst discuss how constraints might be derived from ontological axioms de ned within an open world view of knowledge. Once we have established how we might derive constraints in general, we will move on to the construction of conditional constraints based on OWL restrictions. Enforcing constraints can itself happen in an open or closed world fashion. Both of these alternatives will be discussed together with a way to modulate between them. 4.1
As stated in section 1, the SW assumes an open world view of knowledge. The
OWL language guide speci cally states that \...OWL makes an open world
assumption" and that \[new] information can be contradictory, but facts and
entailments can only be added, never deleted [
However, given the OWA, these \constraints" do not rule out that the
rdfs:range of rdf:type could later be expanded to include rdfs:Resource. Indeed,
rdfs:domain and rdfs:range are not actually used for de nitive exclusions of certain
types with respect to relations, but rather serve as a vehicle for type inference.
Rather than constraining subjects or objects of a certain relationship to certain
types, such \constraints" are used to infer additional type information for these
subjects or objects. To derive integrity constraints from logical axioms, an
articial closed world interpretation must be imposed. In fact, one can rst make
use of the axiomatic interpretation to expand the original ontology. As stated
in section 1, deductive reasoning should be considered complementary to SRL
for link prediction. Making use of the standard supra-domain ontologies2;3;4,
one can compute the deductive closure of any given domain ontology. Once the
ontology has been expanded according to the OWA's internal logic, one can
impose a restrictive interpretation on each logical axiom within the context of
a negative sampling scheme. Indeed, given that it may be assumed that each
entity's type declarations have been expanded beforehand according to what is
already presupposed to be terminologically valid|according to the KG's TBox
or domain ontology|whenever one encounters a triple where the participating
entities' types are not axiomatically consistent, one can meaningfully say this
triple must be invalid. In a sense, when imposing such a restrictive view, we are
pursuing the same route as SHACL, which was introduced explicitly to address
the practical unwieldiness of OWL's open world semantics [
The domain and range constraints already exploited by previous approaches can
easily be derived from their open world formulations [
Formally, one can de ne the domain and range axioms as follows:
8k 2 K; 8c 2 C; 8(rk; rdfs:domain; c) 2 TBox =)
8k 2 K; 8c 2 C; 8(rk; rdfs:range; c) 2 TBox =)
8i; j 2 I; (ei; rk; ej ) =) (ei; a; c)
8i; j 2 I; (ei; rk; ej ) =) (ej ; a; c)
(6)
(7)
2 http://www.w3.org/1999/02/22-rdf-syntax-ns(rdf)
3 http://www.w3.org/2000/01/rdf-schema (rdfs)
4 http://www.w3.org/2002/07/owl (owl)
where K = f1 : : : Nrg, I = f1 : : : Neg, and the relationship a is short for rdf:type.
The corresponding integrity constraints can be derived as follows:
8i; j 2 I; (ei; a; c) =) (ei; rk; ej ) is valid
8i; j 2 I; (ej ; a; c) =) (ei; rk; ej ) is valid
(8)
(9)
Drawing inspiration from SHACL, we note that \[property restrictions] can only
be [de ned] within the context of an owl:Restriction... [where] [t]he
owl:onProperty element indicates the restricted property [
To clarify, owl:allValuesFrom and owl:someValuesFrom are local to their containing class de nitions, meaning that their application is contingent on the subject being of the correct type (the type corresponding to the restricted class). For these restrictions, the axioms can formally be de ned as follows: 8k 2 K; 8c; c0 2 C; 8(b(c; rk); owl:onProperty; rk) 2 TBox &
8(b(c; rk); owl:allValuesFrom; c0) 2 TBox =) 8i; j 2 I; (ei; a; c) =) (ei; rk; ej ) =) (ej ; a; c0) 8k 2 K; 8c; c0 2 C; 8(b(c; rk); owl:onProperty; rk) 2 TBox &
8(b(c; rk); owl:someValuesFrom; c0) 2 TBox =) 8i 2 I; 9j 2 I; (ei; a; c) =) (ei; rk; ej ) & (ej ; a; c0) (10) (11) where b(c; rk) projects a restricted class c 2 C onto the blank node representing its restriction for relation rk. The corresponding integrity constraints are: 8k 2 K; 8c; c0 2 C; 8(b(c; rk); owl:onProperty; rk) 2 TBox & 8(b(c; rk); owl:allValuesFrom; c0) 2 TBox
=) 8i; j 2 I; (ei; a; c) =) (ej ; a; c0) 8k 2 K; 8c; c0 2 C; 8(b(c; rk); owl:onProperty; rk) 2 TBox &
8(b(c; rk); owl:someValuesFrom; c0) 2 TBox =) 8i 2 I; 9j 2 I; (ei; rk; ej ) & (ej ; a; c0) =) (ei; a; c) =) (ei; rk; ej ) is valid (12) =) (ei; rk; ej ) is valid (13) Interpretations Based on these constraints, one can assume two alternative interpretations with respect to negative sampling. On the one hand, one can make use of an open world interpretation, where O contains only invalid triples (i.e. triples that do not satisfy the constraints), while on the other, a closed world interpretation can be imposed, where O contains only valid triples (i.e. triples that do satisfy the constraints).
In the prior case, we know that none of the negative examples will ever appear in the test set. Under this interpretation, every negative example is truly false; no possible facts are excluded except when they are nonsensical. It is no coincidence that this interpretation aligns best with the SW's OWA, where falseness is impossible except where nonsense is concerned.
In the latter case, we are in fact eliminating useless examples from O , on the assumption that nonsensical counterfactuals introduce needless model complexity because they only account for noise. Such facts are not useful for deriving a decision boundary between what exists and what does not. The problem with this interpretation is that it does permit O to be populated by false negatives.
In fact, both interpretations have merit, and it might be interesting to nd a balance between them. To this end, we suggest making use of an additional hyperparameter to tune the reject rate of an invalid triple. 5
To evaluate the various types of constraints and contrast them with one another,
TransE is used as a base model [
For our evaluations, we make use of the AIFB5 and MUTAG6 datasets, the prior of which describes info related to research sta , institutions, and publications, and the latter of which contains details on potentially carcinogenic 5 http://data.dws.informatik.uni-mannheim.de/rmlod/LOD\_ML\_Datasets/ data/datasets/RDF\_Datasets/AIFB/ 6 http://data.dws.informatik.uni-mannheim.de/rmlod/LOD\_ML\_Datasets/ data/datasets/RDF\_Datasets/MUTAG/ molecules. While typically used for entity classi cation rather than link prediction, these datasets have nonetheless been selected for their favourable characteristics. In particular, for AIFB we had access to 152 allValuesFrom OWL restrictions, and for MUTAG we were able to make use of 5087 RDFS constraints. For both of them, a 90-10 train-test split and a 90-10 train-valid split was performed. As a result, for AIFB, the training set contains 19916 entities, the valid set 2213 entities, and the test set 2459 entities. For MUTAG, the training set contains 41999 entities, the valid set 4667 entities, and the test set 5185 entities. For all experiments, the following hyperparameters were used for TransE: batch size 128, embedding size 100, number of epochs 100, learning rate 0.001, margin 1. We conducted separate experiments for each of the constraint interpretations and for di erent values of the negative ratio hyperparameter, which is used to tune the number of the negative samples generated per positive sample. The metrics used to evaluate performance are Hits@10, Mean Rank (MR), and Mean Reciprocal Rank (MRR), which are standard when evaluating link prediction performance.
The test results for AIFB can be found in Table 1, while those for MUTAG can be found in Table 2. Note that for each setting, we include the number of distinct false negatives generated by the sampling method.
Setting no constraints no constraints open world constraints open world constraints closed world constraints closed world constraints Looking at the results, a few things immediately become clear: For both datasets, adding closed world constraints o ers clear bene ts. In AIFB, the OWL restrictions are able to improve the Hits@10 and the MRR when the negative ratio is kept at the default value of 1. In MUTAG, the RDFS domain and range constraints o er signi cant improvements with respect to every metric for negative ratios of both 1 and 5. The discrepancy between the results achieved for AIFB and MUTAG can be explained in terms of the number of false negatives encountered. For MUTAG, this number remains almost completely invariant when constraints are introduced and is furthermore almost negligible with respect to the size of the test set. Conversely, for AIFB, there is a signi cant increase in the number of sampled false negatives when introducing constraints. Interestingly enough, despite the increase in false negatives, for a negative ratio of 1, constraints did improve performance. For now, further investigation is required to determine the exact causes behind these discrepancies: likely, they are caused either by the conditional constraints themselves, or by the speci c conditions (e.g. size, connectivity) of the AIFB dataset.
Interestingly, the open world constraints do seem to o er competitive results in certain cases. Rather than simply introducing unnecessary noise, for RDFS constraints (cfr. MUTAG), when the negative ratio is set to one the lower number of false negatives appears to improve performance. For the conditional constraints, however, this is not the case, mainly because of the low number of available constraints, which is unable to signi cantly diminish the number of false negatives. A hybrid approach making use of the suggested rejection parameter might be able to balance the bene ts and drawbacks of both approaches. Finally, due to the complexity and sparsity of the conditional constraints, running the OWA for larger negative ratios was no longer computationally feasible. This problem seems inherent to the OWA when few constraints are available. 7
In this research paper we provided a thorough justi cation for the derivation of integrity constraints from logical axioms. We supplied formal de nitions for each of the types of constraints used during negative sampling. Furthermore, we introduced a new form of conditional constraints based on OWL restrictions and laid out two opposing views on how constraints might be applied to improve negative sampling. We then evaluated these constraints under the alternative interpretations, while also verifying the e ect of the negative sampling ratio. In the future we would like to take this research much further. First, we would like to systematically contrast the e ect of RDFS constraints with those of OWL restrictions. To this end, we will perform a (partial) conversion from the prior to the latter and vice versa within a given dataset. Second, we would like to empirically validate the e ect of adding a rejection hyperparameter. Third, we would like to investigate the e ect of these strategies on other embedding techniques besides TransE. Finally, we would like to investigate the possibility of using constraints to combat noise in the training set. All of these possibilities are currently being evaluated.
Acknowledgment: This research was funded by the imec.ICON RADIANCE project, co-funded by VLAIO, imec, Skyline Communications, Barco and ML6.