周林娥，游進(jìn)國(guó)

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院,昆明 650500)

1 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展，大規(guī)模數(shù)據(jù)的出現(xiàn)，使得用戶需花費(fèi)太多的時(shí)間和精力去選擇自己需要的信息.基于此，推薦系統(tǒng)作為一種“信息推送”的重要方法進(jìn)入人們的視野并廣泛應(yīng)用于各種電商及音樂平臺(tái).然而，用戶的需求是不斷變化的且推薦的準(zhǔn)確率仍需提升，信息過載問題依然存在.首先，在傳統(tǒng)推薦系統(tǒng)中，大多數(shù)用戶通常只是消費(fèi)很少的項(xiàng)目且一些用戶可能不愿意對(duì)消費(fèi)的商品評(píng)價(jià)，使得數(shù)據(jù)稀疏問題更加的突出，其次，由于受利益的驅(qū)使，買家可能會(huì)對(duì)商品進(jìn)行不真實(shí)的打分，比如購(gòu)買商品時(shí)賣家可能會(huì)用一些紅包來獲得買家的好評(píng)等等.因此，我們需要借助其他信息為用戶提供更加準(zhǔn)確的推薦，由于社交網(wǎng)絡(luò)的發(fā)展和各種社交平臺(tái)的出現(xiàn)，可以利用觀察到的社交信息來緩解傳統(tǒng)推薦系統(tǒng)的數(shù)據(jù)稀疏問題，許多基本方法[1,2]融合了社交關(guān)系提高了推薦的準(zhǔn)確性，顯示了社交信息納入推薦系統(tǒng)非常重要.為了提高推薦表現(xiàn)最近的工作[3,4]把直接觀察到的社交信息融入到矩陣分解(MF)和貝葉斯個(gè)性化排名(BPR)框架中.目前基于社交網(wǎng)絡(luò)的推薦仍然存在一些問題：由于垃圾郵件的存在及社交關(guān)系的復(fù)雜性，使得社交關(guān)系帶有噪音，現(xiàn)實(shí)世界中顯式的社會(huì)關(guān)系非常稀疏.另外，社交網(wǎng)絡(luò)過大需占據(jù)巨大的存儲(chǔ)空間.因而，直接使用原圖推薦存在一定的局限性.

近來，網(wǎng)絡(luò)表示學(xué)習(xí)的出現(xiàn)使得推薦有了進(jìn)一步的發(fā)展，一種利用網(wǎng)絡(luò)表示學(xué)習(xí)進(jìn)行個(gè)性化商品推薦的方法PGE[5]，通過分別獲取商品和用戶的低維向量表示并計(jì)算他們的相似度主要解決時(shí)間因素對(duì)用戶購(gòu)物偏好的影響.另外還有一些方法，使用帶有重啟模型的廣義隨機(jī)游走來建模用戶，并基于貝葉斯個(gè)性化排名的學(xué)習(xí)方法了解網(wǎng)絡(luò)中鏈接的權(quán)重從而進(jìn)行推薦.盡管基于網(wǎng)絡(luò)表示學(xué)習(xí)的方法已經(jīng)有一定的改善，但直接使用其來進(jìn)行推薦存在兩個(gè)不足.首先，計(jì)算復(fù)雜度高并且占據(jù)太大的存儲(chǔ)空間.另外，在網(wǎng)絡(luò)上的一些鏈接可能不能傳遞有意義的語(yǔ)義信息，直接使用表示學(xué)習(xí)方法進(jìn)行推薦表現(xiàn)欠佳.其次，這些方法涉及數(shù)據(jù)矩陣的特征分解這對(duì)于大型的現(xiàn)實(shí)世界網(wǎng)絡(luò)而言效率不高.

考慮到網(wǎng)絡(luò)嵌入方法本身也能抵抗稀疏和嘈雜的數(shù)據(jù).具體而言，我們可以考慮節(jié)點(diǎn)本身及周圍節(jié)點(diǎn)之間的特性(即鄰近性)；另外，可以基于網(wǎng)絡(luò)中節(jié)點(diǎn)的結(jié)構(gòu)特性(即結(jié)構(gòu)等效性)[6,7].因此，必須允許節(jié)點(diǎn)表示遵循兩條原則：學(xué)習(xí)嵌入節(jié)點(diǎn)的表示保證來自同一網(wǎng)絡(luò)的緊密聯(lián)系即鄰近性，以及學(xué)習(xí)表示相似角色的節(jié)點(diǎn)具有相似嵌入的表示即同構(gòu)性.但大多數(shù)存在的網(wǎng)絡(luò)嵌入方法只側(cè)重于網(wǎng)絡(luò)的一部分信息且未考慮存儲(chǔ)及可拓展性問題，考慮如何把這些信息更合理有效的整合和利用到推薦系統(tǒng)中.因此，本文提出了一種基于聚集圖表示學(xué)習(xí)的推薦方法SGE-BPR(Summarized Graph Embedding Bayesian Personalized Ranking).考慮網(wǎng)絡(luò)本身所反映的特征和豐富的語(yǔ)義信息，該方法首先考慮結(jié)構(gòu)一致性利用圖聚集算法提取聚集圖數(shù)據(jù)，更好的保存原圖信息的同時(shí)把相似性高的節(jié)點(diǎn)聚合到一起，隨后使用隨機(jī)游走策略生成有偏差的節(jié)點(diǎn)序列.通過網(wǎng)絡(luò)嵌入計(jì)算相似性并捕獲用戶偏好信息且融合到貝葉斯個(gè)性化排序模型，方法一定程度上減輕了數(shù)據(jù)稀疏性并緩解了噪音問題，有效彌補(bǔ)了直接使用原圖進(jìn)行推薦的不足.

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

