关键词: 图分类, 图核, 成对约束, 半监督降维

Abstract: Graph based data representation and analysis have received more and more attention in machine learning community. Most previous studies focus on designing an appropriate graph kernel which measures the similarity rela- tionship between graph data. Once the graph kernel is constructed, standard support vector machine (SVM) can be used for graph classification. This paper extends graph kernel methods for graph classification. It firstly performs dimensionality reduction using kernel principal component analysis (kPCA) on those high-dimensional data induced by graph kernel to obtain corresponding low-dimensional data with vector representation, and then analyzes those new data using conventional machine learning methods. Furthermore, it introduces supervision information in the form of pairwise constraints into kPCA and proposes the graph kernel based semi-supervised dimensionality reduc-tion algorithm. Experimental results on MUTAG and PTC data sets validate the effectiveness of the proposed methods.

Key words: graph classification, graph kernel, pairwise constraints, semi-supervised dimensionality reduction