Author name cluster

Cristian Molinaro

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.

23 papers

1 author row

AIJ Journal 2025 Journal Article

Defending a city from multi-drone attacks: A sequential Stackelberg security games approach

Dolev Mutzari
Tonmoay Deb
Cristian Molinaro
Andrea Pugliese
V.S. Subrahmanian
Sarit Kraus

To counter an imminent multi-drone attack on a city, defenders have deployed drones across the city. These drones must intercept/eliminate the threat, thus reducing potential damage from the attack. We model this as a Sequential Stackelberg Security Game, where the defender first commits to a mixed sequential defense strategy, and the attacker then best responds. We develop an efficient algorithm called S2D2, which outputs a defense strategy. We demonstrate the efficacy of S2D2 in extensive experiments on data from 80 real cities, improving the performance of the defender in comparison to greedy heuristics based on prior works. We prove that under some reasonable assumptions about the city structure, S2D2 outputs an approximate Strong Stackelberg Equilibrium (SSE) with a convenient structure.

Details DOI

KR Conference 2025 Conference Paper

Extending Abstract Argumentation Frameworks with Knowledge Bases

Gianvincenzo Alfano
Sergio Greco
Cristian Molinaro
Francesco Parisi
Irina Trubitsyna

Dung's abstract Argumentation Framework (AF) has been extended in several directions to make knowledge representation and reasoning more intuitive and expressive. In this paper, we present the Knowledge-based Argumentation Framework (KAF), an extension of AF with a Knowledge Base (KB) expressed in DL-Lite, which includes concept and role instances describing the topology of an AF, besides additional knowledge on the domain. The KAF semantics is given by a set of KAF extensions, each consisting of an extension of the underlying AF together with a ``pertinent'' subset of the original KB, which is obtained by discarding assertions referring to arguments that have been ruled out in the AF extension. Then, the framework is further expanded into the Constrained KAF (CKAF), where a set of restricted relational calculus formulae is used for reasoning over `feasible' subframeworks that satisfy the formulae and minimally differ from the original framework. We thoroughly investigate the computational complexity of classical reasoning problems under popular argumentation semantics, and show that well-known AF-based frameworks are special cases of CKAF.

PDF Details DOI

KR Conference 2025 Conference Paper

On the Complexity of Global Necessary Reasons to Explain Classification

Marco Calautti
Enrico Malizia
Cristian Molinaro

Explainable AI has garnered considerable attention in recent years, as understanding the reasons behind decisions made by AI systems is crucial for their successful adoption. Explaining classifiers' behavior is one prominent problem. Work in this area has proposed notions of both local and global explanations, where the former are concerned with explaining a classifier's behavior for a specific instance, while the latter are concerned with explaining the overall classifier's behavior regardless of any specific instance. In this paper, we focus on global explanations, and explain classification in terms of ``minimal'' necessary conditions for the classifier to assign a specific class to a generic instance. We carry out a thorough complexity analysis of the problem for natural minimality criteria and important families of classifiers considered in the literature.

PDF Details DOI

KR Conference 2023 Conference Paper

Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Preferred Repairs

Thomas Lukasiewicz
Enrico Malizia
Cristian Molinaro

Inconsistency-tolerant semantics have been proposed to provide meaningful ontological query answers even in the presence of inconsistencies. Several such semantics rely on the notion of a repair, which is a "maximal" consistent subset of the database, where different maximality criteria might be adopted depending on the application at hand. Previous work in the context of Datalog+/- has considered only the subset and cardinality maximality criteria. We take here a step further and study inconsistency-tolerant semantics under maximality criteria based on weights and priority levels. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.

PDF Details DOI

AAAI Conference 2023 System Paper

DUCK: A Drone-Urban Cyber-Defense Framework Based on Pareto-Optimal Deontic Logic Agents

Tonmoay Deb
Jürgen Dix
Mingi Jeong
Cristian Molinaro
Andrea Pugliese
Alberto Quattrini Li
Eugene Santos, Jr
V.S. Subrahmanian

Drone based terrorist attacks are increasing daily. It is not expected to be long before drones are used to carry out terror attacks in urban areas. We have developed the DUCK multi-agent testbed that security agencies can use to simulate drone-based attacks by diverse actors and develop a combination of surveillance camera, drone, and cyber defenses against them.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases (Extended Abstract)

John Grant
Maria Vanina Martinez
Cristian Molinaro
Francesco Parisi

We define and investigate new inconsistency measures that are particularly suitable for dealing with inconsistent spatio-temporal information, as they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w. r. t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions, and thus define ``dimension-aware'' counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Explanations for Negative Query Answers under Inconsistency-Tolerant Semantics

Thomas Lukasiewicz
Enrico Malizia
Cristian Molinaro

