融合重要性采樣和池化聚合的知識圖推薦算法

梁順攀，涂 浩，王榮生，原福永，張熙瑞

1(燕山大學 信息科學與工程學院，河北 秦皇島 066004)

2(河北省軟件工程重點實驗室(燕山大學)，河北 秦皇島 066004)

1 引 言

由于互聯(lián)網上的信息逐漸演變?yōu)槎嘣串悩嬓畔ⅲ瑘D神經網絡(GNN)因其更強大的數(shù)據(jù)表達能力得到廣大研究者的密切關注.基于GNN方法的模型也產生了許多的優(yōu)化變種.一些方法側重于對采樣策略的設計.如PinSage[1]方法使用隨機游走的方法進行鄰域采樣，在大規(guī)模圖網絡中取得了不錯的效果.另一些方法側重于如何聚合鄰居節(jié)點的特征，如GAT[2]方法采用注意力機制學習相鄰節(jié)點的特征權重并聚合，通過度量每個鄰居節(jié)點與中心節(jié)點之間特征向量的相關性然后偏向性的聚合不同鄰居的特征.

同時，也有越來越多的學者將GNN應用到知識圖推薦系統(tǒng)中.Rex等人將GNN應用于二部圖推薦模型[3]，并將其部署在Pintereset上.Wang等人提出了RippleNet[4]和KGCN[5].RippleNet是一個向外傳播模型，它在基于每個用戶的潛在首選項的路徑中擴散用戶的興趣項，以生成用戶表示.KGCN利用鄰域聚合來計算項目表示.此外，可以將鄰居聚合擴展到多層節(jié)點之外，并允許模型捕獲高階和遠程實體依賴關系.Wang等人提出知識圖注意力網絡(KGAT)[6]，在知識圖上利用注意力網絡，遞歸地生成用戶和項目嵌入表示.這些方法也遇到了一些新的問題，如，當GCN聚合鄰居節(jié)點時，圖卷積網絡存在鄰居爆炸問題.在基于GNN的推薦模型中，當前層中每個節(jié)點的表示是從其鄰居的上一層表示中聚合出來的.隨著跳數(shù)的增加，多跳鄰居會消耗大量的計算資源.為了解決這個問題，現(xiàn)有的基于GNN方法的知識圖推薦算法，如PinSage，RippleNet和KGCN，均采用“固定鄰域”策略，在每一層模型只采樣固定大小的鄰居，而不是使用完整的鄰居集，以減少計算成本.

除了鄰居爆炸問題，基于GNN的知識圖推薦模型，如KGCN，Pinsage，當圖形特征的階數(shù)增加時，大量的噪聲實體和模型參數(shù)維數(shù)的增長將導致訓練過程難以收斂.Tai等人提出了一種基于階段訓練框架GraphSW[7].在每一個階段，只用KG中一小部分實體而不是大規(guī)模實體以此來探索關鍵信息，分批次進行訓練，后續(xù)的批次可以共享前一批次學習到的權值.該框架在加速模型的訓練上取得了不錯的效果，但并未直接解決以上問題.因此，本文針對以上問題從鄰域采樣和鄰域聚合兩個角度進行了探索，提出了基于關系緊密度的采樣策略和平均池化聚合策略，在選擇鄰域時，依據(jù)關系緊密度來衡量不同鄰居對當前節(jié)點的重要程度，選擇對當前節(jié)點更重要的鄰居進行采樣，換言之，采樣更有可能帶來有價值信息的鄰居，這種方式可以減少隨機采樣帶來的不確定性，也可以預先給模型一個訓練導向，加速訓練過程.而在聚合鄰域時，本文使用mean-pooling聚合代替均值聚合，其可以更有效的捕捉更關鍵的信息而減少因維數(shù)增加產生的大量噪聲.最后，本文在KGCN模型上應用本文所提出的策略，并采用GraphSW框架加速訓練過程，對5個真實數(shù)據(jù)集(BookCrossing，MovieLens-1M，LFM-1b 2015，Amazon-book 和Yelp 2018)進行了實驗.結果表明，本文提出的策略可以幫助KGCN更快的從KG中收集到更關鍵的信息，并改進其在所有數(shù)據(jù)集上的推薦性能.

本文的主要貢獻如下：

1)本文提出了一種基于關系緊密度的啟發(fā)式采樣策略，通過重要性采樣選取更具代表性的鄰域節(jié)點.

2)本文提出了一種基于池化操作的聚合策略，通過一種可學習的差異化聚合方式更好的聚合鄰域信息，進而得到當前節(jié)點的嵌入表示.

3)在真實數(shù)據(jù)集上的實驗結果表明本文提出的改進模型KGCN-PL可以有效的提升推薦效果.

