Sites Inria

Version française

GRAPHIK Research team

GRAPHs for Inferences and Knowledge representation

Team presentation

GraphIK is a team created in 2010. It is located at LIRMM (Laboratory of Informatics Robotics and Microeclectronics of Montpellier) and involves researchers from INRIA, INRA and the University of Montpellier.

The main research domain of GraphIK is Knowledge Representation and Reasoning (KRR). We follow a logic-oriented approach of the field but our specificity lies in our graph-based vision of KRR. GraphIK focuses on some of the main challenges in KRR, such as querying large knowledge bases, dealing with hybrid knowledge bases (i.e., composed of several modules having their own reasoning mechanisms), or reasoning with imperfect knowledge (i.e., vague, uncertain, partially inconsistent, ...).

Our objective is to study and develop KRR formalisms with properties of genericity, readability and algorithmic efficiency, and to validate them in real-world knowledge-based systems.

To reach this aim, we work along three complementary scientific axes. The first axe studies decidability, complexity and algorithms for languages corresponding to fragments of classical logic. The second axe extends these fragments to perform other kinds of reasoning, while keeping a good complexity/expressivity tradeoff. The third axe is devoted to integrating the theoretical tools into real-world knowledge-based systems.

Research themes

  • Decidability, complexity and algorithms. Our kernel formalisms can be seen as specific fragments of classical first-order logic. The represented knowledge can also be seen as labeled graphs and inferences can be based on graph-theoretic notions (such as homomorphism), which allows to take advantage of the structural properties of knowledge pieces. Our objective is to identify decidable fragments which are as large as possible, while keeping a good complexity/expressivity trade-off, and to develop efficient reasoning algorithms. We aim at obtaining results sufficiently generic to impact several data and knowledge representation languages: description logics, conceptual graphs, database languages, semantic web languages.
  • Non-classical features. Classical logic is not able to express certain kinds of reasoning needed in applications. Namely, our priviledged application to agronomy and agrifood chains requires to deal with imperfect knowledge (vague, uncertain, information described at different levels of precision, partially inconsistent, ...), to reason with conflicting viewpoints, or to argue a decision. Our approach consists in extending the kernel languages developed in the first axe, while trying to keep their combinatorial properties, hence the decidability, complexity and algorithmic results already obtained.
  • Integration of theoretical results into real-world knowledge-based systems. We pursue here a double objective. On one hand, we aim at validating the languages and mechanisms of the preceding axes on real-world applications. On the other hand, we try to abstract problems that arise in practice and to formalize them to feed back into the theoretical studies.
  • International and industrial relations

    • International (Research): King's College (UK), Univ. of Southampton (UK), Univ. of Karlsruhe (Germany), KMI Open University (UK), IIT-BAS (Bulgaria),
    • International (R&D): Community Sense (Netherlands), MIMOS (Malaysia)
    • National (R&D, industrial): ABES (Bibliographical French Agency for Universities), INA (National Institute for Audiovisual), Antidot, Mondeca

    Keywords: Knowledge Representation and Reasoning based on Graphs and Logics Complexity and Algorithms Knowledge and Data Engineering Decision Support Systems