劉 峰，王寶亮，鄒榮宇，趙浩淳

（1.天津大學 信息與網(wǎng)絡中心，天津 300072；2.天津大學 電氣自動化與信息工程學院，天津 300072；3.天津大學 國際工程師學院，天津 300072）

0 概述

隨著互聯(lián)網(wǎng)和人工智能等信息技術的快速發(fā)展，信息量呈指數(shù)級的增長，信息過載問題日益突出。為解決這一問題，個性化推薦系統(tǒng)應運而生［1］。個性化推薦系統(tǒng)根據(jù)用戶歷史行為數(shù)據(jù)進行建模分析用戶偏好，進而為其提供個性化的信息推薦，方便用戶獲取自身需求的信息［2-4］。推薦系統(tǒng)在給每位用戶提供有針對性的商品信息推薦服務的同時過濾掉了那些用戶并不感興趣的信息，有效地節(jié)約了人們的信息篩選時間。個性化推薦系統(tǒng)由于在信息推薦方面的優(yōu)秀表現(xiàn)，已成為熱點研究方向。

隨著各類互聯(lián)網(wǎng)業(yè)務的快速發(fā)展，各種輔助信息的獲取越來越容易，而將這些輔助信息應用于推薦算法中，將提升推薦性能，但這也對推薦算法的建模能力提出新的挑戰(zhàn)。基于圖模型的推薦算法是當前的熱點方向，但是不易融合輔助信息，而網(wǎng)絡表示學習（Network Representation Learning，NRL）強大的網(wǎng)絡提取能力與基于圖模型的推薦算法相結合，能提升算法的可擴展性?？傮w而言，網(wǎng)絡表示學習是以稠密、低維的向量形式表示網(wǎng)絡中的各個節(jié)點，并使這些低維向量具有表示和推理能力，從而將這些向量作為輸入應用于節(jié)點分類、鏈接預測和推薦系統(tǒng)中。

基于上述設計思路，研究人員將網(wǎng)絡表示學習技術應用于推薦算法中以提高其建模能力。ZHANG 等［5］利用TransR 提取物品的結構化信息，并融合物品的結構化信息、文本信息與視覺信息進行推薦。BARKAN 等［6］借 鑒Google 提 出的Word2vec方法，實現(xiàn)基于物品的協(xié)同過濾推薦。ZHOU 等［7］提出一種針對非對稱結構的基于隨機游走的網(wǎng)絡表示學習方法。本文對經(jīng)典DeepWalk［8］算法進行改進，面向推薦目標與被推薦對象為相同類型的應用場景，提出一種基于隨機游走的網(wǎng)絡表示學習推薦算法RANE。

1 相關工作

NRL 技術在早期主要是對稀疏高維的節(jié)點進行降維表示，包括主成分分析（Principal Component Analysis，PCA）、局部線 性嵌入（Locally Linear Embedding，LLE）［9］、拉普拉斯特征映射［10］等，但算法復雜度較高且應用條件較嚴苛，因此很難在大規(guī)模的網(wǎng)絡中部署應用。隨著NRL 技術的發(fā)展，研究人員致力于將其與推薦算法相結合，因此Word2vec模型［11］、DeepCrossing 模型［12］等應用于推薦系統(tǒng)的算法模型由此被提出。

Word2vec［11］模型可以較好地計算詞與詞之間的相似度，SkipGram 模型是其中的詞向量訓練模型。對于中心詞而言，該網(wǎng)絡模型在提高上下文單詞出現(xiàn)概率的同時降低其他無關單詞的出現(xiàn)概率。由于訓練網(wǎng)絡所使用的詞匯表通常很大，如果每次預測上下文之后更新全部詞匯表，則會導致過大的計算量，因此需要優(yōu)化模型加速訓練過程。在基于Negative Sampling 的SkipGram 模型中，對于中心詞w規(guī)定上下文單詞均為正樣本，其余單詞均為負樣本，設由隨機游走采樣得到的上下文集合為Context(w)，那么對于一組采樣，最大化目標函數(shù)如下：

其中：對于w上下文中每一個單詞u都要進行負采樣，Neg(u)表示對u的負采樣集合。在n個單詞中，wi出現(xiàn)的頻率為f(wi)，則其被采樣到的概率如下：

引入標志位Lu(x)，對于正采樣x?{u}，令Lu(x)=1，對于負采樣x?Neg(u)，令Lu(x)=0，則式（1）中的條件概率表示如下：

