圖數(shù)據(jù)挖掘技術(shù)的現(xiàn)狀與挑戰(zhàn)

張素智，張琳，曲旭凱

（鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，鄭州　450002）

圖數(shù)據(jù)挖掘技術(shù)的現(xiàn)狀與挑戰(zhàn)

張素智，張琳，曲旭凱

（鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院，鄭州450002）

0　引言

圖作為一種重要的數(shù)據(jù)結(jié)構(gòu)，可以用來描述事物之間的復(fù)雜聯(lián)系［1］。許多系統(tǒng)網(wǎng)絡(luò)例如社交網(wǎng)絡(luò)、萬維網(wǎng)、學(xué)術(shù)合作網(wǎng)、通信網(wǎng)絡(luò)的數(shù)據(jù)都是以圖的結(jié)構(gòu)形式存在。隨著信息技術(shù)的不斷發(fā)展，這些網(wǎng)絡(luò)中的數(shù)據(jù)不斷增長(zhǎng)。如何挖掘這些數(shù)據(jù)中的潛在信息，得到有用價(jià)值是需要迫切解決的問題。圖數(shù)據(jù)挖掘技術(shù)作為研究熱點(diǎn)，近年來引起學(xué)者的廣泛研究與討論。圖數(shù)據(jù)挖掘技術(shù)除了具有傳統(tǒng)數(shù)據(jù)挖掘技術(shù)所具有的性質(zhì)外，還具有數(shù)據(jù)對(duì)象關(guān)系復(fù)雜，數(shù)據(jù)表現(xiàn)形式豐富等特點(diǎn)，是處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)較好的工具。利用圖數(shù)據(jù)挖掘技術(shù)挖掘系統(tǒng)網(wǎng)絡(luò)中的數(shù)據(jù)，獲取潛在信息，并應(yīng)用到模式識(shí)別［2］、電子商務(wù)、金融等領(lǐng)域，滿足眾多實(shí)際需求。

1　圖數(shù)據(jù)定義

圖由點(diǎn)和連接點(diǎn)的邊構(gòu)成，通常用圖的點(diǎn)表示用戶頂點(diǎn)，圖的邊表示用戶之間的關(guān)系。圖包括有向圖和無向圖。邊通常用兩個(gè)頂點(diǎn)表示，若兩個(gè)頂點(diǎn)無序，則是無向圖；若兩個(gè)頂點(diǎn)有序，則是有向圖。圖用有序二次元組表示為G=（V，E）其中：

V表示圖中節(jié)點(diǎn)集合：V=｛v1，v2，v3，…，vn｝；

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

頂點(diǎn)V的邊數(shù)稱為頂點(diǎn)的度，用d（v）表示。若對(duì)邊賦予有關(guān)數(shù)據(jù)信息，稱為該邊的權(quán)重，用權(quán)重表示頂點(diǎn)間關(guān)系的強(qiáng)度。若對(duì)頂點(diǎn)賦予有關(guān)信息，稱為該頂點(diǎn)的屬性。則稱此圖為屬性加權(quán)圖［3］，屬性加權(quán)圖被廣泛應(yīng)用在圖聚類中。此時(shí)G=（V，E，A，ω）；其中：

V表示屬性圖中節(jié)點(diǎn)集合：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'；

ω為邊的權(quán)重值：ω=｛ω1，ω2，ω3，…，ωp｝，其中|ω|=p'；

若Κ為V（G）的非空子集，且對(duì)于任意頂點(diǎn)v，M （v）=｛u|u∈K，uv∈E（G）｝是v在Κ的領(lǐng)域，則對(duì)于任意圖G，N，若V（N）?V（G）且E（N）?E（G），則稱N為G的子圖。

2　圖數(shù)據(jù)挖掘技術(shù)研究現(xiàn)狀

隨著圖數(shù)據(jù)的研究不斷加深，圖數(shù)據(jù)挖掘技術(shù)得到了廣泛的研究，取得了很大的發(fā)展。主要包括圖分類、圖聚類、圖查詢、圖匹配、圖的頻繁子圖挖掘以及與圖數(shù)據(jù)有關(guān)的圖形數(shù)據(jù)庫等。文中將主要介紹這些技術(shù)的研究現(xiàn)狀和特點(diǎn)，并比較其優(yōu)缺點(diǎn)。