1)首先，利用圖聚集技術(shù)把結(jié)構(gòu)相似的節(jié)點(diǎn)聚合到一起提取聚集圖數(shù)據(jù)，然后進(jìn)行有偏的隨機(jī)游走.并從圖聚集和圖嵌入、社會(huì)化推薦及基于表示學(xué)習(xí)的推薦等方面進(jìn)行展開和分析.

2)利用skip-gram學(xué)習(xí)向量的表示并計(jì)算用戶的相似性，結(jié)合貝葉斯個(gè)性化排序模型提出一個(gè)新穎的圖嵌入推薦模型SGE-BPR來提高推薦性能.

3)使用四個(gè)真實(shí)世界的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證方法的有效性.

2 相關(guān)工作

本文回顧相關(guān)工作的研究，并從圖聚集、圖嵌入和社會(huì)化推薦及基于表示學(xué)習(xí)的推薦進(jìn)行討論.

2.1 圖聚集和圖嵌入

隨著數(shù)據(jù)量的增大，圖挖掘逐漸成為熱門的研究領(lǐng)域，當(dāng)前對(duì)圖聚集的研究工作主要有：文獻(xiàn)[8]引入信息增益考慮分組間和分組內(nèi)的結(jié)構(gòu)對(duì)集聚圖的影響并提出了兩種聚集圖構(gòu)建算法，要尋找高質(zhì)量的聚集圖需要計(jì)算重構(gòu)誤差使得原圖的鄰接矩陣與聚集圖的期望鄰接矩陣盡可能的相似，從而來衡量原圖與聚集圖之間的誤差.文獻(xiàn)[9]提出了圖結(jié)構(gòu)查詢并采用最小描述長(zhǎng)度(MDL)表示圖壓縮問題，該方法保證了查詢的準(zhǔn)確性.文獻(xiàn)[10]通過研究通常的聚集類型，提出利用多項(xiàng)式時(shí)間近似算法來計(jì)算給定大小的最可能的聚集方式并生成使重構(gòu)誤差最小的聚集圖.

最初提出網(wǎng)絡(luò)表示學(xué)習(xí)是為了學(xué)習(xí)低維潛在因子來保留大多數(shù)網(wǎng)絡(luò)結(jié)構(gòu).然而，這些方法計(jì)算復(fù)雜、效率低而不適用于當(dāng)前的大型信息網(wǎng)絡(luò).文獻(xiàn)[11]總結(jié)了近來出現(xiàn)的網(wǎng)絡(luò)表示學(xué)習(xí)方法并驗(yàn)證了這些方法，并對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)表示學(xué)習(xí)進(jìn)行了展望.隨著skip-gram[12]算法的出現(xiàn)其顯示了在建模句子方面的優(yōu)勢(shì).受此想法的啟發(fā)，DeepWalk[13]被用來從網(wǎng)絡(luò)中學(xué)習(xí)一個(gè)語(yǔ)言模型，使用隨機(jī)游走從網(wǎng)絡(luò)中產(chǎn)生節(jié)點(diǎn)序列，然后把它放到skip-gram模型中最終輸出表示.緊密的節(jié)點(diǎn)傾向于有相似的上下文，因此嵌入后具有更相近的節(jié)點(diǎn)序列.LINE[14]在圖上定義了一階相似度和二階相似度，一階相似度用來保留兩個(gè)節(jié)點(diǎn)之間的直接聯(lián)系的緊密程度，二階相似度用來保留兩個(gè)節(jié)點(diǎn)鄰居的相似程度.node2vec[15]是另一種隨機(jī)游走的代表性方法，它拓展了DeepWalk并同時(shí)兼顧深度優(yōu)先和廣度優(yōu)先的搜索優(yōu)勢(shì)從而獲得更好的表示效果.GraRep[16]模型從矩陣分解的角度考慮了更高階的上下文信息，捕獲了圖的全局結(jié)構(gòu).對(duì)于基于節(jié)點(diǎn)和邊的預(yù)測(cè)任務(wù)以及現(xiàn)有圖的深度網(wǎng)絡(luò)體系結(jié)構(gòu)的有監(jiān)督的特征學(xué)習(xí)的最新成果[17-19].這些方法直接最小化了損失函數(shù)使用多層非線性的下游預(yù)測(cè)任務(wù)轉(zhuǎn)換可產(chǎn)生高精度，但訓(xùn)練時(shí)間長(zhǎng)，可擴(kuò)展性差.

