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.

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

Paper Type

Short Paper

DOI

10.62036/ISD.2024.102

Download

Share

COinS
 

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.