TWD-GNN：基于三支決策的圖神經網絡推薦方法

李 嫻，張澤華，趙 霞，田 華

太原理工大學 信息與計算機學院，山西 晉中030600

1 引言

推薦系統作為一種有效的信息過濾系統，可通過用戶顯式或隱式行為獲取信息[1]。一方面找到用戶可能感興趣的項目，另一方面通過推薦促進用戶與項目之間的交互來增加收益。推薦系統已經廣泛應用到各個領域，如電子商務、旅游推薦、在線圖書電影、社交網絡等[2]，可以通過個性化服務滿足用戶的內在隱含需求。

目前，國內外研究者提出了很多推薦算法。推薦系統通過用戶的顯式或隱式行為獲取用戶的偏好。主要分為基于內容、協同過濾（基于用戶、基于物品、基于模型、基于矩陣分解）等方法[3]?；趦热莸耐扑]算法[4-5]根據用戶過去喜歡的物品特征學習用戶的喜好，最后生成推薦列表。但是算法要求提取有效的特征，容易出現一詞多義等問題。協同過濾算法[6-7]普遍應用于各大推薦任務中，將有共同興趣的用戶視為相似用戶?；谟脩?項目的評分矩陣計算得到相似用戶列表，在相似列表中出現頻次較多的商品推薦給用戶。這些推薦算法前提條件是用戶信息是清晰且確定的，將用戶劃分到某一類相似群體中。然而在復雜網絡中存在不確定性容易造成信息沖突，直接影響推薦結果。

復雜網絡中存在的信息沖突是由于信息的不充分或者不完備造成的，本文從融合多源信息的角度解決不確定網絡中的推薦問題。推薦結果很大程度受到節點相似度的影響，對于復雜網絡中的節點使用傳統的相似度測量很難取得良好的效果。節點的相似性度量對推薦結果起著關鍵的作用。本文采用圖神經網絡融合結構信息和屬性信息獲得節點表示，更好地挖掘節點相似性。但是圖神經網絡無法適用于以下場景：用戶6電影評分為5分，而用戶3評分為1分。在這種情況下，由于信息不充分容易造成信息沖突，用戶1無法立即做出選擇，如圖1所示。

圖1 電影推薦網絡中的“信息沖突”示例

因此，本文提出基于三支決策的圖神經網絡推薦算法。首先，利用三支決策理論梳理局部沖突；然后，在信息不充分的邊界域基礎上，利用圖神經網絡將節點映射到一個低維的向量空間，同時保持節點結構信息和屬性信息；最后，根據獲得的節點嵌入信息重構網絡并預測評分。

本文的主要貢獻包括兩個方面：

（1）提出了基于三支決策的圖神經網絡推薦系統方法。該方法在三支決策理論的基礎上通過圖神經網絡預測評分，可有效地解決含有部分缺失數據的推薦問題。

（2）本文實現了TWD-GNN算法的評測平臺。在不同數據集上與傳統的推薦算法相比，提高了推薦的準確度，驗證了TWD-GNN算法的可行性與有效性。

2 相關工作

2.1 圖神經網絡

隨著互聯網的迅猛發展，大規模圖結構數據已經遍布各個領域。例如，微博用戶之間形成社交網絡，淘寶用戶與商品構成電子商務網絡，生物分子網絡以及交通網絡等等。與圖像、文本不同，圖結構是復雜多變的不規則領域。利用機器學習算法和數學模型進行圖分析的關鍵之處在于圖的表示。圖神經網絡能夠學習到圖結構信息和節點特征，同時節省計算空間和時間，適用于節點分類、邊預測以及圖分類等任務[8-9]。

圖神經網絡作為一種分析圖結構的深度學習方法受到越來越多的關注。由于非歐幾里德數據的節點排序是沒有規律的，傳統的神經網絡[10]需要遍歷節點可能出現的所有順序，難以承受如此龐大的計算量。同時受到網絡嵌入[11]的啟發，將圖的節點、邊以低維的向量表示出來。Defferrard等人[12]提出ChebNet，將濾波器定義為Chebyshev多項式，驗證了在圖上學習局部特征的能力。Gao等人[13]通過偏置隨機游走保留節點序列，只關注結構信息而忽略了節點的屬性信息。然而推薦任務具有異質性，包含大量且多種類型的信息?；趫D網絡的推薦任務將用戶和項目視為節點，需要整合它們之間的聯系以及其他輔助信息來提高推薦質量?，F有的方法大多只考慮了單一的信息，本文的主要工作是通過圖神經網絡挖掘多源信息獲得更加精確的推薦。

