孟祥福,溫 晶,李子函,紀(jì)鴻樟

(遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院,遼寧 葫蘆島 125105)

1 引 言

在社交網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等大型復(fù)雜關(guān)系網(wǎng)絡(luò)中,一些下游任務(wù)(例如鏈路預(yù)測(cè)、節(jié)點(diǎn)分類、社區(qū)檢測(cè)等)都是基于相似節(jié)點(diǎn)展開的,因此高效準(zhǔn)確的為目標(biāo)節(jié)點(diǎn)檢索top-k相似節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)挖掘中起著至關(guān)重要作用.針對(duì)這一問題,現(xiàn)有研究工作提出了兩種指標(biāo)進(jìn)行相似性搜索:基于局部信息和基于全局信息[1].局部信息主要指的是目標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn),即如果兩個(gè)節(jié)點(diǎn)擁有的公共鄰居數(shù)量越多,兩個(gè)節(jié)點(diǎn)間的相似性越強(qiáng),在結(jié)構(gòu)上越等價(jià).經(jīng)典的衡量指標(biāo)包括Jaccard系數(shù)[2],余弦相似度[3]等.全局信息主要指的是目標(biāo)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu),即這個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中占據(jù)的地位,扮演的角色.拓?fù)浣Y(jié)構(gòu)相似的兩個(gè)節(jié)點(diǎn)在結(jié)構(gòu)上是相似的.然而,局部信息主要以局部的方式為目標(biāo)節(jié)點(diǎn)搜索相似節(jié)點(diǎn),top-k相似節(jié)點(diǎn)的選取范圍僅限于目標(biāo)節(jié)點(diǎn)指定跳數(shù)的鄰居,導(dǎo)致復(fù)雜網(wǎng)絡(luò)中兩個(gè)距離較遠(yuǎn)的節(jié)點(diǎn)無法比較相似性.Gu等人[4]提出的CDALS算法通過節(jié)點(diǎn)與其公共鄰居連接緊密程度定義了一種相似性度量方法搜索相似節(jié)點(diǎn),Fu等人[5]為搜索相似節(jié)點(diǎn)提出改進(jìn)算法similarity,利用節(jié)點(diǎn)局部影響力進(jìn)行相似性度量.雖然有一些工作利用整個(gè)網(wǎng)絡(luò)來計(jì)算相似性,如simrank,sim2vec等,但他們本質(zhì)上利用的是網(wǎng)絡(luò)中相似性的傳遞性,依舊無法獲取節(jié)點(diǎn)在網(wǎng)絡(luò)中的全局信息.通過隨機(jī)游走獲取全局信息,能夠考慮到整個(gè)網(wǎng)路的拓?fù)浣Y(jié)構(gòu),為節(jié)點(diǎn)提供了一個(gè)高質(zhì)量的結(jié)構(gòu)相似性搜索.個(gè)性化PageRank[6]利用圖結(jié)構(gòu)遞歸計(jì)算全局節(jié)點(diǎn)信息;Zhang等人[7]提出了一種基于隨機(jī)路徑抽樣的方法panther來為給定查詢節(jié)點(diǎn)檢索top-k相似節(jié)點(diǎn);Meng等[8]人對(duì)panther做出改進(jìn),提出了一種單源路徑抽樣的相似節(jié)點(diǎn)搜索算法.然而由于全局隨機(jī)游走的遞歸性質(zhì),這些算法將受到高時(shí)間和空間復(fù)雜性的影響,這在大型網(wǎng)絡(luò)中的效率是非常低下的.

上述兩種方式都側(cè)重于節(jié)點(diǎn)間的結(jié)構(gòu)相似性,大型復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)具有文本信息,例如DBLP[9]數(shù)據(jù)集中,文章標(biāo)題下有作者、文章類型、發(fā)表時(shí)間等信息.基于局部信息檢索相似節(jié)點(diǎn)即使加入文本信息也只能在給定查詢節(jié)點(diǎn)附近進(jìn)行搜索,基于全局信息檢索相似節(jié)點(diǎn)時(shí)加入文本信息使得本就受高時(shí)間空間復(fù)雜性限制的算法更加繁瑣,浪費(fèi)大量算力的同時(shí)效果不甚顯著.

