魯富榮，原之安，錢宇華+

1.山西大學(xué)大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院，太原030006

2.山西大學(xué)計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原030006

3.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006

網(wǎng)絡(luò)是對(duì)現(xiàn)實(shí)世界對(duì)象及其相互作用關(guān)系的抽象表示，其中節(jié)點(diǎn)代表實(shí)體對(duì)象，鏈接表示實(shí)體間的成對(duì)關(guān)系。如生物蛋白質(zhì)相互作用網(wǎng)絡(luò)、科學(xué)研究中的引文合作網(wǎng)絡(luò)以及社交網(wǎng)路中朋友關(guān)系網(wǎng)絡(luò)。這些網(wǎng)絡(luò)中包含豐富的節(jié)點(diǎn)屬性信息、結(jié)構(gòu)信息以及網(wǎng)絡(luò)演化信息。在網(wǎng)絡(luò)的演化過程中，某些鏈接可能出現(xiàn)或消失，需要對(duì)缺失數(shù)據(jù)進(jìn)行補(bǔ)全以及對(duì)未來可能出現(xiàn)或消失的鏈接做出預(yù)測(cè)。同時(shí)作為數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支，鏈路預(yù)測(cè)具有很重要的現(xiàn)實(shí)意義。例如，生物網(wǎng)絡(luò)分析[1]中，鏈路預(yù)測(cè)可以對(duì)生物數(shù)據(jù)進(jìn)行挖掘和補(bǔ)全?？茖W(xué)合作者[2]及朋友推薦[3]中，鏈路預(yù)測(cè)可以推薦相關(guān)的新的朋友和科研合作者。

鏈路預(yù)測(cè)問題作為數(shù)據(jù)挖掘領(lǐng)域的經(jīng)典問題，已有很多相關(guān)的模型和方法。目前鏈路預(yù)測(cè)的方法大多基于節(jié)點(diǎn)表示的相似性假設(shè)，也即節(jié)點(diǎn)對(duì)的表示越相似，則產(chǎn)生鏈接的可能性越大，因此問題就歸結(jié)為尋找高質(zhì)量的節(jié)點(diǎn)表示，使得節(jié)點(diǎn)的表示保留原網(wǎng)絡(luò)的拓?fù)涮卣?，也即原網(wǎng)絡(luò)有邊相連的節(jié)點(diǎn)，在節(jié)點(diǎn)的表示中較為相似。

近年來，由于圖結(jié)構(gòu)的網(wǎng)絡(luò)嵌入方法和圖神經(jīng)網(wǎng)絡(luò)的迅速發(fā)展，進(jìn)一步提升了模型對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的表示能力。然而大部分模型都利用節(jié)點(diǎn)的直接鄰居的信息進(jìn)行卷積操作，并未充分利用網(wǎng)絡(luò)的結(jié)構(gòu)信息且較少考慮網(wǎng)絡(luò)的高階拓?fù)湫畔ⅰ?/p>

為提高節(jié)點(diǎn)的表示能力且兼顧計(jì)算效率，本文提出了基于模體的圖神經(jīng)網(wǎng)絡(luò)鏈路預(yù)測(cè)模型，主要貢獻(xiàn)包括三方面：

（1）在自編碼器框架下，提出一種模體圖神經(jīng)網(wǎng)絡(luò)模型為編碼器的鏈路預(yù)測(cè)模型，該模型提取了網(wǎng)絡(luò)的高階拓?fù)涮卣鳌?/p>

（2）構(gòu)建了基于同質(zhì)網(wǎng)絡(luò)的模體圖神經(jīng)網(wǎng)絡(luò)模型，根據(jù)指定的模體結(jié)構(gòu)構(gòu)建節(jié)點(diǎn)的鄰域，進(jìn)而聚合鄰居信息得到節(jié)點(diǎn)的表示。

（3）不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明本文的模型有效提高了鏈路預(yù)測(cè)的準(zhǔn)確率。

1 相關(guān)工作