2.2 社會(huì)化推薦

融入社會(huì)關(guān)系的協(xié)同過濾算法稱為社會(huì)化推薦算法.近年來，國(guó)內(nèi)外學(xué)者針對(duì)社交關(guān)系對(duì)推薦的影響展開深入的研究.在早期，研究者們主要考慮顯式的社會(huì)關(guān)系來促進(jìn)推薦.這些工作如下：文獻(xiàn)[20]提出RSTE一種新穎的概率因子分析框架將用戶的偏好和他們信任的朋友的興趣融合在一起.文獻(xiàn)[21]提出一種融合用戶隱含偏好的推薦算法，用權(quán)重矩陣來衡量用戶相似度和信任度.文獻(xiàn)[3]中提出基于MF的信任，通過考慮隱含鄰居的影響獲取用戶的信任和用戶的評(píng)級(jí).SBPR[4]算法在BPR模型上融入了社交關(guān)系從而得到了更好的推薦效果.文獻(xiàn)[22-25]提出BPR及相關(guān)的解決項(xiàng)目排名問題的方法.文獻(xiàn)[26]基于FM(因子分解機(jī))提出一種通過相似度和信任值來估計(jì)社會(huì)影響傳播并考慮了人群計(jì)算來提高推薦的準(zhǔn)確性.除上述研究外，Taheri等人[27]提出Hell-Trust SVD方法提取隱含社會(huì)關(guān)系和評(píng)級(jí)并結(jié)合到活躍用戶的項(xiàng)目預(yù)測(cè)中.

2.3 基于表示學(xué)習(xí)的推薦

隨著表示學(xué)習(xí)的發(fā)展，一些利用表示學(xué)習(xí)推薦的方法隨之出現(xiàn)，在生成頂點(diǎn)上下文時(shí)，一種基于網(wǎng)絡(luò)嵌入的社交推薦方法稱為CUNE[25]通過構(gòu)建用戶協(xié)作網(wǎng)絡(luò)識(shí)別可信的語(yǔ)義朋友融入MF和BPR框架用于推薦.文獻(xiàn)[28]基于社交網(wǎng)絡(luò)屬性，提出一個(gè)SAEN模型，對(duì)不同用戶進(jìn)行多樣性和個(gè)性化推薦.文獻(xiàn)[29]基于商品間的互補(bǔ)性和用戶對(duì)商品的忠誠(chéng)度兩個(gè)維度提出triple2vec一種新的表示學(xué)習(xí)，進(jìn)而提出一種考慮忠誠(chéng)度的推薦算法來計(jì)算購(gòu)買偏好.文獻(xiàn)[30]提出了基于圖神經(jīng)網(wǎng)絡(luò)的協(xié)同過濾算法NGCF，將用戶-項(xiàng)目的高階交互編碼進(jìn)嵌入中來提升表示能力進(jìn)而提升整個(gè)推薦效果.文獻(xiàn)[31]提出了一種基于生成對(duì)抗訓(xùn)練框架的社會(huì)化推薦模型，對(duì)模型進(jìn)行端到端的訓(xùn)練，取得了很好的效果.文獻(xiàn)[32]基于超圖網(wǎng)絡(luò)模型構(gòu)建了一種通過節(jié)點(diǎn)特征相似度，不斷的迭代和挖掘關(guān)系屬性的圖網(wǎng)絡(luò)進(jìn)化算法.文獻(xiàn)[33]提出一種SLATEQ的強(qiáng)化學(xué)習(xí)算法，將長(zhǎng)期收益加入排序多目標(biāo)中進(jìn)行建模優(yōu)化，優(yōu)化了推薦系統(tǒng)中同時(shí)展示給用戶多個(gè)項(xiàng)目情況的長(zhǎng)期收益.文獻(xiàn)[34]提出一種互補(bǔ)性發(fā)現(xiàn)模型通過商品價(jià)格和商品購(gòu)買記錄來發(fā)掘商品間的互補(bǔ)關(guān)系.文獻(xiàn)[5]提出一種利用網(wǎng)絡(luò)表示學(xué)習(xí)進(jìn)行個(gè)性化商品推薦的方法PGE，該方法構(gòu)建商品網(wǎng)絡(luò)并通過表示學(xué)習(xí)獲取低維向量表示且通過歷史記錄及時(shí)序性線性計(jì)算出動(dòng)態(tài)的用戶偏好從而對(duì)相似度進(jìn)行評(píng)估.

