鄒曉紅,郭景峰,2,賀釋千,2,陳 晶,劉院英

1(燕山大學 信息科學與工程學院,河北 秦皇島 066004)2(河北省虛擬技術(shù)與系統(tǒng)集成重點實驗室,河北 秦皇島 066004)3(河北經(jīng)貿(mào)大學 信息技術(shù)學院,石家莊 050061)

1 引 言

圖是表現(xiàn)力很強的數(shù)據(jù)結(jié)構(gòu),能夠充分表示實體自身的信息及實體間的聯(lián)系,因而在生物信息學、化學等領(lǐng)域廣泛應(yīng)用.并且隨著對結(jié)構(gòu)化數(shù)據(jù)分析需求的大量增加,通過圖建模進行圖挖掘問題已經(jīng)成為一個非常重要的研究課題.圖分類是圖挖掘的一個重要研究分支[1],而圖向量化是圖分類的基礎(chǔ),通過對圖提取特征向量化后根據(jù)得到的圖向量可以進行圖分類.目前關(guān)于圖分類的研究中能用于提取分類特征的算法有兩類,一類是子圖分布算法,另一類是頻繁子圖挖掘算法.用于圖分類的子圖分布算法的相關(guān)研究最早起源于生物學與社會網(wǎng)絡(luò)等領(lǐng)域,其目的是檢測圖的非平凡特性用于發(fā)現(xiàn)不同圖之間的異同,在生物學研究中,通過檢測兩組蛋白質(zhì)交互網(wǎng)絡(luò)的拓撲結(jié)構(gòu)的不同可以發(fā)現(xiàn)兩者功能上的差異.例如通過把要檢測物質(zhì)的化學結(jié)構(gòu)和已知的致癌癥物質(zhì)抽象成圖比對,就可以初步判斷要檢測物質(zhì)是否致癌.

國外對用于圖分類的子圖分布算法研究已經(jīng)有很多,一般是基于一定的圖模型,將現(xiàn)實世界中的網(wǎng)絡(luò)抽象為圖并建模,在構(gòu)建圖模型的基礎(chǔ)上再進行算法研究.如文獻[2]中首先定義小誘導(dǎo)子圖為Graphlet,簡稱為Graphlet模型,提出使用Graphlet頻度來測量網(wǎng)絡(luò)局部的拓撲結(jié)構(gòu),給出了相對圖頻率距離公式和算法.2008年P(guān)rzulj N與Milenkovic′T對GDD改進,在文獻[3]中提出了GDV,又稱為圖簽名和圖簽名相似度以及圖簽名距離.GDV是一個圖向量,存放子圖分布信息,并根據(jù)圖的不同維度給出了相應(yīng)的權(quán)值,用于調(diào)節(jié)因為網(wǎng)絡(luò)的拓撲結(jié)構(gòu)導(dǎo)致某些維度的數(shù)據(jù)嚴重偏高或嚴重偏低.2015年Ahmed N等人在文獻[4]中提出了PGD算法,拓展Graphlet的定義,根據(jù)改進后的Graphlet模型計算子圖分布,利用補圖對所有子圖進行了組合,利用組合數(shù)學公式減少了部分子圖的計算.2015年Elenberg E R等人在文獻[5]中提出了3-Profiles,描述有3個頂點的圖,可用于計算聚類系數(shù),在社會網(wǎng)絡(luò)里,聚類系數(shù)反映了人們間聯(lián)系的緊密程度.該算法利用馬爾科夫鏈建模并估算3-Profiles分布.國內(nèi)的子圖分布研究相對較少,譚尚旺等人對隨機完全圖中某些子圖的概率分布進行了研究并給出極限定理[6].

隨著圖分類在諸多領(lǐng)域的廣泛應(yīng)用,如何提高分類的準確性變得尤為重要.但是,根據(jù)Graphlet模型及改進的模型計算的子圖分布只考慮到圖的拓撲結(jié)構(gòu)信息,并未考慮圖中頂點和邊標簽信息,用于圖分類時,因為提取的圖分類特征過少而影響圖分類的準確性.對此本文加以改進,首先,借鑒統(tǒng)計學的零模型構(gòu)建了n階標簽零模型,該模型同時考慮圖的拓撲結(jié)構(gòu)信息和圖中頂點和邊標簽信息,增加圖分類的特征,提高圖分類的準確性.其次,針對直接計算子圖分布,需要反復(fù)多次進行圖同構(gòu)測試,導(dǎo)致時間復(fù)雜度較高的問題,在n階標簽零模型基礎(chǔ)上提出兩個算法,一個是用于構(gòu)建圖索引的BGLI算法,另一個是在BGLI算法基礎(chǔ)上提出的計算子圖分布ESGS算法,降低時間復(fù)雜度,提高計算速度.

2 標簽零模型

定義1.標簽圖:設(shè)G=(V,E,Σ,L),其中V(G)和E(G)分別為圖G的頂點集和邊集、Σ為標簽集,L為標簽的映射函數(shù):對于?v∈V(G)記為L(v),對于?(vi,vj)∈E(G)記為L(vi,vj),用于映射頂點和邊的標簽.

定義2.圖同構(gòu):圖同構(gòu)是雙射函數(shù)f使得f:V(G)→V(H),若標簽圖G和標簽圖H同構(gòu),則滿足下列條件:

1)若?v∈V(G),?v′∈V(H)

則v?v′,記為V(G)?V(H).

則(vi,vj)?(vk′,vl′),記為E(G)?E(H).

3)若?v∈V(G),?v′∈V(H)

則L(u)=L(v)

4)若?(vi,vj)∈E(G),?(vk′,vl′)∈E(H)

則L(vi,vj)=L(vk′,vl′)

