基于AFP的有向加權注意力流網絡鏈路預測*

馬滿福,姜璐娟,李 勇,張 強,范顏軍,鄧曉飛

(1.西北師范大學計算機科學與工程學院，甘肅 蘭州 730070；2.西北工業大學計算機學院，陜西 西安 710129)

1 引言

個性化推薦系統在線上購物、社交平臺和流媒體等眾多互聯網應用中得到廣泛應用，主要對用戶行為、商品特征等進行學習，對用戶偏好進行預測，從而減輕信息超載，提供個性化服務，輔助用戶決策等[1,2]。目前，大部分電商平臺，如淘寶、京東等，都利用所掌握的用戶行為數據，對用戶偏好進行預測，然后為用戶提供相關的產品推薦[3,4]。在各類推薦系統中，對用戶在線點擊行為數據進行挖掘的鏈路預測方法一直得到廣泛應用。鏈路預測旨在通過分析已知網絡節點和網絡結構等信息，預測網絡中的任意2個節點產生一條連邊的可能性[5]。

鏈路預測最常用的方法是啟發式方法[6]，通過計算節點間的相似性來判斷鏈接存在的可能性。低階啟發式算法，如CN(Common Neighbor)和PA(Preferential Attachment)，涉及網絡中目標節點的一階和二階鄰居，高階啟發式算法，如Katz、PageRank等，考慮x(x≥2)階鄰居。高階啟發式相較一階和二階啟發式算法性能更優，但會導致高的時間復雜度和內存消耗問題，而且啟發式算法使用圖結構特征，缺乏考慮包含豐富信息的網絡顯式特征和隱式特征[7]。此外，現有的鏈路預測算法大多數基于無向無權網絡，不能直接應用于有向加權的注意力流網絡。

推薦系統通常依賴用戶行為數據，如用戶瀏覽時間、點擊次數、搜索次數和停留時間等，基于用戶集體行為數據構建的注意力流網絡CAFN(Collective Attention Flow Network)分析方法為推薦系統研究帶來了新方向[8,9]。集體注意力流網絡由在線用戶點擊流數據構建而成，是節點和邊皆有屬性的有向加權網絡，基于CAFN的鏈路預測對推薦系統和知識圖譜補全等領域具有重要的研究意義[10,11]。

本文針對傳統啟發式鏈路預測方法存在的不足，提出了基于集體注意力流網絡模型的鏈路預測算法AFP(Attention Flow Prediction)。該算法將注意力流網絡節點間不同的邊方向抽象為2種邊關系類型，并引入注意力機制學習網絡中的節點屬性和邊屬性[12]，綜合考慮了網絡的圖結構特征、顯式特征和隱式特征，將鏈路預測問題轉化為一個二分類問題，即判斷節點間的邊屬于某個關系類型的可能性大小，在推薦系統等領域具有重要的應用價值。本文研究內容包含以下4個方面：

(1)基于有向加權注意力流網絡和R-GCN(Relational-Graph Convolutional Network)算法提出了新的鏈路預測算法AFP。該算法引入注意力機制取代了傳統R-GCN算法中的參數權值共享，將網絡中的邊方向抽象為2種關系類型，有效解決了有向加權網絡邊關系的準確預測問題。

(2)在R-GCN基礎上，引入注意力機制學習節點特征表示。注意力流網絡中的節點和邊具有不同的權重，引入注意力機制取代了傳統R-GCN算法中的權重共享方法，通過每個關系的不同重要性程度聚合鄰居信息。

(3)將注意力流網絡中的邊方向抽象為{rin:vi←vj;rout:vi→vj}2種關系類型。針對不同的關系類型，分別學習并聚合不同節點和邊的特征信息，有效表征了網絡中邊的方向信息。

(4)綜合學習網絡的圖結構特征、顯式特征和隱式特征。在學習節點特征的過程中，考慮注意力流網絡的局部結構、節點嵌入、網站停留時間和點擊次數等特征，捕獲了關于網絡的更多信息，并且有效提升了預測性能。

