趙素芬

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

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

中圖分類號(hào)：TP311? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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)。許多應(yīng)用都是定義在圖的基礎(chǔ)上，例如學(xué)術(shù)合作網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、知識(shí)圖譜等等。在基于圖的眾多機(jī)器學(xué)習(xí)問題中，其核心任務(wù)就是找到一種將圖的結(jié)構(gòu)信息和語義信息融合到機(jī)器學(xué)習(xí)任務(wù)的方法，即將網(wǎng)絡(luò)中的節(jié)點(diǎn)、邊或子圖映射到低維的向量空間，并且使得到的特征向量盡可能地保持原有圖結(jié)構(gòu)信息、節(jié)點(diǎn)屬性信息和語義信息等等，即圖嵌入技術(shù)[1]。

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

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

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

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

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

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

1 研究問題定義

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

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

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

從定義1中可以看出，本文要解決的研究問題是多目標(biāo)的。也就是說，模型在為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)生成嵌入的同時(shí)，需要能夠?yàn)樘囟ǖ哪繕?biāo)用戶推薦新的社交關(guān)系。

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

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

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

2.2 NEG-MF矩陣分解模型

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

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

2.3 關(guān)系推薦

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

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

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

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

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

其中，[VL]是帶標(biāo)記的用戶集合;

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

3.2 基線方法和評(píng)估指標(biāo)

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

3.3 實(shí)驗(yàn)結(jié)果和分析

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

4 結(jié)束語

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

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

參考文獻(xiàn)（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.