為解決上述問題,本文提出了一種基于卷積神經(jīng)網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)top-k相似節(jié)點(diǎn)搜索方法(LRE-CNN).該方法首先構(gòu)造基于度和權(quán)重的最近鄰網(wǎng)絡(luò),以最近鄰網(wǎng)絡(luò)相對(duì)加權(quán)熵來度量單個(gè)節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu).利用概率論中的相對(duì)熵[10]度量任意兩個(gè)節(jié)點(diǎn)間的結(jié)構(gòu)差異,搜索到的節(jié)點(diǎn)(稱為候選相似節(jié)點(diǎn))與目標(biāo)節(jié)點(diǎn)在結(jié)構(gòu)上具有高相似性.即使兩個(gè)節(jié)點(diǎn)間相隔很遠(yuǎn),仍然能夠通過節(jié)點(diǎn)相似度檢索到.最后,利用卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks,CNN)和深度學(xué)習(xí)模型DeepL對(duì)目標(biāo)節(jié)點(diǎn)和候選相似節(jié)點(diǎn)的文本進(jìn)行特征提取,根據(jù)文本特征嵌入向量為目標(biāo)節(jié)點(diǎn)預(yù)測(cè)出top-k相似節(jié)點(diǎn).

本文的貢獻(xiàn)主要有以下4個(gè)方面:

1)基于概率論中的相對(duì)熵,提出了一種新的節(jié)點(diǎn)結(jié)構(gòu)相似度評(píng)價(jià)標(biāo)準(zhǔn).

2)將卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用到節(jié)點(diǎn)相似度搜索,利用卷積神經(jīng)網(wǎng)絡(luò)挖掘文本間內(nèi)在聯(lián)系.

3)提出了兩階段相似節(jié)點(diǎn)檢索方法,通過在結(jié)構(gòu)相似候選節(jié)點(diǎn)集合上篩選文本相似節(jié)點(diǎn),節(jié)省了大量算力資源.

4)在3個(gè)不同規(guī)模數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn),并與現(xiàn)有3種主流top-k相似節(jié)點(diǎn)檢索方法進(jìn)行對(duì)比,結(jié)果表明本文方法具有更好的收斂性能,經(jīng)過多次試驗(yàn)后得到的節(jié)點(diǎn)集趨于某個(gè)固定值而不再改變,在運(yùn)行時(shí)間和查詢準(zhǔn)確率上有明顯提升,能有效捕獲節(jié)點(diǎn)的結(jié)構(gòu)相似性和文本相似性.

2 相關(guān)工作

2.1 節(jié)點(diǎn)相似性度量

對(duì)于復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)相似性問題的探索,早期的研究者認(rèn)為:兩個(gè)節(jié)點(diǎn)擁有的公共鄰居越多,兩個(gè)節(jié)點(diǎn)越相似.基于這一思想,提出了相似性度量標(biāo)準(zhǔn),用以搜索相似節(jié)點(diǎn).例如,Jaccard系數(shù)和余弦距離,在這些度量中,節(jié)點(diǎn)的特征(鄰居節(jié)點(diǎn),權(quán)重等)可以用來制定相似度評(píng)分,然而這種基于節(jié)點(diǎn)本地特征的度量標(biāo)準(zhǔn)無法度量不共享本地網(wǎng)絡(luò)的節(jié)點(diǎn)對(duì).Hamedani[11]在Jaccard系數(shù)的基礎(chǔ)上引入歸一化思想[12],以一種有效的方式解決了相似節(jié)點(diǎn)兩兩規(guī)范化問題.Haveliwala[6]提出了一種新的節(jié)點(diǎn)相關(guān)度PPR算法.RWR[13]與PPR的基本思想相似.Jeh[14]等人提出了simrank算法,利用“兩個(gè)對(duì)象如果被相似的對(duì)象引用,則這兩個(gè)對(duì)象是相似的”的思想衡量相似節(jié)點(diǎn).P-rank[15],Topsim[16],Lu[17]利用矩陣形式求解所有節(jié)點(diǎn)對(duì)的simrank得分,Wang[18]采用蒙特卡羅和局部推理加快動(dòng)態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)的simrank估計(jì),都是基于迭代或隨機(jī)游走的思想對(duì)simrank做出的改進(jìn).Zhang[19]利用相對(duì)熵度量節(jié)點(diǎn)間的相似性.Jiang[20]等人提出的LRWE-SNM 利用相對(duì)熵計(jì)算有向加權(quán)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)間的相似性.

