2.1 Logic and graph-based KR

The main research domain of GraphIK is Knowledge Representation and Reasoning (KR), which studies paradigms and formalisms for representing knowledge and reasoning on these representations. A large part of our work is strongly related to data management and database theory.

We develop logical languages, which mainly correspond to fragments of first-order logic. However, we also use graphs and hypergraphs (in the graph-theoretic sense) as basic objects. Indeed, we view labelled graphs as an abstract representation of knowledge that can be expressed in many KR languages: different kinds of conceptual graphs—historically our main focus—the Semantic Web language RDFS, expressive rules equivalent to so-called tuple-generating-dependencies in databases, some description logics dedicated to query answering, etc. For these languages, reasoning can be based on the structure of objects (thus on graph-theoretic notions) while being sound and complete with respect to entailment in the associated logical fragments. An important issue is to study trade-offs between the expressivity and the computational tractability of (sound and complete) reasoning in these languages.

2.2 From theory to applications, and vice-versa

We study logic- and graph-based KR formalisms from three perspectives:

• theoretical (structural properties, expressiveness, translations between languages, problem complexity, algorithm design);
• software (developing tools to implement theoretical results);
• applications (formalizing practical issues and solving them with our techniques, which also feeds back into theoretical work).

2.3 Main challenges

GraphIK focuses on some of the main challenges in KR:

• ontological query answering: querying large, complex or heterogeneous datasets, provided with an ontological layer;
• reasoning with rule-based languages;
• reasoning in presence of inconsistencies and
• decision making.

2.4 Scientific directions

Our research work is currently organized into two research lines, both with theoretical and applied aspects:

1. Ontology-mediated query answering (OMQA). Modern information systems are often structured around an ontology, which provides a high-level vocabulary, as well as knowledge relevant to the target domain, and enables a uniform access to possibly heterogeneous data sources. As many complex tasks can be recast in terms of query answering, the question of querying data while taking into account inferences enabled by ontological knowledge has become a fundamental issue. This gives rise to the notion of a knowledge base, composed of an ontology and a factbase, both described using a KR language. The factbase can be seen as an abstraction of several data sources, and may actually remain virtual. The topical ontology-mediated query answering (OMQA) problem asks for all answers to queries that are logically entailed by the given knowledge base.
2. Reasoning with imperfect knowledge and decision support. To solve real-world problems we often need to consider features that cannot be expressed purely (or naturally) in classical logic. Indeed, information is often “imperfect”: it can be partially contradictory, vague or uncertain, etc. These last years, we mostly considered reasoning in presence of conflicts, where contradictory information may come from the data or from the ontology. This requires to define appropriate semantics, able to provide meaningful answers to queries while taming the computational complexity increase. Reasoning becomes more complex from a conceptual viewpoint as well, hence how to explain results to an end-user is also an important issue. Such questions are natural extensions to those studied in the first axis. On the other hand, the work of this axis is also motivated by applications provided by our INRAE partners, where the knowledge to be represented intrinsically features several viewpoints and involves different stakeholders with divergent priorities, while a decision has to be made. Beyond the representation of conflictual knowledge itself, this raises arbitration issues. The aim here is to support decision making by tools that help eliciting and representing relevant knowledge, including the stakeholders' preferences and motivations, compute syntheses of compatible options, and propose justified decisions.

3.1 Logic-based knowledge representation and reasoning

We follow the mainstream logic-based approach to knowledge representation (KR). First-order logic (FOL) is the reference logic in KR and most formalisms in this area can be translated into fragments (i.e., particular subsets) of FOL. This is in particular the case for description logics and existential rules, two well-known KR formalisms studied in the team.

A large part of research in this domain can be seen as studying trade-offs between the expressivity of languages and the complexity of (sound and complete) reasoning in these languages. The fundamental problem in KR languages is entailment checking: is a given piece of knowledge entailed by other pieces of knowledge, for instance from a knowledge base (KB)? Another important problem is consistency checking: is a set of knowledge pieces (for instance the knowledge base itself) consistent, i.e., is it sure that nothing absurd can be entailed from it? The ontology-mediated query answering problem is a topical problem (see Section 3.3). It asks for the set of answers to a query in the KB. In the case of Boolean queries (i.e., queries with a yes/no answer), it can be recast as entailment checking.

3.2 Graph-based knowledge representation and reasoning

Besides logical foundations, we are interested in KR formalisms that comply, or aim at complying with the following requirements: to have good computational properties and to allow users of knowledge-based systems to have a maximal understanding and control over each step of the knowledge base building process and use.

These two requirements are the core motivations for our graph-based approach to KR. We view labelled graphs as an abstract representation of knowledge that can be expressed in many KR languages (different kinds of conceptual graphs —historically our main focus— the Semantic Web language RDF (Resource Description Framework), its extension RDFS (RDF Schema), expressive rules equivalent to the so-called tuple-generating-dependencies in databases, some description logics dedicated to query answering, etc.). For these languages, reasoning can be based on the structure of objects, thus based on graph-theoretic notions, while staying logically founded.

