A class-specific metric learning approach for graph embedding by information granulation

Graphs have gained a lot of attention in the pattern recognition community thanks to their ability to encode both topological and semantic information. Despite their invaluable descriptive power, their arbitrarily complex structured nature poses serious challenges when they are involved in learning systems. Typical approaches aim at building a vectorial representation of the graph in a suitable embedding space by leveraging on the selection of relevant prototypes that enable the use of common pattern recognition methods. An emerging paradigm able to synthesize prototypes in a data-driven fashion can be found in Granular Computing. Nonetheless, these methods often require a core dissimilarity measure defined directly in the graph domain that usually relies on a set of suitable parameters which are heavily problem-dependent. The automatic selection of these parameters is of utmost importance for building embedding spaces able to preserve the semantic contents between the structured and vector domains. In this paper, we propose an evolutionary-based approach for learning multiple dissimilarity measures tailored on each of the problem-related classes for the classification problem at hand. The learnt class-specific metrics contribute in synthesizing prototypes with high informative content related to each class by means of a Granular Computing approach. Such prototypes induce an embedding space where the graph classification can take place with common pattern recognition techniques for vector data. Tests conducted on publicly available datasets corroborate the effectiveness of the proposed approach both in terms of learning performances and interpretability of the model, as measured by the classification accuracy and number of meaningful prototypes considered in the synthesized model.