其中：σ為Sigmoid 函數(shù)；vw表示的是輸入詞向量與隱藏層權重矩陣乘積的結果；vx表示的是輸出層權重矩陣中單詞x對應某一列，稱vx為單詞x的輔助詞向量。擴展到總語料庫C，最大化目標函數(shù)如下：

為方便計算，取對數(shù)后可得最終的目標函數(shù)：

DeepWalk［8］將自然語言處理（Natural Language Processing，NLP）應用于NRL 中。DeepWalk 將網(wǎng)絡中通過隨機游走得到固定長度的節(jié)點序列看作是NLP 中的語句，將序列中的節(jié)點看作NLP 中的單詞，通過實驗表明由隨機游走得到的節(jié)點序列組成的語料庫與NLP 的語料庫具有相似的冪律分布特性［8］，對應真實網(wǎng)絡的小世界特性說明該節(jié)點序列能有效描述網(wǎng)絡結構信息，進而使用Word2vec 中的SkipGram 模型進行網(wǎng)絡中節(jié)點的表示學習，并通過Hierarchical Softmax 模型加速訓練過程。

Node2vec［13］算法在DeepWalk 基礎上進行改進，在DeepWalk 中隨機游走是從當前節(jié)點的鄰居節(jié)點中隨機均勻地選取下一個節(jié)點，而Node2vec 設計了兩個參數(shù)p和q，p控制跳向上一個節(jié)點的概率，q控制跳向非上一個節(jié)點的鄰居節(jié)點的概率，并以此控制隨機游走的傾向。若p<1 &q>1，則游走偏廣度優(yōu)先遍歷，著重刻畫局部信息；若p>1 &q<1，則游走偏深度優(yōu)先遍歷，著重刻畫全局信息。偏置參數(shù)的添加雖增加了算法的計算量，但使算法具有更強的可擴展性。

上述基于隨機游走的算法主要考慮的是網(wǎng)絡的一階距離（兩節(jié)點有直接連邊），而LINE［14］算法中提出了網(wǎng)絡的二階距離（兩節(jié)點有共同的鄰居節(jié)點）的概念，用更多的鄰域來豐富節(jié)點的表示。GraRep［15］算法則將一階、二階距離推廣到了n階，定義網(wǎng)絡的n階距離矩陣，使用SVD 算法對網(wǎng)絡的1 到n階矩陣進行分解，每個節(jié)點的特征由1 到n階組合表示。

TADW［16］算法證明了DeepWalk 本質上與 矩陣分解是相同的，并在已經(jīng)較為成熟的矩陣分解框架下，將文本特征引入網(wǎng)絡表示學習。設節(jié)點的鄰接矩陣為M，算法將M分解為3 個矩陣的乘積，其中矩陣T是固定的文本特征向量，另外2 個矩陣W與H為參數(shù)矩陣，使用共軛梯度下降法更新W與H矩陣求解參數(shù)，如圖1 所示。

圖1 TADW 矩陣分解模型示意圖Fig.1 Schematic diagram of TADW matrix decomposition model

上述均為網(wǎng)絡表示學習技術的熱門算法，這些算法在推薦系統(tǒng)領域表現(xiàn)出較好的性能。本文受DeepWalk 算法的啟發(fā)，提出RANE 算法，針對隨機游走和網(wǎng)絡表示兩部分分別進行改進，修正游走序列數(shù)和游走長度，網(wǎng)絡學習中融合屬性信息，最終將輸出用于推薦系統(tǒng)中，有效地提高了推薦性能。

2 本文算法

在原始的DeepWalk 算法中，各節(jié)點在網(wǎng)絡中進行均勻的隨機游走，進而得到固定長度、固定數(shù)量的游走序列，然后通過SkipGram 模型學習節(jié)點的向量表示。本文在DeepWalk 算法的基礎上進行改進，RANE 算法具體步驟如下：

算法1RANE 算法

輸入圖G(V，E)、隨機游走停止概率P、每個節(jié)點的最大游走數(shù)量maxT、每個節(jié)點的最小游走數(shù)量minT、上下文窗口大小k、嵌入維度d、負樣本數(shù)量nns、頂點屬性矩陣A

輸出節(jié)點向量矩陣W、節(jié)點向量輔助矩陣W*、權重參數(shù)向量β

在算法1 中，首先基于網(wǎng)絡重要性進行隨機游走采樣得到節(jié)點序列庫，并設置停止概率控制序列長度；然后在表示學習過程中，融合屬性信息進行學習；最后應用學習后的向量進行相似性表示，進而完成推薦任務。因為RANE 算法是在原始DeepWalk中添加隨機游走相關參數(shù)以及融合屬性信息，并未涉及其他函數(shù)的加入，所以時空復雜度基本不變。

