Open-World Knowledge Graph Completion

Knowledge Graphs (KGs) have been applied to many tasks including Web search, link prediction, recommendation, natural language processing, and entity linking. However, most KGs are far from complete and are growing at a rapid pace. To address these problems, Knowledge Graph Completion (KGC) has been proposed to improve KGs by filling in its missing connections. Unlike existing methods which hold a closed-world assumption, i.e., where KGs are fixed and new entities cannot be easily added, in the present work we relax this assumption and propose a new open-world KGC task. As a first attempt to solve this task we introduce an openworld KGC model called ConMask. This model learns embeddings of the entity’s name and parts of its text-description to connect unseen entities to the KG. To mitigate the presence of noisy text descriptions, ConMask uses a relationshipdependent content masking to extract relevant snippets and then trains a fully convolutional neural network to fuse the extracted snippets with entities in the KG. Experiments on large data sets, both old and new, show that ConMask performs well in the open-world KGC task and even outperforms existing KGC models on the standard closed-world KGC task.  Knowledge Graphs (KGs) are a special type of information network that represents knowledge using RDF-style triples 〈h, r, t〉, where h represents some head entity and r represents some relationship that connects h to some tail entity t. In this formalism a statement like “Springfield is the capital of Illinois” can be represented as 〈Springfield, capitalOf, Illinois〉. Recently, a variety of KGs, such as DBPedia (Lehmann et al. 2015), and ConceptNet (Speer, Chin, and Havasi 2017), have been curated in the service of fact checking (Shi and Weninger 2016), question answering (Lukovnikov et al. 2017), entity linking (Hachey et al. 2013), and for many other tasks (Nickel et al. 2016). Despite their usefulness and popularity, KGs are often noisy and incomplete. For example, DBPedia, which is generated from Wikipedia’s infoboxes, contains 4.6 million entities, but half of these entities contain less than 5 relationships. Based on this observation, researchers aim to improve the accuracy and reliability of KGs by predicting the existence Copyright c  (or probability) of relationships. This task is often called Knowledge Graph Completion (KGC). Continuing the example from above, suppose the relationship capitalOf is missing between Indianapolis and Indiana; the KGC task might predict this missing relationship based on the topological similarity between this part of the KG and the part containing Springfield and Illinois. Progress in vector embeddings originating with word2vec has produced major advancements in the KGC task. Typical embedding-based KGC algorithms like TransE (Bordes et al. 2013) and others learn lowdimensional representations (i.e., embeddings) for entities and relationships using topological features. These models are able to predict the existence of missing relationships thereby “completing” the KG. Existing KGC models implicitly operate under the Closed-World Assumption (Reiter 1978) in which all entities and relationships in the KG cannot be changed – only discovered. We formally define the Closed-word KGC task as follows: Definition 1 Given an incomplete Knowledge Graph G = (E,R,T), where E, R, and T are the entity set, relationship set, and triple set respectively, Closed-World Knowledge Graph Completion completes G by finding a set of missing triples T = {〈h, r, t〉|h ∈ E, r ∈ R, t ∈ E, 〈h, r, t〉 / ∈ T} in the incomplete Knowledge Graph G. Closed-world KGC models heavily rely on the connectivity of the existing KG and are best able to predict relationships between existing, well-connected entities. Unfortunately, because of their strict reliance on the connectivity of the existing KG, closed-world KGC models are unable to predict the relationships of poorly connected or new entities. Therefore, we assess that closed-world KGC is most suitable for fixed or slowly evolving KGs. However, most real-world KGs evolve quickly with new entities and relationships being added by the minute. For example, in the 6 months between DBPedia’s October 2015 release and its April 2016 release 36, 340 new English entities were added – a rate of 200 new entities per day. Recall that DBPedia merely tracks changes to Wikipedia infoboxes, so these updates do not include newly added articles without valid infobox data. Because of the accelerated growth of online information, repeatedly re-training closed-world models every day (or hour) has become impractical. In the present work we borrow the idea of openworld assumption from probabilistic database literature (Ceylan, Darwiche, and Van den Broeck 2016) and relax the closed-world assumption to develop an Open-World Knowledge Graph Completion model capable of predicting relationships involving unseen entities or those entities that have only a few connections. Formally we define the openworld KGC task as follows: Definition 2 Given an incomplete Knowledge Graph G = (E,R,T), where E, R, and T are the entity set, relationship set, and triple set respectively, Open-World Knowledge Graph Completion completes G by finding a set of missing triples T = {〈h, r, t〉|〈h, r, t〉 / ∈ T, h ∈ E, t ∈ E, r ∈ R} in the incomplete Knowledge Graph G where E is an entity superset. In Defn. 2 we relax the constraint on the triple set T so that triples in T can contain entities that are absent from the original entity set E. Closed-world KGC models learn entity and relationship embedding vectors by updating an initially random vector based on the KG’s topology. Therefore, any triple 〈h, r, t〉 ∈ T ′ such that h / ∈ E or t / ∈ E will only ever be represented by its initial random vector because its absence does not permit updates from any inference function. In order to predict the missing connections for unseen entities, it is necessary to develop alternative features to replace the topological features used by closed-world models. Text content is a natural substitute for the missing topological features of disconnected or newly added entities. Indeed, most KGs such as FreeBase (Bollacker et al. 2008), DBPedia (Lehmann et al. 2015), and SemMedDB (Kilicoglu et al. 2012) were either directly extracted from (Lin et al. 2016; Ji and Grishman 2011), or are built in parallel to some underlying textual descriptions. However, open-world KGC differs from the standard information extraction task because 1) Rather than extracting triples from a large text corpus, the goal of open-world KGC is to discover missing relationships; and 2) Rather than a pipeline of independent subtasks like Entity Linking (Francis-Landau, Durrett, and Klein 2016) and Slotfilling (Liu and Lane 2016), etc., open-world KGC is a holistic task that operates as a single model. Although it may seem intuitive to simply include an entity’s description into an existing KGC model, we find that learning useful vector embeddings from unstructured text is much more challenging than learning topology-embeddings as in the closed-world task. First, in closed-world KGC models, each entity will have a unique embedding, which is learned from its directly connected neighbors; whereas open-world KGC models must fuse entity embeddings with the word embeddings of the entity’s description. These word embeddings must be updated by entities sharing the same words regardless of their connectivity status. Second, because of the inclusion of unstructured content, open-world models are likely to include noisy or redundant information. With respect to these challenges, the present work makes the following contributions: 1. We describe an open-world KGC model called ConMask that uses relationship-dependent content masking to reduce noise in the given entity description and uses fully convolutional neural networks (FCN) to fuse related text into a relationship-dependent entity embedding. 2. We release two new Knowledge Graph Completion data sets constructed from DBPedia and Wikipedia for use in closed-world and open-world KGC evaluation. Before introduce the ConMask model, we first present preliminary material by describing relevant KGC models. Then we describe the methodology, data sets, and a robust case study of closed-world and open-world KGC tasks. Finally, we draw conclusions and offer suggestions for future work. Closed-World Knowledge Graph  A variety of models have been developed to solve the closedworld KGC task. The most fundamental and widely used model is a translation-based Representation Learning (RL) model called TransE (Bordes et al. 2013). TransE assumes there exists a simple function that can translate the embedding of the head entity to the embedding of some tail entity via some relationship: