竇建凱　林欣　胡文心

摘要：圖數(shù)據(jù)的挖掘工作是數(shù)據(jù)挖掘工作中的重要組成部分，已經(jīng)有許多人在這個(gè)領(lǐng)域進(jìn)行了深入的研究.由于數(shù)據(jù)獲取不可避免噪音數(shù)據(jù)，故在挖掘頻繁圖時(shí)考慮近似十分重要.然而許多此前的工作只考慮了子圖間編輯距離（Graph Edit Distance，GED）的絕對(duì)值，而沒有考慮子圖間編輯距離與子圖大小的相對(duì)關(guān)系.提出了一種在單圖中進(jìn)行近似頻繁子圖挖掘的新算法，并在計(jì)算近似程度時(shí)考慮當(dāng)前子圖的大小.該算法通過對(duì)近似頻繁子圖的大小上限進(jìn)行預(yù)測(cè)，并通過局部反單調(diào)性進(jìn)行剪枝，提高了算法的效率.實(shí)驗(yàn)表明，該算法能夠挖掘出傳統(tǒng)算法無法發(fā)現(xiàn)的近似頻繁子圖，且相比對(duì)比算法具有更好的時(shí)間性能.

關(guān)鍵詞：近似; 圖;頻繁子圖挖掘;剪枝

中圖分類號(hào)：TP391.4

文獻(xiàn)標(biāo)志碼：A

DOI： 10.3969/j.issn.1000-5641. 2019.06.008

0 引言

圖是用來表示數(shù)據(jù)的一種特殊數(shù)據(jù)結(jié)構(gòu)，它不僅可以用來表示實(shí)體本身的性質(zhì)，同時(shí)還可以用來表示實(shí)體之間的關(guān)系.圖的這種特點(diǎn)使得圖在多種領(lǐng)域具有廣泛應(yīng)用，如生物信息學(xué)、網(wǎng)絡(luò)分析等.隨著社會(huì)和科學(xué)的發(fā)展，實(shí)體之間的關(guān)系越來越多樣，實(shí)體的數(shù)量越來越多，使用圖結(jié)構(gòu)來表示實(shí)體間的關(guān)系顯得尤為高效，從圖數(shù)據(jù)中挖掘?qū)嵱玫哪Ｊ揭囡@得越來越重要.

然而圖結(jié)構(gòu)雖然能高效地表示實(shí)體間的關(guān)系，但其結(jié)構(gòu)的復(fù)雜性使得從圖中識(shí)別頻繁的子圖也變得困難.如在挖掘有用子圖的過程中，同構(gòu)圖的識(shí)別問題，就被認(rèn)為是一個(gè)NP（Non-deterministic Polynomia）完全問題.因此需要高效的頻繁子圖挖掘的方法.

現(xiàn)有的從圖結(jié)構(gòu)數(shù)據(jù)中挖掘頻繁子圖的方法主要分為兩種：準(zhǔn)確頻繁圖挖掘和近似頻繁圖挖掘.準(zhǔn)確頻繁圖挖掘指從給定圖或圖數(shù)據(jù)庫中挖掘頻繁子圖，當(dāng)記錄每個(gè)子圖的支持度時(shí)，只計(jì)算與當(dāng)前子圖完全一致的同構(gòu)圖的數(shù)量，如gSpan[1]和Grami[2]而近似頻繁圖挖掘與準(zhǔn)確頻圖挖掘的主要區(qū)別為，除了完全一致的同構(gòu)圖，還同時(shí)記錄與當(dāng)前子圖有一定區(qū)別的同構(gòu)圖的數(shù)量，如gApprox[3]與AGraP[4].

由于獲取數(shù)據(jù)的過程中，不可避免數(shù)據(jù)丟失或噪音，因此在實(shí)際應(yīng)用中，近似頻繁子圖挖掘更加符合用戶需求.已有的近似頻繁子圖挖掘算法在計(jì)算兩個(gè)給定圖的近似程度時(shí)，只關(guān)注其近似程度的絕對(duì)值，即從一個(gè)圖轉(zhuǎn)化為另一個(gè)圖需要的操作數(shù)的絕對(duì)值;而在實(shí)際應(yīng)用中，在衡量兩個(gè)圖的近似程度時(shí)，圖本身的大小也是非常重要的衡量指標(biāo).

針對(duì)以上現(xiàn)有的近似頻繁子圖挖掘算法的問題，本文提出了子圖大小相關(guān)的近似頻繁子圖算法.該算法改進(jìn)了子圖近似程度的計(jì)算方式，使得近似程度的結(jié)果與當(dāng)前候選子圖的大小有關(guān).算法首先通過一個(gè)基于深度優(yōu)先搜索策略的算法，以及基于給定頻繁程度和近似程度的子圖大小上限算法，生成所有符合大小要求的候選子圖;然后對(duì)每個(gè)候選子圖生成一個(gè)最小的、需要搜索的近似子圖集合，并對(duì)其中的每個(gè)近似子圖進(jìn)行圖同構(gòu)搜索;最后計(jì)算所有匹配的同構(gòu)圖中，互斥的同構(gòu)圖的數(shù)量并將其作為子圖的近似支持度.

本文算法的主要難點(diǎn)有：①隨著給定圖的大小增加，候選子圖的數(shù)量呈指數(shù)增加，因此需要一個(gè)有效的搜索方式及early-stop的條件;②對(duì)任意一個(gè)候選子圖，其近似子圖的數(shù)量隨候選子圖的大小呈指數(shù)式增加，且由于圖同構(gòu)問題是一個(gè)NP完全問題，因此高效的識(shí)別同構(gòu)圖十分困難;③計(jì)算所有近似匹配中互斥匹配的數(shù)量，及候選子圖的近似支持度的問題，可以轉(zhuǎn)化為MIS（Maximum Independent Set）問題[5]，而MIS問題是一個(gè)公認(rèn)的NP完全問題，因此計(jì)算子圖的近似支持度是一個(gè)重要且困難的問題.

基于以上算法的主要難點(diǎn)，本文的主要貢獻(xiàn)如下.

（1）基于深度優(yōu)先搜索策略的候選子圖生成算法、候選子圖大小上限的計(jì)算方法.

（2）提出了一個(gè)基于點(diǎn)和邊的刪除嘗試策略的近似子圖生成算法、高效的圖匹配算法.

