图数据挖掘技术的现状与挑战

张素智，张琳，曲旭凯

（郑州轻工业学院计算机与通信工程学院，郑州　450002）

图数据挖掘技术的现状与挑战

张素智，张琳，曲旭凯

（郑州轻工业学院计算机与通信工程学院，郑州450002）

0　引言

图作为一种重要的数据结构，可以用来描述事物之间的复杂联系［1］。许多系统网络例如社交网络、万维网、学术合作网、通信网络的数据都是以图的结构形式存在。随着信息技术的不断发展，这些网络中的数据不断增长。如何挖掘这些数据中的潜在信息，得到有用价值是需要迫切解决的问题。图数据挖掘技术作为研究热点，近年来引起学者的广泛研究与讨论。图数据挖掘技术除了具有传统数据挖掘技术所具有的性质外，还具有数据对象关系复杂，数据表现形式丰富等特点，是处理复杂数据结构较好的工具。利用图数据挖掘技术挖掘系统网络中的数据，获取潜在信息，并应用到模式识别［2］、电子商务、金融等领域，满足众多实际需求。

1　图数据定义

图由点和连接点的边构成，通常用图的点表示用户顶点，图的边表示用户之间的关系。图包括有向图和无向图。边通常用两个顶点表示，若两个顶点无序，则是无向图；若两个顶点有序，则是有向图。图用有序二次元组表示为G=（V，E）其中：

V表示图中节点集合：V=｛v1，v2，v3，…，vn｝；

E表示图中边的集合：E=｛（vi，vj）|（vi，vj）∈R，1≤i，j≤n，i≠j｝；

顶点V的边数称为顶点的度，用d（v）表示。若对边赋予有关数据信息，称为该边的权重，用权重表示顶点间关系的强度。若对顶点赋予有关信息，称为该顶点的属性。则称此图为属性加权图［3］，属性加权图被广泛应用在图聚类中。此时G=（V，E，A，ω）；其中：

V表示属性图中节点集合：V=｛v1，v2，v3，…，vn｝；

E表示属性图中边的集合：E=｛（vi，vj）| （vi，vj）∈R，1≤i，j≤n，i≠j｝；

A表示图的属性的集合：A=｛a1，a2，a3，…，an｝，其中|A|=m'；

ω为边的权重值：ω=｛ω1，ω2，ω3，…，ωp｝，其中|ω|=p'；

若Κ为V（G）的非空子集，且对于任意顶点v，M （v）=｛u|u∈K，uv∈E（G）｝是v在Κ的领域，则对于任意图G，N，若V（N）⊆V（G）且E（N）⊆E（G），则称N为G的子图。

2　图数据挖掘技术研究现状

随着图数据的研究不断加深，图数据挖掘技术得到了广泛的研究，取得了很大的发展。主要包括图分类、图聚类、图查询、图匹配、图的频繁子图挖掘以及与图数据有关的图形数据库等。文中将主要介绍这些技术的研究现状和特点，并比较其优缺点。

图分类是图挖掘技术的重要组成部分，图分类是指根据图的特征子图来构建分类模型［4］，并通过分类模型对图进行分类。根据是图是否有标签节点或者是否有训练元组类号，可将图分类分为无监督分类、有监督分类和半监督分类。由于分类模型的不同［5］，图分类的方法包括基于频繁子图模型的分类、基于概率子结构模型的分类和基于图核函数模型的分类。

基于频繁子图模型的分类：基于频繁子图模型的分类，就是将频繁子图的结构或属性特征作为分类特征对图进行分类。主要包括三个步骤：首先挖掘出图的频繁子图；其次选择频繁子图的特征作为分类特征；最后构造分类模型。该算法的优点是能够适应各种图数据，并以结构特征对图进行分类，算法较为简单。缺点是频繁子图的特征和规模不容易确定，当频繁子图的特征规模少时，将会产生大量分类模型，分类效果较低，分类时间加长，分类准确率降低。

基于概率子结构模型的分类：该方法主要包括两个算法：Apriori算法［6］和FP-Growth算法［7］。核心思想是根据支持度度量来分类出一个完全的子图模型。这些算法的优点是算法时间复杂度低，准确率高，缺点是对于大型输入型数据库来说效率仍然很低。

基于图核模型的分类：“核”是指在图中与图结构有关的核函数框架。基于图核模型的分类，就是为图中的每个节点分配一个“例子”［8］，在对图结构的边进行操作时，计算边的节点“例子”的相似度。通过实验表明，在图分类算法中，计算特征化“例子”间的相似度比基于距离计算相似度能获得更好的分类效果。目前的图核分类算法包括基于循环和基于游走的图核算法。Boser［9］等提出了使用图核方法分类图结构。T.Kudo［10］等提出一种基于Boosting的图核分类算法。图核算法的缺点是具有局限性，无法与频繁子图分类算法一样适用于所有图结构，但在特定图结构的分类效果上要好于频繁子图分类算法。

图聚类是指在考虑边的结构的条件下，把图中的节点划分成一个个簇［11］。划分后的簇能够更好的提取和分析所要研究的对象。图聚类算法不仅局限于对相似结构的划分，目前图聚类算法的主要研究如何同时基于结构和属性的划分［12］，以达到更好的聚类效果。根据识别簇的不同，图聚类算法分为簇适应算法和基于顶点相似性算法。基于顶点相似性算法又包括基于邻接矩阵算法、距离相似型算法和连通性算法。簇适应算法包括基于切的算法以及基于密度的算法。图聚类算法还可分为全局聚类算法和局部聚类算法。全局聚类算法是指将图中所有节点都划分到各个簇中；局部聚类算法每次聚类只划分一部分顶点。基于不同的准则，图聚类还可划分为基于顶点结构相似度的聚类、基于属性相似度的聚类和基于顶点和属性相似度的聚类。目前比较经典的图聚类算法为Kernighan-Lin算法［13］、谱聚类［14］、GN［15］等。

Kernighan-Lin算法是一种基于贪婪算法的图聚类算法。它根据贪婪算法将复杂网络划分为两个社区，并加入增益函数p，划分后的两个社区所有的边数减去两社区间的边数即为p，随后不断搜索另一种划分使得p为最大值，即可完成聚类目的。但此算法需要预先知道两社区的大小，否则无法得到较好的聚类效果，灵活性较差。

谱聚类属于点对聚类，谱聚类算法的核心理论依据是图论。它的实质是将聚类转化为图的划分。在谱聚类算法中，首先聚类对象为无向加权图的节点，对象特征间的相似度则用边的权值表示。其次得到图的距离矩阵，最后根据距离矩阵计算对象坐标，根据坐标进行聚类。谱聚类是一种效率很高的聚类算法，但谱聚类的研究属于起步阶段，还没有形成完善的理论体系，需要进一步的研究探索。

GN算法是基于广度优先搜索的算法，通过广度优先搜索得到某一节点与其余节点的最短路径，边的介数等于经过边的最短路径的条数。介数值越大，最短路径书目越多，这条边处于两个社团间的概率越大，因此划分的依据是不断移除权值大的边来实现聚类。并且可以以此来区分边在社团间的位置。GN算法适用于较大的网络社区聚类［16］，但在聚类前需要知道网络社区的个数。

图查询是指输入检索图，在图数据库中查询与输入图相同或者相似图的模式。图查询主要包括三个方面：可达性查询、距离查询和关键字查询。可达性查询可以用来判断节点间是否存在路径；距离查询可以用来获取节点间的最短路径；关键字查询是用来研究和发现节点间的关系和与关键字有关的特殊群体。目前图查询主要面临三个问题：如何提高挖掘图结构的效率、如何查找所有包含关键字的子图以及提高查询的准确度。图查询的经典算法是BANKS算法［17］和双向查询算法［18］，但这类算法无法知道图的整体结构，也无法获得关键字在图中的分布情况，查询具有盲目性。还有一类算法是基于索引的图查询算法。代表算法是X. Yan［19］提出的以频繁子图作为索引结构进行图挖掘。