圖同構(gòu)表明,若標簽圖G和標簽圖H同構(gòu),則V(G)與V(H)一一對應(yīng)且對應(yīng)頂點的標簽相同,E(G)與E(H)一一對應(yīng)且對應(yīng)邊的標簽相同.

定義3.n階零模型:n階零模型是與原圖G具有相同統(tǒng)計量的隨機圖H.設(shè)統(tǒng)計量有原圖G的頂點數(shù)N、邊數(shù)M和n個頂點的聯(lián)合度分布p(d1,d2,…,dn)(n≤N),其中dn為頂點度為n的個數(shù).要求根據(jù)原圖G生成的圖H滿足如下約束:

1)|V(G)|=|V(H)|=N

2)|E(G)|=|E(H)|=M

3)pG(d1,d2,…,dn)=pH(d1,d2,…,dn)(n≤N)

n階零模型是n階零配置模型的簡稱,n階零模型中的n個頂點的聯(lián)合度分布表明的是,具有n個頂點的子圖形成的子圖分布,并且當n>1時,要求這n個頂點所形成的子圖為連通圖,不出現(xiàn)孤立頂點.下面舉例說明各階模型:

0階零模型:與原圖G具有相同頂點數(shù)N、邊數(shù)M和頂點的平均度D的隨機圖,其中平均度D是G中所有頂點的度的平均值D=2M/N.

1.階零模型:與原圖G具有相同頂點數(shù)N、邊數(shù)M、平均度D和度分布為p(d)的隨機圖,其中度分布p(d)是指原圖G中頂點度頻率分布[7].

2.階零模型:與原圖G具有相同的兩個頂點聯(lián)合度分布p(di,dj)和1階零模型中的所有約束條件的隨機圖.其中di是度為i的頂點,dj是度為j的頂點,p(di,dj)為兩個頂點聯(lián)合度分布,是指每條邊兩端連接頂點度的聯(lián)合度分布.

3.階零模型:與原圖G具有相同的三個頂點聯(lián)合度分布p(di,dj,dk)和2階零模型中的所有約束條件的隨機圖.三個頂點聯(lián)合度分布考慮到三個頂點之間的相互連接性,主要有兩種情況,一種是開三角形,另一種是閉三角形,即保證與原圖G具有相同的開三角形和閉三角形分布.

n階零模型如圖1所示,其中左邊的(a)圖為原圖,(b)到(e)圖分別為根據(jù)原圖提取的0到3階模型生成的隨機圖[8].文獻[8]用實驗驗證了根據(jù)原圖G提取統(tǒng)計量達到3階零模型時,生成的新圖H已經(jīng)比較好的還原了原圖.當階數(shù)n等于原圖G的頂點數(shù)N時,n階零模型的約束最強.

圖1 零模型示例Fig.1 Null model example

本文根據(jù)n階零模型提出了n階標簽零模型用于計算子圖分布,同時考慮圖中頂點和邊標簽信息.n階標簽零模型的定義如下:

定義4.n階標簽零模型:n階標簽零模型是與原圖G具有相同統(tǒng)計量的隨機圖.設(shè)統(tǒng)計量有原圖G的頂點數(shù)N、邊數(shù)M和n個頂點的聯(lián)合標簽分布p(L(v1),L(v2)…L(vn)),(n≤N)其中v1,v2…vn∈V(G),L(vn)為vn的標簽,以及這n個頂點間邊上標簽形成的聯(lián)合標簽分布p(L(e1),L(e2)…

L(em))(m≤M),其中e1e2…em∈E(G),L(em)為em的標簽.

要求根據(jù)原圖G生成的圖H滿足如下約束:

1)|V(G)|=|V(H)|=N

2)|E(G)|=|E(H)|=M

3)pG(L(v1),…,L(vn))=pH(L(v1),…,L(vn))

4)pG(L(e1),…,L(em))=pH(L(e1),…,L(em))

其中(n≤N),(m≤M)

下面舉例說明各階模型,如圖2所示,圖中所示為根據(jù)標簽零模型對標簽圖計算所形成的聯(lián)合標簽分布,即n階標簽零模型對應(yīng)的子圖分布.為方便舉例,圖中邊標簽已省略.

圖2 標簽零模型子圖分布示例Fig.2 Subgraph distribution of label null model example

1.階標簽零模型:與原圖G具有相同頂點數(shù)N、邊數(shù)M、頂點標簽分布p(L(vi))的隨機圖.即要求與原圖G具有相同的頂點數(shù)N、邊數(shù)M、頂點標簽數(shù)、頂點標簽種類數(shù)、每種頂點標簽中的標簽數(shù)、邊標簽數(shù)、邊標簽種類數(shù)、每種邊標簽中的標簽數(shù).