圖分類是圖挖掘技術(shù)的重要組成部分，圖分類是指根據(jù)圖的特征子圖來構(gòu)建分類模型［4］，并通過分類模型對(duì)圖進(jìn)行分類。根據(jù)是圖是否有標(biāo)簽節(jié)點(diǎn)或者是否有訓(xùn)練元組類號(hào)，可將圖分類分為無監(jiān)督分類、有監(jiān)督分類和半監(jiān)督分類。由于分類模型的不同［5］，圖分類的方法包括基于頻繁子圖模型的分類、基于概率子結(jié)構(gòu)模型的分類和基于圖核函數(shù)模型的分類。

基于頻繁子圖模型的分類：基于頻繁子圖模型的分類，就是將頻繁子圖的結(jié)構(gòu)或?qū)傩蕴卣髯鳛榉诸愄卣鲗?duì)圖進(jìn)行分類。主要包括三個(gè)步驟：首先挖掘出圖的頻繁子圖；其次選擇頻繁子圖的特征作為分類特征；最后構(gòu)造分類模型。該算法的優(yōu)點(diǎn)是能夠適應(yīng)各種圖數(shù)據(jù)，并以結(jié)構(gòu)特征對(duì)圖進(jìn)行分類，算法較為簡(jiǎn)單。缺點(diǎn)是頻繁子圖的特征和規(guī)模不容易確定，當(dāng)頻繁子圖的特征規(guī)模少時(shí)，將會(huì)產(chǎn)生大量分類模型，分類效果較低，分類時(shí)間加長(zhǎng)，分類準(zhǔn)確率降低。

基于概率子結(jié)構(gòu)模型的分類：該方法主要包括兩個(gè)算法：Apriori算法［6］和FP-Growth算法［7］。核心思想是根據(jù)支持度度量來分類出一個(gè)完全的子圖模型。這些算法的優(yōu)點(diǎn)是算法時(shí)間復(fù)雜度低，準(zhǔn)確率高，缺點(diǎn)是對(duì)于大型輸入型數(shù)據(jù)庫來說效率仍然很低。

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

圖聚類是指在考慮邊的結(jié)構(gòu)的條件下，把圖中的節(jié)點(diǎn)劃分成一個(gè)個(gè)簇［11］。劃分后的簇能夠更好的提取和分析所要研究的對(duì)象。圖聚類算法不僅局限于對(duì)相似結(jié)構(gòu)的劃分，目前圖聚類算法的主要研究如何同時(shí)基于結(jié)構(gòu)和屬性的劃分［12］，以達(dá)到更好的聚類效果。根據(jù)識(shí)別簇的不同，圖聚類算法分為簇適應(yīng)算法和基于頂點(diǎn)相似性算法?；陧旤c(diǎn)相似性算法又包括基于鄰接矩陣算法、距離相似型算法和連通性算法。簇適應(yīng)算法包括基于切的算法以及基于密度的算法。圖聚類算法還可分為全局聚類算法和局部聚類算法。全局聚類算法是指將圖中所有節(jié)點(diǎn)都劃分到各個(gè)簇中；局部聚類算法每次聚類只劃分一部分頂點(diǎn)?；诓煌臏?zhǔn)則，圖聚類還可劃分為基于頂點(diǎn)結(jié)構(gòu)相似度的聚類、基于屬性相似度的聚類和基于頂點(diǎn)和屬性相似度的聚類。目前比較經(jīng)典的圖聚類算法為Kernighan-Lin算法［13］、譜聚類［14］、GN［15］等。

Kernighan-Lin算法是一種基于貪婪算法的圖聚類算法。它根據(jù)貪婪算法將復(fù)雜網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)，并加入增益函數(shù)p，劃分后的兩個(gè)社區(qū)所有的邊數(shù)減去兩社區(qū)間的邊數(shù)即為p，隨后不斷搜索另一種劃分使得p為最大值，即可完成聚類目的。但此算法需要預(yù)先知道兩社區(qū)的大小，否則無法得到較好的聚類效果，靈活性較差。

