Application of graph embedding to solve graph matching problems

Graphs have very interesting properties for object representation in pattern recognition. However, graph matching algorithms are usually computationally complex. In addition, graphs are harder to manipulate and operate than feature vectors. In the last years, some attempts have been made to combine the best of the graph and the vector domains in order to get the advantages of both worlds. In this paper we review some of these works on graph kernels and graph embedding and we show how graph embedding can be used to obtain accurate and efficient approximations of the median graph. The median graph can be seen as the representative of a set of graphs but its application has been very limited up to now due to computational reasons. With this new approach, we can obtain an approximate median graph using real databases containing large graphs. Mots-clés : Graph Matching, Graph Embedding, Graph Kernels, Vector Spaces, Median Graph tors. Secondly, the repository of algorithmic tools based on graphs is quite limited when compared to the tools available for patterns represented using feature vectors. This is mainly due to the fact that vectors are simple structures with good mathematical properties that can be readily manipulated algebraically. For this reason, new trends in structural pattern recognition have been proposed merging both worlds in order to extend the available statistical tools to the graph domain [BUN 05]. In this way, graph kernels permit to compute the dot product of the representation of a pair of graphs in a vector space without having to define the explicit transformation between the graphs and the vector space. As a consequence all classification algorithms based on the computation of a dot product, such as Support Vector Machines (SVM) become immediately available for graphs. On the other hand, graph embedding aims to find an explicit transformation between graphs and a vector space. In this way, we can give a semantic interpretation to this transformation. In addition we can also manipulate the vectors resulting from this transformation with all the mathematical machinery that can be applied to vectors. We are not restricted to the dot product. In this paper, we firstly review the main techniques used to define graph kernels and graph embedding in sections 2 and 3, respectively. Then, in section 4 we show the application of graph embedding to a particular complex graph matching problem : the computation of the median graph. In this section we introduce the concept of median graph as a representative of a set of graphs and then, we describe how it can be efficiently computed using graph embedding. We also show some results of its application to real pattern recognition problems. Finally, in section 5 we state some conclusions and point out some challenges for the future.Peer ReviewedPostprint (published version