基于圖表示深度學(xué)習(xí)的異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測研究

趙宇紅,吳 昊

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院,內(nèi)蒙古 包頭 014010)

1 引 言

在現(xiàn)實(shí)世界中,網(wǎng)絡(luò)[1]可以很好地描述每個(gè)實(shí)體以及每個(gè)實(shí)體之間的關(guān)系,其中實(shí)體對應(yīng)網(wǎng)絡(luò)中的節(jié)點(diǎn),邊則表示兩個(gè)實(shí)體之間的關(guān)系.現(xiàn)實(shí)生活的網(wǎng)絡(luò)一般都是復(fù)雜網(wǎng)絡(luò),結(jié)構(gòu)復(fù)雜且數(shù)據(jù)豐富,從中挖掘和分析得到有價(jià)值的信息引發(fā)了學(xué)者的廣泛關(guān)注.鏈路預(yù)測[2]是網(wǎng)絡(luò)研究的中比較有挑戰(zhàn)的一個(gè)任務(wù),它主要是對網(wǎng)絡(luò)中的丟失信息或者潛藏信息進(jìn)行預(yù)測,從中挖掘出更有價(jià)值的信息為現(xiàn)實(shí)世界所應(yīng)用.

鏈路預(yù)測是一種應(yīng)用于復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)化分析技術(shù),它的目標(biāo)主要是通過對網(wǎng)絡(luò)結(jié)構(gòu)以及節(jié)點(diǎn)之間的相互關(guān)系進(jìn)行分析,從而預(yù)測節(jié)點(diǎn)之間是否存在連接的可能性,由此應(yīng)用到如今的生活當(dāng)中.例如,當(dāng)今社交媒體軟件的好友推薦[3],根據(jù)用戶的喜好和行為,推薦用戶相同愛好的好友;在電子商務(wù)[4]中,根據(jù)對用戶的行為和購買喜好進(jìn)行分析,篩選最符合用戶的商品進(jìn)行推薦,實(shí)現(xiàn)商品的推廣,促進(jìn)消費(fèi).

隨著計(jì)算機(jī)技術(shù)的發(fā)展,深度學(xué)習(xí)走入人們的視野,并在自然語言處理,圖像處理等方面取得了巨大的突破,鏈路預(yù)測從中獲得一定的啟發(fā),深度學(xué)習(xí)也開始成為鏈路預(yù)測的一大研究熱點(diǎn).其中圖表示學(xué)習(xí)[5]可以將圖數(shù)據(jù)轉(zhuǎn)化成低維稠密的向量化表示,同時(shí)確保圖數(shù)據(jù)的某些性質(zhì)在向量空間中也能夠得到對應(yīng),并且圖數(shù)據(jù)的表示可以包含豐富的語義信息,可以為鏈路預(yù)測提供更為優(yōu)秀的輸入特征.

現(xiàn)今國內(nèi)針對大多數(shù)鏈路預(yù)測的研究都是針對單一網(wǎng)絡(luò)或者同質(zhì)網(wǎng)絡(luò),但是隨著異質(zhì)網(wǎng)絡(luò)[6]的發(fā)展,異質(zhì)網(wǎng)絡(luò)中包含的節(jié)點(diǎn)和鏈接更加綜合全面,使得異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測成為了一個(gè)重要研究方向.

根據(jù)上面的論述,本文提出了一種圖表示學(xué)習(xí)下的異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測,本法的方法大致如下:

1)根據(jù)異質(zhì)信息網(wǎng)絡(luò)構(gòu)建一個(gè)多通道網(wǎng)絡(luò)[7],其中每一個(gè)通道表示一種元路徑下的子網(wǎng)絡(luò),每個(gè)子網(wǎng)絡(luò)都是同質(zhì)網(wǎng)絡(luò),每一個(gè)路徑代表著不同的語義信息,然后可以對每一個(gè)通道進(jìn)行圖卷積操作.

