基于AGRU-GNN的圖網絡社交推薦算法①

卓佳寧,雷景生,周雪雪

(上海電力大學 計算機科學與技術學院,上海 200090)

這是一個信息爆炸的時代,大數據這把雙刃劍在為我們帶來豐富的知識訊息的同時,也產生了不少“數據泡沫”,用戶常常被這些無效信息包圍,無從下手,而用戶真正感興趣的信息被阻絕在外.為了解決這一問題,推薦系統應運而生,旨在為每個特定用戶從海量數據中篩選出其各自感興趣的內容并推薦給用戶.推薦系統的關鍵之一在于對用戶興趣以及物品特征的建模表示,從而能夠進一步通過評分模型對用戶、物品預測相關程度,并以此為依據進行推薦.另一方面,社交網絡中好友、大V 等社交關系也可能會影響用戶的潛在興趣,社交網絡也越來越多地被結合到推薦系統中來[1-3],在推薦時利用通過社交網絡的傳播的信息,提高了推薦的針對性與有效性.

基于圖神經網絡(GNNs)的推薦算法[4,5]是推薦系統應用的熱門算法之一.GNN 在圖結構拓撲上應用深度神經網絡的技術對局部圖的鄰域信息進行迭代,使得信息能夠在非結構化的節點關系中進行交互計算,最終得到各個節點在圖拓撲結構下的特征域表示.社交推薦本質上是在非規則的用戶-物品關系、用戶-用戶關系中聚合并表示各個節點的本征信息與交互關系,因此GNN 在社交推薦中得到了廣泛的應用[6,7].

圖神經網絡通常描述的是靜態拓撲關系,一方面,節點之間的連接關系不會隨時間發生改變.對于推薦系統而言,時時刻刻都有海量新數據產生,新用戶、新物品以及新交互事件都會改變已有圖網絡的拓撲結構.另一方面,對于特定節點,其鄰居節點的時序性通常被GNN 所忽略.例如,對于推薦系統中的用戶-物品圖結構而言,以用戶為中心,則其鄰居節點即為該用戶交互過的物品,而用戶與不同物品的交互自然存在時間上的先后,而交互時間的時序性則可能暗含了用戶興趣隨時間的變化情況.

本文主要針對第二點提出改進GNN 算法,利用門控循環單元(GRU)對時間序列信息進行選擇性遺忘與選擇性記憶,以此對用戶-物品交互歷史以及物品-用戶交互歷史進行建模,增強了GNN 算法在局部圖鄰域迭代過程中對時序信息的抽象能力,使得推薦系統對用戶節點以及物品節點的表示結合了其特點隨時間的變化,提升了推薦的效果.具體而言,我們分別建立了以用戶節點為中心的用戶-物品圖,每個用戶節點的相鄰節點為其交互過的物品,這些相鄰節點通過交互時間戳屬性排序,在GNN 進行局部圖鄰域迭代時通過GRU 學習物品交互歷史潛在關聯,并通過注意力機制與用戶表征進行聚合;類似的,同時建立以物品節點為中心的物品-用戶圖,每個物品節點的相鄰節點為與其交互過的用戶,同樣按照交互事件的時間戳排序,并通過注意力GRU 模型進行聚合,以此來表征對該物品感興趣的群體特征變化;另外,還根據用戶間的社交關系建立了用戶-用戶圖網絡,通過注意力機制來傳遞社交網絡中相鄰用戶之間的相互作用.

1 相關工作

1.1 基于非時序特征的GNN 推薦算法

深度學習主要關注例如文字的序列結構、例如圖片的平面結構,現在處理這些數據的做法也比較成熟,關注序列任務的NLP 領域多用RNN、Transformer、CNN 對數據進行Encoder,而關注平面結構的CV 領域更多使用CNN 及其各種變體對數據進行Encoder.在現實世界中更多的數據表示并不是序列或者平面這種簡單的排列,而是表現為更為復雜的圖結構.

