Combining Graph Seriation and Substructures Mining for Graph Recognition

Many interesting applications of Pattern Recognition techniques can take advantage in dealing with labeled graphs as input patterns. To this aim, the most important issue is the definition of a dissimilarity measure between graphs. In this paper, we outline an ensemble of methods for dealing with such data,focusing on two specific methods. The first one is simply based on a global alignment approach applied to seriated versions of the graphs. The second one is a two-stages method, which applies a recurrent substructures analysis to the seriated graphs, individuating a set of frequent subsequences, employed for embedding the graphs into a real valued feature vector space. Tests have been performed by synthetically generating a set of classification problem instances with increasing problem hardness, and with a shared benchmarking database of labeled graphs.