譜聚類屬于點(diǎn)對(duì)聚類，譜聚類算法的核心理論依據(jù)是圖論。它的實(shí)質(zhì)是將聚類轉(zhuǎn)化為圖的劃分。在譜聚類算法中，首先聚類對(duì)象為無向加權(quán)圖的節(jié)點(diǎn)，對(duì)象特征間的相似度則用邊的權(quán)值表示。其次得到圖的距離矩陣，最后根據(jù)距離矩陣計(jì)算對(duì)象坐標(biāo)，根據(jù)坐標(biāo)進(jìn)行聚類。譜聚類是一種效率很高的聚類算法，但譜聚類的研究屬于起步階段，還沒有形成完善的理論體系，需要進(jìn)一步的研究探索。

GN算法是基于廣度優(yōu)先搜索的算法，通過廣度優(yōu)先搜索得到某一節(jié)點(diǎn)與其余節(jié)點(diǎn)的最短路徑，邊的介數(shù)等于經(jīng)過邊的最短路徑的條數(shù)。介數(shù)值越大，最短路徑書目越多，這條邊處于兩個(gè)社團(tuán)間的概率越大，因此劃分的依據(jù)是不斷移除權(quán)值大的邊來實(shí)現(xiàn)聚類。并且可以以此來區(qū)分邊在社團(tuán)間的位置。GN算法適用于較大的網(wǎng)絡(luò)社區(qū)聚類［16］，但在聚類前需要知道網(wǎng)絡(luò)社區(qū)的個(gè)數(shù)。

圖查詢是指輸入檢索圖，在圖數(shù)據(jù)庫中查詢與輸入圖相同或者相似圖的模式。圖查詢主要包括三個(gè)方面：可達(dá)性查詢、距離查詢和關(guān)鍵字查詢?？蛇_(dá)性查詢可以用來判斷節(jié)點(diǎn)間是否存在路徑；距離查詢可以用來獲取節(jié)點(diǎn)間的最短路徑；關(guān)鍵字查詢是用來研究和發(fā)現(xiàn)節(jié)點(diǎn)間的關(guān)系和與關(guān)鍵字有關(guān)的特殊群體。目前圖查詢主要面臨三個(gè)問題：如何提高挖掘圖結(jié)構(gòu)的效率、如何查找所有包含關(guān)鍵字的子圖以及提高查詢的準(zhǔn)確度。圖查詢的經(jīng)典算法是BANKS算法［17］和雙向查詢算法［18］，但這類算法無法知道圖的整體結(jié)構(gòu)，也無法獲得關(guān)鍵字在圖中的分布情況，查詢具有盲目性。還有一類算法是基于索引的圖查詢算法。代表算法是X. Yan［19］提出的以頻繁子圖作為索引結(jié)構(gòu)進(jìn)行圖挖掘。

圖匹配是指從數(shù)據(jù)圖中找出與給定的輸入模式圖匹配的所有子圖，圖匹配就是比較圖結(jié)構(gòu)間相似度的過程。根據(jù)匹配的精準(zhǔn)率，圖匹配分為精確圖匹配和非精確圖匹配。精確匹配包括最大公共子圖、最小公共子圖以及子圖同構(gòu)等方法。非精確匹配的主要方法是編輯距離算法［20］。文章主要介紹子圖同構(gòu)方法和編輯距離方法。

子圖同構(gòu)是精確匹配的一種，給定一個(gè)數(shù)據(jù)圖和輸入圖，當(dāng)且僅當(dāng)數(shù)據(jù)圖中存在一個(gè)子圖與輸入圖同構(gòu)是，則數(shù)據(jù)圖和輸入圖同構(gòu)。子圖同構(gòu)屬于NP-完全問題［21］，圖匹配效率低。并且子圖同構(gòu)要求匹配圖中的子圖與輸入圖具有相同的圖拓?fù)浣Y(jié)構(gòu)，這降低了子圖同構(gòu)的適配范圍。目前子圖同構(gòu)的研究?jī)?nèi)容主要圍繞如何減少約束因素來提高匹配的適用范圍和效率，常用的方法為近似圖匹配、圖模擬和強(qiáng)模擬等。