2.2 相似節(jié)點(diǎn)搜索

為了在大規(guī)模網(wǎng)絡(luò)中執(zhí)行相似節(jié)點(diǎn)的top-k檢索,Zhang[7]等人利用全局隨機(jī)游動(dòng)和VC維數(shù)理論,提出了一種基于隨機(jī)路徑抽樣的方法panther,大致估計(jì)所有節(jié)點(diǎn)對(duì)的相似性得分從而檢索出top-k相似節(jié)點(diǎn).為加快檢索速度,Wang[21],Song[22],Jiang[23]在大規(guī)模網(wǎng)絡(luò)中建立索引,Mustafa[24]在網(wǎng)絡(luò)近鄰查詢中引入切比雪夫不等式.上述3種方式加快查詢速度的同時(shí)失去了精度,Wei等人[25]采用過濾精化模型迭代計(jì)算節(jié)點(diǎn)PPR直到以高置信度得到top-k結(jié)果集.然而,這些算法著重于為節(jié)點(diǎn)檢索結(jié)構(gòu)相似節(jié)點(diǎn),對(duì)節(jié)點(diǎn)文本信息的描述非常少.

3 問題定義

定義1.無向加權(quán)網(wǎng)絡(luò):設(shè)G=(V,E,W)表示一個(gè)網(wǎng)絡(luò),其中,V表示節(jié)點(diǎn)集V={v1,v2,…vn},n為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量,E表示邊集E={e12,e13,…eij},i,j<=n,eij代表一條連接節(jié)點(diǎn)vi和vj的邊,eij=eji.W表示權(quán)重集W={w12,w13,…wij},i,j<=n,wij代表邊eij上的權(quán)重,wij=wji.

定義2.最近鄰網(wǎng)絡(luò):對(duì)于無向加權(quán)網(wǎng)絡(luò)G中的一個(gè)節(jié)點(diǎn)vi,vi的最近鄰網(wǎng)絡(luò)為Gi=(V′,E′,W′),其中V′={vi,vj},vi∈V,vj表示vi的所有鄰居節(jié)點(diǎn);E′={eij},eij∈E,eij表示所有與節(jié)點(diǎn)vi相連的邊;W′={wij},wij∈W,wij表示eij的權(quán)重.

F(·)是節(jié)點(diǎn)在結(jié)構(gòu)和文本上的相似度度量函數(shù),δ為閾值0～1.

4 top-k相似節(jié)點(diǎn)搜索方法

top-k相似節(jié)點(diǎn)搜索方法主要分為兩步:第1步是為目標(biāo)節(jié)點(diǎn)尋找top-k′結(jié)構(gòu)相似節(jié)點(diǎn);第2步是比較top-k′結(jié)構(gòu)相似節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的文本相似性.通過“先結(jié)構(gòu)匹配后文本匹配”的方式逐步縮小查詢范圍,提高了查詢的效率.

4.1 基于最近鄰網(wǎng)絡(luò)的結(jié)構(gòu)相似度評(píng)估

