基于融合元路徑的圖神經網絡協同過濾算法①

蔣宗禮,田聰聰

(北京工業大學 信息學部,北京 100124)

隨著網絡信息技術的發展,推薦系統被廣泛應用到社交媒體網絡、新聞推送、購物平臺等領域.根據實現思想不同,推薦算法主要分為3 類:基于內容的推薦、基于協同過濾的推薦以及混合推薦方法[1].

協同過濾[2]作為應用最廣泛的一種推薦算法,其主要思想是由用戶對商品的偏好發現用戶之間的關聯性,基于關聯性進行推薦,即相似度高的用戶往往有相似的偏好.一般來講,協同過濾主要通過用戶和商品的歷史交互信息建模(如評分、點擊率等),并得到它們的嵌入表示.如矩陣分解[3]將用戶和商品映射到同一維度的隱空間中,并使用內積計算用戶對商品的偏好程度.近年來,深度學習的發展進一步提高了推薦系統的性能.He 等[4]提出的NCF 模型通過整合傳統的矩陣分解和MLP 進一步優化傳統模型.Wang 等[5]提出的NGCF 模型構建用戶-商品的二部圖,通過圖模型嵌入用戶和商品的歷史互動到特征向量中.雖然這些方法提升了推薦系統的性能,但是當用戶和商品的數量增多,推薦系統可能會面臨據稀疏性和冷啟動等問題,從而無法實現個性化推薦.

近些年來,異質信息網絡[6]由于包含多種類型的結點和邊,被廣泛應用到各個領域中[7–9].由于異質信息網絡能表征豐富的輔助信息,基于異質網的推薦算法被學者廣泛研究.Sun 等[10]提出的PathSim 基于元路徑的相似性做推薦.Feng 等[11]提出的OptRank 基于異質信息解決社交推薦系統的冷啟動問題.Yu 等[12]基于異質網實體間的關系,進一步優化推薦算法.Shi等[13]將隨機游走得到的異質信息與傳統的矩陣分解模型做融合.這些方法通過異質信息網絡中的輔助信息,得到了用戶和商品的潛在特征,但是可能會忽略用戶和商品的歷史互動等信息.

針對以上問題,本文提出了基于融合元路徑的圖神經網絡協同過濾算法.該算法基于NGCF[4]模型,首先構建用戶和商品的二部圖,將它們的歷史互動嵌入到特征向量中,然后通過神經網絡多層傳播獲取用戶和商品的高階表示.異質信息網絡中不僅有用戶和商品兩種類型的結點,還存在其他的結點類型和邊類型,這些節點會影響到用戶和商品的表征.為充分利用異質網絡中的語義信息,在模型的基礎上引入元路徑獲取潛在的信息.而不同的元路徑往往有不同的含義,得到多條元路徑的潛在特征后,引入融合函數及權重對多條元路徑的信息有效融合.總結來說,本文的主要貢獻可概括為以下3 點:

(1)在圖神經網絡協同過濾算法中引入元路徑,基于元路徑的隨機游走生成用戶和商品的潛在特征,并引入融合函數及權重對多條元路徑的表征融合.

(2)將圖神經網絡生成的高階特征與異質網中元路徑生成的潛在特征有效融合,并做評分預測.

(3)在公開數據集Yelp、Amazon Book 和Amazon Movie 數據集上做實驗,并與傳統算法比較,驗證了算法的有效性.

1 基本概念

定義1.異質信息網絡(heterogeneous information network)[14].異質信息網絡可表示為G=(V,E),其中V表示節點的集合,E表示邊的集合.對于每一個結點存在一種映射關系 φ:V→A,對于每一條邊存在一種映射關系 φ:E→R,A和R分別代表結點類型和邊類型,且|A|+|R|＞2.

如圖1(b)所示表示的是IMDB 數據集構成的異質信息網絡.如圖1(a)所示,該異質網絡有3 種類型的節點,分別是演員、電影和導演.同時有兩種類型的邊,分別是演員和電影之間的關系以及電影和演員之間的關系.

圖1 異質信息網絡及元路徑

定義2.網絡模式(network schema)[15].對于給定的網絡G=(V,E),V表示結點的集合,E表示邊的集合,且有映射關系 φ:V→A和φ:E→R,定義其網絡模型為TG=(A,R).

在異質信息網絡中不同類型的實體間的關系可以用元路徑表示.

定義3.元路徑(meta-path)[16].給定網絡模型TG=(A,R),元路徑可定義連接多種結點類型的一組關系,具體形式為其中Ri表示結點間的關系.

如圖1(c)中列舉了兩條元路徑,分別是MDM 和MAM.這兩條元路徑有不同的語義信息,其中MDM代表同一導演編導了不同的電影,而MAM 代表了同一演員出演了不同的電影.為了更豐富的表征異質網中的信息,我們在獲取電影的特征向量時,會賦予這兩條元路徑不同的權重.

2 融合元路徑的圖神經網絡協同過濾算法

