The problem of answering complex First-order Logic queries over incomplete knowledge graphs  is receiving growing attention in the literature. A promising recent approach to this problem has been to exploit neural link predictors, which can be
effective in identifying individual missing triples in the incomplete graph, in order to efficiently answer complex queries. A crucial advantage of this approach over
other methods is that it does not require example answers to complex queries for training, as it relies only on the availability of a trained link  predictor for the knowledge graph at hand.  This approach, however, can be computationally expensive during inference,  and cannot deal with queries involving negation. 

In this paper, we propose a novel approach that addresses all of these limitations.
Experiments on established benchmark datasets demonstrate that our approach offers  superior performance while  significantly reducing inference times.

Efficient Embeddings of Logical Variables for Query Answering over Incomplete Knowledge Graphs

DatalogMTL is a powerful extension of Datalog with operators from metric temporal logic (MTL), which has received significant attention in recent years. In this paper, we investigate materialisation-based reasoning (a.k.a. forward chaining) in the context of DatalogMTL programs and datasets with bounded intervals, where partial representations of the canonical model are obtained through successive rounds of rule applications. Although materialisation does not naturally terminate in this setting, it is known that the structure of canonical models is ultimately periodic. Our first contribution in this paper is a detailed analysis of the periodic structure of canonical models; in particular, we formulate saturation conditions whose satisfaction by a partial materialisation implies an ability to recover the full canonical model via unfolding; this allows us to compute the actual periods describing the repeating parts of the canonical model as well as to establish concrete bounds on the number of rounds of rule applications required to achieve saturation. Based on these theoretical results, we propose a practical reasoning algorithm where saturation can be efficiently detected as materialisation progresses, and where the relevant periods used to evaluate entailment of queries via unfolding are efficiently computed. We have implemented our algorithm  and our experiments suggest that  our approach is both scalable and robust.

Materialisation-based Reasoning in DatalogMTL with Bounded Intervals

DatalogMTL is an extension of Datalog with operators from metric temporal logic which has received significant attention in recent years. It is a highly expressive knowledge representation language that is well-suited for applications in temporal ontology-based query answering and stream processing. Reasoning in DatalogMTL is, however, of high computational complexity, making implementation challenging and hindering its adoption in applications. In this paper, we present a novel approach for practical reasoning in DatalogMTL which combines materialisation (a.k.a. forward chaining) with automata-based techniques. We have implemented this approach in a reasoner called MeTeoR and evaluated its performance using a temporal extension of the Lehigh University Benchmark and a benchmark based on real-world meteorological data. Our experiments show that MeTeoR is a scalable system which enables reasoning over complex temporal rules and datasets involving tens of millions of temporal facts.

MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators

We extend DatalogMTLâ€”Datalog with operators from metric temporal logicâ€”by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rational timeline, study their properties, and establish the computational complexity of reasoning. We show that, as in negation-free DatalogMTL, fact entailment in our language is PSPACE-complete in data and EXPSPACE-complete in combined complexity. Thus, the extension with stratified negation does not lead to higher complexity.

Bernardo Cuenca Grau

4

3

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES