??? 摘 要：隨著對大量結(jié)構(gòu)化數(shù)據(jù)分析需求的增長，從圖集合中挖掘頻繁子圖模式已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點。通過對目前有代表性的頻繁子圖挖掘算法的分析和比較，全面總結(jié)了各算法的特性及優(yōu)缺點，并預(yù)測了今后的發(fā)展趨勢。
??? 關(guān)鍵詞：數(shù)據(jù)挖掘；頻繁子結(jié)構(gòu)；子圖同構(gòu)
?
??? 隨著生物信息學(xué)(蛋白質(zhì)結(jié)構(gòu)、基因組識別和比較分析)、社會網(wǎng)絡(luò)(實體間的聯(lián)系)、Web分析(Web的鏈接結(jié)構(gòu)分析、Web內(nèi)容挖掘和Web日志的搜索)以及文本信息檢索(文檔的選擇、文檔的秩評定)等復(fù)雜結(jié)構(gòu)的廣泛應(yīng)用。圖作為一般數(shù)據(jù)結(jié)構(gòu)在這些結(jié)構(gòu)以及它們的建模方面日趨重要。為了進(jìn)一步對圖進(jìn)行特征化、區(qū)分、分類和聚類分析，挖掘頻繁子圖模式已經(jīng)成為一項重要的任務(wù)，日益受到人們的關(guān)注。
1 現(xiàn)有的頻繁子圖挖掘方法
??? 在各種各樣的圖模式中，頻繁子結(jié)構(gòu)是可以在圖集合中發(fā)現(xiàn)的非?；镜哪Ｊ?。在大型圖數(shù)據(jù)庫中可以用它建立圖索引并進(jìn)行相似性搜索，區(qū)分不同的圖組群，對圖進(jìn)行分類和聚類分析。目前已經(jīng)有了一些成熟的頻繁子結(jié)構(gòu)的挖掘方法，并且在許多領(lǐng)域得到了應(yīng)用，尤其在藥物發(fā)現(xiàn)和化合物合成領(lǐng)域的應(yīng)用更為流行，目前子結(jié)構(gòu)挖掘算法分類如下：
??? (1)基于Apriori的頻繁結(jié)構(gòu)挖掘算法：AGM、PSG、路徑連接算法；
??? (2)基于模式增長的頻繁結(jié)構(gòu)挖掘算法：Espan、FFSM、CloseGraph；
??? (3)基于最小描述長度的近似頻繁子結(jié)構(gòu)挖掘算法：SUBOUE；
??? (4)基于模式增長和模式歸約的精確稠密頻繁子結(jié)構(gòu)挖掘算法：CloseCut、Splat。
1.1 基于Apriori的頻繁子結(jié)構(gòu)挖掘算法
??? 基于Apriori的頻繁子結(jié)構(gòu)挖掘算法與基于Apriori的頻繁項集挖掘算法相類似。頻繁圖的搜索開始于小規(guī)模圖，按照自底向上的方式產(chǎn)生具有附加頂點、邊或路徑的候選圖。最近提出的基于Apriori的頻繁子結(jié)構(gòu)挖掘算法包括AGM、FSG和路徑連接方法等。
??? （1）由Inokuchi等人提出的計算高效性算法AGM[1]，能找到所有滿足某一最小支持度閾值的頻繁子圖，它與基于Apriori的項集挖掘算法具有類似的特點，使用基于頂點的候選產(chǎn)生方法，通過在每一步增加一個頂點來擴(kuò)展子結(jié)構(gòu)的規(guī)模。2個大小為k的頻繁圖進(jìn)行連接，僅當(dāng)它們具有相同的大小為k-1的子圖。新形成的候選包括1個大小為k-1的公共子圖和來自2個大小為k的模式中的2個附加頂點。AGM能夠處理帶有標(biāo)記的頂點和邊的圖，可以有效地挖掘不同類型的子圖，例如一般子圖、導(dǎo)出子圖、連通子圖、有序子樹、無序子樹和子路經(jīng)，特別對于合成密集型數(shù)據(jù)集具有良好的性能。這種方法常用于發(fā)生變異活動的化合物分子結(jié)構(gòu)的分析。實驗證明，在一個包含300個化合物的數(shù)據(jù)集中，當(dāng)最小支持度閾值從20%～10%變化時要找出所有的頻繁生成子圖需要40 min到8天的時間。AGM對于一個生成子圖可以是非連通的，包含幾個獨立的圖片段，但這種方法也需要很長的處理時間。
??? （2）Kuramochi等人利用邊增長策略進(jìn)一步發(fā)展了上述思想，提出了FSG算法[2]。該算法在具有多條邊和頂點標(biāo)記的圖數(shù)據(jù)集中能更好地運行，運行時間依賴于被發(fā)現(xiàn)的頻繁子圖的大小。它的輸入為圖集，但為了減小時間復(fù)雜度，F(xiàn)SG限用于連通圖，由于很多應(yīng)用都可以轉(zhuǎn)化為連通圖，所以FSG的這個限制并未影響到它的應(yīng)用范圍。為了提高導(dǎo)出規(guī)范標(biāo)記效率，它使用了一些圖頂點不變量(例如設(shè)定圖中的每個頂點的度)并且它通過引入TID(transaction ID)方法提高了頻繁子圖的候選產(chǎn)生效率。此外它采用基于邊的候選產(chǎn)生策略，通過每次增加一條邊來擴(kuò)展子結(jié)構(gòu)的規(guī)模。合并2個大小為k的頻繁子圖，當(dāng)且僅當(dāng)他們共享相同的具有k-1條邊的連通主子圖(該主子圖稱為核)，新形成的侯選包括核和來自2個大小為k的模式中的2條附加邊，通過這種合并方法還提高了FSG的連接效率。正因為FSG引入了這些技術(shù)所以運行速度很快，實驗證明，它具有良好的性能并且能夠隨數(shù)據(jù)庫的大小呈線性比例變化，它能夠從一個包含8萬個圖片支持度閾值為2%的合成數(shù)據(jù)集中，以少于500 s的時間發(fā)現(xiàn)所有的頻繁連通子圖。但是對于大型圖數(shù)據(jù)存儲TID列表要占用大量的內(nèi)存空間，而且不像合并項集那樣，2個大小為k的頻繁項集能夠只產(chǎn)生唯一的大小為k+1的項集，這里2個大小為k的子圖可能產(chǎn)生多個大小為k+1的候選子圖，生成大量的重復(fù)候選子圖，降低了算法的整體效率。
??? （3）邊不相交路徑方法[3]依據(jù)圖所擁有的不相交路徑的數(shù)量來分類。如果2條路徑不共享任何邊，那么就稱這兩條路徑是邊不相交的[4]。該方法提出一種合成關(guān)系(composition? relation)的結(jié)構(gòu)來表示邊不相交路徑的連接圖，這種結(jié)構(gòu)是一個二維表的形式，節(jié)點表示行，路徑表示列。另外還提出了雙射和(bijective sum)合成關(guān)系，接合(splice)合成關(guān)系以及合成關(guān)系的圖實現(xiàn)操作，雙射和是用來表示連接2個具有k條不相交路徑的子圖后形成的k+1條不相交路徑的圖，這個圖包括1個具有k-1條不相交路徑的公共子圖和添加到共享節(jié)點(指在2個具有k條路徑的圖中公共子圖連接另外一條路徑的節(jié)點)上的2條附加路徑。接合是把一個圖中屬于2個不同路徑上的2個節(jié)點合并成一個節(jié)點的過程，以此確保挖掘的完全性。合成關(guān)系的圖實現(xiàn)是對于給定的一個有n條路徑的合并關(guān)系C，則可以構(gòu)造一個相對應(yīng)的圖。讓表中的行對應(yīng)圖的頂點并且定義邊(i，j)為：當(dāng)同一個路徑p的2個節(jié)點出現(xiàn)在第i行和第j行中，則在它們之間的那條邊。這種操作就稱為圖實現(xiàn)。
??? 算法的處理主要分成3個階段：
??? （1）通過每次增加一條邊來構(gòu)造頻繁路徑;
??? （2）構(gòu)造路徑數(shù)為2的頻繁圖。通過連接具有一條路徑的圖來完成，在此過程通過合成關(guān)系列出所有的兩條路徑連接的可能性，另外保留那些在圖實現(xiàn)中路徑數(shù)為2、而且通過計算支持度確定的頻繁圖，最后移除所有的非最小的同構(gòu)圖；
??? （3）通過連接具有k-1條路徑的圖來構(gòu)造具有k條路徑的頻繁圖。使用雙射和方法，把找到的2個具有k條路徑的圖(它們具有相同的k-1條路徑的公共子結(jié)構(gòu))連接成一個k+1條路徑的圖模式。但是因為使用雙射和直接合成2個圖模式可能會造成路徑上個別的公共頂點的丟失，因此必須使用接合方法來彌補這一缺陷，添加丟失的公共頂點給候選模式以確保完全性。接下來移除同構(gòu)圖并計算支持度來確定頻繁性。最后移除所有不是最大的頻繁子圖。
1.2 基于模式增長的頻繁子結(jié)構(gòu)挖掘算法
??? 當(dāng)連接2個大小為k的頻繁子結(jié)構(gòu)產(chǎn)生大小為k+1的圖候選時，基于Apriori算法的系統(tǒng)開銷很大，為避免這種系統(tǒng)開銷，提出了模式增長的方法，主要包括gSpan、CloseGraph和FFSM等。這些算法均通過逐步擴(kuò)展頻繁邊得到頻繁子圖，但每個算法對圖的擴(kuò)展過程也有許多不同之處。
1.2.1 gSpan算法
??? gSpan算法[5]旨在減少復(fù)制圖二度發(fā)現(xiàn)的圖)的產(chǎn)生。它首次提出利用DFS(深度優(yōu)先搜索)法生成頻繁子圖，通過兩大技術(shù)的應(yīng)用——DFS詞典序、最小DFS編碼和最右擴(kuò)展，對每個圖建立DFS詞典序，并達(dá)到將每個圖用最小DFS編碼唯一標(biāo)記的目的，使得無需按Apriori算法的思想而直接生成頻繁子圖。該算法通過選擇一個起始頂點開始訪問，并為能分辨出已經(jīng)訪問過的頂點對其做標(biāo)記，然后對被訪問過的頂點集合反復(fù)擴(kuò)展，直到建立一個完全的深度優(yōu)先搜索(DFS)樹。在構(gòu)造DFS樹時，頂點的訪問順序形成一個線性序(用下標(biāo)來記錄此次序)，設(shè)起始頂點為根，則最后訪問的頂點稱為最右頂點，從根到最右頂點的直接路徑稱為最右路徑。gSpan擴(kuò)展時只進(jìn)行最右擴(kuò)展，即在DFS樹中一條新邊可以添加到最右頂點和最右路徑上另一個頂點之間或者引進(jìn)一個新的頂點并連接到最右路徑上的頂點。把每個加下標(biāo)的圖轉(zhuǎn)換為邊序列稱為DFS編碼，用{i，j，li，l(i，j)，lj}5元組表示，然后通過一定規(guī)則來建立邊序列之間的序，即DFS詞典序，基于詞典序，找到圖的最小DFS編碼。只有對最小DFS編碼執(zhí)行最右擴(kuò)展，才能減少復(fù)制圖的產(chǎn)生，也確保了挖掘結(jié)果的完全性。gSpan無論在計算時間上還是內(nèi)存消耗上都是一種高效的方法。但是由于它對圖模式的表示有一個非常嚴(yán)格的順序，于是有人又提出了挖掘閉頻繁圖的CloseGraph算法。
1.2.2 CloseGraph算法
??? CloseGraph算法[6]提出了一些新的方法，如同等出現(xiàn)(Equivalent Occurrence)和提前終止(Eearly Termination)，利用這些方法可以大大減少沒必要的子圖的生成，最終提高挖掘效率。
??? 給定圖g和圖數(shù)據(jù)集D={G1，G2，…，Gn}，設(shè)τ(g，D)為g在D的每個圖中的子圖同構(gòu)的總數(shù)目，圖g可以通過增加一個新邊e來擴(kuò)展形成新的圖g′，令ζ(g，g′，D)為在D的每個圖中g(shù)(對應(yīng)于g′)的可擴(kuò)展的子圖同構(gòu)的總數(shù)目。如果τ(g，D)＝ζ(g，g′，D)成立，則稱g和g′同等出現(xiàn)，即意味著在D中g(shù)出現(xiàn)時g′一定出現(xiàn)。如
不是閉的，此時僅需要擴(kuò)展g′來代替擴(kuò)展g，這種情況稱為提前終止。
??? CloseGraph算法的執(zhí)行主要分3個步驟：
??? (1)生成一個頻繁圖；
??? (2)根據(jù)一個頻繁圖g是閉的當(dāng)且僅當(dāng)不存在與g具有相同支持度的真超圖g′，亦即如果想知道一個圖是否是閉的，僅需要檢查比它多一條邊的超圖的支持度。如果二者支持度不相等，則g是閉的，否則不是閉的。通過這條規(guī)則可以檢查(1)中生成的圖是否是閉頻繁圖；
??? (3)檢查提前終止的條件和任何一種可能導(dǎo)致提前終止失敗的情況，來決定此生成圖是否應(yīng)該被擴(kuò)展。
??? CloseGraph算法不僅能夠減少不必要的生成子圖而且也能充分地提高挖掘的效率，特別是在挖掘大型圖數(shù)據(jù)集時(比如說多于32條邊的較大的頻繁圖)，它的性能大概可以優(yōu)于gSpan性能的4～10個因子。
1.2.3? FFSM算法
??? FFSM算法[7]采用深度逐層遞歸來挖掘頻繁子圖。每個圖均用一個標(biāo)準(zhǔn)鄰接矩陣CAM(Canonical Adjacency? Matrix)來描述，它使用一種獨特的表示圖結(jié)構(gòu)的規(guī)范形式并且提出兩種有效的候選操作：FFSM聯(lián)接操作(子圖“交”)和FFSM擴(kuò)展操作；使用一種代數(shù)圖結(jié)構(gòu)(非最佳標(biāo)準(zhǔn)的CAM樹)能夠完全地列舉出所有的頻繁子圖；能通過對每1個頻繁子圖的嵌入集合測試完全避免子圖同構(gòu)。其中矩陣的聯(lián)接操作是合并兩個矩陣形成一個矩陣集，而對一個矩陣M的擴(kuò)展操作也會產(chǎn)生一個矩陣集，集合中的每一個矩陣增加了一個額外的節(jié)點以及連接此節(jié)點和M中最后一個節(jié)點的一條邊。
1.3 基于最小描述長度的近似頻繁子結(jié)構(gòu)挖掘算法
??? SUBDUE[8]是一個基于圖的學(xué)習(xí)系統(tǒng)，該系統(tǒng)的輸入可以是帶標(biāo)記或不帶標(biāo)記的簡單圖或圖集，采用了最小描述長度(MDL)原則，挖掘近似的頻繁子結(jié)構(gòu)，并將它們精確地表示出來。它根據(jù)最小描述長度原則，輸出最好的壓縮輸入集的子結(jié)構(gòu)模式，它采用了約束搜索(beam search)方法，通過擴(kuò)展節(jié)點遞增地增長單個頂點。每次擴(kuò)展它都搜索最佳總描述長度：模式的描述長度和圖集合的描述長度，模式全部實例都濃縮成單個節(jié)點。在發(fā)現(xiàn)了最好的子結(jié)構(gòu)以后輸入圖就被重寫，下一次迭代使用重寫的圖作為一個新的輸入圖，這樣，在每次迭代中，算法僅能找到一個子結(jié)構(gòu)。此外SUBDUE進(jìn)行近似匹配，允許子結(jié)構(gòu)有輕微變化，從而支持近似子結(jié)構(gòu)的發(fā)現(xiàn)，而且它也能以預(yù)先確定子圖的形式潛入到背景知識里去。
1.4 基于模式增長和模式歸約的精確稠密頻繁子結(jié)構(gòu)挖掘算法
??? 關(guān)系圖是一種特殊的圖結(jié)構(gòu)，其中每個節(jié)點標(biāo)號在每個圖中僅用一次，它被廣泛地應(yīng)用于大型網(wǎng)絡(luò)(例如生物網(wǎng)絡(luò)、社會網(wǎng)絡(luò)、交通網(wǎng)絡(luò)和萬維網(wǎng))的建模和分析中。在大型關(guān)系圖中頻繁高連通的子圖或稠密子圖是一種令人感興趣的模式。這種模式有助于在社會網(wǎng)絡(luò)中識別具有緊密聯(lián)系的人群，高連通的子圖也可以在生物學(xué)中表示相同功能組件中基因的集合。
??? CloseCut和Splat就是用來在大型關(guān)系圖中(大約有10 k個節(jié)點和1M條邊的關(guān)系圖)挖掘具有連通性約束的閉頻繁圖模式，采用邊連通性的概念并運用相關(guān)的圖論知識來加速挖掘過程。
??? CloseCut實際上是一種基于模式增長的方法，它首先開始于一個小的頻繁候選圖，通過增加新邊來盡可能地擴(kuò)展，直到找到具有相同支持度的閉超圖，在閉超圖中把先前候選圖的頂點壓縮成為一個頂點。然后分解這個高連通性的閉超圖，判斷每個頂點的度是否滿足連通性約束條件，提取滿足連通性約束的子圖，刪除所有的與不滿足連通性約束的頂點連接的邊。然后，通過增加新邊來擴(kuò)展候選圖，并且重復(fù)進(jìn)行上述操作直到?jīng)]有候選圖是頻繁的。
??? Splat是一種模式歸約的方法，它代替從小到大的枚舉圖，而且直接對關(guān)系圖取交并分解它們來得到高連通圖。令模式g是關(guān)系圖Gi1，Gi2，…，Gil(i1
??? 上述方法均是基于圖論的數(shù)據(jù)挖掘方法?；贏priori的方法必須使用寬度優(yōu)先搜索(BFS)策略，因為它逐層產(chǎn)生候選。這種方法為了確定大小為k+1的圖是否頻繁，必須檢查它的所有對應(yīng)的大小為k的子圖來獲得其頻度的上界。這樣，在挖掘任何大小為k+1的子圖之前，類Apriori的方法通常必須完成大小為k的子圖的挖掘。因此類Apriori的算法需要采用BFS，相反，模式增長方法在搜索方式上更加靈活一些，它既可以使用寬度優(yōu)先搜索，也可以使用深度優(yōu)先搜索(DFS)，它要比基于Apriori的方法占用較少的內(nèi)存[4]。
??? AGM和FSG算法都利用鄰接矩陣分別對圖的頂點和邊進(jìn)行逐層構(gòu)造，以最終獲取頻繁子圖。所不同的是，AGM求出了導(dǎo)出子圖，圖不一定連通，而FSG則以邊為每次迭代的對象，求出了連通的頻繁子圖。
??? gSpan算法比AGM、FSG算法計算更高效，而且它采取從內(nèi)存到磁盤交換數(shù)據(jù)，減少了內(nèi)存的消耗。gSpan和FSG算法能夠找到所有符合用戶要求的子圖，但是不可否認(rèn)的是它們都產(chǎn)生大量的子結(jié)構(gòu)，而subDue的特色就在于它能高效地發(fā)現(xiàn)較少數(shù)量的但更有趣的最好地壓縮子結(jié)構(gòu)模式。而這些可能是gSpan和FSG不能發(fā)現(xiàn)的，但是在發(fā)現(xiàn)子圖同構(gòu)方面Subdue不比gSpan和FSG具有更高的效率，還需要進(jìn)一步擴(kuò)展。
??? CloseGraph算法類似于gSpan，但是它只挖掘閉頻繁子圖而且在對一個已經(jīng)生成的圖進(jìn)行最右擴(kuò)展之前，先檢查該圖是否存在提前終止。這樣CloseGraph可以經(jīng)常產(chǎn)生更少的圖模式，因此比挖掘全部模式集合的gSpan更有效。
??? FFSM算法能夠回避圖與圖之間直接的同構(gòu)測試，通過使用一種代數(shù)圖方法能高效地處理子圖同構(gòu)的基本問題，它的性能優(yōu)于gSpan算法。特別是對合成數(shù)據(jù)集使用FFSM算法更高效。
??? 稠密子結(jié)構(gòu)的兩種挖掘算法在大的圖數(shù)據(jù)集上具有良好的可伸縮性。在對具有高支持度和低連通性的模式，CloseCut具有更好的性能，相反，在挖掘的初期階段，Splat能夠過濾低連通性的頻繁圖，對于高連通性約束，它具有更好的性能。但是，當(dāng)關(guān)系圖的數(shù)量增加時，它需要枚舉出取并的關(guān)系圖，此時Splat性能可能會惡化。
??? 在頻繁子圖挖掘算法中，需要解決的問題是子圖同構(gòu)問題和找出所有頻繁子圖的方法上，從頻繁子圖的挖掘上，已經(jīng)取得了較大進(jìn)展，上述這些算法都能夠在滿足一定的要求下，找到所需要的結(jié)果，但是子圖同構(gòu)問題仍沒得到很好地解決(子圖同構(gòu)問題已被證明是NP完全問題)，需要對算法進(jìn)一步擴(kuò)展，有待進(jìn)一步研究。
??? 總結(jié)本文所提到的各種頻繁子結(jié)構(gòu)挖掘算法的共同特征及各自特點如表1所示。
?
??? 圖挖掘已經(jīng)具有了廣泛的應(yīng)用，包括化學(xué)、生物學(xué)、材料科學(xué)、通訊網(wǎng)絡(luò)等領(lǐng)域。利用圖挖掘方法挖掘出的各種頻繁子結(jié)構(gòu)可以被應(yīng)用在大型圖數(shù)據(jù)庫中建立圖索引、進(jìn)行結(jié)構(gòu)相似性搜索，對結(jié)構(gòu)數(shù)據(jù)集合的特征化以及進(jìn)行圖數(shù)據(jù)集的分類和聚類分析。雖然圖挖掘領(lǐng)域的研究剛剛起步，但是因為圖拓?fù)浣Y(jié)構(gòu)在數(shù)學(xué)方面是最重要的結(jié)構(gòu)之一，并且同邏輯語言密切相關(guān)，因此圖挖掘理論和技術(shù)將會在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)方面作出突出的貢獻(xiàn)，并將在各個領(lǐng)域得到廣泛的實際應(yīng)用。
參考文獻(xiàn)
[1]?INOKUCHI A， WASHIO T， MMOTODA? H.An apriori-based algorithm for mining frequent substructures from graph data.In Proc.2000 European Symp.Principle of Data Mining and Knowledge Discovery(PKDD’00)，Lyon，F(xiàn)rance，1998(9):13-33.
[2] KURAMOCHI M， KARYPIS G.Frequent subgraphs discovery.In Proc.2001 Int.Conf.Data Mining(ICDM’01)，San Jose，CA，2001(11)：313-320.
[3] VANETIK N， GUDES E， SHIMONY S.E.Computing frequent graph patterns from semistructured data.In Proc.2002 Int.Conf.on Data Mining(ICDM’02)，Maebashi，Japan，2002(10)：458-465.
[4]?HAN J， KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社， 2007.
[5] YAN X.HAN J.gSpan：Graph-based substructure pattern mining.In Proc.2002 Int.Conf.Data Mining(ICDM’02)，Maebashi，Japan，2002(10)：721-724.
[6]?YAN X， HAN J.Closegraph：mining closed frequent graph patterns.In KDD，2003：286-295.
[7] HUAN J， WANG W， PRINS J.Efficient mining of frequent subgraphs in the presence of isomorphism.In ICDM，? 2003：549-552.
[8] KETKAR? S， HOLDER B， COOK J.Subdue：Compression-Based Frequent Pattern Discovery.In ACM， 2005：71-76.