Graph-based pattern recognition on spectral reduced graphs

Graph-based pattern recognition - in particular in conjunction with large graphs - is often computationally expensive. This hampers, or makes it at least challenging, to employ graph-based representations for real world data. To address this issue, we propose a method for reducing the size of the underlying graphs to their most important substructures using spectral graph clustering. The proposed method partitions the nodes of the graphs into clusters and then merges each cluster into supernodes. The motivation of this procedure is to reduce the computational cost of any graph comparison algorithm while maintaining the accuracy of the final classification. To assess the benefits and limitations of our method, we conduct thorough experiments on nine real-world datasets with different levels of graph reductions. The classification is obtained by four different graph classifiers (viz. a KNN based on graph edit distance, two SVMs based on a shortest path graph and a Weisfeiler-Lehman graph kernel, as well as a graph neural network). The results indicate that we can reduce computation time by up to two orders of magnitude without substantially degrading the classification accuracy.