2.1 基于節(jié)點重要性的隨機游走

針對DeepWalk 算法中采樣點過多的問題，重新設計隨機游走策略。對于網(wǎng)絡節(jié)點v，根據(jù)式（6）通過考慮重要性計算游走次數(shù)lv：

其中：maxT為隨機游走的最大次數(shù)；minT為隨機游走的最小次數(shù)；H(v)為節(jié)點的網(wǎng)絡重要性。計算PageRank［17］值需要對H(v)進行數(shù)值量化，迭代公式如下：

其中：d為阻尼系數(shù)；n為總節(jié)點數(shù)；M(v)為網(wǎng)絡中與節(jié)點v關聯(lián)的節(jié)點集合；deg(v)是節(jié)點v的度。通過式（7）不斷進行迭代，最后趨于穩(wěn)定的PR(v)值就是所需的H(v)。

另外，本文在游走過程中加入了停止概率P控制游走序列長度，即在節(jié)點每次向下一個節(jié)點游走時都有概率P結束本次游走，使得游走生成的節(jié)點序列不再是統(tǒng)一長度。

通過以上改進，使得重要的節(jié)點采樣次數(shù)增加，可以更好地還原網(wǎng)絡結構，并且序列長度不一，更接近真實情況。

2.2 融合屬性信息的表示學習

在獲得節(jié)點序列庫后，本文在表示學習階段提出利用屬性信息學習節(jié)點向量表示的ASkipGram 模型。首先，應用自動編碼器調整節(jié)點的屬性維度［18-19］，統(tǒng)一設置為d，所得屬性矩陣為A?R||V×d，其中，V為節(jié)點集，節(jié)點v的屬性向量可以表示為Av。然后，將所得到的屬性信息矩陣融入表示學習中。將屬性信息和網(wǎng)絡結構相結合得到兩者的融合向量U(v)：

其中：Wv為隱藏層的詞向量；βv為節(jié)點v的屬性權重。在式（8）中，在融合節(jié)點屬性信息時，使用進行計算而沒有直接使用權重βv，這樣可以保證無論如何包含屬性信息的部分均不可能為0，進而確保了節(jié)點的屬性信息在模型訓練中的參與度。在得到融合向量U(v)后，使用其代替原文中的詞向量Wv與輸出層的節(jié)點輔助詞向量進行點積，計算得出節(jié)點v與x之間的相似度。

經(jīng)過隨機游走后，可采樣得到節(jié)點v的上下文集合為Context(v)。對于節(jié)點v，Context(v)中的單詞全為正樣本，而其他單詞全為負樣本，因此對而言，最大化目標函數(shù)如下：

其中：u為v上下文集合中的任一單詞。對原模型中條件概率p(x|v)進行改進，計算公式如下：

其中：σ為Sigmoid 函數(shù)；Lu(x)為標志位，當正采樣時Lu(x)=1，負采樣時Lu(x)=0。由于原SkipGram 模型在訓練時未考慮上下文節(jié)點與中心節(jié)點的距離，而對于推薦系統(tǒng)而言，較近的兩節(jié)點之間應該具有更高的相似性，因此本文在式（10）中引入權重λx,v，定義該權重系數(shù)如下：

其中：D(x,v)為節(jié)點x與v之間的距離。當x與v直接相連時，D(x,v)=1；當兩者之間有一個節(jié)點時，D(x,v)=2，以此類推。

將對單個節(jié)點v的計算結論擴展至總語料庫C，則所有節(jié)點最大化目標函數(shù)如下：

將式（9）和式（10）代入式（12），為方便計算對式（12）取對數(shù)作為最終函數(shù)：

令L 對U(v)和分別求偏導：

對于式（14），為在訓練過程中針對每個節(jié)點進行屬性權重的自適應調節(jié)，最終進行更新的參數(shù)為Wv和βv，因此分別對Wv和βv求偏導：

設梯度更新學習速率為η，則Wv、和βv的更新結果為：

算法2ASkipGram(nns，A，k，Cv，W，W*，β)

2.3 應用表示結果推薦

在同質圖的推薦中，以節(jié)點相似性為依據(jù)進行推薦，而其中必然應用到以向量形式對節(jié)點進行表示。根據(jù)上文計算結果，可以得到任意節(jié)點v的向量表示：

為方便進行統(tǒng)一的度量，先對向量進行L2 范數(shù)歸一化處理，然后使用向量內積的方式表示兩節(jié)點的相似度，最終相似度計算結果如下：