Kipf和Welling[8]提出了用于半監督圖分類的圖卷積網絡(GCNs).模型通過利用節點屬性和圖結構來學習節點表示,它由多個圖卷積層組成,每個圖卷積層使用當前節點的表示及其相鄰節點的表示的組合來更新節點表示.通過這個過程,可以捕獲節點之間的依賴關系,然而在原來的公式中,當更新節點表示時,所有的鄰居被賦予靜態權值.Fan 等[9]通過構建用戶-物品關系二元圖 (用戶購買的所有物品)、用戶-朋友關系單元圖 (用戶的社交關系)、物品-用戶關系二元圖 (物品被用戶購買的記錄)這3 個無向圖用于對物品進行評分預測.Ying 等[10]構建了用戶-標簽無向二元圖,通過 PinSage 算法 (隨機游走和圖卷積結合)成功應用于超大規模的網頁內容推薦.Wang 等[11]構建用戶—物品圖,不同之處在于 GNN 算法中使用目標節點及其鄰居節點的點積進行更新,并且通過協同過濾的方法進行推薦.上述文獻證明了圖網絡在推薦上的有效性,但都沒有考慮時序性對用戶興趣以及物品的影響.

1.2 基于時序特征的推薦算法

對于隨時間變化的用戶興趣進行建模在推薦系統領域也引起了大量關注,這些模型大多基于(高斯)矩陣分解[12].例如,Xiong 等[13]通過分解(用戶、物品、時間)張量來學習時間表示.Koren[14]開發了一個類似的模型叫做timeSVD++.Gopalan 等進行了類似的建模,但是使用了泊松分解[15].但是,這些方法假定用戶的興趣在長期范圍內緩慢而平穩地變化,通常以月或年為序.

為了有效地捕捉用戶的短期興趣,最近的研究將RNN 引入到用戶最近的(有序的)行為模型中.例如,Hidasi 等[16]首先提出了SessionRNN 來模擬用戶在會話中的興趣.Wu 等[17]使用兩個獨立的RNNs 根據新的觀察結果更新用戶和項的表示.Beutel 等[18]構建了一個基于rnnde的推薦器,可以包含輔助上下文信息.本文基于這種思路將GRU 引入圖網絡,并且輔之以注意力機制,來捕捉用戶的時變興趣和物品的時變特征,進而提升了推薦系統在時序評分數據集上的有效性.

2 基于AGRU的圖網絡社交推薦算法

本文以圖網絡為骨架建立推薦系統,定義用戶集合{U|u1,u2,···,uN} 與物品集合{V|v1,v2,···,vM},則圖頂點集合為U ∪V.圖網絡中存在兩種非同質邊緣,第一種邊表示用戶與物品之間的交互關系,即{R|U×V}=描述了用戶ui對物品vj進行過評價,邊ri,j的權重記為,表示用戶ui對物品vj的評分量化分值,邊ri,j的時間戳記為,表示此次評分事件發生的時刻;第二種邊表示用戶與用戶之間的有向交互,即{S|U×U}={S|si,j:=(ui→uj),ui,uj∈U},表示用戶ui在 社交平臺上關注了用戶uj,邊si,j的權重記為,表示用戶ui與uj社交關系重要性的量化值,本文不考慮社交網絡的時序特征,因此邊si,j無時間戳屬性.

因此,本文推薦系統可描述為:給定用戶集合 U、物品集合 V,以及評分邊集合R、社交邊集合S,經過一定的訓練算法得到優化預測函數 F,使得對于任意ui∈U,vj∈V,ri,j?R,可預測用戶ui對物品vj的評分=F(ui,vj),作為是否推薦的依據.以下將分別以用戶節點與物品節點為中心,展開介紹圖網絡局部圖鄰域聚合的具體算法細節.

2.1 圖網絡局部圖鄰域聚合

GNN 中常用局部圖鄰域聚合技術[8,19]來傳遞鄰近節點之間的信息,并迭代訓練各節點的抽象表示.對于給定圖G(ν,E),定義k階鄰域函數Neighk(vi)={vk|(vi,vi,1),···,(vi,k-1,vk)∈E},即vi與vk之間存在長度為k的路徑.本文采用一階鄰域函數,簡記為N.則GNN 局部圖鄰域聚合算法可見算法1.