2 相關工作

2.1 鏈路預測

鏈路預測是推薦系統中使用的重要方法之一，通過分析已知網絡節點及網絡結構等信息，挖掘網絡底層的潛在規律，預測網絡中的任意2個節點在未來產生連邊的可能性?，F有的鏈路預測方法大多數都是基于無向無權圖的。文獻[13]在多路復用網絡上結合層相似性度量方法和層重構方法，在多個無向圖上實現了鏈路預測。文獻[14]結合概率啟發式和注意力機制，通過合適的學習方式來預測無向圖中的鏈接，無需依賴復雜特征工程。文獻[15]提出了一種捕獲網絡中的高階結構的嵌入算法，并在多個無向圖上驗證了其有效性。文獻[16]使用屬性信息識別社交網絡中新鏈接和節點的位置，預測網絡中的新關系和缺失關系。這些方法在無向圖上的預測性能優異，但不能有效地應用于有向加權圖。

現實世界中，推薦系統研究面對的大多數網絡都是有向加權圖，基于無向圖的方法不能有效地處理具有復雜交互關系的有向加權圖。文獻[17]提出了一種基于AUC(Area Under the Curve)的鏈路預測方法，將鏈路預測問題轉化為優化問題，在有向圖上實現了高質量預測。文獻[18]提出了WLNM(Weisfeiler-Lehman Neural Model)鏈接預測方法，以圖模式學習拓撲特征，根據頂點在提取的子圖中的結構角色標記頂點，同時保留子圖的內在方向性。文獻[19]提出了一種有監督的鏈接預測方法來預測研究人員的引文數，該方法可以預測鏈接及其權重。這些方法都考慮了網絡中邊的方向，但沒有綜合學習網絡的圖結構特征、顯式特征和隱式特征，有向加權的注意力流網絡節點和邊皆有屬性，所以上述方法在該網絡上是無效的。

Figure 1 Framework of AFP algorithm

2.2 注意力流網絡

注意力流網絡由在線用戶點擊網站的序列數據構建而成，是一種節點和邊都帶有屬性的有向加權網絡。對注意力流網絡的點擊率進行預測是互聯網廣告系統和推薦系統中最重要且最具挑戰的預測之一。文獻[20]提出了基于特征交互的神經網絡，通過三維關系張量對特征交互進行建模，提高了深度神經網絡在點擊率預測任務中的性能。文獻[21]提出了自動特征交互選擇兩階段算法，可以在模型訓練過程中自動識別和去除冗余特征交互。文獻[22]提出了一個端到端的框架RippleNet，通過沿著知識圖中的鏈接自動、迭代地擴展用戶的潛在興趣，以刺激用戶偏好在知識實體集上的傳播，可用于預測最終點擊率并進行推薦。隨著以用戶行為數據分析為主的推薦系統的發展，對基于用戶行為的注意力流網絡的研究吸引了越來越多的研究人員并在網絡的特征捕獲方面取得了優異的效果，但基于該網絡的鏈路預測方法還很少。

綜上，現有針對不同網絡類型考慮不同網絡信息的建模方法，還沒有綜合考慮網絡的圖結構特征、顯式特征和隱式特征，不能有效應用于有向加權的注意力流網絡；此外，注意力流網絡已成為依賴用戶行為數據分析的推薦系統的一個重要分支，卻鮮有基于注意力流網絡的鏈路預測算法研究。鑒于此，本文提出了基于有向加權注意力流網絡的鏈路預測算法AFP，綜合學習了網絡的圖結構特征、顯式特征和隱式特征，彌補了上述相關研究中的不足，并通過多個評價指標驗證了該算法的有效性。

3 鏈路預測算法AFP

