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.

2006-2014 Publications

• 2014
  • N. Labroche, M. Detyniecki, Th. Bärecke : “Comparaison de bornes théoriques pour l’accélération du clustering incrémental en une passe”, EGC 2014, vol. RNTI-E-26, Revue des Nouvelles Technologies de l'Information, Rennes, France, pp. 467-478 (2014)
• 2013
  • N. Labroche, M. Detyniecki, Th. Bärecke : “Accelerating one-pass clustering by cluster selection racing”, Proceedings of IEEE International Conference on Tools with Artificial Intelligence - ICTAI 2013, Washington DC, United States, pp. 491-498, (IEEE) (2013)
• 2011
  • Th. Bärecke, B. Bouchon‑Meunier, M. Detyniecki : “Fuzzy Present Value”, IEEE Symposium on Computational Intelligence for Financial Engineering & Economics (IEEE CIFEr), Paris, France, pp. 75-80, (IEEE) (2011)
  • Th. Bärecke, M.‑J. Lesot, H. Akdag, B. Bouchon‑Meunier : “Prise en compte du réseau de sources pour la fusion d’informations”, Atelier Fouille de données complexes, Journées Francophones Extraction et Gestion des Connaissances, EGC'11, vol. RNTI-E-20, Revue des Nouvelles Technologies de l'Information, Brest, France, pp. 323-324 (2011)
  • Th. Bärecke, Ch. Mansilla, S. Avril, B. Bouchon‑Meunier, M. Detyniecki, F. Werkoff : “Fuzzy sets for assessing the profitability of hydrogen production by the sulphur-iodine thermochemical cycle”, International journal of energy, environment, economics, vol. 19 (1-2), pp. 119-132, (Nova Science Publishers) (2011)
  • Th. Bärecke, M. Bendris, M. CAMPEDEL, M. Detyniecki, D. Marraud : “Traitement des modalités image et vidéo”, chapitre de Sémantique et multimodalité en analyse de l'information, pp. 97-142, (Hermes) (2011)
• 2010
  • Th. Bärecke, Th. Delavallade, M.‑J. Lesot, F. Pichon, H. Akdag, B. Bouchon‑Meunier, Ph. Capet, L. Cholvy : “Un modèle de cotation pour la veille informationnelle en source ouverte”, 6^e colloque Veille Stratégique Scientifique & Technologique, VSST2010, Toulouse, France (2010)
  • Th. Bärecke, Th. Delavallade, M.‑J. Lesot, F. Pichon, H. Akdag, B. Bouchon‑Meunier, Ph. Capet, L. Cholvy : “Des données textuelles au renseignement : vers un modèle global de cotation”, Atelier COTA (Cotation des informations), Journées Francophones d'Ingénierie des Connaissances, IC'10, Nîmes, France, pp. 87-98 (2010)
• 2009
  • Th. Bärecke : “Isomorphisme inexact de graphes par optimisation évolutionnaire”, thesis, phd defence 10/22/2009, supervision Bouchon-meunier, Bernadette, co-supervision : Detyniecki, Marcin (2009)
• 2008
  • Th. Bärecke, E. Kijak, M. Detyniecki, A. Nürnberger : “Organizing Multimedia Information with Maps”, chapter in Recent Advances in Computational Intelligence in Multimedia Processing, vol. 96, Studies in Computational Intelligence, pp. 493-509, (Springer) (2008)
• 2007
  • Th. Bärecke, M. Detyniecki : “Memetic algorithms for inexact graph matching”, CEC: IEEE Congress on Evolutionary Computation, Singapore, Singapore, pp. 4238-4245, (IEEE) (2007)
  • Th. Bärecke, M. Detyniecki : “Combining exhaustive and approximage methods for improved sub-graph matching”, Advances in Pattern Recognition - IWAPR Workshop, Plymouth, United Kingdom (2007)
  • Th. Bärecke, M. Detyniecki, S. Berretti, A. Del Bimbo : “Genetic approximate matching of attributed relational graphs”, Pascal workshop on Learning from and with Graphs, Alicante, Spain (2007)
• 2006
  • Th. Bärecke, Ch. Mansilla, S. Avril, B. Bouchon‑Meunier, M. Detyniecki, F. Werkoff : “On the use of genetic algorithms and fuzzy logics for the assessment of the cost of the hydrogen to be produced by advanced processes”, Fuel Cell Seminar, Honolulu, Hawaii, United States (2006)
  • Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “Using Self-Organizing Maps to Support Video Navigation”, Proc. of 16^th Intl. Conf. on Artificial Neural Networks (ICANN 2006), vol. 4131, Lecture Notes in Computer Science, Athens, Greece, pp. 396-405, (Springer) (2006)
  • Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “Summarizing Video Information using Self-Organizing Maps”, IEEE International Conference on Fuzzy Systems - FUZZ-IEEE, Vancouver, Canada, pp. 540-546, (IEEE) (2006)
  • Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “Video Navigation based on Self-Organizing Maps”, Proc. of the International Conference on Image and Video Retrieval (CIVR), vol. 4071, Lecture Notes in Computer Science, Tempa, Arizona, United States, pp. 340-349, (Springer) (2006)
  • Th. Bärecke, E. Kijak, A. Nürnberger, M. Detyniecki : “VideoSOM: A SOM-based Interface for Video Browsing”, Proc. of the International Conference on Image and Video Retrieval (CIVR), vol. 4071, Lecture Notes in Computer Science, Tempa, Arizona, United States, pp. 506-509, (Springer) (2006)