基于鄰域采樣的異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測算法*

劉 臣 謝寧靜 周立欣

（上海理工大學(xué)管理學(xué)院 上海 200093）

1 引言

圖作為一種常用的抽象數(shù)據(jù)結(jié)構(gòu)，包含著豐富的內(nèi)容信息和復(fù)雜的結(jié)構(gòu)信息?，F(xiàn)實(shí)世界中許多場景都可以用圖來表示，如知識(shí)圖譜［1］、開放學(xué)術(shù)網(wǎng)絡(luò)［2］、交通網(wǎng)絡(luò)［3］等。圖卷積網(wǎng)絡(luò)（Graph Convolution Network，GCN）在學(xué)習(xí)圖表示方面表現(xiàn)優(yōu)異，已經(jīng)受到各個(gè)領(lǐng)域的廣泛關(guān)注［4］。然而，隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)量爆炸式增長，導(dǎo)致圖的規(guī)模日益擴(kuò)大。傳統(tǒng)圖卷積模型在大規(guī)模圖上很難直接有效訓(xùn)練。因此，如何高效處理大規(guī)模圖成為一個(gè)急需解決的問題。

面對(duì)規(guī)模日益增長的圖數(shù)據(jù)，采樣成為提高模型訓(xùn)練速度，節(jié)約計(jì)算資源的常用方法。采樣方法根據(jù)特定規(guī)則選擇圖中的部分節(jié)點(diǎn)作為輸入樣本，從而適當(dāng)調(diào)整輸入數(shù)據(jù)的大小和構(gòu)成。采樣模塊通過靈活地構(gòu)建輸入模型中的數(shù)據(jù)，可以很好地緩解傳統(tǒng)圖卷積訓(xùn)練的鄰域爆炸問題。其中，鄰域爆炸是指圖卷積計(jì)算過程中鄰居節(jié)點(diǎn)數(shù)隨著卷積層深度的增加而呈指數(shù)增長。同時(shí)，采樣模塊避免圖卷積過程一直存儲(chǔ)并處理圖中每個(gè)節(jié)點(diǎn)的鄰居，保證了信息傳播的順利進(jìn)行，降低GCN訓(xùn)練的計(jì)算和存儲(chǔ)成本。

現(xiàn)有采樣方法主要用于同質(zhì)圖處理，按照采樣對(duì)象選擇的角度不同，可簡單分為基于節(jié)點(diǎn)采樣、基于分層采樣以及基于子圖采樣三類。Graph-SAGE［5］是一種典型的基于節(jié)點(diǎn)采樣方法，該方法通過對(duì)訓(xùn)練圖中每個(gè)節(jié)點(diǎn)的鄰居進(jìn)行固定數(shù)量的采樣，學(xué)習(xí)了一個(gè)利用鄰域采樣和聚合生成節(jié)點(diǎn)嵌入的歸納過程，達(dá)到了減少計(jì)算成本的目的。但該方法估計(jì)方式存在著偏差，并且收斂性無法保證。隨后，有學(xué)者通過添加某些獨(dú)特采樣機(jī)制提出了新的節(jié)點(diǎn)采樣方法。Ying等［6］通過模擬隨機(jī)行走過程遍歷節(jié)點(diǎn)，計(jì)算訪問計(jì)數(shù)，為每個(gè)節(jié)點(diǎn)選取最具影響力的鄰居。Dai等［7］提出通過添加交替采樣策略對(duì)單跳鄰居進(jìn)行采樣以更新嵌入和函數(shù)。VR-GCN［8］則通過方差減少技術(shù)將采樣鄰居的大小限制為任意小的數(shù)字，并利用歷史激活來近似嵌入，避免了遞歸計(jì)算。這些方法已經(jīng)取得了不錯(cuò)的效果，但除了SSE［7］方法外，其他方法仍然面臨著鄰居爆炸問題。

為了減輕節(jié)點(diǎn)采樣方法中鄰居節(jié)點(diǎn)數(shù)隨著層數(shù)增長呈指數(shù)擴(kuò)展帶來的昂貴計(jì)算，有學(xué)者提出分層采樣方法。分層采樣的思想是在一個(gè)抽樣步驟中對(duì)一定數(shù)量的節(jié)點(diǎn)進(jìn)行抽樣，避免鄰居爆炸并降低采樣過程的時(shí)間開銷?；诜謱硬蓸拥拇硇怨ぷ髦皇荈astGCN［9］，其采用蒙特卡洛方法，根據(jù)預(yù)先設(shè)定的概率分布，在每一層獨(dú)立采樣一定數(shù)量的節(jié)點(diǎn)，避免了對(duì)多跳鄰居的遞歸采樣。然而該采樣方法可能導(dǎo)致采樣節(jié)點(diǎn)產(chǎn)生的鄰接矩陣是稀疏的，無法實(shí)現(xiàn)高精度。因此Huang等［10］在FastGCN的基礎(chǔ)上做出改進(jìn)，AS-GCN通過自上而下對(duì)每層固定數(shù)量的節(jié)點(diǎn)進(jìn)行抽樣，保證了較高的準(zhǔn)確性。上述采樣方法避免了鄰域爆炸，提高了模型的訓(xùn)練速度，但當(dāng)訓(xùn)練圖的規(guī)模很大時(shí)，這些方法在加速訓(xùn)練時(shí)并不能優(yōu)化內(nèi)存成本。

