Abstract Knowledge graph completion is the task of predicting correct facts that can be expressed by the vocabulary of a given knowledge graph, which are not explicitly stated in that graph. Broadly, there are two main approaches for solving the knowledge graph completion problem. Sub-symbolic approaches embed the nodes and/or edges of a given graph into a low-dimensional vector space and use a scoring function to determine the plausibility of a given fact. Symbolic approaches learn a model that remains within the primary representation of the given knowledge graph. Rule-based approaches are well-known examples. One such approach is AnyBURL. It works by sampling random paths, which are generalized into Horn rules. Previously published results show that the prediction quality of AnyBURL is close to current state of the art with the additional benefit of offering an explanation for a predicted fact. In this paper, we propose several improvements and extensions of AnyBURL. In particular, we focus on AnyBURL’s capability to be successfully applied to large and very large datasets. Overall, we propose four separate extensions: (i) We add to each rule a set of pairwise inequality constraints which enforces that different variables cannot be grounded by the same entities, which results into more appropriate confidence estimations. (ii) We introduce reinforcement learning to guide path sampling in order to use available computational resources more efficiently. (iii) We propose an efficient sampling strategy to approximate the confidence of a rule instead of computing its exact value. (iv) We develop a new multithreaded AnyBURL, which incorporates all previously mentioned modifications. In an experimental study, we show that our approach outperforms both symbolic and sub-symbolic approaches in large-scale knowledge graph completion. It has a higher prediction quality and requires significantly less time and computational resources.

Including temporal scopes of facts in knowledge graph embedding (KGE) presents significant opportunities for improving the resulting embeddings, and consequently for increased performance in downstream applications. Yet, little research effort has focussed on this area and much of the carried out research reports only marginally improved results compared to models trained without temporal scopes (static models). Furthermore, rather than leveraging existing work on static models, they introduce new models specific to temporal knowledge graphs. We propose a novel perspective that takes advantage of the power of existing static embedding models by focussing effort on manipulating the data instead. Our method, SPLIME, draws inspiration from the field of signal processing and early work in graph embedding. We show that SPLIME competes with or outperforms the current state of the art in temporal KGE. Additionally, we uncover issues with the procedure currently used to assess the performance of static models on temporal graphs and introduce two ways to counteract them.

We study temporal knowledge graph completion by using tensor decomposition. In particular, we use Candecomp/Parafac decomposition to factorize a given four dimensional sparse representation of a temporal knowledge graph into rank-one tensors that correspond to entities (subject and object), relations and timestamps. Using the factorized tensors, we can perform link and timestamp prediction. We compared our approach against the state of the art and found out that we are highly competitive. We report our preliminary experimental results on 5 different datasets.

Acknowledging the dynamic nature of knowledge graphs, the problem of learning temporal knowledge graph embeddings has recently gained attention. Essentially, the goal is to learn vector representation for the nodes and edges of a knowledge graph taking time into account. These representations must preserve certain properties of the original graph, so as to allow not only classification or clustering tasks, as for classical graph embeddings, but also approximate time-dependent query answering or link predictions over knowledge graphs. For instance, "who was the leader of Germany in 1994?'' or "when was Bonn the capital of Germany?''

Several probabilistic extensions of description logic languages have been proposed and thoroughly studied. However, their practical use has been hampered by intractability of various reasoning tasks. While present-day knowledge bases (KBs) contain millions of instances and thousands of axioms, most state-of-the-art reasoners are capable of handling small scale KBs with thousands of instances. Thus, recent research has focused on leveraging the structure of KBs and queries in order to speed up inference runtime. However, these efforts have not been satisfactory in providing reasoners that are suitable for practical use in large scale KBs. In this study, we aim to tackle this challenging problem. In doing so, we use a probabilistic extension of OWL RL (called PRORL) as a modeling language and exploit graph neighborhoods (of undirected graphical models) for efficient approximate probabilistic inference. We show that subgraph extraction based inference is much faster and has comparable accuracy to full graph inference. We perform several experiments, in order to support our claim, over a NELL KB containing millions of instances and thousands of axioms. Furthermore, we propose a novel graph-based algorithm to automatically partition inferences rules based on their structure for efficient parallel inference.

