圖數據挖掘技術的現狀與挑戰

張素智，張琳，曲旭凱

（鄭州輕工業學院計算機與通信工程學院，鄭州　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］。核心思想是根據支持度度量來分類出一個完全的子圖模型。這些算法的優點是算法時間復雜度低，準確率高，缺點是對于大型輸入型數據庫來說效率仍然很低。

基于圖核模型的分類：“核”是指在圖中與圖結構有關的核函數框架?；趫D核模型的分類，就是為圖中的每個節點分配一個“例子”［8］，在對圖結構的邊進行操作時，計算邊的節點“例子”的相似度。通過實驗表明，在圖分類算法中，計算特征化“例子”間的相似度比基于距離計算相似度能獲得更好的分類效果。目前的圖核分類算法包括基于循環和基于游走的圖核算法。Boser［9］等提出了使用圖核方法分類圖結構。T.Kudo［10］等提出一種基于Boosting的圖核分類算法。圖核算法的缺點是具有局限性，無法與頻繁子圖分類算法一樣適用于所有圖結構，但在特定圖結構的分類效果上要好于頻繁子圖分類算法。

圖聚類是指在考慮邊的結構的條件下，把圖中的節點劃分成一個個簇［11］。劃分后的簇能夠更好的提取和分析所要研究的對象。圖聚類算法不僅局限于對相似結構的劃分，目前圖聚類算法的主要研究如何同時基于結構和屬性的劃分［12］，以達到更好的聚類效果。根據識別簇的不同，圖聚類算法分為簇適應算法和基于頂點相似性算法?；陧旤c相似性算法又包括基于鄰接矩陣算法、距離相似型算法和連通性算法。簇適應算法包括基于切的算法以及基于密度的算法。圖聚類算法還可分為全局聚類算法和局部聚類算法。全局聚類算法是指將圖中所有節點都劃分到各個簇中；局部聚類算法每次聚類只劃分一部分頂點?；诓煌臏蕜t，圖聚類還可劃分為基于頂點結構相似度的聚類、基于屬性相似度的聚類和基于頂點和屬性相似度的聚類。目前比較經典的圖聚類算法為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.