編輯距離是基于字符串間的匹配算法產(chǎn)生的，是一種用來衡量圖之間差異的方法。通過一系列編輯操作對(duì)圖之間結(jié)構(gòu)差異建模，說明不同圖結(jié)構(gòu)之間的差異通過某些編輯操作可以進(jìn)行相互轉(zhuǎn)化。編輯操作包括節(jié)點(diǎn)和邊的插入、替換和刪除。編輯距離有許多經(jīng)典算法，Myers［22］等提出了基于貝葉斯的編輯距離算法，Justice［23］等提出了基于二項(xiàng)限行規(guī)劃的編輯距離算法，這些算法都取得了很好的圖匹配效果。

頻繁子圖挖掘是指挖掘圖中出現(xiàn)次數(shù)大于最小支持度的公共子結(jié)構(gòu)［24］。頻繁子圖挖掘算法包括基于貪心搜索算法、基于深度優(yōu)先遍歷算法、基于廣度優(yōu)先遍歷算法以及處理大規(guī)模圖的最大頻繁子圖挖掘算法。

基于貪心搜索算法其實(shí)是基于最小描述長(zhǎng)度的頻繁子圖挖掘算法。常見的算法為SUBDUE［25］等。SUBDUE的核心是最小描述長(zhǎng)度，根據(jù)貪心算法，用頂點(diǎn)模式挖掘出可以有效壓縮輸入數(shù)據(jù)的模式。SUBDUE同時(shí)支持發(fā)現(xiàn)近似子結(jié)構(gòu)。SUBDUE可以靈活的運(yùn)用到例如社交網(wǎng)絡(luò)圖結(jié)構(gòu)等定義模糊的領(lǐng)域。

基于廣度優(yōu)先遍歷算法大多數(shù)是基于Apriori的頻繁子圖挖掘算法［26］，主要包括 AGM（Apriori-based Graph Mining）［27］、FSG（Frequent Subgraph Discovery）［17］等算法。AGM算法通過在每一步算法中增加節(jié)點(diǎn)來擴(kuò)展子圖規(guī)模，以此挖掘出頻繁子圖。該算法以數(shù)學(xué)遞歸統(tǒng)計(jì)思想為基礎(chǔ)，適用于密集型圖數(shù)據(jù)。FSG是AGM的改進(jìn)算法，在算法過程中通過增加邊來加強(qiáng)子圖的規(guī)模，并且通過優(yōu)化措施計(jì)算候選子圖，提高了挖掘效率，但是FSG算法只局限于連通圖，具有一定的局限性。

基于深度優(yōu)先遍歷算法是基于模式增長(zhǎng)的頻繁子圖挖掘算法。主要包括gSpan、CloseGraph、FFSM（Fast Frequent Subgarph Mining）等。Yan［28］等首先提出了gS-pan算法，該算法對(duì)圖的節(jié)點(diǎn)集合的增加，以此建立起深度優(yōu)先搜索樹，減少了復(fù)制圖的產(chǎn)生。CloseGraph算法不僅能提高對(duì)大圖數(shù)據(jù)的挖掘效率，還能減少不必要的生成子圖。FFSM算法的效率高于gSpan算法，該算法能夠高效處理子圖同構(gòu)的基本問題，提高了挖掘效率。

最大頻繁子圖挖掘算法是針對(duì)大圖數(shù)據(jù)挖掘的算法。這些算法提高了大圖數(shù)據(jù)挖掘的效率，降低了挖掘過程中子圖產(chǎn)生的規(guī)模，常見的算法有Spin［29］、MARGIN［30］和MFME［31］。MARGIN算法占用的存儲(chǔ)空間要大于Spin算法，但處理效率更高。MFME算法對(duì)圖中的邊進(jìn)行映射形成邊表，并針對(duì)邊表進(jìn)行挖掘，提高了挖掘效率。

3　圖數(shù)據(jù)庫

數(shù)據(jù)庫模型包括層次模型、圖模型和關(guān)系模型。隨著大數(shù)據(jù)時(shí)代的到來，社交網(wǎng)絡(luò)的發(fā)展。數(shù)據(jù)規(guī)模不斷增加，數(shù)據(jù)復(fù)雜度不斷加大。傳統(tǒng)關(guān)系數(shù)據(jù)庫已經(jīng)無法滿足數(shù)據(jù)挖掘的需要。圖形數(shù)據(jù)庫作為非傳統(tǒng)關(guān)系數(shù)據(jù)庫，能夠快速地更新數(shù)據(jù)以及數(shù)據(jù)間的關(guān)系，高效地進(jìn)行復(fù)雜操作。因此，圖數(shù)據(jù)庫得到了較快的發(fā)展和應(yīng)用。

