Comparing performance of graph matching algorithms on huge graphs

Graph matching algorithms are gaining more and more interest in the last years from different scientific communities; indeed, they allow comparing any kind of objects represented using their intrinsic structure, represented in terms of attributed relational graphs. The challenge is to make these algorithms able to provide solutions over huge graphs, with many thousands of nodes, and in a time that is adequate for practical applications; in this paper, we propose a comparison among the best performing algorithms available in the literature on a variety of very large graph databases used for performance assessment. The chosen datasets vary in terms of graph structure, size, density, presence of symmetric or repetitive substructures; this variability makes such datasets very challenging. The aim of this paper is to characterize the performance of the compared algorithms with respect to the typology, the size and other structural properties of the graphs; in this way, the user may consciously select the best suited algorithm for a given purpose. The results of an impressive experimentation that required 556 days of machine time are here presented and extensively discussed.