2.2 三支決策理論

三支決策（three-way decision）旨在處理信息模糊和不確定性問題，將集合分為正域、負域和邊界域，分別對三個區域進行不同的處理[14]。正域表示接受，負域表示拒絕，邊界域表示信息不充分時，延遲做決策。當信息不充分時，邊界域相當于加入一個緩沖區，從而規避了傳統二支決策帶來的錯誤拒絕或錯誤接受。三支決策形式化描述如下[15-16]：

定義1基于一個標準C，整體集合U劃分為正域（POS）、邊界域（BND）、負域（NEG）。存在2種狀態：屬于C和不屬于C，3種行為：A={aP,aB,aN}分別對應接受、延遲、拒絕。

定義2不同狀態下采取不同行為對應的損失函數矩陣，如表1。其中，λPP,λBP,λNP表示當對象屬于C時采取aP,aB,aN三種行為對應的損失值。λPN,λBN,λNN表示當對象不屬于C時采取aP,aB,aN三種行為對應的損失值。

表1 損失函數矩陣

定義3決策規則為：

若p(C|[x])≥α，則x∈POS(C)

若β＜p(C|δ(xi))＜α，則x∈BND(C)

若p(C|[x])≤β，則x∈NEG(C)

其中，p(C|[x])表示對象x屬于標準C的概率：

定義4在非空樣本集合U中給定任意xi，xi在條件屬性C的子集B中的鄰域為：

其中，δ為鄰域參數。ΔB(xi,xj)表示xi和xj在屬性子集B上的距離。

定義5對象x屬于某一類C的概率為：

近年來，三支決策已應用到很多研究工作中。許多學者對三支決策進行分析，探討了三支決策未來的發展方向[17-18]。Liu等人[19]將不完備信息系統中出現的缺失值與損失函數性結合形成一個新的三支決策模型。Zhang等人[20]提出一種新的多標簽分類模型（TSEN）降低數據的復雜性和標簽的模糊度。從粒度角度來看，Yang等人[21]提出多粒度粗糙集的層次結構屬性。Qian等人[22]構建多粒度序貫三支模型利用多視圖角度處理不確定的數據。除此之外，三支決策模型還應用到垃圾郵件過濾、醫療選擇、面部相似性分析等各個方面[23]。

綜上所述，三支決策理論遵循“三分而治”，將復雜的問題簡單化。當信息不充分或不完備時，這種動態決策為大數據處理帶來了新的思路。本文選擇三支決策理論梳理不確定信息并挖掘更加詳細的知識。

3 基于三支決策的圖神經網絡推薦系統方法

TWD-GNN算法利用三支決策理論將訓練集劃分為POS、BND、NEG。由于信息不充分或者不完備，BND易發生信息沖突，NEG是噪聲數據。對POS中的用戶保留結果，對BND數據加入屬性信息，形成特征矩陣。通過圖神經網絡學習用戶和項目的節點表示，提取有用信息并重構網絡預測未觀察到的鏈接解決圖稀疏問題。TWD-GNN算法將三支決策理論與圖神經網絡相結合預測用戶評分，提高推薦質量。算法步驟如下：

算法1基于三支決策的圖神經網絡算法

輸入：A；/*評分矩陣*/

L；/*損失函數矩陣*/

輸出：A′；/*預測評分矩陣*/

①POS=?，

BND=?，

NEG=?；/*初始化*/

②for each x in A：

POS,BND,NEG←x；/*將用戶x劃分到正域、負域、邊界域*/

end for

③if x in BND：

X←x；/*將基于BND進行one-hot編碼融合屬性信息，形成特征矩陣X*/

h=f(X,A)；/*將用戶和項目嵌入到低維的空間*/

A′=g(h)/*預測評分矩陣*/

end if

TWD-GNN算法由數據集劃分、圖網絡表示、重構圖網絡等部分組成。

3.1 數據集劃分

基于三支決策模型將整個訓練集劃分為正域、邊界域、負域。本文設計的損失函數矩陣，如表2所示。假設推薦給用戶不喜歡的項目帶來的損失值大于用戶喜歡的項目沒有被推薦的損失值。其中，Y表示喜歡，N表示不喜歡。90表示推薦給用戶不喜歡的項目帶來的損失值；18表示當用戶喜歡這部電影時，延遲決策所對應的損失值；45表示用戶喜歡的項目沒有被推薦的損失值。

表2 MovieLens的損失函數矩陣