2.階標簽零模型:與原圖G具有相同的兩個頂點聯(lián)合標簽分布p(L(vi),L(vj))、這兩個頂點間的邊標簽分布p(L(ei′))和1階標簽零模型中的所有約束條件的隨機圖.其中頂點vi的標簽為L(vi),頂點vj的標簽為L(vi),p(L(vi),L(vj))為兩個頂點的聯(lián)合標簽分布,是指每條邊兩端連接頂點的聯(lián)合標簽分布,p(L(ei′)是這兩個頂點間邊的標簽分布.

3.階標簽零模型:與原圖G具有相同的三個頂點聯(lián)合標簽分布p(L(vi),L(vj),L(vk)),這三個頂點間的三條邊聯(lián)合標簽分布p(L(ei′),L(ej′),L(ek′))和2階標簽零模型中的所有約束條件的隨機圖.

根據(jù)n階標簽零模型提取圖G中n個頂點的子圖,該子圖包括了n個頂點及其互相連接的邊,其中包括頂點和邊的標簽,即根據(jù)頂點提取的誘導(dǎo)子圖.因為各階子圖的種類和每種子圖的個數(shù)由n階標簽零模型唯一確定,所以子圖分布為同一分布是圖同構(gòu)的必要條件.下面給出定理和證明.

定理1.若圖G與圖H同構(gòu),且要求圖G與圖H的頂點集、邊集和標簽集都為有限集或可列集,則根據(jù)n階標簽零模型計算的子圖分布必為同一分布,即兩圖的子圖分布為同一分布是兩圖同構(gòu)的必要條件.

證明:當n階標簽零模型的階數(shù)等于1時.因為圖G與圖H同構(gòu),所以圖G與圖H擁有相同標簽的頂點一一對應(yīng),并且標簽的種類數(shù)相同,每種子圖擁有相同標簽的頂點的個數(shù)也相同.因此,當階數(shù)等于1時,子圖分布退化成標簽分布,此時定理顯然成立.

當n階標簽零模型的階數(shù)n等于大于1時,用反證法證明,假設(shè)圖G與圖H同構(gòu),對應(yīng)的子圖分布分別為FG和FH,且為不同分布.

(1)

(2)

(3)

……,……

(4)

因為MG=MH所以

(5)

(6)

因此可知在圖G與圖H中分別選取n個頂點的分布分別一一對應(yīng),這些分布聯(lián)合后分別為FG和FH,圖G與圖H的分布FG和FH是同一分布,與假設(shè)矛盾.所以兩圖的子圖分布為同一分布是兩圖同構(gòu)的必要條件,該必要條件證明了n階標簽零模型用于圖分類的有效性.

問題1.子圖分布估計問題:設(shè)圖G有N個頂點,M條邊,L個標簽,SGi是G中的子圖.若SGi在圖G中有Ci個與其同構(gòu)的子圖,記其頻度為Ci,在G中根據(jù)標簽零模型選取具有n個頂點的子圖SGi,將子圖集合{SGi}作為基本事件集,要求據(jù)此估計子圖分布.

為描述子圖分布需要引入隨機變量X,設(shè)X為一隨機變量

F(x)=P{X=φ(SGi)}=pi

(7)

其中{xi=φ(SGi)|(i=1,2…)},φ(SGi)∈[1,+).pi滿足條件:為隨機變量X的分布函數(shù),簡稱分布.

其中φ是一個標識函數(shù),用于給每一個SGi一個唯一標識,用于圖向量化,子圖的編號從1開始到+.根據(jù)標簽零模型計算子圖分布,然后把提取的子圖及其頻度以向量的形式作為圖分類特征進行圖分類.因為大多數(shù)分類算法不能直接把子圖作為特征計算,所以需要給每一個子圖一個唯一標識進行向量化.

為估算子圖分布可以通過采樣估算子圖總體分布,樣本分布近似替代總體分布會有一定的偏差,為此需要知道當樣本量一定時,樣本分布提取了總體分布多少信息,即量化樣本信息提取比.

問題2.量化樣本信息提取比問題:假設(shè)窮舉圖G中所有子圖,可得到G圖中所有子圖的總體分布,簡稱總體分布,記為p(x).在圖G中采樣,當子圖樣本,簡稱為樣本,量為k時,可得到此k個子圖的樣本分布,簡稱樣本分布,記為q(x).要求據(jù)此定量分析q(x)在p(x)中提取了多少信息.

對于給定的概率分布可用信息熵進行量化,因為子圖分布是概率分布,所以使用信息熵量化子圖分布信息.

定義5.信息提取比例:

r=Hq/Hp

(8)

信息提取比例是指樣本信息占總體信息的比例,簡稱信息提取比,其中Hp為總體分布的熵值,簡稱總體熵值,Hq為樣本分布熵值,簡稱樣本熵值.

樣本熵值可以通過樣本直接計算,而對于總體熵值,當總體分布的信息熵收斂的情況下,可以通過窮舉計算出總體熵值,但時間復(fù)雜度是NP,所以可以根據(jù)最大熵原理推斷出總體最大熵分布,推斷出總體的極限熵值,近似替代總體熵值.考慮到實際需求,在樣本中最容易提取也最具有一般意義的統(tǒng)計量是均值和方差,所以假設(shè)均值和方差都存在的情況下,根據(jù)最大熵原理和相對熵推斷出總體最大熵分布.子圖分布本身是離散型分布,最大熵原理對離散或連續(xù)型分布都適用,為方便計算,令每個子圖映射為一個數(shù),且要求這些映射數(shù)相互間隔大于1.經(jīng)映射后,xi表示一個子圖.約束條件,xi在[1,+)區(qū)間內(nèi),總體的參數(shù)均值μ、總體的參數(shù)方差σ2都存在時,總體最大熵分布p(x)就是正態(tài)分布N(μ,σ2).

設(shè):總體最大熵分布的概率密度函數(shù)為p(x),簡寫為p、熵函數(shù)為H(p)、總體的參數(shù)均值、總體的參數(shù)方差σ2、總體的極限熵值Hp.樣本的分布概率密度函數(shù)為q(x),簡寫為q、熵函數(shù)為H(q)、樣本統(tǒng)計量均值x、樣本統(tǒng)計量方差s2、樣本的信息熵Hq.

由相對熵公式可知

(9)

(10)

(11)

當均值μ和方差σ2都存在時,取p(x)=N(μ,σ2)則

(12)

令底數(shù)為e得

(13)

(14)

由于q(x)的均值方差有如下關(guān)系

(15)

所以

(16)

當p(x)=N(μ,σ2)時,上式取等號.根據(jù)最大熵原理求出總體最大熵分布后,就可以根據(jù)上式計算其極限熵值.

3 子圖分布算法

3.1 算法主要思想

子圖分布最基本的兩個步驟是:第一步,對圖進行采樣.其中,樣本是圖中的子圖.第二步,對采集的樣本進行圖同構(gòu)檢測,并對其計數(shù).

計算子圖分布過程中,不進行任何優(yōu)化直接計算,會不可避免反復(fù)多次進行圖同構(gòu)測試,導(dǎo)致相對較高時間復(fù)雜度.設(shè)k為采樣的子圖數(shù),則k個具有n個頂點的子圖需計算k2n!次.所以計算子圖分布的時間復(fù)雜度是O(k2n!).因為直接搜索子圖需多次進行掃描遍歷,會耗費很多時間,尤其是在分布式的情況下,多機并發(fā)搜索子圖會極大增加網(wǎng)絡(luò)開銷減慢算法效率.而建立一個合適的索引實現(xiàn)對子圖的快速查找,可以避免多機并發(fā)搜索子圖,并通過每個索引找到關(guān)于子圖的信息,減少搜索時間.

為此,本文根據(jù)n階標簽零模型提出兩個算法,一個是用于構(gòu)建GLI索引的BGLI(Build Graph Location Index)算法,另一個是在BGLI算法基礎(chǔ)上提出的計算子圖分布ESGS (Estimate SubGraph on Spark)算法.

3.2 基于圖不變量的圖索引

圖不變量是圖自身的屬性.如果兩個圖同構(gòu),那么它們不但擁有相同的拓撲結(jié)構(gòu)而且也具有相同的圖不變量,反之,該性質(zhì)不成立,即不變量是判定圖同構(gòu)的必要非充分條件.例如一個圖的頂點數(shù)和邊數(shù)就是兩個圖不變量,圖中最大頂點度也是圖不變量.對于同構(gòu)的圖其圖不變量都是相同的,而圖不變量相同的圖不一定同構(gòu),所以,圖不變量不能直接用在同構(gòu)子圖的匹配或計數(shù)上.然而,圖不變量可以用來對非同構(gòu)圖進行過濾,縮減搜索空間,間接提高算法效率.

本文提出兩個函數(shù),圖似然函數(shù)和頂點度映射函數(shù).這兩個函數(shù)分別利用標簽信息和頂點度建立圖不變量.

定義6.圖似然函數(shù)(Graph Likelihood function):

(17)

該函數(shù)是利用子圖中頂點和邊的標簽信息建立的圖不變量.其中G為標簽圖,SG為G的子圖,pi是G中頂點標簽i的頻率,ci是SG中標簽i的出現(xiàn)次數(shù),CN為SG中標簽總數(shù).其中標簽分為頂點標簽和邊標簽兩種情況.圖似然函數(shù),簡稱GL函數(shù).

定理2.若SG和SG′同構(gòu),則

gl(G,SG)=gl(G,SG′)

(18)

定理可以分別應(yīng)用于頂點標簽和邊標簽,得到下列等式:

glv(G,SG)=glv(G,SG′)

(19)

gle(G,SG)=gle(G,SG′)

(20)

證明:設(shè)標簽圖G有N個頂點,M條邊,SG和SG′是G的子圖.epi是G中邊標簽i的頻率,eci和ec′i分別是SG和SG′中邊標簽i的出現(xiàn)次數(shù),CLE(SG)為SG邊標簽的種類集合,|CLE(SG)|=em,CLE(SG′)為SG′邊標簽的種類集合,|CLE(SG′)|=em′,若SG和SG′同構(gòu),則當標簽為邊標簽時:

gle(G,SG)=gle(G,SG′)

(21)

(22)

若SG和SG′同構(gòu),則SG和SG′共同擁有圖G的子邊標簽集合{L1,L2,…,Li}=CLE(SG)=CLE(SG′)并且邊標簽集合中的標簽滿足下列等式

ec1=ec′1,ec2=ec′2,…,eci=ec′i

(23)

兩邊分別乘以各自邊標簽Li的頻率的對數(shù)log(epi)得

ec1log(ep1)=ec′1log(ep1)

(24)

ec2log(ep2)=ec′2log (ep2)

(25)

…

ecilog (epi)=ec′ilog (epi)

(26)

因為|CLE(SG)|=|CLE(SG′)|所以

gle(G,SG)=gle(G,SG′)

(27)

同理可得

glv(G,SG)=glv(G,SG′)

(28)

因此定理成立.

定義7.圖頂點度映射函數(shù)(graph vertex Degree Map function):

(29)

該函數(shù)是利用子圖中頂點的度信息建立的圖不變量.其中G為標簽圖,SG為G的子圖,vi是G中頂點,d(vi)是SG中頂點vi的度,f(d(vi))為SG中頂點vi的函數(shù).其中f映射函數(shù)是將具有相同度的頂點映射為同一正整數(shù),比如素數(shù).圖頂點度映射函數(shù),簡稱DM函數(shù).

定理3.若SG和SG′同構(gòu),則

dm(SG)=dm(SG′)

(30)

證明:設(shè)標簽圖G有N個頂點,M條邊,其中|V(G)|=N,|E(G)|=M.SG和SG′是G的子圖.d(vi)是SG中頂點vi的度,d(v′i)是SG′中頂點v′i的度,若SG和SG′同構(gòu),則下式相等

dm(SG)=dm(SG′)

(31)

若SG和SG′同構(gòu),則SG中頂點vi,SG′中頂點v′i分別一一對應(yīng),且頂點的度相等,有等式(v1)=d(v′1),d(v2)=d(v′2),d(vi)=d(v′i),令f映射函數(shù)是將具有相同度的頂點映射為同一正整數(shù),比如素數(shù).

f(d(v1))=f(d(v′1))

(32)

f(d(v2))=f(d(v′2))

(33)

…

f(d(vi))=f(d(v′i))

(34)

則

(35)

dm(SG)=dm(SG′)

(36)

但兩圖圖同構(gòu)也有可能度分布不相同,所以DM函數(shù)值是判斷圖同構(gòu)的非充分條件.由上述討論可知DM函數(shù)值是判斷圖同構(gòu)的必要非充分條件,所以是圖不變量.

本文提出了基于GL函數(shù)值和DM函數(shù)值的GLI索引,該索引可以用于分布式條件下.由定理2和定理3可知,GL函數(shù)值和DM函數(shù)值相同是圖同構(gòu)的必要條件,所以用GL函數(shù)值和DM函數(shù)值作為子圖的索引值,對子圖進行分組.若有兩個子圖的GL函數(shù)值和DM函數(shù)值都分別相等,則把這兩個子圖分到同一組中.因為應(yīng)用GL函數(shù)值和DM函數(shù)建立索引的過程類似,因此以GL函數(shù)為例進行介紹.GLI索引如圖3所示.在圖3中(a)圖為圖G,(b)圖為根據(jù)其子圖GL函數(shù)值構(gòu)建的索引.

3.3 圖索引算法BGLI

算法1.BGLI

輸入:圖G,SG_list子圖列表

輸出:GLI索引

1 初始化GLI索引,GLI為空字典

2 ForSGiin SG_list:

3 Key=根據(jù)GL函數(shù)和DM函數(shù)計算SGi的索引值

4 If Key not in GLI:

5 Then初始化SG_Vec子圖向量,放入SG

6 Else SG_Vec =GLI[Key] 找鍵為Key的子圖向量

7 IfSGiin SG_Vec:

8 ThenSGi對應(yīng)的同構(gòu)圖計數(shù)加1

9 Else 在SG_Vec中初始化SGi

10 Return GLI索引

圖3 圖索引示例Fig.3 Index of graph example

BGLI算法的輸入為圖G,SG_list子圖列表,其中子圖列表是在圖G中通過采樣獲得的樣本.GLI索引是3層的森林結(jié)構(gòu).GLI索引的第一層和第二層形成了鍵值對(key value)字典結(jié)構(gòu),其中,鍵是子圖SGi的GL函數(shù)值和DM函數(shù)值,在BGLI算法第3行計算;值是具有相同GL函數(shù)值和DM函數(shù)值的子圖向量SG_Vec,在BGLI算法第4～10行計算.GLI索引的第二層和第三層也是鍵值對字典結(jié)構(gòu),其中,鍵是第二層中子圖向量SG_Vec中的子圖;值是該子圖的計數(shù)和該子圖鄰接字典,即由哈希列表實現(xiàn)的鄰接列表.

3.4 子圖分布算法ESGS

計算子圖分布問題有兩個技術(shù)難點.其一是,當數(shù)據(jù)規(guī)模過大時,會導(dǎo)致較高時間復(fù)雜度,針對小規(guī)模數(shù)據(jù)的算法將難以處理海量數(shù)據(jù).其二是,計算子圖分布過程中會有大量的子圖數(shù)據(jù)存放在內(nèi)存當中,這些中間運算結(jié)果數(shù)據(jù)十分龐大.而基于分布式框架Spark的分布式算法能利用集群資源快速處理海量數(shù)據(jù).

ESGS算法是基于Spark的分布式算法,因此ESGS算法的計算流程也必須符合Spark的MapReduce計算模型流程,所以ESGS算法分為map過程和reduce過程,下面分別對ESGS算法的map過程和reduce過程詳細說明.

下面介紹ESGS算法的map過程,該過程主要負責將要計算任務(wù)分發(fā)到集群中每一個負責計算的worker節(jié)點中,包括對給定k個n階的子圖采樣,建立延遲采樣列表,根據(jù)BGLI算法對子圖列表中的子圖分類計數(shù)并構(gòu)建GLI索引.

算法2.ESGS-Fun-Map

輸入:階數(shù)n,圖G,采樣個數(shù)max_k

輸出:被索引的子圖數(shù)據(jù)GLI_data

1 初始化當前采樣數(shù)k,初始化SG_list延遲采樣子圖列表

2 While k

3 初始化當前采樣子圖SGi數(shù)的頂點集合vs={}

4 根據(jù)隨機游走選取頂點并放入vs中

5 根據(jù)頂點集合vs中的頂點提取子圖SGi

6 將SGi放入SG_list延遲采樣子圖列表

7 k++

8 調(diào)用算法 BGLI(G,SG_list)

9 Return GLI_data

算法ESGS-Fun-Map中2到7行是圖采樣過程,該圖采樣過程是基于隨機游走的.圖采樣過程有兩個條件,其一,若頂點集合vs為空且vs中的頂點數(shù)小于n,則隨機選取第一個頂點v,然后將頂點v放入頂點集合vs.其二,若頂點集合vs非空且vs中的頂點數(shù)小于n,則在鄰居頂點集合nvs中隨機選取一個頂點,然后將其放入頂點集合vs.根據(jù)上述頂點選取的方法保證了采樣的子圖SGi是連通圖.該過程并不會真正在map過程全部發(fā)生,其第6行是構(gòu)建延遲采樣子圖列表,該延遲采樣子圖列表會記錄采樣的條件和隨后的行為,直至reduce函數(shù)觸發(fā)Spark提交作業(yè)完成.

下面介紹ESGS算法的reduce過程,該過程主要負責將集群中每一個負責計算的worker節(jié)點中數(shù)據(jù)回收與合并.

算法3.ESGS-Fun-Reduce

輸入:被索引的子圖數(shù)據(jù)GLI_src和 GLI_dec

輸出:合并后的被索引的子圖數(shù)據(jù)GLI_dec

1 For Key in GLI_src:

2 If Key not in GLI_dec:

3 Then在GLI_dec加入新數(shù)據(jù),其鍵為Key

4 value為GLI_src 對應(yīng)的SG_Vec

5 Else 合并GLI_src與GLI_dec具有相同Key的

6 SG_Vec,由相近頻率子圖開始圖同構(gòu)測試,

7 直到對全部子圖測試完畢.

8 If未找到同構(gòu)子圖 Then 插入 GLI_dec

其中偽代碼第5到7行是優(yōu)化的關(guān)鍵,該過程是數(shù)據(jù)回收合并階段,集群中每一個負責計算的worker節(jié)點,都采集了相同數(shù)量的子圖樣本并依照索引對子圖進行了分組,同一組的子圖都具有相同的GL函數(shù)值和DM函數(shù)值,在同一組的子圖已經(jīng)無法按照上述函數(shù)值進行區(qū)分,必須進行圖同構(gòu)測試.為提高計算速度,提出了依子圖頻度搜索及合并子圖的策略.該策略過程先依頻率對子圖排序,然后測試頻率相近的子圖,再測試頻率差異大的子圖,直到測試完畢.

該策略假設(shè)對獨立同分布的兩組樣本,當采樣足夠大時,同構(gòu)的子圖在這兩組樣本中的頻率應(yīng)相近或相同.設(shè)有兩個負責計算的worker節(jié)點,都采集k個樣本,返回兩組子圖記為SG_Vec1與SG_Vec2,令每一個子圖的頻率為隨機變量,則由大數(shù)定律可知隨樣本量增大頻率會逼近其概率,則在SG_Vec1中任意取一個子圖sg1,其頻率為sg1f,若在SG_Vec2中有與sg1同構(gòu)的子圖sg2,則當樣本量足夠大時,sg2的頻率sg2f應(yīng)與sg1f相近或相同.根據(jù)上述討論可知,在上述情況下合并子圖時,應(yīng)先測試頻率相近的子圖,進而避免無效的圖同構(gòu)測試.

3.5 算法性能分析

BGLI與ESGS算法需要計算分以下幾個部分(1)計算圖G的各個標簽頻率,設(shè)N=|V(G)|,其中N為圖G的頂點個數(shù),則需要計算N次.(2)根據(jù)GL函數(shù)和DM函數(shù)對k個子圖計算檢索,需要2k次.(3)設(shè)k為子圖個數(shù),c為索引類別個數(shù),λ為同一索引檢索到的子圖個數(shù),則k=cλ,則k個子圖需要計算kλ2n!次.則計算量總計為N+2kn+kλ2n!,其中N+2kn遠遠小于kλ2n!,所以ESGS算法的時間復(fù)雜度是O(kλ2n!).其中根據(jù)實驗觀察發(fā)現(xiàn),當無標度網(wǎng)絡(luò)中的頂點標簽分布服從參數(shù)為1.1的泊松分布時,λ一般小于5.

4 實驗分析

實驗在一臺基本配置為:CPU AMD Athlon(tm)II X4 605e Processor、內(nèi)存4G、64G硬盤的PC上進行、操作系統(tǒng)Fedora 23、Python 3.4.3 、Spark-2.0.2-bin-hadoop2.7、Java 1.8.0_60.為了驗證(1)n階標簽零模型用于圖分類的有效性.(2)根據(jù)n階標簽零模型計算信息提取比可以間接確定合適的樣本數(shù)量減少冗余計算.(3)基于n階標簽零模型的ESGS算法提取的子圖向量化后作為分類特征進行圖分類的正確率.分別進行三組實驗.

4.1 實驗1.卡方檢驗實驗

卡方檢驗實驗要驗證的是:

1)根據(jù)標簽零模型計算的子圖分布可以判斷圖不同構(gòu).