2 基于重要性采樣和池化聚合的知識圖推薦算法

2.1 本文改進后的模型

在結合重要性采樣和池化聚合方法之后，本文提出的改進模型KGCN-PL如圖1所示.首先通過計算關系緊密度作為鄰居的重要性并以此作為采樣標準對鄰居進行篩選，其中中心灰色節(jié)點為待訓練節(jié)點，外圍灰色節(jié)點則為被采樣鄰居節(jié)點，白色節(jié)點為非采樣鄰居節(jié)點.然后根據(jù)所采樣鄰居節(jié)點進行池化聚合，并結合自身節(jié)點特征聚合成新的節(jié)點表示.最后將聚合得到的項目嵌入與用戶嵌入相乘得到最終預測結果.采用Graph-SW框架加速訓練，對輸入節(jié)點進行分批次訓練，第一批初始權重隨機，后續(xù)批次使用上一批次訓練權重作為初始權重.最終得到所有預測結果.KGCN-PL算法流程如算法1所示.

圖1 KGCN-PL模型圖

算法1.KGCN-PL算法

輸入：數(shù)據(jù)集用戶-項目交互矩陣Y、知識圖g、鄰域采樣集合S(e)、參數(shù)Θ

輸出：預測用戶項目交互概率

F(u，v|Θ，Y，G)

1.使用Graph-SW框架分T批次訓練.

2.for i=0，…，Tdo

3. while KGCN-pl[i]未收斂 do

4. for(u，v)inYdo

6.eu[0]←e，?e∈ε[0]；

7. fork= 1，…，Hdo

8. fore∈E[k]do

11. end

12. end

13.vu←eu[H]；

16. 梯度下降更新參數(shù)；

17. end

18. returnF，w

19.end

20.returnF；

21.Function 獲取鄰域集合：

22.ε[H]←v；

23.for k = H-1，…，0 do

24.ε[k]←ε[k+1]；

25. for e∈ε[k+1]do

26.ε[k]←ε[k]∪S(e)；

27 end

28.end

2.2 基于關系緊密度的采樣方法

基于GNN的推薦模型通常使用隨機的固定大小的鄰居采樣方式，由于計算資源有限，使用少量樣本模擬全部樣本固然可行，但是隨機采樣的方式會導致模型效果的不穩(wěn)定，很容易丟失重要的鄰居節(jié)點信息.本文考慮在采樣過程中更有針對性的選擇相對重要的鄰域節(jié)點以使模型更容易的學到用戶偏好.具體來說，本文計算網絡中所有節(jié)點與中心節(jié)點之間的關系緊密度，值越高則說明該節(jié)點對于中心節(jié)點越重要，即為本文的采樣目標節(jié)點.在沒有獲取節(jié)點具體特征的情況下，常用的計算關系緊密度的指標有CN系數(shù)(common neighbors)[8]，Adamic/Adar系數(shù)[9]，RA系數(shù)(資源分配系數(shù))[10]等，相關公式如下，其中Sxy代表鄰域節(jié)點y和中心節(jié)點x的關系緊密度，Γ(x)表示節(jié)點x的1階鄰居節(jié)點集合，k(i)為節(jié)點度值.

CN共同鄰居數(shù)公式如式(1)所示：

Sxy=|Γ(x)∩Γ(y)|

(1)

AA系數(shù)公式如式(2)所示：

(2)

RA系數(shù)公式如式(3)所示：

(3)

其中CN系數(shù)直接比較共同鄰居的數(shù)量，以共同鄰居的數(shù)量考量關系緊密度，共同鄰居數(shù)越多，節(jié)點間關系更緊密.RA系數(shù)在共同鄰居數(shù)的基礎上引入了度值的考量，對共同鄰居的影響加以區(qū)分，認為共同鄰居的度值越高越有價值.AA系數(shù)對RA系數(shù)中的度值計算做了取對數(shù)處理，它考慮到可能存在某些節(jié)點的度數(shù)過高對關系緊密度的計算帶來干擾，比如一個節(jié)點與大部分節(jié)點相連，那么它必然成為很多節(jié)點的共同鄰居，而它的度值很大，使得其它共同鄰居的作用變得很小，這使得度值大小反而不利于計算關系緊密度，故而對其取對數(shù)處理可以縮小度值的絕對值，這樣可以有效的考慮度值因素帶來的影響，而又不使其影響過大.

考慮到推薦場景中知識圖中節(jié)點共同鄰居數(shù)量并不多，度值大的節(jié)點僅僅表示該實體特征比較平均，而計算度值會帶來指數(shù)級的計算量成本，故而本文采用CN系數(shù)作為關系緊密度計算標準.