對某一節(jié)點而言，利用式（22）計算出該節(jié)點與其他節(jié)點的相似度，排序后根據(jù)預先設定的閾值取出相似度高的節(jié)點進行推薦。

3 實驗與結果分析

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

實驗選取3 個數(shù)據(jù)集進行驗證，分別為Cora、Citeseer 和BlogCatalog，其中，Cora 和Citeseer 數(shù)據(jù)集來源于科學出版物網(wǎng)絡，BlogCatalog 來源于社交網(wǎng)絡。具體統(tǒng)計信息如表1 所示。

表1 實驗數(shù)據(jù)集信息Table 1 Experimental dataset information

3.2 對比算法

本文選定以下4 種算法與RANE 算法進行對比：

1）DeepWalk［8］。該算法 是本文 算法的 思想基礎，采用均勻隨機游走生成節(jié)點序列，并通過SkipGram 模型進行網(wǎng)絡表示學習。

2）Node2vec［13］。該算法針對DeepWalk 的隨機游走部分進行改進，控制隨機游走偏向。

3）GraRep［15］。該算法是對LINE 算法的擴展，定義了網(wǎng)絡的n階距離矩陣并使用SVD 算法對網(wǎng)絡的1 到n階矩陣進行分解，每個節(jié)點的特征由1 到n階的特征拼接表示。

4）TADW［16］。該算法是DeepWalk 算法的 擴展算法，將節(jié)點的文本信息特征矩陣融入到矩陣分解過程中，最終將得到的兩個分解后的矩陣中的對應向量進行拼接，作為節(jié)點的最終嵌入表示。

3.3 評價指標

采用ROC 曲線下方面積（Area Under Curve，AUC）來評測推薦系統(tǒng)性能。在計算過程中，采用下式降低計算復雜度［20］：

3.4 實驗環(huán)境

實驗環(huán)境為Ubuntu 16.04，應用Python 3.6.5 進行算法開發(fā)。為了控制實驗中輸出結果的可比較性，設定所有算法輸出節(jié)點向量的維度均為128 維，使用余弦相似度進行節(jié)點間的相似度計算。對于使用均勻隨機游走的算法，規(guī)定任一節(jié)點游走的次數(shù)為20，序列長度為40，其余參數(shù)根據(jù)實驗選擇最優(yōu)設定。RANE 算法中maxT設為40，minT設為10，隨機游走終止概率P設為0.15。在節(jié)點嵌入學習部分，DeepWalk、Node2vec 與RANE 算法的上下文窗口大小設為5，學習率設為0.01，負樣本個數(shù)設為4。對于GraRep 算法設定融合1 至4 階鄰居信息組成節(jié)點向量，其余參數(shù)均沿用原論文設定。對于TADW 算法，除節(jié)點嵌入維度外其他參數(shù)依照原論文設定，取迭代至穩(wěn)定的節(jié)點嵌入向量作為結果。

在實驗過程中，選取數(shù)據(jù)集的10%作為測試集，其是在保證訓練集中無孤立節(jié)點的情況下隨機選取的，并且保證測試集中正采樣與負采樣數(shù)量相同。

3.5 結果分析

3.5.1 推薦性能分析

改變訓練集的數(shù)量比率（R），使其占數(shù)據(jù)集的40%～90%，測試集不變，均為上文設置。對不同數(shù)量訓練集，每種算法進行10 次獨立測試，取平均值后作為該次實驗的最終結果。

在Citeseer 數(shù)據(jù)集上，5 種算法的準確度對比結果如表2 所示?？梢钥闯?，RANE 算法在不同的訓練集比率下所得結果均優(yōu)于其他算法，而在訓練集比率為40%的情況下，優(yōu)勢最明顯。

表2 5 種算法在Citeseer 數(shù)據(jù)集上的準確度對比結果Table 2 Comparison results of the accuracy of five algorithms on the Citeseer dataset

在Cora 數(shù)據(jù)集上，5 種算法的準確度對比結果如表3 所示，可以看出整體趨勢和Citeseer 數(shù)據(jù)集相同，RANE 算法仍然具有最優(yōu)的性能表現(xiàn)，且在訓練集比率較低的情況下優(yōu)勢更明顯。

表3 5 種算法在Cora 數(shù)據(jù)集上的準確度對比結果Table 3 Comparison results of the accuracy of five algorithms on the Cora dataset

