基于圖注意力和特征融合的鏈路預(yù)測(cè)方法

李峰 王俊峰 陳虹呂

摘要：?鏈路預(yù)測(cè)是一種還原網(wǎng)絡(luò)缺失信息的方法，通過(guò)當(dāng)前已觀察到的鏈路，預(yù)測(cè)實(shí)際存在但未被觀察到的鏈路或可能出現(xiàn)的新鏈路.當(dāng)前鏈路預(yù)測(cè)主要是基于圖神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)方法，相比基于規(guī)則的啟發(fā)式方法，前者可有效利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，較大地提升了網(wǎng)絡(luò)鏈路預(yù)測(cè)性能，并可應(yīng)用到類(lèi)型更廣泛的網(wǎng)絡(luò)中.但是現(xiàn)有基于圖神經(jīng)網(wǎng)絡(luò)的方法，僅利用網(wǎng)絡(luò)中節(jié)點(diǎn)相對(duì)位置信息，忽視了節(jié)點(diǎn)基本屬性和鏈路的鄰居信息，且無(wú)法區(qū)分不同節(jié)點(diǎn)對(duì)鏈路形成的重要程度.為此，本文提出一種基于圖注意力網(wǎng)絡(luò)和特征融合的鏈路預(yù)測(cè)方法.通過(guò)增加節(jié)點(diǎn)的度、鏈路的共同鄰居數(shù)量和共同鄰居最大度等特征，豐富了網(wǎng)絡(luò)的輸入特征信息.本文首先提取以目標(biāo)節(jié)點(diǎn)對(duì)為中心的子圖，然后將其轉(zhuǎn)化為對(duì)應(yīng)的線圖，線圖中的節(jié)點(diǎn)和原圖中的鏈路一一對(duì)應(yīng)，從而將原圖節(jié)點(diǎn)和鏈路信息融合到線圖的節(jié)點(diǎn)中，提升了特征融合的有效性和可解釋性.同時(shí)本文使用圖注意力機(jī)制學(xué)習(xí)節(jié)點(diǎn)的權(quán)重，增強(qiáng)了特征融合的靈活性.實(shí)驗(yàn)表明，本文所提出的方法，在多個(gè)不同領(lǐng)域數(shù)據(jù)集上的AUC和AP均超過(guò)90%，在已觀測(cè)鏈路缺失較多時(shí)，預(yù)測(cè)性能保持80%以上，且均優(yōu)于現(xiàn)有最新方法.

關(guān)鍵詞：鏈路預(yù)測(cè); 圖神經(jīng)網(wǎng)絡(luò); 線圖; 特征融合; 圖注意力

中圖分類(lèi)號(hào)：??TP301.6? 文獻(xiàn)標(biāo)識(shí)碼：A? ?DOI：10.19907/j.0490-6756.2023.052002

收稿日期： ?2022-08-27

基金項(xiàng)目： ??基礎(chǔ)加強(qiáng)計(jì)劃重點(diǎn)項(xiàng)目（2019-JCJQ-ZD-113）； 國(guó)家自然科學(xué)基金（U2133208）； 四川省青年科技創(chuàng)新研究團(tuán)隊(duì)（2022JDTD0014）

作者簡(jiǎn)介： ??李峰（1994-）， 安徽阜陽(yáng)人， 碩士研究生， 研究方向?yàn)榫W(wǎng)絡(luò)空間安全. E-mail： 2807229316@qq.com

通訊作者： ?王俊峰. E-mail：wangjf@scu.edu.cn

Graph attention based feature fusion for link prediction

LI Feng， WANG Jun-Feng， CHEN Hong-Lü

（College of Computer Science， Sichuan University， Chengdu 610065， China）

Link prediction is a method to restore the missing information of a network by predicting the actual but unobserved links or possible new links from the observed links. Currently， link prediction is mainly based on deep learning methods of graph neural networks， which compared with rule-based heuristics， can effectively utilize the network topology information， greatly improves the performance of network link prediction and can be applied to a wider range of network types. However， the existing graph neural network-based methods only use the relative position information of nodes in the network， ignore the basic attributes of nodes and the neighboring information of links， and cannot distinguish the importance of different nodes to the formation of links. To addess these limitation， this paper proposes a link prediction method based on graph attention network and feature fusion， the input features of the network are enriched by adding features such as the degree of nodes， the number of common neighbors of links and the maximum degree of common neighbors. This method ?first extracts the subgraph centered on the target node pair， and then transforms it into a corresponding line graph， where the nodes in the line graph correspond to the links in the original graph， thus fusing the nodes and link information of the original graph into the nodes of the line graph， which improves the effectiveness and interpretability of feature fusion. Meanwhile， the proposed method uses the graph attention mechanism to learn the weights of nodes， which enhances the flexibility of feature fusion. Experimental results on various network datasets show that the proposed method achieves over 90% in terms of AUC and AP， outperforming existing state-of-the-art methods. Moreover， the method maintains more than 80% prediction performance even when there are many missing observed links.

Link prediction; Graph neural network; Line graph; Feature fusion; Graph attention

1 引 言

