NEG-MF：一種針對推薦系統(tǒng)的矩陣分解圖嵌入模型

趙素芬

摘? 要： 傳統(tǒng)的矩陣分解圖嵌入模型由于不對大量未知關(guān)系建模，其性能面臨著很大的挑戰(zhàn)性。為了提升矩陣分解模型的性能，提出了一種基于負采樣技術(shù)的矩陣分解模型NEG-MF。該模型能夠從跳數(shù)大于6的鄰居節(jié)點中進行負采樣，以降低模型生成圖嵌入時對于負樣本的偏差。在DBLP數(shù)據(jù)集上做的大量實驗結(jié)果表明，相比其他的基線方法，基于NEG-MF的推薦算法在學術(shù)合作關(guān)系推薦問題上的性能有明顯地提升。

關(guān)鍵詞： 矩陣分解; 圖嵌入; 推薦系統(tǒng); 負采樣

中圖分類號：TP311? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2021）09-06-04

Abstract： The traditional matrix factorization graph embedding model does not consider a large number of unknown relationships， so that its performance faces great challenges. In order to improve the performance of the generated embeddings， NEG-MF， a matrix factorization model based on negative sampling is proposed. When the model generates node embeddings， it can perform negative sampling from the neighbor nodes with hops>6 to reduce the bias of negative samples. A large number of experiment results on DBLP data sets show that， compared with the baseline methods， the performance of the recommendation algorithm based on the proposed NEG-MF has a significant improvement in the recommendation of academic collaborators.

Key words： matrix factorization; graph embedding; recommender system; negative sampling

0 引言

圖是自然界中一種非常重要的數(shù)據(jù)結(jié)構(gòu)。許多應用都是定義在圖的基礎(chǔ)上，例如學術(shù)合作網(wǎng)絡、蛋白質(zhì)交互網(wǎng)絡、社交網(wǎng)絡、知識圖譜等等。在基于圖的眾多機器學習問題中，其核心任務就是找到一種將圖的結(jié)構(gòu)信息和語義信息融合到機器學習任務的方法，即將網(wǎng)絡中的節(jié)點、邊或子圖映射到低維的向量空間，并且使得到的特征向量盡可能地保持原有圖結(jié)構(gòu)信息、節(jié)點屬性信息和語義信息等等，即圖嵌入技術(shù)[1]。

隨著word2vec模型[2-3]在文本嵌入領(lǐng)域的廣泛應用，目前已經(jīng)涌現(xiàn)了大量的圖嵌入算法，包括各種基于矩陣分解的模型（GF[4]，LAE[5]，GraRep[6]，HOPE[7]，LINE[8]等等），基于隨機游走的方法（Deepwalk[9]，Node2vec[10]等），基于鄰居的自編碼模型（SDNE[11]，DNGR[12]）以及基于圖神經(jīng)網(wǎng)絡的模型（GCN[13]，GraphSage[14]）等等。不過，由于真實世界中網(wǎng)絡的復雜性，現(xiàn)有的圖嵌入模型通常面臨如下挑戰(zhàn)。

⑴ 網(wǎng)絡的大規(guī)模性 真實世界中的網(wǎng)絡常常是大規(guī)模的，包含成千上萬的節(jié)點和復雜的關(guān)系，這對圖嵌入算法的學習效率提出了很大的挑戰(zhàn)。一個好的模型應當具有很好的可擴展性，具有更少的時間復雜度和空間復雜度，否則難以在小規(guī)模的計算平臺上運行。

⑵ 嵌入模型本身需要滿足多目標性 圖嵌入模型不僅需要考慮網(wǎng)絡的結(jié)構(gòu)特征，還需要考慮屬性信息、語義信息等。除此以外，嵌入模型在滿足通用性的要求之外，還應當能夠針對特定的機器學習任務有較好的效果。如何在一個模型中同時滿足多個學習目標，對圖嵌入算法提出了巨大的挑戰(zhàn)。