由表2損失函數矩陣和公式（1）計算得到：α=0.8，β=0.4。同時也符合文獻[24]提到的閾值組合，其中(0.3,0.8)符合人們中性的決策習慣。下面進一步舉例說明三支決策的思想，如圖1所示。首先，將整個數據集按照電影類型分為喜劇、科幻等，假設圖1中所有電影為喜劇。然后，根據公式（4）用戶對電影喜歡（評分[4,5]）的概率PY初步判定用戶偏好。評價標準為：[0.6,1]-喜歡(Y)，[0.4,0.6)-可能喜歡(M)，[0,0.4)-不喜歡(N)，如表3所示。其中：

表3 用戶的初步評價結果

最后，根據評分矩陣得到用戶之間的余弦距離，即鄰域距離，如表4所示。本文設置鄰域參數δ為0.4。傳統的鄰域三支決策模型定義的距離為Minkowski Distance距離越小，樣本相似度越高，將小于鄰域參數δ的劃為鄰域類。但是，閔式距離不適用于稀疏矩陣，在推薦系統中常用0代替用戶未評分的項，過多的0會影響閔式距離的計算。因此，本文使用余弦距離的值越大，樣本越相似，將大于鄰域參數δ的劃為鄰域類。

表4 用戶的鄰域距離

以用戶u1為例，根據表3中的決策屬性D得到u1∈{u1,u2,u4},根據公式（3）計算：

即β＜0.67＜α，因此u1屬于邊界域。同理，將每個用戶劃分到各個區域。算法具體步驟如下：

算法2數據集劃分

輸入：A,L；

輸出：POS,BND,NEG

①C；/*制定評價標準*/

D；/*決策屬性*/

δ；/*初始化鄰域參數*/

α,β；/*根據表2計算閾值*/

②S1,S2,…,Sn；/*將數據集劃分為n類*/

③for each x in Sido：

δ(xi)={xj|xj∈S,dis(xi,xj)≥δ}；/*計算用戶的鄰域類*/

end for

④POS←p(C|δ(xi))≥α；BND←β＜p(C|δ(xi))＜α；

NEG←p(C|δ(xi))≤β；/*根據決策規則將用戶劃分到正域、邊界域和負域*/

在推薦過程中，用戶與商品的交互是稀疏的。其中，得到的POS結果保留并直接推薦。在BND的基礎上通過one-hot編碼形成用戶和項目的特征矩陣。

3.2 圖網絡表示

有效的建模和利用復雜信息是推薦任務的關鍵。對于已經形成的用戶-項目鄰接矩陣（評分矩陣）和特征矩陣，仍然是大規模、高維度、稀疏的網絡并存在一些噪聲數據。為降低計算復雜度，利用圖神經網絡將其壓縮至低維、稠密的向量空間，學習節點的有用信息。令G=(u,v,ε,?)表示含有用戶節點ui∈u，項目節點vi∈v以及邊(ui,r,vj)∈ε的無向圖。其中，r∈{1,2,…,R}=?表示邊帶有的評分等級。

圖神經網絡的特征提取主要依賴于卷積操作。為了更好地學習節點的隱藏狀態，需要卷積層取得局部特征。通常圖神經網絡的卷積操作分為譜方法和空間域兩類。其中，譜方法依賴于拉普拉斯矩陣分解，計算復雜度較高。而空間域是通過整合鄰域節點信息將圖映射到向量。TWD-GNN算法通過一階鄰域獲取局部特征可以被認為是信息傳遞的過程[25]。將信息從用戶傳遞并轉換到項目節點，反之亦然，如圖2所示。

從節點本身和信息傳遞兩個角度形式化表示：

其中，xi表示每個節點原始的特征向量。xi'表示整合每個節點的鄰居信息獲得節點表示，形成N×D的特征矩陣。同時為每個評分級r分別做相應的信息傳遞。即：

圖2 信息傳遞示意圖

其中，mi→j,r表示用戶i到項目j在評級r下的信息傳遞。Ni表示節點xi的鄰居個數，作為歸一化常數。由于邊上帶有評分的標簽，Wr表示不同類型邊參數矩陣。接下來，使用非線性激活函數σ(?)=ReLU(?)進行映射：

將上層得到的特征向量hi進行權重計算，即經過全連接層得到用戶節點的最終嵌入ui，項目節點的最終嵌入vj也類似：

其中，W1表示原始特征向量的權重矩陣，b表示偏置項，加入b是為了能夠更好地擬合數據，fi表示用戶特征（輔助信息）的表示，W2表示用戶鄰居的權重矩陣，W表示嵌入之后特征向量的權重矩陣。

以特征矩陣和各個評級下的鄰接矩陣為輸入，融合了結構和屬性信息。通過在用戶-項目圖上傳遞信息，將其壓縮至低維空間，得到用戶和項目的最終嵌入表示。

