The main research domain of GraphIK is Knowledge Representation and Reasoning (KRR) , which studies paradigms and formalisms for representing knowledge and reasoning on these representations. We follow a logic-oriented approach of this domain: the different kinds of knowledge have a logical semantics and reasoning mechanisms correspond to inferences in this logic. However, in the field of logic-based KRR, we distinguish ourselves by using 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 KRR languages: different kinds of conceptual graphs –historically our main focus– the Semantic Web language RDFS, 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 on graph-theoretic notions), with homomorphism as a core notion, 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 of languages and the computational tractability of reasoning in these languages.

We study KRR formalisms from three perspectives:

  • theoretical (structural properties, expressiveness, translations into other languages, problem complexity, algorithm design),
  • software (developing tools to implement theoretical results),
  • applications (which also feed back into theoretical work).

A crucial point is that we are interested in knowledge bases for real-world applications , which means in particular that: even if logical soundness and completeness are fundamental properties of a reasoning mechanism, its empirical relevance is important too; even if the theoretical algorithmic complexity is a key criterion for evaluating the efficiency of an algorithm, practical experiments are also needed; and besides fundamental theoretical problems, we also study problems that arise in practice even if they may not be well defined from a theoretical viewpoint (as it can be the case for KB validation, KB evolution, reasoning in presence of inconsistencies, query-answering mechanisms etc.), which involves clarifying and formalizing them.

GraphIK focuses on some of the main challenges in KRR :

  • ontology-based query answering , i.e., query answering taking an ontology into account and able to deal with large data sets,
  • reasoning with rule-based languages,
  • dealing with heterogeneous and with hybrid knowledge bases, i.e., composed of several modules that have their own formalism and reasoning mechanisms,
  • representing preferences and reasoning with preferences,
  • argumentative reasoning,
  • dealing with inconsistencies.

Research directions

GraphIK has three main scientific directions :

  • decidability, complexity and algorithms for problems in languages corresponding to first order logic fragments (with deduction being the fundamental problem),
  • representation of and reasoning with imperfect information and priorities,
  • the integration of theoretical tools to real knowledge-based systems.

Permanent link to this article: https://team.inria.fr/graphik/overview/