Book: Graph Classification and Clustering Based on Vector Space Embedding
Publisher: World Scientific Publishing
Due to the ability of graphs to represent properties of entities and binary relations at the same time, a growing interest in graph based object repre sentation can be observed in science and engineering. Yet, graphs are still not the common data structure in pattern recognition and related fields. The reason for this is twofold. First, working with graphs is unequally more challenging than working with feature vectors, as even basic mat hematic operations cannot be defined in a standard way for graphs. Second, we observe a significant increase of the complexity of many algorithms when graphs rather than feature vectors are employed. In conclusion, almost none of the standard methods for pattern recognition can be applied to graphs without significant modifications and thus we observe a severe lack of graph based pattern recognition tools.
This thesis is concerned with a fundamentally novel approach to graph based pattern recognition based on vector space embeddings of graphs. We aim at condensing the high representational power of graphs into a compu tationally efficient and mathematically convenient feature vector. Based on the explicit embedding of graphs, the considered pattern recognition task is eventually carried out. Hence, the whole arsenal of algorithmic tools read ily available for vectorial data can be applied to graphs. The key idea of our embedding framework is to regard dissimilarities of an input graph to some prototypical graphs as vectorial description of the graph. Obviously, by means of such an embedding we obtain a vector space where each axis is associated with a prototype graph and the coordinate values of an em bedded graph are the distances of this graph to the individual prototypes.