图匹配是指从数据图中找出与给定的输入模式图匹配的所有子图，图匹配就是比较图结构间相似度的过程。根据匹配的精准率，图匹配分为精确图匹配和非精确图匹配。精确匹配包括最大公共子图、最小公共子图以及子图同构等方法。非精确匹配的主要方法是编辑距离算法［20］。文章主要介绍子图同构方法和编辑距离方法。

子图同构是精确匹配的一种，给定一个数据图和输入图，当且仅当数据图中存在一个子图与输入图同构是，则数据图和输入图同构。子图同构属于NP-完全问题［21］，图匹配效率低。并且子图同构要求匹配图中的子图与输入图具有相同的图拓扑结构，这降低了子图同构的适配范围。目前子图同构的研究内容主要围绕如何减少约束因素来提高匹配的适用范围和效率，常用的方法为近似图匹配、图模拟和强模拟等。

编辑距离是基于字符串间的匹配算法产生的，是一种用来衡量图之间差异的方法。通过一系列编辑操作对图之间结构差异建模，说明不同图结构之间的差异通过某些编辑操作可以进行相互转化。编辑操作包括节点和边的插入、替换和删除。编辑距离有许多经典算法，Myers［22］等提出了基于贝叶斯的编辑距离算法，Justice［23］等提出了基于二项限行规划的编辑距离算法，这些算法都取得了很好的图匹配效果。

频繁子图挖掘是指挖掘图中出现次数大于最小支持度的公共子结构［24］。频繁子图挖掘算法包括基于贪心搜索算法、基于深度优先遍历算法、基于广度优先遍历算法以及处理大规模图的最大频繁子图挖掘算法。

基于贪心搜索算法其实是基于最小描述长度的频繁子图挖掘算法。常见的算法为SUBDUE［25］等。SUBDUE的核心是最小描述长度，根据贪心算法，用顶点模式挖掘出可以有效压缩输入数据的模式。SUBDUE同时支持发现近似子结构。SUBDUE可以灵活的运用到例如社交网络图结构等定义模糊的领域。

基于广度优先遍历算法大多数是基于Apriori的频繁子图挖掘算法［26］，主要包括 AGM（Apriori-based Graph Mining）［27］、FSG（Frequent Subgraph Discovery）［17］等算法。AGM算法通过在每一步算法中增加节点来扩展子图规模，以此挖掘出频繁子图。该算法以数学递归统计思想为基础，适用于密集型图数据。FSG是AGM的改进算法，在算法过程中通过增加边来加强子图的规模，并且通过优化措施计算候选子图，提高了挖掘效率，但是FSG算法只局限于连通图，具有一定的局限性。

基于深度优先遍历算法是基于模式增长的频繁子图挖掘算法。主要包括gSpan、CloseGraph、FFSM（Fast Frequent Subgarph Mining）等。Yan［28］等首先提出了gS-pan算法，该算法对图的节点集合的增加，以此建立起深度优先搜索树，减少了复制图的产生。CloseGraph算法不仅能提高对大图数据的挖掘效率，还能减少不必要的生成子图。FFSM算法的效率高于gSpan算法，该算法能够高效处理子图同构的基本问题，提高了挖掘效率。

最大频繁子图挖掘算法是针对大图数据挖掘的算法。这些算法提高了大图数据挖掘的效率，降低了挖掘过程中子图产生的规模，常见的算法有Spin［29］、MARGIN［30］和MFME［31］。MARGIN算法占用的存储空间要大于Spin算法，但处理效率更高。MFME算法对图中的边进行映射形成边表，并针对边表进行挖掘，提高了挖掘效率。

3　图数据库

