趙素芬

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

關鍵詞： 矩陣分解; 圖嵌入; 推薦系統(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 引言

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

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

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

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

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

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

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

1 研究問題定義

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

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

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

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

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

2.1 經典的矩陣分解模型Graph Factorization（GF）

經典的矩陣分解模型GF[4]的編碼函數為直接編碼，即：

2.2 NEG-MF矩陣分解模型

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

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

2.3 關系推薦

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

⑴ 內積函數：[frs，u=zs?zu]

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

⑵ 非線性神經網絡模型：[frs，u=σ（Wzszu+b）]

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

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

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

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

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

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

3 實驗結果

3.1 數據集和預處理

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

3.2 基線方法和評估指標

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

3.3 實驗結果和分析

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

4 結束語

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

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

參考文獻（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.