Author name cluster

İsmail İlkan Ceylan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

1 author row

AIJ Journal 2025 Journal Article

Explanations for query answers under existential rules

İsmail İlkan Ceylan
Thomas Lukasiewicz
Enrico Malizia
Andrius Vaicenavičius

Ontology-based data access is an extensively studied paradigm aiming at improving query answers with the use of an “ontology”. An ontology is a specification of a domain of interest, which, in this context, is described via a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for ontological query answers. This is a quite important aspect, as the fact that many recent AI systems mostly operating as black boxes has led to some serious concerns. In the literature, various works on explanations in the context of description logics (DLs) have appeared, mostly focusing on explaining concept subsumption and concept unsatisfiability in the ontologies. Some works on explaining query entailment in DLs have appeared as well, however, mainly dealing with inconsistency-tolerant semantics and, actually, non-entailment of the queries. Surprisingly, explaining ontological query entailment has received little attention for ontology languages based on existential rules. In fact, although DLs are popular formalisms to model ontologies, it is generally agreed that rule-based ontologies are well-suited for data-intensive applications, as they allow us to conveniently deal with higher-arity relations, which naturally occur in standard relational databases. The goal of this work is to close this gap, and study the problem of explaining query entailment in the context of existential rules ontologies in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations for various classes of existential rules, and for different complexity measures.

Details DOI

AIJ Journal 2022 Journal Article

Approximate weighted model integration on DNF structures

Ralph Abboud
İsmail İlkan Ceylan
Radoslav Dimitrov

Weighted model counting consists of computing the weighted sum of all satisfying assignments of a propositional formula. Weighted model counting is well-known to be #P-hard for exact solving, but admits a fully polynomial randomized approximation scheme when restricted to DNF structures. In this work, we study weighted model integration, a generalization of weighted model counting which involves real variables in addition to propositional variables, and pose the following question: Does weighted model integration on DNF structures admit a fully polynomial randomized approximation scheme? Building on classical results from approximate weighted model counting and approximate volume computation, we show that weighted model integration on DNF structures can indeed be approximated for a class of weight functions. Our approximation algorithm is based on three subroutines, each of which can be a weak (i. e. , approximate), or a strong (i. e. , exact) oracle, and in all cases, comes along with accuracy guarantees. We experimentally verify our approach over randomly generated DNF instances of varying sizes, and show that our algorithm scales to large problem instances, involving up to 1K variables, which are currently out of reach for existing, general-purpose weighted model integration solvers.

Details DOI

AIJ Journal 2021 Journal Article

Open-world probabilistic databases: Semantics, algorithms, complexity

İsmail İlkan Ceylan
Adnan Darwiche
Guy Van den Broeck

Large-scale probabilistic knowledge bases are becoming increasingly important in academia and industry. They are continuously extended with new data, powered by modern information extraction tools that associate probabilities with knowledge base facts. The state of the art to store and process such data is founded on probabilistic databases. Many systems based on probabilistic databases, however, still have certain semantic deficiencies, which limit their potential applications. We revisit the semantics of probabilistic databases, and argue that the closed-world assumption of probabilistic databases, i. e. , the assumption that facts not appearing in the database have the probability zero, conflicts with the everyday use of large-scale probabilistic knowledge bases. To address this discrepancy, we propose open-world probabilistic databases, as a new probabilistic data model. In this new data model, the probabilities of unknown facts, also called open facts, can be assigned any probability value from a default probability interval. Our analysis entails that our model aligns better with many real-world tasks such as query answering, relational learning, knowledge base completion, and rule mining. We make various technical contributions. We show that the data complexity dichotomy, between polynomial time and Image 1, for evaluating unions of conjunctive queries on probabilistic databases can be lifted to our open-world model. This result is supported by an algorithm that computes the probabilities of the so-called safe queries efficiently. Based on this algorithm, we prove that evaluating safe queries is in linear time for probabilistic databases, under reasonable assumptions. This remains true in open-world probabilistic databases for a more restricted class of safe queries. We extend our data complexity analysis beyond unions of conjunctive queries, and obtain a host of complexity results for both classical and open-world probabilistic databases. We conclude our analysis with an in-depth investigation of the combined complexity in the respective models.

Details DOI

AAAI Conference 2021 Conference Paper

Preferred Explanations for Ontology-Mediated Queries under Existential Rules

İsmail İlkan Ceylan
Thomas Lukasiewicz
Enrico Malizia
Cristian Molinaro
Andrius Vaicenavičius

Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.

PDF Details

IJCAI Conference 2021 Conference Paper

The Surprising Power of Graph Neural Networks with Random Node Initialization

Ralph Abboud
İsmail İlkan Ceylan
Martin Grohe
Thomas Lukasiewicz

Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman graph isomorphism heuristic. In order to break this expressiveness barrier, GNNs have been enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this work, we analyze the expressive power of GNNs with RNI, and prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. This universality result holds even with partially randomized initial node features, and preserves the invariance properties of GNNs in expectation. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.

PDF Details DOI

KR Conference 2020 Conference Paper

Explanations for Negative Query Answers under Existential Rules

İsmail İlkan Ceylan
Thomas Lukasiewicz
Enrico Malizia
Cristian Molinaro
Andrius Vaicenavičius