網(wǎng)絡(luò)是分析復(fù)雜系統(tǒng)的有力工具 ?［1］ ，用于建模實(shí)體間的交互關(guān)系.然而由于客觀條件的限制，已觀測(cè)的網(wǎng)絡(luò)大多是不完整的 ?［2］ .為了解決網(wǎng)絡(luò)信息缺失問(wèn)題，形成了鏈路預(yù)測(cè)方法.其通過(guò)當(dāng)前已觀察到的鏈路，預(yù)測(cè)缺失的鏈路或可能出現(xiàn)的新鏈路，推斷網(wǎng)絡(luò)形成過(guò)程 ?［3］ ，補(bǔ)全網(wǎng)絡(luò)信息.在許多現(xiàn)實(shí)領(lǐng)域中，鏈路預(yù)測(cè)得到了廣泛應(yīng)用.例如：社交網(wǎng)絡(luò)中的好友推薦 ?［4］ ，電子商務(wù)網(wǎng)站中的商品推薦 ?［5-7］ ，知識(shí)圖譜補(bǔ)全 ?［8］ 和代謝網(wǎng)絡(luò)重建 ?［9］ 等.然而這些現(xiàn)實(shí)應(yīng)用受到了鏈路預(yù)測(cè)性能的制約.如何進(jìn)一步提高預(yù)測(cè)性能，成為鏈路預(yù)測(cè)實(shí)際應(yīng)用的關(guān)鍵.

近年來(lái)，圖神經(jīng)網(wǎng)絡(luò)在處理圖結(jié)構(gòu)數(shù)據(jù)取得了較大成功，為提升鏈路預(yù)測(cè)性能提供了有效途徑.SEAL ?［10］ 證明了大多數(shù)手動(dòng)設(shè)計(jì)的啟發(fā)式規(guī)則，都可以從局部子圖得到很好近似，并提出使用圖神經(jīng)網(wǎng)絡(luò)自動(dòng)學(xué)習(xí)一個(gè)合適的啟發(fā)式規(guī)則.但所使用的平均池化策略 ?［11］ 不可避免地會(huì)導(dǎo)致信息丟失.LGLP ?［12］ 則在前者的基礎(chǔ)上進(jìn)行了改進(jìn)，提出了將原始子圖轉(zhuǎn)化為對(duì)應(yīng)線圖的方法.線圖和原圖在數(shù)學(xué)上是等價(jià)的，轉(zhuǎn)換過(guò)程不存在信息丟失.同時(shí)原圖的鏈路特征可由線圖對(duì)應(yīng)的節(jié)點(diǎn)直接獲得，無(wú)需使用圖池化操作.盡管LGLP模型進(jìn)一步提升了鏈路預(yù)測(cè)性能，但仍存在一定的不足.首先，其輸入到神經(jīng)網(wǎng)絡(luò)的原始特征，僅僅是子圖中節(jié)點(diǎn)間相對(duì)位置的編碼，所提供的信息過(guò)于單一.其次，該方法在特征學(xué)習(xí)過(guò)程中，采用固定的模式聚集鄰居節(jié)點(diǎn)特征，忽視了不同節(jié)點(diǎn)的重要程度.

為了解決上述問(wèn)題，本文提出了一種基于圖注意力和特征融合的鏈路預(yù)測(cè)方法（Graph Attention based Feature Fusion，AFF ）. 通過(guò)增加更多節(jié)點(diǎn)和鏈路屬性，豐富輸入神經(jīng)網(wǎng)絡(luò)的原始特征.所增加的屬性均為一階鄰居信息，計(jì)算代價(jià)小且可解釋性強(qiáng).另外本文使用圖注意力網(wǎng)絡(luò)（GATs） ?［13］ 搭建了新的特征學(xué)習(xí)模塊，通過(guò)注意力機(jī)制，自動(dòng)學(xué)習(xí)鄰居節(jié)點(diǎn)權(quán)重，增強(qiáng)節(jié)點(diǎn)特征聚集的靈活性.同時(shí)本文利用線圖轉(zhuǎn)化，將原圖中節(jié)點(diǎn)屬性和鏈路屬性統(tǒng)一融合到線圖節(jié)點(diǎn)特征中，將鏈路預(yù)測(cè)問(wèn)題轉(zhuǎn)化為節(jié)點(diǎn)分類(lèi)問(wèn)題. 本文在7個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，分類(lèi)性能指標(biāo)AUC和AP達(dá)90%以上，超過(guò)現(xiàn)有對(duì)比方法，有效地提升了鏈路預(yù)測(cè)性能.

2 相關(guān)工作

鏈路預(yù)測(cè)作為網(wǎng)絡(luò)分析的重要組成部分，近年來(lái)學(xué)界提出了各種鏈路預(yù)測(cè)方法.按照判定鏈路存在性標(biāo)準(zhǔn)的不同，鏈路預(yù)測(cè)方法可分為：基于規(guī)則的啟發(fā)式方法、基于相似性的節(jié)點(diǎn)嵌入方法和基于分類(lèi)的圖神經(jīng)網(wǎng)絡(luò)方法.

2.1 啟發(fā)式方法

基于規(guī)則的啟發(fā)式方法大多采用預(yù)先定義的可能性指標(biāo)，作為判斷鏈路是否存在的依據(jù)，指標(biāo)的設(shè)計(jì)通常是基于一定的假設(shè).按照計(jì)算過(guò)程中需要使用到的節(jié)點(diǎn)最大鄰居跳數(shù)（hop），該類(lèi)方法又可細(xì)分為：一階、二階和高階啟發(fā)式方法.其計(jì)算代價(jià)也是逐漸遞增的.共同鄰居（Common Neighbor， CN） ?［14］ 和優(yōu)先連接（Preferential Attachment， PA） ?［15］ 就是典型的一階啟發(fā)式方法，因?yàn)槠溆?jì)算僅需要一跳鄰居的節(jié)點(diǎn).類(lèi)似的，二階啟發(fā)式方法則最多使用二跳鄰居的節(jié)點(diǎn)，如AA指標(biāo)（Adamic-Adar，AA） ?［16］ 和資源分配指標(biāo)（Resource Allocation， RA） ?［17］ .而高階啟發(fā)式方法則用到了全圖所有的節(jié)點(diǎn)，卡茨指標(biāo)（Katz） ?［18］ 、SimRank ?［19］ 和rooted PageRank ?［20］ 屬于該類(lèi)方法，比起前兩類(lèi)方法，高階啟發(fā)方法的預(yù)測(cè)性能更好，但是計(jì)算代價(jià)也更高.

