Improving Graph Classification by Isomap

摘要

Isomap emerged as a powerful tool for analyzing input patterns on manifolds of the underlying space. It builds a neighborhood graph derived from the observable distance information and recomputes pairwise distances as the shortest path on the neighborhood graph. In the present paper, Isomap is applied to graph based pattern representations. For measuring pairwise graph dissimilarities, graph edit distance is used. The present paper focuses on classification and employs a support vector machine in conjunction with kernel values derived from original and Isomap graph edit distances. In an experimental evaluation on five different data sets from the IAM graph database repository, we show that in four out of five cases the graph kernel based on Isomap edit distance performs superior compared to the kernel relying on the original graph edit distances.