On the Necessity of Graph Kernel Baselines

Naturally, graph structured data is not easy to learn from. As opposed to itemsets which can be represented by a table of fixed length, there is no obvious representation language for graphs which allows for an easy similarity measure in order to perform e.g. classification tasks on sets of graphs. There have been introduced numerous graph kernels which tackle the problem of defining a suitable similarity between graphs by incorporating structural information. In this article, however, we revert to the very simplistic approach which is to regard a graph as a (multi-) itemset made up of node and edge labels. We consider our method as a baseline and compare it to several established graph kernels on a wide range of benchmark datasets. Our observations suggest that for the overwhelming number of available datasets, actually utilizing the graphs’ structure in graph kernels does not significantly improve the classification accuracy.