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.