We propose an anytime bottom-up technique for learning logical rules from large knowledge graphs. We apply the learned rules to predict candidates in the context of knowledge graph completion. Our approach outperforms other rule-based approaches and it is competitive with current state of the art, which is based on latent representations. Besides, our approach is significantly faster, requires less computational resources, and yields an explanation in terms of the rules that propose a candidate.

The emergence of open information extraction as a tool for constructing and expanding knowledge graphs has aided the growth of temporal data, for instance, YAGO, NELL and Wikidata. While YAGO and Wikidata maintain the valid time of facts, NELL records the time point at which a fact is retrieved from some Web corpora. Collectively, these knowledge graphs (KG) store facts extracted from Wikipedia and other sources. Due to the imprecise nature of the extraction tools that are used to build and expand KG, such as NELL, the facts in the KG are weighted (a confidence value representing the correctness of a fact). Additionally, NELL can be considered as a transaction time KG because every fact is associated with extraction date. On the other hand, YAGO and Wikidata use the valid time model because they maintain facts together with their validity time (temporal scope). In this paper, we propose a bitemporal model (that combines transaction and valid time models) for maintaining and querying bitemporal probabilistic knowledge graphs. We study coalescing and scalability of marginal and MAP inference. Moreover, we show that complexity of reasoning tasks in atemporal probabilistic KG carry over to the bitemporal setting. Finally, we report our evaluation results of the proposed model.

There is an ever increasing number of rule learning algorithms and tools for automatic knowledge base (KB) construction. These tools often produce weighted rules and facts that make up a probabilistic KB (PKB). In such a PKB, probabilistic inference is used in order to perform marginal inference, consistency checking and other tasks. However, in general, inference is known to be intractable. Hence, recently, there are a number of studies aimed at lifting (making tractable or approximating) inference by exploiting symmetries in the structure of a PKB. These studies alleviate grounding entirely a given PKB which can generate a sizable factor graph for inference (e.g. to compute the probability of a query). In line with this, we propose a novel technique to automatically partition rules based on their structure for efficient parallel grounding. In addition, we perform query expansion so as to generate a factor graph small enough to be used for efficient probability computation. We present a novel approximate marginal inference algorithm that uses N-hop subgraph extraction and query expansion. Moreover, we show that our system is much faster than state-of-the-art systems.

The management of uncertainty is crucial when harvesting structured content from unstructured and noisy sources. Knowledge Graphs ( KGs ) are a prominent example. KGs maintain both numerical and non-numerical facts, with the support of an underlying schema. These facts are usually accompanied by a confidence score that witnesses how likely is for them to hold. Despite their popularity, most of existing KGs focus on static data thus impeding the availabilityof timewise knowledge. What is missing is a comprehensive solution for the management of uncertain and temporal data in KGs . The goal of this paper is to fill this gap. We rely on two main ingredients. The first is a numerical extension of Markov Logic Networks (MLNs) that provide the necessary underpinning to formalize the syntax and semantics of uncertain temporal KGs . The second is a set of Datalog constraints with inequalities that extend the underlying schema of the KGs and help to detect inconsistencies. From a theoretical point of view, we discuss the complexity of two important classes of queries for uncertain temporal KGs: maximuma-posteriori and conditional probability inference. Due to the hardness of these problems and the fact that MLN solvers do not scale well, we also explore the usage of Probabilistic Soft Logics (PSL) as a practical tool to support our reasoning tasks. We report on an experimental evaluation comparing the MLN and PSL approaches.

Open information extraction has driven automatic construction of (temporal) knowledge graphs (e.g. YAGO) that maintain probabilistic (temporal) facts and inference rules. One of the most important tasks in these knowledge graphs is query evaluation. This task is well known to be #P-hard. One of the bottlenecks of probabilistic (temporal) query evaluation is finding efficient ways of grounding the query and inference rules, to generate a factor graph that can be used for approximate query evaluation or to retrieve lineages of queries for exact evaluation. In this work, we propose the PRATiQUE (PRobAbilistic Temporal QUery Evaluation) framework for scalable temporal query evaluation. It harnesses the structure of temporal inference rules for efficient in-database grounding, i.e., it uses partitions to store structurally equivalent rules. Besides,PRATiQUE leverages a state-of-the-art Gibbs sampler to compute marginal probabilities of query answers. We report on an extensive experimental evaluation, which confirms the efficiency of our proposal.

