Graph-based representation and reasoning in artificial intelligence

Dr. Madalina Croitoru, Associate Professor, University Montpellier 2, France

New challenges, problems, and issues have emerged in the context of Artificial Intelligence (AI), involving the logical manipulation of increasingly large information sets. Therefore, current research is faced with a challenge of developing knowledge representation structures optimized for large scale reasoning. In this course we give three examples of graph based representation and reasoning in AI that open the way to new graph inspired, optimisations. The three detailed domains are: conjunctive query answering, combinatorial auctions and argumentation. The graph operations used for reasoning are labelled homomorphism, max flows and graph colouring. The course will also give an overview of the results from the last three editions of the IJCAI GKR (GRAPH STRUCTURES FOR KNOWLEDGE REPRESENTATION AND REASONING) workshop co-organised by the speaker. Since the GKR workshop addresses exactly the topic of the course, it will allow students to have a fresh view of the current approaches and open problems in the field.

The course is organised in five parts:

1. The interest for graph based representation and reasoning in AI. Formulation of the problem. Desirable properties.
   
2. Example 1: Conjunctive Query Answering and labelled graph homomorphism. The Conjunctive Query Answering problem. Conceptual Graphs. Soundness and completeness of projection in conceptual Graphs and entailment. Rules and Constraints.
   
3. Example 2: Combinatorial Auctions and max flows. Combinatorial Auctions. Representing bids using network flows. Winner Determination and max flows. Coalition Formation.
   
4. Example 3: Argumentation and graph colouring. Abstract argumentation. Extensions and admissibility. Labelling and graph colouring.
   
5. Overview of the past three editions of GKR and identification of current issues and open problems.

El curso será dictado en inglés. Para cursar, es necesario tener conocimientos elementales de teoría de grafos, lógica proposicional y lógica de primer orden. La evaluación consistirá en un examen con modalidad "take-home".

Acerca de la profesora

Dr. Madalina Croitoru obtained her PhD in 2006 from the University of Aberdeen with a thesis on improving Conceptual Graphs applicability in Artificial Intelligence. After two years of postdoctoral research in the IAM group at the University of Southampton she had joined the University of Montpellier 2 as Associate Professor. Her current research interests include graph based models and their applicability in various Artificial Intelligence field (ontological conjunctive query answering, coalition formation in multi agent systems, combinatorial auctions, argumentation, constraint satisfaction, etc.). In complement of her research activities she has initiated a workshop series on Graph based Knowledge Representation and Reasoning (GKR@IJCAI workshop series).