算法1.GNN 局部圖鄰域聚合算法的第n 次迭代1)遍歷圖的頂點,對每個頂點,執行第2)～4)步操作;vi N(vi)=Neigh(vi)G V vi 2)計算的鄰域節點集合;Agg N(vi)vagg i=Agg(N(vi))3)利用聚合函數 計算的聚合表示結果;vagg i 4)將聚合結果 與頂點自身 拼接,并進行線性仿射與非線性激活,得到該頂點本次迭代的表示.vi v(n)i

上述算法中聚合函數Agg有多種選擇,常見的如拼接、注意力、卷積等.本文根據邊ri,j存在時序性的特點,選擇基于注意力機制的門控循環單元作為鄰域聚合函數,以提取各節點鄰域集合中的時序信息,提高推薦系統對時序數據的學習能力.

本文推薦系統圖模型中(如圖1所示),頂點集合由用戶集合 U、物品集合 V兩部分組成,邊集合由評分關系集合 R、社交關系集合 S構成,其中不包含關于物品集合 V的閉集邊集,因此整個圖可劃分為3 個局部圖:用戶-物品圖、用戶-用戶圖以及物品-用戶圖,以下將分別討論其鄰域聚合算法.另外,用戶ui、物品vj分別通過嵌入層獲得其向量表示,;考慮到數據集中評分的取值為離散整數0-5,權重也通過對評分分值的嵌入向量表示,即.

2.2 用戶模型:AGRU 聚合+社交影響力聚合

考慮圖模型中的用戶節點ui以及以其為端點的評分邊Rui構成的局部圖(圖1左上角子圖),即用戶-物品圖.則ui的鄰域節點為用戶ui所 評價過的物品集合NV(ui),根據各評分邊的時間戳t,可得到用戶評分事件的時序排列.為提取用戶評價物品的時序特征,本文在用戶-物品圖鄰域聚合采用基于注意力的門控循環單元(Attention-GRU)來提取評分序列特征,算法如算法2 所示.

算法2.用戶-物品圖AGRU 聚合算法,第n 次迭代1)遍歷用戶集合,對每個頂點,執行第2)～8)步操作;ui V NV(ui)=NeighV(ui)L=■■■NV(ui)■■■U ui 2)計算 在物品集合 上的鄰域節點集合,鄰域節點數量;NV(ui)v jti,j S eq(ui)=[v1,v2,···,vL] ti,1≤ti,2≤···≤ti,L 3)將 中的物品節點 按時間戳 升序排列,得到長度為L的物品序列,其中;S eq(ui)v jeVj wRi,jeRi,jeVjeRi,j e j′ S eq(ui)=[e1′,e2′,···,eL′]4)對序列 中的每個物品元素,查詢其嵌入表示,以及對應評分的嵌入表示;將 與 拼接輸入多層感知機降維得到包含評分分值信息的物品表示;更新;S eq(ui)h0 Outseq=[h(k)1,h(k)2,···,h(k)L 5)將序列 作為GRU的輸入,同時輸入初始隱藏狀態,得到GRU 在每個時刻末層輸出構成的長度為L的序列,其中k為GRU的縱向堆疊層數;h(k)L]6)以GRU 末層最后時刻的隱藏狀態為參考,用注意力機制對中的L 個元素進行加權平均得到;h′ h(k)L Outseqh′7)拼接 與,并經過線性層以及非線性ReLU 激活,得到,作為鄰域集合的聚合結果,即;uagg i NV(ui)Agg(NV(ui))=uagg uagg i i eUi 8)將聚合結果 與頂點自身嵌入表示拼接,并進行線性仿射與非線性激活,得到該用戶節點第n 次迭代的表示.u(n)i

上述算法中,第4)步采用雙層感知機降維:

第5)步中第m=1,2,···,k層GRU[20]在時刻t=1,2,···,L執行下列計算:

其中,δ表示Dropout 函數,*表示Hadamard 乘積,σ表示Sigmoid 激活函數:

每個GRU 單元的內部結構如圖2所示,xt表示當前時刻的輸入,h(t-1)則表示該GRU 單元上一時刻的隱藏狀態.兩者拼接并分別通過獨立全連接層得到重置因子rt和遺忘因子zt,由于經過了Sigmoid 激活,兩種因子的取值范圍均在0 到1 之間.重置因子對上一時刻的隱藏狀態進行重置,并將結果與當前輸入拼接后傳遞給tanh 激活的全連接層,得到以當前輸入為主、隱藏狀態為輔的表示nt.另一方面,遺忘因子zt與記憶因子1-zt分別對h(t-1)和nt調制,實現了對序列歷史隱含信息的選擇遺忘以及當前輸入的選擇記憶.

圖1 基于AGRU-GNN的圖網絡社交推薦算法架構

圖2 GRU 單元內部結構

取GRU 第k層的隱藏狀態Outseq=作為輸出,并基于輸出單元數量為1的多層感知機+Softmax 實現注意力機制(如圖3所示),獲得的注意力權重系數pi:

則鄰域NV(ui)聚合特征:

圖3 基于注意力機制的GRU 聚合算法架構

另一方面,考慮用戶節點ui以及以其為起始端點的社交邊 Sui構成的局部圖,即用戶-用戶圖(圖1右上角子圖).本算法中社交邊集為有向邊集,每條邊表示用戶的單向關注關系,則ui的鄰域節點為用戶ui所關注的用戶集合NU(ui).社交邊si,j的權重量化為被關注者uj的影響力因子:

在用戶-用戶局部圖的鄰域聚合的第n次迭代中,使用用戶-物品局部圖第n次迭代聚合的結果u作為節點ui的向量表示,使得AGRU 捕獲到的時序特征也能夠通過社交邊進行傳播.具體聚合過程如下:

首先,查詢用戶-物品圖在用戶集合NU(ui)上的迭代結果得到:隨后通過如式(10)-(14)所示的注意力網絡得到關于其每個鄰域節點的邊權加權表示的注意力權重pj.則社交局部圖的鄰域聚合特征

最終經過式(16)-式(18),將與節點自身特征融合降維后得到,即為用戶ui在第n次迭代后的最終向量表示.

2.3 物品模型:對偶AGRU 聚合

類似地,考慮以物品節點為中心情形下的局部圖鄰域聚合算法.由于評分邊集 R是無向邊集,因此物品-用戶圖(圖1左下角子圖)與用戶-物品圖完全對偶,對于物品vi,其鄰域用戶集合NU(vi)也可通過評分邊的時間戳排序得到用戶時間序列,表示對物品vi評價過的用戶在時間上的先后次序.因此對于物品的特征迭代算法與算法2 關于 (U,V)對偶,可對稱地得到物品vi在第n次迭代后的表示.顯然地,物品社交圖沒有明顯的物理意義,因此物品模型中不包含自身社交影響力聚合,用戶ui在 第n次迭代后的最終向量表示=.當然,用戶社交的影響因素會在物品進行鄰域聚合時傳播給物品模型.

2.4 評分預測模型

根據第2.2、2.3 節對用戶ui、物品vi的AGRU 聚合算法,分別得到第n次迭代后的向量表示,.將其拼接后經過單輸出多層感知機(如圖1右下角子圖),得到對評分關系ri,j權重(即評分分值)的預測值.

在訓練過程中,以一個批次(batch)數據的均方誤差MSE作為目標函數對模型中的參數進行優化:

其中,bsize為批次規模.

在推理過程中,則即為推薦系統給出的用戶ui對物品vi的評分分值預測.

3 實驗結果與分析

3.1 數據集選取與預處理

實驗采用Ciao 數據集和Epinions 數據集對算法進行驗證,兩者均為包含社交關系信息的在線購物數據[21].數據集包含兩部分數據:(1)評分信息,每條評分數據包括用戶索引、物品索引、評分分值(0-5)以及時間戳4 個維度;(2)社交信息,每條社交數據包括關注者用戶索引以及被關注者用戶索引,表示用戶單向關注關系.Ciao 數據集與Epinions 數據集的特點如表1所示.