（3）根據(jù)近似頻繁子圖的特點(diǎn)，利用候選子圖的支持度上限，來代替候選子圖的準(zhǔn)確支持度，極大地提高了算法的效率.

（4）實(shí)驗(yàn)證明，與對(duì)比算法相比，本文算法不僅高效，同時(shí)能發(fā)現(xiàn)對(duì)比算法無法發(fā)現(xiàn)的近似頻繁子圖.

本文的結(jié)構(gòu)如下：第1節(jié)介紹一些與本文提出算法及目標(biāo)相關(guān)的工作;第2節(jié)介紹一些相關(guān)概念;第3節(jié)到第5節(jié)詳細(xì)介紹本文算法的3大模塊;第6節(jié)通過實(shí)驗(yàn)展現(xiàn)本文算法的有效性;第7節(jié)給出本文的總結(jié)與展望.

1 相關(guān)工作

頻繁子圖挖掘指的是，給定一個(gè)頻繁程度下限，從給定的圖或圖集合中挖掘出全部的、符合頻繁程度要求的子圖.因此頻繁子圖挖掘問題主要分為兩種：單圖中的頻繁子圖挖掘和圖集合上的頻繁子圖挖掘.圖集合上的頻繁子圖挖掘已經(jīng)有許多成熟的工作，如，gSpan算法[1]，在圖集合中挖掘頻繁子圖，避免了候選子圖的生成;Gaston算法[6]修改了搜索策略，從而使得算法速度加快.類似的算法還有g(shù)Red[7]和GraphSig[8].這些算法的不同及其優(yōu)缺點(diǎn)在Cheng等的文章[9]和Krishna等的文章[10]中有詳述的論述.

近年來，隨著數(shù)據(jù)規(guī)模的增大和需求的不斷變化，一些特殊的頻繁子圖挖掘算法也不斷被提出.如，Choudhury等研究了在動(dòng)態(tài)不斷變化的圖中挖掘可擴(kuò)展的子圖[11]，他們提出的算法可以隨著給定圖的變化，動(dòng)態(tài)地判定某個(gè)子圖是否頻繁;Ingalalli等研究了在多重圖中的頻繁子圖挖掘[12]，其所提出的算法的目的是適應(yīng)不斷豐富且復(fù)雜化的數(shù)據(jù)，除此之外，該算法在應(yīng)用于簡單圖上時(shí)，也能取得良好的效果.

雖然單圖中的頻繁子圖挖掘工作已經(jīng)在多種應(yīng)用中被提及，如Alguliev等的工作[13]和Lima等的工作[14]，以及Elseidy等人提出的Grami算法[2]，都能有效地從單圖中挖掘頻繁子圖.但對(duì)單圖中的頻繁子圖挖掘的研究，仍然少于圖集合中的頻繁子圖挖掘的研究.研究表明，單圖中的頻繁子圖挖掘算法可以通過簡單修改，應(yīng)用于圖集合上;然而圖集合上的算法并不能應(yīng)用于單圖中[5].

近似頻繁子圖挖掘是在頻繁子圖挖掘的基礎(chǔ)上，當(dāng)計(jì)算一個(gè)子圖的支持度時(shí)，除了與該子圖完全一致的匹配，同時(shí)計(jì)算滿足一定近似程度的匹配.近似程度的計(jì)算通常有圖的編輯距離[15]、結(jié)構(gòu)區(qū)別[16]、特性區(qū)別[17]等幾種方式.已經(jīng)有一些近似頻繁子圖挖掘方面的工作，如Holder等在SUBDUE上設(shè)計(jì)了一種變形函數(shù)[18]，使計(jì)算支持度時(shí)可以計(jì)算有一定區(qū)別的近似匹配;Chen等的gApprox在無標(biāo)簽的圖上，設(shè)計(jì)了函數(shù)計(jì)算圖之間的編輯距離[18];Jia等的APGM通過相容性矩陣計(jì)算圖之間的距離，從而允許子圖的近似匹配與子圖之間可以有點(diǎn)的區(qū)別[19].AGraP[4]算法在此基礎(chǔ)上進(jìn)行了改進(jìn)，從而允許近似匹配與子圖之間擁有點(diǎn)和邊上的區(qū)別，包括缺失和替換等.Flores-Garrido等在AGraP上進(jìn)行了修改，使算法挖掘全部近似頻繁子圖的子集CloseAFG[20].

除此之外，Acosta-Mendoza等研究了在多重圖上的近似頻繁子圖挖掘[21]，并利用范式的思想，使算法在時(shí)間成本和可擴(kuò)展性上都有良好的效果.同時(shí)，Acosta-Mendoza等利用近似頻繁子圖挖掘算法，設(shè)計(jì)了新的圖像分類算法[22]，他們利用近似頻繁子圖挖掘算法的結(jié)果，作為圖像分類中圖像的特征，從而實(shí)現(xiàn)了在過程中自動(dòng)計(jì)算和獲取需求的替換矩陣，并獲得了令人滿意的結(jié)果，再次證明了近似頻繁子圖算法具有實(shí)際的意義.同時(shí)，Acosta-Mendoza等也對(duì)近似頻繁子圖挖掘算法的結(jié)果，在圖像聚類方面的應(yīng)用做了研究[23]，并通過實(shí)驗(yàn)表明，以近似頻繁子圖作為聚類的特征，同樣可以提升聚類的效果.

然而已有的近似頻繁子圖的挖掘算法，在計(jì)算近似程度時(shí)，只考慮了編輯距離的絕對(duì)值，而忽略了圖大小對(duì)近似程度的影響.因此，本文提出了子圖大小相關(guān)的近似程度計(jì)算方式，并在此基礎(chǔ)上設(shè)計(jì)了算法挖掘符合要求的近似頻繁子圖.

2 基本概念

定義1標(biāo)簽圖一個(gè)標(biāo)簽圖G是一個(gè)四元組G=（V，E，L，f），V表示圖中所有點(diǎn)的集合，E表示邊的集合，L是所有標(biāo)簽的集合，，：V，E一L是一個(gè)映射函數(shù)，將L中的標(biāo)簽映射到每個(gè)點(diǎn)和邊上.