傳統(tǒng)的鏈路預(yù)測(cè)方法主要分為兩大部分：基于拓?fù)渲笜?biāo)的方法和基于機(jī)器學(xué)習(xí)的方法。第一類方法又可分為基于局部拓?fù)涞姆椒ê突谌滞負(fù)涞姆椒?。此類方法通常假設(shè)節(jié)點(diǎn)間的共同鄰居越多則越相似。如共同鄰居CN（common neighbour）[4]和AA（adamic-adar）[5]指標(biāo)以及基于資源分配的RA（resource allocation）[6]指標(biāo)等，這類方法的優(yōu)點(diǎn)是計(jì)算效率高且可并行，但缺點(diǎn)是準(zhǔn)確率相對(duì)較低，尤其當(dāng)網(wǎng)絡(luò)比較大而且稀疏時(shí)。基于全局的方法利用全局的拓?fù)湫畔碛?jì)算節(jié)點(diǎn)間的相似性，準(zhǔn)確度有一定的提升，但由于利用了全局的拓?fù)湫畔?，?jì)算復(fù)雜度偏高。另一大類方法是基于機(jī)器學(xué)習(xí)的模型，包括基于機(jī)器學(xué)習(xí)的分類方法、基于概率似然函數(shù)的方法和矩陣分解方法，其中分類方法將節(jié)點(diǎn)對(duì)標(biāo)記為0 或1，0表示不存在鏈接，1 代表存在鏈接，進(jìn)而將鏈路預(yù)測(cè)轉(zhuǎn)化為二分類問題。該類方法用的是監(jiān)督學(xué)習(xí)中一些常用的分類算法（如決策樹、K 近鄰法、支持向量機(jī)）對(duì)缺失的連邊進(jìn)行預(yù)測(cè)?；诟怕实哪Ｐ椭饕▽哟谓Y(jié)構(gòu)模型，這類方法假設(shè)網(wǎng)絡(luò)有一定的先驗(yàn)的分層結(jié)構(gòu)或分塊的結(jié)構(gòu)[7]，給出了網(wǎng)絡(luò)的結(jié)構(gòu)特征的定量刻畫。基于矩陣分解的方法將鏈路預(yù)測(cè)視為鄰接矩陣的填充問題，基于非負(fù)矩陣或者譜分解等方法，給出節(jié)點(diǎn)的向量表示，進(jìn)而計(jì)算節(jié)點(diǎn)的相似性，預(yù)測(cè)節(jié)點(diǎn)間鏈接的存在性。這類方法的學(xué)習(xí)參數(shù)較少，但計(jì)算復(fù)雜度較高。

隨著深度學(xué)習(xí)的深入發(fā)展以及深度學(xué)習(xí)和網(wǎng)絡(luò)數(shù)據(jù)挖掘的融合，進(jìn)一步提高了模型的表達(dá)能力，國(guó)內(nèi)外學(xué)者提出了一系列基于圖嵌入和圖神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法。網(wǎng)絡(luò)嵌入的方法是自動(dòng)從原始網(wǎng)絡(luò)結(jié)構(gòu)信息中抽取局部的和全局的特征，將網(wǎng)絡(luò)節(jié)點(diǎn)映射到低維的向量空間。這類方法包括DeepWalk[8]、node2vec[9]、LINE[10]以及struc2vec[11]。相比傳統(tǒng)方法，這類方法達(dá)到了較高的鏈路預(yù)測(cè)準(zhǔn)確率。然而這類方法也存在一定的局限性：首先，訓(xùn)練過程中缺乏監(jiān)督信息，使得節(jié)點(diǎn)的表示與任務(wù)的關(guān)聯(lián)性不足。其次，在運(yùn)算過程中要多次用到基于全局拓?fù)浣Y(jié)構(gòu)的隨機(jī)游走方法，因此計(jì)算復(fù)雜度較高。

