Heuristics for the generalized median graph problem

Structural approaches for pattern recognition frequently make use of graphs to represent objects. The concept of object similarity is of great importance in pattern recognition. The graph edit distance is often used to measure the similarity between two graphs. It basically consists in the amount of distortion needed to transform one graph into the other. The median graph of a set S of graphs is a graph of S that minimizes the sum of its distances to all other graphs in S. The generalized median graph of S is a graph that minimizes the sum of the distances to all graphs in S. It is the graph that best captures the information contained in S and may be regarded as the best representative of the set. Exact methods for solving the generalized median graph problem are capable to handle only a few small graphs. We propose two new heuristics for solving the generalized median graph problem: a greedy adaptive algorithm and a GRASP heuristic. Numerical results indicate that both heuristics can be used to obtain good approximate solutions for the generalized median graph problem, significantly improving the initial solutions and the median graphs. Therefore, the generalized median graph can be effectively computed and used as a better representation than the median graph in a number of relevant pattern recognition applications. This conclusion is supported by experiments with a classification problem and comparisons with algorithm k-NN.