⑶ 網(wǎng)絡的動態(tài)性真實世界中的網(wǎng)絡是在不斷變化的。如果圖嵌入模型是直推式的，則每次網(wǎng)絡有變化時，都需要重新訓練，這是一種巨大的耗費。如何處理動態(tài)變化的網(wǎng)絡，對圖嵌入模型提出了嚴峻的挑戰(zhàn)。

在現(xiàn)有的圖嵌入模型中，矩陣分解是其中一種最經(jīng)典和基礎(chǔ)的一種。由于矩陣分解類模型相對簡單，針對大圖的可擴展性非常好，因此在各類應用中應用十分廣泛。然而，基本的矩陣分解模型[4]僅對正例進行建模，給了負樣本太多的誤差。這會導致生成的嵌入性能非常有限。為了提升矩陣分解模型生成圖嵌入的性能，針對挑戰(zhàn)問題⑴和⑵，我們提出了一種新的基于負采樣技術(shù)的矩陣分解模型NEG-MF。NEG-MF模型在原有的GF模型的基礎(chǔ)上，加入了對未知關(guān)系的建模。具體來說，模型能夠從跳數(shù)大于6的網(wǎng)絡鄰居節(jié)點中進行負采樣，以降低模型生成嵌入時對于負例的偏差。

針對DBLP數(shù)據(jù)集，我們做了大量的實驗。實驗結(jié)果表明，相比較傳統(tǒng)的基線推薦方法（共同鄰居法、AA算法、DeepWalk、Node2Vec以及基本的矩陣分解模型等），改進的NEG-MF模型在推薦系統(tǒng)的性能上有較大的提升。

1 研究問題定義

本文使用的數(shù)據(jù)集是DBLP文獻數(shù)據(jù)集（https：//dblp.uni-trier.de/xml/）。該數(shù)據(jù)集中包含了計算機類學術(shù)論文的元數(shù)據(jù)信息，包括論文的標題、作者、發(fā)表年份、發(fā)表期刊/會議名、URL鏈接等等。通過對文獻數(shù)據(jù)集中作者之間的合作關(guān)系進行提取，可以構(gòu)建一個學術(shù)社交網(wǎng)絡[G=V，E]。其中，[V=v1，v2，…，vn]表示網(wǎng)絡中的學者，[E=eij，1≤i，j≤n]表示兩個作者[vi]和[vj]之間具有合作關(guān)系。基于已有的合作關(guān)系，我們?yōu)槊恳粋€目標用戶推薦潛在最有價值的top-k個新的合作關(guān)系。

定義1：基于圖嵌入技術(shù)的學術(shù)合作推薦問題

針對任意一個t時刻之前的學術(shù)社交網(wǎng)絡[G=（V，E）]，為[G]中每一個節(jié)點[vi]生成低維特征表示[zi∈Rd，d?|V|]，使該特征表示能夠盡可能的捕獲[G]中的網(wǎng)絡結(jié)構(gòu)信息和屬性信息。同時，針對給定的目標用戶s，為其推薦在[t+Δt]時刻最具潛在合作性的top-k個合作關(guān)系。

從定義1中可以看出，本文要解決的研究問題是多目標的。也就是說，模型在為網(wǎng)絡中的每個節(jié)點生成嵌入的同時，需要能夠為特定的目標用戶推薦新的社交關(guān)系。

2 新的基于負采樣技術(shù)的矩陣分解模型NEG-MF

2.1 經(jīng)典的矩陣分解模型Graph Factorization（GF）

經(jīng)典的矩陣分解模型GF[4]的編碼函數(shù)為直接編碼，即：

2.2 NEG-MF矩陣分解模型

為了提升GF模型的性能，我們提出了一個新的矩陣分解模型：NEG-MF，其思路是在損失函數(shù)⑶中增加對負樣本的建模。我們將公式⑶中的損失函數(shù)修改為：

基于計算好的梯度公式，我們在表1中給出了NEG-MF算法的隨機梯度下降（SGD）的版本。在實際運行過程中，也可以視系統(tǒng)內(nèi)存大小將其修改成為批梯度下降的版本。

2.3 關(guān)系推薦