由于深度學(xué)習(xí)在圖像分類和自然語(yǔ)言處理方向的成功應(yīng)用，推動(dòng)了深度學(xué)習(xí)方法在圖網(wǎng)絡(luò)方向的遷移。借鑒卷積神經(jīng)網(wǎng)絡(luò)的思想，圖卷積網(wǎng)絡(luò)（graph convolutional networks，GCN）[12]結(jié)合網(wǎng)絡(luò)的全局拓?fù)湫畔⒑凸?jié)點(diǎn)的屬性信息，對(duì)節(jié)點(diǎn)的鄰居信息進(jìn)行聚合，最終基于節(jié)點(diǎn)分類任務(wù)給出了節(jié)點(diǎn)的表示。在此基礎(chǔ)上，Velickovic 等提出了圖注意力網(wǎng)絡(luò)（graph attention network，GAT）[13]，基于網(wǎng)絡(luò)的節(jié)點(diǎn)一階鄰居信息和屬性信息，將任意兩個(gè)節(jié)點(diǎn)的信息進(jìn)行拼接作為連邊信息，得到節(jié)點(diǎn)j相對(duì)于節(jié)點(diǎn)i的注意力權(quán)重，進(jìn)而按鄰居節(jié)點(diǎn)的注意力權(quán)重不同，對(duì)鄰居信息進(jìn)行加權(quán)聚合，得到節(jié)點(diǎn)的最終表示。圖神經(jīng)網(wǎng)絡(luò)模型得到了更好的節(jié)點(diǎn)表示，進(jìn)而達(dá)到更高的節(jié)點(diǎn)分類和鏈路預(yù)測(cè)準(zhǔn)確度。同時(shí)也存在如下缺陷：（1）聚合函數(shù)采用最大或平均的方法，不能很好地對(duì)網(wǎng)絡(luò)進(jìn)行區(qū)分。（2）在網(wǎng)絡(luò)增長(zhǎng)或遭受攻擊時(shí)，網(wǎng)絡(luò)結(jié)構(gòu)會(huì)發(fā)生改變，此時(shí)要得到節(jié)點(diǎn)表示，只能重新用GCN展開計(jì)算。（3）在網(wǎng)絡(luò)表示的過程中用到了節(jié)點(diǎn)鄰居信息，但并未用到網(wǎng)絡(luò)的高階信息，也即GCN 對(duì)網(wǎng)絡(luò)的拓?fù)湫畔⒗貌怀浞帧?/p>

對(duì)于第一個(gè)問題，Graph Isomorphism Network[14]進(jìn)行了初步的嘗試，聚合過程采用MLP+sumpooling，在多個(gè)任務(wù)上準(zhǔn)確率達(dá)到目前最好的結(jié)果。在第二個(gè)問題上，圖神經(jīng)網(wǎng)絡(luò)模型GraphSage[15]在迭代過程中固定采樣尺寸，然后采取一種特殊的聚合策略，對(duì)不斷增長(zhǎng)的網(wǎng)絡(luò)的表示提供了很好的解決方案。對(duì)于第三個(gè)問題，Zhang 等人[16]提出了SEAL（learning from subgraphs，embeddings and attributes for link prediction）模型，該模型從原網(wǎng)絡(luò)中提取包含待預(yù)測(cè)節(jié)點(diǎn)對(duì)的特定子圖結(jié)構(gòu)，得出一系列拓?fù)渲笜?biāo)作為節(jié)點(diǎn)對(duì)的向量表示，進(jìn)而學(xué)習(xí)出兩個(gè)節(jié)點(diǎn)存在鏈接的可能性。然而利用子圖結(jié)構(gòu)進(jìn)行學(xué)習(xí)時(shí)，對(duì)于每一對(duì)待預(yù)測(cè)節(jié)點(diǎn)u、v，需要構(gòu)建以u(píng)、v為中心的子圖，同時(shí)計(jì)算該子圖對(duì)應(yīng)的拓?fù)渲笜?biāo)，進(jìn)而利用神經(jīng)網(wǎng)絡(luò)進(jìn)行相應(yīng)的訓(xùn)練，計(jì)算成本較高。由于網(wǎng)絡(luò)由一些基本的子圖結(jié)構(gòu)（motif）構(gòu)成，有很多研究者試圖將圖神經(jīng)網(wǎng)絡(luò)和模體信息結(jié)合起來執(zhí)行下游的任務(wù)。

