代 秀 珍

(包頭鐵道職業(yè)技術(shù)學(xué)院 內(nèi)蒙古 包頭 014060)

0 引 言

網(wǎng)絡(luò)對于現(xiàn)代社會是不可缺少的一部分,對網(wǎng)絡(luò)中不可觀測的鏈路進(jìn)行預(yù)測對維護(hù)網(wǎng)絡(luò)的穩(wěn)定運(yùn)行、提升網(wǎng)絡(luò)運(yùn)行效率等具有重要的意義[1]。例如,它可以省去盲目檢查蛋白質(zhì)網(wǎng)絡(luò)中的交互作用,改進(jìn)社交網(wǎng)絡(luò)和電子商務(wù)網(wǎng)絡(luò)的推薦服務(wù),幫助完成信息確認(rèn)[2-3]。

近年來,鏈路預(yù)測研究越來越重視鄰域信息,它代表了網(wǎng)絡(luò)節(jié)點(diǎn)的局部結(jié)構(gòu),通常被認(rèn)為是鏈路預(yù)測的重要線索之一。許多方法側(cè)重于人工設(shè)計相似性指標(biāo)和鄰域特征,最具代表性的是基于鄰域的啟發(fā)式算法,如公共鄰域算法(Common Neighborhood,CN)、ADAMIAC adar(AA)和Simrank(SR)[4-6]。雖然方法簡單,但這些啟發(fā)式算法一個主要的限制是,由于它們的線性增強(qiáng)性,往往不能廣泛應(yīng)用于多個網(wǎng)絡(luò)。并且在為不同類型的網(wǎng)絡(luò)選擇啟發(fā)式和特征時,先驗(yàn)知識或昂貴的試驗(yàn)和錯誤是不可避免的。因此,尋找一種能夠自動學(xué)習(xí)具有表達(dá)性的鄰域特征并具有廣泛的鏈路預(yù)測適用性的方法是非常重要的。

因此近年來發(fā)展了一些基于神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測模型,這些模型利用神經(jīng)層來探索非線性的深層結(jié)構(gòu)特征。文獻(xiàn)[7]使用圖標(biāo)記算法將兩個節(jié)點(diǎn)的聯(lián)合鄰域作為矩陣,并使用卷積神經(jīng)層來預(yù)測鏈路編碼。文獻(xiàn)[8]在對抗生成網(wǎng)絡(luò)(Generative Adversarial Networks,GAN)中引入一個鑒別器與之進(jìn)行對抗博弈,鑒別器嘗試將生成的樣本從地面真實(shí)樣本中分離出來。近年來,針對網(wǎng)絡(luò)嵌入模型提出了一些基于對抗學(xué)習(xí)的正則化方法,以提高網(wǎng)絡(luò)嵌入模型的魯棒性。但是上述方法均沒有充分挖掘鄰域特征信息,無法實(shí)現(xiàn)端到端的方式預(yù)測鏈路,且模型的泛化能力不強(qiáng)。

針對上述問題,提出了一種基于對抗學(xué)習(xí)鄰域注意網(wǎng)絡(luò)的鏈路預(yù)測模型。在各種網(wǎng)絡(luò)類型的12個基準(zhǔn)數(shù)據(jù)集上評估所提出方法的性能,實(shí)驗(yàn)結(jié)果證明了提出方法的優(yōu)越性。

1 基礎(chǔ)理論

1.1 基礎(chǔ)定義

網(wǎng)絡(luò)可以表示為圖G(V,E),其中V={v1,v2,…,vN}是節(jié)點(diǎn)的集合,E?V×V是鏈路的集合,并且總數(shù)為節(jié)點(diǎn)為N。圖的結(jié)構(gòu)信息通常表示為鄰接矩陣A,其中,如果存在從節(jié)點(diǎn)vi到vj的鏈接,則Ai,j=1,否則Ai,j=0。如果鏈接是無向的,則A是對稱的。使用Nh(vi)表示節(jié)點(diǎn)vi的第h階鄰域,即到vi的距離不大于h階的節(jié)點(diǎn)集。vi為中心節(jié)點(diǎn),vj∈Nh(vi)為h階內(nèi)vi的鄰域。

在鏈路預(yù)測場景中,給定目標(biāo)節(jié)點(diǎn)對(vi,vj),本文將vi的相鄰節(jié)點(diǎn),即vk∈Nh(vi)定義為vj的自鄰域節(jié)點(diǎn)和vj的跨鄰域節(jié)點(diǎn)。同樣,vj的相鄰節(jié)點(diǎn),即v1∈Nh(vj),被定義為vj的自鄰域節(jié)點(diǎn)和vi的交叉相鄰節(jié)點(diǎn)。