数据库模型包括层次模型、图模型和关系模型。随着大数据时代的到来，社交网络的发展。数据规模不断增加，数据复杂度不断加大。传统关系数据库已经无法满足数据挖掘的需要。图形数据库作为非传统关系数据库，能够快速地更新数据以及数据间的关系，高效地进行复杂操作。因此，图数据库得到了较快的发展和应用。

图模型是层次模型的另一种发展。在图数据库中，数据以图表的形式存储。传统数据库的增加、删除、修改和查询等操作变为了图数据的挖掘。而社交网络、电子商务等产生的大量数据，更适合用图数据库进行存储和操作。常见的图数据库为Neo4j［33］。

Neo4j是一个开源的图数据库，该数据库由Java语言实现。Neo4j相当于一个嵌入式的、具有完全实物特性的基于磁盘的持久化引擎［32］。在Neo4j数据库中，数据以图的形式存储，使数据库操作更具灵活性和高效性，尤其在属性图处理中具有较高的效率。Neo4j数据库完全兼容ACID特性［33］，与许多操作系统兼容。在处理大规模社交网络数据时，具有延迟低、高效率和可扩展等特点。

4　图数据挖掘的挑战

随着图数据研究的深入，图数据挖掘的研究取得了很大的进展。目前，围绕图聚类、图分类等挖掘算法已经日渐成熟。图搜索、图数据库、图建模、化学图数据以及图在生物信息学上的应用将是未来的研究热点。如何将图数据挖掘应用在复杂网络上的分析上也是今后的研究方向。同时，图数据挖掘又面临着许多挑战：

（1）可扩展图的挖掘：图数据挖掘技术目前只能应用于内存中规模较小的图数据，对于高度可扩展的大图仍的研究仍有很大的挑战。因此，需要研究基于磁盘的图挖掘算法或者基于一些并行处理模型的图挖掘算法，例如DNA模型［34］、MapReduce等。

（2）图数据流的挖掘：随着社交网络的发展，大量数据具有突发性，用户之间的关系以图结构的形式在不同时间节点出现，数据不再存储在磁盘中，而是以数据流结构的形式存在。如何对大规模的图数据流挖掘是未来非常具有挑战性的课题。

（3）不确定图数据的挖掘：在图数据挖掘过程中，有些图数据的关系存在不确定性［35］，如何挖掘这些不确定图数据间的潜在关系和信息是图数据挖掘的一个难点和挑战。目前已有很多针对不确定数据挖掘的理论研究，可将这些理论研究应用在图数据挖掘上。

（4）多图和异构图的挖掘：图挖掘目前研究只是局限于单个图对象，如何对多个图进行同时挖掘将是未来的研究热点，例如多图之间的查询以及具有多个图结构的单个图的挖掘。同时，具有不同定点和边结构的异构图挖掘也是很大的挑战［36］。

5　结语

随着Web2.0技术的发展［37］，社交网络和Web网络数据的不断增加，图数据挖掘已成为数据挖掘领域新的研究热点。本文介绍了图数据挖掘的定义和分类，综述了图分类、图聚类、图查询、图匹配、图的频繁子图挖掘和图数据库的研究现状，并分析了图数据挖掘所面临的问题和挑战。虽然图数据挖掘已经产生了一些很有价值的研究，但图数据挖掘技术依然需要很多研究人员付出很多努力，希望本文能对研究起到一定的参考作用。

［1］丁悦，张阳，李战怀，等.图数据挖掘技术的研究与进展［J］.计算机应用，2012，32（1）：182-190.

［2］Tri08l，Silke，Leser，Ulf.Fast and practical indexing and querying of very large graphs［C］.SIGMOD'07 Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data，2007.

［3］Samet H，Sankaranarayanan J，Alborzi H.Scalable network distance browsing in spatial databases［J］.Sigmod Proceedings of the Acm Sigmod International Conference on Management of Data，2008，24（2）：43-54.