2)傳統(tǒng)的GCN(Graph Convolutional Network)[8]只能學(xué)習(xí)淺層的網(wǎng)絡(luò),為了學(xué)習(xí)深層次的關(guān)系特征,于是本文使用了GraphInception模型[9],該模型改進(jìn)了傳統(tǒng)的inception模型,使其可以處理圖數(shù)據(jù).GraphInception模型由不同規(guī)格的卷積核組成,并且通過多層堆疊,構(gòu)造了從簡單到復(fù)雜的關(guān)系特征的層次結(jié)構(gòu).由此,本文可以使用該方法,對上文的多通道網(wǎng)絡(luò)進(jìn)行深層次的關(guān)系特征提取,得到更加全面準(zhǔn)確的關(guān)系特征向量.

3)通過計(jì)算Hadamard距離處理關(guān)系特征向量來表示邊向量,并通過訓(xùn)練邏輯回歸函數(shù)來評估邊存在的概率,最終完成鏈路預(yù)測任務(wù).

2 相關(guān)知識介紹

2.1 圖表示學(xué)習(xí)

網(wǎng)絡(luò)表示學(xué)習(xí)的主要目標(biāo)是學(xué)習(xí)網(wǎng)絡(luò)頂點(diǎn)的潛在低維表示,同時(shí)保留網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、頂點(diǎn)內(nèi)容和其他輔助信息,在學(xué)習(xí)新的頂點(diǎn)表示之后,通過將傳統(tǒng)的基于向量的機(jī)器學(xué)習(xí)算法應(yīng)用到新的表示空間,可以容易且有效地執(zhí)行網(wǎng)絡(luò)分析任務(wù).其在節(jié)點(diǎn)分類[10],鏈路預(yù)測等任務(wù)中取得了不錯(cuò)的進(jìn)展.網(wǎng)絡(luò)可通過圖進(jìn)行建模,但通常都是高維的,難以處理,圖嵌入可以作為一種降維的技術(shù),通過構(gòu)造一個(gè)D維的空間,將圖的節(jié)點(diǎn)嵌入到d(d<

本文使用的就是第3種方法,通過一種高效的圖卷積網(wǎng)絡(luò)(GCN)學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示,然后將向量表示應(yīng)用于鏈路預(yù)測中.

2.2 相關(guān)指標(biāo)介紹

傳統(tǒng)的鏈路預(yù)測的度量方法大部分是使用基于相似性的方法,這些方法通過使用圖的結(jié)構(gòu)屬性在節(jié)點(diǎn)對(vx,vy)之間度量相似性分?jǐn)?shù)S(vx,vy)來評估產(chǎn)生鏈接的可能性,主要有如下方法:

2.2.1 基于局部信息的相似性指標(biāo)

PA(Preferential Attachment)指標(biāo)[11]只考慮到節(jié)點(diǎn)度數(shù)的影響,如果兩個(gè)節(jié)點(diǎn)度數(shù)越高,則兩個(gè)節(jié)點(diǎn)之間的相似度越大.在某些特定的網(wǎng)絡(luò)中能取得很好的預(yù)測效果.如在路由網(wǎng)絡(luò)中,PA 指標(biāo)的預(yù)測效果都明顯高于其他指標(biāo),其計(jì)算公式如公式(1)所示:

S(vx,vy)=kxky

(1)

其中,kx表示節(jié)點(diǎn)vx的度數(shù).

2.2.2 基于路徑的相似性指標(biāo)

1)LP(Local Path)局部路徑指標(biāo)[12],該指標(biāo)是對于CN(共同鄰居)指標(biāo)的改進(jìn),主要體現(xiàn)在其考慮到節(jié)點(diǎn)的2階,3階鄰居的貢獻(xiàn).由于2階鄰居更為重要,該指標(biāo)使用了可調(diào)參數(shù)α控制3階路徑,其定義如公式(2)所示:

(2)

2)Katz指標(biāo)[13]考慮的是兩節(jié)點(diǎn)之間全部路徑,由于短路徑需要更多的權(quán)重,于是Katz指標(biāo)使用了權(quán)重衰減因子β,當(dāng)β十分小的時(shí)候Katz指標(biāo)就和CN指標(biāo)表現(xiàn)得差不多.其定義如公式(3)所示:

S=βA+βA2+βA3+…

(3)

2.2.3 基于隨機(jī)游走的相似性指標(biāo)

1)LRW(Local Random Walk)局部隨機(jī)游走指標(biāo)[14],該指標(biāo)為了減少了計(jì)算復(fù)雜度,使用了限制隨機(jī)游走過程中步長大小的方法,其適用于規(guī)模較大、節(jié)點(diǎn)稀疏的網(wǎng)絡(luò).其定義如公式(4)所示:

(4)

其中pvi,vj(t)表示從節(jié)點(diǎn)vi出發(fā)經(jīng)過t步之后到達(dá)節(jié)點(diǎn)vj的概率,E表示網(wǎng)絡(luò)節(jié)點(diǎn)的連邊集合,k表示節(jié)點(diǎn)的度.

2)SRW(Super-posed Random Walk)疊加隨機(jī)游走指標(biāo)[14],它在LRW的基礎(chǔ)上考慮了目標(biāo)節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)連邊的可能性,在隨機(jī)游走過程中將游走者每一步的概率都計(jì)算進(jìn)去從而得到疊加的局部隨機(jī)游走指標(biāo).其定義如公式(5)所示:

(5)

3 MDGCN模型

3.1 異質(zhì)信息網(wǎng)絡(luò)的定義

異質(zhì)信息網(wǎng)絡(luò)是信息網(wǎng)絡(luò)的一種,它包含了更豐富的語義信息(節(jié)點(diǎn)或邊具有多種類型).可以將其定義為G=(V,E),其中V代表著節(jié)點(diǎn)的集合,E代表節(jié)點(diǎn)之間邊的集合,同時(shí)存在一個(gè)節(jié)點(diǎn)類型的映射函數(shù)φ:V→A和一個(gè)變類型映射函數(shù)Ψ:E→R,并且要求節(jié)點(diǎn)類型|A|>1或者邊類型|R|>1.

3.2 MDGCN模型的基本思想

本文提出的MDGCN(Multichannel Deep Graph Convolutional Network)模型主要是通過將異質(zhì)信息網(wǎng)絡(luò)進(jìn)行多通道劃分,接著對于每個(gè)通道進(jìn)行圖卷積操作,最終獲得節(jié)點(diǎn)的關(guān)系特征用于下游任務(wù):鏈路預(yù)測.圖卷積過程使用graph inception模型,從而能夠進(jìn)行深層次的關(guān)系特征獲取,解決傳統(tǒng)GCN只能學(xué)習(xí)淺層網(wǎng)絡(luò)的問題.該算法框架如圖1所示.

圖1 MDGCN模型的過程Fig.1 Process of MDGCN model

3.3 構(gòu)造多通道網(wǎng)絡(luò)

異質(zhì)網(wǎng)絡(luò)擁有豐富的節(jié)點(diǎn)類型,而不同的節(jié)點(diǎn)類型之間也存在著差異,因此網(wǎng)絡(luò)上的卷積運(yùn)算變得難以解決.元路徑是異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)關(guān)聯(lián)的路徑,能豐富的表達(dá)一類節(jié)點(diǎn)中節(jié)點(diǎn)之間的語義信息,不同元路徑表達(dá)了不同的含義和不同的鏈接網(wǎng)絡(luò).于是本文使用了多通道網(wǎng)絡(luò),以元路徑對異質(zhì)網(wǎng)絡(luò)進(jìn)行劃分,劃分之后的每一個(gè)通道都是由目標(biāo)類型節(jié)點(diǎn)組成的同質(zhì)網(wǎng)絡(luò),代表著不同語義,從而可以獲得節(jié)點(diǎn)不同語義下的鏈接關(guān)系.