鏈路預(yù)測問題可分為時間鏈路預(yù)測和臨時性鏈路預(yù)測,前者可預(yù)測不斷發(fā)展的網(wǎng)絡(luò)中潛在的新鏈路,后者可推斷靜態(tài)網(wǎng)絡(luò)中的缺失鏈路。重點(diǎn)介紹結(jié)構(gòu)鏈接預(yù)測。給定部分觀察到的網(wǎng)絡(luò)結(jié)構(gòu),其目標(biāo)是預(yù)測未觀察到的鏈路。形式上,給定部分觀測的網(wǎng)絡(luò)G=(V,E),本文將未知鏈路狀態(tài)的節(jié)點(diǎn)對集合表示為EΣ=V×V-E,則結(jié)構(gòu)鏈接預(yù)測的目標(biāo)是推斷EΣ中節(jié)點(diǎn)對的鏈接狀態(tài)。

提出了一種用于多空間鄰域注意機(jī)制(Multi Spatial Neighborhood Attention,MSNA)以及用于鏈路預(yù)測的兩個鄰域注意網(wǎng)絡(luò)(Neighborhood Attention Network,NAN)即自鄰域注意網(wǎng)絡(luò)(Self Neighborhood Attention Network,SNAN)和跨鄰域注意網(wǎng)絡(luò)(Cross Neighborhood Attention Network,CNAN)。給定一對節(jié)點(diǎn)(vi,vj)及其鄰域信息,提出的注意神經(jīng)網(wǎng)絡(luò)旨在將其鏈接得分推斷為:si,j=NAN(vi,Nh(vi),vj,Nh(vj))。

1.2 多空間鄰域注意機(jī)制

在鏈接預(yù)測問題中,通常將鄰域視為關(guān)鍵上下文信息。提出的多空間鄰域注意機(jī)制原因是鄰域?qū)τ谥行墓?jié)點(diǎn)具有不同的結(jié)構(gòu)重要性,并且如果從不同方面來看,重要性也有所不同。例如,在社交網(wǎng)絡(luò)中,某些鄰居在考慮共同的朋友時更重要,而其他一些鄰居在考慮中心性時則更為重要。該機(jī)制在多個潛在空間中學(xué)習(xí)重要的注意關(guān)系,這些潛在空間代表了潛在的不同方面。通過在不同空間中集中關(guān)注重點(diǎn),該機(jī)制能夠構(gòu)建全面的鄰域特征。

形式上,給定中心節(jié)點(diǎn)vi、其h階鄰域Nh(vi),以及這些節(jié)點(diǎn)的特征x∈Rdx,該算法利用注意分量構(gòu)造中心節(jié)點(diǎn)的潛在鄰域特征ci=fattn(xi,{xj∈Nh(vi)}),其中fattn()是基于注意力的編碼函數(shù)。

在每個潛在空間s中,定義中心節(jié)點(diǎn)vi對它的相鄰節(jié)點(diǎn)vj∈Nh(vi)的關(guān)注,它表示相鄰節(jié)點(diǎn)vj在Nh(vi)中的重要性,如下所示:

(1)

(2)

(3)

式中:[;]表示串聯(lián)運(yùn)算ci∈RSdx。另外,使用fattn(xi,{xj})表示在中心節(jié)點(diǎn)vi和上下文節(jié)點(diǎn){vj}之間發(fā)送上述基于注意力的編碼過程。

1.3 自鄰域注意網(wǎng)絡(luò)

基于MSNA機(jī)制,本文首先提出SNAN。如圖1(a)所示,SNAN由用于自鄰域編碼的注意層和用于鏈路分?jǐn)?shù)預(yù)測的節(jié)點(diǎn)對匹配層組成。

(a) SNAN (b) CNAN

SNAN的輸入是一對節(jié)點(diǎn)(vi,vj)。由于本文沒有考慮節(jié)點(diǎn)的其他信息,因此節(jié)點(diǎn)的輸入表示是節(jié)點(diǎn)IDs的一元向量o∈RN。本文通過線性映射x=Wxo將一元向量作為潛在節(jié)點(diǎn)特征進(jìn)行傳輸,其中Wx∈Rdx×N將通過模型學(xué)習(xí)。

給定輸入節(jié)點(diǎn)及其鄰近節(jié)點(diǎn)的節(jié)點(diǎn)嵌入,SNAN的關(guān)注層使用所提出的關(guān)注機(jī)制對兩個輸入節(jié)點(diǎn)的各自鄰域信息進(jìn)行編碼:

ci=fattn(xi,{xk|vk∈Nh(vi)})

(4)

cj=fattn(xj,{xl|vl∈Nh(vj)})

(5)

給定已編碼的自相鄰信息ci和cj,節(jié)點(diǎn)對匹配層將如下預(yù)測鏈路得分:

(6)

這里采用由矩陣W∈RSdx×Sdx參數(shù)化的雙線性評分函數(shù)。此功能通過匹配兩個輸入節(jié)點(diǎn)的鄰域上下文嵌入來測量鏈接分?jǐn)?shù)。該函數(shù)適用于有向圖和無向圖,當(dāng)圖是無向的時,本文將W設(shè)為一個單位矩陣,以使分?jǐn)?shù)對一對節(jié)點(diǎn)是對稱的。

1.4 跨鄰域注意網(wǎng)絡(luò)