2.2 節(jié)點(diǎn)嵌入方法

基于相似性的節(jié)點(diǎn)嵌入方法，通過(guò)從整個(gè)網(wǎng)絡(luò)拓?fù)渲袑W(xué)習(xí)節(jié)點(diǎn)嵌入（embedding），計(jì)算節(jié)點(diǎn)間的相似性，相似性較高則認(rèn)為節(jié)點(diǎn)間存在鏈路.借鑒自然語(yǔ)言處理領(lǐng)域的詞嵌入方法，Deepwalk ?［21］ 、LINE ?［22］ 和node2vec ?［23］ 被相繼提出.然而該類(lèi)方法在網(wǎng)絡(luò)較為稀疏時(shí)，預(yù)測(cè)性能會(huì)受到較大影響.

2.3 圖神經(jīng)網(wǎng)絡(luò)方法

基于分類(lèi)的圖神經(jīng)網(wǎng)絡(luò)方法是目前主流的鏈路預(yù)測(cè)方法，通過(guò)有監(jiān)督學(xué)習(xí)的方式，讓網(wǎng)絡(luò)模型自動(dòng)學(xué)習(xí)得到鏈路的分布規(guī)律.SEAL ?［10］ 將以目標(biāo)節(jié)點(diǎn)為中心的子圖編碼成特征矩陣，然后通過(guò)排序池化得到固定大小的向量，將問(wèn)題轉(zhuǎn)化為子圖分類(lèi)問(wèn)題.沿用該思想，相關(guān)的改進(jìn)方法不斷被提出.SHFF ?［24］ 進(jìn)一步考慮了子圖的層次化結(jié)構(gòu)，提出層次化聚集節(jié)點(diǎn)特征得到子圖表示.ARCLink ?［25］ 利用Re-weight操作為網(wǎng)絡(luò)中每個(gè)鏈路賦予0-1的權(quán)值，通過(guò)選取權(quán)值較大的鏈路，減少子圖提取的盲目性.

圖神經(jīng)網(wǎng)絡(luò)的方法在各種網(wǎng)絡(luò)數(shù)據(jù)集上都有較為優(yōu)異的性能表現(xiàn)，但其對(duì)節(jié)點(diǎn)間交互關(guān)系的挖掘大多聚焦于節(jié)點(diǎn)特征上，如相對(duì)位置，沒(méi)有更全面地綜合鏈路特征，如共同鄰居數(shù)量和共同鄰居最大度.本文通過(guò)線圖轉(zhuǎn)化將節(jié)點(diǎn)和鏈路特征有效融合，并利用圖注意力機(jī)制以更靈活的模式進(jìn)行特征學(xué)習(xí)，從而達(dá)到更高的鏈路預(yù)測(cè)性能.

3 AFF方法

3.1 問(wèn)題定義

本文中的網(wǎng)絡(luò)采用無(wú)向無(wú)權(quán)圖進(jìn)行建模.對(duì)于給定的無(wú)向網(wǎng)絡(luò) G ，可以表示為 G=（V，E o，E p） .其中 V 代表節(jié)點(diǎn)集合; E o 表示當(dāng)前已觀測(cè)到的鏈路; E ?p ?表示所有未觀測(cè)到的鏈路.鏈路預(yù)測(cè)就是通過(guò)當(dāng)前觀測(cè)到的信息 （V，E o） ，去預(yù)測(cè) E ?p ?中鏈路的存在性. （u，v） 表示節(jié)點(diǎn) u 和 v 組成的節(jié)點(diǎn)對(duì)，當(dāng)前基于分類(lèi)的鏈路預(yù)測(cè)方法一般先提取以 （u，v） 為中心的子圖，然后將子圖中所編碼的信息用于判斷鏈路存在性.若 f 表示某種鏈路預(yù)測(cè)方法， Φ 表示節(jié)點(diǎn)對(duì)構(gòu)成的鏈路是否存在， t 表示分類(lèi)閾值，則鏈路預(yù)測(cè)問(wèn)題可以形式化表示為：

Φ （u，v） = ?1， f （u，v） ≥t 0， f （u，v）

3.2 模型架構(gòu)

本文AFF方法的總體架構(gòu)如圖1所示.主要由三個(gè)模塊組成：基于線圖轉(zhuǎn)化的特征融合模塊、基于圖注意力的特征學(xué)習(xí)模塊和用于判斷存在性的分類(lèi)模塊.對(duì)于給定的 （u，v） ，首先會(huì)以 （u，v） 為中心提取其周?chē)?h 跳子圖 ?G ??h ??u，v ?，經(jīng)實(shí)驗(yàn)驗(yàn)證， ?h =2 是預(yù)測(cè)性能和計(jì)算代價(jià)的平衡點(diǎn).然后會(huì)給子圖中的所有節(jié)點(diǎn)賦予原始特征，即節(jié)點(diǎn)打標(biāo)（node labeling）.接著利用線圖轉(zhuǎn)化實(shí)現(xiàn)節(jié)點(diǎn)和鏈路特征的有效融合.最后將 ?G ??h ??u，v ?編碼為包含所有節(jié)點(diǎn)原始信息的特征矩陣 ??G ??h ??u，v ???. 特征學(xué)習(xí)模塊包含兩層圖注意力層，利用多頭注意力機(jī)制學(xué)習(xí)節(jié)點(diǎn)權(quán)重，實(shí)現(xiàn)節(jié)點(diǎn)特征靈活聚集.此時(shí) ??G ??h ??u，v ???就轉(zhuǎn)化為聚集后的特征矩陣 ???G ??h ??u，v ????? ?，通常會(huì)對(duì)其進(jìn)行池化操作，降維成一個(gè)表征 （u，v） 的特征向量.但是由于本文之前采用了線圖轉(zhuǎn)化，所以可直接從特征矩陣中取出 （u，v） 對(duì)應(yīng)的特征向量 ??v ??h ??u，v ???，從而避免圖池化帶來(lái)的信息損失.最后的分類(lèi)器根據(jù) ??v ??h ??u，v ???輸出 （u，v） 的得分，用于判斷 （u，v） 對(duì)應(yīng)的鏈路是否存在.

