ON DISSIMILARITY EMBEDDING OF GRAPHS IN VECTOR SPACES

Recently, in pattern recognition and related fields an emerging trend of representing objects by graphs can be observed. In fact, graph based object representation offers a versatile alternative to vectorial representations. The domain of graphs, however, contains only little mathematical structure. That is, most of the basic mathematical operations, actually required by many standard pattern recognition algorithms, are not available for graphs. Consequently, we observe a severe lack of algorithmic tools in the domain of graphs. The present chapter aims at introducing a novel approach for graph embedding in vector spaces. The rationale for such an embedding is to bridge the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. The key-idea of the proposed embedding method is to use the distances of an input graph to a number of training graphs, termed prototypes, as a vectorial description of the graph. In contrast with some other graph embedding methods, there are no restrictions on the type of graphs the proposed embedding framework can deal with. Moreover, the dissimilarity embedding of graphs is particularly able to cope with noisy data. In an experimental evaluation we show that the proposed methodology of first embedding graphs in vector spaces and then applying a statistical classifier has significant potential to outperform classifiers that directly operate in the graph domain.