2)對比標簽零模型與Graphlet模型在判斷圖不同構(gòu)方面的差異顯著性水平.

用于卡方檢驗的數(shù)據(jù),是由文獻[9]的模擬數(shù)據(jù)生成器生成的兩個圖,這兩個圖都是無標度網(wǎng)絡(luò),其中模擬數(shù)據(jù)生成器的參數(shù)設(shè)置為:頂點數(shù)n為1000、隨機添加新邊數(shù)m為2、添加新邊后形成的三角形概率p分別為0.1和0.5.模擬數(shù)據(jù)生成器生成的圖并無標簽,所以使用泊松分布生成標簽,其中泊松分布的參數(shù)為1.1.

圖4 卡方檢驗對比Fig.4 Comparison of chi2 testing

卡方檢驗對比的實驗結(jié)果如圖4,圖中Graphlet曲線是根據(jù)Graphlet模型計算的子圖分布進行的卡方檢驗值的曲線,ESGS曲線是根據(jù)標簽零模型計算的子圖分布進行的卡方檢驗值的曲線.橫坐標為樣本量,縱坐標為顯著水平,顯著水平代表的是兩分布為同一分布的概率,接近1表示相同,接近0表示不相同.待檢測的數(shù)據(jù)是兩個不同構(gòu)的圖,通過各自的子圖分布檢驗兩個圖不同構(gòu).