面對(duì)訓(xùn)練過程中的內(nèi)存成本問題，有學(xué)者提出基于子圖的采樣方法?；谧訄D的采樣方法在形式上是對(duì)GCN訓(xùn)練中的每個(gè)小批進(jìn)行一個(gè)或多個(gè)子圖抽樣，而不是在完整的圖上進(jìn)行節(jié)點(diǎn)采樣或邊采樣。Cluster-GCN［11］使用圖聚類算法將原始圖劃分為多個(gè)簇，再隨機(jī)抽樣固定數(shù)量的聚類構(gòu)造子圖。但在實(shí)際操作簇的大小很難控制。Graph-SAINT［12］通過使用隨機(jī)游走策略對(duì)根節(jié)點(diǎn)集中一個(gè)節(jié)點(diǎn)的鄰居進(jìn)行采樣，并利用所選的鄰居和根節(jié)點(diǎn)集生成子圖。J.Bai等提出的Ripple Walk Training［13］考慮圖結(jié)構(gòu)數(shù)據(jù)的隨機(jī)性和連通性，通過紋波行走采樣器采樣高質(zhì)量子圖，用于后續(xù)模型訓(xùn)練。

目前，上述三類采樣方法已經(jīng)在同質(zhì)網(wǎng)絡(luò)中取得了相多的應(yīng)用。但相較于同質(zhì)網(wǎng)絡(luò)，異質(zhì)網(wǎng)絡(luò)［14］結(jié)構(gòu)更加復(fù)雜。異質(zhì)網(wǎng)絡(luò)是一種包括多種節(jié)點(diǎn)類型以及多種關(guān)系類型的特殊網(wǎng)絡(luò)。關(guān)于異質(zhì)網(wǎng)絡(luò)的研究有很多數(shù)據(jù)挖掘任務(wù)，其中鏈接預(yù)測能夠有效挖掘網(wǎng)絡(luò)中的丟失信息，在實(shí)際生活中具有重要的使用價(jià)值，如好友推薦［15］、電影推薦［16］、知識(shí)圖譜完善［17］、新陳代謝網(wǎng)絡(luò)重建［18］等。Schlichtkrull等［19］提出的關(guān)系圖卷積網(wǎng)絡(luò)（RGCN）是學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)表示的強(qiáng)大模型，能夠有效解決鏈接預(yù)測任務(wù)。但當(dāng)面臨真實(shí)世界中的大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，關(guān)系圖卷積模型的使用成本、計(jì)算復(fù)雜度太高，因此迫切需要引入采樣方法以保證大規(guī)模圖的可擴(kuò)展性。

本文提出了基于鄰域采樣的異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測小批量訓(xùn)練算法，我們將鄰域采樣和批處理結(jié)合起來，可用于大規(guī)模異質(zhì)網(wǎng)絡(luò)。算法的主要思想是通過小批量訓(xùn)練的方式，對(duì)全圖進(jìn)行采樣得到鄰域子圖。通過每次只構(gòu)建一個(gè)批量的子圖進(jìn)行更新參數(shù)，從而減少訓(xùn)練過程的計(jì)算開銷。簡單來說，就是在訓(xùn)練過程中，隨機(jī)打亂訓(xùn)練圖數(shù)據(jù)，確定固定大小的小批量數(shù)據(jù)。然后以每個(gè)批量數(shù)據(jù)為中心，對(duì)訓(xùn)練圖進(jìn)行采樣，得到每個(gè)批量對(duì)應(yīng)的鄰域子圖。最后將子圖輸入關(guān)系圖卷積模型中，進(jìn)行圖卷積操作，得到對(duì)應(yīng)的低維節(jié)點(diǎn)表征。并且由于DistMult［20］是一個(gè)簡單有效的因式分解，其在鏈接預(yù)測任務(wù)中有著良好表現(xiàn)。因此，在得到節(jié)點(diǎn)嵌入后，本文將DistMult模型作為評(píng)分函數(shù)處理后續(xù)異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測任務(wù)。

