A Graph Classification Method Based on Support Vector Machines and Locality-Sensitive Hashing

Graphs classification is a relevant problem that arises in many disciplines. Using graphs directly instead of vectorization allows exploiting the intrinsic representations of the data. Support Vector Machines (SVM) is a supervised learning method based on the use of graph kernel functions used for this task. One of the problems of SVM, as the number of samples increases, is the cost of storing and solving the optimization problem related to SVM. In this work, we propose a method capable of finding a small representative subset of the whole graph data set such that an approximate solution of the SVM optimization problem can be obtained in a fraction of the time, and without significantly degrading the classification prediction error. The method is based on the use of Locality-Sensitive Hashing for projecting over the Hilbert spaces defined by appropriate graph kernels that measure similarity between the graphs. A description of the algorithm, as well as numerical results using two graph kernels (Simple Product and Random Walk) on simulated and real life data sets are presented. The numerical experiments compare the training times and the classification error between the SVM obtained with our smart sampling approach, and the SVM obtained over the complete data set or over a random sub-sample. The results offer evidence of the advantages of our proposal for solving large scale graph classification problems when using SVM.