Wang 等人[17]提出了基于motif 的深度特征學(xué)習(xí)模型，利用正則表達(dá)式和圖自編碼器模型保留網(wǎng)絡(luò)的模體特征，最后獲得節(jié)點(diǎn)的表示。該模型僅利用了三階模體的信息而且并未真正將模體信息和圖神經(jīng)網(wǎng)絡(luò)進(jìn)行融合。Sankar 在2019 年給出了基于異質(zhì)網(wǎng)絡(luò)模體結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)模型Meta-GNN[18]，將異質(zhì)模體結(jié)構(gòu)嵌入圖卷積網(wǎng)絡(luò)，并結(jié)合圖注意力模型，對(duì)異質(zhì)網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)行了分類。然而對(duì)于同質(zhì)網(wǎng)絡(luò)，該模型并沒有給出相應(yīng)將高階結(jié)構(gòu)和圖神經(jīng)網(wǎng)絡(luò)相結(jié)合的解決方案。

本文提出的基于模體圖神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法，將網(wǎng)絡(luò)的模體結(jié)構(gòu)和圖神經(jīng)網(wǎng)絡(luò)模型結(jié)合，融合了網(wǎng)絡(luò)的高階拓?fù)涮卣?，增?qiáng)了圖神經(jīng)網(wǎng)絡(luò)的表示能力。在復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)驗(yàn)證了模型的有效性，可運(yùn)用到后續(xù)其他任務(wù)中。

2 預(yù)備知識(shí)

2.1 基本定義

本節(jié)列舉了文章中的預(yù)備性知識(shí)和記號(hào)，如表1所示。設(shè)G=(V;E)表示一個(gè)圖網(wǎng)絡(luò)，V表示節(jié)點(diǎn)集，E表示邊集，若兩個(gè)節(jié)點(diǎn)vi、vj有邊相連，則(vi,vj)∈E。模體M是指由網(wǎng)絡(luò)的少量節(jié)點(diǎn)構(gòu)成的圖G的子圖，定義如下：

表1 文中使用的符號(hào)和變量Table 1 Variables and notations in text

定義1（模體）[18]設(shè)M是圖G=(V;E) 的連通子圖，且滿足對(duì)任意(vi,vj)∈EM,(vi,vj)∈E，則稱M為G的模體，其中EM表示子圖M的邊集。

不同三階模體和四階模體如圖1 所示（表示為M3.、M4.，每個(gè)模體Mij的第一個(gè)下標(biāo)i代表節(jié)點(diǎn)數(shù)，第二個(gè)下標(biāo)j是指定排序），在科研合作網(wǎng)中模體M31代表兩個(gè)作者和另外一位都有合作，但他們彼此并沒有合作。往往這種情況發(fā)生在普通科研人員和科研名人的合作中。M32代表的則是接近同類一水平的科研人員的合作，三位作者彼此之間都有合作。

圖1 所有的三模體和四模體Fig.1 All tri-motifs and quad-motifs

定義2（模體的實(shí)例）[18]設(shè)Su=(VS，ES)是模體S的包含節(jié)點(diǎn)u實(shí)例，如果Su是圖G的一個(gè)子圖，且有VS∈V,ES∈E，使得對(duì)任意的x,y∈VS,(x,y)∈ES存在一個(gè)雙射ψ：S→M滿足 (x,y)∈ES當(dāng)且僅當(dāng)(ψS(x),ψS(y))∈EM。

定義3(模體鄰居）對(duì)于指定的模體類型M，節(jié)點(diǎn)vi的一階鄰居中，與vi位于同一類型模體中的節(jié)點(diǎn)稱為節(jié)點(diǎn)vi基于模體M的鄰居。

圖2 中的兩個(gè)模體(v,v1,v2)以及(v,v3,v4)是模體M32的兩個(gè)實(shí)例，同時(shí)v1、v2、v3、v4也是v的模體鄰居。在不同的網(wǎng)絡(luò)中，有隸屬于網(wǎng)絡(luò)的不同特征模體，其發(fā)生頻率遠(yuǎn)大于隨機(jī)圖中該子圖的發(fā)生頻率。在計(jì)算過程中，為提取網(wǎng)絡(luò)的模體特征，需要從網(wǎng)絡(luò)中搜索與不同類型模體同構(gòu)的所有模體，該過程計(jì)算成本較高。為降低計(jì)算的復(fù)雜度，本文僅考慮三階和四階模體，首先利用軟件mfinder[19]對(duì)網(wǎng)絡(luò)所包含的不同類型模體比例進(jìn)行計(jì)算，給出每個(gè)網(wǎng)絡(luò)的模體分布情況。

圖2 節(jié)點(diǎn)v的接受域包含v1、v2、v3、v4Fig.2 Receptive field around node v contains v1,v2,v3,v4

2.2 圖卷積網(wǎng)絡(luò)

傳統(tǒng)的圖卷積網(wǎng)絡(luò)模型結(jié)合了網(wǎng)絡(luò)的拓?fù)湫畔⒑蛯傩孕畔?，在網(wǎng)絡(luò)的每一層中將節(jié)點(diǎn)的鄰居信息進(jìn)行聚合，然后進(jìn)行非線性變換得到節(jié)點(diǎn)的表示，具體的形式如下：