3.3 特征融合

特征融合模塊主要實(shí)現(xiàn)原始特征的提取與融合，將網(wǎng)絡(luò)拓?fù)湫畔⒕幋a成特征矩陣.主要包括以下流程：子圖提取，節(jié)點(diǎn)打標(biāo)和線圖轉(zhuǎn)化.

3.3.1 子圖提取 ?對(duì)于節(jié)點(diǎn)對(duì) （u，v） ，其 h 跳子圖 ?G ??h ??u，v ?可以表述為：節(jié)點(diǎn) u 和 v 各自 h 跳鄰居節(jié)點(diǎn)的并集及其所關(guān)聯(lián)的邊構(gòu)成的圖.可形式化表示為式（2）.

G ??h ??u，v = ?Θ ???G ??Γ ??h ?u ∪ Γ ??h ?v ???（2）

其中， ?Γ ??h （x） 表示到節(jié)點(diǎn) x 最短路徑長(zhǎng)度小于等于 h 的所有節(jié)點(diǎn)集合; ??Θ ???G ?V ?表示由節(jié)點(diǎn)集 V 推導(dǎo)出的 G 的子圖.具體流程由算法1所示.

算法1： ????h -hop子圖提取

Input： ??（u，v） 目標(biāo)節(jié)點(diǎn)對(duì)，原網(wǎng)絡(luò) G ，跳數(shù) h

Output： ???G ??h ??u，v ?，以 （u，v） 為中心的 h 跳子圖

1） procedure SubgraphExtract（ （u，v） ）

2） ?V←u，v ，使用節(jié)點(diǎn) u 和 v 初始化節(jié)點(diǎn)集

3） ?d←1 ，初始化最短路徑長(zhǎng)度

4） while ?d

5） ??V←∪ ?i∈V ??Γ ??1 （i）∪V

6） end while

7） for any 節(jié)點(diǎn) i，j∈V ?do

8） ?if ??e ??i，j ∈G .edges then

9） ???E←E+ e ??i，j

10） ?end if

11） end for

12） ???G ??h ??u，v ?←induced （V，E）

13） ?return ??G ??h ??u，v

14） end procedure

3.3.2 節(jié)點(diǎn)打標(biāo) ?在對(duì)子圖進(jìn)行特征學(xué)習(xí)之前，需要為子圖中的每個(gè)節(jié)點(diǎn)賦予一定的屬性（原始特征）.該原始特征豐富程度和判別能力會(huì)對(duì)最終的鏈路預(yù)測(cè)結(jié)果有較大影響.因此本文提出使用更加豐富的節(jié)點(diǎn)和鏈路特征：對(duì)于節(jié)點(diǎn)，增加了節(jié)點(diǎn)的度這一基本屬性;對(duì)于鏈路，增加了共同鄰居數(shù)量和共同鄰居的最大度這兩個(gè)基本屬性.上述三種屬性可形式化為式（3）.

D ??v =size ?Γ ??1 （v） ??（3）

其中， ?D ??v ?表示節(jié)點(diǎn) v 的度； ?Γ ??1 （v） 是節(jié)點(diǎn) v 一階鄰居的集合.

N ??u，v =size ?Γ ??1 ?u ∩ Γ ??1 ?v ???（4）

其中， ?N ??u，v ?表示節(jié)點(diǎn)對(duì) （u，v） 的共同鄰居數(shù)量.

M ??u，v = ?max ???x∈ ?Γ ???1 （u）∩ ?Γ ???1 （v） ??D ??x ??（5）

其中， ?M ??u，v ?表示節(jié)點(diǎn)對(duì) （u，v） 的共同鄰居最大度.

為了描述全局拓?fù)湫畔?，本文還對(duì)子圖中所有節(jié)點(diǎn)與中心節(jié)點(diǎn)的相對(duì)位置進(jìn)行了編碼.具體計(jì)算如式（6）所示.

f ??l ?i =1+ min ??d ??u ， d ??v ?+

d 2 ???d 2 +d%2-1 ??（6）

其中， ?f ??l （i） 表示子圖中任意節(jié)點(diǎn) i 的標(biāo)簽值; ?d ??u ?和 ?d ??v ?分別表示節(jié)點(diǎn) i 到中心節(jié)點(diǎn)對(duì) （u，v） 的最短路徑長(zhǎng)度， d= d ??u + d ??v ， d 2 ?和 d%2 表示 d 除以2的商和余數(shù).另外規(guī)定： ?f ??l （u）=1， f ??l （v）=1 .對(duì)于 ?d ??u →∞ 或 ?d ??v →∞ 時(shí)， ?f ??l （i）=0 .至于編碼值的大小并無(wú)任何含義，所以實(shí)際使用時(shí)需要將其轉(zhuǎn)化為獨(dú)熱編碼（one-hot）向量.

3.3.3 線圖轉(zhuǎn)化 ?圖神經(jīng)網(wǎng)絡(luò)能夠很好地學(xué)習(xí)節(jié)點(diǎn)特征，卻很少關(guān)注鏈路特征.所以當(dāng)前方法 ?［24，25］ 為了學(xué)習(xí)鏈路特征，一般是對(duì)子圖的節(jié)點(diǎn)特征矩陣進(jìn)行池化，這不可避免地導(dǎo)致了信息丟失.另外使用的點(diǎn)邊特征相對(duì)孤立，無(wú)法充分利用圖神經(jīng)網(wǎng)絡(luò)的優(yōu)勢(shì).為了解決以上問(wèn)題，本文采用了線圖轉(zhuǎn)化的方法.