本文主要工作如下：

1）本文提出了一種針對(duì)大規(guī)模異質(zhì)網(wǎng)絡(luò)的鄰域采樣方法。該采樣方法能夠更好地保留異質(zhì)網(wǎng)絡(luò)的結(jié)構(gòu)信息，并且在保持子圖的連通性和隨機(jī)性上具有明顯優(yōu)勢。因此，該算法不僅提高了RGCN在大圖上的訓(xùn)練速度，還能減少訓(xùn)練過程的計(jì)算內(nèi)存。

2）本文通過小批量訓(xùn)練的方式實(shí)現(xiàn)了鄰域采樣方法。對(duì)全圖進(jìn)行采樣得到批量鄰域子圖。RGCN模型在子圖內(nèi)執(zhí)行小批量隨機(jī)梯度下降，梯度計(jì)算不依賴于子圖之外的節(jié)點(diǎn)。

3）本文選擇多個(gè)基線方法，在規(guī)模不同的數(shù)據(jù)集進(jìn)行鏈接預(yù)測任務(wù)的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了本文提出的采樣方法的有效性。實(shí)驗(yàn)表明，大規(guī)模圖中鏈接預(yù)測準(zhǔn)確率提高了30.67%。

2 相關(guān)研究

本文提出基于鄰域采樣的異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測小批量訓(xùn)練算法，該算法利用鄰域采樣獲得子圖，并利用關(guān)系圖卷積模型對(duì)子圖進(jìn)行編碼，捕獲異質(zhì)網(wǎng)絡(luò)的結(jié)構(gòu)和語義信息。本文將相關(guān)研究分為了兩類：圖卷積網(wǎng)絡(luò)的訓(xùn)練技術(shù)和關(guān)系圖卷積模型。

1）圖卷積網(wǎng)絡(luò)的訓(xùn)練技術(shù)

為了提高圖卷積的計(jì)算效率以及減少內(nèi)存成本，一個(gè)簡單的解決措施是通過子圖采樣構(gòu)建淺領(lǐng)域。通過將全局視角轉(zhuǎn)化到局部視角，即整個(gè)消息傳遞的步驟不是在全圖上進(jìn)行的，而是在局部子圖上執(zhí)行的，這樣我們能夠解決表達(dá)和計(jì)算的問題。Cluster-GCN［11］是一種基于子圖采樣的典型方法，該方法通過對(duì)全圖聚類構(gòu)造子圖，但實(shí)際上聚類的大小是很難控制的，而且在大規(guī)模圖上聚類的空間和時(shí)間的開銷是不可忽略。于是Zeng等［12］以在大規(guī)模上訓(xùn)練GCN模型為動(dòng)機(jī)提出GraphSAINT，該方法在訓(xùn)練過程中構(gòu)建小批量的隨機(jī)漫步采樣器，模型性能優(yōu)于先前工作。此外，Zhang等［21］提出的SEAL鏈接預(yù)測框架通過提取k階封閉子圖進(jìn)行鏈接預(yù)測，并獲得了不錯(cuò)的效果，證實(shí)了使用局部子圖來代替全局網(wǎng)絡(luò)的可行性。Zeng等［22］分析了深度圖神經(jīng)網(wǎng)絡(luò)面臨著鄰居爆炸和過度平滑的缺點(diǎn)，并據(jù)此提出打破傳統(tǒng)的分層采樣思想，使用多種子圖采樣器，將在全圖上進(jìn)行的圖卷積操作轉(zhuǎn)向局部子圖。實(shí)驗(yàn)證明，這種基于子圖的采樣方法提高了推理精度和計(jì)算效果。因此，我們考慮通過采樣，使用局部子圖代替全局網(wǎng)絡(luò)進(jìn)行訓(xùn)練。

為了提高模型鏈接預(yù)測能力與訓(xùn)練速率，基于以上研究，本文提出一種針對(duì)大規(guī)模網(wǎng)絡(luò)的鄰域采樣方法。該方法結(jié)合k階采樣器［22］對(duì)異質(zhì)圖進(jìn)行采樣，在保留網(wǎng)絡(luò)的結(jié)構(gòu)信息的基礎(chǔ)上，獲取局部子圖，后續(xù)卷積操作都在小批量子圖上進(jìn)行。

2）關(guān)系圖卷積模型