輸入是網(wǎng)絡(luò)的鄰接矩陣A∈RN×N和節(jié)點(diǎn)的屬性矩陣X∈RN×D，V是圖G的節(jié)點(diǎn)集，N是網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，是鄰接矩陣A對(duì)應(yīng)的標(biāo)準(zhǔn)化拉普拉斯矩陣，WD×F是對(duì)應(yīng)的權(quán)重矩陣，σ表示激活函數(shù)（這里指Softmax），H是一次迭代的輸出，即原網(wǎng)絡(luò)節(jié)點(diǎn)的低維表示。在神經(jīng)網(wǎng)絡(luò)的一次迭代過程中，節(jié)點(diǎn)vi的表示聚合了其一階鄰居的信息，最后通過激活函數(shù)得到節(jié)點(diǎn)的低維表示，對(duì)于每個(gè)節(jié)點(diǎn)，上述過程可表示為：

一個(gè)節(jié)點(diǎn)v的接受域是節(jié)點(diǎn)的一階鄰居構(gòu)成的鄰域。在本文中一個(gè)節(jié)點(diǎn)v的接受域是指和v包含在同一類型模體中的節(jié)點(diǎn)，如圖2 所示。類似于鄰接矩陣，這里也定義了同質(zhì)網(wǎng)絡(luò)的模體鄰接矩陣。

式（3）是模體S到AM的一個(gè)映射，AM是一個(gè)矩陣。IS(u)是一個(gè)示性函數(shù)，如果u∈S,則IS(u)=1,否則為0。定義對(duì)角矩陣DM∈RN×N，對(duì)角線上的第i元素是包含第i個(gè)節(jié)點(diǎn)的模體M的個(gè)數(shù)，也即。通常對(duì)于一個(gè)給定的機(jī)器學(xué)習(xí)任務(wù)，需要綜合考慮多個(gè)相關(guān)的模體結(jié)構(gòu)，一類模體代表一種結(jié)構(gòu)特征，然而對(duì)給定的數(shù)據(jù)挖掘任務(wù)通常需要多個(gè)方面的特征，本文采用多類模體的信息構(gòu)建神經(jīng)網(wǎng)絡(luò)。

3 基于模體圖神經(jīng)網(wǎng)絡(luò)的鏈路預(yù)測(cè)模型

3.1 模體圖神經(jīng)網(wǎng)絡(luò)

本文引入一個(gè)基于模體的空間卷積操作來提取節(jié)點(diǎn)的特征[18]。給定模體M以及目標(biāo)節(jié)點(diǎn)vi，設(shè)輸入節(jié)點(diǎn)的是1 維向量，經(jīng)過映射之后的節(jié)點(diǎn)的維度F=1。定義節(jié)點(diǎn)vi權(quán)重矩陣w0及其鄰居節(jié)點(diǎn)vj的權(quán)重wj，則節(jié)點(diǎn)v處的卷積可定義為與節(jié)點(diǎn)vi基于模體M的模體鄰居的加權(quán)和，即：

其中，xi、xj表示節(jié)點(diǎn)vi、vj的屬性向量。hM(vi)表示節(jié)點(diǎn)vi的卷積輸出，σ(·)表示激活函數(shù)，例如ReLU(·)或Softmax(·)，權(quán)重共享過程就是賦予節(jié)點(diǎn)vi的模體鄰居相同的權(quán)重。進(jìn)而可將上式的情況推廣到一般情形：節(jié)點(diǎn)的屬性矩陣X為N×D維的矩陣，輸出維度為F，則有：