由圖4可知,隨著樣本量增加,Graphlet和ESGS顯著水平波動性下降,其中ESGS顯著水平下降更快,當樣本量增加到50至100時,ESGS顯著水平已經(jīng)迅速下降到0.05左右,并且較為穩(wěn)定,而Graphlet還在劇烈波動.當超過100后ESGS基本穩(wěn)定在0左右.

卡方檢驗實驗結(jié)果分析:造成顯著水平劇烈波動的原因分兩方面,一方面,當樣本量小于50時,根據(jù)隨機采樣得到的子圖數(shù)量和種類差異都比較大,導(dǎo)致子圖分布收斂性不好,以至于Graphlet和ESGS顯著水平劇烈波動.另一方面,當樣本量大于50時,因為Graphlet模型只考慮圖的拓撲信息不考慮頂點和邊的標簽信息,提取出用于區(qū)分圖的特征較少,導(dǎo)致顯著水平劇烈波動.而ESGS不僅考慮圖的拓撲信息還考慮頂點和邊的標簽信息,提取出用于區(qū)分圖的特征相對較多,相對較多特征使得子圖分布檢驗更容易判斷出兩圖是不同構(gòu)的,結(jié)果表現(xiàn)在ESGS顯著水平波動較小.

在當前的試驗條件下,上述實驗結(jié)果表明:(1)根據(jù)標簽零模型計算的子圖分布能夠判斷圖不同構(gòu).(2)ESGS的顯著水平下降更快且相對穩(wěn)定,說明用標簽零模型比Graphlet模型在判斷圖不同構(gòu)方面的差異顯著性水平上更好.