［4］李孝伟，陈福才，刘力雄.一种融合节点与链接属性的社交网络社区划分算法［J］.计算机应用研究，2013，30（5）：1477-1480.DOI：10.3969/j.issn.1001-3695.2013.05.050.

［5］Zou L，Chen L，00zsu，M.Tamer.DistanceJoin：pattern match query in a large graph database.［J］.Proceedings of the Vldb Endowment，2009，2：886-897.

［6］Mahé P，Vert J P.Graph kernels based on tree patterns for molecules［J］.Machine Learning，2009.

［7］Huan J，Wang W，Prins J，et al.Spin：Mining maximal frequent subgraphs from graph databases［C］.In KDD.2004：581-586.

［8］Thomas L T，Valluri S R，Karlapalem K.MARGIN：maximal frequent subgraph mining［C］.Data Mining，2006.ICDM'06.Sixth International Conference on.IEEE，2006：1097-1101.

［9］Boser B E，Guyon I M，Vapnik V N.A training algorithm for optimal margin classifiers［C］.Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory，1992：144-152.

［10］Kudo T，Maeda E，Matsumoto Y.An application of boosting to graph classification［J］.Advances in Neural Information Processing Systems，2004：729-736.

［11］吴烨，钟志农，熊伟，等.一种高效的属性图聚类方法［J］.计算机学报，2013，36（8）：1704-1713.DOI：10.3724/SP.J.1016.2013. 01704.

［12］Kuramochi，M，Karypis，G.GREW-A scalable frequent subgraph discovery algorithm［C］.null.IEEE Computer Society，2004：439-442.

［13］Shang H，Zhang Y，Lin X，et al.Taming verification hardness：an efficient algorithm for testing subgraph isomorphism［J］.［31］Yan X，Han J.CloseGraph：mining closed frequent graph patterns［C］.Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining.ACM，2003：286-295.

［14］Zhou X F，Gao L，Dong A G.An Algorithm for finding frequent patterns in a large sparse graph［J］.International Multiconference of Engineers&Computer Scientists，2007.Proceedings of the Vldb Endowment，2008，1（1）：364-375.

［15］Chen C，Lin C X，Fredrikson M，et al.Mining graph patterns efficiently via randomized summaries［J］.Proceedings of the Vldb Endowment，2009，2（1）.

［16］M.E.J.Newman，M.Girvan.Finding and evaluating community structure in networks［J］.Phys.rev.e，2004，69（2）：292-313.

［17］Xu X，Yuruk N，Feng Z，et al.Scan：A structural clustering algorithm for networks［J］.Kdd，2007.

［18］Inokuchi A，Washio T，Okada T，et al.Applying the apriori-based graph mining method to mutagenesis data analysis［J］.Journal of Computer Aided Chemistry，2001：87-92.

［19］Yan X，Yu P S，Han J.Graph Indexing：A frequent structure-based approach［J］.Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data，2004：335-346.

［20］李继腾，骆志刚，丁凡，等.最大频繁子图挖掘算法研究［J］.计算机工程与科学，2009（12）：67-70.

［21］Kuramochi，M，Karypis，G.GREW-A scalable frequent subgraph discovery algorithm［C］.null.IEEE Computer Society，2004：439-442. ［22］Myers R，Wison，R.C，Hancock E R.Bayesian graph edit distance［J］.Pattern Analysis&Machine Intelligence IEEE Transactions on，2000，22（6）：628-635.

［23］Justice D，Hero A.A Binary linear programming formulation of the graph edit distance［J］.IEEE Transactions on Pattern Analysis& Machine Intelligence，2006，28（8）：1200-1214.

［24］邹兆年，李建中，高宏，等.从不确定图中挖掘频繁子图模式［J］.软件学报，2009，20（11）：2965-2976.

［25］Zhou X F，Gao L，Dong A G.An algorithm for finding frequent patterns in a large sparse graph［J］.International Multiconference of Engineers&Computer Scientists，2007.Proceedings of the Vldb Endowment，2008，1（1）：364-375.