基于2.2節(jié)抽取的用戶節(jié)點嵌入，我們可以使用多種推薦模型為特定的目標用戶s進行新的關(guān)系推薦。首先， 我們定義了多種打分函數(shù)對s和候選推薦用戶u的交互值進行評分。

⑴ 內(nèi)積函數(shù)：[frs，u=zs?zu]

這是最簡單直接的推薦模型。也就是說，基于前面已經(jīng)求解的嵌入，使用內(nèi)積函數(shù)求解目標用戶s和候選推薦用戶u之間的關(guān)系得分。在這個模型中，求解節(jié)點嵌入和合作關(guān)系推薦是兩個互相獨立的組件。

⑵ 非線性神經(jīng)網(wǎng)絡模型：[frs，u=σ（Wzszu+b）]

這里，[σ]是sigmoid函數(shù)，W和b是可以訓練的模型參數(shù)，[zszu]表示向量的拼接。在這個模型中，由于包含可訓練的參數(shù)，因此可以定義推薦模型階段的損失函數(shù)為：

其中，[VL]是帶標記的用戶集合;

[pu|s=exp （frs，u）u'∈Vexp （frs，u'）]是用戶u和用戶s之間的條件概率相似度。

這時，求解節(jié)點嵌入和關(guān)系推薦既可以是兩個相互獨立的部分，也可以進行融合。如果將這兩個部分放在同一個模型中一起訓練，則模型的總損失函數(shù)為：

這樣，可以在一個模型中同時學習到節(jié)點嵌入，以及推薦系統(tǒng)部分的模型參數(shù)值。在實際應用中，除了單層的神經(jīng)網(wǎng)絡模型，還可以選擇很多其他類型的推薦模型和嵌入模型進行融合。

使用打分函數(shù)[frs，u]計算出針對用戶s的候選用戶得分之后，按照從高到低的次序選擇值最大的前k個推薦給用戶s即可。

3 實驗結(jié)果

3.1 數(shù)據(jù)集和預處理

本文使用的數(shù)據(jù)集是DBLP數(shù)據(jù)集（2019-05版本）。我們首先將數(shù)據(jù)集中全部的期刊論文、會議論文以及全部作者的信息抽取出來，然后將所有論文中發(fā)表年份小于1990的全部去除。接著，以2014年為分割線，統(tǒng)計每個作者在1990年至2013年期間（訓練階段）以及2014年至2020年（測試階段）發(fā)表論文的總篇數(shù)?？紤]到發(fā)表論文數(shù)較少的學者對整體的網(wǎng)絡結(jié)構(gòu)影響較小，我們?nèi)?-核作者（在訓練階段和測試階段發(fā)表論文數(shù)均不小于4篇的作者）。基于這些4-核作者在訓練階段發(fā)表論文建立的合作關(guān)系，我們首先生成了訓練階段的鄰接矩陣S1，然后得到一個囊括156021個作者的極大聯(lián)通組件。我們剔除了不在極大連通子圖中的作者，以及在測試階段沒有創(chuàng)建任何關(guān)系的作者，將剩下的153248個作者作為最終的實驗對象。數(shù)據(jù)集的最終統(tǒng)計信息如表2所示。

3.2 基線方法和評估指標

為了評估NEG-MF圖嵌入算法在學術(shù)合作關(guān)系推薦問題上的性能，我們將NEG-MF方法的推薦性能和以下基線方法進行了比較，包括無監(jiān)督推薦算法：共同鄰居（CNs）、Academic/Ada（AA）以及最短距離（SP），以及圖嵌入算法：基本的矩陣分解（GF）、DeepWalk（DW）以及node2vec （N2V）模型。模型的評估指標為top-k關(guān)系推薦的準確率precision@k以及召回率recall@k。

3.3 實驗結(jié)果和分析