The management of uncertainty is crucial when harvesting structured content from unstructured and noisy sources. Knowledge Graphs ( kg s), maintaining both numerical and non-numerical facts supported by an underlying schema, are a prominent example. Knowledge Graph management is challenging because: (i) most of existing kg s focus on static data, thus impeding the availability of timewise knowledge; (ii) facts in kg s are usually accompanied by a confidence score, which witnesses how likely it is for them to hold. We demonstrate T e C o R e , a system for temporal inference and conflict resolution in uncertain temporal knowledge graphs ( utkg s). At the heart of T e C o R e are two state-of-the-art probabilistic reasoners that are able to deal with temporal constraints efficiently. While one is scalable, the other can cope with more expressive constraints. The demonstration will focus on enabling users and applications to find inconsistencies in utkg s. T e C o R e provides an interface allowing to select utkg s and editing constraints; shows the maximal consistent subset of the utkg , and displays statistics (e.g., number of noisy facts removed) about the debugging process.

Most description logics (DL) query languages allow instance retrieval from an ABox. However, SPARQL is a schema query language allowing access to the TBox (in addition to the ABox). Moreover, its entailment regimes enable to take into account knowledge inferred from knowledge bases in the query answering process. This provides a new perspective for the containment problem. In this paper, we study the containment of SPARQL queries over OWL EL axioms under entailment. OWL EL is the language used by many large scale ontologies and is based on EL++. The main contribution is a novel approach to rewriting queries using SPARQL property paths and the μ-calculus in order to reduce containment test under entailment into validity check in the μ-calculus.

Ontology matching is an important part of enabling the semantic web to reach its full potential. Most existing ontology matching methods are mainly based on linguistic information (label, name, title and comment) but from the results achieved it is realized that this information is not sufficient. The latest ontology matching research works are trying to deeply dig into the structural information of ontologies by using "similarityflooding" method. However, there are several innate issues in similarity-flooding methods that lead to wrong matching results. In this paper, we report the problems of similarity-flooding in ontology matching and propose a novel method to effectively leverage the structural information of the ontology. The evaluation is conducted on OAEI ontology matching benchmarks from 2011 to 2015. The result shows that the proposed approach performs comparatively well with other state of the art matching systems.

Markov logic networks (MLNs) have proven to be useful tools for reasoning about uncertainty in complex knowledge bases. In this paper, we extend MLNs with numerical constraints and present an efficient implementation in terms of a cutting plane method. This extension is useful for reasoning over uncertain temporal data. To show the applicability of this extension, we enrich log-linear description logics (DLs) with concrete domains (datatypes). Thereby, allowing to reason over weighted DLs with datatypes. Moreover, we use the resulting formalism to reason about temporal assertions in DB-pedia, thus illustrating its practical use.

Information explosion leads to continuous growth of data distributed over different data sources. However, the increasing number of data sources increases the risk of inconsistency. In such a federative setting, description logics can be applied to define a central schema that serves as a conceptual view comprising and extending the semantics of each data source. Consequently, each data source is treated as a single knowledge base that is integrated in a federated knowledge base. Following this idea, we propose an approach for automated debugging of federated knowledge bases that targets the identification and repair of inconsistency. We report on experiments with a large distributed dataset from the domain of library science.

SPARQL query containment under schema axioms is the problem of determining whether, for any RDF graph satisfying a given set of schema axioms, the answers to a query are contained in the answers of another query. This problem has major applications for verification and optimization of queries. In order to solve it, we rely on the mu-calculus. Firstly, we provide a mapping from RDF graphs into transition systems. Secondly, SPARQL queries and RDFS and SHI axioms are encoded into mu-calculus formulas. This allows us to reduce query containment and equivalence to satisfiability in the mu-calculus. Finally, we prove a double exponential upper bound for containment under SHI schema axioms.