Optimized dissimilarity space embedding for labeled graphs

This paper introduces a new general-purpose classification system able to face automatically a wide range of classification problems for labeled graphs. The proposed graph classifier explicitly embeds the input labeled graphs using the dissimilarity representation framework. We developed a method to optimize the dissimilarity space representation estimating the quadratic Rényi entropy of the underlying distribution of the generated dissimilarity values. The global optimization governing the synthesis of the classifier is implemented using a genetic algorithm and it is carried out by means of two operations that perform prototype selection and extraction on the input set of graphs. During the optimization step, we adopted a suitable objective function which includes the classification accuracy achieved by the whole classification model on a validation set. Experimental evaluations have been conducted on both synthetic and well-known benchmarking datasets, achieving competitive test set classification accuracy results with respect to other state-of-the-art graph embedding based classification systems.