上述工作的核心思想是基于社交關(guān)系進(jìn)行推薦.然而，大數(shù)據(jù)時(shí)代，空間效率及可拓展性也是必須考慮的重要因素.考慮現(xiàn)有研究的不足，本文的工作主要是采用基于信息增益的圖聚集算法[8](GSum_EG)，獲取聚集圖數(shù)據(jù).然后，借鑒node2vec的思想在聚集圖上隨機(jī)游走后學(xué)習(xí)學(xué)習(xí)有效的圖結(jié)構(gòu)生成節(jié)點(diǎn)向量，隨后通過聚集圖映射表進(jìn)行節(jié)點(diǎn)向量的還原并尋找相似用戶.最后，將信息融合到貝葉斯排序模型進(jìn)行項(xiàng)目推薦.

3 一種結(jié)合聚集圖嵌入的社會(huì)化推薦算法

3.1 問題定義

為了更好的闡述，本文先對(duì)相關(guān)概念進(jìn)行描述并形式化聚集圖的表示學(xué)習(xí)問題，具體如下所示：

定義1.聚集圖[8]：一個(gè)聚集圖S=(Vs,Es,P)是輸入圖G=(V，E)的壓縮表達(dá)，其中Vs是V中k是中個(gè)組的一個(gè)劃分，Es是相應(yīng)的超邊的集合，P與每條邊相關(guān)聯(lián)，表示兩個(gè)超點(diǎn)之間或者一個(gè)超點(diǎn)自身的連接概率.聚集圖S的正式定義如下所示：

ES={(Vi,Vj)|?u∈Vi,v∈Vj,(u,v)∈E}；

p:ES→R=[0,1].