這是一個(gè)被廣泛應(yīng)用的定義，圖中的點(diǎn)表示實(shí)體，邊表示實(shí)體之間有一定關(guān)系，點(diǎn)上的標(biāo)簽表示實(shí)體的屬性或類別，邊上的標(biāo)簽表示的是實(shí)體之間關(guān)系的類別.如在蛋白質(zhì)相互作用圖（PPI： Protein-Protein Interaction）中，點(diǎn)表示蛋白質(zhì)，點(diǎn)上的標(biāo)簽可以表示蛋白質(zhì)種類.因此有許多點(diǎn)具有相同的標(biāo)簽，邊表示蛋白質(zhì)之間可以發(fā)生相互作用，邊的標(biāo)簽表示相互作用的種類.

定義5子圖的近似支持度δ給定圖G和近似程度下限θ，圖g在圖G中的兩個(gè)近似匹配如果不包含任何相同的點(diǎn)，則說這兩個(gè)近似匹配是互斥的.圖g在圖G中的支持度δ指圖g能在圖G中找到的互斥的近似匹配的最大數(shù).

通過以上定義，可以對(duì)單圖中的近似頻繁子圖挖掘問題給出形式化定義：給定單圖G，支持度下限δ和近似程度下限θ，單圖中的近似頻繁子圖挖掘的目的是，找出圖G的所有近似支持度θ'≥δ的子圖.

定義6置信度ρ 給定圖G和近似程度下限θ，圖g和圖g'是圖G中的子圖，其近似支持度分別為θ1和θ2，且g是g'的子圖，則置信度ρ是指在子圖g表示的實(shí)體間的關(guān)系成立的前提下，子圖g'表示的實(shí)體間關(guān)系成立的概率，即p=θ2/θ1.

例如圖1中圖G（圖1（b）），若設(shè)δ=2且θ=0.8，圖G的所有近似頻繁子圖如圖2所示.

本文算法的框架如圖3所示，算法主要分為3個(gè)部分：①第一部分遍歷給定圖的所有候選子圖，由于子圖數(shù)量過多，此處通過預(yù)測(cè)來確定可能的頻繁子圖的大小上限，提高遍歷速度.②算法第二部分對(duì)每個(gè)子圖生成所有的近似匹配，由于當(dāng)近似程度下限為1時(shí)，尋找近似匹配的問題實(shí)際上是子圖同構(gòu)問題，二子圖同構(gòu)問題被廣泛認(rèn)為是一個(gè)NP-complete的問題，為了降低計(jì)算成本，算法利用生成和搜索過程，在生成階段，對(duì)候選子圖的每個(gè)結(jié)點(diǎn)和邊進(jìn)行嘗試刪除，生成所有符合近似要求，且不互相包含的近似子圖;在搜索過程，對(duì)每個(gè)近似子圖進(jìn)行查詢，③第三部分主要對(duì)子圖的近似支持度進(jìn)行計(jì)算.本文算法的原理和詳細(xì)過程將在下面幾節(jié)中詳細(xì)闡述.

3 候選子圖生成

定理1候選子圖大小上限對(duì)給定圖G，支持度下限δ和近似程度下限θ，有可能成為近似頻繁子圖的子圖g的大小上限為

（2）從圖G中移除點(diǎn)1，然后回到步驟（1），任選另一個(gè)點(diǎn)開始，直到圖G中沒有點(diǎn).

為了實(shí)現(xiàn)策略中的步驟（1），本文設(shè)計(jì)了以下算法，具體步驟如下.

（1）如圖4所示，從點(diǎn)l開始，將點(diǎn)1標(biāo)記為“必須的”.

（2）以當(dāng)前子圖為起點(diǎn)，標(biāo)記其所有鄰居結(jié)點(diǎn)為被標(biāo)記的，如圖4中的點(diǎn)1，2，3.

（3）使用鄰居結(jié)點(diǎn)依次擴(kuò)展當(dāng)前子圖，獲得的子圖依次為01，02，03.

（4）每獲得一個(gè)新子圖，判斷其大小是否超出候選子圖大小上限.若不超出，以當(dāng)前子圖為新起點(diǎn)，重復(fù)步驟（2）.

（5）若獲得的子圖大小超出候選子圖大小上限，則終止當(dāng)前擴(kuò)展策略，嘗試擴(kuò)展下一個(gè)被標(biāo)記的鄰居結(jié)點(diǎn).

圖4中，不考慮最小近似程度和支持度，所有獲得的子圖按順序應(yīng)為：0，01，012，0123，01234， 012345， 0123456， 012346， 01235， 0125-

反單調(diào)性是提高挖掘效率的重要條件.在頻繁圖挖掘中，反單調(diào)性是指，給定圖G中，若圖g'是圖g的子圖，且圖g'與圖g這兩圖都是圖G的子圖，則圖g在G中的支持度必然不超過g'在G中的支持度.在利用近似程度的絕對(duì)值，即點(diǎn)或邊的缺失數(shù)量作為衡量指標(biāo)時(shí)，反單調(diào)性是滿足的.如圖5中，若設(shè)最小支持度為3，最多缺失點(diǎn)或邊的數(shù)量為2，則圖5（a）和圖5（b）在圖G中都是近似頻繁的.但本文中，反單調(diào)性并不能全局保持.如圖5中，圖5（a）是圖5（b）的子圖，但若設(shè)δ=2，θ=0.7，由于圖5（a）的近似匹配可以允許最多1個(gè)點(diǎn)或邊的缺失（由于任何點(diǎn)或邊的缺失都會(huì)造成圖的不連通，因此（a）沒有任何近似子圖），而圖5（b）可以允許最多兩個(gè)點(diǎn)或邊的缺失，因此圖5（b）擁有更多的近似匹配（如刪除點(diǎn)A及相連的邊），圖5（b）是一個(gè)近似頻繁子圖，而圖5（a）不是.

本文提出部分反單調(diào)性的概念，定理如下.

定理2局部反單調(diào)性給定圖g和近似程度θ，圖g'是圖g的子圖，在滿足近似程度的前提下，若圖g可允許的點(diǎn)和邊的缺失數(shù)量，等于圖g'可允許的點(diǎn)和邊的缺失數(shù)量，即0≤（|g|- |g'|）×（1-θ）<1，則g'的支持度不超過g的支持度.

