Improved Knowledge Graph Embedding using Background Taxonomic Information

Knowledge graphs are used to represent relational information in terms of triples. To enable learning about domains, embedding models, such as tensor factorization models, can be used to make predictions of new triples. Often there is background taxonomic information (in terms of subclasses and subproperties) that should also be taken into account. We show that existing fully expressive (a.k.a. universal) models cannot provably respect subclass and subproperty information. We show that minimal modifications to an existing knowledge graph completion method enables injection of taxonomic information. Moreover, we prove that our model is fully expressive, assuming a lower-bound on the size of the embeddings. Experimental results on public knowledge graphs show that despite its simplicity our approach is surprisingly effective. The AI community has long noticed the importance of structure in data. While traditional machine learning techniques have been mostly focused on feature-based representations, the primary form of data in the subfield of Statistical Relational AI (STARAI) (Getoor and Taskar, 2007; Raedt et al., 2016) is in the form of entities and relationships among them. Such entity-relationships are often in the form of (head, relationship, tail) triples, which can also be expressed in the form of a graph, with nodes as entities and labeled directed edges as relationships among entities. Predicting the existence, identity, and attributes of entities and their relationships are among the main goals of StaRAI. Knowledge Graphs (KGs) are graph structured knowledge bases that store facts about the world. A large number of KGs have been created such as NELL (Carlson et al., 2010), FREEBASE (Bollacker et al., 2008), and Google Knowledge Vault (Dong et al., 2014). These KGs have applications in several fields including natural language processing, search, automatic question answering and recommendation systems. Since accessing and storing all the facts in the world is difficult, KGs are incomplete. The goal of link prediction for KGs – a.k.a. KG completion – is to predict the unknown links or relationships in a KG based on the existing ones. This often amounts to infer (the probability of) new triples from the existing triples.  A common approach to apply machine learning to symbolic data, such as text, graph and entity-relationships, is through embeddings. Word, sentence and paragraph embeddings (Mikolov et al., 2013; Pennington, Socher, and Manning, 2014), which vectorize words, sentences and paragraphs using context information, are widely used in a variety of natural language processing tasks from syntactic parsing to sentiment analysis. Graph embeddings (Hoff, Raftery, and Handcock, 2002; Grover and Leskovec, 2016; Perozzi, Al-Rfou, and Skiena, 2014) are used in social network analysis for link prediction and community detection. In relational learning, embeddings for entities and relationships are used to generalize from existing data. These embeddings are often formulated in terms of tensor factorization (Nickel, Tresp, and Kriegel, 2012; Bordes et al., 2013; Trouillon et al., 2016; Kazemi and Poole, 2018c). Here, the embeddings are learned such that their interaction through (tensor-)products best predicts the (probability of the) existence of the observed triples; see (Nguyen, 2017; Wang et al., 2017) for details and discussion. Tensor factorization methods have been very successful, yet they rely on a large number of annotated triples to learn useful representations. There is often other information in ontologies which specifies the meaning of the symbols used in a knowledge base. One type of ontological information is represented in a hierarchical structure called a taxonomy. For example, a knowledge base might contain information that DJTrump, whose name is “Donald Trump” is a president, but may not contain information that he is a person, a mammal and an animal, because these are implied by taxonomic knowledge. Being told that mammals are chordates, lets us conclude that DJTrump is also a chordate, without needing to have triples specifying this about multiple mammals. We could also have information about subproperties, such as that being president is a subproperty of “managing”, which in turn is a subproperty of “interacts with”. This paper is about combining taxonomic information in the form of subclass and subproperty (e.g., managing implies interaction) into relational embedding models. We show that existing factorization models that are fully expressive cannot reflect such constraints for all legal entity embeddings. We propose a model that is provably fully expressive and can represent such taxonomic information, and evaluate its performance on real-world datasets. ar X iv :1 81 2. 03 23 5v 1 [ cs .L G ] 7 D ec 2 01 8 Factorization and Embedding Let E represent the set of entities and R represent the set of relations. Let W be a set of triples (h, r, t) that are true in the world, where h, t ∈ E are head and tail, and r ∈ R is the relation in the triple. We use W to represent the triples that are false – i.e., W ≐ {(h, r, t) ∈ E × R × E ∣ (h, r, t) ∉ W}. An example of a triple in W can be (Paris, CapitalCityOfCountry, France) and an example of a triple in W can be (Paris, CapitalCityOfCountry, Germany). A KG K ⊆ W is a subset of all the facts. The problem of the KG completion is to infer W from its subset KG. There exists a variety of methods for KG completion. Here, we consider embedding methods and in particular using tensor-factorization. For a broader review of the existing KG completion that can use background information see Related Work.  An embedding is a function from an entity or a relation to a vector (or sometimes higher order tensors) over a field. We use bold lower-case for vectors – that is s ∈ R is an embedding of an entity and r ∈ R is an embedding of a relation.  It is common to have structure over the symbols used in the triples, see (e.g., Shoham, 2016). The Ontology Web Language (OWL) (Hitzler et al., 2012) defines (among many other meta-relations) subproperties and subclasses, where p1 is a subproperty of p2 if ∀x, y ∶ (x, p1, y)→ (x, p2, y), that is whenever p1 is true, p2 is also true. Classes can be defined either as a set with a class assertion (often called “type”) between an entity and a class, e.g., saying x is in class C using (x, type,C) or in terms of the characteristic function of the class, a function that is true of element of the class. If c is the characteristic function of class C, then x is in class c is written (x, c, true). For representations that treat entities and properties symmetrically, the two ways to define classes are essentially the same. C1 is a subclass of C2 if every entity in class C1 is in class C2, that is, ∀x ∶ (x, type,C1) → (x, type,C2) or ∀x ∶ (x, c1, true) → (x, c2, true) . If we treat true as an entity, then subclass can be seen as a special case of subproperty. For the rest of the paper we will refer to subsumption in terms of subproperty (and so also of subclass). A non-trivial subsumption is one which is not symmetric; p1 is a subproperty of p2 and there is some relations that is true of p1 that is not true of p2. We want the subsumption to be over all possible entities; those entities that have a legal embedding according to the representation used, not just those we know exist. Let E∗ be the set of all possible entities with a legal embedding according to the representation used. Tensor factorization: For KG completion a tensor factorization defines a function μ ∶ R ×R ×R → [0,1] that takes the embeddings h, r and t of a triple (h, r, t) as input, and generates a prediction, e.g., a probability, of the triple being true (h, r, t) ∈ W . In particular, μ is often a nonlinearity applied to a multi-linear function of h, r, t. The family of methods that we study uses the following multilinear form: Let x, y, and z be vectors of length k. Define ⟨x,y,z⟩ to be the sum of their element-wise product, namely