Normalized graph compression distance – A novel graph matching framework

Computing dissimilarities between pairs of graphs is a common task in many pattern recognition applications. A widely used method to accomplish this task is graph edit distance (GED). However, computation of exact GED is challenging due to its exponential time complexity with respect to the size of the underlying graphs. The major contribution of the present paper is that we introduce a complementary – and much faster – method to compute dissimilarities between pairs of graphs. Our novel framework involves a compressor-based metric that is adapted to the graph domain. Basically, the compressor-based metric identifies regularities in compressed graphs and assigns smaller distances to pairs of graphs that are comparable and are thus assumed to belong to the same class. To assess the effectiveness of the proposed graph matching framework, we perform a series of evaluations on eleven real-world datasets. It turns out that the novel matching framework performs equally well as, or even better than, GED, yet with significantly lower computation time. • We propose a novel graph matching termed Normalized Graph Compression Distance (NGCD) • We introduce a pre-processing step for NGCD that improves the classification accuracy. • We conduct empirical evaluations on 11 datasets to assess the benefits of NGCD. • We find that our framework NGCD outperforms the widely used graph edit distance.