SNAN僅通過具有編碼的自鄰域特征的匹配層隱式捕獲兩個節(jié)點(diǎn)之間的結(jié)構(gòu)交互。為了以更明確的方式捕獲交互,提出了一個擴(kuò)展模型,即CNAN。如圖1(b)所示,還設(shè)計了一個跨鄰域注意,使CNAN能夠探索注意層的結(jié)構(gòu)相互作用。通過計算一個輸入節(jié)點(diǎn)與另一輸入節(jié)點(diǎn)的鄰域之間的注意力來生成跨上下文嵌入。如果兩個節(jié)點(diǎn)鏈接在一起,則對于相同的鄰域上下文,它們應(yīng)該具有相似的上下文表示。

跨上下文嵌入是使用提出的注意力機(jī)制構(gòu)造的,不同之處在于上下文節(jié)點(diǎn)是交叉相鄰節(jié)點(diǎn),而不是自鄰域節(jié)點(diǎn)。令ci→j表示從輸入節(jié)點(diǎn)vi到vj的相鄰節(jié)點(diǎn)Nh(vj)的跨上下文嵌入,反之亦然,則ci→j和cj→i的計算定義為:

ci→j=fattn(xi,{xl|vl∈Nh(vj)})

(7)

cj→i=fattn(xj,{xk|vk∈Nh(vk)})

(8)

此外,CNAN以與SNAN相同的方式構(gòu)造自上下文嵌入ci和cj。給定已編碼的自身和跨鄰域信息,本文定義鏈接評分功能如下:

(9)

在這里使用三個雙線性乘積來測量鏈接得分。該評分功能不僅匹配兩個自上下文嵌入,還匹配交叉鄰域嵌入和相應(yīng)的自鄰域嵌入。另外該函數(shù)還針對有向圖和無向圖進(jìn)行了概括:如果圖形是有向的,則W1,W2,W3∈RSdx×Sdx是三個不同的參數(shù)矩陣;如果圖是無向的,則令W1為單位矩陣,W2=W3。

2 對抗制模式學(xué)習(xí)

2.1 學(xué)習(xí)目標(biāo)

鏈接預(yù)測問題的目的是推斷節(jié)點(diǎn)對是否鏈接。由于網(wǎng)絡(luò)的稀疏性,鏈接對和非鏈接對之間經(jīng)常存在極度不平衡的現(xiàn)象。為了更好地處理不平衡問題,本文采用了模型學(xué)習(xí)的排序思想,其目的是對鏈接節(jié)點(diǎn)對進(jìn)行評分,使其得分高于非鏈接對。

sij>skl?(vi,vj)∈E和?(vk,vt)∈E-

(10)

式中:E-是真正的非鏈接對的集合。將學(xué)習(xí)目標(biāo)定義如下:

(11)

式中:Dθ代表NAN模型,θ是模型參數(shù)集,因此Si,j=Dθ(vi,vj)。對于正樣本(vi,vj)∈E,考慮每一個邊界負(fù)樣本(vi,vk),該樣本將vi視為錨節(jié)點(diǎn),并將其鏈接節(jié)點(diǎn)vj替換為未鏈接的一個vk。如果網(wǎng)絡(luò)是無向的,則將vi或vj視為錨點(diǎn)。本文采用基于邊界的排名損失,這迫使正樣本的得分高于具有邊界γ的負(fù)樣本的得分(γ=1)。

實(shí)際上,訓(xùn)練數(shù)據(jù)中沒有真正的非鏈接集E-。常規(guī)策略是使用vi隨機(jī)采樣具有未觀察到的鏈路狀態(tài)的節(jié)點(diǎn)vk并將(vi,vk)假定為負(fù)樣本。但是,由于完全隨機(jī)性,隨機(jī)采樣策略的性能并不總是穩(wěn)定的。例如,在訓(xùn)練過程達(dá)到一定水平之后,隨機(jī)采樣器有較高的可能性提取學(xué)習(xí)良好的樣本,這滿足了裕度約束,并不可避免地帶來損失。這些無用的負(fù)樣本使模型幾乎沒有改善,因此卡在了一些不太理想的點(diǎn)上。在其他任務(wù)中也發(fā)現(xiàn)了類似的隨機(jī)負(fù)采樣問題,例如知識圖嵌入和圖像檢索。

本文提出了一種對抗學(xué)習(xí)框架,可為所提出的模型提供更有效和魯棒的優(yōu)化解決方案。具體來說,引入了一個生成模型G?(由?參數(shù)化)來生成負(fù)樣本,而不是隨機(jī)樣本。G?和鏈接預(yù)測模型Dθ(判別器)在此框架中進(jìn)行極小極大博弈。G?連續(xù)提供高質(zhì)量的信息性負(fù)樣本,Dθ觀察到的真實(shí)鏈接與生成的負(fù)樣本之間有明顯的區(qū)別。正式地,將極小極大博弈定義為:

(12)

(13)

鏈接預(yù)測模型Dθ的目標(biāo)是一個類似于式(11)的最小化問題。唯一的區(qū)別是負(fù)樣本由G?給出,其中Evk～G?(vk|vi)表示對生成器中負(fù)樣本分布的期望G?。另一方面,生成器G?的目的是最大化問題。這些負(fù)樣本將被直接測量為鏈接得分Dθ(vi,vk),分?jǐn)?shù)越高,樣本越豐富。分別通過最大化和最小化兩個目標(biāo)函數(shù)可以迭代地學(xué)習(xí)Dθ和G?的最優(yōu)參數(shù)。