More precisely, our basic objects are labelled graphs (or hypergraphs) representing entities and relationships between these entities. These graphs have a natural translation in first-order logic. Our basic reasoning tool is graph homomorphism. The fundamental property is that graph homomorphism is sound and complete with respect to logical entailment i.e., given two (labelled) graphs $G$ and $H$, there is a homomorphism from $G$ to $H$if and only if the formula assigned to $G$ is entailed by the formula assigned to $H$. In other words, logical reasoning on these graphs can be performed by graph mechanisms. These knowledge constructs and the associated reasoning mechanisms can be extended (to represent rules for instance) while keeping this fundamental correspondence between graphs and logics.

3.3 Ontology-mediated query answering

Querying knowledge bases has become a central problem in knowledge representation and in databases. A knowledge base is classically composed of a terminological part (metadata, ontology) and an assertional part (facts, data). Queries are supposed to be at least as expressive as the basic queries in databases, i.e., conjunctive queries, which can be seen as existentially closed conjunctions of atoms or as labelled graphs. The challenge is to define good trade-offs between the expressivity of the ontological language and the complexity of querying data in presence of ontological knowledge. Description logics have been so far the prominent family of formalisms for representing and reasoning with ontological knowledge. However, classical description logics were not designed for efficient data querying. On the other hand, database languages are able to process complex queries on huge databases, but without taking the ontology into account. There is thus a need for new languages and mechanisms, able to cope with the ever growing size of knowledge bases in the Semantic Web or in scientific domains.

This problem is related to two other problems identified as fundamental in KR:

• Query answering with incomplete information. Incomplete information means that it might be unknown whether a given assertion is true or false. Databases classically make the so-called closed-world assumption: every fact that cannot be retrieved or inferred from the base is assumed to be false. Knowledge bases classically make the open-world assumption: if something cannot be inferred from the base, and neither can its negation, then its truth status is unknown. The need of coping with incomplete information is a distinctive feature of querying knowledge bases with respect to querying classical databases (however, as explained above, this distinction tends to disappear). The presence of incomplete information makes the query answering task much more difficult.
• Reasoning with rules. Researching types of rules and adequate manners to process them is a mainstream topic in the Semantic Web, and, more generally a crucial issue for knowledge-based systems. For several years, we have been studying rules, both in their logical and their graph form, which are syntactically very simple but also very expressive. These rules, known as existential rules or Datalog$+$, can be seen as an abstraction of ontological knowledge expressed in the main languages used in the context of KB querying.

3.4 Inconsistency and decision making

While classical FOL is the kernel of many KR languages, to solve real-world problems we often need to consider features that cannot be expressed purely (or not naturally) in classical logic. The logic and graph-based formalisms used for previous points have thus to be extended with such features. The following requirements have been identified from scenarios in decision making, privileging the agronomy domain:

• to cope with inconsistency;
• to cope with defeasible knowledge;
• to take into account different and potentially conflicting viewpoints;
• to integrate decision notions (priorities, gravity, risk, benefit).

Although the solutions we develop require to be validated on the applications that motivated them, we also want them to be sufficiently generic to be applied in other contexts. One approach (but not the only possible one) consists in increasing the expressivity of our core languages, while trying to preserve their essential combinatorial properties, so that algorithmic optimizations can be transferred to these extensions.

4.1 Agronomy

Agronomy is a strong expertise domain in the area of Montpellier. Some members of GraphIK are INRAE researchers (computer scientists). We closely collaborate with the Montpellier research laboratory IATE, a join unit of INRAE and other organisms. A major issue for INRAE and more specifically IATE applications is modeling agrifood chains (i.e., the chain of all processes leading from the plants to the final products, including waste treatment). This modeling has several objectives. It provides better understanding of the processes from begin to end, which aids in decision making, with the aim of improving the quality of the products and decreasing the environmental impact. It also facilitates knowledge sharing between researchers, as well as the capitalization of expert knowledge and “know how”. This last point is particularly important in areas strongly related to local know how (like in cheese or wine making), where knowledge is transmitted by experience, with the risk of non-sustainability of the specific skills. An agrifood chain analysis is a highly complex procedure since it relies on numerous criteria of various types: environmental, economical, functional, sanitary, etc. Quality objectives involve different stakeholders, technicians, managers, professional organizations, end-users, public organizations, etc. Since the goals of the implied stakeholders may be divergent dedicated knowledge and representation techniques are to be employed.

4.2 Data journalism

One of today’s major issues in data science is to design techniques and algorithms that allow analysts to efficiently infer useful information and knowledge by inspecting heterogeneous information sources, from structured data to unstructured content. We take data journalism as an emblematic use-case, which stands at the crossroad of multiple research fields: content analysis, data management, knowledge representation and reasoning, visualization and human-machine interaction. We are particularly interested in issues raised by the design of data and knowledge management systems that will support data journalism. These systems include an ontology (which typically expresses domain knowledge), heterogeneous data sources (provided with their own vocabulary and querying capabilities), and mappings that relate these data sources to the ontological vocabulary. Ontologies play a central role as they act both as a mediation layer that glue together pieces of knowledge extracted from data sources, and as an inference layer that allow to draw new knowledge.