在復(fù)雜網(wǎng)絡(luò)中分析節(jié)點(diǎn)結(jié)構(gòu)相似性時(shí),考慮所有節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)結(jié)構(gòu)的影響將會(huì)耗費(fèi)大量算力,并且部分節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)結(jié)構(gòu)的影響微乎其微.現(xiàn)有研究發(fā)現(xiàn)節(jié)點(diǎn)在復(fù)雜網(wǎng)絡(luò)中的“地位”是由其鄰居節(jié)點(diǎn)決定的[26,27].因此,本文在第3節(jié)中定義的最近鄰網(wǎng)絡(luò)中計(jì)算節(jié)點(diǎn)結(jié)構(gòu)相似度,從而為目標(biāo)節(jié)點(diǎn)搜索top-k′結(jié)構(gòu)相似節(jié)點(diǎn).圖1展示了兩個(gè)節(jié)點(diǎn)結(jié)構(gòu)相似度的完整計(jì)算過程.

圖1 節(jié)點(diǎn)結(jié)構(gòu)相似度計(jì)算過程Fig.1 Calculation process of node structure similarity

對(duì)于目標(biāo)節(jié)點(diǎn)vi及其最近鄰網(wǎng)絡(luò)Gi,Di表示節(jié)點(diǎn)vi的度,Disum表示Gi中所有節(jié)點(diǎn)度之和,即Disum =ΣDi.vi的任一鄰居節(jié)點(diǎn)在最近鄰網(wǎng)絡(luò)Gi中的度概率公式為:

d(i)=Di/Dsum

(1)

目標(biāo)節(jié)點(diǎn)vi在Gi中的度概率表示為:

P(i)
={d(1),d(2),d(3)……d(k),0,0,…….d(MAXn+1)}
={D1/Dsum,D2/Dsum,D3/Dsum,……D(MAXn+1)/Dsum}

(2)

MAXn表示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)度的最大值,n表示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù),最終得到的P(i)是一個(gè)按照d(i)降序排列的向量.由于模型在計(jì)算度概率時(shí)將不同鄰居節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的權(quán)重均設(shè)置為1,未能考慮鄰居節(jié)點(diǎn)權(quán)重不同帶來的影響,因此提出權(quán)重概率來衡量在最近鄰網(wǎng)絡(luò)中權(quán)重對(duì)目標(biāo)節(jié)點(diǎn)的影響.目標(biāo)節(jié)點(diǎn)vi在Gi中的權(quán)重概率表示為:

C(i)={Coni1,Coni2,……Conin′}

(3)

Conin′表示vi的任一鄰居節(jié)點(diǎn)在最近鄰網(wǎng)絡(luò)Gi中的權(quán)重概率,定義為:Conin′={wi1/wsum},wi1表示任一鄰居節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)連接形成的邊的權(quán)重,wsum表示最近鄰網(wǎng)絡(luò)Gi中所有邊權(quán)重之和.

利用最近鄰網(wǎng)絡(luò)相對(duì)加權(quán)熵綜合評(píng)價(jià)權(quán)重和度對(duì)節(jié)點(diǎn)結(jié)構(gòu)的影響,計(jì)算方法定義如式(4)所示:

(4)

概率論中通常用KL散度(相對(duì)熵)來描述兩個(gè)概率分布之間的差異,概率分布P與Q的概率之差可以用式(5)描述:

(5)

N是概率集合R和T中元素的個(gè)數(shù).同樣可以將兩個(gè)節(jié)點(diǎn)的最近鄰網(wǎng)絡(luò)相對(duì)加權(quán)熵代入上式,比較兩個(gè)節(jié)點(diǎn)之間的差異.

(6)

(7)

綜上所述,復(fù)雜網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)的結(jié)構(gòu)相似性均可由上式計(jì)算出,兩個(gè)節(jié)點(diǎn)之間的相似度值越大,就表明兩個(gè)節(jié)點(diǎn)在結(jié)構(gòu)上越具有相似性.根據(jù)相似度計(jì)算出的與目標(biāo)節(jié)點(diǎn)具有高結(jié)構(gòu)相似性的節(jié)點(diǎn)被稱為候選相似節(jié)點(diǎn).