本文首先通過在有限長度內(nèi)用廣度優(yōu)先算法獲取異質(zhì)網(wǎng)絡(luò)中由目標(biāo)類型節(jié)點(diǎn)組成的元路徑(每條元路徑代表著節(jié)點(diǎn)之間的唯一關(guān)系),從而得到多個(gè)同質(zhì)網(wǎng)絡(luò)作為多通道網(wǎng)絡(luò)的輸入.

元路徑定義如式(6)所示:

S={P1,…,Pn}

(6)

其中,n表示元路徑的數(shù)目.

從而可以將多通道網(wǎng)絡(luò)定義為:

(7)

其中V1代表目標(biāo)類型節(jié)點(diǎn)集合,e1l代表V1之間的關(guān)系(即V1之間一種類型關(guān)系邊的集合),它們通過元路徑Pl連接.

3.4 MDGCN算法

3.4.1 圖卷積的介紹

傳統(tǒng)的圖卷積模型只適用于同質(zhì)網(wǎng)絡(luò),本文將其擴(kuò)展到異質(zhì)網(wǎng)絡(luò),從而可以通過非目標(biāo)類型節(jié)點(diǎn)來細(xì)化目標(biāo)類型節(jié)點(diǎn)的關(guān)系特征.同質(zhì)網(wǎng)絡(luò)Ghomo上的卷積可以定義為特征向量X與對稱歸一化鄰接矩陣P(轉(zhuǎn)移概率矩陣)上的濾波器gθ的乘積,如式(8)所示:

gθ?GhomoX=gθ(PX)=gθ(U∧UT)X=Ugθ(∧)UTX

(8)

為了選擇給定節(jié)點(diǎn)的局部鄰居,本文將gθ定義為多項(xiàng)式參數(shù)濾波器:

(9)

其中參數(shù)θ是多項(xiàng)式系數(shù)的向量.

所以最終可以得出同質(zhì)網(wǎng)絡(luò)Ghomo上的卷積公式:

(10)

這個(gè)表達(dá)式表示的是K階鄰域,因?yàn)樗寝D(zhuǎn)移概率矩陣的第K階多項(xiàng)式.

(11)

(12)

其中,Θlk=(1=1,…,n)為濾波器參數(shù)矩陣,向量x的函數(shù)r定義為r(x)=(r(x1),…,r(xm)),函數(shù)中r(xi)=max(0,xi)是Relu函數(shù),H的第i行向量表示節(jié)點(diǎn)v1i學(xué)習(xí)的關(guān)系特征.

與傳統(tǒng)的圖卷積模型相比,本文的模型學(xué)習(xí)的是關(guān)系特征,而不是內(nèi)容特征,因此本文的模型不需要考慮節(jié)點(diǎn)本身的屬性,即K=0的情況.并且,本文的模型可以應(yīng)用于異質(zhì)網(wǎng)絡(luò),而傳統(tǒng)的圖卷積模型不能.

3.4.2 深層次的圖卷積方法

一個(gè)異質(zhì)網(wǎng)絡(luò)通常涉及一個(gè)多關(guān)系層次結(jié)構(gòu),然而,公式(12)只捕獲每個(gè)子網(wǎng)中的潛在關(guān)系.也就是說,它既不處理不同類型節(jié)點(diǎn)之間的復(fù)雜交互,也不捕捉不同子網(wǎng)中潛在關(guān)系之間的不兼容性.在圖1中,受zhang等人工作[9]的啟發(fā),本文設(shè)計(jì)了一種基于Graph Inception模型的關(guān)系特征學(xué)習(xí)方法,以通過多層卷積從現(xiàn)有的多關(guān)系層次生成深層關(guān)系特征.

傳統(tǒng)的Inception模型只能處理歐幾里得數(shù)據(jù),不能夠運(yùn)用在一般的圖結(jié)構(gòu)中,例如:網(wǎng)絡(luò)數(shù)據(jù),因此為了更有效得學(xué)習(xí)網(wǎng)絡(luò)中的關(guān)系特征,本文使用了Graph Inception模型,該模型框架如圖2所示.

