ABSTRACT. Embeddings of knowledge bases (KBs) emerged as a way of “softening” their classical crisp representation. The idea is to represent KBs in vector spaces via an optimization procedure that encourages axioms in the KB to hold. To illustrate, consider a KB that keeps the records of politicians. There may be crisp rules, such as the condition that politicians need to be lawful citizens to be elected, but also data patterns indicating that politicians are commonly senior male natives. By including facts and rules from the KB in the optimization procedure, the resulting vector representation can accommodate both “soft” inferences based on data patterns and rule-based inferences, all within the vector representation. In this talk, I will discuss opportunities and challenges of representing the semantics of KBs in vector spaces, focusing on geometric-based embedding methods. I will cast light on certain aspects of data analysis, such as biases and fairness, as well as relate KB embeddings with approximate reasoning and query answering.

ABSTRACT. We study the problem of fitting ontologies and constraints to positive and negative examples that take the form of a finite relational structure. As ontology and constraint languages, we consider the description logics EL and ELI as well as several classes of tuple-generating dependencies (TGDs): full, guarded, frontier-guarded, frontier-one, and unrestricted TGDs as well as inclusion dependencies. We pinpoint the exact computational complexity, design algorithms, and analyze the size of fitting ontologies and TGDs. We also investigate the related problem of constructing a finite basis of concept inclusions / TGDs for a given set of finite structures.

ABSTRACT. Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for concepts formulated in the description logic ALC and its syntactic fragments. We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting comes with probabilistic guarantees in Valiant's PAC learning framework. In contrast, we show that other classes of algorithms for learning ALC concepts do not provide such guarantees. Finally, we present an implementation of bounded fitting in ALC and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.

ABSTRACT. We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form (A, q) with A an ABox and q a query, we seek an ontology O such that A ∪ O entails q for all positive examples (A, q) and A ∪ O does not entail q for all negative examples (A, q). We consider the description logics ALC and ALCI as ontology languages and a range of query languages that includes atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). For all of the resulting fitting problems, we provide effective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be coNP-complete for AQs and full CQs and 2ExpTime-complete for CQs and UCQs. These results hold for both ALC and ALCI.

ABSTRACT. While the computation of Craig interpolants for description logics (DLs) with the Craig Interpolation Property (CIP) is well understood, very little is known about the computation and size of interpolants for DLs without CIP or if one aims at interpolating concepts in a weaker DL than the DL of the input ontology and concepts. In this paper, we provide the first elementary algorithms computing (i) ALC-interpolants between ALC-concepts under ALCH-ontologies and (ii) ALC-interpolants between ALCQ-concepts under ALCQ-ontologies. The algorithms are based on recent decision procedures for interpolant existence. We also observe that, in contrast, uniform (possibly depth restricted) interpolants might be of non-elementary size.

ABSTRACT. We propose an interactive repair method for the description logic EL that is based on the optimal-repair framework. The obtained repair might not be optimal in the theoretical sense, i.e. more than a minimal amount of consequences might have been removed — but from a practical perspective it is superior to a theoretically optimal repair as the interaction strategy enables the users to identify further faulty consequences connected to the initially reported errors. This is an extended abstract of a paper published in the proceedings of the 40th ACM/SIGAPP Symposium on Applied Computing (SAC ’25), KRR track. https://doi.org/10.1145/3672608.3707750

ABSTRACT. An abductive difference between two quantified ABoxes consists of the knowledge that needs to be added to the first to make the second entailed. We describe a generic construction of such differences and show that all minimal abductive differences can be computed in exponential time. Moreover, we present first results when ontologies are taken into account.

ABSTRACT. Consequence-based reasoning can be used to construct proofs that explain entailments of description logic (DLs) ontologies. In the literature, one can find multiple consequence-based calculi for reasoning in the ℰℒ family of DLs, each of which gives rise to proofs of different shapes. Here, we study three such calculi and the proofs they produce on a benchmark based on the OWL Reasoner Evaluation. The calculi are implemented using a translation into existential rules with stratified negation, which had already been demonstrated to be effective for the calculus of the ELK reasoner. We then use the rule engine Nemo to evaluate the rules and obtain traces of the rule execution. After translating these traces back into DL proofs, we compare them across several metrics that reflect different aspects of their complexity, such as proof size and depth.

ABSTRACT. In this extended abstract, we report on our recent work on quantitative approaches to explaining query answers employs responsibility measures to assign scores to facts in order to quantify their respective contributions to obtaining a given answer. In this paper, we study the complexity of computing such responsibility scores in the setting of ontology-mediated query answering, focusing on a very recently introduced family of Shapley-value-based responsibility measures defined in terms of weighted sums of minimal supports (WSMS). By exploiting results from the database setting, we can show that such measures enjoy polynomial data complexity for classes of ontology-mediated queries that are first-order-rewritable, whereas the problem becomes #P-hard when the ontology language can encode reachability queries (via axioms like ∃R.A ⊑ A). To better understand the tractability frontier, we next explore the combined complexity of WSMS computation. We prove that intractability applies already to atomic queries if the ontology language supports conjunction, as well as to unions of ‘well-behaved’ conjunctive queries, even in the absence of an ontology. By contrast, our study yields positive results for common DL-Lite dialects: by means of careful analysis, we identify classes of structurally restricted conjunctive queries (which intuitively disallow undesirable interactions between query atoms) that admit tractable WSMS computation.

ABSTRACT. We introduce the notion of contrastive ABox explanations to answer questions of the type “Why is a an instance of C, but b is not?”. While there are various approaches for explaining positive entailments (why is C(a) entailed by the knowledge base) as well as missing entailments (why is C(b) not entailed) in isolation, contrastive explanations consider both at the same time, which allows them to focus on the relevant similarities and differences between a and b. We discuss and develop an appropriate notion of contrastive explanations for the special case of ABox reasoning with description logics, and then analyze the computational complexity for different variants under different optimality criteria, considering both light-weight and more expressive description logics. We furthermore present a first prototype for computing contrastive explanations, and evaluate it on constructed problems with realistic ontologies.