4.2 基于卷積神經(jīng)網(wǎng)絡(luò)的top-k相似節(jié)點(diǎn)預(yù)測(cè)

復(fù)雜網(wǎng)絡(luò)中,節(jié)點(diǎn)除了具有拓?fù)浣Y(jié)構(gòu)外,還具有標(biāo)簽,類別,含義等文本信息.在為目標(biāo)節(jié)點(diǎn)搜索相似節(jié)點(diǎn)時(shí),需要綜合考慮節(jié)點(diǎn)的結(jié)構(gòu)相似和文本相似.本節(jié)通過構(gòu)建CNN卷積神經(jīng)網(wǎng)絡(luò)在候選相似節(jié)點(diǎn)的基礎(chǔ)上為目標(biāo)節(jié)點(diǎn)篩選top-k相似節(jié)點(diǎn).

4.2.1 卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)節(jié)點(diǎn)對(duì)文本關(guān)聯(lián)

候選相似節(jié)點(diǎn)集vk′中的任意一個(gè)節(jié)點(diǎn)v與目標(biāo)節(jié)點(diǎn)u構(gòu)成節(jié)點(diǎn)對(duì)(u,v).為了比較(u,v)之間的文本關(guān)聯(lián),首先將節(jié)點(diǎn)對(duì)的文本特征以稠密低維向量u={u1,u2,…,um},v={v1,v2,…,vm}的形式嵌入到同一向量空間中,不同數(shù)據(jù)集文本特征也是不同的,因此不同類型的文本特征采用不同的嵌入方式.對(duì)于嵌入向量u和v,通過函數(shù)fθ(u,v)生成一個(gè)節(jié)點(diǎn)對(duì)文本相互作用矩陣Xc來表示u,v之間的文本關(guān)聯(lián).其中,每個(gè)元素fij表示向量u的元素ui和向量v的元素vj之間的關(guān)聯(lián).然后,將Xc輸入進(jìn)卷積層進(jìn)行特征提取,計(jì)算方法如式(8)所示:

Mc=a(W×Xc+b)

(8)

其中,W為權(quán)重矩陣,b為W的偏置,α為非線性激活函數(shù)(如ReLU).

將卷積后得到的特征進(jìn)行池化,此時(shí)得到的結(jié)果MP為節(jié)點(diǎn)對(duì)文本相互作用的局部向量,為了增加特征提取的準(zhǔn)確性補(bǔ)充卷積丟失的信息,將Xc展平為一個(gè)向量,與局部向量連接,最終得到節(jié)點(diǎn)對(duì)全局相互作用向量E.向量E代表卷積神經(jīng)網(wǎng)絡(luò)提取到的節(jié)點(diǎn)對(duì)(u,v)的文本信息.

4.2.2 DeepL預(yù)測(cè)相似節(jié)點(diǎn)

本小節(jié)構(gòu)建一個(gè)深度學(xué)習(xí)模型DeepL,捕捉了從評(píng)分行為推斷出的隱含節(jié)點(diǎn)對(duì)文本間聯(lián)系從而預(yù)測(cè)相似節(jié)點(diǎn)對(duì)(網(wǎng)絡(luò)模型如圖2下部所示).評(píng)分行為被定義為由結(jié)構(gòu)相似度形成的評(píng)分函數(shù).為簡(jiǎn)化計(jì)算,DeepL將節(jié)點(diǎn)u和v的id的one-hot向量映射到具有相同維度的聯(lián)合潛在因子空間中,生成低維稠密向量p,q

圖2 相似節(jié)點(diǎn)預(yù)測(cè)Fig.2 Similarity node prediction

(9)

將p,q進(jìn)行元素級(jí)乘積,得到節(jié)點(diǎn)對(duì)的線性交互向量r.

r=p?q=(p1q1,p2q2…pkqk)

(10)