目前有多個(gè)研究利用圖卷積神經(jīng)網(wǎng)絡(luò)（GCN）［4］處理圖數(shù)據(jù)，作為GCN模型的擴(kuò)展，關(guān)系圖卷積模型（RGCN）［19］在處理多關(guān)系圖上的優(yōu)秀表現(xiàn)也受到了各個(gè)研究領(lǐng)域的廣泛關(guān)注。該模型通過計(jì)算邊緣的方向和分別處理不同關(guān)系的消息傳遞將圖卷積擴(kuò)展到多關(guān)系圖上。實(shí)驗(yàn)結(jié)果表明，RGCN作為一個(gè)學(xué)習(xí)多關(guān)系圖潛在特征的消息傳遞框架，可以有效應(yīng)用于多關(guān)系數(shù)據(jù)的建模。然而，盡管RGCN在處理異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)上性能較好，但它仍然面臨挑戰(zhàn)。對(duì)于圖卷積操作來說，節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息影響著該節(jié)點(diǎn)的特征表示，在消息傳遞過程中起著至關(guān)重要的作用。在RGCN訓(xùn)練過程中，模型會(huì)在整個(gè)網(wǎng)絡(luò)中隨機(jī)采樣邊，并在采樣的邊緣上執(zhí)行消息傳遞，生成節(jié)點(diǎn)嵌入。在此過程，大規(guī)模異質(zhì)網(wǎng)絡(luò)的結(jié)構(gòu)信息很容易丟失，而且并不能保證目標(biāo)節(jié)點(diǎn)的鄰域結(jié)構(gòu)信息被充分保留，因此，RGCN模型在大規(guī)模異質(zhì)圖上并不能得到有效擴(kuò)展。

基于以上研究，本文將使用關(guān)系圖卷積模型對(duì)采樣得到的子圖進(jìn)行編碼以獲取各節(jié)點(diǎn)的特征表示。該部分能夠充分考慮異質(zhì)圖中的關(guān)系類型，有利于鏈接預(yù)測任務(wù)的完成。

3 基于鄰域采樣的異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測算法

3.1 問題描述

其中，Vt表示通過在訓(xùn)練圖上進(jìn)行批量處理確定的種子節(jié)點(diǎn)集合。子圖G[v]表示以節(jié)點(diǎn)v為初始節(jié)點(diǎn)對(duì)訓(xùn)練圖G進(jìn)行采樣得到的子圖。G'm表示批量m對(duì)應(yīng)的子圖。此基礎(chǔ)上我們探究了異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測任務(wù)。異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測研究的是異質(zhì)網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)之間是否存在鏈接［21］，即判斷節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的邊(vi,vj)是否存在，以及存在邊的關(guān)系類型r。

3.2 基于k階采樣器的鄰域采樣

本節(jié)將介紹基于k階采樣器［22］的鄰域采樣方法，該方法對(duì)全圖進(jìn)行采樣得到批量鄰域子圖，將圖的規(guī)?？刂圃诳捎?jì)算的范圍內(nèi)。我們將采樣方法分成三個(gè)步驟：確定種子節(jié)點(diǎn)、k階采樣、子圖節(jié)點(diǎn)重排序。鄰域子圖的構(gòu)建過程如圖1所示。

圖1 鄰域子圖的構(gòu)建

3.2.1 確定種子節(jié)點(diǎn)

輸入異質(zhì)圖G，將圖G中的N個(gè)三元組隨機(jī)打亂來構(gòu)建M個(gè)批次，每個(gè)批次內(nèi)固定b條數(shù)據(jù)。通過計(jì)算批次內(nèi)數(shù)據(jù)源節(jié)點(diǎn)和終節(jié)點(diǎn)的并集確定種子節(jié)點(diǎn)。由于種子節(jié)點(diǎn)集合的結(jié)果依賴于分批的隨機(jī)性，這在一定程度上考慮到數(shù)據(jù)的多樣性，使得不同類型的節(jié)點(diǎn)能夠被收集，進(jìn)而減少了網(wǎng)絡(luò)信息的損失。

3.2.2k階采樣

利用k階采樣器對(duì)每個(gè)批次中的種子節(jié)點(diǎn)進(jìn)行采樣，將相同批次中所有種子節(jié)點(diǎn)的k階鄰域子圖連接得到采樣結(jié)果圖。其中，k階采樣器的實(shí)現(xiàn)方式是從種子節(jié)點(diǎn)出發(fā)尋找與其自身的最短路徑為k跳的節(jié)點(diǎn)集合，并從該集合中隨機(jī)選取b個(gè)節(jié)點(diǎn)作為采樣的結(jié)果。在該過程中，采樣器能夠捕捉到原始輸入圖一些有意義的全局結(jié)構(gòu)特征。同時(shí)，SEAL框架［21］證明了局部網(wǎng)絡(luò)能夠表示全局網(wǎng)絡(luò)。因此，我們采樣得到的子圖包含自身和輸入原始圖的結(jié)構(gòu)信息。使得節(jié)點(diǎn)嵌入中蘊(yùn)含的信息更為豐富。此外，與隨機(jī)采樣的方式不同，本文所使用的采樣方法在保證隨機(jī)性的同時(shí)，還考慮了鄰域子圖的連接性。使得采樣結(jié)果子圖更好地保留了異質(zhì)網(wǎng)絡(luò)中的領(lǐng)域結(jié)構(gòu)信息。