AFP算法整體框架如圖1所示，由一個編碼器和一個解碼器組成。首先，編碼器將高維的圖數據映射到低維的向量空間中。在學習節點特征向量的過程中，把網絡中不同的邊方向抽象為2種關系類型，目標節點根據不同的類型聚合不同的鄰居信息，并引入注意力機制融合學習網絡中的節點屬性和邊屬性，經過多個隱藏層得到的向量可以表征網絡中節點的局部結構。其次，編碼器獲得的節點向量表示和關系類型以三元組形式輸入解碼器，解碼器采用DistMult評分函數計算三元組成立的概率，當概率值大于閾值ε時輸出1，表示三元組關系成立;否則輸出0，表示三元組關系不成立。最后，將評分結果映射到高維圖數據中，便可得到最終的鏈路預測結果。

3.1 網絡構建

本文使用中國物聯網信息中心提供的在線用戶瀏覽網站的行為日志數據作為實驗對象，數據記錄了用戶開關時間、瀏覽網站的URL等信息。首先，清洗數據并過濾無用信息，抽取1 000名用戶1個月的點擊網站數據來構建注意力流網絡。將在線用戶瀏覽點擊的網站抽象成網絡中的節點，網站與網站之間的跳轉抽象成網絡中的邊，網站停留時長作為節點權重，網站間的跳轉頻數作為邊權重。當用戶在網站停留時間超過30 min時，該網站作為一個新節點加入網絡，同時產生一條新連邊，以此構建了集體注意力流網絡。該網絡由20 115個節點和125 557條邊組成，構建的集體注意力流網絡符合復雜網絡的“冪律分布”[23]，網絡的可視化效果如圖2所示。

Figure 2 Collective attention flow network

3.2 網絡特征學習

集體注意力流網絡中，用戶在網站的停留總時間表示網站對用戶注意力的吸引。網站間的跳轉次數與網站的度相關，入度反映了網站的吸引力，出度反映了網站的活躍程度，綜合考慮網站的出度和入度，網站度集和鄰居網站中網站vi的總度值，即集體注意力流網絡的顯式特征。通過結合R-GCN和注意力機制來學習網站間關系的復雜性和關系權重的多樣性，即隱式特征。

具體地，網絡中的節點vi將自身的特征信息hi經過抽取變換后，共享給同一關系下的鄰居節點vj；接著，將2個節點的特征信息hi和hj聚集起來，實現局部結構信息融合；最后，將聚合的信息進行非線性變換，更新網絡中節點在l+1層的特征狀態，如式(1)所示：

(1)

(2)

(3)

(4)

將注意力機制與R-GCN算法鄰域特征更新規則相結合，式(1)轉換為式(5)：

(5)

以注意力流網絡中任意節點vi為例，基于關系類型rin:vi←vj，該節點不僅考慮了節點自身特征hi，而且還聚合了其鄰居節點vj的特征信息hj，并根據關系類型進行相應變換和歸一化操作，此時節點特征狀態的更新由式(5)轉換為式(6)：

(6)

節點vi基于第2種關系類型rout:vi→vj，節點特征狀態更新如式(7)所示：

(7)

綜合考慮節點vi與任意節點的2種不同關系類型，其特征狀態更新描述如式(8)所示：

(8)

3.3 邊關系預測及損失優化

(9)

基于上述給定的評分函數f()，在訓練過程中使用負采樣，對網絡中的每一個正樣本，隨機修改三元組中的節點。利用交叉熵損失函數優化損失值，通過迭代求解損失值，并采用隨機梯度下降來優化算法，迭代過程直至收斂或迭代次數超過一個閾值α時停止，故損失函數如式(10)所示：

(1-yij)log(1-σ(f(Z))))

(10)

其中，σ()是sigmoid激活函數，yij是節點標簽，yij=1表示節點vi和節點vj間存在連邊，yij=0表示節點vi和節點vj不存在連邊。Dtrain表示訓練集，Z為訓練集中的樣本。

3.4 具體算法AFP

鏈路預測算法AFP如算法1所示。

算法1AFP算法

輸入:三元組Z=(vi,R,vj)；層數L;輸入特征{hi,?vi∈V}；激活函數。