Inconsistency-tolerant semantics have been proposed to provide meaningful query answers even in the presence of inconsistent knowledge. Recently, explainability has also become a prominent problem in different areas of AI. While the complexity of inconsistency-tolerant semantics is rather well-understood, not much attention has been paid yet to the problem of explaining query answers when inconsistencies may exist. Recent work on existential rules in the inconsistent setting has focused only on understanding why a query is entailed. In this paper, we address another important problem, which is explaining why a query is not entailed under an inconsistency-tolerant semantics. In particular, we consider three popular semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.

PDF Details DOI

IS Journal 2022 Journal Article

Guest Editorial: Reasoning With Inconsistent, Incomplete, and Uncertain Knowledge

Enrico Malizia
Cristian Molinaro
Francesco Parisi

The five papers in this special section focus on the management and analysis of uncertain, incomplete, and inconsistent information. This has become a crucial issue in the development of intelligent systems. Nowadays, such systems have to efficiently manage large amounts of information of different kinds, often represented in different formats and coming from different sources, such as databases, knowledge bases, sensor networks, as well as various data-driven applications. In the presence of such complex and heterogeneous forms of information, incompleteness, inconsistency, and/or inherent uncertainty inevitably arise. These scenarios call for innovative and intelligent approaches that, by leveraging AI techniques, can explicitly represent inconsistency, incompleteness, and uncertainty, and adequately deal with them. Such approaches are crucial to model realworld scenarios, making systems more effective and successful. Moreover, in many domains, knowledge is subject to frequent changes, so handling evolving knowledge is a key feature that knowledge-based systems should provide. In domains having high-impact consequences (e. g. , healthcare and cybersecurity), intelligent systems should support human-in-the-loop models that provide tools to help users to understand and interpret the decisions they suggest, while tackling the challenges of inconsistency, incompleteness, and uncertainty. The AI community has also lately been facing the rising demand of explainable AI systems, which have inevitably to deal with inconsistency, incompleteness, and uncertainty.

Details DOI

AIJ Journal 2022 Journal Article

Inconsistency-tolerant query answering for existential rules

Thomas Lukasiewicz
Enrico Malizia
Maria Vanina Martinez
Cristian Molinaro
Andreas Pieris
Gerardo I. Simari

Querying inconsistent knowledge bases is an intriguing problem that gave rise to a flourishing research activity in the knowledge representation and reasoning community during the last years. It has been extensively studied in the context of description logics (DLs), and its computational complexity is rather well-understood. Although DLs are popular formalisms for modeling ontologies, it is generally agreed that rule-based ontologies are well-suited for data-intensive applications, since they allow us to conveniently deal with higher-arity relations, which naturally occur in standard relational databases. The goal of this work is to perform an in-depth complexity analysis of querying inconsistent knowledge bases in the case of the main decidable classes of existential rules, based on the notions of guardedness, linearity, acyclicity, and stickiness, enriched with negative (a. k. a. denial) constraints. Our investigation concentrates on three central inconsistency-tolerant semantics: the ABox repair (AR) semantics, considered as the standard one, and its main sound approximations, the intersection of repairs (IAR) semantics and the intersection of closed repairs (ICR) semantics.

Details DOI

AIJ Journal 2022 Journal Article

Preference-based inconsistency-tolerant query answering under existential rules

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Ontology-mediated query answering (OMQA) emerged as a paradigm to enhance querying of data sources with an ontology that encodes background knowledge. In applications involving large amounts of data from multiple data sources, it might well be the case that inconsistency arises, making standard query answering useless, since everything is entailed by an inconsistent knowledge base. Being able to provide meaningful query answers in the presence of inconsistency is thus a critical issue to make OMQA systems successful in practice. The problem of querying inconsistent knowledge has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics of query answering have been proposed, that is, approaches to answer queries in a meaningful way despite the knowledge at hand being inconsistent. Most of the semantics in the literature are based on the notion of repair, that is, a “maximal” consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. Specifically, we introduce preference rules, a declarative formalism which enable users to express (i) preferences over both the database and the knowledge that can be derived from it via an ontology, and (ii) preconditions for preferences to hold. We then define two notions of preferred repairs which take preference rules into account. This naturally leads us to introducing preference-aware counterparts of popular inconsistency-tolerant semantics, where only preferred repairs are considered for query answering. We provide a thorough analysis of the data and combined complexity of different relevant problems for a wide range of existential rule languages.

Details DOI

TCS Journal 2022 Journal Article