3.2.3 子圖節(jié)點(diǎn)重排序

將每個(gè)批次中采樣得到的子圖分別重新編號(hào)得到最終的采樣結(jié)果圖。重新編號(hào)能夠清除原始輸入圖中的鏈接關(guān)系，避免模型學(xué)習(xí)到無關(guān)信息。通過這樣的方式能夠提升計(jì)算效率，消除采樣結(jié)果子圖中的冗余信息，提升模型的泛化性能。上述采樣方法的總體流程的偽代碼如算法1所示。

算法1基于k階采樣器的鄰域采樣算法

輸出：每個(gè)批量構(gòu)建的子圖｛G'}={G1'…GM'}，每個(gè)批量對(duì)應(yīng)的訓(xùn)練樣本

3.3 鏈接預(yù)測任務(wù)

本節(jié)介紹鏈接預(yù)測總框架。先通過采樣模塊對(duì)異質(zhì)圖進(jìn)行采樣，獲得各批量對(duì)應(yīng)的子圖，再使用關(guān)系圖卷積模型編碼器對(duì)鄰域子圖進(jìn)行特征提取，并采用解碼器處理下游鏈接預(yù)測任務(wù)的過程。具體來說，先利用關(guān)系圖卷積模型的學(xué)習(xí)能力和泛化能力對(duì)各鄰域子圖進(jìn)行編碼，學(xué)習(xí)子圖中各節(jié)點(diǎn)和關(guān)系的低維嵌入，再利用DistMult解碼器對(duì)這些嵌入進(jìn)行學(xué)習(xí)。鏈接預(yù)測整體結(jié)構(gòu)如圖2所示。

圖2 鏈接預(yù)測框架

3.3.1 鄰域子圖的特征提取

本文采用Schlichtkrull等［19］提出的關(guān)系圖卷積（RGCN）的方法在多關(guān)系鄰域子圖上執(zhí)行消息傳遞來獲得各節(jié)點(diǎn)和關(guān)系的低維嵌入。該方法是獲得異質(zhì)圖表征的一個(gè)有效方法，其在基于GCN的聚合鄰居的操作之上，對(duì)關(guān)系維度也進(jìn)行了一次聚合，從而使得節(jié)點(diǎn)的聚合操作成為鄰居、關(guān)系維度上的雙重聚合。其核心公式表達(dá)如下：

其中，ci,r是通過預(yù)先學(xué)習(xí)或者選擇的特定的標(biāo)準(zhǔn)化常數(shù)，一般可選為表示與節(jié)點(diǎn)vi具有r關(guān)系的鄰居集合。為可學(xué)習(xí)參數(shù)，是節(jié)點(diǎn)自身對(duì)應(yīng)的權(quán)重參數(shù)。

如圖2所示，RGCN模型的輸入是鄰域子圖。經(jīng)過兩層關(guān)系卷積神經(jīng)計(jì)算之后，編碼器會(huì)生成鄰域子圖各節(jié)點(diǎn)的特征向量，并將其輸入解碼器中。

3.3.2 預(yù)測評(píng)分

鏈接預(yù)測通常是指預(yù)測一個(gè)實(shí)體與另一個(gè)給定實(shí)體之間有特定關(guān)系的任務(wù)，包括實(shí)體排名［23～24］和關(guān)系預(yù)測［25］。具體來說，實(shí)體排名是給定(r,vj)預(yù)測實(shí)體vi或給定（vi，r）預(yù)測實(shí)體vj。前者表示為（?,r,vj），后者表示為（vi,r,?）。關(guān)系預(yù)測是預(yù)測兩個(gè)給定實(shí)體之間的關(guān)系，表示為（vi,?,vj）。這里我們僅考慮采用異質(zhì)網(wǎng)絡(luò)關(guān)系預(yù)測任務(wù)。DistMult評(píng)分函數(shù)可用于計(jì)算關(guān)系存在可能性分?jǐn)?shù)值。

預(yù)測兩個(gè)給定節(jié)點(diǎn)之間的關(guān)系（vi,?,vj）時(shí)，對(duì)于給定的三元組，模型通過使用以下函數(shù)對(duì)所有可能的三元組打分來訓(xùn)練：