輸出:三元組成立的概率f(Z)。

1.VK←V;

2.forl=L,…,1do

3.Vl←Vl+1;

4.forvi∈Vl+1do

5.Vl←Vl∪Nl+1(i);/*Nl+1(i)表示節點vi在第l+1次聚合時的鄰域*/

6.end

7.end

9.forl=L,…,1do

10.forvi∈Vldo

13.end

14.end

17.returnf(Z)

4 實驗和結果分析

4.1 數據集

基于中國互聯網絡信息中心提供的在線用戶行為數據[24]，本文構建了一個由20 115個節點和125 557條邊組成的集體注意力流網絡，網絡中節點的平均度為6.251。集體注意力流網絡中度大的節點相對稀少，度小的節點較多且分布集中，符合“長尾分布”[23]，可用于復雜網絡鏈路預測任務研究。

4.2 基準算法

本文選擇了6個經典算法與提出的AFP算法作對比：(1)GCN(Graph Convolutional Network)[25]算法結合深度優先搜索和廣度優先搜索對圖中的節點進行采樣，利用word2vec的思想來學習節點表示向量；(2)GAT(Graph Attention Network)[26]在GCN的基礎上引入Attention思想,計算每個節點的鄰居節點對它的權重，從而獲取鄰近點的特征；(3)GraphSAGE(Graph SAmple and aggreGatE)[27]利用節點特征信息和結構信息得到圖嵌入映射；(4)TransE(Translating Embeddings)[28]利用詞向量的平移不變，對三元組實例，通過不斷調整h、r和t(Head、Relation和Tail的向量)使(h+r)盡可能與t相等；(5)DistMult[29]采用基于相似性的打分函數，通過匹配實體和關系在嵌入向量空間的潛在語義衡量三元組成立的可能性；(6)ComplEx(ComplEx embeddings)[30]在DistMult的基礎上引入復值嵌入，取復值點積的實部作為三元組得分。

4.3 評價指標與實驗設置

本文采用鏈路預測任務中常用的評價指標準確度(Accuracy)、精準度(Precision)、召回率(Recall)和F1值來評價各算法。下述各公式中的TP表示正例預測正確的個數；FP表示負例預測正確的個數；TN表示負例預測錯誤的個數；FN表示正例預測錯誤的個數。各指標簡要描述如下：

(1)Accuracy：所有三元組Z=(vi,R,vj)中預測正確的比例，如式(11)所示：

(11)

(2)Precision：正確預測正例樣本數與預測為正例的樣本數的比例，如式(12)所示：

(12)

(3)Recall：正確預測正例樣本數與所有正例樣本數的比例，如式(13)所示：

(13)

(4)F1值：綜合考慮Precision和Recall得分，是Precision和Recall的調和均值，如式(14)所示：

(14)

除上述4個評價指標外，本文還采用推薦系統和知識圖譜廣泛使用的MRR和Hits@K指標對TransE、DistMult、ComplEx和AFP進行對比。分別簡要描述如下：

(1)MRR(Mean Reciprocal Rank)是一個國際上通用的評價檢索算法的機制，其第1個預測結果匹配分數為1，第2個匹配分數為0.5，第n個匹配分數為1/n，沒有結果匹配的分數為0，最終的分數為所有得分之和,如式(15)所示:

(15)

其中,Dtest為測試集。

(2)HR(Hit Ratio)是Top-K推薦中常用的衡量召回率的指標。若正例三元組Z=(vi,R,vj)出現在Top-K中，則Hits@K=1，否則Hits@K=0，Hits@K*為所有命中Hits@K=1的測試正例，總體的Hits@K是通過對所有測試用例求平均來確定的，如式(16)所示：

(16)

注意力流數據集擁有數萬級的節點集和邊集，將數據集按一定比例劃分為訓練集Dtrain、驗證集Dvalid和測試集Dtest，劃分情況如表1所示。

