PhD graduated
Departure date : 11/30/2009

Supervision : Bernadette BOUCHON-MEUNIER

Co-supervision : DETYNIECKI Marcin

Evolutionary Optimisation for Inexact Graph Isomorphism

The solution to the inexact graph matching problem is the key for defining any type of graph distance. It is even more complex than the exact graph isomorphism problem. On the one hand, inexact graph matching is a combinatorial optimization problem in NP taking into account perturbations inherent in noisy real world environments. Exact graph matching, on the other hand, is a decision problem for which it has not yet been shown if its complexity class is P and which applies only to exactly identical graphs. In this thesis, we study an approach based on genetic algorithms addressing both exact and inexact isomorphisms. We introduce several new crossover operators, some more general for use with any kind of permutation encoding, some specialized which include a greedy heuristic specific to graph matching. We conduct an exhaustive study in order to compare these operators with the existing ones, underlining their respective characteristics, advantages and disadvantages. Furthermore, we examine several aspects for enhancing the algorithm, both theoretical and practical ones, leading to faster execution, better precision or even the assurance of finding the global optimum. We combine the genetic algorithm with generalized black-box heuristics, such as local search, specialized heuristics such as the A* algorithm or practical tools like parallelization techniques. Our final aim is to present a method addressing all different types of graph matching problems, i.e. exact and inexact, isomorphisms of graphs having the same size and sub-graph isomorphisms. We illustrate the generality of our approach with three applications with very distinct properties which cover the different problem types.

Defence : 10/22/2009 - 14h30 - Site Passy-Kennedy - salle 549

Jury members :

Mme Bernadette Bouchon-Meunier
M Marcin Detyniecki
M Patrick Gallinari
Mme Evelyne Lutton [Rapporteur]
Mme Michèle Sebag [Rapporteur]
M El-Ghazali Talbi

2006-2014 Publications