2.2 負(fù)樣本生成器

由于考慮到每個邊緣的負(fù)樣本,因此生成器的輸入是正樣本(vi,vj)中的選定錨節(jié)點(diǎn)。對于定向網(wǎng)絡(luò),選擇源節(jié)點(diǎn)vi作為錨點(diǎn)節(jié)點(diǎn)。對于無向網(wǎng)絡(luò),vi或vj以相等的概率隨機(jī)選擇。

(14)

(15)

2.3 優(yōu) 化

1) 優(yōu)化鑒別器Dθ:可以通過隨機(jī)梯度下降法直接解決鑒別器Dθ的最小化問題。給定從生成器G?生成的正樣本(vi,vj)和負(fù)樣本(vi,vk),Dθ的參數(shù)將使用以下梯度更新。

2) 優(yōu)化生成器G?:生成器G?的目標(biāo)是最大化問題,但是,由于發(fā)生器的輸出是離散的,即節(jié)點(diǎn)IDvk,因此無法通過梯度上升方法直接優(yōu)化該問題。為了解決這個問題,采用了廣泛使用的基于策略梯度的強(qiáng)化學(xué)習(xí)(RL)算法。在RL的意義上,生成器G?充當(dāng)“代理”,而鑒別符Dθ被視為“環(huán)境”。代理G?通過基于當(dāng)前“狀態(tài)”執(zhí)行“操作”來與環(huán)境Dθ進(jìn)行交互,并通過最大化響應(yīng)于其操作而從環(huán)境返回的“獎勵”來改善自身。在該場景中,狀態(tài)由輸入錨節(jié)點(diǎn)vi表示,動作生成負(fù)樣本(vi,vk),獎勵定義為生成的樣本Dθ(vi,vk)的鏈接得分。返回的獎勵直接用于強(qiáng)化學(xué)習(xí)中的梯度計算。對于正樣本(vi,vj)和生成的負(fù)樣本Dθ(vi,vk)的獎勵,得出式(13)的梯度如下:

(16)

在最后一步中,對K個生成的樣本使用近似值。另外,通常使用獎勵的基線值來減小強(qiáng)化學(xué)習(xí)的方差。本文將基線rb定義為一個訓(xùn)練時期的平均獎勵。使用該獎勵基準(zhǔn),將式(17)中的獎勵Dθ(vi,vk)替換為Dθ(vi,vk)-rb。

3) 整體學(xué)習(xí)算法:如前所述,本文可以通過迭代優(yōu)化兩個目標(biāo)來得出最佳參數(shù)。算法1中提供了該對抗性學(xué)習(xí)框架的詳細(xì)信息。通過小批量訓(xùn)練來更新參數(shù)。對于每個小批量的正樣本,首先讓Gφ生成相同數(shù)量的具有批次大小的負(fù)樣本。給定一批正樣本和負(fù)樣本,該算法會迭代更新鑒別器和生成器的參數(shù)。學(xué)習(xí)率分別為η1和η2。在這里,介紹了一種傳統(tǒng)梯度算法(Vanilla Gradient Method,VGM),但是可以用任何基于梯度的優(yōu)化方法代替。在每個訓(xùn)練時期之后,該算法都會計算新的獎勵基準(zhǔn)。

算法1NANs的對抗性學(xué)習(xí)

輸入:訓(xùn)練網(wǎng)絡(luò)G=(V,E)。

輸出:鏈接預(yù)測模型Dθ(SNAN或CNAN)。

1 初始化Dθ的參數(shù)θ和生成器Gφ的參數(shù)φ。

2 循環(huán)

3 當(dāng) 每個小批量Ebat∈E時 執(zhí)行

4 當(dāng) (vi,vj)∈Ebat執(zhí)行

5 用電流生成器Gφ(vk|vi)產(chǎn)生一個負(fù)對(vi,vk);

6 當(dāng)固定Gφ時更新Dθ:

8 當(dāng)固定Dθ時更新Gφ:

10rs←rs+ΣDθ(vi,vk);

12 收斂。

3 實(shí)驗(yàn)與分析

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

本文在包括多種網(wǎng)絡(luò)類型的12個基準(zhǔn)數(shù)據(jù)集上評估所提出方法的性能。EML是電子郵件通信網(wǎng)絡(luò)。該網(wǎng)絡(luò)中的節(jié)點(diǎn)是電子郵件地址,每個邊緣代表至少已發(fā)送一封電子郵件。CEG是隱桿線蟲的生物神經(jīng)網(wǎng)絡(luò)。神經(jīng)元是節(jié)點(diǎn),神經(jīng)元之間的連接突觸是邊界。PLB是美國2004年選舉后的政治博客網(wǎng)絡(luò),博客代表節(jié)點(diǎn),博客之間的超鏈接是邊緣。KHN是一個引用網(wǎng)絡(luò)Kohonen網(wǎng)絡(luò)。節(jié)點(diǎn)是科學(xué)論文,主題為“自組織圖”,引用關(guān)系代表邊界。HTC是一個科學(xué)合作網(wǎng)絡(luò)。關(guān)于“高能物理”主題的預(yù)印本作者代表節(jié)點(diǎn),每個邊緣代表兩個作者至少共同創(chuàng)作了一次。