證明 當(dāng)子圖g'和圖g允許缺失的點(diǎn)或邊的數(shù)量相同時(shí)，圖g的任意近似匹配必然是圖g'的某個(gè)近似匹配的超圖，而g'的互斥近似匹配的數(shù)量，即g'的支持度，必然不超過其互斥的超圖的數(shù)量，即g的支持度.

根據(jù)局部反單調(diào)性，可以在前述算法上繼續(xù)剪枝，即在使用當(dāng)前子圖做新輸入時(shí)，若當(dāng)前子圖的支持度不符合最小支持度的要求，則可以直接擴(kuò)展當(dāng)前子圖，而不需要判斷其是否頻繁，直到可允許的點(diǎn)或邊的數(shù)量發(fā)生改變.因此，不需要對(duì)每個(gè)候選子圖生成近似匹配和支持度的計(jì)算，從而可以節(jié)省大量時(shí)間成本.同時(shí)，由局部反單調(diào)性的證明可知，當(dāng)兩個(gè)子圖之間的關(guān)系符合局部反單調(diào)性的要求，則其中較大的圖的所有近似匹配，必然是其子圖的某個(gè)近似匹配的超圖，因此可以通過記錄子圖的所有近似匹配，減少超圖的近似匹配的搜索范圍，從而節(jié)省大量時(shí)間成本.改進(jìn)后算法流程如圖6所示.

4 近似匹配生成

4.1 近似子圖生成

定義7近似子圖給定圖g，近似程度θ，當(dāng)且僅當(dāng)g的子圖g'與g的相似度超過θ，即θ≤|g|- |g'|/|g|，則稱g'是g的一個(gè)近似子圖.

為了查詢每個(gè)候選子圖的近似支持度，需要針對(duì)每個(gè)候選子圖，找出其在圖中的所有近似匹配.為此提出了一個(gè)定理，并在此基礎(chǔ)上設(shè)計(jì)了一個(gè)基于點(diǎn)和邊的刪除的生成算法，來找出候選子圖的所有符合近似條件的子圖.

定理3 給定圖G和近似程度θ，圖g是G的子圖，圖a和圖b是g的子圖，a 是b的子圖，則任意b在G中的匹配，都與至少一個(gè)a 在G中的匹配有重復(fù)點(diǎn).

證明 任意b在G中的匹配，是b的一個(gè)同構(gòu)圖，則a是此匹配的一個(gè)子圖，因此此匹配包含a，即包含一個(gè)a在G中的匹配，因此任意b在G中的匹配，都與至少一個(gè)a在G中的匹配有重復(fù)點(diǎn).

根據(jù)定理3，可以確定對(duì)任意候選子圖，其最小需要進(jìn)行匹配的近似子圖集合中，應(yīng)不含兩個(gè)圖具有包含關(guān)系.

基于以上定理，本文設(shè)計(jì)了一個(gè)基于點(diǎn)和邊的刪除的子圖生成算法，生成給定候選子圖的所有符合近似條件的子圖，其基本思路如下，具體算法見算法1.

（1）對(duì)所有點(diǎn)和邊進(jìn)行編號(hào)，并按編號(hào)排序，計(jì)算給定候選子圖g在給定的近似條件θ下，可以允許的缺失的點(diǎn)或邊的最大數(shù)量，即|g|×（1- 0）.

（2）遍歷所有編號(hào)，嘗試刪除編號(hào)對(duì)應(yīng)的點(diǎn)或邊，并判斷結(jié)果是否連通.若連通，則將編號(hào)對(duì)應(yīng)的點(diǎn)或邊標(biāo)記為已刪除，并更新當(dāng)前已刪除的點(diǎn)或邊的數(shù)量.若不連通，則跳過當(dāng)前編號(hào)，繼續(xù)嘗試.

（3）以步驟（2）的結(jié)果為新的起點(diǎn)，繼續(xù)遍歷剩余編號(hào)，直至已刪除的點(diǎn)或邊的數(shù)量到達(dá)最大數(shù)量，或剩余任意點(diǎn)或邊的刪除都會(huì)導(dǎo)致數(shù)量超出最大值，則當(dāng)前結(jié)果即為一個(gè)近似子圖.

（4）跳過最后一個(gè)被刪除的點(diǎn)或邊，繼續(xù)步驟（2），直到所有點(diǎn)或邊的組合刪除都被嘗試過.

步驟（3）的所有結(jié)果，即為最終需要進(jìn)行匹配的候選子圖的近似圖，由于每個(gè)子圖被刪除的點(diǎn)或邊的數(shù)量不超出最大值，保證了所有結(jié)果都是候選子圖的近似圖;同時(shí)，由于任意一個(gè)子圖都刪除了允許刪除的最多的點(diǎn)或邊，保證了任意兩個(gè)結(jié)果不具有包含關(guān)系.

4.2 近似子圖匹配

為了對(duì)每個(gè)候選子圖，生成對(duì)應(yīng)的近似匹配，本文設(shè)計(jì)了一種在單圖中查詢給定子圖的所有同構(gòu)圖的算法.給定圖G=（V， E，L，f），目的是找到一個(gè)合適的點(diǎn)的順序，使得查找過程的時(shí)間花費(fèi)最小，即在第i步，需要從未找到匹配的點(diǎn)中，選擇一個(gè)點(diǎn)，使得該點(diǎn)一旦找到匹配，則已被匹配的圖的大小增大最多，或使得可能匹配的數(shù)量減小到最小.

為了完成上述要求，需要對(duì)所有的可能匹配進(jìn)行最大的約束，使得算法能盡早過濾掉錯(cuò)誤匹配.為此，本文設(shè)計(jì)了一種貪心算法，為給定圖中的所有點(diǎn)，生成一個(gè)匹配順序.

算法首先初始化點(diǎn)的匹配順序丁為空，從擁有最多鄰居結(jié)點(diǎn)的點(diǎn)開始，若有多個(gè)點(diǎn)擁有相同的鄰居數(shù)量，則根據(jù)點(diǎn)的標(biāo)簽，在目標(biāo)圖中擁有最少對(duì)應(yīng)標(biāo)簽的點(diǎn)的點(diǎn)，作為起始點(diǎn)，插入匹配順序丁，對(duì)剩余未插入匹配順序的點(diǎn)，按照以下條件插入匹配順序.