然后將向量r輸入到一個(gè)多層全連接神經(jīng)網(wǎng)絡(luò)中,深入學(xué)習(xí)高層抽象節(jié)點(diǎn)對(duì)的交互.在訓(xùn)練DeepL模型后,Wu和Wv為所有的節(jié)點(diǎn)呈現(xiàn)潛在因素.每層的輸出,計(jì)算如式(11)所示:

a1=ReLu(WT·r+b1)
a2=ReLu(WT·a1+b2)
……
aL=ReLu(WT·aL-1+bL)

(11)

DeepL通過sigmoid函數(shù)將模型輸入壓縮到[0,1]進(jìn)一步預(yù)測(cè)節(jié)點(diǎn)對(duì)相似的概率,0表示節(jié)點(diǎn)對(duì)不相似,1表示節(jié)點(diǎn)對(duì)相似.通過將多尺度評(píng)分轉(zhuǎn)化為二進(jìn)制,解釋了節(jié)點(diǎn)對(duì)相似預(yù)測(cè).

Pθ(y=1|(u,v))

(12)

θ是神經(jīng)網(wǎng)絡(luò)權(quán)重,使用y′作為預(yù)測(cè)輸出.

(13)

5 實(shí)驗(yàn)與評(píng)估

5.1 實(shí)驗(yàn)設(shè)置

5.1.1 數(shù)據(jù)集

Dolphin[28]:Lusseau等在新西蘭對(duì)62只寬吻海豚的生活習(xí)性進(jìn)行了長(zhǎng)時(shí)間的觀察,他們研究發(fā)現(xiàn)這些海豚的交往呈現(xiàn)出特定的模式,并構(gòu)造了包含有62個(gè)結(jié)點(diǎn),159條邊的社會(huì)網(wǎng)絡(luò).如果某兩只海豚經(jīng)常一起頻繁活動(dòng),那么網(wǎng)絡(luò)中相應(yīng)的兩個(gè)結(jié)點(diǎn)之間就會(huì)有一條邊存在.

Grqc[29]:Arxiv gr-qc(廣義相對(duì)論和量子宇宙學(xué))協(xié)作網(wǎng)絡(luò)來自電子印刷的 arxiv,涵蓋作者之間提交到廣義相對(duì)論和量子宇宙學(xué)類的科學(xué)合作.由5242個(gè)節(jié)點(diǎn)和28980條邊組成.如果一個(gè)作者i和作者 j 合著了一篇論文,這個(gè)圖包含一個(gè)從 i 到 j 的無向邊,如果這篇論文是 k 作者合著的,這個(gè)圖就會(huì)在 k 上生成一個(gè)完全連通的(子)圖.

表1 數(shù)據(jù)集Table 1 Dataset

Facebook[30]:收集2017年11月 facebook 頁面的數(shù)據(jù).從這些數(shù)據(jù)中選出了代表運(yùn)動(dòng)員的頁面,組成13866個(gè)節(jié)點(diǎn)和86858條邊的運(yùn)動(dòng)員社交網(wǎng)絡(luò).其中,一個(gè)節(jié)點(diǎn)表示一個(gè)運(yùn)動(dòng)員頁面,邊表示這些運(yùn)動(dòng)員具有相同的喜好.除此之外,還包括運(yùn)動(dòng)員的姓名,性別,地區(qū),運(yùn)動(dòng)類型等文本信息.

5.1.2 參數(shù)與環(huán)境

在所有的實(shí)驗(yàn)中,設(shè)定學(xué)習(xí)率為0.005,迭代輪次為30次.所有的實(shí)驗(yàn)都在windows10操作系統(tǒng),Intel(R)Core(TM)i5-6300HQ CPU @ 2.30GHZ cpu和12GB內(nèi)存的服務(wù)器上進(jìn)行,算法采用python實(shí)現(xiàn).對(duì)比方法中基于路徑的panther和random的路徑長(zhǎng)度設(shè)置為5,因?yàn)槲墨I(xiàn)[7]中證實(shí)t=5時(shí),算法精度和效率都趨于穩(wěn)定.

