二分类图上的非冗余协同图模式挖掘算法

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