Query answering over inconsistent knowledge bases: A probabilistic approach

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Consistent query answering (CQA) is a widely accepted paradigm for querying inconsistent knowledge bases (KBs). A consistent answer to a query is a tuple that is an answer to the query over every repair of the KB, which is in turn a consistent KB whose extensional knowledge “minimally” differs from the original one's. This coarse-grained classification of answers into consistent and non-consistent ones lacks any information about their degree of consistency, i. e. , how likely it is that a tuple is an answer to the query, when considering all the repaired KBs. To overcome this limitation, we consider a fine-grained notion of repair for KBs with equality-generating dependencies (EGDs), based on attribute-level updates, and exploit this notion to propose a probabilistic CQA approach, which associates a confidence to each answer, thereby providing more informative query answers. We first show that computing the query answer confidence is # P -hard. Then, in the light of this intractability result, we study the existence of efficient randomized, approximation schemes. In particular, we show that absolute error approximation schemes always exist in the general case, while more refined relative error approximation schemes, i. e. , fully polynomial-time, randomized approximation schemes (FPRAS) exist when assuming that the constraints of the knowledge base are primary keys. Finally, we extend our framework to knowledge bases with tuple-generating dependencies (TGDs) and generalize our approximability results to the new setting, and prove additional inapproximability results.

Details DOI

JAIR Journal 2021 Journal Article

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases

John Grant
Maria Vanina Martinez
Cristian Molinaro
Francesco Parisi

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting. In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

PDF 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

AAAI Conference 2021 Conference Paper

Randomized Generation of Adversary-aware Fake Knowledge Graphs to Combat Intellectual Property Theft

Snow Kang
Cristian Molinaro
Andrea Pugliese
V. S. Subrahmanian

Knowledge Graphs (KGs) can be used to store information about software design, biomedical designs, and financial information—all domains where intellectual property and/or specialized knowledge must be kept confidential. Moreover, KGs can also be used to represent the content of technical documents. In order to deter theft of intellectual property via cyber-attacks, we consider the following problem: given a KG K0 (e. g. , representing a software or biomedical device design or the content of a technical document), can we automatically generate a set of KGs that are similar enough to K0 (so they are hard to discern as synthetic) but sufficiently different (so as to be wrong)? If this is possible, then we will be one step closer to automatically generating fake KGs that an adversary has difficulty distinguishing from the original. We will also be closer to automatically generating documents corresponding to fake KGs so that an adversary who steals such documents has difficulty distinguishing the real from the fakes. We formally define this problem and prove that it is NP-hard. We show that obvious approaches to solving this problem do not satisfy a novel concept of “adversary-awareness” that we define. We provide a graphtheoretic characterization of the problem and leverage it to devise an “adversary-aware” algorithm. We validate the efficacy of our algorithm on 3 diverse real-world datasets, showing that it achieves high levels of deception.

PDF Details

AAAI Conference 2020 Conference Paper

Explanations for Inconsistency-Tolerant Query Answering under Existential Rules

Thomas Lukasiewicz
Enrico Malizia
Cristian Molinaro

Querying inconsistent knowledge bases is a problem that has attracted a great deal of interest over the last decades. While several semantics of query answering have been proposed, and their complexity is rather well-understood, little attention has been paid to the problem of explaining query answers. Explainability has recently become a prominent problem in different areas of AI. In particular, explaining query answers allows users to understand not only what is entailed by an inconsistent knowledge base, but also why. In this paper, we address the problem of explaining query answers for existential rules under three popular inconsistency-tolerant semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs semantics. We provide a thorough complexity analysis for a wide range of existential rule languages and for different complexity measures.

PDF Details

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

Preference-based Inconsistency-Tolerant Query Answering under Existential Rules

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Query answering over inconsistent knowledge bases is a problem that has attracted a great deal of interest over the years. Different inconsistency-tolerant semantics have been proposed, and most of them are based on the notion of repair, that is, a "maximal" consistent subset of the database. In general, there can be several repairs, so it is often natural and desirable to express preferences among them. In this paper, we propose a framework for querying inconsistent knowledge bases under user preferences for existential rule languages. We provide generalizations of popular inconsistency-tolerant semantics taking preferences into account and study the data and combined complexity of different relevant problems.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Complexity of Approximate Query Answering under Inconsistency in Datalog+/-

Thomas Lukasiewicz
Enrico Malizia
Cristian Molinaro

Several semantics have been proposed to query inconsistent ontological knowledge bases, including the intersection of repairs and the intersection of closed repairs as two approximate inconsistency-tolerant semantics. In this paper, we analyze the complexity of conjunctive query answering under these two semantics for a wide range of Datalog+/- languages. We consider both the standard setting, where errors may only be in the database, and the generalized setting, where also the rules of a Datalog+/- knowledge base may be erroneous.

PDF Details

IJCAI Conference 2018 Conference Paper