圖模型是層次模型的另一種發(fā)展。在圖數(shù)據(jù)庫中，數(shù)據(jù)以圖表的形式存儲(chǔ)。傳統(tǒng)數(shù)據(jù)庫的增加、刪除、修改和查詢等操作變?yōu)榱藞D數(shù)據(jù)的挖掘。而社交網(wǎng)絡(luò)、電子商務(wù)等產(chǎn)生的大量數(shù)據(jù)，更適合用圖數(shù)據(jù)庫進(jìn)行存儲(chǔ)和操作。常見的圖數(shù)據(jù)庫為Neo4j［33］。

Neo4j是一個(gè)開源的圖數(shù)據(jù)庫，該數(shù)據(jù)庫由Java語言實(shí)現(xiàn)。Neo4j相當(dāng)于一個(gè)嵌入式的、具有完全實(shí)物特性的基于磁盤的持久化引擎［32］。在Neo4j數(shù)據(jù)庫中，數(shù)據(jù)以圖的形式存儲(chǔ)，使數(shù)據(jù)庫操作更具靈活性和高效性，尤其在屬性圖處理中具有較高的效率。Neo4j數(shù)據(jù)庫完全兼容ACID特性［33］，與許多操作系統(tǒng)兼容。在處理大規(guī)模社交網(wǎng)絡(luò)數(shù)據(jù)時(shí)，具有延遲低、高效率和可擴(kuò)展等特點(diǎn)。

4　圖數(shù)據(jù)挖掘的挑戰(zhàn)

隨著圖數(shù)據(jù)研究的深入，圖數(shù)據(jù)挖掘的研究取得了很大的進(jìn)展。目前，圍繞圖聚類、圖分類等挖掘算法已經(jīng)日漸成熟。圖搜索、圖數(shù)據(jù)庫、圖建模、化學(xué)圖數(shù)據(jù)以及圖在生物信息學(xué)上的應(yīng)用將是未來的研究熱點(diǎn)。如何將圖數(shù)據(jù)挖掘應(yīng)用在復(fù)雜網(wǎng)絡(luò)上的分析上也是今后的研究方向。同時(shí)，圖數(shù)據(jù)挖掘又面臨著許多挑戰(zhàn)：

（1）可擴(kuò)展圖的挖掘：圖數(shù)據(jù)挖掘技術(shù)目前只能應(yīng)用于內(nèi)存中規(guī)模較小的圖數(shù)據(jù)，對(duì)于高度可擴(kuò)展的大圖仍的研究仍有很大的挑戰(zhàn)。因此，需要研究基于磁盤的圖挖掘算法或者基于一些并行處理模型的圖挖掘算法，例如DNA模型［34］、MapReduce等。

（2）圖數(shù)據(jù)流的挖掘：隨著社交網(wǎng)絡(luò)的發(fā)展，大量數(shù)據(jù)具有突發(fā)性，用戶之間的關(guān)系以圖結(jié)構(gòu)的形式在不同時(shí)間節(jié)點(diǎn)出現(xiàn)，數(shù)據(jù)不再存儲(chǔ)在磁盤中，而是以數(shù)據(jù)流結(jié)構(gòu)的形式存在。如何對(duì)大規(guī)模的圖數(shù)據(jù)流挖掘是未來非常具有挑戰(zhàn)性的課題。

（3）不確定圖數(shù)據(jù)的挖掘：在圖數(shù)據(jù)挖掘過程中，有些圖數(shù)據(jù)的關(guān)系存在不確定性［35］，如何挖掘這些不確定圖數(shù)據(jù)間的潛在關(guān)系和信息是圖數(shù)據(jù)挖掘的一個(gè)難點(diǎn)和挑戰(zhàn)。目前已有很多針對(duì)不確定數(shù)據(jù)挖掘的理論研究，可將這些理論研究應(yīng)用在圖數(shù)據(jù)挖掘上。