4.2 實驗2.信息提取比實驗

信息提取比實驗要驗證的是:(1)子圖總體分布信息熵的上限是存在的,其上限是正態(tài)分布的熵值.(2)計算信息提取比可間接確定樣本量,避免樣本量過多造成冗余計算.

圖5 熵曲線和信息提取比Fig.5 Entropy curve and information extraction ratio

用于信息提取比實驗的數(shù)據(jù)和上文的卡方檢驗實驗數(shù)據(jù)相同.信息提取比實驗結(jié)果如圖5,在圖5中的(a)到(d)圖為從數(shù)據(jù)中分別對3到6階各自采樣的子圖樣本的熵曲線圖.其中,橫坐標為采樣數(shù)量,單位為子圖個數(shù),縱坐標為熵值,底數(shù)為e,單位為奈特nat;圖中Hpe、Hpn、Hq分別為指數(shù)分布熵曲線、正態(tài)分布熵曲線、樣本分布熵曲線,其中指數(shù)分布、正態(tài)分布的參數(shù)都是通過樣本統(tǒng)計量均值、方差和參數(shù)上下界估算的.圖5中的(e)到(h)圖為從數(shù)據(jù)中分別對3到6階各自采樣的子圖樣本的信息提取比曲線圖,其中橫坐標為采樣數(shù)量,縱坐標為信息提取比r,Hper為以指數(shù)分布為上限的信息提取比熵曲線,Hpnr為以正態(tài)分布為上限的信息提取比熵曲線.