圖2 Graph Inception模型框架圖Fig.2 Graph Inception model frame diagram

如圖2所示,Graph Inception結(jié)合不同大小的卷積核提取關(guān)系特征,以通過多層卷積從現(xiàn)有的多關(guān)系層次生成深層關(guān)系特征.其中,本文為每一層上的每個(gè)子網(wǎng)取兩個(gè)卷積核,并將核大小分別設(shè)置為1和2,則Graph Inception模型的第t層的定義如式(13)所示:

(13)

(14)

于是通過計(jì)算可以得到最終目標(biāo)類型節(jié)點(diǎn)的關(guān)系特征如式(15)所示:

(15)

接著,通過堆疊多個(gè)Graph Inception層來提取復(fù)雜的關(guān)系特征,并通過調(diào)整層數(shù)來控制學(xué)習(xí)到的關(guān)系特征的復(fù)雜性.

與公式(12)相比Graph Inception模型擁有3大優(yōu)點(diǎn):

2)當(dāng)網(wǎng)絡(luò)很深的時(shí)候該方法所需要的參數(shù)更少.

3)該模型能夠緩解具有非常寬的節(jié)點(diǎn)度分布的圖的局部鄰域結(jié)構(gòu)上的過擬合問題.

3.5 訓(xùn)練模型

在學(xué)習(xí)了所有目標(biāo)類型節(jié)點(diǎn)的關(guān)系特征之后,本文通過隨機(jī)選取目標(biāo)類型節(jié)點(diǎn)V1中的任意兩個(gè)節(jié)點(diǎn)V1i和V1j,然后經(jīng)過計(jì)算Hadamard距離來表示邊向量,并通過訓(xùn)練邏輯回歸函數(shù)來評估邊存在概率.邊向量的定義如式(16)所示:

eij=Hi⊙Hj

(16)

(17)

得到兩節(jié)點(diǎn)之間連接的概率之后,本文可以通過邏輯回歸函數(shù)計(jì)算其損失,如公式(18)所示:

(18)

其中,yij表示在元路徑S下V1i和V1j是否鏈接,若連接yij=1,否則yij=0;N表示目標(biāo)類型節(jié)點(diǎn)V1中兩節(jié)點(diǎn)之間可能存在邊的數(shù)目.

4 實(shí)驗(yàn)及結(jié)果分析

本文選取了3個(gè)擁有著不同節(jié)點(diǎn)類型數(shù)目的數(shù)據(jù)集,通過MDGCN模型構(gòu)造多通道網(wǎng)絡(luò)分解異質(zhì)網(wǎng)絡(luò),使用GCN進(jìn)行學(xué)習(xí)和訓(xùn)練,從而獲取目標(biāo)類型節(jié)點(diǎn)的關(guān)系特征向量,最終通過邏輯回歸完成鏈路預(yù)測.同時(shí),為了驗(yàn)證本文方法的可行性,本文選取了一些傳統(tǒng)的鏈路預(yù)測方法:PA,LP,Katz,LRW,SRW進(jìn)行了對比實(shí)驗(yàn)分析.

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

為了驗(yàn)證本文模型的有效性,本文選取了3個(gè)真實(shí)的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn):

·Cora數(shù)據(jù)集[15]:該數(shù)據(jù)集是一種典型的論文引用網(wǎng)絡(luò),它具有2種類型的節(jié)點(diǎn),即論文和作者,以及兩種類型的鏈接:作者和作者鏈接,作者和論文鏈接.在實(shí)驗(yàn)中本文將論文視為目標(biāo)類型節(jié)點(diǎn),論文標(biāo)題的獨(dú)熱向量作為每個(gè)論文的內(nèi)容特征.

·DBLP數(shù)據(jù)集[16]:該數(shù)據(jù)集是一種書目信息網(wǎng)絡(luò),它具有3種類型的節(jié)點(diǎn),即會(huì)議,論文和作者,以及兩種類型的鏈接:作者和論文的鏈接,論文和會(huì)議的鏈接.在實(shí)驗(yàn)中本文將作者作為目標(biāo)類型節(jié)點(diǎn),作者發(fā)表的論文標(biāo)題的獨(dú)熱向量作為目標(biāo)類型節(jié)點(diǎn)的內(nèi)容特征.