獲得匹配順序后，算法根據(jù)匹配順序，對(duì)任意一個(gè)未匹配的點(diǎn)，遍歷目標(biāo)圖中的點(diǎn)，檢測(cè)是否符合匹配要求，若符合要求，則記錄該匹配，并按順序?qū)ふ蚁乱粋€(gè)未匹配點(diǎn)的匹配;若不符合，則跳過該點(diǎn)，嘗試目標(biāo)圖中的下一個(gè)點(diǎn)進(jìn)行匹配.算法通過匹配順序，對(duì)任意一個(gè)未匹配的點(diǎn)，僅計(jì)算其前一個(gè)已匹配的點(diǎn)的所有對(duì)應(yīng)點(diǎn)的鄰居結(jié)點(diǎn)中，未被匹配到任何一個(gè)點(diǎn)上的點(diǎn)，具體見圖7.

5 支持度計(jì)算及結(jié)果展示

5.1 支持度計(jì)算

在獲得了每個(gè)候選子圖在給定圖中的近似匹配后，需要判斷一個(gè)候選子圖是否是近似頻繁圖.根據(jù)子圖的近似支持度的定義（定義5），一個(gè)候選子圖的支持度應(yīng)該是候選子圖所有近似匹配中，可能的互斥的近似匹配的最大數(shù)量.然而，確定這個(gè)最大數(shù)量可以被轉(zhuǎn)化為最大獨(dú)立集（Maximum Independent Set，MIS）問題，這是一個(gè)NP-complete的問題，因此計(jì)算一個(gè)候選子圖的準(zhǔn)確近似支持度是十分耗時(shí)和困難的.

然而，在本文的情況下，在計(jì)算子圖的匹配時(shí)，已經(jīng)利用的是子圖的近似匹配，因此一個(gè)候選子圖的準(zhǔn)確近似支持度其實(shí)不是非常重要.此處本文參考了gApprox算法中支持度的計(jì)算方式，為每個(gè)候選子圖的近似支持度計(jì)算了一個(gè)上限閾值，本文相信這個(gè)閾值在本文問題中已經(jīng)足夠可以作為參考，來判斷一個(gè)候選子圖是否近似頻繁.計(jì)算方式如下.

（1）將候選子圖的一個(gè)匹配圖的頂點(diǎn)作為一個(gè)集合，初始化近似支持度上限為0.

（2）計(jì)算候選子圖的所有匹配圖的點(diǎn)集中的點(diǎn)的出現(xiàn)次數(shù)，即每個(gè)點(diǎn)出現(xiàn)在多少個(gè)匹配圖中，并按數(shù)字從大到小排序.

（3）選擇出現(xiàn)次數(shù)最高的點(diǎn)，若有多個(gè)，則任選一個(gè).將近似支持度上限加1，刪除所有包含該點(diǎn)的匹配圖的點(diǎn)集，并更新每個(gè)點(diǎn)的出現(xiàn)次數(shù).

（4）不斷迭代第（3）步，直到所有的點(diǎn)集都被刪除，