線圖（Line Graph）是表示網(wǎng)絡(luò)的另一種數(shù)學(xué)模型，它和原圖是等價(jià)的，并可相互轉(zhuǎn)化且不會(huì)有信息損失.二者的關(guān)系是：線圖中的節(jié)點(diǎn)表示的是原圖中的邊，若原圖中兩條邊存在公共節(jié)點(diǎn)，則對(duì)應(yīng)的線圖中節(jié)點(diǎn)存在連接.線圖轉(zhuǎn)化的過(guò)程如圖2所示.

由于在線圖中節(jié)點(diǎn)表示的是原圖中的鏈路，因此通過(guò)圖神經(jīng)網(wǎng)絡(luò)可以直接得到目標(biāo)鏈路特征.此外，在轉(zhuǎn)化過(guò)程中，原圖中的點(diǎn)邊特征可以有效融合到線圖的節(jié)點(diǎn)中.對(duì)于原圖中的節(jié)點(diǎn)信息，本文采用了一種固定模式進(jìn)行拼接，避免因拼接順序的不同而導(dǎo)致的差異，方法如下式所示.

v ????l ??u，v = min ???v ????o ??u ， ?v ????o ??v ?|| max ???v ????o ??u ， ?v ????o ??v ???（7）

其中， ???v ????l ??u，v ?表示轉(zhuǎn)換過(guò)后線圖中節(jié)點(diǎn)特征向量； ???v ????o ??u ?和 ??v ????o ??v ?表示原圖中的節(jié)點(diǎn)特征向量，由節(jié)點(diǎn)的相應(yīng)位置編碼 ?f ??l （v） 和節(jié)點(diǎn)的度 ?D ??v ?組成；‖表示連接操作；min和max采用的是逐位比較的方式.

原圖的鏈路信息，可以直接作為線圖的節(jié)點(diǎn)信息.最終結(jié)果如下所示.

v ????u，v = ?v ????l ??u，v || ?e ????o ??u，v ??（8）

其中， ???e ????o ??u，v ?是原圖 （u，v） 的鏈路特征向量，由 ?N ??u，v ?和 ?M ??u，v ?標(biāo)準(zhǔn)化后合并而成.通過(guò)線圖轉(zhuǎn)化，原圖中節(jié)點(diǎn)特征和鏈路特征融合成線圖中的節(jié)點(diǎn)特征 ???v ????u，v ?，其蘊(yùn)含的信息更加豐富且更具判別力.

3.4 特征學(xué)習(xí)

本文利用圖注意力網(wǎng)絡(luò) ?［13］ 進(jìn)行特征學(xué)習(xí)，如圖3所示.由于進(jìn)行了線圖轉(zhuǎn)化，所以并未使用圖池化層.另外現(xiàn)有方法大多忽視了周?chē)?jié)點(diǎn)的相對(duì)重要性，從而在節(jié)點(diǎn)特征學(xué)習(xí)時(shí)損失了部分信息，GAT使用掩蓋注意力機(jī)制（Masked Attention）自動(dòng)學(xué)習(xí)這種權(quán)重 α .

模型的初始輸入是線圖所有融合后節(jié)點(diǎn)特征矩陣 v ，輸出為 v ′.

v= ??v ????1 ， ?v ????2 ，…， ?v ????N ?， ?v ????i ∈ 瘙綆

F ??（9）

其中， ???v ????i ?表示融合后的線圖特征； N 為線圖中節(jié)點(diǎn)數(shù)； F 為節(jié)點(diǎn)的特征維度大小.

v′= ??v ????1 ′， ?v ????2 ′，…， ?v ????N ′ ， ?v ????i ′∈ 瘙綆

F′ ??（10）

其中， ???v ????i ′ 為模型輸出的特征； F ′為輸出后的特征維度大小.

α ???ij = ?exp ?σ ??a ?????T ?W ?v ?????i ‖W ?v ?????j ?????∑ ???k∈ N ???i ??exp ?σ ??a ?????T ?W ?v ?????i ‖W ?v ?????k ??????（11）

其中，矩陣 W∈ 瘙綆

F× F ?′ ??；向量 ??a ????T ∈ 瘙綆

2F′ ?為可學(xué)習(xí)的參數(shù)； ?N ??i ?為節(jié)點(diǎn) i 的一階鄰居集合（包括節(jié)點(diǎn) i ）；‖表示連接操作； σ 代表LeakyReLU激活函數(shù)，坡度系數(shù)取0.2.最后進(jìn)行softmax操作得到 j 相對(duì)于 i 的權(quán)重.

v ???′ ??i = ?| ????K ??k=1 σ ∑ ?j∈ N ???i ???α ???k ??ij ?W ???k ??v ?????j ???（12）

利用式（11）得到標(biāo)準(zhǔn)化的權(quán)重，將節(jié)點(diǎn)的一階鄰居節(jié)點(diǎn)特征進(jìn)行加權(quán)連接，得到單層網(wǎng)絡(luò)的輸出，為了使注意力學(xué)習(xí)更加穩(wěn)定，采用了多頭注意力， K 代表了head的大小.

v ???′ ??i =σ ?1 K ∑ ?K ??k=1 ??∑ ?j∈ N ???i ???α ???k ??ij ?W ???k ??v ?????j ???（13）

式（13）將式（12）的連接操作改為了求和平均操作，主要考慮用于最后一層時(shí)，連接操作缺乏可解釋性，改為求和操作.