·IMDB數(shù)據(jù)集[17]:該數(shù)據(jù)集是一個(gè)電影數(shù)據(jù)集,其包含了4種類型的節(jié)點(diǎn),即電影,導(dǎo)演,演員和女演員,其中有3種類型的鏈接:電影與導(dǎo)演的鏈接.電影與演員的鏈接,電影和女演員的鏈接.在實(shí)驗(yàn)中本文將電影作為目標(biāo)類型節(jié)點(diǎn),一個(gè)關(guān)于電影的所有情節(jié)摘要的獨(dú)熱向量作為目標(biāo)類型節(jié)點(diǎn)的內(nèi)容特征.

3個(gè)數(shù)據(jù)集參數(shù)如表1所示.

表1 數(shù)據(jù)集參數(shù)Table 1 Data set parameter

4.2 評價(jià)指標(biāo)

AUC指標(biāo)[18]作為鏈路預(yù)測中的常用方法,它能夠從整體上衡量鏈路預(yù)測結(jié)果的準(zhǔn)確性,在衡量一個(gè)算法好壞的時(shí)候,本文需要將數(shù)據(jù)集劃分為訓(xùn)練集和測試集,則AUC可以被解釋為從測試集中隨機(jī)抽取一條鏈接的預(yù)測值比隨機(jī)從不存在鏈接中選擇的一條鏈接的概率值大的可能性.也就是說,AUC是將從測試集中選取的鏈接的分?jǐn)?shù)與隨機(jī)從不存在鏈接中選擇的鏈接的分?jǐn)?shù)相比較,當(dāng)前者分?jǐn)?shù)大于后者則加1分,兩者相等加0.5分,否則不加分.之后進(jìn)行獨(dú)立隨機(jī)比較n次,記加1分的次數(shù)為n′,加0.5分的次數(shù)為n″次,則AUC的計(jì)算公式定義為:

(19)

由此可見,如果所有分?jǐn)?shù)都是隨機(jī)產(chǎn)生的AUC=0.5,所以AUC比0.5大得越多算法越精確.

Precision指標(biāo)[19]相比于AUC從宏觀的角度評價(jià)算法的準(zhǔn)確性,它只考慮了前L位是否預(yù)測準(zhǔn)確,也就是將不存在的邊根據(jù)所對應(yīng)的概率值進(jìn)行排序,排序后選擇前L個(gè)(本文的L=100)與測試集進(jìn)行比對,得出Precision的公式:

(20)

其中N表示L中屬于測試集的數(shù)目.

4.3 實(shí)驗(yàn)結(jié)果與分析

本文將實(shí)驗(yàn)數(shù)據(jù)隨機(jī)劃分為訓(xùn)練集和測試集,劃分比例采取9:1的比例,之后進(jìn)行100次獨(dú)立實(shí)驗(yàn),對于每次獨(dú)立實(shí)驗(yàn)都要求其 AUC值和Precision值,最終將所得到的所有AUC值和Precision值進(jìn)行平均值計(jì)算作為最終的實(shí)驗(yàn)結(jié)果.其中對于每一次獨(dú)立實(shí)驗(yàn)都要進(jìn)行10000次的隨機(jī)抽樣比較預(yù)測邊與不存在邊的分?jǐn)?shù)計(jì)算AUC和Precision.

4.3.1 參數(shù)分析

