Mining non-redundant synergy graph patterns from two classes of graphs

Graph patterns are widely used to define the feature space for building an efficient graph classification model. Synergy graph patterns refer to those graphs, where the relationships among the nodes are highly inseparable. Compared with the general graph patterns, synergy graph patterns which have much higher discriminative powers are more suitable as the classification features. This paper investigates the problem of mining non-redundant synergy graph patterns from two classes of graphs. By guaranteeing the property that the discriminative powers of synergy graph patterns are much higher than all their subgraphs, mining non-redundant synergy graph patterns can dramatically reduce the number of results and still capture the strong discriminative powers synergy graph patterns. However, finding all non-redundant synergy graph patterns is computationally challenging because all their subgraphs should theoretically be checked. Also, through studying the properties of non-redundant synergy graph patterns, the corresponding pruning techniques are proposed. Moreover, two fast synergy graph pattern detection methods are proposed based on the bound estimation of the discriminative powers. Based on those techniques, an efficient depth-first algorithm GINS is presented for this mining problem. Extensive experiments are conducted on a series of real-life and synthetic datasets. The results show that GINS is more efficient than two representative competitors. Besides, when the non-redundant synergy graph patterns are considered, the classification accuracy is improved much.