基于融合元路徑的圖神經(jīng)網(wǎng)絡(luò)協(xié)同過濾算法①

蔣宗禮,田聰聰

(北京工業(yè)大學(xué) 信息學(xué)部,北京 100124)

隨著網(wǎng)絡(luò)信息技術(shù)的發(fā)展,推薦系統(tǒng)被廣泛應(yīng)用到社交媒體網(wǎng)絡(luò)、新聞推送、購物平臺等領(lǐng)域.根據(jù)實現(xiàn)思想不同,推薦算法主要分為3 類:基于內(nèi)容的推薦、基于協(xié)同過濾的推薦以及混合推薦方法[1].

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

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

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

(1)在圖神經(jīng)網(wǎng)絡(luò)協(xié)同過濾算法中引入元路徑,基于元路徑的隨機游走生成用戶和商品的潛在特征,并引入融合函數(shù)及權(quán)重對多條元路徑的表征融合.

(2)將圖神經(jīng)網(wǎng)絡(luò)生成的高階特征與異質(zhì)網(wǎng)中元路徑生成的潛在特征有效融合,并做評分預(yù)測.

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

1 基本概念

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

如圖1(b)所示表示的是IMDB 數(shù)據(jù)集構(gòu)成的異質(zhì)信息網(wǎng)絡(luò).如圖1(a)所示,該異質(zhì)網(wǎng)絡(luò)有3 種類型的節(jié)點,分別是演員、電影和導(dǎo)演.同時有兩種類型的邊,分別是演員和電影之間的關(guān)系以及電影和演員之間的關(guān)系.

圖1 異質(zhì)信息網(wǎng)絡(luò)及元路徑

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

在異質(zhì)信息網(wǎng)絡(luò)中不同類型的實體間的關(guān)系可以用元路徑表示.

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

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

2 融合元路徑的圖神經(jīng)網(wǎng)絡(luò)協(xié)同過濾算法

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

2.1 圖神經(jīng)網(wǎng)絡(luò)協(xié)同過濾

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

2.1.1 嵌入層

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

2.1.2 傳播層

根據(jù)用戶和商品的鄰接矩陣,將特征向量與其鄰居節(jié)點向量融合,然后通過多層神經(jīng)網(wǎng)絡(luò)進行信息傳遞得到最終的特征向量.

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

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

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

2.2 異質(zhì)信息網(wǎng)絡(luò)中的低維表征

2.2.1 元路徑的隨機游走

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

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

通過Skip-gram 模型學(xué)習異質(zhì)網(wǎng)中節(jié)點的低維表征,優(yōu)化函數(shù)如式(8)所示.其中Nt表示頂點為v的鄰居節(jié)點中類型為t的集合.

2.2.2 低維表征融合

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

2.3 模型預(yù)測

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

2.4 模型優(yōu)化

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

3 實驗結(jié)果與分析

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

3.1 數(shù)據(jù)集

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

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

3.2 評價指標

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

3.3 方法對比

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

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

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

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

表1 數(shù)據(jù)集的具體信息

表2 數(shù)據(jù)集的元路徑

3.4 實驗結(jié)果及分析

3.4.1 確定訓(xùn)練集比例

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

圖2 RMSE 在不同訓(xùn)練集比例下的值

3.4.2 用戶和商品的歷史互動

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

在這個部分只保留用戶和商品的歷史互動,而不考慮異質(zhì)信息網(wǎng)絡(luò)中用戶和商品的潛在的語義信息.在3 種數(shù)據(jù)集上分別實驗,RMSE值的結(jié)果如表3所示.

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

3.4.3 異質(zhì)信息網(wǎng)絡(luò)中的語義信息

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

表4 異質(zhì)網(wǎng)中的語義信息

3.4.4 預(yù)測函數(shù)中的權(quán)重系數(shù)

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

圖3 RMSE 在不同α 下的值

3.4.5 實驗結(jié)果與分析

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

表5 實驗結(jié)果

4 結(jié)論與展望

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