A local branching heuristic for solving a Graph Edit Distance Problem

The Graph Edit Distance (GED) problem is a very interesting problem that relates to Graph Matching (GM) problems, wherever a graph models a problem-defined pattern. Solving the GED problem leads to compute the matching between two given graphs by minimizing their GED, which is also called a dissimilarity measure between them. It has many application domains such as structural pattern recognition and chemical Structure-Activity Relationships (SAR). GED(EnA) (Edges no Attributes) is a sub-problem of the GED problem that deals with a special type of graphs where edges do not carry attributes. They are both NP-hard problems and it is difficult to find the optimal solution in reasonable time. Many heuristics exist in the literature that give suboptimal solutions. Some other works have used mathematical programming tools to model and solve these two problems. The present work takes advantage of a powerful Mixed Integer Linear Program (MILP) formulation and proposes a heuristic called Local Branching to solve the GED(EnA )problem. Mainly, a MILP model is iteratively modified by adding additional constraints to define neighborhoods in the solution space, which are explored using a black-box solver. A problem-dependent exploration is performed to find efficient solutions. Lastly, the proposed heuristic is evaluated considering two factors: its computational time and solution quality against the heuristics available in the literature and exact methods. The computational experiments reported in this paper show that the proposed local branching heuristic strongly outperforms the existing heuristics for the GED(EnA) problem. (C) 2018 Elsevier Ltd. All rights reserved.