對(duì)于最后的分類(lèi)模塊，本文采用了兩層MLP作為分類(lèi)器，輸出維度分別為128和2.使用交叉熵（Cross-Entropy）作為二分類(lèi)的損失函數(shù).

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

4.1 數(shù)據(jù)集和基準(zhǔn)方法

本文選取了7個(gè)現(xiàn)實(shí)世界中不同領(lǐng)域的真實(shí)網(wǎng)絡(luò)拓?fù)渥鳛閷?shí)驗(yàn)數(shù)據(jù)集，對(duì)所提出的模型AFF進(jìn)行驗(yàn)證.這些數(shù)據(jù)集包括： Celegans ?［26］ ， USAir ?［27］ ， SMG， EML， Power ?［26］ ， Yeast ?［28］ 和GRQ ?［29］ .拓?fù)湫畔⒁?jiàn)表1，具體表示含義如下.

（1） Celegans 線蟲(chóng)的神經(jīng)網(wǎng)絡(luò)，節(jié)點(diǎn)代表神經(jīng)元，鏈路表示神經(jīng)元間的神經(jīng)連接.

（2） USAir美國(guó)航空網(wǎng)絡(luò)，節(jié)點(diǎn)代表航空公司，鏈路表示航空公司之間的航線

（3） EML 郵件共享網(wǎng)絡(luò)，節(jié)點(diǎn)代表用戶，鏈路表示用戶間存在郵件共享.

（4） Power 美國(guó)西部電力網(wǎng)絡(luò)，節(jié)點(diǎn)代表發(fā)電站，鏈路表示電站間電路連接.

（5） Yeast 蛋白質(zhì)間交互網(wǎng)絡(luò)，節(jié)點(diǎn)代表蛋白質(zhì)，鏈路代表蛋白質(zhì)間存在交互.

（6） GRQ SMG 若干領(lǐng)域?qū)W者合著網(wǎng)絡(luò)，節(jié)點(diǎn)代表學(xué)者，鏈路表示存在合著關(guān)系.

使用以上數(shù)據(jù)集，將本文所提出的模型和五個(gè)基準(zhǔn)方法進(jìn)行實(shí)驗(yàn)對(duì)比.主要包括三種基于規(guī)則的方法CommonNeighbor（CN）， SimRank（SR）， rootedPageRank（PR）以及兩種基于深度學(xué)習(xí)的方法SEAL和LGLP.

（1） CN ?［14］ 一種鏈路預(yù)測(cè)的經(jīng)典方法，將兩個(gè)目標(biāo)節(jié)點(diǎn)的共同鄰居數(shù)量作為鏈路存在性的評(píng)分，得分最高的節(jié)點(diǎn)對(duì)作為鏈路預(yù)測(cè)的結(jié)果.

（2） SR ?［19］ 一種通過(guò)節(jié)點(diǎn)鄰居相似性衡量相應(yīng)節(jié)點(diǎn)相似性的方法，將節(jié)點(diǎn)間的相似性得分作為鏈路存在性指標(biāo).

（3） PR ?［20］ 起初是一種網(wǎng)頁(yè)重要性排序的算法，通過(guò)計(jì)算節(jié)點(diǎn)隨機(jī)游走的靜態(tài)分布，得出所有節(jié)點(diǎn)對(duì)的PR值，取值最高的節(jié)點(diǎn)對(duì)作為鏈路預(yù)測(cè)的結(jié)果.

（4） SEAL ?［10］ 基于圖分類(lèi)的鏈路預(yù)測(cè)方法，通過(guò)抽取目標(biāo)鏈路的周?chē)訄D，使用深度圖卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行子圖分類(lèi)，預(yù)測(cè)鏈路存在性.

（5） LGLP ?［11］ 基于節(jié)點(diǎn)分類(lèi)的鏈路預(yù)測(cè)方法，將目標(biāo)鏈路周?chē)訄D轉(zhuǎn)化為線圖，經(jīng)過(guò)圖神經(jīng)網(wǎng)絡(luò)處理后，使用節(jié)點(diǎn)特征預(yù)測(cè)鏈路存在性.

本文主要采用曲線下面積（AUC）和平均準(zhǔn)確率（AP）作為方法性能評(píng)價(jià)指標(biāo).其中AUC是真正例率-假正例率曲線面積，AP則是查準(zhǔn)率-查全率曲線面積. 二者都是越接近1說(shuō)明分類(lèi)性能越好.

4.2 超參數(shù)設(shè)置

所有對(duì)比的基準(zhǔn)方法在上述數(shù)據(jù)集上被調(diào)整至最優(yōu)，SR的重要性系數(shù)為0.9，最大迭代次數(shù)為1000，公差為0.000 1.PR的衰減系數(shù)為0.85.

對(duì)于SEAL方法，采取與原論文中一致的超參數(shù)設(shè)置.抽取目標(biāo)鏈路的2-hop封閉子圖，4層圖卷積層用來(lái)計(jì)算節(jié)點(diǎn)嵌入表示，通道大小分別為32，32，32和1.排序池化層用于為封閉子圖生成固定尺寸的特征向量，排序比例設(shè)置為0.6. 兩個(gè)一維卷積層的輸出通道數(shù)分別為16和32.一個(gè)128個(gè)神經(jīng)元的全連接層用作分類(lèi)器預(yù)測(cè)鏈路存在性.訓(xùn)練50輪次取最好的輪次作為最終結(jié)果.

對(duì)于LGLP方法同樣采用和原文一致的超參數(shù)設(shè)置，4個(gè)GCNConv層，通道大小分別為32，32，32和1.從圖卷積層輸出的子圖嵌入表示中取出對(duì)應(yīng)的節(jié)點(diǎn)嵌入作為下一模塊的輸入.兩個(gè)全連 接層用作分類(lèi)器，輸出通道分別為128和2.學(xué)習(xí)率設(shè)置為0.005，批次大小為32，最大訓(xùn)練輪次為15.