Ontology-mediated query answering is an extensively studied paradigm, where the conceptual knowledge provided by an ontology is leveraged towards more enhanced querying of data sources. A major advantage of ontological reasoning is its interpretability, which allows one to derive explanations for query answers. Indeed, explanations have a long history in knowledge representation, and have also been investigated for ontology languages based on description logics and existential rules. Existing works on existential rules, however, merely focus on understanding why a query is entailed, i. e. , explaining positive query answers. In this paper, we continue this line of research and address another important problem, namely, explaining why a query is not entailed under existential rules, i. e. , explaining negative query answers. We consider various problems related to explaining non-entailments from the abduction literature, and also introduce new problems. For all considered problems, we give a detailed complexity analysis for a wide range of existential rule languages and complexity measures.

PDF Details DOI

KR Conference 2020 Conference Paper

On the Approximability of Weighted Model Integration on DNF Structures

Ralph Abboud
İsmail İlkan Ceylan
Radoslav Dimitrov

Weighted model counting (WMC) consists of computing the weighted sum of all satisfying assignments of a propositional formula. WMC is well-known to be #P-hard for exact solving, but admits a fully polynomial randomised approximation scheme (FPRAS) when restricted to DNF structures. In this work, we study weighted model integration, a generalization of weighted model counting which involves real variables in addition to propositional variables, and pose the following question: Does weighted model integration on DNF structures admit an FPRAS? Building on classical results from approximate volume computation and approximate weighted model counting, we show that weighted model integration on DNF structures can indeed be approximated for a class of weight functions. Our approximation algorithm is based on three subroutines, each of which can be a weak (i. e. , approximate), or a strong (i. e. , exact) oracle, and in all cases, comes along with accuracy guarantees. We experimentally verify our approach over randomly generated DNF instances of varying sizes, and show that our algorithm scales to large problem instances, involving up to 1K variables, which are currently out of reach for existing, general-purpose weighted model integration solvers.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Explanations for Query Answers under Existential Rules

İsmail İlkan Ceylan
Thomas Lukasiewicz
Enrico Malizia
Andrius Vaicenavičius

Ontology-mediated query answering is an extensively studied paradigm, which aims at improving query answers with the use of a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for query answers. Surprisingly, however, explaining answers for ontology-mediated queries has received little attention for ontology languages based on existential rules. In this paper, we close this gap, and study the problem of explaining query answers in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations under existential rules.

PDF Details

AAAI Conference 2019 Conference Paper

Ontology-Mediated Query Answering over Log-Linear Probabilistic Data

Stefan Borgwardt
İsmail İlkan Ceylan
Thomas Lukasiewicz

Large-scale knowledge bases are at the heart of modern information systems. Their knowledge is inherently uncertain, and hence they are often materialized as probabilistic databases. However, probabilistic database management systems typically lack the capability to incorporate implicit background knowledge and, consequently, fail to capture some intuitive query answers. Ontology-mediated query answering is a popular paradigm for encoding commonsense knowledge, which can provide more complete answers to user queries. We propose a new data model that integrates the paradigm of ontology-mediated query answering with probabilistic databases, employing a log-linear probability model. We compare our approach to existing proposals, and provide supporting computational results.

PDF Details

IJCAI Conference 2018 Conference Paper

Recent Advances in Querying Probabilistic Knowledge Bases

Stefan Borgwardt
İsmail İlkan Ceylan
Thomas Lukasiewicz

We give a survey on recent advances at the forefront of research on probabilistic knowledge bases for representing and querying large-scale automatically extracted data. We concentrate especially on increasing the semantic expressivity of formalisms for representing and querying probabilistic knowledge (i) by giving up the closed-world assumption, (ii) by allowing for commonsense knowledge (and in parallel giving up the tuple-independence assumption), and (iii) by giving up the closed-domain assumption, while preserving some computational properties of query answering in such formalisms.

PDF Details

IJCAI Conference 2017 Conference Paper

Most Probable Explanations for Probabilistic Database Queries

İsmail İlkan Ceylan
Stefan Borgwardt
Thomas Lukasiewicz

Forming the foundations of large-scale knowledge bases, probabilistic databases have been widely studied in the literature. In particular, probabilistic query evaluation has been investigated intensively as a central inference mechanism. However, despite its power, query evaluation alone cannot extract all the relevant information encompassed in large-scale knowledge bases. To exploit this potential, we study two inference tasks; namely finding the most probable database and the most probable hypothesis for a given query. As natural counterparts of most probable explanations (MPE) and maximum a posteriori hypotheses (MAP) in probabilistic graphical models, they can be used in a variety of applications that involve prediction or diagnosis tasks. We investigate these problems relative to a variety of query languages, ranging from conjunctive queries to ontology-mediated queries, and provide a detailed complexity analysis.

PDF Details

IJCAI Conference 2017 Conference Paper

Query Answering in Ontologies under Preference Rankings

İsmail İlkan Ceylan
Thomas Lukasiewicz
Rafael Peñaloza
Oana Tifrea-Marciuska

We present an ontological framework, based on preference rankings, that allows users to express their preferences between the knowledge explicitly available in the ontology. Using this formalism, the answers for a given query to an ontology can be ranked by preference, allowing users to retrieve the most preferred answers only. We provide a host of complexity results for the main computational tasks in this framework, for the general case, and for EL and DL-Lite_core as underlying ontology languages.

PDF Details