定義2.聚集圖的表示學(xué)習(xí)[11]：給定聚集圖G=(V，E)，其表示學(xué)習(xí)是：G對(duì)應(yīng)的頂點(diǎn)特征X是一個(gè)高度稀疏的矩陣，其維數(shù)通常為|V|×m(m(是頂點(diǎn)屬性的特征空間大小)，對(duì)每個(gè)頂點(diǎn)v∈V,低維向量表示學(xué)習(xí)rv∈Rk,k實(shí)質(zhì)上遠(yuǎn)小于|V|,rv表示為一個(gè)稠密的實(shí)數(shù)向量表示.

3.2 總體框架

圖1為本文提出的總體框架.如圖1(a)在社交網(wǎng)絡(luò)中，頂點(diǎn)表示節(jié)點(diǎn)，邊表示節(jié)點(diǎn)之間的社交關(guān)系.圖1(b)為圖1(a)的聚集圖，其中每個(gè)頂點(diǎn)代表一個(gè)超點(diǎn)，邊代表超邊，邊上的值代表權(quán)重，超點(diǎn)1對(duì)應(yīng)的節(jié)點(diǎn)集合為{x,d,e},超點(diǎn)2對(duì)應(yīng)的節(jié)點(diǎn)集合為{a,b,c},超點(diǎn)3對(duì)應(yīng)的節(jié)點(diǎn)集合為{g,f},超點(diǎn)4對(duì)應(yīng)的節(jié)點(diǎn)集合為{y,i,j},超點(diǎn)5對(duì)應(yīng)的節(jié)點(diǎn)集合為{h}.圖1(c)為在聚集圖上產(chǎn)生的隨機(jī)游走節(jié)點(diǎn)序列.圖1(d)輸入為聚集圖的節(jié)點(diǎn)，當(dāng)預(yù)測(cè)節(jié)點(diǎn)1時(shí)，使用skip-gram嵌入，輸出為其他節(jié)點(diǎn)出現(xiàn)在中心節(jié)點(diǎn)1周圍的概率.圖1(e)計(jì)算節(jié)點(diǎn)的表示向量的相似度將其輸入到貝葉斯排序模型，最終輸出推薦列表.

3.3 聚集圖及隨機(jī)游走

在社交網(wǎng)絡(luò)中，采用基于信息增益的圖聚集算法[8](GSum_EG)保留原圖關(guān)鍵的結(jié)構(gòu)關(guān)系并去除帶有噪音的數(shù)據(jù)獲取聚集圖，由于信息熵越小包含的原圖信息越多，因此尋找信息增益最大的分組即信息熵最小的分組，依次調(diào)整直至所有節(jié)點(diǎn)調(diào)整完，最終得到聚集圖.

考慮到聚集圖的鄰近性及同構(gòu)性，即聚集圖上距離越近的節(jié)點(diǎn)及結(jié)構(gòu)相近的節(jié)點(diǎn)相似的可能性更大.相連比較緊密的節(jié)點(diǎn)應(yīng)該有相似的嵌入.在圖1中假設(shè)(a)為聚集圖，超點(diǎn)x和超點(diǎn)y屬于同構(gòu)性節(jié)點(diǎn)，超點(diǎn)x和超點(diǎn)d屬于鄰近性節(jié)點(diǎn)，因而采用同時(shí)兼顧兩種特性的方法進(jìn)行有偏的隨機(jī)游走，捕獲相似節(jié)點(diǎn).

設(shè)f(u)是將頂點(diǎn)u映射為嵌入向量的映射函數(shù),對(duì)于圖中頂點(diǎn)u的近鄰頂點(diǎn)集合.通過以下公式計(jì)算近鄰頂點(diǎn)出現(xiàn)的概率：

(1)

為使上述問題得到最優(yōu)化解，進(jìn)行如下兩方面的假設(shè)：條件獨(dú)立性假設(shè)：假設(shè)給定起始頂點(diǎn)下，其近鄰頂點(diǎn)出現(xiàn)的概率與近鄰集合中其余頂點(diǎn)無關(guān).用如下公式表示：

(2)

圖1 SGE-BPR方法說明Fig.1 Illustration of summarized graph embedding bayesian personalized ranking method

特征空間對(duì)稱性假設(shè)：一個(gè)頂點(diǎn)作為起始頂點(diǎn)和作為近鄰頂點(diǎn)的時(shí)候共用同一嵌入向量.(與LINE[13]中的2階相似度，一個(gè)頂點(diǎn)作為起始點(diǎn)和近鄰點(diǎn)的時(shí)候是擁有不同的嵌入向量不一樣)在這個(gè)假設(shè)下，上述條件概率公式可表示為:

(3)

由上述假設(shè)可得最終的目標(biāo)函數(shù)如下：

(4)

其中Zu代表每個(gè)節(jié)點(diǎn)的函數(shù)，表示為：

(5)

為了減少計(jì)算量的同時(shí)更好的保留聚集圖的原始信息并獲得潛在的信息，采用有偏的隨機(jī)游走獲取頂點(diǎn)的近鄰序列.受node2vec[14]啟發(fā)，給定當(dāng)前頂點(diǎn)v，訪問下一個(gè)頂點(diǎn)x的概率為:

(6)

其中πvx是頂點(diǎn)v和頂點(diǎn)x之間未歸一化的轉(zhuǎn)移概率，z是歸一化常數(shù).

引入兩個(gè)超參數(shù)p和q來控制游走的策略，假設(shè)當(dāng)前隨機(jī)游走經(jīng)過邊(t,v)到達(dá)頂點(diǎn)v時(shí),πvx=αpq(t,x).wvx設(shè)，其中wvx是頂點(diǎn)v和x之間的權(quán)值.

(7)

其中dtx為頂點(diǎn)v到x的最短路徑的距離.超參數(shù)p和q對(duì)游走策略均有影響.其中p決定再訪問節(jié)點(diǎn)的可能性，為返回參數(shù).若p值調(diào)高(p>max(q，1))，這樣可以保證在兩步內(nèi)采樣已訪問過的節(jié)點(diǎn)的可能性比較低；若p調(diào)低(p1游走會(huì)選擇離t近的節(jié)點(diǎn)，以此達(dá)到接近廣度優(yōu)先遍歷的效果；q<1游走會(huì)選擇離t較遠(yuǎn)的節(jié)點(diǎn)，達(dá)到類似深度優(yōu)先遍歷的效果.

3.4 聚集圖的表示學(xué)習(xí)

對(duì)于每種類型的游走方案，我們可以獲得基于聚集圖的隨機(jī)游走步行序列，這是一個(gè)旨在學(xué)習(xí)的skip-gram模型通過預(yù)測(cè)節(jié)點(diǎn)上下文的節(jié)點(diǎn)嵌入向量.通常，目標(biāo)是使上下文出現(xiàn)的概率最大化，在給定的中心節(jié)點(diǎn)下Sw0=(w0,w1,….,wM)即：形式上，給定一系列單詞，目標(biāo)函數(shù)是：

(8)

其中b是上下文的窗口大小,p(wt′|wt)定義為Softmax函數(shù).同樣，我們最大化每個(gè)節(jié)點(diǎn)共現(xiàn)的概率隨機(jī)行走Wv固定長(zhǎng)度L：

(9)

其中τ是vt′上下文的窗口大小，即vt′-τ…vt+τ.因此，skip-gram學(xué)習(xí)了一個(gè)嵌入E的特征，其中包含|V|×l個(gè)自由參數(shù)(V是聚集圖上所有節(jié)點(diǎn)的集合和E的每一行表示特定用戶的特征向量大小l.真實(shí)世界網(wǎng)絡(luò)規(guī)模龐大，為了高效的計(jì)算，分層Softmax應(yīng)用于近似p(vt′|E(vt)為了避免在Softmax中歸一化函數(shù)的復(fù)雜性計(jì)算.我們模擬以每個(gè)節(jié)點(diǎn)為根的行走生成語(yǔ)義社會(huì)語(yǔ)料庫(kù)并使用隨機(jī)梯度下降訓(xùn)練.

3.5 項(xiàng)目推薦

表示學(xué)習(xí)后可直接通過計(jì)算相似性進(jìn)行推薦但這種方式效果并不理想，因此考慮把獲得的用戶信息融合到貝葉斯排序模型.結(jié)合實(shí)際，通常為用戶推薦項(xiàng)目是以一個(gè)有序的列表呈現(xiàn)的，用Pu表示用戶消費(fèi)的項(xiàng)目(喜歡或購(gòu)買的項(xiàng)目)，Nu表示沒有消費(fèi)的項(xiàng)目(沒有興趣或沒有訪問過的項(xiàng)目).

受SBPR[4]的啟發(fā)，其充分利用了社交關(guān)系的優(yōu)勢(shì)，并拓展了排序算法BPR[21]，如下：

xua≥xub,xub≥xuc,a∈Pu,b∈SPu,b∈Nu

(10)

其中xu.表示用戶u對(duì)其中一個(gè)項(xiàng)目的偏好.SPu表示對(duì)項(xiàng)目集I至少有一個(gè)確定的朋友，但沒有任何積極的反饋.

根據(jù)上述拓展并結(jié)合模型需要進(jìn)行如下修改，給定Pu，IPu，Nu項(xiàng)目排名如下：

xui≥xuk≥xuj,i∈Pu,k∈IPu,j∈Nu

(11)

其中IPu表示用戶沒有過正反饋但是至少有一個(gè)語(yǔ)義朋友，因此自然可以想到u喜歡k超過j,u更喜歡k.這種假設(shè)可以很好的解釋朋友信任朋友的推薦并且其項(xiàng)目排名高于觀察到的消極項(xiàng)目.每個(gè)用戶的優(yōu)化標(biāo)準(zhǔn)表示如下：

(12)

其中Tu=Pu∪IPu，Hu=IPu∪Nu.如果i∈Pu并且k∈IPu時(shí)，σ(u,i,k)=1,反之σ(u,i,k)=0.以此類推，如果k∈IPu并且j∈Nu時(shí)，σ(u,k,j)=1,反之σ(u,k,j)=0.因此，后驗(yàn)概率如下：

(13)

(14)

本文使用隨機(jī)梯度下降進(jìn)行訓(xùn)練，SGE-BPR使用如下的梯度方程對(duì)每個(gè)觀察到的結(jié)構(gòu)進(jìn)行參數(shù)更新.

(15)

3.6 SGE-BPR算法

算法.SGE-BPR算法

輸入:The summarized graphG=(V,E), walk lengthn,embedding dimensionX, context sizeb, negative samplesM, returnp, in-outq.

輸出：Recommendation list.

/*計(jì)算轉(zhuǎn)移概率并初始化*/

1.π=MW(G,P,q);

2.G′=(V,E,π);

3.Initialize walks to Empty，initialize node embeddingsX;

/*聚集圖上隨機(jī)游走并嵌入*/

4. forl=1 tordo

5. for all nodesu∈V

6. RW=node2vecWalk(G′,u,n);

7. add walk to walks;

8.X=skip-gram(X,RW,b);

/*計(jì)算相似度并進(jìn)行推薦*/

9. for useriinV

10. for userjinV

11. sim=cos(X[i],X[j]);

12. add sim to user similarity list;

13. Integrate sim into BPR model and generate the recommendation list.

如上給出了SGE-BPR算法的主要步驟.其中1-3行表示聚集圖上轉(zhuǎn)移概率的計(jì)算及初始化.第6行表示聚集圖上的隨機(jī)游走，第8行表示skip-gram嵌入，9-12行表示相似度的計(jì)算并加入到相似列表.

通過分析SGE-BPR算法可知，算法的可靠性主要由聚集圖的質(zhì)量來決定，即聚集圖是否能保證原圖信息的完整性和準(zhǔn)確性.下面通過理論分析和實(shí)驗(yàn)來進(jìn)行簡(jiǎn)要的證明.

證明：由聚集圖的相關(guān)研究可知，信息熵可以衡量原圖信息的完整性[8].假設(shè)聚集圖包含k個(gè)超點(diǎn)，當(dāng)k=n(n為原圖的頂點(diǎn)數(shù))時(shí)，信息熵H(Gn)=0；當(dāng)k=1(一個(gè)超點(diǎn))時(shí)，此時(shí)的信息熵最大.綜上信息熵為0≤H(Gk)≤H(G1).進(jìn)一步推論可知，k越大，信息熵越小，原圖信息越完整，而k值可由用戶自己控制，因而輸入圖為聚集圖不影響算法的可靠性.最后通過karate數(shù)據(jù)集的具體例子來驗(yàn)證該算法在原圖和聚集圖的表現(xiàn)，進(jìn)一步說明算法的可靠性.該數(shù)據(jù)集有34個(gè)用戶U={ui|i=1,2,…,34},若k=20其聚集圖包含20個(gè)超點(diǎn)，在嵌入后對(duì)其向量進(jìn)行還原(根據(jù)聚集圖映射表最終得到34個(gè)用戶的向量表示)，這樣處理能降低信息的損失，最后融入到BPR算法中，其結(jié)果如表1所示，從中可以觀察到聚集圖和原圖在推薦的表現(xiàn)方面很相似.綜上所述，該方法是可靠的.

表1 算法可靠性驗(yàn)證Table 1 Algorithm reliability verification

與最初的帶有社會(huì)關(guān)系的個(gè)性化排序模型[23]及其他基于社會(huì)化BPR改進(jìn)的方法相比，SGE-BPR使用圖聚集技術(shù)捕獲了結(jié)構(gòu)相似的節(jié)點(diǎn)并豐富了社交排名的假設(shè)，且考慮了表示學(xué)習(xí)的拓展性及空間存儲(chǔ)等更符合大規(guī)模圖的實(shí)際情況，因而不僅保護(hù)了用戶的信息且獲得較好的推薦效果，另外通過相關(guān)實(shí)驗(yàn)證明其更好的提高了社會(huì)化推薦的表現(xiàn).

4 實(shí)驗(yàn)結(jié)果與分析

在這一部分，我們將進(jìn)行實(shí)驗(yàn)來驗(yàn)證方法的有效性.

4.1 實(shí)驗(yàn)設(shè)計(jì)

根據(jù)第3節(jié)所述設(shè)計(jì)實(shí)現(xiàn)融合聚集圖表示學(xué)習(xí)的推薦方法，并對(duì)數(shù)據(jù)進(jìn)行驗(yàn)證.實(shí)驗(yàn)環(huán)境為PC機(jī)Windows 10系統(tǒng)、Intel Core i5處理器、8GB內(nèi)存，開發(fā)環(huán)境為PyCharm，采用Python 3.6進(jìn)行算法的實(shí)現(xiàn).采用4個(gè)常見的社交推薦數(shù)據(jù)集FilmTrust(1)http://www.librec.net/datasets.html,LastFM(2)https://grouplens.org/datasets/hetrec-2011/,Ciao(3)https://www.librec.net/datasets.html,Epinions(4)http://www.librec.net/datasets.html.對(duì)于每一個(gè)數(shù)據(jù)集本文使用80%作為訓(xùn)練集，10%作為交叉驗(yàn)證集，10%作為測(cè)試集，使用五折交叉驗(yàn)證，對(duì)比平均表現(xiàn).數(shù)據(jù)集如表2所示.

表2 數(shù)據(jù)集Table 2 Datasets

4.2 效果比較

為了證明本文方法的有效性，與顯式的社會(huì)信息相關(guān)的貝葉斯排名模型進(jìn)行比較.基線方法如下：BPR[21]是一種假設(shè)用戶購(gòu)買過的物品的偏好排序優(yōu)于用戶未購(gòu)買過的物品，利用用戶對(duì)物品反饋情況進(jìn)行個(gè)性化排序的方法.SBPR[4]是一種利用顯式的社會(huì)信息拓展BPR模型的方法.CUNE[25]提出利用網(wǎng)絡(luò)嵌入技術(shù)獲得top-k隱性朋友.為了評(píng)估本文模型的性能，本文選擇3種評(píng)價(jià)指標(biāo)：準(zhǔn)確率(Precision)和召回率(Recall)和排序指標(biāo)平均精度均值MAP(Mean average precision)進(jìn)行度量.

圖2 4個(gè)數(shù)據(jù)集上算法效果比較Fig.2 Comparison of algorithm effects on four datasets

參數(shù)設(shè)置：對(duì)于所有的基線方法，基于先前工作的建議及實(shí)驗(yàn)，設(shè)置如下：正則化系數(shù)λX=0.01，潛在特征維數(shù)d=20，對(duì)兩種網(wǎng)絡(luò)嵌入方法，CUNE和SGE-BPR步數(shù)n=20,每一步的長(zhǎng)度l=20，窗口大小b=5,負(fù)樣本數(shù)量M=5.

如圖2所示，不同的推薦方法推薦表現(xiàn)不一樣，從圖中可以觀察到：首先，4個(gè)數(shù)據(jù)集上顯示本文方法優(yōu)于其他基線方法同時(shí)我們對(duì)本文中的方法在原圖(GE-BPR)和聚集圖上的效果做了比較，在聚集圖上的效果優(yōu)于原圖.其次，3種網(wǎng)絡(luò)嵌入方法推薦表現(xiàn)優(yōu)于其他普通的排序方法，可能的原因是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以幫助更好的獲得潛在的社會(huì)關(guān)系通過網(wǎng)絡(luò)嵌入能緩解數(shù)據(jù)稀疏因而提高了在推薦上的表現(xiàn).最后，使用隱式關(guān)系最終的推薦結(jié)果好于直接使用顯式關(guān)系的結(jié)果，我們的方法加強(qiáng)了顯式關(guān)系且降低了計(jì)算復(fù)雜度從而推薦效果好于直接使用隱式或顯式關(guān)系的方法.

為了證明SGE-BPR算法的效率，我們同時(shí)對(duì)比同一算法下原圖和聚集圖的表現(xiàn)，進(jìn)行實(shí)驗(yàn)驗(yàn)證了在3種指標(biāo)下，本文的算法在原圖和聚集圖上進(jìn)行時(shí)間的對(duì)比(見表3).

表3 算法運(yùn)行時(shí)間對(duì)比Table 3 Algorithm running time comparison

從表3中可以看出，聚集圖上的算法效率更高，特別是當(dāng)數(shù)據(jù)量增大的時(shí)候，聚集圖上表現(xiàn)了明顯的優(yōu)勢(shì)，可能的原因是聚集圖上的噪音少于原圖且聚集圖的節(jié)點(diǎn)表示得到的向量更高效.另外有研究表明，基于隨機(jī)游走的采樣策略所占內(nèi)存少于其他方式，比如矩陣分解的方法[16]，一般而言對(duì)于無監(jiān)督的圖嵌入來說，使用skip-gram模型本身也存在一定的優(yōu)勢(shì)且聚集圖是對(duì)原圖的聚集，因而節(jié)省空間.

圖3 4個(gè)數(shù)據(jù)集上維度的影響Fig.3 Effect of dimensions on four datasets

在方法SGE-BPR上我們主要對(duì)比了維度為10，20，40，60，80這5種不同維度下，準(zhǔn)確率(Pre@10)、召回率(Rec@10)和平均精度均值(Map@10)的變化.從圖3左圖我們可以看到剛開始時(shí)小幅度的上升，隨后平穩(wěn)之后小幅度的下降，當(dāng)維度達(dá)到一定閾值時(shí)所反映的信息比較完全，因此呈現(xiàn)穩(wěn)定而后再增加維度不利于信息的獲取.而右圖波動(dòng)幅度較大但變化趨勢(shì)類似，因此綜合而言本文維度值取20是合理且有效的，便于達(dá)到更好的推薦效果.

圖4 4個(gè)數(shù)據(jù)集上負(fù)樣本數(shù)目的影響Fig.4 Effect of negative sample numbers on four datasets

在方法SGE-BPR上我們主要對(duì)比了負(fù)采樣數(shù)為1，2，3，4，5這5種不同負(fù)樣本數(shù)，準(zhǔn)確率(Pre@10)、召回率(Rec@10)和平均精度均值(Map@10)的變化.從圖4中我們可以看到剛開始時(shí)小幅度的上升，隨后平穩(wěn)之后小幅度的下降，當(dāng)負(fù)樣本達(dá)到一定閾值時(shí)所反映的信息比較完全，因此呈現(xiàn)穩(wěn)定而后再增加負(fù)采樣時(shí)不利于信息的獲取.因此本文負(fù)采樣本數(shù)取5是合理且有效的.

5 結(jié) 語(yǔ)

本文主要利用聚集圖上的表示學(xué)習(xí)挖掘潛在的信息從而加強(qiáng)顯式關(guān)系提高推薦，受網(wǎng)絡(luò)嵌入的啟發(fā)，本文設(shè)計(jì)了一種新穎的SGE-BPR項(xiàng)目排名方法，使用聚集圖表示學(xué)習(xí)并融合貝葉斯個(gè)性化排名模型.實(shí)驗(yàn)結(jié)果顯示我們的方法優(yōu)于傳統(tǒng)的基于模型的方法及顯式的社會(huì)推薦模型.

下一步工作將進(jìn)一步考慮時(shí)間因素對(duì)推薦的影響，優(yōu)化聚集圖上隨機(jī)游走方案，將模型拓展并結(jié)合到異構(gòu)圖中進(jìn)行推薦.