3.3 重構圖網絡

在現實生活中，用戶只與有限的項目交互，即網絡中缺少鏈接?；谏缃痪W絡的推薦系統本質上是預測問題，將用戶和項目的嵌入恢復成原始數據，也就是重構圖預測評分，補充網絡中缺失的鏈接，從而解決圖稀疏的問題。為了重構圖中的鏈接，將每一種評級視為單獨的類，然后應用softmax函數，在可能的評級上生成概率分布：

其中，ui是用戶最終的嵌入表示，vj是項目最終的嵌入表示。p(A′ij=r)表示softmax函數獲得用戶和項目之間存在不同評分鏈接的概率。Er∈E×E是用戶或項目嵌入后的參數矩陣。預測評級A′ij為：

本文設定的損失函數為預測評分的負對數似然：

當r=Aij時Ι[r=Aij]=1，否則為0。矩陣Ω∈{0,1}Nu×Ni使得A中觀測到的評級表示為1，而未觀測到的評級表示為0。那么，這樣只優化了觀測到的評級。

傳統的dropout讓神經網絡的某個神經元以一定概率停止工作來減少過擬合。為了更好地訓練未觀測到的評級，通過隨機丟棄特定節點的所有傳出消息，稱為節點丟失（node dropout）[26]。在實驗中發現節點丟失比信息丟失在正則化方面更加有效。節點丟失使嵌入更加獨立于特定的用戶或項目影響。

通過不同觀測到的評級對公式（13）中損失函數的貢獻引入小批量梯度下降（mini-batching）。也就是說，本文只從用戶和項目對的總和中抽取固定數量的貢獻。通過僅考慮對損失函數的固定數量的貢獻，移除未出現在當前批次中的用戶和項目。這既是一種有效的正規則化手段，也是降低訓練模型的內存需求，同時加快收斂速度。TWD-GNN算法訓練的復雜度為ο((N+F)HI)，其中N是節點數，F是節點特征的維數，H是隱藏層的大小，I是迭代次數。實際上，F,H?N,I獨立于N，因此整個算法的時間復雜度為ο(N)。

4 實驗設計與分析

4.1 測試數據集

實驗使用的數據集是推薦系統常用的MovieLens（100K）數據，包括943用戶對1 682部電影的100 000個評分，評分范圍是[1，5]。還有用戶（包括年齡、性別、職業等）和電影類型等輔助信息。整個數據集稀疏度為0.063 。

實驗需要對數據集進行預處理。首先，輸入評分矩陣，根據設計的損失函數矩陣計算出閾值α=0.8,β=0.4，訓練得到最優的鄰域參數δ為0.4。

其次，由于用戶喜歡一部電影不僅僅是因為評分高，還可能因為電影的類型等等諸多因素。在邊界域的基礎上，融合用戶和電影的輔助信息。由于用戶和項目特征都是離散的，需要對其進行one-hot編碼。例如，用戶性別={男，女}，編碼后為，男：10，女：01；電影類型={喜劇，戰爭，科幻}，編碼后為，喜?。?01，戰爭：010，科幻：100?？梢?，one-hot是一位有效編碼，當用戶或者項目有多個特征出現時，將各個特征的編碼連起來形成最終的節點表示。one-hot編碼便于特征歸一化，同時距離計算更合理。

通過多次實驗設置全連接層隱藏單元個數為8，學習率設置為0.01，dropout率為0.6得到結果最優。本次實驗將整個數據分為80%訓練集，20%的測試集。實驗結果取5次運行的平均值。

4.2 實驗方法及評測指標

為驗證TWD-GNN算法的可行性，分別與以下三種算法比較。

CF：傳統的協同過濾根據評分矩陣，采用余弦相似度發現相似偏好的用戶，前k個為最終推薦結果。

fMF[27]：構建決策樹，每個節點代表一個問題。在訪問過程中通過用戶對項目問題的反饋不斷改變用戶表征，啟動用戶偏好。

ApproSVD[28]：基于奇異值分解的增量算法轉換為矩陣更新問題。將用戶的偏好向量乘以電影特征向量，獲得最終的預測評級。

實驗采用的評測指標是均方根誤差（RMSE）及平均絕對誤差（MAE），T是測試集：

為了驗證算法的有效性，與傳統的協同過濾算法CF、冷啟動推薦算法fMF以及矩陣分解算法ApproSVD的RMSE、MAE進行橫向比較，以及在數據不同稀疏度時分析推薦性能?？v向分析三支決策閾值的上邊界α、鄰域參數δ對推薦結果的影響。

