Ph.D Dissertation

My PhD dissertation entitled Anytime and Distributed Approaches for Graph Matching was supervised by Dr. Romain Raveaux, Prof. Jean-Yves Ramel and Prof. Patrick Martineau.

The dissertation tackles the problem of graph matching (GM) in Pattern Recognition (PR). It focuses on a generic framework called Graph Edit Distance(GED). Proposing an exact algorithm that can scale up to match large graphs involved in PR tasks is a great challenge. In the dissertation, two promising ways to cut-off the computational time are: search space pruning and distributed algorithms. We first propose a depth-first GED algorithm which requires less memory and search time. An evaluation of all possible solutions is performed without explicitly enumerating all of them. Candidates are discarded using an upper and lower bounds strategy. This algorithm is then converted to an anytime one by integrating anytime properties inside it. To go one step further and to be able to match large graphs, this algorithm is also extended using some parallel and distributed fashions. A graph matching repository dedicated to scalability is also proposed. In this repository, low level information like graph edit distances and their matching correspondences are provided. Moreover, a set of performance evaluation metrics to assess the performance of GED methods are put forward.

This dissertation brings into question the usual evidences saying that it is impossible to use exact error-tolerant GM methods in real-world applications when matching large graphs, or even in a classification context. However, we argue and show that a new type of GM, referred to as anytime methods, can be successful in a graph-level context as well as a classification one.

The dissertation is publicly available at http://www.rfai.li.univ-tours.fr/PublicData/PhD/PhD2016zeina.pdf

Take a look at the slides of the defense. It was a travel of 45 minutes across the world of Graph Matching. The idea is inspired by the journal paper of Mario Vento entitled A long trip in the charming world of graphs for Pattern Recognition ;-)