王瑋皓
(1.南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106)
(2.模式分析與機(jī)器智能工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室 南京 211106)
隨著網(wǎng)絡(luò)和通信技術(shù)的發(fā)展,互聯(lián)網(wǎng)信息爆炸式增長(zhǎng),涌現(xiàn)出購(gòu)物、新聞、音樂(lè)、視頻、微博等豐富的互聯(lián)網(wǎng)服務(wù),用戶(user)面臨的選擇也越來(lái)越多,但過(guò)多的選擇未必起到完全正面的作用[1],用戶花費(fèi)大量時(shí)間機(jī)械地瀏覽可能并不感興趣的物品(item),導(dǎo)致互聯(lián)網(wǎng)經(jīng)濟(jì)效率下降,這一現(xiàn)象稱為信息過(guò)載。推薦系統(tǒng)是解決信息過(guò)載的一種方案,例如在線購(gòu)物平臺(tái)亞馬遜利用協(xié)同過(guò)濾技術(shù)提高了其零售效率[2]、Netflix舉辦競(jìng)賽來(lái)預(yù)測(cè)用戶對(duì)電影的評(píng)分[3]等。推薦系統(tǒng)建模的對(duì)象是用戶、物品及用戶對(duì)物品的點(diǎn)擊、瀏覽、購(gòu)買、評(píng)價(jià)等交互行為,此外,還存在用戶資料、物品屬性、上下文信息等其它輔助對(duì)象。推薦系統(tǒng)中的各類對(duì)象可用高維稀疏向量或圖結(jié)構(gòu)來(lái)表示。
高維稀疏向量表示法將用戶與物品的每個(gè)交互視為一個(gè)樣本,每個(gè)樣本包含了用戶和物品ID、用戶興趣分布、物品類目等特征域,而每個(gè)特征域都是一個(gè)one-hot或multi-hot編碼,因此特征維度高且稀疏,其標(biāo)簽(label)表示用戶對(duì)物品是否產(chǎn)生了交互行為,如圖1(a)所示。向量表示法構(gòu)造了表格形式的樣本特征和標(biāo)簽,可直接用于傳統(tǒng)機(jī)器學(xué)習(xí)模型的訓(xùn)練,但其缺點(diǎn)是獨(dú)立地對(duì)待每個(gè)樣本,無(wú)法顯式利用對(duì)象間的隱含語(yǔ)義關(guān)系,只能通過(guò)大量樣本的學(xué)習(xí)才能隱式地捕捉到這種聯(lián)系。例如,用戶u1購(gòu)買物品i1,用戶u2購(gòu)買物品i2,即構(gòu)成兩個(gè)樣本x1=(u1,i1)和x2=(u2,i2),假設(shè)物品i1可能是物品i2的配件,此時(shí)除非通過(guò)其他相關(guān)樣本的訓(xùn)練,如用戶u1同時(shí)也購(gòu)買了物品i2,即x3=(u1,i2),否則模型很難主動(dòng)捕捉到、并顯式地利用這樣的先驗(yàn)信息。所以,孤立對(duì)待每一次用戶-物品交互帶來(lái)了信息孤島問(wèn)題:無(wú)法利用用戶與用戶、物品與物品間的關(guān)聯(lián)性;模型表示能力不足;很難對(duì)冷門物品進(jìn)行有效推薦。
利用推薦系統(tǒng)中廣泛存在的圖結(jié)構(gòu)可以緩解信息孤島問(wèn)題。不難發(fā)現(xiàn),上述向量表示法的每一維都是一個(gè)對(duì)象,這些對(duì)象間又有所聯(lián)系,如用戶對(duì)物品產(chǎn)生的行為、物品之間的關(guān)系、用戶的社交關(guān)系等,因此它們可以構(gòu)成一個(gè)異構(gòu)圖G={V,?},如圖1(b)所示,其中用戶、物品、屬性等對(duì)象構(gòu)成了節(jié)點(diǎn)集合V,對(duì)象間的各種連接關(guān)系構(gòu)成邊集合?。圖結(jié)構(gòu)表示法直觀反映了對(duì)象之間的關(guān)系,但這種不規(guī)則結(jié)構(gòu)的數(shù)據(jù)難以直接用機(jī)器學(xué)習(xí)模型進(jìn)行處理,必須先通過(guò)圖表示學(xué)習(xí)方法將圖的節(jié)點(diǎn)嵌入到低維向量空間中,并要求節(jié)點(diǎn)的嵌入能夠反映節(jié)點(diǎn)的鄰域信息。
圖1 推薦系統(tǒng)對(duì)象的兩種表示
為了充分利用高維稀疏向量表示法和圖結(jié)構(gòu)表示法各自的優(yōu)勢(shì),提升推薦算法的性能,我們提出一種結(jié)合圖卷積和特征交叉的方法,稱為圖卷積交 叉 網(wǎng) 絡(luò)(Graph Convolutional Cross Networks,GraphCross),其可以在兩種表示方法間靈活轉(zhuǎn)換。
推薦系統(tǒng)輸入特征高維且稀疏的特點(diǎn)在引言中已有所介紹,此時(shí)特征交叉(feature cross)就對(duì)用戶興趣的推斷起到了十分重要的作用,例如用戶喜歡品牌A的服裝,當(dāng)前季節(jié)為冬季,那么二階特征交叉xA·xwinter=1意味著用戶可能對(duì)品牌A的冬裝感興趣。除了二階特征交叉,也存在高階特征交叉。通??筛鶕?jù)場(chǎng)景和專家經(jīng)驗(yàn),手工設(shè)計(jì)特征交叉交給對(duì)率回歸(Logistic Regression,LR)[1]這樣的模型學(xué)習(xí),此方法簡(jiǎn)單,但需要手工設(shè)計(jì)特征交叉,且設(shè)計(jì)未必是最優(yōu)的。Rendel等[4]提出的因子分解機(jī)(Factorization Machine,F(xiàn)M)分解了二階多項(xiàng)式回歸中二階特征交叉項(xiàng)的系數(shù),即為每維特征學(xué)習(xí)一個(gè)低維嵌入,然后用兩兩特征嵌入的內(nèi)積來(lái)衡量?jī)商卣鞯慕徊骊P(guān)系,可自動(dòng)捕捉特征的二階交叉,并能發(fā)現(xiàn)訓(xùn)練樣本中從未同時(shí)出現(xiàn)的兩特征的交叉關(guān)系。隨后,涌現(xiàn)了很多對(duì)FM的改進(jìn),例如使用凸目標(biāo)函數(shù)來(lái)達(dá)到全局最優(yōu)解的CFM[5]、考慮特征域之間關(guān)系的FFM[6]等,但FM及其改進(jìn)方法只能捕捉二階特征交叉。深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network,DNN)可用于構(gòu)建高階特征交叉:Wide&Deep[7]結(jié)合了由LR組成的“寬”的部分和由DNN組成的“深”的部分,前者可以接受手工設(shè)計(jì)的特征交叉的輸入,記憶專家認(rèn)為對(duì)于當(dāng)前場(chǎng)景有意義的特征交叉,而后者通過(guò)多隱層前饋網(wǎng)絡(luò)隱式地構(gòu)建高階特征交叉,提供了學(xué)習(xí)新特征交叉的泛化性能;DeepFM[8]將Wide&Deep中的LR替換為FM模型,其嵌入層與DNN部分共享,避免了手工設(shè)計(jì)低階特征交叉;xDeepFM[9]顯式地利用特征嵌入進(jìn)行高階特征交叉。但上述特征交叉模型無(wú)一不孤立地對(duì)待樣本,忽視了推薦系統(tǒng)中對(duì)象之間的關(guān)系,導(dǎo)致了信息孤島問(wèn)題。
為了利用圖結(jié)構(gòu),圖表示學(xué)習(xí)受到人們的關(guān)注。早期的圖嵌入方法主要包括基于流形學(xué)習(xí)的同態(tài)映射[10]和局部線性嵌入[11]。近年來(lái),Deep-Walk[12]和node2vec[13]通過(guò)隨機(jī)游走生成圖節(jié)點(diǎn)的序列,進(jìn)而用自然語(yǔ)言處理中的skip-gram方法[14]生成節(jié)點(diǎn)的低維嵌入,另外一些工作[15~17]則將用于規(guī)則網(wǎng)格(如時(shí)間序列、圖像等)的卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neutal Network,CNN)推廣到不規(guī)則的圖上,來(lái)學(xué)習(xí)節(jié)點(diǎn)的表示。目前已有一些工作將圖表示學(xué)習(xí)應(yīng)用于推薦系統(tǒng)[18~19],但它們又忽視了構(gòu)建特征交叉的重要性。
本文提出的GraphCross模型分為圖卷積網(wǎng)絡(luò)和特征交叉兩部分。圖卷積部分通過(guò)構(gòu)建異構(gòu)圖、進(jìn)行圖卷積運(yùn)算,使得生成的節(jié)點(diǎn)嵌入聚合了其鄰域信息,解決了樣本被孤立對(duì)待的問(wèn)題;特征交叉部分利用圖卷積層生成的圖嵌入構(gòu)建特征交叉。下面將按順序分別介紹這兩部分。
模型第一部分采用圖結(jié)構(gòu)表示法,將推薦系統(tǒng)中的對(duì)象及其關(guān)系視為一個(gè)無(wú)向異構(gòu)圖G={V,?},其鄰接矩陣為A,元素aij是節(jié)點(diǎn)表示的對(duì)象i和對(duì)象j之間的連接權(quán)重:若有邊相連則aij=1,否則取0。圖的拉普拉斯矩陣L=D-A,其中度矩陣D為對(duì)角矩陣,其第i個(gè)元素稱為節(jié)點(diǎn)i的度。
圖的空域不規(guī)則,很難定義滑動(dòng)卷積濾波器,因此,首先對(duì)拉普拉斯矩陣L進(jìn)行特征分解得到圖的譜域,進(jìn)而由譜域上的乘積等價(jià)于空域上的卷積這一信號(hào)處理領(lǐng)域的經(jīng)典結(jié)論[20],定義圖的卷積。這樣,只需將譜域上的濾波器視為可學(xué)習(xí)參數(shù),就得到了可訓(xùn)練的圖卷積網(wǎng)絡(luò)。Defferrard等[15]基于譜域推導(dǎo)的圖卷積網(wǎng)絡(luò)通過(guò)L的0到K次冪與節(jié)點(diǎn)表示向量的乘積,使每個(gè)節(jié)點(diǎn)都聚集了其K階鄰域節(jié)點(diǎn)的信息,這與傳統(tǒng)CNN的局部性一致。Kipf等[16]對(duì)上述譜域圖卷積網(wǎng)絡(luò)進(jìn)行了簡(jiǎn)化,指出通過(guò)K層一階圖卷積層的疊加,就可達(dá)到聚集K階鄰域節(jié)點(diǎn)信息的目的,假設(shè)第k-1層的輸出為Ck-1個(gè)通道的節(jié)點(diǎn)表示矩陣的第i行表示第k-1層圖卷積輸出的節(jié)點(diǎn)i的表示,則第k層一階圖卷積為
對(duì)上述一階圖卷積層進(jìn)一步簡(jiǎn)化,去除特征變換和非線性激活函數(shù)[21],稱為簡(jiǎn)化的圖卷積網(wǎng)絡(luò)(Simplified Graph Convolution,SGC)。
或者寫成對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行運(yùn)算的形式:
其中Ni表示節(jié)點(diǎn)i的鄰域。實(shí)驗(yàn)驗(yàn)證去除這些冗余的運(yùn)算后,SGC仍然擁有較好的性能,且計(jì)算復(fù)雜度更低。SGC是一個(gè)完全線性的模型,可證明其等價(jià)于一個(gè)固定的低通濾波器。
出于SGC的上述優(yōu)點(diǎn),GraphCross使用SGC圖卷積層。需要注意的是,這里用戶、物品、屬性等圖的節(jié)點(diǎn)并不帶有稠密數(shù)值特征,為了將節(jié)點(diǎn)完全區(qū)分開來(lái),設(shè)定每個(gè)節(jié)點(diǎn)的特征為||V維標(biāo)準(zhǔn)單位向量,那么節(jié)點(diǎn)的初始表示矩陣H(0)=I為||V階單位陣,通過(guò)K層SGC后,再通過(guò)線性變換層進(jìn)行降維,即:
其中W∈R|V|×d為線性變換層的參數(shù),最終將節(jié)點(diǎn)嵌入到d維(d<<|V|)空間中。
通過(guò)式的推導(dǎo)可以發(fā)現(xiàn),將節(jié)點(diǎn)用高維單位向量表示、經(jīng)過(guò)圖卷積網(wǎng)絡(luò)后再進(jìn)行降維,實(shí)際上等價(jià)于直接為每個(gè)節(jié)點(diǎn)初始化一個(gè)隨機(jī)低維嵌入,作為節(jié)點(diǎn)的初始表示,再進(jìn)行圖卷積得到最終的節(jié)點(diǎn)嵌入,而前者計(jì)算復(fù)雜度為O((K-1)|V|3+|V|2d),后者為O(K|V|2d),因此采用第二種方式。那么,W則成為節(jié)點(diǎn)的初始矩陣表示,即H(0)=W。
通過(guò)SGC將鄰域節(jié)點(diǎn)信息聚合之后,將每一層SGC輸出的節(jié)點(diǎn)表示向量拼接起來(lái),從而保留不同階鄰域節(jié)點(diǎn)的信息,得到節(jié)點(diǎn)i最終的圖嵌入向量為
模型第二部分采用高維稀疏向量表示法作為輸入特征x∈R|V|,同時(shí)以圖卷積部分得到的節(jié)點(diǎn)嵌入式作為特征的嵌入,進(jìn)而用兩特征的圖嵌入向量的內(nèi)積作為二階特征交叉項(xiàng)的系數(shù):
實(shí)質(zhì)上就是一個(gè)FM模型,這里我們只構(gòu)建了二階特征交叉,也可以進(jìn)行高階特征交叉。
通過(guò)兩部分端到端聯(lián)合訓(xùn)練,可充分利用圖結(jié)構(gòu)和特征交叉各自的優(yōu)勢(shì)。圖卷積解決了樣本孤立問(wèn)題,生成更優(yōu)的特征嵌入,進(jìn)行更準(zhǔn)確的特征交叉;而特征交叉部分在訓(xùn)練時(shí)反向傳播回圖卷積層的監(jiān)督信息可以幫助訓(xùn)練節(jié)點(diǎn)的初始表示矩陣W,使其適合于特定的推薦任務(wù)。
算法1 GraphCross模型訓(xùn)練過(guò)程
輸入訓(xùn)練數(shù)據(jù)集合D={(u,i)}、用戶資料、物品屬性
輸出求解得到的模型參數(shù)Θ
1)根據(jù)D、用戶資料、物品屬性構(gòu)建異構(gòu)圖G={V,?}
2)隨機(jī)初始化圖的嵌入表示矩陣H(0)=W
3)for epoch in 1,2,…,n:
4)for mini-batch of(u,i)in D:
5)for k in 1,2,…,K:
7)Z=concat(H(0),H(1),…,H(K))
8)從D負(fù)采樣物品負(fù)樣本j
9)根據(jù)式分別計(jì)算正負(fù)樣本排序得分yui,yuj
10)根據(jù)式計(jì)算損失
11)反向傳播求梯度并使用Adam進(jìn)行參數(shù)更新
本文以top-K推薦作為具體場(chǎng)景,采用貝葉斯個(gè)性化排序作為損失函數(shù)[22],即目標(biāo)函數(shù)為
其中三元組(u,i,j)中,u,i分別為用戶及其訪問(wèn)過(guò)的物品,j是隨機(jī)采樣的負(fù)樣本(本文實(shí)驗(yàn)中每輪訓(xùn)練為每個(gè)正樣本采樣3個(gè)負(fù)樣本);Θ={W,wb,w0,…,wp}為可訓(xùn)練參數(shù)的集合。模型使用Adam算法[23]進(jìn)行優(yōu)化,詳細(xì)訓(xùn)練流程見算法1。
事實(shí)上,可將GraphCross推廣為廣義的圖表示學(xué)習(xí)-特征交叉推薦算法框架,將推薦系統(tǒng)中的高維稀疏特征轉(zhuǎn)換為對(duì)象的異構(gòu)圖,利用圖表示學(xué)習(xí)打破樣本的孤立狀態(tài),從而獲得更優(yōu)的特征嵌入以進(jìn)行精準(zhǔn)的特征交叉。兩部分均可依據(jù)實(shí)際場(chǎng)景進(jìn)行調(diào)整。例如,當(dāng)節(jié)點(diǎn)數(shù)量龐大、無(wú)法進(jìn)行超大規(guī)模鄰接矩陣乘法時(shí),可使用隨機(jī)游走為每個(gè)節(jié)點(diǎn)生成固定大小的鄰域,然后以分布式的方式進(jìn)行圖卷積[16]。又如,將特征交叉部分替換為DNN、壓縮交互網(wǎng)絡(luò)[9]等,在數(shù)據(jù)量較大時(shí)應(yīng)能取得更好的效果。根據(jù)推薦任務(wù)的不同,也可更換不同的損失函數(shù)。
我們?cè)贕oogleLocal和MovieLens-100k數(shù)據(jù)集上進(jìn)行了不同模型的對(duì)比實(shí)驗(yàn):1)GoogleLocal[24]包含美國(guó)各洲用戶在本地商鋪的消費(fèi)歷史,以及商鋪的經(jīng)營(yíng)類型和地點(diǎn)信息,我們使用其中New York、Texas、California共3個(gè)子集;2)MovieLens-100k是檢驗(yàn)推薦算法的標(biāo)準(zhǔn)數(shù)據(jù)集,包含用戶對(duì)電影的評(píng)分,以及用戶年齡、性別、職業(yè)等資料,為了符合本文top-K推薦的目標(biāo),我們只利用用戶觀看電影的信息,而忽略評(píng)分。數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)信息見表1,表格中的物品泛指電影或商鋪。
表1 數(shù)據(jù)集的統(tǒng)計(jì)信息
對(duì)于所有數(shù)據(jù)集,我們將其劃分成訓(xùn)練集、驗(yàn)證集和測(cè)試集,在圖卷積部分,用戶-物品二分圖僅使用訓(xùn)練集中用戶-物品的交互數(shù)據(jù)構(gòu)建,此外還包括用戶與用戶資料的連接,以及物品與物品屬性的連接。在訓(xùn)練集上進(jìn)行模型訓(xùn)練;根據(jù)訓(xùn)練好的模型在驗(yàn)證集上的表現(xiàn)選擇最優(yōu)的學(xué)習(xí)率和正則化項(xiàng)系數(shù);最后報(bào)告在測(cè)試集上的推薦準(zhǔn)確度指標(biāo):AUC、命中率(HR)和歸一化折損累計(jì)增益(NDCG)。實(shí) 驗(yàn) 代 碼 參 見https://github.com/heygrain/graphcross。
SGC和FM是GraphCross的兩個(gè)組成部分,我們嘗試使用了不同層數(shù)SGC的圖卷積網(wǎng)絡(luò),將僅使用一層SGC的模型架構(gòu)記為SGC-FM,使用兩層SGC的模型架構(gòu)記為SGC*2-FM,依此類推。當(dāng)不使用圖卷積網(wǎng)絡(luò)時(shí),GraphCross退化為FM。我們與FM模型,以及使用了Kipf等[16]提出的GCN圖卷積層的GraphCross模型的變體進(jìn)行了模型性能對(duì)比,測(cè)試集上的AUC評(píng)價(jià)指標(biāo)見表2,HR@5和HR@10指標(biāo)見表3,NDCG@5和NDCG@10指標(biāo)見表4。
表2 測(cè)試集上的AUC指標(biāo)
表3 測(cè)試集上的HR指標(biāo)
表4 測(cè)試集上的NDCG指標(biāo)
實(shí)驗(yàn)結(jié)果顯示,GraphCross在三種指標(biāo)上都超越了原始的FM模型,驗(yàn)證了利用圖結(jié)構(gòu)可以解決樣本孤立問(wèn)題、提供更優(yōu)的特征嵌入、提升推薦系統(tǒng)性能。與此同時(shí),通過(guò)對(duì)比使用不同層數(shù)SGC的GraphCross模型,可以發(fā)現(xiàn),當(dāng)圖卷積層數(shù)增加時(shí),模型性能先呈上升趨勢(shì),隨后趨于平穩(wěn)而又略有下降,其原因是圖卷積網(wǎng)絡(luò)過(guò)深時(shí),節(jié)點(diǎn)聚合了離自身路徑較遠(yuǎn)、相關(guān)性較弱的其他節(jié)點(diǎn)的信息,給特征交叉帶來(lái)了干擾和噪聲,因此,圖卷積網(wǎng)絡(luò)也并非越深越好,對(duì)于本文所使用的數(shù)據(jù)集,2~3層圖卷積層較為合適。
通過(guò)將SGC置換成Kipf等[16]提出的帶有特征變換和非線性激活單元的GCN,可得到GraphCross的一個(gè)變體,但GCN在此場(chǎng)景下表現(xiàn)較差,其原因可能是節(jié)點(diǎn)初始表示矩陣經(jīng)多次特征變換和非線性激活函數(shù)后不再適用于特征交叉。
嵌入維數(shù)是GraphCross的重要超參數(shù),為了分析其對(duì)模型性能的影響,圖2繪制了FM和兩種架構(gòu)的GraphCross對(duì)嵌入維數(shù)的敏感性,即HR和NDCG隨嵌入維數(shù)增大的變化曲線??梢园l(fā)現(xiàn),隨嵌入維數(shù)增加,圖卷積網(wǎng)絡(luò)的表示能力逐漸增強(qiáng),模型性能因而得到改善,但當(dāng)嵌入維數(shù)足夠大時(shí),再增加嵌入維數(shù)帶來(lái)的性能提升有限。此外,幾乎在各個(gè)嵌入維數(shù)上,GraphCross的表現(xiàn)均優(yōu)于FM。使用兩層和三層SGC圖卷積層的GraphCross模型性能差異并不大。
圖2 驗(yàn)證集上的指標(biāo)隨嵌入維數(shù)的變化
為了驗(yàn)證利用圖結(jié)構(gòu)可以解決樣本孤立問(wèn)題、提高冷門物品的推薦準(zhǔn)確度,將物品根據(jù)其流行程度(即歷史被訪問(wèn)次數(shù))分組,然后報(bào)告GraphCross(SGC*2-FM)和FM在不同流行度物品上的AUC,實(shí)驗(yàn)結(jié)果如圖3中的折線圖所示,同時(shí)柱狀圖也展示了物品流行度的冪律分布??梢园l(fā)現(xiàn),在不同流行度的物品分組上,GraphCross的表現(xiàn)均超越FM,這是因?yàn)镚raphCross利用了用戶、物品和其他信息組成的異構(gòu)圖,通過(guò)圖卷積,冷門物品也可以利用其鄰域節(jié)點(diǎn)信息生成較好的特征嵌入。
圖3 物品流行度的冪律分布及不同流行度物品組AUC指標(biāo)
本文介紹了推薦系統(tǒng)中對(duì)象的高維稀疏向量表示法和圖結(jié)構(gòu)表示法各自的優(yōu)缺點(diǎn),提出結(jié)合圖卷積網(wǎng)絡(luò)和特征交叉的GraphCross模型,進(jìn)而將GraphCross推廣為一個(gè)圖表示學(xué)習(xí)-特征交叉的推薦算法框架,用圖結(jié)構(gòu)解決樣本孤立問(wèn)題、幫助生成更好的特征嵌入,從而更有效地進(jìn)行特征交叉。實(shí)驗(yàn)驗(yàn)證,相比孤立對(duì)待每個(gè)樣本的FM,GraphCross可以顯式地利用不同訓(xùn)練樣本中對(duì)象之間的關(guān)聯(lián)性,提高推薦系統(tǒng)的準(zhǔn)確度,尤其是對(duì)于冷門物品的推薦。