實驗結(jié)果分析:

1)可以觀察到給定均值和方差的情況下,隨階數(shù)增大,樣本熵曲線與正態(tài)分布熵曲線接近速度最快,而且相對于樣本熵與指數(shù)分布的熵偏離更小,正態(tài)分布的熵值是樣本分布的熵值上界.隨階數(shù)增高,信息提取比熵曲線逐漸穩(wěn)定,以正態(tài)分布為上限的信息提取比高于以指數(shù)分布為上限的信息提取比,這進一步證明了正態(tài)分布的熵值比指數(shù)分布的熵值更接近樣本分布的熵值,所以正態(tài)分布的熵值可以近似替代總體分布的極限熵.樣本分布的熵值與正態(tài)分布的熵值接近速度最快,但依舊有發(fā)散趨勢,說明正態(tài)分布并非總體分布.

2)結(jié)合信息提取比實驗和上文的卡方檢驗實驗結(jié)果分析,可發(fā)現(xiàn)當樣本量為50以下時信息熵增長最快,此時顯著水平劇烈波動,當樣本量為50到200時,信息熵增長趨于平緩,信息提取比處于90%到98%之間,此時顯著水平也趨于0.顯著水平接近0表明兩圖不同構(gòu).

在當前的試驗條件下,通過本實驗可以得出結(jié)論:

1)從熵極限角度看,正態(tài)分布的熵是總體分布的上限,但總體分布并非正態(tài)分布.因此可以使用正態(tài)分布的熵近似替代總體分布的極限熵計算信息提取比.

2)通過對信息提取比計算可以間接確定樣本的數(shù)量,避免樣本量過多造成冗余計算.

4.3 實驗3.分類實驗

本實驗驗證在不同數(shù)據(jù)集下,基于n階標簽零模型的ESGS算法提取的子圖向量化后作為分類特征進行圖分類的正確率.

本實驗使用的數(shù)據(jù)集是由美國國家癌癥研究院(NCI)公開的兩組基準數(shù)據(jù),包括NCI1數(shù)據(jù)集和NCI109數(shù)據(jù)集,NCI提供的兩組基準數(shù)據(jù)來自于抗腫瘤活性預(yù)測任務(wù).這兩組基準數(shù)據(jù)分別代表兩組可能致癌物的數(shù)據(jù)集,致肺癌物質(zhì)和致卵巢癌物質(zhì).每一種物質(zhì)表示為一個圖,若癌癥檢測為陽性則為1,否則為0.如圖6和圖7所示,圖中橫坐標為分類使用的方法,縱坐標為正確率.

