卷積神經(jīng)網(wǎng)絡(luò)的top-k相似節(jié)點搜索方法

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

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

1 引 言

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

2.2 相似節(jié)點搜索

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

3 問題定義

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

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

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

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

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

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

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

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

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

d(i)=Di/Dsum

(1)

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

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

(3)

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

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

(4)

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

(5)

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

(6)

(7)

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

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

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

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

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

Mc=a(W×Xc+b)

(8)

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

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

4.2.2 DeepL預(yù)測相似節(jié)點

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

圖2 相似節(jié)點預(yù)測Fig.2 Similarity node prediction

(9)

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

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

(10)

然后將向量r輸入到一個多層全連接神經(jīng)網(wǎng)絡(luò)中,深入學(xué)習(xí)高層抽象節(jié)點對的交互.在訓(xùn)練DeepL模型后,Wu和Wv為所有的節(jié)點呈現(xiàn)潛在因素.每層的輸出,計算如式(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ù)測節(jié)點對相似的概率,0表示節(jié)點對不相似,1表示節(jié)點對相似.通過將多尺度評分轉(zhuǎn)化為二進(jìn)制,解釋了節(jié)點對相似預(yù)測.

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

(12)

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

(13)

5 實驗與評估

5.1 實驗設(shè)置

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

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

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

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

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

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

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

5.1.3 評價指標(biāo)

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

(14)

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

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

(15)

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

5.1.4 比較方法

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

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

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

5.2 實驗評估

5.2.1 準(zhǔn)確性

圖3(a～c)顯示了不同網(wǎng)絡(luò)上top-k結(jié)果集的子圖密度.從圖中可以看出,LRE-CNN在Dolphin和Grqc數(shù)據(jù)集上表現(xiàn)不佳.基于路徑對Panther和Random進(jìn)行采樣,得到的結(jié)果集具有很高的可見性.Simrank利用遞歸的思想來獲得路徑上具有連接性的結(jié)果集.LRE-CNN的提出打破了隨機游動和遞歸的局部化.因此,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é)點具有較高的文本相似度.

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

5.2.2 可擴展性

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

圖5 可擴展性比較Fig.5 Comparison on scalability

5.2.3 超參數(shù)

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

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

圖6 超參數(shù)實驗Fig.6 Hyperparametric experiment

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

6 結(jié) 論

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