Abstract
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.
Paper Type
Short Paper
DOI
10.62036/ISD.2024.102
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.
Recommended Citation
Kuhar, Y. & Čibej, U. (2024). Symmetry Kernel for Graph Classification. In B. Marcinkowski, A. Przybylek, A. Jarzębowicz, N. Iivari, E. Insfran, M. Lang, H. Linger, & C. Schneider (Eds.), Harnessing Opportunities: Reshaping ISD in the post-COVID-19 and Generative AI Era (ISD2024 Proceedings). Gdańsk, Poland: University of Gdańsk. ISBN: 978-83-972632-0-8. https://doi.org/10.62036/ISD.2024.102