圖分類的實驗結(jié)果如圖6和圖7,在圖6和圖7中Graphlet代表的是根據(jù)Graphlet模型提取特征后應(yīng)用于各分類算法的實驗結(jié)果.圖中PGD代表的是根據(jù)PGD算法提取特征后,應(yīng)用于各分類算法的實驗結(jié)果.圖中ESGS代表的是ESGS算法根據(jù)標簽零模型提取特征后,應(yīng)用于各分類算法的實驗結(jié)果.圖中ESGS_gl代表的是ESGS算法近似計算版,其中提取特征為圖似然函數(shù)值分布,應(yīng)用于各分類算法的實驗結(jié)果.圖6和圖7中分類方法分別為,基于伯努利模型的貝葉斯分類算法bernoulliNB,基于多項式模型的貝葉斯分類算法MultinomialNB,支持向量機分類算法clf_svm.其中clf_svm_ch2代表的是數(shù)據(jù)經(jīng)過卡方校驗的方法進行特征選取后,進行支持向量機分類算法計算.

實驗結(jié)果分析:由圖6和圖7可知,Graphlet模型的正確率最低,隨子圖頂點個數(shù)增加,正確率有所提升.PGD算法的正確率有所提高,而應(yīng)用標簽零模型計算的ESGS算法正確率最高.即使是當ESGS算法僅計算了圖似然函數(shù)值分布,對應(yīng)的分類正確率也比PGD算法的要好.

圖6 NCI1數(shù)據(jù)分類對比Fig.6 NCI1 data classification and comparison

其中支持向量機的正確率提高最為顯著,這是由于支持向量機在處理線性不可分數(shù)據(jù)的方法決定的.支持向量機會通過核函數(shù)將輸入的低維空間數(shù)據(jù)映射到高維特征空間中,然后在其中構(gòu)造出最優(yōu)分離超平面,把低維空間中不好分的非線性數(shù)據(jù)分開.顯然當對同一組數(shù)組,提取的分類特征越多,就越容易形成高維空間,從實驗結(jié)果看,在這樣的高維空間更容易對數(shù)據(jù)分類.

圖7 NCI109數(shù)據(jù)分類對比Fig.7 NCI109 data classification and comparison

Graphlet模型提取的分類特征最少,所以正確率最低.PGD算法的正確率有所提高,這是因為PGD算法提取的分類特征包含了Graphlet模型中所不包含的非連通子圖.ESGS_gl代表了當ESGS算法僅計算圖似然函數(shù)值分布時,忽略了部分結(jié)構(gòu)信息,導(dǎo)致分類特征減少,正確率稍低.ESGS算法提取的分類特征雖然是連通子圖,但包含了子圖中頂點的標簽信息,其分類特征最多,所以正確率最高.

4.4 實驗總結(jié)

首先,用實驗驗證了n階標簽零模型用于圖分類的有效性.其次,通過實驗的結(jié)果驗證了子圖總體分布信息極限熵值的上限是正態(tài)分布的熵值,計算信息提取比可以間接確定樣本的數(shù)量,避免樣本量過多造成冗余計算.最后,在NCI1數(shù)據(jù)集和NCI109數(shù)據(jù)集上的實驗驗證了,基于n階標簽零模型的ESGS算法提取的子圖向量化后作為分類特征可以提高圖分類的準確性.

5 總結(jié)和展望

為提高子圖分布算法用于圖分類的準確性,本文構(gòu)建了n階標簽零模型,該模型同時考慮圖的拓撲結(jié)構(gòu)信息和圖的標簽信息,增加了圖分類的特征.證明和驗證了n階標簽零模型用于圖分類的有效性.借鑒信息熵,對子圖分布進行了量化分析.針對計算子圖分布時需要反復(fù)多次進行圖同構(gòu)測試的問題,本文提出了索引算法BGLI和子圖分布算法ESGS并在spark上實現(xiàn),降低了時間復(fù)雜度.通過實驗驗證了,基于n階標簽零模型的ESGS算法提取的子圖作為分類特征可以提高圖分類的準確性.

本文在計算子圖分布時,計算的是全部子圖的分布,覆蓋面雖然全面,但計算量大.因為在圖分類時,不同類別的圖,可能具有共同的子圖,而這部分子圖作為共有特征,分類意義不大.所以下一步的工作是,整合子圖分布到圖分類算法中,進一步提高圖分類的準確性,減少計算量.

：

[1] Lam W W M,Chan K C C.A graph mining algorithm for classifying chemical compounds [C].IEEE International Conference on Bioinformatics and Biomedicine,2008:321-324.

[2] Przulj N,Corneil D I.Modeling interactome scale-free or geometric [J].Bioinformatics,2004,20(18):3508-3515.

[4] Ahmed N K,Neville J,Rossi R A,et al.Efficient graphlet counting for large networks [C].IEEE International Conference on Data Mining,2015:1-10.

[5] Elenberg E R,Shanmugam K,Borokhovich M,et al.Beyond triangles:a distributed framework for estimating 3-profiles of large graphs [C].Proceedings of the 21thACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2015:229-238.

[6] Tan Shan-wang,Huang Guo-xun.The limit theorem of probability distribution for some subgraphs in random complete graphs [J].Journal of Guangxi University Natural Science Edition,1991,16(3):12-18.

[7] Newman M,Guo Shi-ze,Chen Zhe.Networks:an introduction [M].Beijing:Oxford University Press,Inc,2014.

[8] Mahadevan P,Krioukov D,Fall K,et al.Systematic topology analysis and generation using degree correlations [C].ACM Special Interest Group on Data Communication Computer Communication Review,2006,36(4):135-146.

[9] Holme P,Kim B J.Growing scale-free networks with tunable clustering [J].Physical Review E,2002,65(2):026107.

附中文參考文獻：

[6] 譚尚旺,黃國勛.隨機完全圖中某些子圖的概率分布極限定理 [J].廣西大學學報自然科學版,1991,16(3):12-18.

[7] 馬克·紐曼,郭世澤,陳 哲.網(wǎng)絡(luò)科學引論 [M].北京：電子工業(yè)出版社,2014.