這部分主要介紹基于融合元路徑的圖神經網絡協同過濾模型.第一階段基于NGCF[4]框架先構建二部圖,將用戶和商品的歷史互動嵌入到特征向量中,并通過神經網絡傳播.異質信息網絡中包含多種類型的節點和邊.為了更豐富的表征用戶和商品,在第二階段通過元路徑的隨機游走獲取用戶和商品的低維表征,并將多條元路徑的潛在特征有效融合.第三階段將用戶和商品的低維表征與高階特征融合并做評分預測.

2.1 圖神經網絡協同過濾

從用戶和商品的向量點積中很容易看出用戶對商品的偏好程度.傳統推薦算法,如矩陣分解等沒有將交互信息嵌入到特征向量中,只是用ID 等屬性初始化向量,用交互信息優化模型.為了從用戶和商品的歷史互動獲取二者的高階特征,在本文中我們采用NGCF 模型.該模型主要分為3 層:輸出層、嵌入層和傳播層.

2.1.1 嵌入層

嵌入層將輸入的稀疏向量轉化為稠密向量,隨機初始化用戶和商品的向量矩陣E∈R(M+N)×d,如式(1)所示,其中用戶數量為M,商品數量N,d為表示維度的大小.

2.1.2 傳播層

根據用戶和商品的鄰接矩陣,將特征向量與其鄰居節點向量融合,然后通過多層神經網絡進行信息傳遞得到最終的特征向量.

對于用戶商品的任一結點對(u,i),定義從商品i到用戶u的信息傳遞函數為式(2)所示.其中ei為商品的特征向量,eu為用戶的特征向量,為用戶u和商品i之間的權重系數,Nu>和Ni分別代表用戶和商品的鄰居結點個數,W1,W2∈Rd′×d是權重矩陣參數,⊙為向量對應元素之間的乘積.

式(2)是針對一個鄰居節點的表示,由于用戶的鄰居節點可能有多個,故用戶最終的向量表示是其所有鄰居結點的融合.通過l層的信息傳遞,用戶可以獲得其l階鄰居的信息,第l層的特征向量表示為式(3)所示.從中可以看出信息傳遞過程中用戶不僅融合了其鄰居結點商品的特征,而且保留了用戶本身的特征.

經過l層傳播得到用戶向量表示可為集合商品向量可表示為用戶和商品的特征向量最終表示為式(6)所示,其中‖ 表示向量之間的拼接.

2.2 異質信息網絡中的低維表征

2.2.1 元路徑的隨機游走

對于DeepWalk[16]和Node2Vec[17]采用的是隨機游走生成網絡中的節點序列,這種方式的隨機游走會偏向于節點類型多的節點.為了解決這個問題,Dong 等[18]提出的Metapath2Vec 基于元路徑的隨機游走,能更好的涵蓋異質網中豐富的語義信息.首先基于元路徑進行隨機游走生成節點序列,然后采用Skip-gram 學習異質網中的低維表征.

在得到隨機游走的節點序列后,由于我們關注的用戶和商品的低維表征,所以進行節點類型限制和過濾[13].具體來說,只選擇以用戶、商品類型節點為起點的節點序列.并且在每條序列中,只保留與起點類型相同的節點,對其他類型的節點過濾.例如,對于元路徑MDM 我們可能游走出序列u1→m1→u2→m2→u3→m2→u4,對節點過濾得到u1→u2→u3→u4.

通過Skip-gram 模型學習異質網中節點的低維表征,優化函數如式(8)所示.其中Nt表示頂點為v的鄰居節點中類型為t的集合.

2.2.2 低維表征融合

對于給定的節點v,其元路徑對應的表征集合為其中p為元路徑的個數.現有的表征融合往往采用簡單的線性的融合方式,即賦予每條元路徑一個權重,這可能會造成表征質量降低.在本文中我們在權重的基礎上引入融合函數,融合公式如式(9)所示.其中為第i個 元路徑的權重,M(i)∈RD×d為權重矩陣,b(i)∈RD為權重參數.

2.3 模型預測

在2.1 節中通過圖神經網絡得到了用戶和商品的高階向量表示,2.2 節中通過元路徑得到了用戶和商品潛在的特征,模型最終預測為式(10)所示.其中eu及ei是通過圖神經網絡得到的特征向量,zu及zi是由元路徑得到的潛在向量,α為權重參數.

2.4 模型優化

為了更好地將高階特征與潛在向量融合起來,我們采用式(11)所示的函數優化.其中ru,i表示用戶和商品的實際分數,ru,i′是預測分數,eu及ei是通過圖神經網絡得到的特征向量,zu及zi是由元路徑得到的潛在向量,λ為權重參數,Θ(U)及Θ(I)分別表示模型中用戶和商品對應的參數.

3 實驗結果與分析

通過在Yelp、Douban book 及Douban movie 3 個數據集上做實驗,實驗結果表明均方根誤差都小于傳統模型,證明了算法的有效性.

3.1 數據集

為了證明算法的有效性,選取了3 個不同領域的數據集.Yelp是商務類型的數據,稀疏度為0.08%.Douban book是書籍類型的數據,稀疏度為0.27%.Douban movie是電影類型的數據,稀疏度為0.63%.3 種數據集的具體信息如表1所示.

