An experimental study of graph classification using prototype selection

In structural pattern recognition, a major drawback of graph based representation is the lack of algorithmic tools. To overcome this lack, we embed graphs in vector spaces by means of prototype selection and graph edit distance, thus making them available to all algorithms of statistical pattern recognition that operate on feature vectors. In previous work a similar procedure was applied. However, the only classifier used within this framework was support vector machine (SVM). In the present paper, we significantly extend the scope of the previous work and present an experimental study where, in addition to SVM, a number of other well established classifiers from statistical pattern recognition are used for graph classification. On a total of five different graph data sets of diverse nature it is demonstrated that the proposed graph embedding in conjunction with standard classifiers from statistical pattern recognition has great potential to outperform classification methods applied in the original graph domain.