其中⊙為哈達(dá)瑪積，evi，evi表示關(guān)系r和節(jié)點(diǎn)vi的嵌入。表示可能的關(guān)系類型嵌入。本文利用交叉熵?fù)p失進(jìn)行優(yōu)化，使模型的正三元組評(píng)分高于負(fù)三元組，通過最小化交叉熵?fù)p失來得到知識(shí)圖譜中實(shí)體與關(guān)系的嵌入，損失函數(shù)公式如下：

其中T是該批次內(nèi)正負(fù)三元組的全部集合，l是激活函數(shù)，y是一個(gè)指示符，當(dāng)y=1時(shí)表示正三元組，y=0時(shí)表示負(fù)三元組。f(vi,r,vj)包括來自RGCN編碼器的實(shí)體嵌入和來自DistMult解碼器的關(guān)系嵌入。

3.4 空間算法復(fù)雜度分析

與以往的圖卷積操作不同，基于領(lǐng)域采樣的異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測算法考慮構(gòu)建一種內(nèi)存友好的方式。該算法只需要存儲(chǔ)鄰域子圖的節(jié)點(diǎn)特征向量矩陣與關(guān)系向量矩陣。其空間開銷如下：

對(duì)于傳統(tǒng)的關(guān)系圖卷積來說，在計(jì)算過程中通常依賴于全局網(wǎng)絡(luò)，其內(nèi)存開銷為

其中|G|v表示整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量，|G|r表示整個(gè)網(wǎng)絡(luò)的關(guān)系類型數(shù)量，K為RGCN設(shè)置層數(shù)。

由3.2節(jié)算法介紹可知，鄰域子圖是從大規(guī)模網(wǎng)絡(luò)中采樣得到，其規(guī)模遠(yuǎn)小于原網(wǎng)絡(luò)，領(lǐng)域子圖中節(jié)點(diǎn)遠(yuǎn)小于原網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，即因此，顯然本文提出算法空間開銷遠(yuǎn)小于以往訓(xùn)練方法，即S1＜S2。這使得模型能夠在大規(guī)模圖上高效地進(jìn)行訓(xùn)練。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

為了證明提出的鄰域采樣算法框架的通用性及有效性，本文實(shí)驗(yàn)針對(duì)三種規(guī)模不同的異質(zhì)網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測對(duì)比，主要包括知識(shí)圖譜Freebase中的子集FB15k-237［19］，F(xiàn)B-Toy［26］以及詞匯數(shù)據(jù)庫WordNet中的子集WN18［19］。上述數(shù)據(jù)集的各項(xiàng)指標(biāo)統(tǒng)計(jì)如表1所示。

表1 數(shù)據(jù)集描述

鑒于WN18數(shù)據(jù)集中存在一個(gè)影響實(shí)驗(yàn)結(jié)果的缺陷：存在反向三元組對(duì)（vi,r,vj）和（vj,r-1,vi），其中（vi,r,vj）存在于訓(xùn)練集，（vj,r-1,vi）存在于測試集。這在很大程度上影響了RGCN模型在異質(zhì)網(wǎng)絡(luò)中鏈接預(yù)測任務(wù)的準(zhǔn)確性。因此我們選擇FB15k-237與FB-Toy作為我們的主要評(píng)估數(shù)據(jù)集。

本文主要采用了準(zhǔn)確率（Accuracy）評(píng)估指標(biāo)，判斷關(guān)系類型的預(yù)測與標(biāo)簽是否一致，公式如下：

其中，TP代表預(yù)測正確的正例樣本數(shù)，TN表示預(yù)測正確的負(fù)例樣本數(shù)，R為總樣本數(shù)。準(zhǔn)確率越高，說明模型鏈接預(yù)測越準(zhǔn)確。

4.2 對(duì)比模型

為了驗(yàn)證鄰域采樣算法的有效性，我們將結(jié)合鄰域采樣進(jìn)行訓(xùn)練的RGCN模型與原始RGCN模型以及其他添加本文提出的鄰域采樣機(jī)制的GCN［4］、GAT［27］、GraphSAGE［5］模型進(jìn)行比較。

1）RGCN：該模型將圖卷積應(yīng)用到異質(zhì)網(wǎng)絡(luò)中，能夠處理圖中不同的邊關(guān)系類型對(duì)節(jié)點(diǎn)嵌入的影響，適用于解決異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測以及實(shí)體分類問題。

2）RGCN+：添加了本文提出的鄰域采樣機(jī)制的RGCN模型。原始RGCN模型通過隨機(jī)邊采樣構(gòu)建訓(xùn)練圖，考慮對(duì)高度多關(guān)系數(shù)據(jù)的建模。