5.1.3 評(píng)價(jià)指標(biāo)

參考Mei[31]提出的網(wǎng)絡(luò)科學(xué)密度利用top-k結(jié)果的子圖密度來度量結(jié)果集的結(jié)構(gòu)相似性.圖的密度是途中存在邊數(shù)除以圖中可能的最大邊數(shù),密度越大,結(jié)構(gòu)相似性越好.子圖密度定義如下:

(14)

給定節(jié)點(diǎn)vi的top-k相似結(jié)果集,利用結(jié)果集中的頂點(diǎn)構(gòu)造子圖Gk,Gk中邊的總數(shù)除以結(jié)果集的個(gè)數(shù)即為vi的子圖密度.整張圖的子圖密度衡量算法在結(jié)構(gòu)相似性上的準(zhǔn)確性.

兩個(gè)節(jié)點(diǎn)擁有的相同屬性越多,兩個(gè)節(jié)點(diǎn)在文本上就越具有相似性.因此,利用公共屬性分?jǐn)?shù)[7]來衡量結(jié)果集與給定查詢節(jié)點(diǎn)的文本相似程度.公共屬性分?jǐn)?shù)定義如下:

(15)

其中,u為目標(biāo)節(jié)點(diǎn),v為u的top-k相似節(jié)點(diǎn)集S中的元素,A(u),A(v)分別代表u,v的屬性.CA評(píng)估結(jié)果集中所有成對(duì)節(jié)點(diǎn)的屬性相似性.

5.1.4 比較方法

Random:從圖的任意一個(gè)頂點(diǎn)vi出發(fā),隨機(jī)走至其鄰居節(jié)點(diǎn)中的任意一個(gè)節(jié)點(diǎn),將鄰居節(jié)點(diǎn)視為目標(biāo)節(jié)點(diǎn)繼續(xù)選中鄰居節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn),直到獲得一條長(zhǎng)度為5的路徑,以vi為初始點(diǎn)的n條路徑中,出現(xiàn)次數(shù)最多的節(jié)點(diǎn)即為vi的相似節(jié)點(diǎn).

Simrank[14]:基本思想是如果圖中兩個(gè)節(jié)點(diǎn)相似,那么它們相關(guān)的節(jié)點(diǎn)也相似.為節(jié)省時(shí)間空間消耗,使用矩陣形式代替迭代公式,定義相似度矩陣S和轉(zhuǎn)移概率矩陣Q,如果從節(jié)點(diǎn)vi可以轉(zhuǎn)移到節(jié)點(diǎn)vj,則這兩個(gè)節(jié)點(diǎn)相似.通過迭代更新相似度矩陣,尋找目標(biāo)節(jié)點(diǎn)的top-k相似節(jié)點(diǎn).

Panther[7]:隨機(jī)選擇網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)vi作為起點(diǎn),根據(jù)其轉(zhuǎn)移概率從vi到其鄰居進(jìn)行l(wèi)步的隨機(jī)行走得到r條隨機(jī)路徑,之后通過迭代所有采樣路徑來累計(jì)每個(gè)節(jié)點(diǎn)對(duì)的相似性分?jǐn)?shù).最后,根據(jù)基于堆結(jié)構(gòu)的相似性得分對(duì)節(jié)點(diǎn)進(jìn)行排序,以返回排名top-k的相似節(jié)點(diǎn)的列表.

5.2 實(shí)驗(yàn)評(píng)估

5.2.1 準(zhǔn)確性

圖3(a～c)顯示了不同網(wǎng)絡(luò)上top-k結(jié)果集的子圖密度.從圖中可以看出,LRE-CNN在Dolphin和Grqc數(shù)據(jù)集上表現(xiàn)不佳.基于路徑對(duì)Panther和Random進(jìn)行采樣,得到的結(jié)果集具有很高的可見性.Simrank利用遞歸的思想來獲得路徑上具有連接性的結(jié)果集.LRE-CNN的提出打破了隨機(jī)游動(dòng)和遞歸的局部化.因此,LRE-CNN在子圖密度下的低性能從側(cè)面證明了算法的有效性.