UPG是美國電網(wǎng)的物理基礎(chǔ)設(shè)施網(wǎng)絡(luò),其中節(jié)點(diǎn)是發(fā)電站,鏈路是發(fā)電站之間的傳輸線。UAL是美國航空公司的交通網(wǎng)絡(luò)。節(jié)點(diǎn)是美國的機(jī)場,邊緣是機(jī)場之間的現(xiàn)有航線。F2F是展覽中的面對面行為網(wǎng)絡(luò)。節(jié)點(diǎn)是展覽的參與者,邊緣代表一定時間內(nèi)的F2F通信。SMG是另一個引文網(wǎng)絡(luò),其中節(jié)點(diǎn)是對經(jīng)典文章的引用。YST是一種蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)。節(jié)點(diǎn)是不同的蛋白質(zhì),每個邊界表示觀察到兩種蛋白質(zhì)之間的相互作用。CORA和CITESEER是兩個流行的引文網(wǎng)絡(luò),在圖神經(jīng)網(wǎng)絡(luò)和鏈接預(yù)測的最新研究中被廣泛用作基準(zhǔn)數(shù)據(jù)集。數(shù)據(jù)的詳細(xì)統(tǒng)計數(shù)據(jù)在表1中示出。較低的平均程度表示網(wǎng)絡(luò)的稀疏性較高,這可能會給鏈接預(yù)測帶來困難。

表1 詳細(xì)統(tǒng)計數(shù)據(jù)

3.2 對比方法

為了充分證明所提出模型的有效性,本文將以下三種方法作為對比方法:

1) 基于鄰域的啟發(fā)式方法[9-11]:本文以六種傳統(tǒng)啟發(fā)式方法為基準(zhǔn),包括三種一階啟發(fā)式方法,即CN、Jaccard索引(JC)和優(yōu)先連接(PA);兩種二階啟發(fā)式算法,即Adamic Adar(AA)和資源分配(RA);和一個代表性的高階鄰域啟發(fā)式SR。

2) 潛在節(jié)點(diǎn)嵌入模型[12-14]:學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的潛在嵌入是鏈路預(yù)測問題的另一個至關(guān)重要的方式。

矩陣分解(MF):基于矩陣分解的鏈接預(yù)測方法是最經(jīng)典的潛在特征學(xué)習(xí)模型之一,它旨在基于節(jié)點(diǎn)潛在特征來重建用戶對的二進(jìn)制分?jǐn)?shù)。

LINE:LINE是一種流行的通用網(wǎng)絡(luò)表示學(xué)習(xí)方法,它分別學(xué)習(xí)一階接近嵌入和二階接近嵌入,并將它們串聯(lián)為最終嵌入。

N2V:Node2vec是另一個代表性的節(jié)點(diǎn)嵌入模型。它通過隨機(jī)行走對結(jié)構(gòu)信息進(jìn)行采樣,并通過保留行走附近節(jié)點(diǎn)的相似性來學(xué)習(xí)嵌入。

PNRL:PNRL是最新的鏈路預(yù)測專用嵌入模型。該模型通過共同保存觀察到的結(jié)構(gòu)信息并預(yù)測假定的隱藏鏈接來學(xué)習(xí)嵌入。

3) 基于神經(jīng)網(wǎng)絡(luò)的模型[15-16]:隨著神經(jīng)網(wǎng)絡(luò)在各種任務(wù)上的成功,提出了幾種基于神經(jīng)網(wǎng)絡(luò)的鏈接預(yù)測模型。

圖自動編碼器(Graph Automatic Encoder,GAE)和變異圖自動編碼器(Variants Graph Automatic Encoder,VGAE):GAE和VGAE使用圖卷積網(wǎng)絡(luò)(Graph Convolution Network,GCN)將圖鄰接矩陣編碼為潛在表示并重建觀察到的鏈接或使用內(nèi)部產(chǎn)品解碼器預(yù)測未觀察到的鏈接。

Weisfeiler-Lehman神經(jīng)機(jī)器(Weisfeiler Lehman Neural Machine,WLNM):WLNM是用于鏈路預(yù)測的最先進(jìn)的神經(jīng)網(wǎng)絡(luò)。它使用圖標(biāo)記算法將包圍的子圖轉(zhuǎn)換為有意義的矩陣,該子圖是節(jié)點(diǎn)對在結(jié)構(gòu)上的組合鄰域。然后,使用卷積神經(jīng)網(wǎng)絡(luò)(CNN)對標(biāo)記的矩陣進(jìn)行編碼,并通過分類層預(yù)測鏈接分?jǐn)?shù)。