3）GCN+：該模型將GCN與本文提出的鄰域采樣機(jī)制相融合。原始GCN是在訓(xùn)練中對(duì)整個(gè)圖進(jìn)行操作的半監(jiān)督方法，在學(xué)習(xí)圖表示方面表現(xiàn)優(yōu)異。

4）GAT+：添加了本文提出的鄰域采樣機(jī)制的GAT模型。原始GAT在傳播過程引入自注意力（self-attention）機(jī)制，每個(gè)節(jié)點(diǎn)的隱藏狀態(tài)通過為其鄰居節(jié)點(diǎn)分配權(quán)重來計(jì)算。

5）GraphSAGE+：添加本文提出的鄰域采樣機(jī)制的GraphSAGE模型。GraphSAGE是一個(gè)利用節(jié)點(diǎn)特征信息為未知節(jié)點(diǎn)生成有效嵌入的通用歸納框架。

4.3 實(shí)驗(yàn)參數(shù)設(shè)置

經(jīng)過多次實(shí)驗(yàn)，針對(duì)不同數(shù)據(jù)集，本文模型的超參數(shù)設(shè)置不同，具體如下。

默認(rèn)設(shè)置RGCN模型層數(shù)為兩層。設(shè)置FB15k-237數(shù)據(jù)集在RGCN模型隱藏層的大小為256，學(xué)習(xí)率為0.0001，迭代次數(shù)為5；設(shè)置WN18數(shù)據(jù)集在RGCN模型隱藏層的大小為200，學(xué)習(xí)率為0.0005，迭代次數(shù)為25；對(duì)于FB-Toy數(shù)據(jù)集，其模型隱藏層的大小設(shè)為200，學(xué)習(xí)率設(shè)為0.0001，迭代次數(shù)為30。為了防止過擬合，上述三個(gè)數(shù)據(jù)集都使用了dropout［28］技術(shù)，統(tǒng)一設(shè)置為0.2，并且都選擇ADAM［29］作為優(yōu)化器。經(jīng)過多次實(shí)驗(yàn)比較，本文鄰域采樣機(jī)制中采樣參數(shù)k,B選擇為k=1,B=7時(shí)，模型效果最好。

本文所使用的對(duì)比模型的超參數(shù)設(shè)置如下：對(duì)比模型默認(rèn)層數(shù)為兩層。原始RGCN模型在不同數(shù)據(jù)集上超參數(shù)設(shè)置不同，F(xiàn)B-Toy數(shù)據(jù)集及WN18數(shù)據(jù)集的嵌入維度設(shè)為200，迭代次數(shù)為10000；FB15k-237數(shù)據(jù)集隱藏層的大小為500，迭代次數(shù)為10000；其余參數(shù)遵循原始論文設(shè)置。GCN+、GAT+、Graph SAGE+模型的超參數(shù)設(shè)置與本文模型在不同數(shù)據(jù)集上參數(shù)設(shè)置相同。

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

4.4.1 鏈接預(yù)測任務(wù)評(píng)估指標(biāo)對(duì)比

本文在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表2和圖3所示，其中表2中加粗的表示最好的結(jié)果。根據(jù)實(shí)驗(yàn)結(jié)果，我們總結(jié)出如下重要發(fā)現(xiàn)。

圖3 鏈接預(yù)測準(zhǔn)確率對(duì)比結(jié)果

表2 模型在各數(shù)據(jù)集的評(píng)估指標(biāo)對(duì)比

隨著數(shù)據(jù)集規(guī)模的增大，添加了本文提出的鄰域采樣算法的模型性能基本上都在不斷地提升。與小規(guī)模數(shù)據(jù)集FB-Toy對(duì)比，RGCN+模型在大規(guī)模數(shù)據(jù)集FB15k-237數(shù)據(jù)集上性能提升了14.68%。而在GCN+模型上對(duì)應(yīng)的數(shù)據(jù)為16.73%。此外，由于WN18數(shù)據(jù)集本身存在缺陷，導(dǎo)致了在RGCN+、GAT+和SAGE+模型上的表現(xiàn)并未與數(shù)據(jù)規(guī)模同步遞增。但是，在主要評(píng)估數(shù)據(jù)集FB-Toy以及FB15k-237上，數(shù)據(jù)規(guī)模越大，GAT+和SAGE+表現(xiàn)也越好。與小數(shù)據(jù)集FB-Toy相比，GAT+、SAGE+模型在大數(shù)據(jù)集FB15k-237上的鏈接預(yù)測準(zhǔn)確率分別提升了7.63%、9.93%。綜上所述，本文提出的采樣方法有效且在大規(guī)模數(shù)據(jù)集上優(yōu)勢明顯。

