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

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

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

2(河北省軟件工程重點(diǎn)實(shí)驗(yàn)室(燕山大學(xué))，河北 秦皇島 066004)

1 引 言

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

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

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

本文的主要貢獻(xiàn)如下：

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

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

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

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

2.1 本文改進(jìn)后的模型

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

圖1 KGCN-PL模型圖

算法1.KGCN-PL算法

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

輸出：預(yù)測(cè)用戶項(xiàng)目交互概率

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

1.使用Graph-SW框架分T批次訓(xùn)練.

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 基于關(guān)系緊密度的采樣方法

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

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

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

(1)

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

(2)

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

(3)

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

考慮到推薦場(chǎng)景中知識(shí)圖中節(jié)點(diǎn)共同鄰居數(shù)量并不多，度值大的節(jié)點(diǎn)僅僅表示該實(shí)體特征比較平均，而計(jì)算度值會(huì)帶來(lái)指數(shù)級(jí)的計(jì)算量成本，故而本文采用CN系數(shù)作為關(guān)系緊密度計(jì)算標(biāo)準(zhǔn).

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

算法2.重要性采樣算法

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

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

1.for i = 0，…，ndo

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

3. end

5.end

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

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

(4)

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

圖2 池化聚合示例圖

(5)

3 實(shí)驗(yàn)與結(jié)果

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

3.1 評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

Amazon-book：Amazon-book是關(guān)于用戶對(duì)圖書(shū)產(chǎn)品的偏好的數(shù)據(jù)集.它記錄關(guān)于用戶、項(xiàng)目、等級(jí)和時(shí)間戳的信息.數(shù)據(jù)集包含9854個(gè)項(xiàng)目，7000名用戶以及50萬(wàn)條評(píng)分記錄.

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

3.3 實(shí)驗(yàn)和結(jié)果

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

圖3 MovieLens-1M AUC對(duì)比柱狀圖

圖4 Book-crossing AUC對(duì)比柱狀圖

圖5 Yelp2018AUC對(duì)比柱狀圖

圖6 LFM-1b2015 AUC對(duì)比柱狀圖

圖7 Amazon-book AUC對(duì)比柱狀圖

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

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

4 總 結(jié)

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