通過計算關系緊密度，即可獲取一個按關系緊密度排序的節(jié)點列表，選取固定大小的前n個節(jié)點作為本文選擇的鄰域.考慮到推薦數(shù)據(jù)集通常比較稀疏，節(jié)點度值通常較小，對采樣影響較小，為便于計算，本文采用CN系數(shù)作為采樣標準.具體算法流程如算法2所示.實驗結果表明，加入了采樣策略后的推薦模型可以在較少批次下的訓練達到隨機采樣更多批次下后的訓練效果，模型會更快的收斂.分析認為，加入重要性采樣因素，實際相當于給推薦模型指導了一個方向，使其更易于找到更突出的特征，減少模型維數(shù)增長帶來的噪聲.

算法2.重要性采樣算法

輸入：實體e，知識圖G，e的鄰域S(e)

輸出：e的n階采樣鄰域Sk(e)

1.for i = 0，…，ndo

2. 計算cal[v1]=S(v1)∩S(e)

3. end

5.end

2.3 基于池化操作的聚合方法

在KGCN中，提出了3種聚合方式，即Sum，Concat和neighbour，然而三者的區(qū)別僅在與是否保留自身節(jié)點的特性，以及鄰居和自身的結合方式，主要針對鄰域與自身的聚合.在鄰域的聚合方式上均使用均值聚合，這種直接求均值的聚合方式可能會丟失很多特征信息，在KGCN中也提出了一種策略，使用用戶嵌入和關系矩陣相乘求得用戶關系評分，從而獲取一個用戶偏見權重，類似于GAT方法，但是由于關系矩陣是隨機采樣后的矩陣，所以其并不能表示用戶真正的興趣偏好，經實驗驗證該方法對有效捕獲鄰居特征并無明顯幫助.受GraphSage[11]的啟發(fā)，本文發(fā)現(xiàn)在鄰域聚合過程中，使用對稱可訓練的函數(shù)可能有益于更好的捕捉鄰域的不同方面的特征，本文在實驗幾種聚合方法后，使用mean-pooling方法作為鄰域聚合方法.在這種池方法中，每個鄰居的向量通過一個完全連接的神經網絡獨立地輸入；在此轉換之后，平均池化操作被應用于跨鄰居集聚合信息，如式(4)所示.

(4)

Meanpooling方法通常用于卷積層之后，作為特征提取層聚合新的特征.如圖2所示，本文將其應用于全連接層結構之后充當特征提取層.簡單來說，首先為鄰域中的每個節(jié)點表示計算特征向量，然后引入一個全連接層學習權重信息，再通過均值池化將鄰域向量聚合.最后與自身節(jié)點表示進行聚合以保留部分原始信息，如式(5)所示.該方法有效地捕獲了多層鄰居的不同方面特征，并將其聚合到節(jié)點表示當中.

圖2 池化聚合示例圖

(5)

3 實驗與結果

在本節(jié)中，為了評估本文所提出的兩種改進策略的有效性，本文在KGCN中使用本文的改進策略，并使用分級訓練Graphsw框架得到本文的改進模型KGCN-PL.在CTR任務中，使用MovieLens-1M和Book-Crossing2個數(shù)據(jù)集與基于知識圖嵌入的模型CKE[12]，SHINE[13]，基于鏈路的模型PER[14]，KGCN原模型以及僅使用GraphSW框架的KGCN-SW這5個近年提出的效果最優(yōu)異的知識圖推薦模型進行對比評測.另外，為了驗證所改進模型的泛化性能，在Top-K任務中，使用5個數(shù)據(jù)集與KGCN以及KGCN-SW進行了詳細的對比評測.

3.1 評價指標

為了更直觀的體現(xiàn)本文所提出的兩種改進策略的作用，本文使用在KGCN論文中所使用的同時也是推薦系統(tǒng)在CTR任務中最常用的指標AUC進行驗證.另外，在Top-K任務中，也使用常用指標Recall進行驗證.

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

本文在CTR和Top-K任務中一共使用了5個數(shù)據(jù)集(Book-Crossing，MovieLens-1M，LFM-1b 2015，Amazon-book，Yelp 2018)驗證本文提出的方法，下面簡單介紹一下各個數(shù)據(jù)集的基本情況.

MovieLens-1M：MovieLens-1M數(shù)據(jù)集是電影推薦中廣泛使用的基準數(shù)據(jù)集，該數(shù)據(jù)集包含大約6036名用戶，總共2445個條目，100萬條評分記錄(從1到5).

