Classification of graph topologies by machine learning methods

Many objects of the real world, both living and man-made, may be described in the terms of graph theory and represented as graph data. One of the tasks of graph data analysis is to classify graph topologies. This work explored the possibilities of machine learning methods, and in particular graph neural networks (GNNs), to classify graphs with different topologies. The aim was to study the robustness of the classifiers based on graph convolutional networks depending on the samples they were trained on. The authors also compared solutions based on GNNs and non-graph classifiers, which were fed several graph characteristics. The non-graph methods, which included support vector machine, decision trees and linear discriminant analysis, demonstrated results comparable to GNNs with a single convolutional layer on the test sample, but overfitting was clearly visible on the validation sample. GNNs were less sensitive to the changes in the number of vertices. However, GNNs showed a large number of false alarms when classifying regular graphs.