摘要
提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Clus-ter-TopK.Greedy-TopK先产生频繁子图,然后按增量贪心方式选择K个图模式.Cluster-TopK先挖掘频繁子图的一个代表模式集合,然后从代表模式中按增量贪心方式选择K个图模式.当意义度量满足submodular性质时,Greedy-TopK能提供近似比保证.Cluster-TopK没有近似比保证,但比Greedy-TopK更高效.实验结果显示,在结果可用性方面,文中提出的Top-K挖掘优于传统的Top-K挖掘.Cluster-TopK比Greedy-TopK快至少一个数量级.而且,在质量和可用性方面,Cluster-TopK的挖掘结果非常类似于Greedy-TopK的挖掘结果.
This paper proposes a novel problem of mining top-k graph patterns that jointly maximize some significance measure from graph databases. By exploiting the concepts of information theory, it gives two problem formulations, MES and MIGS, and proves that they are NP-hard. Two efficient algorithms, Greedy-TopK and Cluster-TopK, are proposed for this new problem. Greedy-TopK first generates frequent subgraphs, and then incrementally and greedily selects K graph patterns from frequent subgraphs. Cluster-TopK first mines a set of representative patterns for frequent subgraphs, and then incrementally and greedily selects K graph patterns from representative patterns. When a given significance measure satisfies the submodular property, Greedy-TopK can provide tight approximation bound. Cluster-TopK has no approximation bound guarantee but is more efficient than Greedy-TopK. Extensive experimental results demonstrate that the Top-K mining proposed in this paper is superior to the traditional Top-K mining in terms of results usefulness. Cluster-TopK can achieve at least an order of magnitude speedup than Greedy-TopK, while achieving comparable mining results in terms of quality and usefulness.
出处
《计算机学报》
EI
CSCD
北大核心
2010年第2期215-230,共16页
Chinese Journal of Computers
基金
国家"九七三"重点基础研究发展规划项目基金(2006CB303005)
国家自然科学基金(60533110
60773063)资助~~
关键词
图挖掘
图数据库
频繁子图
代表模式
联合熵
信息增益
graph mining
graph database
frequent subgraph
representative pattern
joint entropy
information gain