其中，WM是權(quán)重矩陣，HM是在模體M下的卷積輸出。由于在表示每個(gè)節(jié)點(diǎn)的過程中，單類模體的特征信息不能充分地表示節(jié)點(diǎn)，有必要綜合多類模體的信息。但在聚合的過程中不同類型的模體對(duì)每個(gè)節(jié)點(diǎn)的重要性各不相同，為了體現(xiàn)卷積過程中各類模體對(duì)節(jié)點(diǎn)表示的不同影響，本文加入模體的注意力機(jī)制[18]。

式中，U是模體的個(gè)數(shù)，ek,i=α(hk(vi))=W·hk(vi)是關(guān)于hk(vi)的一維卷積，注意力系數(shù)αk,i反映了模體Mk對(duì)于節(jié)點(diǎn)vi的重要性，hk(vi)是節(jié)點(diǎn)vi在Mk下的卷積輸出。本文將模體圖神經(jīng)網(wǎng)絡(luò)模型簡(jiǎn)稱為MGNN（motif-based graph neural network），其網(wǎng)絡(luò)架構(gòu)如圖3 所示。經(jīng)過對(duì)不同類模體的卷積的聚合，在激活層連接注意力網(wǎng)絡(luò)，這兩部分構(gòu)成一個(gè)基本神經(jīng)網(wǎng)絡(luò)單元，進(jìn)而逐層迭代。最后對(duì)卷積層聚合各類模體的卷積輸出之后，通過全連接網(wǎng)絡(luò)得到最終節(jié)點(diǎn)的表示。

圖3 MGNN 的深度圖神經(jīng)網(wǎng)絡(luò)框架Fig.3 Deep graph neural network framework MGNN

3.2 圖自編碼器

本文的模型采用了自編碼器VGAE（variational graph auto-encoders）[20]結(jié)構(gòu)，自編碼器是通過編碼器和解碼器結(jié)構(gòu)對(duì)節(jié)點(diǎn)進(jìn)行表示的一種無監(jiān)督學(xué)習(xí)方式，以網(wǎng)絡(luò)鄰接矩陣A和屬性矩陣X作為輸入，編碼器采用的是模體圖神經(jīng)網(wǎng)絡(luò)模型（MGNN），對(duì)編碼以后的向量做內(nèi)積運(yùn)算作為解碼器，給出連邊的預(yù)測(cè)值，最后選取交叉熵作為損失函數(shù)進(jìn)行梯度反傳（結(jié)構(gòu)如圖4 所示）。本文的算法流程如下：

圖4 圖自編碼器的結(jié)構(gòu)框架Fig.4 Architecture of GAE

算法1結(jié)合圖自編碼器的模體圖卷積網(wǎng)絡(luò)模型

3.3 復(fù)雜度分析

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

本文提出了基于同質(zhì)網(wǎng)絡(luò)的MGNN 的鏈路預(yù)測(cè)模型，并且在幾個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)集驗(yàn)證了方法的有效性。訓(xùn)練過程中，數(shù)據(jù)集的部分鏈接（正類邊）已被刪除，而所有節(jié)點(diǎn)特征保持不變。用移除的邊和相同數(shù)量的隨機(jī)抽樣的未連接節(jié)點(diǎn)對(duì)（負(fù)類邊）形成驗(yàn)證集和測(cè)試集。根據(jù)模型正確區(qū)分正類邊和負(fù)類邊的能力來比較模型。驗(yàn)證集和測(cè)試集分別包含5%和10%的引文鏈接，剩余作為訓(xùn)練集。驗(yàn)證集用于優(yōu)化超參數(shù)。用glorot 方法初始化神經(jīng)網(wǎng)絡(luò)權(quán)重，學(xué)習(xí)率為0.001，神經(jīng)網(wǎng)絡(luò)的層數(shù)為3 層，一次實(shí)驗(yàn)訓(xùn)練200輪，每個(gè)數(shù)據(jù)集訓(xùn)練20次，計(jì)算平均值和方差。

4.1 度量標(biāo)準(zhǔn)

本文使用的鏈路預(yù)測(cè)的度量指標(biāo)為AUC（area under the curve of ROC）和AP（average precision）。AUC 是ROC 曲線下方的面積，AP 是平均準(zhǔn)確率。AUC 值至少大于0.5，AUC 的值越高，算法的精確度越高，但AUC 的值最高不超過1。AP 是在不同召回率下準(zhǔn)確率的加權(quán)平均，取值越高表明算法精度越高，同樣不超過1。

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