Table 1 Data set and its division

為保證收斂速度和質量，經過反復實驗，最終將訓練的迭代次數設置為epoch=3000，訓練批大小batch_size=3000，激活函數采用sigmoid，學習率lr=0.001，優化器采用Adam，隱藏層層數H=200，節點嵌入維度E=200。

4.4 實驗結果

AFP算法預測的注意力流網絡中網站的點擊率排名如表2所示，其中Rank列代表網站排名序號，Source_Node列代表源節點網站，SN_f(Z)列代表源節點網站的點擊概率，Target_Node列代表目標節點網站，TN_f(Z)列代表目標節點網站的點擊概率。表2所示的排名結果與網站的停留時長、點擊次數、度值等網絡屬性值成正比關系，并且與注意力流網絡的真實點擊情況基本一致。

Table 2 Ranking of predictive click-through rate of websites in the attention flow network

將4.2節的6個對比算法和AFP算法的10次實驗結果取平均值，得到表3和表4，粗體顯示的是本文算法AFP的結果，其整體表現最好。例如，在Accuracy、Precision、Recall和F1指標上，AFP與未加入注意力機制的R-GCN相比，AFP的平均Accuracy值提高了1.52%，平均Precision提高了7.88%，平均Recall提高了1.59%，平均F1提高了4.89%。此外，在MRR和Hits@K指標上，AFP與R-GCN相比，平均MRR提高了0.54%，平均Hits@1提高了0.44%，平均Hits@3提高了0.58%，平均Hits@10提高了0.14%。

Table 3 Comparison of Accuracy,Precision,Recall,and F1 of different algorithms on the attention flow network

Table 4 Comparison of MRR and Hits@K of different algorithms on the attention flow network

此外，本文還將訓練集按比例從50%到90%劃分以驗證本文算法的有效性。不同算法在不同訓練集規模下的預測性能如圖3～圖6所示。由圖可知，AFP算法在訓練集不同規模下的性能依舊顯著，說明AFP算法的預測性能優勢與網絡訓練集劃分的大小無關，且在網絡不完整的情況下，預測性能依舊顯著。

Figure 3 Comparison of Accuracy values of different algorithms under different sizes of training set

Figure 4 Comparison of Precision values of different algorithms under different sizes of training set

Figure 5 Comparison of Recall values of different algorithms under different sizes of training set

Figure 6 Comparison of F1 values of different algorithms under different sizes of training set

5 結束語

本文提出了適用于有向加權網絡的鏈路預測算法AFP，該算法綜合考慮了網絡的圖結構特征、顯式特征和隱式特征；將有向網絡中的邊方向抽象為2種關系類型，實現了邊方向的預測；引入了注意力機制，以捕獲節點和邊的不同重要性。研究結果表明：(1)針對有向加權注意力流網絡鏈路預測，AFP算法比基準算法的預測準確率提高了至少3.52%；(2)網絡中的節點和邊皆有屬性，綜合考慮多種特征能夠提高邊關系預測性能；(3)注意力流網絡中度大的節點相對稀少，度小的節點較多且分布集中，符合“長尾分布”。

AFP算法的優點有：(1)AFP可以有效地預測有向加權網絡中的邊關系；(2)構建的注意力流網絡由20 115個節點和125 557條邊組成，因此AFP的預測結果不受在大數據集上預測性能差假設的影響。但也存在以下不足：(1)引入注意力機制捕獲網絡特征提高了特征學習效果，同時也提高了時間復雜度；(2)相比于鏈路預測，知識圖譜補全關注的是網絡中最可能出現的鏈路的預測正確度。與知識圖譜算法相比，AFP預測效果在MRR和Hits@K指標上均比較低。

有向加權集體注意力流網絡鏈路預測是個性化推薦的重要方法之一。在未來的研究中，針對知識圖譜存在的大量非對稱關系，將進一步研究AFP服務于知識圖譜補全等領域，以提高其預測性能,降低時間復雜度。