SEAL:SEAL是另一個基于圖神經(jīng)網(wǎng)絡(luò)的最新鏈接預(yù)測框架。它從局部封閉的子圖學(xué)習(xí)一般的圖結(jié)構(gòu)特征。SEAL彌補(bǔ)了WLNM的一些缺點(diǎn),深度圖卷積神經(jīng)網(wǎng)絡(luò)(Depth Graph Convolution Neural Network,DGCNN)被用來代替WLNM中的CNN,從而實(shí)現(xiàn)了更好的圖特征學(xué)習(xí)能力。

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

為了更加有效地評估提出的模型,本文使用五重交叉驗(yàn)證設(shè)置進(jìn)行比較實(shí)驗(yàn)。對于每個交叉驗(yàn)證,隨機(jī)抽樣原始網(wǎng)絡(luò)的10%邊緣進(jìn)行測試,另外隨機(jī)抽取10%進(jìn)行驗(yàn)證,還分別對相同數(shù)量的非關(guān)聯(lián)對進(jìn)行了采樣,它們分別與測試和對等陰性實(shí)例相符。本文刪除采樣的邊緣,并將其余80%的邊緣視為訓(xùn)練網(wǎng)絡(luò)。鏈路預(yù)測性能是通過接收器工作特性曲線(Area Under Curve,AUC)下的面積測量的,該曲線是廣泛使用的標(biāo)準(zhǔn)度量。

比較方法的詳細(xì)參數(shù)設(shè)置如下。對于SR,本文遵循文獻(xiàn)[12]中的設(shè)置,其中衰減率為0.6。所有潛在嵌入模型的嵌入大小均設(shè)置為64。對于LINE,負(fù)對比估計的采樣數(shù)設(shè)置為5。對于N2V,窗口大小為10,步長為80,每個節(jié)點(diǎn)的步長為10。對于LINE和N2V,邊緣特征為節(jié)點(diǎn)的Hadamard乘積嵌入。

對于預(yù)測性網(wǎng)絡(luò)表示學(xué)習(xí)(Predictive Network Representation Learning,PNLR),噪聲對比估計(Noise Contrast Estimation,NCE)的數(shù)量為5,使用秩損失以實(shí)現(xiàn)更好的性能,正則化權(quán)重為0.01,隱藏鏈接采樣比為0.2。比較的神經(jīng)網(wǎng)絡(luò)模型的嵌入大小和隱藏大小也設(shè)置為64。對于VGAE,潛變量的維度大小為64,并使用默認(rèn)的高斯先驗(yàn)。對于WLNM,文獻(xiàn)[12]中的原始設(shè)置用于模型訓(xùn)練,其中,負(fù)樣本是正鏈接的兩倍,并且對不同的封閉子圖大小10和20都進(jìn)行了評估,分別表示為WLAN10和WLAN20。對于SEAL,使用推薦的設(shè)置。批大小為50,排序池的k為0.6,模型自動選擇包圍子圖的躍點(diǎn)。用于檢查驗(yàn)證集性能的早期停止策略用于訓(xùn)練所有嵌入和神經(jīng)網(wǎng)絡(luò)模型。

提出模型的詳細(xì)參數(shù)設(shè)置如下:對于NAN模型,嵌入大小為64,潛在空間的數(shù)量為8,每個空間的尺寸大小為8,因此,總隱藏大小也為64,即8×8。對于負(fù)樣本生成器,嵌入大小和隱藏大小均為64。對于鑒別器和生成器,將非線性激活函數(shù)σ(·)選擇為指數(shù)線性單位。本文采用參數(shù)學(xué)習(xí)率為0.001的Adam更新規(guī)則。為防止過度擬合,對隱含單元和注意力應(yīng)用了主動丟失技術(shù),其權(quán)重為0.000 5的保持概率為0.8且L2正則化,還使用了相同的提前停止策略。

3.4 評估結(jié)果

實(shí)驗(yàn)結(jié)果如表2所示,為了驗(yàn)證改進(jìn)的重要性,本文對提出模型與比較方法中最佳競爭對手之間的五倍交叉結(jié)果進(jìn)行了配對t檢驗(yàn)。

從實(shí)驗(yàn)結(jié)果,總結(jié)出以下發(fā)現(xiàn):提出的模型實(shí)現(xiàn)了最優(yōu)的預(yù)測性能。本文發(fā)現(xiàn)提出的NAN模型在十個數(shù)據(jù)集上顯著優(yōu)于所有比較方法,并且與其余兩個數(shù)據(jù)集上的最佳方法相比仍具有很大的競爭力。這有力地證明了所提出的模型對于各種類型的網(wǎng)絡(luò)上的鏈路預(yù)測普遍有效。

神經(jīng)網(wǎng)絡(luò)的廣泛應(yīng)用:與傳統(tǒng)的啟發(fā)式方法和節(jié)點(diǎn)嵌入方法相比,基于神經(jīng)網(wǎng)絡(luò)的模型在不同網(wǎng)絡(luò)之間穩(wěn)定地展示了良好的性能。這表明神經(jīng)網(wǎng)絡(luò)的引入能夠有效提升預(yù)測性能。