本節(jié)分析MDGCN模型中的參數(shù),包括:圖卷積過程中卷積核的大小k,節(jié)點(diǎn)向量表示的向量維度d和Graph Inception模型堆疊的層數(shù)t.其中卷積核的大小影響著感受野(receptive field),一般情況下,隨著卷積核大小的增加,感受野會(huì)隨之變大,看到的網(wǎng)絡(luò)信息就會(huì)越多,所獲得的全局特征越好.雖說如此,但是更大的卷積核會(huì)影響到計(jì)算復(fù)雜度,導(dǎo)致模型深度增加的計(jì)算難度提升,計(jì)算性能嚴(yán)重下降;節(jié)點(diǎn)向量表示的維度則用來刻畫節(jié)點(diǎn)向量映射空間的復(fù)雜程度;層數(shù)t的數(shù)量影響著深層次節(jié)點(diǎn)關(guān)系特征的獲取程度.在Cora,DBLP,IMDB 3個(gè)數(shù)據(jù)集下各個(gè)參數(shù)對AUC的影響,如圖3所示.

圖3 MDGCN模型的參數(shù)分析Fig.3 Parameter analysis of MDGCN model

本文使用了控制變量法對3個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)向量維度、卷積核大小以及堆疊層數(shù)對預(yù)測結(jié)果AUC的影響進(jìn)行了測試.其中,默認(rèn)kernel size=4,number of layers=1,Dimension=100,對于卷積核大小與堆疊的層數(shù)的調(diào)節(jié)步長都設(shè)置為1,節(jié)點(diǎn)向量維度則以20為調(diào)節(jié)步長.

從圖3中可以看出,在控制其他參數(shù)大小不變的情況下,隨著卷積核的大小不斷變大,AUC都呈增加趨勢,在DBLP和IMDB中卷積核大小在3的時(shí)候得到了最優(yōu)表現(xiàn),Cora數(shù)據(jù)集中雖然還在增長,但是不是很明顯,為了減少計(jì)算復(fù)雜度選取大小4左右的卷積核就行.對于關(guān)系更加復(fù)雜的DBLP中堆疊層數(shù)的大小對AUC的影響也足夠明顯,但在關(guān)系相對簡單的Cora和IMDB中的效果不是很好.對于節(jié)點(diǎn)向量維度,不同維度對于AUC的影響波動(dòng)大小無明顯差異,波動(dòng)的范圍大概在0.03左右,整體效果都不錯(cuò).其中,Cora數(shù)據(jù)集在120～140之間,DBLP數(shù)據(jù)集在60～80之間,IMDB數(shù)據(jù)集在80～100之間達(dá)到最優(yōu)效果.

4.3.2 實(shí)驗(yàn)結(jié)果

本文使用PA,LP,Katz,LRW,SRW 5種指標(biāo)作為校準(zhǔn)方法與本文方法進(jìn)行對比,它們的對比結(jié)果如表2和表3所示.

表2 各方法在不同數(shù)據(jù)集下的AUC值Table 2 AUC values for each method in different data sets

表3 各方法在不同數(shù)據(jù)集下的Precision值Table 3 Precision for each method in different data sets

通過表2可知,對于節(jié)點(diǎn)類型和邊類型都較少的論文引用網(wǎng)絡(luò)Cora來說,各種方法的效果都不錯(cuò),LP、Katz、GCN都達(dá)到了0.9以上,PA,LRW,SRW也都達(dá)到了0.8以上.由于Cora中節(jié)點(diǎn)數(shù)目較多,但連邊數(shù)卻相對較少,所以考慮節(jié)點(diǎn)度的PA算法效果不是很理想.由于Cora網(wǎng)絡(luò)規(guī)模不是很大,Katz指標(biāo)取得了傳統(tǒng)算法中的最優(yōu)結(jié)果,本文的方法比其還擁有了3%的提升,由此可見本文方法有著更高的準(zhǔn)確率.