表3中給出了各個算法的整體的性能的比較（其中，所有圖嵌入算法DW，N2V，GF，NEG-GF的節(jié)點嵌入維度均設置為256維）。從表3中可以看出，與經(jīng)典的各種基線方法相比，NEG-MF方法在精確率和召回率上均取得了最好的效果。即使相對于能夠?qū)Ω唠A鄰居關(guān)系建模的DeepWalk算法和Node2vec算法來說，新提出的NEG-MF算法也毫不遜色。除此以外，我們還探討了當節(jié)點嵌入維度從64變化到512時矩陣分解嵌入算法的推薦效果的比較，結(jié)果顯示在表4中。從表4可以看出，當生成的節(jié)點嵌入維度增加時，模型的推薦性能會變的更好。但是，當嵌入維度較低時，維度增加會使推薦性能增加的幅度更大;當維度增加到一定程度的時候（比如超過256維），靠增加維度的方式能夠提升的性能非常有限?？紤]到模型的性能與復雜度之間的平衡，我們認為128～256維是一個較合適的維度區(qū)間。

4 結(jié)束語

本文中，針對學術(shù)合作者推薦問題，我們設計了一種基于負采樣技術(shù)的矩陣分解嵌入模型NEG-MF，并將該模型生成的嵌入用于學術(shù)合作推薦問題。實驗結(jié)果表明，相比較傳統(tǒng)的基線推薦算法，NEG-MF由于引入了有策略性的負采樣技術(shù)，而使生成的嵌入質(zhì)量有很大的提升，其推薦性能超越了已有的基線方法。

未來，我們的研究方向主要有三個方面：①將模型擴大到異質(zhì)網(wǎng)絡嵌入的范疇;②在矩陣分解嵌入模型中引入對屬性信息的考慮，增強模型的建模能力;③考慮將模型擴展到動態(tài)網(wǎng)絡的范疇，設計出歸納式模型。

參考文獻（References）：

[1] William L. Hamilton， Rex Ying， Jure Leskovec. Represen-tation Learning on Graphs： Methods and Applications. IEEE Data Engineering Bulletin，2017.40（3）：52-74

[2] Tomas Mikolov， IlyaSutskever， Chen Kai， et.al. Neural Information Processing Systems， Lake Tahoe， Nevada， United States，2013.

[3] Omer Levy， YoavColdberg. Neural Word Embedding as Implicit Matrix Factorization.NIPS， 2014.

[4] Amr Ahmed， Nino Shervashidze， Shravan Narayanamur-thy.Distributed Large-scale Natural Graph Factorization.WWW， Rio de Janeiro， Brazil，2003.

[5] MikhaiBelkin， ParthaNiyogi. LaplacianEigenmaps and Spectral Techniques for Embedding and Clustering.NIPS，2001：585-591

[6] Cao Shaosheng， Lu Wei， XuQiongkai. GraRep： Learning Graph Representations with Global Structural Information. CIKM， Melbourne， Australia， 2015.

[7] MingdongOu， Peng Cui， Jian Pei， etc.Asymmetric Transitivity Preserving Graph Embedding. KDD，2016.

[8] Jian Tang， MengQu， Minzhe Wang， etc. LINE： Large-scale Information Network Embedding. WWW，2015.

[9] Bryan Perozzi， Rami AI-Rfou， Steven Skiena.DeepWalk：Online Learning of Social Representations. KDD， New York， NY， USA，2014.

[10] Aditya Grover，Jure Leskovec.Node2vec：Scalable Feature Learning for Networks. KDD， San Francisco， CA， USA，2016.

[11] Wang Daixin， Cui Peng， Zhu Wenwu. Structural Deep Network Embedding. KDD， San Francisco， CA， USA，2016.

[12] Shaosheng Cao， Wei Lu， QiongkaiXu. Deep Neural Networks for Learning Graph Representations. AAAI，2016：1145-1152

[13] Thomas N. Kips， Max Welling.Semi-Supervised Classification with Graph Convolutional Networks.5th International Conference on Learning Representations， ICLR 2017， Toulon， France，2017.

[14] William L. Hamilton， Rex Ying， Jure Leskovec. Inductive Representation Learning on Large Graphs.NIPS， Long Beach， CA， USA， 2017.