NAN對鄰域編碼更有效:GAE、VGAE、WLNM和SEAL使用不同的方法進(jìn)行鄰域編碼。與這些方法相比,NAN的性能始終更好。這歸因于引入的注意力機(jī)制,該機(jī)制全面捕獲了結(jié)構(gòu)重要性并提取了鄰域的普遍潛在特征。

跨鄰域關(guān)注對預(yù)測性能提升有利:可以發(fā)現(xiàn)CNAN在大多數(shù)數(shù)據(jù)集上始終優(yōu)于SNAN。與SNAN相比,CNAN通過交叉注意力直接捕獲結(jié)構(gòu)交互,從而在注意力層探索了更明確的鏈接線索。V-E4部分中的可視化示例也驗(yàn)證了交叉注意力的良好區(qū)分能力。

3.5 NAN的分析

多空間鄰域的有效性注意:為了證明所提出的MSNA的有效性,本文針對以下鄰域編碼方法進(jìn)行了對比實(shí)驗(yàn)。

AVG:此編碼方法僅通過取鄰居所有嵌入的平均值來構(gòu)造鄰域嵌入。

單空間注意(Single Space Attention,SSA):這是一種通用的SSA機(jī)制,在對節(jié)點(diǎn)特征進(jìn)行線性映射后,在單個潛在空間中計算注意力,其中維是MSNA中多個空格的總維。

圖形注意力(Graph Attention,GA):GA是一種針對圖形的最新注意力機(jī)制,輸入是節(jié)點(diǎn)特征的線性映射。

由于上述競爭方法不能直接用于鏈接預(yù)測,因此將它們?nèi)糠湃胩岢龅目蚣躍NAN中進(jìn)行性能評估。根據(jù)表3中的結(jié)果,可以發(fā)現(xiàn)集中注意力收集鄰域的信息是有利的,這可以通過所有基于注意力的方法在大多數(shù)情況下勝過AVG方法來證明。相鄰節(jié)點(diǎn)在鄰域關(guān)系中具有不同的重要性,注意機(jī)制可以從結(jié)構(gòu)信息中捕獲這種重要性,從而提取出更好的鄰域特征。在MSNA中,注意力集中在多個潛在空間中,這將從不同潛在方面構(gòu)建更全面的上下文特征。此外,角色專用連接層的設(shè)計使MSNA能夠深入探索鄰域的非線性結(jié)構(gòu)關(guān)系和特征。提出的MSNA勝過其他的注意機(jī)制。

表3 性能評估對比表

參數(shù)敏感性:提出的注意力機(jī)制能夠?qū)Σ煌A數(shù)的鄰域進(jìn)行編碼,因此,首先證明鄰域范圍的影響。如圖2所示,比較了從一階到五階的五個范圍大小,可以發(fā)現(xiàn)一階鄰域信息對于大多數(shù)數(shù)據(jù)集的鏈接預(yù)測而言更為重要,然而HTC、CORA、CITESEER和UPG的四個稀疏數(shù)據(jù)集是例外?？紤]使用高階數(shù)鄰域有助于減輕稀疏性,并在這四個數(shù)據(jù)集上獲得較大的改進(jìn)。同時,即使引入了更多無關(guān)的鄰域信息,所提出的模型也可以獲得相對魯棒的性能。這歸因于注意力機(jī)制,可以選擇性地編碼更重要的鄰域。

(a) 在鄰域范圍內(nèi)的表現(xiàn)

進(jìn)一步研究了潛在空間的數(shù)量和維數(shù)大小如何影響模型。以三個數(shù)據(jù)集為例,而其他數(shù)據(jù)集具有相似的結(jié)果。如圖3(a)所示,更多的潛在空間可以提高模型的預(yù)測能力。但是,當(dāng)數(shù)量達(dá)到一定水平時,改進(jìn)效果會變?nèi)?。尺寸大小具有相似的特征。如圖3(b)所示,當(dāng)維數(shù)變大時,模型的性能會更好,但當(dāng)維數(shù)超過一定比例時,模型性能的改善效果會越來越弱。增大潛在空間的數(shù)量或尺寸大小不可避免地會增加計算復(fù)雜性。因此,在實(shí)踐中應(yīng)該綜合考慮性能和效率的關(guān)系。

(a) 稀疏網(wǎng)絡(luò)CITESEER

性能稀疏度:進(jìn)一步分析所提出模型的性能稀疏性。以最稀疏的網(wǎng)絡(luò)之一CITESEER和最密集的網(wǎng)絡(luò)PLB之一為例。如圖3所示,當(dāng)剩余邊緣減少時,即稀疏度增加,兩個模型的AUC分?jǐn)?shù)在兩個網(wǎng)絡(luò)上都會降低。由于PLB的稀疏性較低,即使刪除了50%的邊緣,PLB的性能也相對穩(wěn)定。另外,CNAN的性能始終優(yōu)于SNAN,而當(dāng)網(wǎng)絡(luò)變得稀疏時,改進(jìn)的幅度更加明顯。這可以歸因于CNAN的交叉關(guān)注,每個節(jié)點(diǎn)在稀疏網(wǎng)絡(luò)中只有很少的鄰域,因此,SNAN僅從自鄰域捕獲非常有限的鏈接線索,而CNAN可以利用來自鄰域的更多信息,從而緩解這種情況。