4.3 與傳統推薦算法比較

TWD-GNN算法基于電影MovieLens數據集與上述三種算法進行比較。推薦的RMSE、MAE結果如表5所示。從表5中可以看出：與傳統的協同過濾CF相比，TWD-GNN算法具有較好的推薦準確性。因為傳統的協同過濾只是基于評分矩陣來推薦，現實中用戶只對有限的電影進行打分。ApproSVD算法實際上是基于矩陣分解來學習潛在特征，沒有融入用戶或者項目的輔助信息。fMF算法是通過初始訪問啟動用戶偏好，以函數的形式將用戶的反饋與配置文件綁定。但是繁瑣的訪問過程或者涉及用戶的隱私問題會逐漸降低用戶對推薦系統的信心。由于TWD-GNN算法不只是基于評分矩陣，同時融入了用戶和電影的輔助信息，即結合了結構屬性和特征屬性。TWD-GNN算法的推薦效果優于其他的推薦算法。TWD-GNN算法還在Douban電影數據集下與其他三種算法進行比較，如表6所示。取Douban數據集2 000名用戶對2 000部電影的106 828個評分，評分范圍是[1，5]，數據集稀疏度為0.027?？梢钥闯?，在Douban數據集上TWD-GNN算法仍有較好的推薦效果。

表5 MovieLens下不同算法比較

表6 Douban下不同算法比較

4.4 算法在不同稀疏度下的表現

為驗證TWD-GNN算法在稀疏數據下的效果，從MovieLens訓練集中刪除一部分數據，得到不同稀疏度下的RMSE和MAE。如圖3和圖4所示。隨著數據稀疏度的不斷增加，CF算法準確度下降得最快。fMF和ApproSVD算法在稀疏度為95%之前準確度下降得比較平緩。而TWD-GNN算法即使在稀疏度為97%時仍有較好的推薦效果。

圖3 不同稀疏度下RMSE比較

圖4 不同稀疏度下MAE比較

4.5 參數的影響

參數影響著推薦結果，對參數敏感性進行分析顯得尤為重要。本節基于MovieLens數據集的訓練集和測試集分析三支決策閾值的上邊界α，以及鄰域參數δ對推薦準確度RMSE和MAE的影響。根據表2的損失函數矩陣，計算出三支決策最優的閾值。在β≤α的約束條件下計算α和β變化時的推薦準確度。經多次實驗驗證參數步長為0.1時結果變化最明顯，同時驗證α和β在訓練/測試集是否最優。

參數α決定整個數據集中正域的多少，α過小可能會把不確定信息推薦給用戶，造成錯誤的接受；α過大使推薦要求更加苛刻，容易把有用的信息視為噪聲數據，直接影響最終的推薦結果。圖5和圖6中的取值范圍是[0.5,1]，步長為0.1。從測試集與訓練集可以看出，在α=0.8時RMSE及MAE的值最小，即TWD-GNN算法推薦效果最優。同理，三支決策閾值的下邊界β=0.4時效果最優。

圖5 α對RMSE的影響

圖6 α對MAE的影響

參數δ決定鄰域類的個數，鄰域參數δ過大，對鄰居的要求更高，甚至找不到鄰居；鄰域參數δ過小，不足以把數據分開。本文工作設置δ的取值范圍為[0，1]，步長為0.1。從圖7和圖8中可以看出δ=0.4的時候效果最好。

圖7 δ對RMSE的影響

圖8 δ對MAE的影響

綜上所述，TWD-GNN算法的優勢在于采用三支決策理論將大規模的復雜網絡縮小至易于處理的集合。正域直接推薦，而邊界域由于信息不足使得用戶延遲決策，負域是噪聲數據。將邊界域融合除電影評分以外的其他輔助信息，如用戶的年齡、職業，電影的類型等。根據輔助信息中提取的有效信息重構圖網絡，從而解決含有部分缺失數據的推薦問題?？梢钥吹皆诓煌∈瓒群蛿祿?，TWD-GNN算法有較好的推薦效果。

5 結束語

本文提出了一種基于三支決策的圖神經網絡推薦方法。針對復雜網絡中存在信息沖突的問題，將大規模數據經三支決策劃分可有效將不確定問題域空間縮小到一個有限的集合范疇內。然后通過圖神經網絡學習結構信息和屬性信息，使其適用于某些信息不完備的場景。TWD-GNN算法在一定程度上能夠解決含有不確定信息的推薦問題。同時與傳統推薦系統方法比較，TWD-GNN算法具有較好的推薦質量。