假設(shè)有一個(gè)候選子圖的所有近似匹配有{v1，v2），{v1，v3），{v2，v3），{v1，v4），{v4，v5），根據(jù)上述算法，初始化支持度上限為O，點(diǎn)V1出現(xiàn)在3個(gè)近似匹配中，是所有點(diǎn)中最多的，則刪除所有包含v1的近似匹配;支持度上限加l，剩余的近似匹配為{v2，v3），{v4，v5），繼續(xù)迭代，刪除所有包含點(diǎn)v2的;上限加1，然后刪除包含v4的匹配，上限加l;此時(shí)所有匹配已經(jīng)被刪除，停止迭代，得到最終上限為3.

定理4 所有候選子圖的真實(shí)近似支持度都不超過上述算法中的支持度上限.

證明 由于對(duì)于任意一個(gè)點(diǎn)，只記錄一次近似匹配，即只將支持度上限加1，相當(dāng)于記錄了一個(gè)包含該點(diǎn)的近似匹配，則保證了記錄的近似匹配至少在該點(diǎn)上是互斥的，但由于并不保證在所有點(diǎn)上都是互斥的，因此支持度上限必然大于或等于真實(shí)的近似支持度.

5.2 結(jié)果展示

通過上節(jié)算法計(jì)算，可以獲得每一個(gè)候選近似頻繁子圖的近似支持度;在與給定的支持度閾值進(jìn)行比較之后，可以最終確定一個(gè)候選近似頻繁子圖是否頻繁.為了提高算法結(jié)果的展示效果，以及提高算法效率，對(duì)算法挖掘結(jié)果的展示作以下約束，

第一，對(duì)具有相同結(jié)構(gòu)，以及相同標(biāo)簽的結(jié)果圖，只在結(jié)果中展示一次，

第二，對(duì)于每個(gè)結(jié)果圖，需展示其點(diǎn)的ID和標(biāo)簽，以及邊的左右兩點(diǎn)的ID和標(biāo)簽，其中ID是重新編輯的，

第三，對(duì)于每個(gè)結(jié)果圖，展示其近似頻繁程度和全部對(duì)應(yīng).

以上約束中，第一條的原因是在候選子圖的生成中，可能有多個(gè)具有相同標(biāo)簽和結(jié)構(gòu)的子圖，由于其在給定單圖中的位置不同，可能出現(xiàn)多次，如圖8（a）中，點(diǎn)0和點(diǎn)1組成的圖，與點(diǎn)4和點(diǎn)3組成的圖結(jié)構(gòu)和標(biāo)簽都相同，但在圖中的位置不同，因此會(huì)在候選子圖生成的過程中出現(xiàn)兩次.為了提高算法效率，在記錄候選子圖時(shí)，僅記錄其中一個(gè)，對(duì)生成的每一個(gè)候選子圖，首先與已經(jīng)被記錄的候選子圖作比較，若果有相同結(jié)構(gòu)和標(biāo)簽的記錄，則不再記錄此子圖，對(duì)于第二條與第三條約束，主要目的是為了更好地理解近似頻繁子圖的結(jié)構(gòu)，以及更好地展示其近似匹配.如圖8（a）中的點(diǎn)O和點(diǎn)2組成的子圖，若其為近似頻繁子圖，則顯示結(jié)果為圖8（b）.

6 實(shí)驗(yàn)

本文設(shè)計(jì)了兩種實(shí)驗(yàn)來證明本文算法的有效性，以及發(fā)現(xiàn)更多近似頻繁子圖的能力.第一種實(shí)驗(yàn)為有效性試驗(yàn)，實(shí)驗(yàn)分別在真實(shí)數(shù)據(jù)及人工數(shù)據(jù)上進(jìn)行.第二種實(shí)驗(yàn)僅基于人工數(shù)據(jù)，用于證明本文算法與使用近似程度絕對(duì)值算法相比，本文算法可以發(fā)現(xiàn)更多的近似頻繁子圖.所有實(shí)驗(yàn)的真實(shí)數(shù)據(jù)抽取自PPI網(wǎng)絡(luò)，PPI網(wǎng)絡(luò)獲取自DIP（Database of Interacting Proteins）數(shù)據(jù)庫（http：//dip.doe-mbi.ucla.edu），人工數(shù)據(jù)由NetworkX工具（https：//networkx.github.io/ documentation/stable/）構(gòu)建.所有實(shí)驗(yàn)都在1臺(tái)Windows設(shè)備上完成，設(shè)備配置為CPU i5-4690，8 GB MEM.實(shí)驗(yàn)程序由Java完成.據(jù)本文所知，目前已有的與本文算法目的最接近的算法為AGraP，因此本文所有實(shí)驗(yàn)中的對(duì)比實(shí)驗(yàn)為AGraP算法，本文僅修改了AGraP中的近似度計(jì)算公式與支持度計(jì)算方式，使對(duì)比實(shí)驗(yàn)基于同一種相似度公式，從而降低不同相似度公式造成的影響.

由于對(duì)比算法AGraP在使用子圖大小相關(guān)的相似度時(shí)效率較低，算法時(shí)間和空間消耗隨給定圖大小的增長而增長過快，受條件限制，無法完成對(duì)普通大小的圖的挖掘.因此本文通過NetworkX工具分別生成了7個(gè)、9個(gè)、11個(gè)、13個(gè)點(diǎn)的樣本圖（G7、G9、G11、G13），并在樣本圖上進(jìn)行挖掘，取θ= 0.9，δ=2，結(jié)果表1所示.

通過表l可知，本文算法相對(duì)于AGraP算法有較大優(yōu)勢(shì)，且由于AGraP算法時(shí)間消耗隨圖大小增長過快，因此不適于對(duì)較大的圖的挖掘，而本文算法隨著圖大小的增長，雖然時(shí)間消耗有所增加，但增長速度相對(duì)較為合理，

除了在樣本圖上的對(duì)比實(shí)驗(yàn)，本文利用本文算法，對(duì)規(guī)模更大的圖進(jìn)行了挖掘，從而展示本文算法除了可以應(yīng)用于十分小的樣本圖，同樣可以應(yīng)用于較大規(guī)模的圖，本文在人工數(shù)據(jù)與真實(shí)數(shù)據(jù)上都進(jìn)行了實(shí)驗(yàn).人工數(shù)據(jù)同樣由NetworkX工具生成，為了顯示算法效率隨圖大小的變化，分別生成了100個(gè)、125個(gè)、150個(gè)、175個(gè)、200個(gè)點(diǎn)的不同大小的圖.

實(shí)驗(yàn)真實(shí)數(shù)據(jù)來自于PPI網(wǎng)絡(luò).PPI網(wǎng)絡(luò)為蛋白質(zhì)交互網(wǎng)絡(luò)，其中包含多種已被發(fā)現(xiàn)的蛋白質(zhì)及蛋白質(zhì)交互反應(yīng).其中有多條蛋白質(zhì)對(duì)擁有高于10-7的BLAST（Basic LocalAlignment Search Tool）相似度，本文認(rèn)為這些蛋白質(zhì)對(duì)具有極其相似的的性質(zhì)，因此可以用相同的標(biāo)簽做標(biāo)記，不同的蛋白質(zhì)之間有不同種類的反應(yīng)，每種反應(yīng)可以用不同的標(biāo)簽進(jìn)行標(biāo)記，因此PPI網(wǎng)絡(luò)可以轉(zhuǎn)化為一個(gè)標(biāo)簽圖，本文從中分別抽取了5個(gè)不同的250個(gè)點(diǎn)（GIOO、G125、G150、G175、G200、G250（真）），作為實(shí)驗(yàn)數(shù)據(jù)，并將其結(jié)果取平均數(shù)作為真實(shí)數(shù)據(jù)上的結(jié)果.實(shí)驗(yàn)結(jié)果如圖9、圖10所示.

從圖9、圖10中可以發(fā)現(xiàn)，算法的時(shí)間消耗隨近似支持度要求的提升不斷降低，原因是隨著近似支持度要求的提升，更多的候選子圖在早期被過濾掉，根據(jù)局部反單調(diào)性的特點(diǎn)，其特定大小范圍內(nèi)的超圖都不可能是頻繁的，因此減少了需要生成近似子圖及近似子圖匹配的候選子圖數(shù)量，大大節(jié)省了時(shí)間消耗.同樣地，隨著近似程度要求的降低，每個(gè)候選子圖會(huì)擁有更多的近似子圖，因此需要進(jìn)行匹配的近似子圖增加，同時(shí)，更多的候選子圖被判定為頻繁，因此時(shí)間消耗上升.除此之外，給定單圖的大小對(duì)時(shí)間消耗也具有較大的影響，原因是隨給定單圖大小增加，其候選子圖的數(shù)量呈指數(shù)上升，因此時(shí)間消耗上升.

除上述實(shí)驗(yàn)，本文還在樣本圖上進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)主要比較本文算法發(fā)現(xiàn)的近似頻繁子圖數(shù)量，與利用近似程度絕對(duì)大小的算法發(fā)現(xiàn)的近似頻繁子圖的數(shù)量的區(qū)別.實(shí)驗(yàn)利用的樣本圖為圖8（a）.實(shí)驗(yàn)對(duì)比算法為本文算法的修改版，即近似程度計(jì)算公式為缺失的點(diǎn)或邊的絕對(duì)值.實(shí)驗(yàn)設(shè)置近似程度相對(duì)值θ為0.6，對(duì)比算法中近似程度絕對(duì)值為1，即僅允許一個(gè)點(diǎn)或一條邊的缺失，近似支持度δ都為3.實(shí)驗(yàn)結(jié)果如表2.

如表2所示，本文算法利用候選子圖大小相關(guān)的近似度相對(duì)值計(jì)算公式，在近似支持度設(shè)置為3時(shí)，發(fā)現(xiàn)候選子圖B-A-C為近似頻繁子圖，而對(duì)比算法利用缺失點(diǎn)或邊的絕對(duì)值，則忽略了該候選子圖.

7 結(jié)論

隨著數(shù)據(jù)規(guī)模的增加和數(shù)據(jù)中可能產(chǎn)生的噪音數(shù)據(jù)量的增長，近似頻繁子圖挖掘算法將受到越來越廣泛的關(guān)注，因此，近似頻繁子圖挖掘算法需要根據(jù)候選子圖大小，來判斷可容忍的噪音數(shù)據(jù)量的多少，即可容忍的數(shù)據(jù)缺失數(shù)量是多少.本文設(shè)計(jì)了一種利用候選子圖大小相關(guān)的近似程度計(jì)算公式，從而允許不同大小子圖缺失不同數(shù)量的點(diǎn)或邊的近似頻繁子圖挖掘算法.該算法利用缺失點(diǎn)或邊的數(shù)量與子圖大小的百分比作為近似程度計(jì)算的標(biāo)準(zhǔn)，通過候選子圖生成，近似子圖生成及匹配，近似支持度的計(jì)算幾個(gè)步驟，實(shí)現(xiàn)了候選子圖大小相關(guān)的近似頻繁子圖挖掘算法.人工數(shù)據(jù)和真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)都表明，本算法效率更高，且能發(fā)現(xiàn)利用缺失點(diǎn)或邊數(shù)量絕對(duì)值作為近似程度的算法不能發(fā)現(xiàn)的候選子圖.在未來的工作中，希望能進(jìn)一步提高算法效率，使得算法能在大規(guī)模數(shù)據(jù)上應(yīng)用.

[參考文獻(xiàn)]

[1]YAN x F，HAN J W. gSpan： Graph-based substructure pattern mining [Cl// Proceedings of the 2002 IEEEInternational Conference on Data Mining. 2002：721-724.

[2] ELSEIDY M，ABDELHAMID E，SKIADOPOULOS s，et al.GraMi： Frequent subgraph and pattern mining ina single large graph [J]. Proceedings of the VLDB Endowment， 2014，7：517-528.

[3] CHEN c，YAN x F，ZHU F D，et al.gApprox： Mining frequent approximate patterns from a massive network[C]// 7th IEEE International Conference on Data Mining. 2007：445-450.

[4] FLORES-GARRIDO M，CARRASCO-OCHOA J A，MARTINEZ-TRINIDAD J F.AGraP： An algorithm formining frequent patterns in a single graph using inexact matching [J]. Knowledge and Information Systems，2015，2（44）： 385-406.

[5] KURAMOCHI M，KARYPIS G.Finding frequent patterns in a large sparse graph[J].Data Mining and Knowl-edge Discovery， 2005， 11（3）： 243-271

[6] NIJSSEN s，KOK J N A quickstart in frequent structure mining can make a difference [Cl// Proceedings of thelOth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2004： 647-652.

[7] ALONSO A G，PAGOLA J E M，CARRASCO-OCHOA J A，et al.Mining frequent connected subgraphs reducingthe number of candidates [C]// Joint European Conference on Machine Learning and Knowledge Discovery inDatabases. 2008： 365-376.

[8] RANU s，SINGH A K.Graphsig：A scalable approach to mining significant subgraphs in large graph databases[C]// 2009 IEEE 25th International Conference on Data Engineering. 2009： 844-855.

[9] CHENG H，YAN x F，HAN J W. Mining graph patterns [C]// Frequent Pattern Mining， Berlin： Springer， 2014：307-338.

[10] KRISHNA V，SURI N R，ATHITHAN G.A comparative survey of algorithms for frequent subgraph discovery[J]. Current Science， 2011，： 190-198.

[11] CHOUDHURY s，PUROHIT s，LIN P，et al.Percolator： Scalable pattern discovery in dynamic graphs[c]，/Proceedings of the llth ACM International Conference on Web Search and Data Mining. 2018： 759-762.

[12]

INGALALLI V，IENCO D，PONCELET P.Mining frequent subgraphs in multigraphs[J].Information Sciences，2018： 451/452： 50-66.

[13] ALGULIEV R M，ALIGULIYEV R M，GANJALIYEV F s.Extracting a heterogeneous social network of aca-demic researchers on the Web based on information retrieved from multiple sources [J]. American Journal ofOperations Research， 2011： 1（2）：33.

[14] LIMA JR D P，GIACOMINI H c，TAKEMOTO R M，et al Patterns of interactions of a large fishparasitenetwork in a tropical floodplain [J]. Journal of Animal Ecology， 2012， 81（4）： 905-913_

[15] GAO x B，XIAO B，TAO D c，et al.A survey of graph edit distance [J]. Pattern Analysis and Applications，2010， 13（1）：113-129.

[16] HIDOVIC D，PELILLO M.Metrics for attributed graphs based on the maximal similarity common subgraph[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2004， 18（3）： 299-313.

[17]

DEHMER M，EMMERT-STREIB F.Comparing large graphs efficiently by margins of feature vectors[J].Appliedhematics and Computation， 2007， 188（2）： 1699-1710.

如表2所示，本文算法利用候選子圖大小相關(guān)的近似度相對(duì)值計(jì)算公式，在近似支持度設(shè)置為3時(shí)，發(fā)現(xiàn)候選子圖B-A-C為近似頻繁子圖，而對(duì)比算法利用缺失點(diǎn)或邊的絕對(duì)值，則忽略了該候選子圖.

7 結(jié)論

隨著數(shù)據(jù)規(guī)模的增加和數(shù)據(jù)中可能產(chǎn)生的噪音數(shù)據(jù)量的增長，近似頻繁子圖挖掘算法將受到越來越廣泛的關(guān)注，因此，近似頻繁子圖挖掘算法需要根據(jù)候選子圖大小，來判斷可容忍的噪音數(shù)據(jù)量的多少，即可容忍的數(shù)據(jù)缺失數(shù)量是多少.本文設(shè)計(jì)了一種利用候選子圖大小相關(guān)的近似程度計(jì)算公式，從而允許不同大小子圖缺失不同數(shù)量的點(diǎn)或邊的近似頻繁子圖挖掘算法.該算法利用缺失點(diǎn)或邊的數(shù)量與子圖大小的百分比作為近似程度計(jì)算的標(biāo)準(zhǔn)，通過候選子圖生成，近似子圖生成及匹配，近似支持度的計(jì)算幾個(gè)步驟，實(shí)現(xiàn)了候選子圖大小相關(guān)的近似頻繁子圖挖掘算法.人工數(shù)據(jù)和真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)都表明，本算法效率更高，且能發(fā)現(xiàn)利用缺失點(diǎn)或邊數(shù)量絕對(duì)值作為近似程度的算法不能發(fā)現(xiàn)的候選子圖.在未來的工作中，希望能進(jìn)一步提高算法效率，使得算法能在大規(guī)模數(shù)據(jù)上應(yīng)用.

[參考文獻(xiàn)]

[1]YAN x F，HAN J W. gSpan： Graph-based substructure pattern mining [Cl// Proceedings of the 2002 IEEEInternational Conference on Data Mining. 2002：721-724.

[2] ELSEIDY M，ABDELHAMID E，SKIADOPOULOS s，et al.GraMi： Frequent subgraph and pattern mining ina single large graph [J]. Proceedings of the VLDB Endowment， 2014，7：517-528.

[3] CHEN c，YAN x F，ZHU F D，et al.gApprox： Mining frequent approximate patterns from a massive network[C]// 7th IEEE International Conference on Data Mining. 2007：445-450.

[4] FLORES-GARRIDO M，CARRASCO-OCHOA J A，MARTINEZ-TRINIDAD J F.AGraP： An algorithm formining frequent patterns in a single graph using inexact matching [J]. Knowledge and Information Systems，2015，2（44）： 385-406.

[5] KURAMOCHI M，KARYPIS G.Finding frequent patterns in a large sparse graph[J].Data Mining and Knowl-edge Discovery， 2005， 11（3）： 243-271

[6] NIJSSEN s，KOK J N A quickstart in frequent structure mining can make a difference [Cl// Proceedings of thelOth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， 2004： 647-652.

[7] ALONSO A G，PAGOLA J E M，CARRASCO-OCHOA J A，et al.Mining frequent connected subgraphs reducingthe number of candidates [C]// Joint European Conference on Machine Learning and Knowledge Discovery inDatabases. 2008： 365-376.

[8] RANU s，SINGH A K.Graphsig：A scalable approach to mining significant subgraphs in large graph databases[C]// 2009 IEEE 25th International Conference on Data Engineering. 2009： 844-855.

[9] CHENG H，YAN x F，HAN J W. Mining graph patterns [C]// Frequent Pattern Mining， Berlin： Springer， 2014：307-338.

[10] KRISHNA V，SURI N R，ATHITHAN G.A comparative survey of algorithms for frequent subgraph discovery[J]. Current Science， 2011，： 190-198.

[11] CHOUDHURY s，PUROHIT s，LIN P，et al.Percolator： Scalable pattern discovery in dynamic graphs[c]，/Proceedings of the llth ACM International Conference on Web Search and Data Mining. 2018： 759-762.

[12]

INGALALLI V，IENCO D，PONCELET P.Mining frequent subgraphs in multigraphs[J].Information Sciences，2018： 451/452： 50-66.

[13] ALGULIEV R M，ALIGULIYEV R M，GANJALIYEV F s.Extracting a heterogeneous social network of aca-demic researchers on the Web based on information retrieved from multiple sources [J]. American Journal ofOperations Research， 2011： 1（2）：33.

[14] LIMA JR D P，GIACOMINI H c，TAKEMOTO R M，et al Patterns of interactions of a large fishparasitenetwork in a tropical floodplain [J]. Journal of Animal Ecology， 2012， 81（4）： 905-913_

[15] GAO x B，XIAO B，TAO D c，et al.A survey of graph edit distance [J]. Pattern Analysis and Applications，2010， 13（1）：113-129.

[16] HIDOVIC D，PELILLO M.Metrics for attributed graphs based on the maximal similarity common subgraph[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2004， 18（3）： 299-313.

[17]

DEHMER M，EMMERT-STREIB F.Comparing large graphs efficiently by margins of feature vectors[J].Appliedhematics and Computation， 2007， 188（2）： 1699-1710.

[18] HOLDER L B， COOK D J， DJOKO S. Substucture discovery in the SUBDUE system [C]// KDD Workshop，1994： 169-180.

[19]

JIA Y， ZHANG J T， HUAN J. An efficient graph-mining method for complicated and noisy data with real-worldapplications [J] . Knowledge and Information Systems， 2011， 28（2） ： 423-447.

[20] FLORES-GARRIDO M， CARRASCO-OCHOA J A， MARTiNEZ-TRINIDAD J F. Extensions to AGraP algo-rithm for finding a reduced set of inexact graph patterns [J]. International Journal of Pattern Recognition andArtificial Intelligence， 2018， 32（1）： 1860012.

[21] ACOSTA-MENDOZA N， GAGO-ALONSO A： CARRASCO-OCHOA J A， et al. Extension of canonical adja-cency matrices for frequent approximate subgraph mining on multi-graph collections [J]. International Journalof Pattern Recognition and Artificial Intelligence， 2017， 31（8）： 1750025.

[22] ACOSTA-MENDOZA N. MORALES-GONZaLEZ A， GAGO-ALONSO A， et al. Image classification using fre-quent approximate subgraphs [C]// Iberoamerican Congress on Pattern Recognition. 2012： 292-299.

[23]

ACOSTA-MENDOZA N， CARRASCO-OCHOA J A， MARTiNEZ-TRINIDAD J F， et al. Image clustering basedon frequent approximate subgraph mining [C]// Mexican Conference on Pattern Recognition. 2018： 189-198.

收稿日期：2018-12-21

第一作者：竇建凱，男，碩士研究生，研究方向?yàn)轭l繁圖挖掘.E-mail： yirandjk@163.com.

通信作者：胡文心，女，高級(jí)工程師，碩士生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)科學(xué).E-mail：wxhu@cc。ecnu.edu.cn.