注意力可視化:如圖4所示,將KHN中的學(xué)習(xí)注意力示例可視化,在該示例中,將潛在空間的數(shù)量設(shè)置為4。第一幅圖像顯示了節(jié)點(diǎn)240的自鄰關(guān)注。第二個繪制正樣本的交叉注意力,即節(jié)點(diǎn)1 504對節(jié)點(diǎn)240的鄰域關(guān)注,其中節(jié)點(diǎn)1 504與節(jié)點(diǎn)240鏈接。第三幅圖是負(fù)樣本的交叉注意力,即節(jié)點(diǎn)1 390未與節(jié)點(diǎn)240鏈接,顏色越深,表示關(guān)注度越高。

可以發(fā)現(xiàn),在多個潛在空間中,對鄰域的學(xué)習(xí)注意力有所不同。進(jìn)一步說明提出的注意力機(jī)制從不同的潛在方面抓住了結(jié)構(gòu)的重要性,而每個潛在方面都有不同的重點(diǎn)。另外,交叉注意力具有很好的區(qū)分性。如果這對節(jié)點(diǎn)是鏈接的,則學(xué)習(xí)的注意力和自我注意就很好地匹配,如圖4(a)和圖4(b)所示,但是如果節(jié)點(diǎn)沒有鏈接,則交叉注意和自我注意之間會有很大差異。如圖4(a)和圖4(c)所示,具有交叉注意力的交互可以進(jìn)一步提高預(yù)測能力。

3.6 對抗學(xué)習(xí)分析

為了驗(yàn)證對抗學(xué)習(xí)的有效性和魯棒性,在提出的對抗學(xué)習(xí)和隨機(jī)否定采樣策略之間進(jìn)行了比較實(shí)驗(yàn)。由于空間有限,在該消融研究中選擇了兩個最困難的網(wǎng)絡(luò),即CEG和UPG。實(shí)驗(yàn)進(jìn)行了十次,每一次都通過五重交叉驗(yàn)證設(shè)置進(jìn)行評估。為了更清楚地可視化性能變化,在x軸的中間繪制了最佳結(jié)果,而在兩側(cè)則繪制了較差的結(jié)果。如圖5所示,在兩個數(shù)據(jù)集上,對抗學(xué)習(xí)的平均性能始終優(yōu)于隨機(jī)抽樣。另外,對抗學(xué)習(xí)的方差比兩個數(shù)據(jù)集上的隨機(jī)抽樣都要低約50%。盡管隨機(jī)采樣有機(jī)會獲得良好的性能,但它不是很穩(wěn)定。對抗學(xué)習(xí)通過在學(xué)習(xí)過程中不斷生成高質(zhì)量的否定樣本來顯著提高NAN模型的有效性和魯棒性。

(a) CEG數(shù)據(jù)集

此外,研究了對抗學(xué)習(xí)和隨機(jī)抽樣之間的學(xué)習(xí)曲線差異。以CEG數(shù)據(jù)集為例。如圖6所示,隨機(jī)采樣在50個周期后實(shí)現(xiàn)了相對較低的損耗,但是在此之后性能幾乎沒有提高。正如上文所提到的,經(jīng)過一定時間的訓(xùn)練后,大多數(shù)負(fù)面樣本都是學(xué)得很好的,隨機(jī)樣本可能總是提取沒有信息或較少信息的樣本,因此,性能可能會停滯不前。與隨機(jī)抽樣相比,在50個周期后對抗學(xué)習(xí)的損失明顯更高,這意味著對抗學(xué)習(xí)會產(chǎn)生更多的信息性負(fù)面樣本。因此,停滯的可能性較小,并且進(jìn)一步提高了性能。

(a) 損耗曲線

4 結(jié) 語

針對傳統(tǒng)鏈路預(yù)測模型無法充分挖掘鄰域特征信息,且模型的泛化能力不強(qiáng)等缺點(diǎn),提出了一種基于對抗學(xué)習(xí)鄰域注意網(wǎng)絡(luò)的鏈路預(yù)測。通過在12個基準(zhǔn)數(shù)據(jù)集上評估所提出方法的性能可以得出如下結(jié)論:

(1) 提出的模型對于各種類型的網(wǎng)絡(luò)上的鏈路預(yù)測普遍有效,且能夠保證較好的預(yù)測性能。

(2) 引入的注意力機(jī)制,該機(jī)制全面捕獲了結(jié)構(gòu)重要性并提取了鄰域的普遍潛在特征,對鄰域編碼更有效。

(3) 通過交叉注意力直接捕獲結(jié)構(gòu)交互,從而在注意力層探索了更明確的鏈接線索,能夠有效地提升鏈路預(yù)測性能。

(4) 更多的潛在空間可以提高模型的預(yù)測能力。但是,當(dāng)數(shù)量達(dá)到一定水平時,改進(jìn)效果會變?nèi)?當(dāng)維數(shù)變大時,模型的性能會更好,但當(dāng)維數(shù)超過一定比例時,模型性能的改善效果會越來越弱。