Besides pure knowledge representation and reasoning issues, querying such systems raise issues at the crossroad of data and knowledge management. In particular, although mappings have been widely investigated in databases, they need to be revisited in the light of the reasoning capabilities enabled by the ontology. More generally, the consistency and the efficiency of the system cannot be ensured by considering the components of the system in isolation (i.e., the ontology, data sources and mappings), but require to study the interactions between these components and to consider the system as a whole.

6.1 Awards

Ray Reiter Best paper award at the conference KR 2021 (ranked A*): “Capturing Homomorphism-Closed Decidable Queries with Existential Rules”, Camille Bourgaux, David Carral, Markus Krötzsch, Sebastian Rudolph, and Michaël Thomazo, 18th International Conference on Principles of Knowledge Representation and Reasoning 17.

7.1 New software

8.1 Ontology-mediated query answering

Participants: Jean-François Baget, David Carral, Michel Leclère, Marie-Laure Mugnier, Elie Najm, Guillaume Pérution-Kihli, Olivier Rodriguez, Federico Ulliana.

Ontology-mediated query answering is the issue of querying data through a conceptual layer formalized by knowledge (often called an ontology). From an abstract viewpoint, this gives rise to knowledge bases, composed of an ontology and a factbase (which can be seen as a database under incomplete data assumption). Answers to queries are logically entailed from the knowledge base, therefore taking into account inferences enabled by the ontology. In practice, the factbase may be not be given but instead computed from (several) data sources. This gives rise to a three-level architecture comprising the ontology, the data sources and the mapping between the two, known as OBDA (Ontology-Based Data Access). The key idea in OBDA is that a user expresses queries at a conceptual level, thereby abstracting from the actual data storage. The factbase may be materialised by triggering the mappings or it may remain virtual. In the latter case, the system rewrites these queries into queries on the data via the mapping, while integrating ontological reasoning.

To represent knowledge and reason with it, we study an expressive rule language, known as existential rules (or datalog+, as this framework generalizes the deductive database language datalog). Existential rules are also able to express powerful relational mappings (i.e., Global-Local-As-View mappings), which provide great flexibility to integrate heterogeneous data sources. Hence, a uniform language can be used to express both knowledge and mappings.

A fundamental tool to do reasoning with existential rules is a forward chaining process, called the chase: the rules are repeatedly applied to enrich the factbase, and query answering can then be solved by evaluating the query against the saturated factbase (as in a classical database system, i.e., with forgetting the ontological knowledge). In an OBDA context the factbase may remain virtual, in which case query-rewriting-based techniques are used, however the chase remains relevant as a reference tool to prove the correctness of the developed techniques. Indeed, the set of answers to a (conjunctive) query evaluated on the saturated factbase is exactly the set of answers to its rewriting evaluated on the data sources.

This year, we investigated three main issues:

• Optimisation of the chase by a new technique avoiding redundant computation;
• Optimisation of query answering in the presence of mapping by compiling reasoning into the mapping;
• Expressivity of existential rules as a query language.

8.2 Reasoning with conflicts and decision support

Participants: Pierre Bisquert, Patrice Buche, Madalina Croitoru, Martin Jedwabny, Rallou Thomopoulos.

In real-world applications, data is likely to generate inconsistencies in the presence of ontological knowledge, specially when it comes from several independent sources. In particular, data coming from different stakeholders, such as preferences and opinions, is generally conflicting. In order to use this data, for instance in a decision support setting, it is thus necessary to be able to reason in the presence of inconsistencies. In such a context, classical logical reasoning fails because any statement can be derived from a contradiction. Argumentation is one approach to this problem, where inference steps are represented as possibly conflicting arguments. To a set of arguments is naturally associated a graph in which arguments are nodes and conflicts are edges.

One interest of the argumentation framework is that it allows to define a variety of semantics for reasoning in the presence of inconsistencies, some of them having been shown to be semantically equivalent to repair-based approaches. Second, this framework naturally benefits from the explanatory potential of graphs, which is particularly interesting to help the users better understand the results of the reasoning.

This year, we have continued our investigations of the management of knowledge bases in presence of conflicts. Our work has been centered around two main topics: the management of conflicts among factual information and the management of conflicts between user preferences.

• In the first context we have investigated either the source of information (in our case the agent that is stating the facts) makes a difference in the management techniques. In order to do this we have proposed a framework that allows to determine the agent that has most contributed to an exchange. Furthermore, we have also investigated whether the query in itself might induce some changes in the management.
• Regarding the second context, we have placed ourselves in an applicative context that is getting more and more traction: ethical scenarios. In these scenarios the ethical preferences of the user play a major role but it is yet not clear how to elicit these preferences. To handle this issue, we have studied the interest of case-based reasoning (CBR) and probabilistic inductive logic programming (PILP).

10.1 International initiatives

10.2 International research visitors

10.3 European initiatives

10.4 National initiatives

11.1 Promoting scientific activities