作为一种通用的数据结构,图可以用来表示数据对象之间的各种复杂关系。例如:图可以表示化合物的分子结构,蛋白质交互网络,社会网络,Web结构图等。随着科学与工程领域中图数据的大量出现,从图数据库中发现有用的知识已成为数据挖掘领域一项重要的研究课题。图模式挖掘是其中最重要的一个研究分支,因为与图有关的绝大部分应用(例如:图查询、图分类、图聚类等)都需要利用图模式来管理、查询和分析图数据。本文主要对图模式挖掘技术进行深入研究,归纳总结了现有研究成果的主要思想和优缺点,提出了一些新的图模式挖掘问题和解决方法,主要研究成果如下:第一、提出从图数据库中挖掘代表模式问题及其有效解决方法。目前的频繁子图挖掘算法通常产生大量的甚至指数级数量的频繁子图,严重地影响了挖掘结果的可用性。挖掘代表模式既可以极大地减少图模式的输出数量,又能使有有意义的图模式保留在挖掘结果中。本文给出了挖掘代表模式问题的形式化定义,并证明了该问题是NP-hard。提出了一系列新的概念:δ-覆盖图,跳跃值,δ-跳跃模式等。发现了δ-跳跃模式的一个重要性质:δ-跳跃模式一定是代表模式。利用δ-跳跃模式的性质,提出了挖掘代表模式的三个算法:RP-FP,RP-GD,RP-Leap。RP-FP和RP-GD挖掘完整的代表模式集合,RP-Leap挖掘近似的代表模式集合。RP-FP从频繁闭图模式中计算代表模式,具有紧的近似比保证。然而,当频繁闭图模式数量大时,RP-FP效率低。RP-GD采用联机算法的思想,直接从图数据库中挖掘代表模式。算法复杂性分析表明RP-GD的效率要远远高于RP-FP的效率。RP-Leap利用了图模式搜索空间中大量分枝之间的相似性,快速跳过那些几乎不产生代表模式的分枝,来挖掘一个近似代表模式集合。实验结果表明:(1) RP-FP,RP-GD,RP-Leap能得到一个小的而有意义的代表模式集合;(2) RP-GD的挖掘效率远远高于RP-FP的挖掘效率;而在结果质量方面,RP-GD类似于RP-FP;(3) RP-Leap以丢失少量代表模式的代价,取得了比RP-GD快一个数量级的性能改善。第二、提出从图数据库中挖掘核心子结构问题及其有效解决方法。核心子结构在真实的图数据库中大量存在,例如化合物中的功能团就是一类核心子结构。针对核心子结构的特征,本文给出了核心子结构的形式化定义,称为?-跳跃模式。发现了Δ-跳跃模式的很多重要性质。例如: ?-跳跃模式是稳定的,它们对躁声和数据的变化不敏感,?值越大,它们的抗干扰能力越强。然而,?-跳跃模式不具有反单调性质性质,挖掘它们非常具有挑战性。通过仔细研究跳跃模式自身的特性,本文提出了两种新的裁剪技术,基于内扩展的裁剪和基于外扩展的裁剪。利用这两裁剪技术,设计了一个高效的跳跃模式挖掘算法GraphJP。在理论上,严格地证明了这两种裁剪技术的正确性以及算法GraphJP的正确性。实验结果表明:这两种新的裁剪技术能有效地裁剪图模式搜索空间,算法GraphJP能高效可扩展地挖掘频繁跳跃模式,而且挖掘结果中含有图数据库中的核心子结构。第三、提出基于联合意义度量的Top-K图模式挖掘问题及其有效解决方法。传统Top-K挖掘并不考虑图模式之间的相关性,输出的Top-K模式在结构上非常相似。如果用户得到其中一个图模式,就对其它图模式失去了兴趣。联合意义度量的作用域是图模式集合而不是图模式。因此,基于联合意义度量的Top-K挖掘,隐含排斥相关的图模式,可以得到一个多样化而有意义的图模式集合。本文讨论了适用于图模式集合的联合意义度量,并利用信息论中的概念(联合熵和信息增益)给出了两个具体的问题定义MES和MIGS,证明了它们是NP-hard问题。提出了两个高效的Top-K挖掘算法Greedy-TopK和Cluster-TopK。Greedy-TopK先产生频繁图模式,然后增量贪心地选择K个图模式。如果用户给定的意义度量满足submodular性质,Greedy-TopK能提供近似比保证。为了进一步提高Greedy-TopK的效率,针对MES和MIGS这两个具体问题的意义度量又设计了一系列有效的裁剪技术,将其嵌入到频繁子图挖掘框架中帮助裁剪图模式搜索空间。然而,当频繁图模式数量多时,Greedy-TopK仍然效率低,可扩展性差。为克服Greedy-TopK的缺点,Cluster-TopK先从图数据库中挖掘所有频繁图模式的一个代表模式集合,然后从代表模式中增量贪心地选择K个图模式。Cluster-TopK最大的优点是无需产生频繁图模式就能快速地从图数据库中挖掘一个代表模式集合。本文从理论上证明了Cluster-TopK产生的解和Greedy-TopK产生的解非常接近。实验结果表明:在结果质量和可用性方面,本文提出的Top-K挖掘远远优于传统的Top-K挖掘。Cluster-TopK比Greedy-TopK快一到两个数量级。而且,Cluster-TopK的挖掘结果质量非常接近于Greedy-TopK的挖掘结果质量。第四、提出了一种基于频繁闭显露模式的图分类框架CEP。CEP包括三个主要步骤:(1)挖掘频繁闭图模式;(2)过滤非显露模式;(3)构造分类规则。第一步,CEP挖掘所有频繁闭图模式作为候选分类特征。第二步,CEP保留频繁闭图模式中的显露模式。该步需要计算图模式在不同类别数据库中的支持度,涉及大量子图同构测试。为改善CEP的效率,CEP将频繁闭图模式组织成一个树型结构T。对数据库中的每个图G,采用深度优先方式遍历树T。在遍历过程中,利用Aprior(反单调)性质进行裁剪:如果G不包含节点P,G也不可能包含P的孩子节点。通过这种方式,可以极大地减少子图同构测试次数。第三步,CEP根据剩余的显露模式构造分类规则。在构造分类规则时,提出了一个新的特征选择方法,该方法既考虑显露模式如何覆盖图数据,又考虑显露模式在图数据中如何分布。实验结果显示:CEP具有良好的分类性能。而且,领域专家容易理解和利用CEP产生的分类规则。