圖3 子圖密度比較Fig.3 Comparison on subgraph density

圖4(a～c)顯示了不同網(wǎng)絡(luò)中top-k結(jié)果集的公共屬性得分.可以看到LRE-CNN明顯優(yōu)于Panther和Simrank.LRE-CNN得到的top-k結(jié)果集與目標(biāo)節(jié)點(diǎn)具有較高的文本相似度.

圖4 公共屬性得分比較Fig.4 Comparison on CA

5.2.2 可擴(kuò)展性

圖5(a～c)顯示了在不同k條件下,這4種方法在Dolphin、Grqc和Facebook網(wǎng)絡(luò)中的運(yùn)行時(shí)間.從圖中可以看出,數(shù)據(jù)集大小和k值的變化都會(huì)導(dǎo)致simrank和panther的檢索時(shí)間出現(xiàn)波動(dòng),并且隨著k值的增加,運(yùn)行時(shí)間顯著增加.當(dāng)LRE-CNN和random對(duì)同一數(shù)據(jù)集進(jìn)行不同的top-k檢索時(shí),時(shí)間基本沒有變化.LRE-CNN和random比其他兩種方法有更好的收斂性.

圖5 可擴(kuò)展性比較Fig.5 Comparison on scalability

5.2.3 超參數(shù)

本實(shí)驗(yàn)旨在驗(yàn)證LRE-CNN算法的超參數(shù).具體實(shí)驗(yàn)如下:將Grqc數(shù)據(jù)集上的epoch固定為30,改變學(xué)習(xí)速率l(分別設(shè)置為0.001、0.003、0.005和0.01),測(cè)試算法在不同k值下的準(zhǔn)確性.將學(xué)習(xí)速率固定在0.005,改變epoch輪數(shù),測(cè)試不同k值下算法的準(zhǔn)確性.

從圖6可看出,當(dāng)學(xué)習(xí)速率l=0.001時(shí),算法的準(zhǔn)確率最高.但是,epoch的變化對(duì)算法的精度影響很小.證明了算法的穩(wěn)定性和收斂性.

圖6 超參數(shù)實(shí)驗(yàn)Fig.6 Hyperparametric experiment

根據(jù)不同方法的子圖密度和公共屬性得分以及不同的參數(shù)敏感性,可以得出LRE-CNN可以有效地估計(jì)結(jié)構(gòu)和文本中節(jié)點(diǎn)的相似度,具有較高的精度和收斂性,大大提高了查詢效率.

6 結(jié) 論

本文針對(duì)復(fù)雜環(huán)境下,搜索與給定節(jié)點(diǎn)具有結(jié)構(gòu)和文本相似性的top-k節(jié)點(diǎn)問題,提出了一種基于卷積神經(jīng)網(wǎng)絡(luò)的相似節(jié)點(diǎn)搜索算法.本文與現(xiàn)有先進(jìn)方法的不同之處在于3個(gè)方面:1)基于概率論中的相對(duì)熵,提出了一種新的結(jié)構(gòu)相似度評(píng)價(jià)標(biāo)準(zhǔn),節(jié)點(diǎn)相似度;2)將卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用到節(jié)點(diǎn)相似度檢索,利用卷積神經(jīng)網(wǎng)絡(luò)挖掘文本間內(nèi)在聯(lián)系;3)提出了兩階段相似節(jié)點(diǎn)檢索方法,通過在結(jié)構(gòu)相似候選節(jié)點(diǎn)集合上篩選文本相似節(jié)點(diǎn),節(jié)省了大量算力資源.未來工作將研究將本文方法推廣到規(guī)模更大,節(jié)點(diǎn)具有更多文本屬性,以及節(jié)點(diǎn)間具有更多復(fù)雜關(guān)系的網(wǎng)絡(luò)中.