在獲取用戶及商品的潛在特征向量階段會使用到元路徑,對于3 種數據集我們使用的元路徑如表2所示.以Yelp 數據集為例,用戶在神經網絡傳播層部分通過用戶和物品的交互可以得到UBU,同理物品在神經網絡傳播層部分通過物品和用戶的交互可以得到BUB 的路徑,所以在元路徑中不再使用這兩條元路徑.Douban movie 和Douban book 的元路徑中采用同樣的思想.

3.2 評價指標

在本文中采用均方根誤差(RMSE)評價推薦模型,均方根誤差是均方誤差的算數平方根.均方誤差指的是參數估計值和參數真實值之差平方的期望值.其中均方根誤差值越小,推薦模型的效果越好,預測越精確.它的表示如式(12)所示.其中Dtest表示測試集數據,ru,i和ru,i′分別表示結點對(u,i)的實際分數和模型的預測分數.

3.3 方法對比

為了驗證算法的有效性,采取以下模型作為對比:

(1)HeteMF[12]:基于異質網中元路徑的相似性做推薦.

(2)SoMF[19]:基于社交網絡的推薦模型,提出了具有社會正則化的矩陣分解模型.

(3)SemRec[20]:基于協同過濾的思想,在加權異質信息網絡中考慮不同元路徑之間用戶和商品的相似度做推薦.

表1 數據集的具體信息

表2 數據集的元路徑

3.4 實驗結果及分析

3.4.1 確定訓練集比例

通過改變訓練集與測試集的比例,測試模型在不同比例下RMSE的值.對于Yelp 數據,由于比較稀疏將訓練集數據的比例設為{90%,80%,70%,60%},而對于Douban movie 和Douban book 將訓練集數據的比例設為{80%,60%,40%,20%},實驗結果如圖2所示,從左到右分別為Yelp、Douban movie 及Douban book的實驗結果.從圖2中可以看出Yelp 數據在訓練集數據占90%時RMSE達到最好的結果;Douban movie及Douban book 數據在訓練集數據占80%時RMSE達到最好的結果.所以我們將Yelp 的訓練集和測試集的比例設為9:1,而Douban movie 及Douban book 的訓練集和測試集的比例設為8:2.

圖2 RMSE 在不同訓練集比例下的值

3.4.2 用戶和商品的歷史互動

在模型最后的預測中既考慮了用戶和商品的高階歷史互動,又考慮了異質信息網絡中用戶和商品的潛在語義信息.為了證明模型的有效性,將分別討論用戶和商品的歷史互動及異質網中的語義信息對RMSE結果的影響.

在這個部分只保留用戶和商品的歷史互動,而不考慮異質信息網絡中用戶和商品的潛在的語義信息.在3 種數據集上分別實驗,RMSE值的結果如表3所示.

表3 用戶和商品的歷史互動

3.4.3 異質信息網絡中的語義信息

在這個部分只保留異質信息網絡中用戶和商品的潛在語義信息,而不考慮用戶和商品的歷史互動的信息.同時在原有的元路徑基礎上,加上用戶和物品的交互.在3 種數據集上分別實驗,RMSE值的結果如表4所示.

表4 異質網中的語義信息

3.4.4 預測函數中的權重系數

我們通過調整預測函數中的權重參數 α,研究這個權重參數時如何影響模型性能的.選定參數 α的值在集合{0.5,0.7,0.9,1.1}間調整.實驗結果如圖3所示,從圖中可以看出RMSE的值隨著 α的增大先下降后上升,在0.9 時RMSE達到最小值.

圖3 RMSE 在不同α 下的值

3.4.5 實驗結果與分析

3 種數據集在不同模型上的實驗結果如表5所示,表中的數字代表實驗結果RMSE的值.由實驗結果可知,基于融合元路徑的圖神經網絡協同過濾算法比傳統的推薦算法有一定提高.同時與表3中只考慮用戶和商品的歷史互動以及表4中只考慮異質信息網絡中的潛在語義信息的結果相比,融合元路徑的圖神經網絡模型的RMSE值更小.本模型通過圖神經網絡模型既考慮了用戶和商品的歷史互動,又通過元路徑考慮了異質信息網絡中的語義信息,并將兩者有效的融合起來,RMSE值更小,推薦效果更好.

表5 實驗結果

4 結論與展望

本論文通過分析傳統推薦算法的缺點,提出了基于融合元路徑的圖神經網絡協同過濾算法.該算法既考慮了異質信息網絡中的語義信息,通過元路徑獲取潛在的信息,并引入融合函數和權重對多條元路徑的表征融合,避免了冷啟動及數據稀疏等問題.同時又充分利用了用戶和商品的歷史互動,通過二部圖嵌入用戶和商品的特征,圖神經網絡的多層傳播得到高階向量.本論文還與傳統的推薦算法對比,證明了模型的有效性.在未來的工作中,我們將進一步優化元路徑的融合方式,將注意力機制[21]引入元路徑中,獲取異質信息網絡中更精準的語義信息.