Computing Approximate Query Answers over Inconsistent Knowledge Bases

Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Consistent query answering is a principled approach for querying inconsistent knowledge bases. It relies on the notion of a "repair", that is, a maximal consistent subset of the facts in the knowledge base. One drawback of this approach is that entire facts are deleted to resolve inconsistency, even if they may still contain useful "reliable" information. To overcome this limitation, we propose a new notion of repair allowing values within facts to be updated for restoring consistency. This more fine-grained repair primitive allows us to preserve more information in the knowledge base. We also introduce the notion of a "universal repair", which is a compact representation of all repairs. Then, we show that consistent query answering in our framework is intractable (coNP-complete). In light of this result, we develop a polynomial time approximation algorithm for computing a sound (but possibly incomplete) set of consistent query answers.

PDF Details

AIJ Journal 2016 Journal Article

Diffusion centrality: A paradigm to maximize spread in social networks

Chanhyun Kang
Sarit Kraus
Cristian Molinaro
Francesca Spezzano
V.S. Subrahmanian

We propose Diffusion Centrality (DC) in which semantic aspects of a social network are used to characterize vertices that are influential in diffusing a property p. In contrast to classical centrality measures, diffusion centrality of vertices varies with the property p, and depends on the diffusion model describing how p spreads. We show that DC applies to most known diffusion models including tipping, cascade, and homophilic models. We present a hypergraph-based algorithm (HyperDC) with many optimizations to exactly compute DC. However, HyperDC does not scale well to huge social networks (millions of vertices, tens of millions of edges). For scaling, we develop methods to coarsen a network and propose a heuristic algorithm called “Coarsened Back and Forth” (CBAF) to compute the top-k vertices (having the highest diffusion centrality). We report on experiments comparing DC with classical centrality measures in terms of runtime and the “spread” achieved by the k most central vertices (using 7 real-world social networks and 3 different diffusion models). Our experiments show that DC produces higher quality results and is comparable to several centrality measures in terms of runtime.

Details DOI

IJCAI Conference 2015 Conference Paper

Logic Program Termination Analysis Using Atom Sizes

Marco Calautti
Sergio Greco
Cristian Molinaro
Irina Trubitsyna

Recent years have witnessed a great deal of interest in extending answer set programming with function symbols. Since the evaluation of a program with function symbols might not terminate and checking termination is undecidable, several classes of logic programs have been proposed where the use of function symbols is limited but the program evaluation is guaranteed to terminate. In this paper, we propose a novel class of logic programs whose evaluation always terminates. The proposed technique identifies terminating programs that are not captured by any of the current approaches. Our technique is based on the idea of measuring the size of terms and atoms to check whether the rule head size is bounded by the body, and performs a more fine-grained analysis than previous work. Rather than adopting an all-ornothing approach (either we can say that the program is terminating or we cannot say anything), our technique can identify arguments that are “limited” (i. e. , where there is no infinite propagation of terms) even when the program is not entirely recognized as terminating. Identifying arguments that are limited can support the user in the problem formulation and help other techniques that use limited arguments as a starting point. Another useful feature of our approach is that it is able to leverage external information about limited arguments. We also provide results on the correctness, the complexity, and the expressivity of our technique.

PDF Details

IJCAI Conference 2013 Conference Paper

Bounded Programs: A New Decidable Class of Logic Programs with Function Symbols

Sergio Greco
Cristian Molinaro
Irina Trubitsyna

While function symbols are widely acknowledged as an important feature in logic programming, they make common inference tasks undecidable. To cope with this problem, recent research has focused on identifying classes of logic programs imposing restrictions on the use of function symbols, but guaranteeing decidability of common inference tasks. This has led to several criteria, called termination criteria, providing sufficient conditions for a program to have finitely many stable models, each of finite size. This paper introduces the new class of bounded programs which guarantees the aforementioned property and strictly includes the classes of programs determined by current termination criteria. Different results on the correctness, the expressiveness, and the complexity of the class of bounded programs are presented.

PDF Details DOI

IJCAI Conference 2011 Conference Paper

Finding "Unexplained" Activities in Video

Massimiliano Albanese
Cristian Molinaro
Fabio Persia
Antonio Picariello
V. S. Subrahmanian

Consider a video surveillance application that monitors some location. The application knows a set of activity models (that are either normal or abnormal or both), but in addition, the application wants to find video segments that are unexplained by any of the known activity models - these unexplained video segments may correspond to activities for which no previous activity model existed. In this paper, we formally define what it means for a given video segment to be unexplained (totally or partially) w. r. t. a given set of activity models and a probability threshold. We develop two algorithms - FindTUA and FindPUA - to identify Totally and Partially Unexplained Activities respectively, and show that both algorithms use important pruning methods. We report on experiments with a prototype implementation showing that the algorithms both run efficiently and are accurate.

PDF Details DOI