（4）多圖和異構(gòu)圖的挖掘：圖挖掘目前研究只是局限于單個(gè)圖對(duì)象，如何對(duì)多個(gè)圖進(jìn)行同時(shí)挖掘?qū)⑹俏磥淼难芯繜狳c(diǎn)，例如多圖之間的查詢以及具有多個(gè)圖結(jié)構(gòu)的單個(gè)圖的挖掘。同時(shí)，具有不同定點(diǎn)和邊結(jié)構(gòu)的異構(gòu)圖挖掘也是很大的挑戰(zhàn)［36］。

5　結(jié)語

隨著Web2.0技術(shù)的發(fā)展［37］，社交網(wǎng)絡(luò)和Web網(wǎng)絡(luò)數(shù)據(jù)的不斷增加，圖數(shù)據(jù)挖掘已成為數(shù)據(jù)挖掘領(lǐng)域新的研究熱點(diǎn)。本文介紹了圖數(shù)據(jù)挖掘的定義和分類，綜述了圖分類、圖聚類、圖查詢、圖匹配、圖的頻繁子圖挖掘和圖數(shù)據(jù)庫的研究現(xiàn)狀，并分析了圖數(shù)據(jù)挖掘所面臨的問題和挑戰(zhàn)。雖然圖數(shù)據(jù)挖掘已經(jīng)產(chǎn)生了一些很有價(jià)值的研究，但圖數(shù)據(jù)挖掘技術(shù)依然需要很多研究人員付出很多努力，希望本文能對(duì)研究起到一定的參考作用。

［1］丁悅，張陽，李戰(zhàn)懷，等.圖數(shù)據(jù)挖掘技術(shù)的研究與進(jìn)展［J］.計(jì)算機(jī)應(yīng)用，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］李孝偉，陳福才，劉力雄.一種融合節(jié)點(diǎn)與鏈接屬性的社交網(wǎng)絡(luò)社區(qū)劃分算法［J］.計(jì)算機(jī)應(yīng)用研究，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］吳燁，鐘志農(nóng)，熊偉，等.一種高效的屬性圖聚類方法［J］.計(jì)算機(jī)學(xué)報(bào)，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，F(xiàn)redrikson 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，F(xiàn)eng 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］.計(jì)算機(jī)工程與科學(xué)，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］.軟件學(xué)報(bào)，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，F(xiàn)redrikson 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，F(xiàn)irst 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］張碩，高宏，李建中，等.不確定圖數(shù)據(jù)庫中高效查詢處理［J］.計(jì)算機(jī)學(xué)報(bào)，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）

國家自然科學(xué)基金青年科學(xué)基金項(xiàng)目（No.61201447）

1007-1423（2015）26-0052-06

10.3969/j.issn.1007-1423.2015.26.014

張素智（1965-），男，博士，教授，研究方向?yàn)閃eb數(shù)據(jù)庫、分布式計(jì)算和異構(gòu)系統(tǒng)集成張琳（1993-），女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與集成

2015-07-02

2015-08-15

圖作為一種重要的數(shù)據(jù)結(jié)構(gòu)，可以用來描述事物之間的復(fù)雜聯(lián)系。隨著社交網(wǎng)絡(luò)、Web網(wǎng)等網(wǎng)絡(luò)中圖數(shù)據(jù)數(shù)量不斷增加，圖數(shù)據(jù)挖掘技術(shù)逐漸成為研究熱點(diǎn)。傳統(tǒng)數(shù)據(jù)挖掘技術(shù)不斷應(yīng)用到圖數(shù)據(jù)挖掘領(lǐng)域，加快圖數(shù)據(jù)挖掘技術(shù)的發(fā)展。首先介紹圖數(shù)據(jù)的定義，其次介紹現(xiàn)階段圖數(shù)據(jù)挖掘算法，包括圖分類、圖聚類、圖查詢、圖匹配、圖的頻繁子圖挖掘等，以及圖數(shù)據(jù)庫的發(fā)展現(xiàn)狀，最后介紹圖挖掘技術(shù)所面臨的挑戰(zhàn)。

圖；圖數(shù)據(jù)；圖挖掘

曲旭凱（1990-），男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘與集成

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.