在BlogCatalog 數(shù)據(jù)集上，5 種算法的準確度對比結果如表4 所示。綜合3 個數(shù)據(jù)集上所得結果可以看出，RANE 算法相比其他算法具有更好的推薦效果，并且在訓練集比率較小時優(yōu)勢更明顯，主要原因筆者認為是該算法可以更好地解決冷啟動問題。

表4 5 種算法在BlogCatalog 數(shù)據(jù)集上的準確度對比結果Table 4 Comparison results of the accuracy of five algorithms on the BlogCatalog dataset

3.5.2 隨機游走與表示學習模塊消融實驗

由于本文算法在DeepWalk 算法上對隨機游走和節(jié)點表示學習兩部分均進行改進，為了測試每一部分的改進對最終結果的影響情況，本文對兩部分進行了消融實驗。RRANE 算法表示僅改進隨機游走部分，ARANE 算法表示僅改進節(jié)點表示學習部分，在BlogCatalog 數(shù)據(jù)集上進行消融實驗，準確度結果如表5 所示?？梢钥闯?，兩部分均對最終結果有一定的性能提升，但節(jié)點表示學習部分對整體算法的性能影響更大。

表5 RANE 隨機游走與節(jié)點表示學習模塊的消融實驗結果Table 5 Results of ablation experiments of random walk and node representation learning module of RANE

3.5.3 隨機游走模塊采樣效果驗證

為驗證改進后的隨機游走策略對采樣序列的修正效果，選取BlogCatalog 數(shù)據(jù)集進行實驗，結果如圖2 所示。設置maxT為40，minT為10，隨機游走終止概率為0.15。可以看出，改進后的隨機游走策略更好地保留了網(wǎng)絡結構特性。

圖2 RANE 隨機游走序列節(jié)點分布Fig.2 Node distribution of random walk sequence of RANE

3.5.4 參數(shù)敏感性分析

在BlogCatalog 數(shù)據(jù)集上對算法進行參數(shù)敏感性分析。本文分析maxT與minT參數(shù)，在分別固定minT或maxT的同時調節(jié)另一個參數(shù)進行實驗。如圖3 所示，minT對AUC值的影響更大。

圖3 min T 與max T 的參數(shù)敏感性實驗Fig.3 Experiment on parameters sensitivity of min T and max T

對隨機游走部分的終止概率P進行敏感性測試，設置P為0.05、0.10、0.15、0.20、0.25、0.30。如圖4所示，終止概率越小，AUC 值越大，但此時游走長度更長，相應的計算量就會增大，因此實驗過程中應綜合考慮推薦效果與計算成本。

圖4 游走終止概率的參數(shù)敏感性實驗Fig.4 Experiment on parameter sensitivity of walk termination probability

由于RANE 算法在計算節(jié)點相似性時引入了有關上下文節(jié)點與中心點距離的權重，因此需要對ASkipGram 模型的窗口大小k進行參數(shù)敏感性分析，窗口大小依次設置為1、3、5、7、9、11、13、15。如圖5所示，隨著窗口的不斷增大，AUC 值呈先增大后減小的變化趨勢，說明窗口取得過大或過小都會影響節(jié)點網(wǎng)絡特征的表征效果。

圖5 ASkipGram 模型窗口大小的參數(shù)敏感性實驗Fig.5 Experiment on parameter sensitivity of window size of ASkipGram model

測試節(jié)點嵌入維度d分別為16、32、64、128 和256 時的RANE 算法AUC 值，其他參數(shù)均為上文設置，在BlogCatalog 數(shù)據(jù)集上的實驗結果如圖6 所示，可以看出在嵌入維度為128 時AUC 取得最優(yōu)值。

圖6 節(jié)點嵌入維度的參數(shù)敏感性實驗Fig.6 Experiment on parameter sensitivity of node embedded dimension

4 結束語

本文在DeepWalk 算法的基礎上，提出基于隨機游走的網(wǎng)絡表示學習推薦算法。根據(jù)節(jié)點重要性決定游走序列數(shù)，設置終止概率使得游走序列的長度不完全相同，從而更接近真實情況。同時，在節(jié)點表示學習過程中，融合節(jié)點的屬性信息，自適應調整節(jié)點屬性信息權重，并考慮上下文節(jié)點離中心節(jié)點的距離，以獲得更準確的推薦結果。在3 個數(shù)據(jù)集上的實驗結果表明，該算法具有較好的推薦性能，并且有效解決了冷啟動問題。但由于該算法隨機游走部分設置的截止概率為隨機生成，因此后續(xù)可將其與游走長度相關聯(lián)，進一步提高推薦準確度。