本文將在Cora、CiteSeer、PubMed 3 個(gè)數(shù)據(jù)集上測(cè)試提出的方法。下面從數(shù)據(jù)集大小和數(shù)據(jù)特點(diǎn)等方面分別介紹這3 個(gè)數(shù)據(jù)集。

Cora 數(shù)據(jù)集共2 708 個(gè)樣本點(diǎn)，每個(gè)樣本點(diǎn)都是一篇科學(xué)論文，每篇論文都由一個(gè)1 433 維的詞向量表示。

CiteSeer 數(shù)據(jù)集是從CiteSeer 數(shù)字論文圖書館中選取的一部分論文，整個(gè)語(yǔ)料庫(kù)共有3 327 篇論文，在詞干提取和刪除停止詞之后，只剩下3 703個(gè)單詞。

PubMed 數(shù)據(jù)集包括來自PubMed 數(shù)據(jù)庫(kù)的19 717 篇關(guān)于糖尿病的科學(xué)出版物。引文網(wǎng)絡(luò)由44 338 個(gè)鏈接組成。數(shù)據(jù)集中的每個(gè)出版物都由一個(gè)由500 個(gè)唯一單詞組成的字典中的TF/IDF 加權(quán)詞向量來描述。

用mfinder 軟件給出每個(gè)網(wǎng)絡(luò)的模體分布情況（如表2 所示）。為進(jìn)一步提高計(jì)算效率，選取網(wǎng)絡(luò)中包含3 個(gè)節(jié)點(diǎn)和4 個(gè)節(jié)點(diǎn)的模體。

表2 3 個(gè)數(shù)據(jù)集各類模體的比例Table 2 Proportion of various motifs in 3 datasets 單位：%

4.3 結(jié)果

本節(jié)選取幾個(gè)算法進(jìn)行對(duì)比實(shí)驗(yàn)，分別是MGNN、VGAE[2]、node2vec[9]、LINE[10]、DeepWalk[8]、DeepLinker[22]，MGNN 表示本文結(jié)合自編碼器的方法，VMGNN 表示本文方法與變分自編碼器結(jié)合的方法，(*)表示網(wǎng)絡(luò)輸入僅考慮拓?fù)湫畔⒍话瑢傩孕畔?。Deep-Walk、LINE、node2vec 是基于拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)嵌入的方法，結(jié)合隨機(jī)游走和Skip-gram 的思想給出節(jié)點(diǎn)的表示。VGAE 是結(jié)合圖卷積網(wǎng)絡(luò)和自編碼器的模型，在鏈路預(yù)測(cè)上取得了較好的效果。DeepLinker 是基于圖注意力網(wǎng)絡(luò)的鏈路預(yù)測(cè)模型，在鏈路預(yù)測(cè)上取得了較好的表現(xiàn)。在此情況下，網(wǎng)絡(luò)的輸入矩陣包括鄰接矩陣和維度為節(jié)點(diǎn)數(shù)的單位矩陣，實(shí)驗(yàn)過程中主要選取模體M31、M32、M42構(gòu)建模型。

4.4 實(shí)驗(yàn)描述和總結(jié)

實(shí)驗(yàn)結(jié)果如表3 所示，在兩個(gè)數(shù)據(jù)集上結(jié)合高階結(jié)構(gòu)信息之后本文方法在大部分網(wǎng)絡(luò)上能夠得到網(wǎng)絡(luò)節(jié)點(diǎn)的更好的表示，鏈路預(yù)測(cè)的結(jié)果較傳統(tǒng)方法提升了1%～4%。同時(shí)在PubMed 數(shù)據(jù)集上的預(yù)測(cè)結(jié)果略低于VGAE，由于考慮了節(jié)點(diǎn)的模體結(jié)構(gòu)信息，模體的數(shù)目未必服從正態(tài)分布，因此自編碼器在某些情況下的實(shí)驗(yàn)結(jié)果會(huì)低于變分自編碼器對(duì)應(yīng)的結(jié)果。

表3 基于MGNN 的鏈路預(yù)測(cè)實(shí)驗(yàn)結(jié)果Table 3 Experimental results of link prediction modes based on MGNN 單位：%

