Symmetry Kernel for Graph Classification

This paper presents a novel way to conduct machine learning analysis on graphs and empirically evaluates it. We can not perform such analysis on non-fixed length feature vectors, so first, we must find a way to represent graphs as such. We propose a graph kernel based on graph automorphisms, also known as graph symmetries. We then empirically evaluate the classification accuracy of three machine learning algorithms, SVM, Random Forest, and AdaBoost, using this novel graph kernel against two existing graph kernels and a naive baseline. The models reach a higher classification accuracy on some datasets using our Symmetry kernels than the graphlet kernel and Weisfeiler-Lehman kernel despite our kernel constructing far smaller feature vectors than the existing approaches.