Book-Crossing：Book-Crossing數(shù)據(jù)集是從book-crossing社區(qū)收集的.它包含139746條評分記錄(從0到10)對應14967個項目和17860名用戶.

LFM-1b 2015：LFM-1b 2015是關于記錄藝術家、專輯、音軌和用戶的音樂以及個人收聽事件信息的數(shù)據(jù)集.數(shù)據(jù)集包含總共有15471個項目，12134用戶以及300萬條的評分記錄.

Amazon-book：Amazon-book是關于用戶對圖書產品的偏好的數(shù)據(jù)集.它記錄關于用戶、項目、等級和時間戳的信息.數(shù)據(jù)集包含9854個項目，7000名用戶以及50萬條評分記錄.

Yelp2018：Yelp2018是Yelp挑戰(zhàn)賽2018年版的數(shù)據(jù)集，是關于當?shù)仄髽I(yè)的.數(shù)據(jù)集包含16000名用戶，14000個項目和120萬條評分記錄.

3.3 實驗和結果

在本節(jié)中，本文分別針對CTR和Top-k兩個任務分析評估本文所提出的策略的有效性.在CTR任務中，本文首先選取數(shù)據(jù)豐富的Movielens-1M和數(shù)據(jù)相對稀疏的Book-crossing兩個數(shù)據(jù)集將本文提出的改進模型KGCN-PL與5個近年來表現(xiàn)優(yōu)異的相關基線模型進行對比評測.如圖3和圖4所示，其中CKE使用實體嵌入方法學習知識圖譜中的實體特征，由于未能直接將知識圖譜中的實體特征用于推薦任務，因此效果比較差.SHINE原本為處理社交網絡信息而設計，這里用于處理知識圖譜信息，效果不是很好，這可能與社交網絡和知識圖譜本身的結構差異有關.而PER過于依賴元路徑的設計，在沒有專家設計元路徑的情況下在兩個數(shù)據(jù)集均取得了最差的效果.KGCN-PL在信息更豐富的Movielens-1M數(shù)據(jù)集上取得了一定的優(yōu)勢，由于有效數(shù)據(jù)很豐富，KGCN本身也可以在多輪訓練后在該數(shù)據(jù)集上取得很好的效果，此時KGCN-PL在訓練速度上會更有優(yōu)勢.在數(shù)據(jù)較為稀疏的Book-Crossing數(shù)據(jù)集上，本文的KGCN-PL獲得了更明顯的優(yōu)勢，這證明了本文所提出的策略在捕獲重要特征，且在彌補數(shù)據(jù)稀疏性上有一定的作用.此外，為了驗證本文的改進策略的泛化性能，本文在Yelp2018、LFM-1b2015、Amazon-book3個數(shù)據(jù)集上與KGCN和KGCN-SW進行進一步對比評測，如圖5、圖6和圖7所示，實驗結果表明KGCN-PL在以上3個數(shù)據(jù)集上與KGCN相比同樣取得了有效的提升，這證明了本文提出的改進策略具有很好的泛化性能.

圖3 MovieLens-1M AUC對比柱狀圖

圖4 Book-crossing AUC對比柱狀圖

圖5 Yelp2018AUC對比柱狀圖

圖6 LFM-1b2015 AUC對比柱狀圖

圖7 Amazon-book AUC對比柱狀圖

在Top-K任務中，本文取K=25和K=50兩種情況，在5個數(shù)據(jù)集上進行實驗.如表1所示.結果表明，本文的KGCN-PL在所有數(shù)據(jù)集上與KGCN以及KGCN-SW相比推薦效果均有提升.其中在更有說服力的R@25上與之前效果更好的KGCN-SW對比在MovieLens-1M，Book-Crossing，LFM-1b 2015，Amazon-book，Yelp2018上分別取得了2.5%，8.1%，15.2%，14.3%，3.6%的提升，這進一步證明本文所提出的策略是具有泛化性的，并且在數(shù)據(jù)稀疏的數(shù)據(jù)集上可以提供更多幫助.

表1 在各個數(shù)據(jù)集中進行Top-K任務的Recall@25 和Recall@50的結果

4 總 結

本文提出了基于重要性的采樣策略和基于池化操作的聚合策略，并將其應用在最新的GNN知識圖推薦模型中，分別從鄰域采樣和鄰域聚合兩個角度有效的緩解維數(shù)增多帶來的噪聲問題以及模型難以收斂的問題.實驗結果表明，使用本文提出的兩種改進策略后，模型在準確度和效率方面優(yōu)于現(xiàn)有的最新的基于知識圖的推薦模型.因此，本文的方法是可行且高效的.在今后的工作中，本文考慮在保證訓練效率的情況進一步探索非固定鄰域采樣方法.