李峰 王俊峰 陳虹呂

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

關鍵詞：鏈路預測; 圖神經(jīng)網(wǎng)絡; 線圖; 特征融合; 圖注意力

中圖分類號：??TP301.6? 文獻標識碼：A? ?DOI：10.19907/j.0490-6756.2023.052002

收稿日期： ?2022-08-27

基金項目： ??基礎加強計劃重點項目（2019-JCJQ-ZD-113）； 國家自然科學基金（U2133208）； 四川省青年科技創(chuàng)新研究團隊（2022JDTD0014）

作者簡介： ??李峰（1994-）， 安徽阜陽人， 碩士研究生， 研究方向為網(wǎng)絡空間安全. 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)絡是分析復雜系統(tǒng)的有力工具 ?［1］ ，用于建模實體間的交互關系.然而由于客觀條件的限制，已觀測的網(wǎng)絡大多是不完整的 ?［2］ .為了解決網(wǎng)絡信息缺失問題，形成了鏈路預測方法.其通過當前已觀察到的鏈路，預測缺失的鏈路或可能出現(xiàn)的新鏈路，推斷網(wǎng)絡形成過程 ?［3］ ，補全網(wǎng)絡信息.在許多現(xiàn)實領域中，鏈路預測得到了廣泛應用.例如：社交網(wǎng)絡中的好友推薦 ?［4］ ，電子商務網(wǎng)站中的商品推薦 ?［5-7］ ，知識圖譜補全 ?［8］ 和代謝網(wǎng)絡重建 ?［9］ 等.然而這些現(xiàn)實應用受到了鏈路預測性能的制約.如何進一步提高預測性能，成為鏈路預測實際應用的關鍵.

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

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

2 相關工作

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

2.1 啟發(fā)式方法

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

2.2 節(jié)點嵌入方法

基于相似性的節(jié)點嵌入方法，通過從整個網(wǎng)絡拓撲中學習節(jié)點嵌入（embedding），計算節(jié)點間的相似性，相似性較高則認為節(jié)點間存在鏈路.借鑒自然語言處理領域的詞嵌入方法，Deepwalk ?［21］ 、LINE ?［22］ 和node2vec ?［23］ 被相繼提出.然而該類方法在網(wǎng)絡較為稀疏時，預測性能會受到較大影響.

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

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

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

3 AFF方法

3.1 問題定義

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

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

3.2 模型架構

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

3.3 特征融合

特征融合模塊主要實現(xiàn)原始特征的提取與融合，將網(wǎng)絡拓撲信息編碼成特征矩陣.主要包括以下流程：子圖提取，節(jié)點打標和線圖轉化.

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

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

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

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

Input： ??（u，v） 目標節(jié)點對，原網(wǎng)絡 G ，跳數(shù) h

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

1） procedure SubgraphExtract（ （u，v） ）

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

3） ?d←1 ，初始化最短路徑長度

4） while ?d

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

6） end while

7） for any 節(jié)點 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é)點打標 ?在對子圖進行特征學習之前，需要為子圖中的每個節(jié)點賦予一定的屬性（原始特征）.該原始特征豐富程度和判別能力會對最終的鏈路預測結果有較大影響.因此本文提出使用更加豐富的節(jié)點和鏈路特征：對于節(jié)點，增加了節(jié)點的度這一基本屬性;對于鏈路，增加了共同鄰居數(shù)量和共同鄰居的最大度這兩個基本屬性.上述三種屬性可形式化為式（3）.

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

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

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

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

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

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

為了描述全局拓撲信息，本文還對子圖中所有節(jié)點與中心節(jié)點的相對位置進行了編碼.具體計算如式（6）所示.

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

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

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

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

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

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

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

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

原圖的鏈路信息，可以直接作為線圖的節(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 ?標準化后合并而成.通過線圖轉化，原圖中節(jié)點特征和鏈路特征融合成線圖中的節(jié)點特征 ???v ????u，v ?，其蘊含的信息更加豐富且更具判別力.

3.4 特征學習

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

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

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

F ??（9）

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

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′ ?為可學習的參數(shù)； ?N ??i ?為節(jié)點 i 的一階鄰居集合（包括節(jié)點 i ）；‖表示連接操作； σ 代表LeakyReLU激活函數(shù)，坡度系數(shù)取0.2.最后進行softmax操作得到 j 相對于 i 的權重.

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

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

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

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

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

4 實驗與分析

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

本文選取了7個現(xiàn)實世界中不同領域的真實網(wǎng)絡拓撲作為實驗數(shù)據(jù)集，對所提出的模型AFF進行驗證.這些數(shù)據(jù)集包括： Celegans ?［26］ ， USAir ?［27］ ， SMG， EML， Power ?［26］ ， Yeast ?［28］ 和GRQ ?［29］ .拓撲信息見表1，具體表示含義如下.

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

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

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

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

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

（6） GRQ SMG 若干領域學者合著網(wǎng)絡，節(jié)點代表學者，鏈路表示存在合著關系.

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

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

（2） SR ?［19］ 一種通過節(jié)點鄰居相似性衡量相應節(jié)點相似性的方法，將節(jié)點間的相似性得分作為鏈路存在性指標.

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

（4） SEAL ?［10］ 基于圖分類的鏈路預測方法，通過抽取目標鏈路的周圍子圖，使用深度圖卷積神經(jīng)網(wǎng)絡進行子圖分類，預測鏈路存在性.

（5） LGLP ?［11］ 基于節(jié)點分類的鏈路預測方法，將目標鏈路周圍子圖轉化為線圖，經(jīng)過圖神經(jīng)網(wǎng)絡處理后，使用節(jié)點特征預測鏈路存在性.

本文主要采用曲線下面積（AUC）和平均準確率（AP）作為方法性能評價指標.其中AUC是真正例率-假正例率曲線面積，AP則是查準率-查全率曲線面積. 二者都是越接近1說明分類性能越好.

4.2 超參數(shù)設置

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

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

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

4.3 鏈路預測性能驗證

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

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

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

4.4 鏈路預測有效性驗證

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

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

4.5 消融實驗

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

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

5 結 論

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

參考文獻：

［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.