綜合考慮異質(zhì)圖的關(guān)系類型有益于提升鏈接預(yù)測的準(zhǔn)確性。在不同數(shù)據(jù)集上，RGCN+模型與基線模型相比，效果基本上都是最優(yōu)的。在FB-Toy，Wn18，F(xiàn)B15k-237數(shù)據(jù)集上，RGCN+模型性能與其他基準(zhǔn)模型相比平均提升了12.84%，15.69%，23.19%。其中，由于FB-Toy數(shù)據(jù)集過小，導(dǎo)致RGCN+與RGCN效果差異不大。這也說明了采樣方法在大規(guī)模數(shù)據(jù)集中才更加凸顯優(yōu)勢。此外，在添加了采樣方法的GCN+，GAT+，SAGE+，RGCN+中，由于RGCN+額外考慮了異質(zhì)圖中的關(guān)系類型，而其他模型忽略了這一因素，使得它們的表現(xiàn)不如RGCN+。

4.4.2 模型效率分析

我們通過在實(shí)驗(yàn)中記錄模型訓(xùn)練所需要的時(shí)間，證明了本文提出的采樣方法能夠減少模型訓(xùn)練時(shí)間。具體數(shù)據(jù)如表3所示。結(jié)果表明在不同數(shù)據(jù)集上，添加本文提出的鄰域采樣算法能夠提高模型的訓(xùn)練速度。在三個(gè)數(shù)據(jù)集上，RGCN+模型比RGCN模型運(yùn)行時(shí)間平均減少了32281s。在RGCN上使用鄰域采樣算法不僅需要較少的內(nèi)存空間，而且可以加快訓(xùn)練過程的收斂速度。這是因?yàn)槊總€(gè)訓(xùn)練階段涉及的空間和計(jì)算復(fù)雜度都較小。在每次批處理中，基于鄰域采樣的異質(zhì)網(wǎng)絡(luò)鏈接預(yù)測算法模型在GUP加載的每個(gè)子圖內(nèi)執(zhí)行小批量隨機(jī)梯度下降。并在算法的后續(xù)運(yùn)行過程中，前向傳播和后向傳播都在小而完整的鄰域子圖上進(jìn)行，而不是對(duì)原始圖進(jìn)行處理。綜上所述，本文提出的采樣方法能夠提升模型的運(yùn)行效率。

表3 訓(xùn)練時(shí)間對(duì)比（單位：s）

4.4.3 采樣參數(shù)敏感性分析

為了驗(yàn)證采樣過程中鄰居數(shù)量對(duì)模型的影響，本文在三種數(shù)據(jù)集上對(duì)采樣參數(shù)B進(jìn)行了敏感性分析。實(shí)驗(yàn)結(jié)果如圖4所示，隨著采樣鄰居數(shù)量的遞增，在小規(guī)模數(shù)據(jù)集FB-Toy以及規(guī)模較大但存在缺陷的WN18數(shù)據(jù)集上，鏈接預(yù)測準(zhǔn)確率整體呈上升趨勢，但幅度較小。而在大規(guī)模數(shù)據(jù)集FB15k-237，采樣鄰居數(shù)量越多，模型的性能也更佳，鄰居數(shù)量到達(dá)一定的值后，模型的性能趨于平穩(wěn)。因此，綜合考慮訓(xùn)練時(shí)間和模型性能，本文將參數(shù)b設(shè)為7進(jìn)行對(duì)比實(shí)驗(yàn)。

5 結(jié)語

本文提出了一種基于鄰域子圖采樣的訓(xùn)練框架，該框架通過小批量訓(xùn)練的方式實(shí)現(xiàn)了一種針對(duì)大規(guī)模異質(zhì)圖的領(lǐng)域采樣方法。該方法采樣得到的子圖很好地保留了異質(zhì)圖的結(jié)構(gòu)信息，而且子圖內(nèi)依然保持著良好的連通性。這樣就使得模型能夠在大規(guī)模圖上高效地進(jìn)行訓(xùn)練。此外，通過在子圖內(nèi)進(jìn)行小批量的隨機(jī)梯度下降的方式解決了梯度爆炸的問題。本文通過將采樣方法應(yīng)用于鏈接預(yù)測問題來驗(yàn)證其有效性。在多個(gè)真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)表明，添加該采樣算法的關(guān)系圖卷積模型與基線相比能夠顯著提升鏈接預(yù)測的準(zhǔn)確率。同時(shí)，模型的訓(xùn)練速度也得到了顯著的提升。未來的研究方向是將該采樣方法與不同的模型結(jié)合應(yīng)用到更多的實(shí)際問題中。