［26］Chen C，Lin C X，Fredrikson M，et al.Mining graph patterns efficiently via randomized summaries［J］.Proceedings of the Vldb Endowment，2009，2（1）.

［27］M.E.J.Newman，M.Girvan.Findingand Evaluating Community Structure Innetworks［J］.Phys.rev.e，2004，69（2）：292-313.

［28］Yan X，Han J.gSpan：graph-based substructure pattern mining［C］.Data Mining，2002.ICDM 2003.Proceedings.2002 IEEE International Conference on.IEEE，2002：721.

［29］Soussi，R，Aufaure，M，Baazaoui，H.Towards social network extraction using a graph database［C］.Advances in Databases，First International Conference on.IEEE，2010：28-34.

［30］Kadge S，Bhatia G.Graph based forecasting for social networking site［C］.Communication，Information&Computing Technology（ICCICT），2012 International Conference on.2012：1-6.

［31］Satuluri V，Parthasarathy S.Scalable graph clustering using stochastic flows：applications to community discovery［C］.Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2009：737-746.

［32］张硕，高宏，李建中，等.不确定图数据库中高效查询处理［J］.计算机学报，2009，32（10）：2066-2079.

［33］Ester M，Ge R，Gao B J，et al.Joint cluster analysis of attribute data and relationship data：the connected k-center problem［J］.Acm Transactions on Knowledge Discovery from Data Tkdd Homepage，2008：285-312.

［34］Moser F，Ge R，Ester M.Joint cluster analysis of attribute and relationship data without a-priori specification of the number of clusters［C］.KDD'07.2007：510-519.

［35］Saigo H，Nowozin S，Kadowaki T，et al.gBoost：a mathematical programming approach to graph classification and regression［J］.Machine Learning，2009，75（1）：69-89.

［36］Kudo K T.Clustering graphs by weighted substructure mining［C］.ICML'06 Proceedings of the 23rd international conference on Machine learning，2006：953-960.

［37］Zeng Z，Tung A K H，Wang J，t al.Comparing stars：on approximating graph edit distance［J］.Proceedings of the Vldb Endowment，2009，2（1）：25-36.

Graph；Graph Data；Graph Mining

Present Situation and Challenge of Graph Data Mining Technology

ZHANG Su-zhi，ZHANG Lin，QU Xu-kai

（School of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450002）

国家自然科学基金青年科学基金项目（No.61201447）

1007-1423（2015）26-0052-06

10.3969/j.issn.1007-1423.2015.26.014

张素智（1965-），男，博士，教授，研究方向为Web数据库、分布式计算和异构系统集成张琳（1993-），女，硕士研究生，研究方向为数据挖掘与集成

2015-07-02

2015-08-15

图作为一种重要的数据结构，可以用来描述事物之间的复杂联系。随着社交网络、Web网等网络中图数据数量不断增加，图数据挖掘技术逐渐成为研究热点。传统数据挖掘技术不断应用到图数据挖掘领域，加快图数据挖掘技术的发展。首先介绍图数据的定义，其次介绍现阶段图数据挖掘算法，包括图分类、图聚类、图查询、图匹配、图的频繁子图挖掘等，以及图数据库的发展现状，最后介绍图挖掘技术所面临的挑战。

图；图数据；图挖掘

曲旭凯（1990-），男，硕士研究生，研究方向为数据挖掘与集成

Graph as an important data structure，it can be used to describe the complex relationship between things.In social network，web network and other network in figure data is increasing，data mining technology has become a hot research.Traditional data mining technology has been applied to the field of graph data mining，and has accelerated the development of the technology of data mining.In this paper first introduced the definition of graph data，followed by the introduction of the current graph data mining algorithms，including classification graph，graph clustering，query graph，graph matching，graph of frequent subgraph mining，and graph database development status，at last，the paper introduces the graph mining technology is facing the challenges.