對數據集的預處理包括數據清洗、索引重映射、數據集切分、圖建模、時間戳排序5 個步驟.數據清洗主要完成數據去重,評分數據中包含少量重復評分邊ri,j,根據其時間戳t保留較新的數據;隨后對數據集用戶集合 U、物品集合 V分別進行索引重映射,將原始索引映射至 [1,2,···,|U|],[1,2,···,|V|]范圍內,方便嵌入層映射;之后將數據集中的評分邊 R集隨機劃分為訓練評分邊集 Rtrain和測試評分邊集Rtest,分別比較訓練集比重為60%和80%的實驗結果;對訓練集和測試集,分別建立第2 節中描述的推薦圖模型,并對每個用戶節點的鄰域物品節點按時間戳提前排序,則圖網絡迭代過程中無需重復排序,以降低計算量,對于物品節點的鄰域用戶節點,也按同樣方法提前排序.

表1 Ciao 數據集與Epinions 數據集特征

3.2 評價指標

本文采用衡量推薦系統推薦效果的兩個常用指標作為評判標準:均方根誤差RMSE和平均絕對誤差MAE:

其中,y表示測試集所有評分邊的權重(真實值)則表示推薦系統對測試集各評分邊的預測權重(預測值)RMSE與MAE越小,表明推薦系統預測的評分與真實值差距越小,推薦效果越好.

3.3 對比模型

我們選取下列模型作為本算法對比的基準模型:

(1)概率矩陣分解(PMF)[12]:對用戶潛在因子、物品潛在因子建模,利用用戶-物品評分概率矩陣進行推薦;

(2)社交推薦(SoRec)[22]:基于用戶-物品評分矩陣提取聯合潛在因子特征,并結合社交矩陣進行推薦;

(3)社交矩陣分解(SocialMF)[3]:考慮了社交信任度在用戶-物品評分矩陣分解空間中的傳播;

(4)神經網絡矩陣分解(NCF)[23]:將神經網絡與矩陣分解結合進行推薦;

(5)深度社交網絡推薦(Deep-SoR)[24]:利用深度神經網絡對用戶在社交關系中的特征進行訓練,并通過概率矩陣分解實現推薦;

(6)圖網絡推薦(GraphRec)[9]:根據社交關系和評分關系建立圖網絡,利用注意力機制迭代圖節點,訓練用戶、物品的嵌入表示來實現推薦.

3.4 實驗環境與超參數設置

本文采用Python 3.8,PyTorch 1.6,Cuda 10.2 作為搭建算法的環境,工作站CPU為4 核Intel(R)Core(TM)i5-7500@3.40 GHz,GPU 型號為NVIDIA GP102 [TITAN Xp].

本算法以batch為單位進行訓練,為了避免過擬合,在各非線性激活函數輸出端增加dropout 層,丟棄概率全局統一設置;同時在圖網絡的每一批次迭代中,對同一batch的用戶、物品向量表示進行批次歸一化.算法中的超參數經過驗證集(從訓練集中抽取20%得到)反復調整得到:嵌入維度(用戶、物品、評分采用統一嵌入維度)為64,GRU 縱向堆疊層數k=2,dropout 丟棄概率為0.5,批次大小為64,學習率為0.0005.

3.5 結果分析

本文在Ciao、Epionions 數據集分別選取60%、80%作為訓練集,其余作為測試集對提出的算法進行了驗證,并與第3.3 節列出的幾種基準模型進行了對比,RMSE和MAE比較結果如表2.

從表2的結果可以看出,本文所提出的基于AGRUGNN 算法在Ciao 數據集和Epinions 數據集上比表中所列的基準模型誤差更小.其中PMF和NCF 只利用了用戶與物品的評分數據,而SoRec、SocialMF、Deep-SoR和GraphRec 均使用了數據集中的社交關系數據,因此平均比同類模型具有更小的誤差.本文所采用的AGRU 聚合算法,通過GRU 對評分事件的時序信息提取,并加以注意力機制對不同時刻的輸出進行了有選擇的加權平均,結合社交局部圖使得用戶對物品的時變興趣信息能夠基于社交影響關系在用戶之間傳播,從而達到了更好的推薦效果.這證明了本文提出的算法在時序推薦數據集上具有一定的優越性.