4.3 鏈路預(yù)測(cè)性能驗(yàn)證

為了驗(yàn)證所提方法的性能，本文隨機(jī)抽取80%的存在邊作為訓(xùn)練正例，余下的20%作為測(cè)試正例.然后隨機(jī)抽取相同數(shù)量的不存在邊作為負(fù)例，按照8∶2的比例劃分訓(xùn)練集和測(cè)試集.總共進(jìn)行10次隨機(jī)實(shí)驗(yàn)，AUC平均值和標(biāo)準(zhǔn)差如表2所示，AP平均值和標(biāo)準(zhǔn)差如表3所示.

上述結(jié)果表明，各種鏈路預(yù)測(cè)方法在不同數(shù)據(jù)集上的分類(lèi)性能差別很大，對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)稠密（鏈路節(jié)點(diǎn)比值較大）的數(shù)據(jù)集，其鏈路預(yù)測(cè)的性能普遍高于網(wǎng)絡(luò)結(jié)構(gòu)稀疏的數(shù)據(jù)集.不同方法之間也存在較大差異，基于深度學(xué)習(xí)的方法明顯優(yōu)于啟發(fā)式方法，這是由于后者都是人工設(shè)計(jì)，無(wú)法處理所有的情況，具有很大局限性，而前者通過(guò)圖神經(jīng)網(wǎng)絡(luò)自動(dòng)學(xué)習(xí)鏈路分布規(guī)律.值得注意的是，本文所提出的方法比所有基準(zhǔn)方法性能表現(xiàn)更好，即使對(duì)比SEAL和LGLP這種最新方法，AFF依然展現(xiàn)了更優(yōu)的性能.

為了進(jìn)一步驗(yàn)證所提方法在數(shù)據(jù)集受限時(shí)的性能，本文在訓(xùn)練集和測(cè)試集劃分比例為 1∶1 時(shí)，重新進(jìn)行了上述實(shí)驗(yàn)，結(jié)果如表4和表5所示.可以看出本文的方法還是優(yōu)于其余五種基準(zhǔn)方法.相較80%的情況，AUC和AP兩個(gè)性能指標(biāo)并未下降過(guò)多，說(shuō)明在樣本受限的場(chǎng)景中，本文的方法依然表現(xiàn)出良好的性能.

4.4 鏈路預(yù)測(cè)有效性驗(yàn)證

為了驗(yàn)證模型的有效性，對(duì)訓(xùn)練集比例依次為40%，50%，60%，70%和80%進(jìn)行實(shí)驗(yàn)，每種劃分比例下，測(cè)試集的部分要進(jìn)行鏈路掩蓋，相當(dāng)于考慮原網(wǎng)絡(luò)不同殘缺情況對(duì)方法性能的影響.每種比例進(jìn)行10次重復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4和圖5所示.縱坐標(biāo)為AUC或AP的平均值，橫坐標(biāo)為訓(xùn)練集比例.其中，AFF使用實(shí)線表示，其余對(duì)比方法使用不同線型的虛線表示.

實(shí)驗(yàn)結(jié)果表明，在AUC和AP兩種評(píng)價(jià)指標(biāo)下，無(wú)論采用哪種劃分比例，AFF的鏈路預(yù)測(cè)性能均優(yōu)于其他基準(zhǔn)方法.同時(shí)發(fā)現(xiàn)：隨著訓(xùn)練比例上升，所有方法的性能均有提升.但是對(duì)比三種啟發(fā)式的方法，AFF明顯更加穩(wěn)定，在訓(xùn)練比例為40%的時(shí)候已經(jīng)達(dá)到較優(yōu)性能，說(shuō)明本文所提出的方法在原有網(wǎng)絡(luò)殘缺程度較大時(shí)，仍能學(xué)習(xí)到有用信息.

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

為了驗(yàn)證本文所增加的節(jié)點(diǎn)和鏈路特征是否增強(qiáng)了神經(jīng)網(wǎng)絡(luò)判別性，進(jìn)而提高鏈路預(yù)測(cè)的性能，本文將AFF的圖注意力網(wǎng)絡(luò)替換成LGLP的圖卷積網(wǎng)絡(luò)，形成了一個(gè)新方法，本文稱(chēng)之為 F ??1 .同時(shí)為了驗(yàn)證本文提出使用圖注意力網(wǎng)絡(luò)能夠考慮不同節(jié)點(diǎn)的重要性，從而學(xué)習(xí)到更具結(jié)構(gòu)化的特征，本文將LGLP的圖卷積層替換為本文中采用的圖注意力層，形成方法 F ??2 .對(duì)兩種新方法進(jìn)行實(shí)驗(yàn)，結(jié)果如圖6所示.

從圖6可以看出， F ??1 和 F ??2 方法均優(yōu)于LGLP方法，說(shuō)明本文所提出的兩項(xiàng)改進(jìn)是有效的，所增加的節(jié)點(diǎn)和鏈路特征可增強(qiáng)網(wǎng)絡(luò)的判別性，圖注意力網(wǎng)絡(luò)學(xué)到了一定結(jié)構(gòu)化特征.同時(shí) F ??1 方法優(yōu)于 F ??2 方法，說(shuō)明豐富輸入的原始特征，對(duì)性能提升的貢獻(xiàn)更大.

5 結(jié) 論

