中文摘要：

图模式广泛应用于构建高效图分类模型的特征空间识别.协同图模式是一种内部节点高度相关的图结构,与普通图模式相比,协同图模式具有更高的区分能力,从而更加适用于分类模型的特征选择.文中研究了从二分类图中挖掘非冗余协同图模式的问题,通过限制协同图模式的区分能力远远高于其所有子图模式的非冗余性质,大幅度减少了挖掘结果的数量,同时保留了具有强区分能力的协同图模式.由于协同图模式理论上必须检测其所有子图是否满足约束条件,挖掘它们非常具有计算挑战性.基于非冗余协同图模式的多种特性,提出相对应的削减规则;通过对区分能力的边界估计,提出两个快速检测非冗余协同图模式方法,在此基础上给出了一种高效的深度优先挖掘算法GINS.大量真实与合成数据集上的实验结果表明,GINS算法明显优于其他两个代表性算法,作为图分类模型的分类特征时,非冗余协同图模式获得了较高的分类精度.

英文摘要：

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 thatGINS is more efficient than two representative competitors.Besides,when the non-redundant synergy graph patterns are considered,the classification accuracy is improved much.