Présentation de Mostafa Darwiche

A Local Branching Heuristic for the Graph Edit Distance Problem

Graph Edit Distance (GED) problem is an error-tolerant graph matching problem. It provides a dissimilarity measure between two graphs, by computing the cost of editing one graph to transform it into another. The set of edit operations are substitution, insertion and deletion, and can be applied on both vertices and edges. Solving the GED problem consists of finding the set of edit operations that minimizes the total cost. GED, by concept, is known to be flexible because it has been shown that changing the edit cost properties can result in solving other matching problems like maximum common subgraph, graph and subgraph isomorphism. Also, GED problem has many applications such as Image Analysis, Handwritten Document Analysis, Malware Detection, Bio- and Chemoinformatics and many others. GED is a NP-Hard problem, so the optimal solution cannot be obtained in polynomial time. Nevertheless, many heuristics have been proposed to compute good solutions in reasonable amount of time. GED is treated in the exact sense as well, by mathematical programming tools to produce Mixed Integer Linear Programs (MILP).

We proposes the use of Local Branching (LocBra) heuristic, which is well-known in Operational Research domain. It is presented originally as a general metaheuristic for MILP models. It makes use of a MILP solver in order to explore the solution space, through a defined branching scheme. As well, it involves techniques, such as intensification and diversification during the exploration. To benefit from the efficiency of these techniques, a LocBra version is designed and adapted to handle the GED problem. Also, the original diversification is modified to consider information about the problem that will improve the exploration and return better solutions. Subsequently, it is evaluated and compared with existing competitive heuristic algorithms.