本文提出了一種新型的鏈路預(yù)測(cè)方法，針對(duì)現(xiàn)有方法存在的輸入特征單一和忽視節(jié)點(diǎn)相對(duì)重要程度的問(wèn)題，提出增加節(jié)點(diǎn)和鏈路基礎(chǔ)屬性，并利用線圖轉(zhuǎn)化進(jìn)行特征融合，形成信息更加豐富且更具判別力的特征.同時(shí)利用圖注意力網(wǎng)絡(luò)靈活學(xué)習(xí)節(jié)點(diǎn)權(quán)重.實(shí)驗(yàn)結(jié)果表明，本文所提出的方法在7個(gè)不同領(lǐng)域的數(shù)據(jù)集上，預(yù)測(cè)性能均優(yōu)于現(xiàn)有方法.在網(wǎng)絡(luò)缺失比例較大時(shí)仍有很好的性能表現(xiàn).但是當(dāng)前仍然面臨數(shù)據(jù)集正例過(guò)少的現(xiàn)象，如何更好解決數(shù)據(jù)不均衡問(wèn)題將是下一步的研究方向.

參考文獻(xiàn)：

［1］ ??Newman ?M E. Communities， modules and large-scale structure in networks［J］. Nat Phys， 2012， 8： 25.

［2］ ?Huisman M. Imputation of missing network data： Some simple procedures［J］. J Soc Struct， 2009， 10： 1.

［3］ ?Martínez V， Berzal F， Cubero J C. A survey of link prediction in complex networks［J］. ACM Comput ?Surv， 2016， 49： 1.

［4］ ?Ghasemi S， Zarei A. Improving link prediction in social networks using local and global features： a clustering-based approach ［J］. Progr Artif ?Intel， 2022， 11： 79.

［5］ ?Zhou C， Liu Y， Liu X， ?et al . Scalable graph embedding for asymmetric proximity ［C］//Proceedings of the 31th AAAI Conference on Artificial Intelligence. San Francisco： AAAI， 2017： 2942.

［6］ ?Talasu N， Jonnalagadda A， Pillai S S A， ?et al . A link prediction based approach for recommendation systems ［C］//Proceedings of the 2017 International Conference on Advances in Computing， Communications and Informatics （ICACCI）. Udupi：IEEE，2017： 2059.

［7］ ?Wang H， Zhang F， Zhang M， ?et al . Knowledge-aware graph neural networks with label smoothness regularization for recommender systems［C］//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York： ACM， 2019： 968.

［8］ ?Nickel M， Murphy K， Tresp V， ?et al . A review of relational machine learning for knowledge graphs［J］. Proc ?IEEE， 2015， 104： 11.

［9］ ?Oyetunde T， Zhang M， Chen Y， ?et al . BoostGAPFILL： improving the fidelity of metabolic network reconstructions through integrated constraint and pattern-based methods［J］. Bioinformatics， 2017， 33： 608.

［10］ ?Zhang M， Chen Y. Link prediction based on graph neural networks［J］. Adv Neural Inf Process Sys， 2018， 31： 5171.

［11］ Zhang M， Cui Z， Neumann M， ?et al . An end-to-end deep learning architecture for graph classification ［C］//Proceedings of the 32th AAAI Conference on Artificial Intelligence.New Orleans：AAAI， 2018： 4438.

［12］ Cai L， Li J， Wang J， ?et al . Line graph neural networks for link prediction ［J］. IEEE T ?Pattern Anal， 2021， 44： 5103.

［13］ Veli ??kovi ???P， Cucurull G， Casanova A， ?et al . Graph attention networks ［J］. Stat， 2017， 1050： 10.48550.

［14］ Newman M E. Clustering and preferential attachment in growing networks ［J］. Phys ?Rev ?E， 2001， 64： 025102.

［15］ Barabási A L， Albert R. Emergence of scaling in random networks ［J］. Science， 1999， 286： 509.

［16］ Adamic L A， Adar E. Friends and neighbors on the web ［J］. Soc Netw， 2003， 25： 211.

［17］ Zhou T， Lü L， Zhang Y C. Predicting missing links via local information ［J］. Eur Phys J B， 2009， 71： 623.

［18］ Katz L. A new status index derived from sociometric analysis ［J］. Psychometrika， 1953， 18： 39.

［19］ Jeh G， Widom J. Simrank： a measure of structural-context similarity ［C］//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton：ACM，2002： 538.

［20］ Brin S， Page L. Reprint of： the anatomy of a large-scale hypertextual web search engine［J］. Comput Netw， 2012， 56： 3825.

［21］ Perozzi B， Al-Rfou R， Skiena S. Deepwalk： online learning of social representations［C］//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 701.

［22］ Tang J， Qu M， Wang M， ?et al . Line： large-scale information network embedding［C］// Proceedings of the 24th International Conference on World Wide Web.Florence： ACM， 2015： 1067.

［23］ Grover A， Leskovec J. node2vec： Scalable feature learning for networks ［C］//Proceedings of the 22 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.San Francisco：ACM， 2016： 855.

［24］ Liu Z， Lai D， Li C， ?et al . Feature fusion based subgraph classification for link prediction［C］// Proceedings of the 29th ACM International Conference on Information & Knowledge Management.Ireland： ACM， 2020： 985.

［25］ Lai D， Liu Z， Huang J， ?et al . Attention based subgraph classification for link prediction by network re-weighting ［C］//Proceedings of the 30th ACM International Conference on Information & Knowledge Management.Queensland：ACM， 2021： 3171.

［26］ Martínez V， Berzal F， Cubero J C. Adaptive degree penalization for link prediction［J］. J Comput ?Sci-Neth， 2016， 13： 1.

［27］ Rossi R， Ahmed N. The network data repository with interactive graph analytics and visualization［C］//Proceedings of the 29th AAAI Conference on Artificial Intelligence. Austin： AAAI， 2015.

［28］ Von Mering C， Krause R， Snel B， ?et al . Comparative assessment of large-scale data sets of protein-protein interactions ［J］. Nature， 2002， 417： 399.

［29］ Newman M E. Finding community structure in networks using the eigenvectors of matrices ［J］. Phys Rev ?E， 2006， 74： 036104.