4.5 消融實(shí)驗(yàn)

本節(jié)將本文方法和VGAE 以及MGNN+MLP（全連接網(wǎng)絡(luò)）進(jìn)行了對(duì)比，VGAE 將圖卷積網(wǎng)絡(luò)GCN 和自編碼器相結(jié)合，在鏈路預(yù)測(cè)任務(wù)中取得了很好的效果。MGNN+MLP 是在MGNN 網(wǎng)絡(luò)之后鏈接了全連接網(wǎng)絡(luò)MLP，以說明本文的模型MGNN+Attention的有效性。結(jié)果如圖5 所示。

圖5 MGNN+Attention、MGNN+MLP、VGAE對(duì)比實(shí)驗(yàn)Fig.5 Comparison of results on MGNN+Attention,MGNN+MLP and VGAE

實(shí)驗(yàn)結(jié)果表明，本文模型在大部分情形下優(yōu)于其他兩類模型，進(jìn)一步說明模型中融入模體結(jié)構(gòu)可有效提高神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)能力。同時(shí)MGNN+MLP與MGNN+Attention 的對(duì)比，也驗(yàn)證了MGNN 網(wǎng)絡(luò)中鏈接注意力網(wǎng)絡(luò)的有效性，說明在節(jié)點(diǎn)表示的過程中，需要考慮不同模體的重要性。

4.6 實(shí)驗(yàn)效率對(duì)比

本節(jié)給出了各個(gè)模型在網(wǎng)絡(luò)Cora 和CiteSeer 上鏈路預(yù)測(cè)任務(wù)的運(yùn)行時(shí)間對(duì)比，本文采用的實(shí)驗(yàn)環(huán)境是Ubuntu 16.04，CPU 為Intel?Xeon CPU E5-2620 v2@2.10 GHz，內(nèi)存容量48 GB，圖6 給出了6 個(gè)相應(yīng)算法的運(yùn)行效率對(duì)比圖。

圖6 在Cora 和CiteSeer兩個(gè)數(shù)據(jù)集上算法效率對(duì)比Fig.6 Efficiency comparison of algorithms on Cora and CiteSeer datasets

如圖6 所示，基于圖表示學(xué)習(xí)的淺層網(wǎng)絡(luò)模型運(yùn)行效率較高，但此類模型很難學(xué)習(xí)到網(wǎng)絡(luò)中節(jié)點(diǎn)的復(fù)雜結(jié)構(gòu)信息。本文方法結(jié)合了多層的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)以及高階的模體信息，盡管計(jì)算成本較高，但在鏈路預(yù)測(cè)的指標(biāo)上較圖表示學(xué)習(xí)的方法取得了較大幅度提升。同時(shí)由于模型采用了自編碼器框架，運(yùn)行時(shí)間與圖自編碼器（VGAE）等模型的運(yùn)行時(shí)間接近。

5 結(jié)束語(yǔ)

本文提出了一種基于同質(zhì)網(wǎng)絡(luò)的模體圖神經(jīng)網(wǎng)絡(luò)鏈路預(yù)測(cè)模型，在圖卷積網(wǎng)絡(luò)的基礎(chǔ)上結(jié)合了網(wǎng)絡(luò)的高階結(jié)構(gòu)-模體的信息，結(jié)合每一種模體結(jié)構(gòu)給出了節(jié)點(diǎn)的表示，并進(jìn)一步考慮了各類模體對(duì)于節(jié)點(diǎn)的注意力權(quán)重，最后利用節(jié)點(diǎn)的表示重構(gòu)網(wǎng)絡(luò)。在幾個(gè)常規(guī)的引文數(shù)據(jù)集的鏈路預(yù)測(cè)任務(wù)上驗(yàn)證了算法的有效性。在大規(guī)模的網(wǎng)絡(luò)中計(jì)算效率和準(zhǔn)確度有待進(jìn)一步改善。

在模型的訓(xùn)練過程中，MGNN 用到了節(jié)點(diǎn)的高階模體信息，模型的計(jì)算成本有一定的增加，后續(xù)的研究考慮采取適當(dāng)?shù)牟蓸臃椒▉斫档湍Ｐ偷膹?fù)雜度。