對于連邊類型數(shù)目與Cora相同,節(jié)點(diǎn)類型更多的書目信息網(wǎng)絡(luò)DBLP,傳統(tǒng)算法的AUC都有所下降.只考慮節(jié)點(diǎn)度的PA算法對網(wǎng)絡(luò)鏈路的預(yù)測只能得到0.6312,效果明顯欠佳.考慮高階節(jié)點(diǎn)信息的LP算法一定程度增加了網(wǎng)絡(luò)的局部連通性,準(zhǔn)確度有所提升.考慮全局路徑的Katz算法,相比于LP準(zhǔn)確度也有所提高.基于隨機(jī)游走的LRW,SRW方法更加適合該數(shù)據(jù)集,相比于其他傳統(tǒng)算法,這兩種算法的準(zhǔn)確度更高.相較于這些算法基于圖表示學(xué)習(xí)的GCN和MDGCN能同時(shí)考慮網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu)和多樣化的屬性類型,使得準(zhǔn)確度得到了一定的提升.其中MDGCN考慮了深層次的節(jié)點(diǎn)關(guān)系,相較于GCN還提高了13.02%.

在節(jié)點(diǎn)類型和連邊類型都比較多的IMDB網(wǎng)絡(luò)中,傳統(tǒng)的算法PA,LP,Katz,LRW,SRW方法表現(xiàn)都十分欠佳,AUC處于0.7以下.本文提出的方法能夠取得較好的預(yù)測結(jié)果,相比較于效果最好的傳統(tǒng)圖表示學(xué)習(xí)算法GCN有了1.96%的提高,對于傳統(tǒng)算法有了百分之十以上的提高.對于同樣使用圖表示學(xué)習(xí)的GCN算法,MDGCN通過多通道網(wǎng)絡(luò)考慮了網(wǎng)絡(luò)的異質(zhì)性和不同類型邊的語義信息,并在卷積過程中考慮了更深層次節(jié)點(diǎn)的關(guān)系,從而得出了更具有表現(xiàn)的節(jié)點(diǎn)關(guān)系特征向量,利用該向量得出的邊向量進(jìn)行邏輯回歸,從而得出了更加精確的結(jié)果.

AUC值雖然是鏈路預(yù)測中最為重要的指標(biāo),但是當(dāng)AUC之間相差不多的時(shí)候,Precision值有著關(guān)鍵的作用.在AUC值相差無幾的時(shí)候,Precision值越高,代表算法的準(zhǔn)確性越好.可以通過表3得知,本文的方法在3個(gè)數(shù)據(jù)集的表現(xiàn)依舊有較好的提升.

綜上所述,本文提出的MDGCN方法在不同節(jié)點(diǎn)類型數(shù)目和不同連邊類型數(shù)目的網(wǎng)絡(luò)中都可以表現(xiàn)出相對較好的預(yù)測精度.

5 總 結(jié)

本文研究了一種在異質(zhì)網(wǎng)絡(luò)中進(jìn)行鏈路預(yù)測的方法,即MDGCN模型,該方法提出一種使用多通道網(wǎng)絡(luò)分解異質(zhì)網(wǎng)絡(luò),用Graph Inception模型獲取節(jié)點(diǎn)關(guān)系特征,最終通過邏輯回歸進(jìn)行鏈路預(yù)測.此方法能夠高效處理圖數(shù)據(jù),使圖數(shù)據(jù)的某些性質(zhì)在向量空間體現(xiàn),從而得到豐富的節(jié)點(diǎn)信息和語義信息,讓向量能夠更加準(zhǔn)確得表示節(jié)點(diǎn).通過實(shí)驗(yàn)結(jié)果可以得出,MDGCN模型對Cora,DBLP和IMDB真實(shí)數(shù)據(jù)集均表現(xiàn)出良好的預(yù)測結(jié)果.

本文提出的方法是基于當(dāng)前狀態(tài)進(jìn)行預(yù)測,沒有考慮到時(shí)間因素對網(wǎng)絡(luò)的影響(即網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可能隨時(shí)間變化而發(fā)生改變).同時(shí),對于關(guān)系層次相對簡單的網(wǎng)絡(luò),本文方法通過堆疊層數(shù)效果反而不是很理想,需要進(jìn)一步得改進(jìn).所以,后續(xù)的研究將會(huì)著手于考慮通過時(shí)序網(wǎng)絡(luò)模型的引入,研究動(dòng)態(tài)網(wǎng)絡(luò)下的鏈路預(yù)測方法.