我們還探究了不同超參數設置下,對本文推薦算法效果的影響.以Ciao(80%)數據集為例,基準超參數的設置為GRU 縱向堆疊層數k=2,dropout 概率為0.5,迭代周期數為5.圖4展示了在基準超參數設置下,模型預測誤差隨迭代周期數(epoch)的變化,一次迭代周期表示圖網絡中所有頂點U ∪V均被聚合迭代了一次.可以看出模型的收斂速度較快,5 個周期后便達到了最優值,隨著迭代次數的增加,模型出現了一定程度的過擬合.收斂速度快得益于GRU 對時序信息具有較強的表示能力,快速地提取了用戶、物品的時變特征;另一方面,由于GRU 內部結構較為復雜,也增大了模型的參數量,因此隨即出現了一定程度的過擬合現象.

表2 本文算法AGRU-GNN 與其他推薦模型對比結果

圖4 模型預測誤差隨迭代周期數的變化

GRU的層數一定程度上決定了模型的復雜程度,為了避免嚴重的過擬合,我們研究了不同GRU 層數設置對模型誤差的影響,如圖5.可以看出,雙層GRU 在此數據集上具有較好的推薦效果,而層數過大則存在較嚴重的過擬合,層數過小則削弱了模型對時序信息的學習能力.

為了更好地抑制過擬合,模型中在大部分非線性激活單元的輸出端以及GRU 層間加入了dropout 層,并通過全局統一的dropout 概率加以調節.圖6展示了模型最佳預測誤差隨dropout 概率的變化,以50%概率進行丟棄時,模型在預測誤差和過擬合之間達到了較好的平衡.即使以較大的概率75%進行丟棄,模型的功能依然沒有受損,但預測誤差開始陡增.

另外,我們還對比了本文模型的若干變種模型,分別為:

圖5 模型最佳預測誤差隨GRU 層數的變化

圖6 模型最佳預測誤差隨dropout 概率的變化

(1)AGRU-GNN:采用GRU 作為圖網絡時序聚合模型,并在物品-用戶圖、社交圖的鄰域聚合均采用了注意力機制,即本文提出的最終模型;

(2)GRU-GNN:禁用了模型中的注意力機制,其余參數與(1)相同;

(3)ARNN-GNN:采用Vanilla RNN 作為圖網絡時序聚合模型,也同時采用了注意力機制;

(4)GNN(即GraphRec[9]):基準圖網絡模型,主要采用注意力聚合.

四種變種模型分別在Ciao(80%)和Epinions(80%)數據集上進行了對比,結果如圖7所示.GRU 對時序信息的提取篩選能力明顯優于普通RNN,普通RNN對時序信息的選擇記憶、遺忘能力不足,導致ARNNGNN的推薦有效性甚至弱于基準模型GraphRec;另外,注意力機制的存在也對模型整體性能有一定提升,這說明注意力機制有助于在用戶的物品交互時間序列關注重點事件,同樣地,在社交圖中也對不同的好友存在不同的關注權重.

圖7 變種模型最佳預測誤差RMSE 對比

綜上所述,本文提出的基于AGRU的圖網絡聚合算法,在帶有時間戳及社交信息的推薦數據集Ciao、Epinions 上取得了良好的性能,證明了本算法中采用的AGRU 聚合從用戶時序評價歷史中提取了有效信息,提升了推薦系統的準確度.

4 結論與展望

本文在圖神經網絡GNN 架構的基礎上,基于推薦系統中評價事件的時序性以及用戶特征、物品特征的時變特點,提出了一種基于門控循環單元的注意力聚合算法.通過Ciao、Epinions 數據集,證明了本算法在時序評價數據集上具有更低的預測誤差,說明用戶的時變興趣、物品的時變特征對于推薦系統也至關重要.GRU 對于時間序列有較強的學習能力,后續工作可考慮基于此算法實現推薦系統的在線訓練,即輸入數據是隨時間流動的流式數據,圖結構也隨數據的增長動態變化,使GRU 從流式數據中捕獲動態的時序特征,以此實現推薦系統的在線演變和動態推薦.在線的動態推薦更加接近實際生活中的推薦系統產品,當然,還需要解決冷啟動、計算開銷大甚至是分布式架構設計等問題.