基于鄰節(jié)點和關系模型優(yōu)化的網絡表示學習

冶忠林 趙海興 張 科 朱 宇 肖玉芝

1(青海師范大學計算機學院 西寧 810008)2(陜西師范大學計算機科學學院 西安 710119)3(藏文信息處理教育部重點實驗室(青海師范大學)西寧 810008)(zhonglin_ye@foxmail.com)

隨著計算機處理性能的提升和網絡數(shù)據(jù)規(guī)模的不斷增長，對網絡數(shù)據(jù)挖掘的重視程度也越來越高.網絡數(shù)據(jù)挖掘不僅可以挖掘出隱藏在數(shù)據(jù)之下的真實價值，更可以推動改變現(xiàn)實生活的進程.網絡數(shù)據(jù)挖掘主要面向對象為各類現(xiàn)實生活中的數(shù)據(jù)網絡，例如：社交網絡、引文網絡、博客網絡和通信網絡等.這些網絡統(tǒng)稱為信息網絡，且具有規(guī)模大、數(shù)據(jù)雜、噪音多等特點[1].目前，信息網絡的數(shù)據(jù)挖掘是研究的熱點和前沿，而深度學習、終生學習、強化學習等技術的提出更是將信息網絡的數(shù)據(jù)挖掘引入了更深層次的研究范疇.網絡數(shù)據(jù)挖掘具有重要的意義.例如在社交網絡中，通過挖掘好友出行記錄和文本內容可以預測游客未來出行安排，該預測結果可幫助旅游公司更加精準地推薦旅游服務信息.而信息網絡與自然語言處理結合進行產品和服務的推薦是目前挖掘數(shù)據(jù)挖掘最有價值的應用.單純地使用網絡結構數(shù)據(jù)或者使用文本信息進行數(shù)據(jù)挖掘，則難以完全反映出真實網絡的特征.因此，將網絡結構特征和文本特征進行聯(lián)合的學習和預測是數(shù)據(jù)挖掘致力于解決的難題.

信息網絡數(shù)據(jù)挖掘首先需要面對的難題是如何恰當?shù)乇硎揪W絡數(shù)據(jù).如果僅考慮網絡的結構特征，則可以使用網絡的鄰接矩陣.如果僅考慮網絡節(jié)點的文本特征，則可以將文本轉化為共現(xiàn)矩陣.如果同時考慮網絡的結構特征和網絡節(jié)點的文本特征，則可以將2個矩陣進行列拼接或者降維后再拼接.這種簡單的矩陣拼接雖然包含了2種不同數(shù)據(jù)的特征，但是卻沒有充分地考慮2種數(shù)據(jù)之間的關系，即關系被忽略.不論何種處理方式，矩陣的運算會導致模型的訓練產生較高的計算復雜度，另外，在大規(guī)模的網絡數(shù)據(jù)挖掘任務中也不具有可行性.

網絡表示學習算法對上述任務提出了可行的解決方案.網絡表示學習通過神經網絡對網絡節(jié)點之間的結構進行編碼，能夠處理大規(guī)模網絡結構特征編碼任務.其中最經典的算法為DeepWalk[2]算法，之后基于DeepWalk算法和思路提出了各種改進算法.然而現(xiàn)有的基于神經網絡的表示學習算法將當前節(jié)點的所有上下文節(jié)點平等對待，使得在上下文窗口中的節(jié)點對當前中心節(jié)點具有同等地位的影響，即忽略了上下文節(jié)點的位置信息.例如在神經網絡模型中當前窗口大小設置為5時，則當前節(jié)點前后的各2個節(jié)點作為其上下文節(jié)點.在神經網絡訓練過程中，上下文節(jié)點對(n-2,n0)，(n-1,n0)，(n0,n1)，(n0,n2)被輸入到神經網絡模型中通過節(jié)點對共現(xiàn)不斷地調整其向量中的元素值.該過程使得常出現(xiàn)于節(jié)點對中的節(jié)點在向量表示空間中擁有更近的空間表示距離，未出現(xiàn)于節(jié)點對中的節(jié)點在向量表示空間中具有更遠的空間表示距離.但是，該訓練過程并未考慮n-2，n-1，n1，n2與n0之間的距離.此時模型采用的是上下文結構無關性假設，采用這個假設的目的是為了加速模型訓練速度.在文獻[3-4]中已經驗證了當窗口大小設置為5時，上下文對當前元素的影響達到最大.過大的窗口和過小的窗口都會影響模型的泛化和學習能力.因此，本文在采用神經網絡模型訓練網絡表示的過程中，首次對網絡采樣的上下文節(jié)點對進行深入的優(yōu)化，即在上下文窗口內對當前節(jié)點的鄰居節(jié)點進行優(yōu)化.本文同樣設置神經網絡采樣上下文節(jié)點的窗口大小為5，此時n0的上下文節(jié)點為n-2，n-1，n1和n2.n-1，n1與n0之間的距離大于n-2和n2與n0之間的距離.因此，訓練所得的網絡表示中，n-1和n1的網絡表示比n-2和n2的網絡表示在向量空間中與n0的網絡表示具有更近的空間距離.為了實現(xiàn)該目標，本文優(yōu)化了當前節(jié)點的1階鄰節(jié)點，即優(yōu)化了n-1，n1對n0的學習過程.2階鄰居節(jié)點n-2，n2并未做任何處理.因為，優(yōu)化了n-1，n1與n0之間的學習強度，則同時自然地降低了n-2，n2與n0之間學習強度.對于n0，最終的結果是n-1和n1被訓練出了更近的位置關系，n-2和n2被訓練出了較遠的位置關系.本文對1階鄰節(jié)點所采用的優(yōu)化過程不同于node2Vec[5]和Walklets[6]，這2類算法采用通過改變隨機游走策略的方法改變神經網絡的輸入.而本文并未改變神經網絡的輸入，而是在神經網絡訓練的過程中優(yōu)化隨機游走序列中1階鄰節(jié)點對當前節(jié)點的貢獻.

另外，現(xiàn)有的網絡表示學習算法通常將節(jié)點文本作為特殊的節(jié)點或使用另外一個神經網絡訓練文本向量.例如TADW[7](text-associated deep walk)將網絡節(jié)點的文本內容轉化為詞共現(xiàn)矩陣，之后使用降維方法得到文本的低維度特征.為了將文本特征和網絡結構特征有效地融合，TADW引入了誘導矩陣補全算法[8]，該算法將網絡結構特征作為待分解的目標特征矩陣，同時將文本特征作為目標矩陣的輔助分解矩陣.TriDNR[9]使用第1個3層神經網絡建模節(jié)點與節(jié)點之間的關系，并使用第2個3層的神經網絡建模節(jié)點與其文本中的詞語之間的關系.TriDNR同樣使用第2個3層神經網絡建模標簽類別與文本中詞語之間的關系.CENE[10]仍然采用DeepWalk[2,11-12]建模節(jié)點與節(jié)點之間的關系，并使用循環(huán)神經網絡(recurrent neural network,RNN)和雙向循環(huán)神經網絡(bidirectional recurrent neural network,BiRNN)建模節(jié)點與文本內容之間的關系.TADW和CENE方法在構建文本特征時均采用了獨立于建模節(jié)點關系之外的策略，TriDNR采用了將文本中的詞語作為特殊的網絡節(jié)點的策略.這3類方法在網絡表示學習過程中采用了不同的策略建模節(jié)點與節(jié)點、節(jié)點與文本內容之間的關系.因此，本文在以上網絡表示學習融入文本特征的研究基礎上，引入了知識表示學習中的關系模型.利用關系模型可以在建模節(jié)點與節(jié)點關系的同時考慮節(jié)點文本之間的關系類型.為了實現(xiàn)該目標，本文引入了節(jié)點三元組的概念.而知識三元組(subject,predict,object)[13]常被用來表示知識及其關系，并在知識庫中被大量應用.在關系模型中，知識被定義為關系三元組(h,r,t)[14]的形式.本文采用關系三元組(h,r,t)定義節(jié)點與節(jié)點關于文本的關系.h項和t項表示頭節(jié)點和尾節(jié)點，r表示節(jié)點與節(jié)點之間在文本上擁有的共現(xiàn)詞語，即2個節(jié)點的文本特征中含有共同的詞語則表示2個節(jié)點之間具有了文本關聯(lián)性.本文并不采用單獨的關系模型建模節(jié)點與文本之間的關系，而是采用統(tǒng)一的目標函數(shù)將節(jié)點關系建模與節(jié)點與文本關系建模融合在一起進行訓練，這樣處理既可以保留節(jié)點關系建模過程，又可以引入節(jié)點與文本內容建模對節(jié)點關系建模的指導和影響.

以上過程詳細討論了優(yōu)化鄰節(jié)點對網絡表示學習過程的影響，又討論了引入關系模型建模對建模節(jié)點與文本之間的關聯(lián)關系的意義，從而強化網絡表示學習過程.這2個部分可單獨建模和學習，驗證其對網絡表示學習的影響.為了學習得到更加穩(wěn)健的網絡表示，這2個部分可進行聯(lián)合學習，從而提出了一個統(tǒng)一的聯(lián)合學習框架.而本文提出的NRNR算法正是為了解決以上3個問題而提出.本文通過3個真實的引文網絡數(shù)據(jù)集驗證了其有效性和魯棒性.

1 相關工作

表示學習又被稱為嵌入學習，而Bengio等人[15]于2003年首次提出了“Word Embedding”一詞.隨后，Bengio等人[16]在2013年提出了一種基于深度神經網絡的表示學習算法，但是該算法受限于計算機計算能力的限制并沒有得到重視.而表示學習真正地受到科研人員的重視是在Mikolov 等人[3-4]與2013年提出了Word2Vec算法之后.Word2Vec使用窗口獲取當前詞語的上下文節(jié)點對，然后將節(jié)點對輸入到一個淺層的3層神經網絡中，基于節(jié)點對的共現(xiàn)不斷地調整詞語之間的表示向量.Word2Vec算法被廣泛地應用于各類自然語言處理任務[17-20].2014年Perozzi 等人[2]基于Word2Vec算法提出了DeepWalk算法.DeepWalk在語言模型中引入了隨機游走的采樣方法，通過隨機游走粒子在網絡上的游走模擬語言模型中的句子，底層同樣采用Word2Vec所采用的3層神經網絡模型.DeepWalk被廣泛應用于網絡節(jié)點分類[11-12]、鏈路預測[21-22]、推薦系統(tǒng)[23]和可視化[24]等任務中.

DeepWalk為大規(guī)模網絡表示學習任務提供了一種高效的解決方法，但是因其模型簡單，在某些任務中效果并沒有傳統(tǒng)的方法好，因此基于DeepWalk提出了各類網絡表示學習的改進模型.例如node2Vec[5]和Walklets[6]改進了網絡表示學習中的隨機游走過程.LINE[25]引入1階相似度和高階相似度對大規(guī)模網絡進行表示學習.NEU[26](net-work embedding update)和GraRep[27]提出了高階逼近的網絡表示學習.TADW[7]僅引入誘導矩陣補全算法[8]將網絡節(jié)點的文本特征嵌入到網絡表示學習中.DDRW[28](discriminative deep random walk)，MMDW[29](max-margin deepwalk)，TLINE[30]，GENE[31](group enhanced network embedding)和SemiNE[32](semi-supervised network embedding)引入了網絡節(jié)點的標簽類別信息約束網絡表示學習模型.TriDNR[9](tri-party deep network represen-tation)，LDE[33](linked document embedding)，DMF[34](discriminative matrix factorization)，Planetoid[35](predicting labels and neighbors with embeddings transductively or inductively from data)，LANE[36](label informed attributed network embedding)同時引入了網絡節(jié)點的文本內容和節(jié)點的標簽類別約束網絡表示學習模型.針對動態(tài)網絡和超網絡等特殊的網絡結構，也提出了相應的網絡表示學習算法，例如DynamicTriad[37](dynamic triadic)，DepthLG[38]，DHNE[39](deep hyper-network embedding)等.另外，生成對抗網絡(generative adversarial network,GAN)[40]也被引入到網絡表示學習中，例如ANE[41](adversarial network embedding)，GraphGAN[42]，NetGAN[43]等.

以上內容詳細地討論了網絡表示學習的起源，描述和解釋了網絡表示學習中的經典算法，并介紹了最新的一些網絡表示學習算法，例如特殊結構的網絡表示學習和生成對抗式的網絡表示學習算法等.但是，以上部分算法在基于神經網絡訓練表示學習模型時，并未考慮不同位置的上下文節(jié)點對中心節(jié)點的影響，也未考慮使用關系模型構建節(jié)點對之間的關系.因此，本文提出的NRNR算法正是為了優(yōu)化以上2個目標而提出.因為，在上下文窗口中，不同位置的節(jié)點對中心節(jié)點的影響力是不相同的.應該使中心節(jié)點的1階鄰居節(jié)點比2階鄰居節(jié)點擁有更大的影響力.另外，通過矩陣分解或者異構網絡將文本特征嵌入到網絡表示具有較大的計算開銷，而本文首次采用關系模型機制將及節(jié)點之間的多元關系嵌入到網絡表示，其計算開銷較小且擁有統(tǒng)一的目標函數(shù)，且在多元關系向量建模過程中優(yōu)化具有相同關系節(jié)點對之間的表示向量學習過程.

2 算法設計

2.1 定 義

2.2 關系模型

關系模型最經典的算法為TransE(translating embeddings)，該算法于2013年被Bordes等人[14]在NIPS(neural information processing systems)會議上提出.TransE被提出主要是用來解決大規(guī)模知識庫中知識的表征學習[44]，即研究如何將知識嵌入到一個低維度的向量空間中，其目的是建模多關系數(shù)據(jù).現(xiàn)有的知識庫有OpenCyc(open cycorp)，WordNet，F(xiàn)reebase，Dbpedia[13]等.這些知識庫中已有大量的知識，但是這些知識都是基于現(xiàn)有的知識抽取而得，而研究基于知識庫的知識推理就需要研究如何對知識進行表征，進而從現(xiàn)有的知識中推導出大量的未知知識.

TransE是基于翻譯機制的知識嵌入模型，其將關系三元組(h，r，t)中的關系r作為實體h到實體t的翻譯，并通過關系三元組的不斷涌現(xiàn)從而持續(xù)地調整實體h、關系r和實體t的表示向量，使實體h與關系r的和向量xh+xr盡可能與實體t的向量xt具有更近的空間距離，即模型訓練的目標為xh+xr≈xt基于該目標，TransE的目標函數(shù)為

(1)

其中：

S′(h,r,t)={(h′,r,t)|h′∈E}∪
{(h,r,t′)|t′∈E},

(2)

(3)

S為三元組(h,r,t)的集合,S′為三元組(h,r,t)的負采樣集合，即存在于知識庫中的(h,r,t)為正樣本，不存在于知識庫中的(h,r,t)為負樣本.λ>0為間隔距離超參；x>0時[x]+=x，x≤0時[x]+=0.

本文使用節(jié)點關系三元組作為關系模型的輸入.在構建節(jié)點關系三元組時，本文僅考慮了一元關系.一元關系是2個節(jié)點的文本中含有一個共同詞語時，則將該詞語作為2個節(jié)點的關系.例如，節(jié)點1的文本標題為“Neural Network for Pattern Recog-nition”，節(jié)點2的文本標題為“Neural Network:A Comprehensive Foundation”.則可以構建的節(jié)點三元組為(Node1，neural,Node2)和(Node1,network,Node2).這種類型的節(jié)點三元組被稱為含一元關系的節(jié)點三元組.

2.3 使用負采樣的CBOW模型

Word2Vec提供了2種模型：CBOW和Skip-Gram，并提供了2種優(yōu)化方法：負采樣和層次化的Softmax[3-4].DeepWalk是基于Word2Vec模型提出的大規(guī)模網絡表示學習算法[2]，因此，DeepWalk完全繼承了Word2Vec提供的訓練模型和優(yōu)化方法.CBOW模型訓練速度快，但是精度略劣于Skip-Gram.負采樣優(yōu)化方法由于不用構建huffman樹，故優(yōu)化速度也優(yōu)于層次化的Softmax.因此，本文采用負采樣優(yōu)化的CBOW訓練DeepWalk模型，并將1階鄰節(jié)點優(yōu)化的目標函數(shù)和關系模型的目標函數(shù)融入到DeepWalk的目標函數(shù)中.

對于當前中心節(jié)點v,其上下文定義為Context(v).負采樣集合定義為NEG(v),且NEG(v)≠?.對于?u∈D,D表示節(jié)點集合.定義節(jié)點u的標簽為

(4)

即正樣本的標簽為1，負樣本的標簽為0.

在負采樣的過程中，當前中心節(jié)點為正樣本，其他所有節(jié)點為負樣本，然后將所有概率相乘使其最大化.對于單個樣本(v,Context(v))有:

(5)

則所有樣本的概率之和為

(6)

xv是上下文Context(v)中每個節(jié)點的向量之和,θξ是節(jié)點ξ的待訓練向量，式(6)可被簡化為

(7)

因此，函數(shù)g(v)通過式(5)和式(7)生成為

(8)

綜上，基于語料C,負采樣優(yōu)化的CBOW的整體優(yōu)化目標函數(shù)可定義為

(9)

對式(9)取對數(shù)操作，則整體的目標函數(shù)可修改為

(10)

在神經網絡模型中，目標函數(shù)一般取對數(shù)似然函數(shù)，且對數(shù)的底通常省略，因為在最終的參數(shù)更新公式中，對數(shù)形式會被轉化為非對數(shù)形式.從式(10)抽取出基于負采樣優(yōu)化的CBOW模型的目標函數(shù)最常用的形式為

(11)

其中:

(12)

式(11)中，C為節(jié)點序列語料，使用隨機梯度上升法獲得式(10)中變量θξ的更新公式為

θξ

(13)

c(v)c(v)+

(14)

式(13)中μ表示學習率,xv為Context(v)中每個節(jié)點的表示向量之和.通過xv可以獲得Context(v)中每個節(jié)點的表示向量更新方式，如式(14)所示.

2.4 NRNR建模

本文提出的NRNR算法旨在于解決如何使用1階鄰節(jié)點優(yōu)化網絡表示學習過程，同時解決如何采用網絡節(jié)點的文本內容優(yōu)化網絡表示學習過程，為了適應大規(guī)模網絡表示學習任務要求，需要提出一種簡單高效的聯(lián)合學習模型.為了實現(xiàn)該方案，本文提出了一種基于神經網絡的網絡表示聯(lián)合學習框架，該框架由3個部分構成，分別為1階鄰節(jié)點優(yōu)化部分、網絡節(jié)點關系建模部分和節(jié)點與文本關系模型構建部分.具體如圖1所示:

Fig.1 NRNR algorithm framework圖1 NRNR 算法框架

如圖1所示，Nvi表示當前中心節(jié)點vi的1階鄰節(jié)點集合，Rvi表示當前中心節(jié)點vi的節(jié)點三元組集合.在Word2Vec中，CBOW模型是通過上下文詞語出現(xiàn)的概率去預測當前中心詞出現(xiàn)的概率.而DeepWalk算法是基于Word2Vec算法的改進，因此，底層同樣可以采用CBOW模型學習節(jié)點與節(jié)點之間的關系.例如對于當前中心節(jié)點vi，CBOW模型通過其在隨機游走序列中的前面2個節(jié)點vi-2和vi-1以及其后面2個節(jié)點vi+1和vi+2來預測當前中心節(jié)點vi出現(xiàn)的概率.CBOW模型通過不斷地調整網絡表示向量中的值，使得具有連邊的節(jié)點對之間具有更近的表示向量空間距離，使得具有多跳邊或者沒有邊的節(jié)點對之間具有較遠的表示向量空間距離.本文提出的NRNR算法在該調節(jié)的過程中添加了一些約束，即使得當前中心節(jié)點vi的1階鄰居節(jié)點vi-1和vi+1比2階鄰居節(jié)點vi-2和vi+2在向量表示空間中與vi具有較近的空間距離.在圖1中，vj∈Nvi=(vi-1,vi+1).另外，NRNR算法添加了文本特征，該文本特征是將具有共同出現(xiàn)詞語的節(jié)點對之間轉化為節(jié)點三元組關系.NRNR算法采用多源關系建模思想優(yōu)化了網絡表示向量學習過程，即使得具有三元組關系約束的節(jié)點對比沒有三元組關系約束的節(jié)點對在網絡表示向量空間中具有更近的空間距離.

在NRNR算法中，以上過程可被認為是3個CBOW模型的疊加.另外，CBOW模型與1階鄰節(jié)點優(yōu)化過程共享一份節(jié)點向量，同時，與關系模型優(yōu)化過程也共享1份節(jié)點向量.因此，本文提出的NRNR通過共享向量來獲得和交換彼此的特征信息，使得NRNR算法在建模學習過程中能夠從1階鄰居節(jié)點和節(jié)點三元組中獲取有價值的特征信息，從而使獲得的網絡表示能夠在各類任務中具有更強的泛化能力.另外，共享節(jié)點向量為聯(lián)合學習模型提供了解決思路.

為了將1階鄰節(jié)點信息融入到網絡表示學習模型中，本文提出的目標函數(shù)為

(15)

本文中，NRNR_N算法的學習目標是最大化式(15)，因此，本文采用了類似于Word2Vec[3-4]所采用的隨機梯度上升法獲得每個參數(shù)的更新公式.其中，gCv(v)與gNv(v)的具有相同的形式.式(15)的v即為圖1中的vi，因為我們在式(15)中最外層的求和符號下標設定為v∈C，如果將此下標設置為1≤i≤|C|，則式(15)中的v全部應替換為vi.式(15)的左邊項為CBOW的目標函數(shù)，其參數(shù)更新見式(13)(14).式(15)右邊項為本文添加的約束項，其本質為一個CBOW模型，即再一次使用1階鄰居節(jié)點優(yōu)化網絡表示學習模型，故優(yōu)化求解方法與CBOW完全相同.首先我們設求偏導的表達式為

(16)

令:

(17)

式(16)中，對于當前節(jié)點的1階鄰居節(jié)點集合而言，目標節(jié)點是正樣本，而該集合之外的所有節(jié)點均為負樣本.然后采用f1分別對θξ和xu求偏導.最終求得式(17)中θξ和1階鄰居節(jié)點n(u)的更新公式為

θξ

(18)

n(u)n(u)+μ·

(19)

本文中通過權重α控制1階鄰居的權重，因此權重α需要乘到式(18)(19)中的μ之前.另外，xu為當前節(jié)點的1階鄰居節(jié)點的表示向量之和，n(u)為其中每個1階鄰居節(jié)點的表示向量.

NRNR然引入了關系模型，但是并未使用TransE[14]算法建模節(jié)點三元組，如果使用TransE模型，需要將TransE的目標函數(shù)融入到DeepWalk算法的目標函數(shù)中.在TransE算法中，三元組(h,r,v)滿足xh+xr≈xv.該式子是TransE算法的訓練目標，即如果節(jié)點v和節(jié)點h之間存在關系r，則讓節(jié)點h和節(jié)點r的向量之和盡量靠近節(jié)點v的表示向量，否則應該遠離v的表示向量.本文將關系模型的思想引入到NRNR算法中，實現(xiàn)了在建模網絡節(jié)點對之間關系的同時建模了節(jié)點三元組之間的關系.基于此，本文提出了一種基于CBOW的關系模型構建方法NRNR_R.其目標函數(shù)為

(20)

在式(20)中，Rv表示構成v的關系三元組(h,r,v)的集合.式(20)中gh+r(v)可被認為是通過節(jié)點h之間的關系r來預測節(jié)點v出現(xiàn)的概率.式(20)類似于式(15)，均可被認為是2個CBOW模型的疊加，左邊的第1個CBOW模型的更新公式可見式(13)(14).右邊第2項我們設:

(21)

令：

(22)

又令：

(23)

NEG(v)進行負采樣時，客觀存在的三元組設置為正樣本，而非客觀存在的三元組設置為負樣本.然后用函數(shù)f2對θξ求偏導數(shù)，最終得到θξ的更新公式為

θξ

(24)

由于xh+r=xh+xr，因此，需要單獨對xh和xr求偏導，得到最終的更新公式為

xhxh+μ·

(25)

xrxr+μ·

(26)

本文中通過權重β控制三元組的權重，因此，權重β需要乘到式(24)～(26)中的μ之前.

(27)

式(27)可被認為是3個CBOW模型的疊加，因此，每個部分的參數(shù)更新即為整個表達式的參數(shù)更新公式.故式(27)的參數(shù)更新公式由式(13)(14)(18)(19)(24)～(26)組成.另外，也需要在參數(shù)更新公式中添加權重α和β.為了更加詳盡地介紹本文提出的NRNR算法的具體流程，我們給出了算法偽代碼：

算法1.NRNR.

輸入:圖G(V,E)、節(jié)點向量大小d、每個節(jié)點的隨機游走數(shù)量wp、隨機游走長度wl、節(jié)點三元組R、節(jié)點三元組權重β,1階鄰居節(jié)點權重α；

輸出:節(jié)點向量V.

/*獲取所有節(jié)點的隨機游走序列*/

① fori=0 towpdo

②O←Shuffle(V);

③ forv∈Odo

④C←WalkSeqAppend(G,v,wl);

⑤ end for

⑥ end for

/*初始化所有參數(shù)*/

⑦vertex_size←GetVocabSize(C);

⑧relation_num←GetRelationNum(R);

⑨V←InitVector(vertex_size,d);

⑩θ←InitVector(vertex_size,d);

/*對每一個節(jié)點作如下訓練和優(yōu)化*/

/*訓練原始的負采樣優(yōu)化的CBOW模型*/

/*根據(jù)式(13)(14)更新CBOW模型的參數(shù)*/

/*更新上下文節(jié)點的表示向量*/

/*采用1階鄰居節(jié)點優(yōu)化網絡表示學習模型*/

/*根據(jù)式(18)(19)更新模型參數(shù)*/

/*采用節(jié)點三元組優(yōu)化網絡表示學習模型*/

/*獲取所有的節(jié)點三元組*/

/*根據(jù)式(24)～(16)更新模型參數(shù)*/

3 實驗與分析

3.1 數(shù)據(jù)集描述

本文使用Citeseer(M10)，DBLP(V4)數(shù)據(jù)集驗證本文提出算法的可行性.為了驗證在稠密網絡中的可行性，本文基于DBLP(V4)構造了一個高平均度的網絡Shifted DBLP(SDBLP).在SDBLP中刪除了所有孤立節(jié)點，并且刪除了節(jié)點連邊數(shù)少于或等于2的所有節(jié)點及其連邊.3個數(shù)據(jù)集的具體屬性描述如表1所示：

Table 1 Property Description on Citeseer,DBLP and SDBLP Datasets表1 Citeseer,DBLP和SDBLP數(shù)據(jù)集屬性描述

如表1所示，列2和列3分別為原始數(shù)據(jù)集中的節(jié)點數(shù)量和連邊數(shù)量.列4為網絡中孤立節(jié)點的數(shù)量.經過刪除孤立節(jié)點等操作，剩余的節(jié)點數(shù)量和連邊數(shù)量如列5和列6所示.最終刪除后的網絡中，Citeseer，DBLP，SDBLP數(shù)據(jù)集中節(jié)點個數(shù)分別為4610，17725，3119，網絡平均度分別為2.57，11.936，25.339.可以發(fā)現(xiàn)，網絡的密度越來越高.本文使用Citeseer，DBLP，SDBLP模擬3類屬性不同的網絡數(shù)據(jù)集，從而驗證本文提出算法的泛化能力.

3.2 對比算法

1)DeepWalk.DeepWalk算法是基于神經網絡的最經典的網絡表示學習算法，后續(xù)的諸多網絡表示學習算法均是基于DeepWalk算法而提出.DeepWalk起源于Word2Vec算法.DeepWalk可使用CBOW和Skip-Gram兩種模型訓練基于神經網絡的表示學習模型，另可采用負采樣和層次化的Softmax加速網絡訓練過程，CBOW具有訓練速度快的特點，Skip-Gram具有精度高的特點.在本文中，使用CBOW和負采樣訓練DeepWalk.

2)LINE.Tang等人[25]提出了一種大規(guī)模網絡表示學習算法，該算法通過部分舍棄精度的方式追求在超大規(guī)模網絡中編碼網絡結構成為低維度的網絡表示.因此，LINE的訓練速度非常快，但是精度不高，尤其在稀疏網絡中網絡節(jié)點分類性能較差.這種速度的提升主要來自于LINE僅考慮網絡的1階相似度1st LINE或者2階相似度2nd LINE.本文中使用2nd LINE訓練網絡表示.

3)node2Vec.node2Vec是基于DeepWalk算法而提出的一種網絡表示學習算法.DeepWalk的隨機游走策略是完全的隨機，而node2Vec改進了Deep-Walk的隨機游走策略，即采用了圖論中的廣度優(yōu)先搜索策略和深度優(yōu)先搜索策略來采樣節(jié)點，廣度優(yōu)先搜索控制網絡的全局宏觀視圖特征，深度優(yōu)先搜索控制網絡的局部微觀視圖特征.

4)GraRep.GraRep是一種基于矩陣分解的高階網絡表示學習算法，在該算法中，定義1階的概率轉移矩陣為A=D-1S，其中S為鄰接矩陣,D為對角矩陣,則第k階的網絡結構特征定義為Ak.然后使用SVD去分解每一階的網絡結構特征，最后拼接所有階的表示向量.在本文中，設置k=3.

6)DeepWalk+TF.將DeepWalk和TF生成的網絡表示向量通過列向量擴充的形式拼接在一起.

7)MFDW.網絡表示學習算法DeepWalk被證明是分解矩陣M=(A+A2)/2，本文使用SVD算法去分解矩陣M，并使用W=U·S0.5作為網絡的表示向量.

8)TADW.網絡表示學習算法DeepWalk被證明是分解矩陣M=(A+A2)/2，其中A為鄰接矩陣.TADW并非使用SVD去分解矩陣M，而是引入了誘導矩陣補全算法去分解矩陣M.因為誘導矩陣補全算法可提供一個外部矩陣輔助分解矩陣M的功能.

9)STADW.該算法是TADW算法的簡化形式，在TADW算法中刪除了對文本特征的優(yōu)化處理.

3.3 實驗設置

本文使用網絡節(jié)點分類任務評估本文提出的算法與本文引入的對比算法.本文使用Liblinear[45]作為基線分類器.為了驗證算法的泛化能力，本文將訓練集設置為0.1～0.9，共9個比例的訓練集，將剩余的網絡節(jié)點作為測試集.網絡表示學習算法得到的網絡表示向量統(tǒng)一設置為100維.另外，設置隨機游走長度為40，隨機游走個數(shù)為10條，窗口大小為5，負采樣為5，最小節(jié)點頻度為5，神經網絡的學習率為0.05，1階鄰居節(jié)點的權重為0.7，節(jié)點三元組的權重為0.3.本文中所有實驗均重復10次取平均值作為最終的結果.

3.4 實驗結果分析

本文使用Citeseer，DBLP，SDBLP等真實的網絡數(shù)據(jù)集作為評估數(shù)據(jù)集.并從數(shù)據(jù)集中抽取10%～90%的數(shù)據(jù)作為訓練集，剩余的數(shù)據(jù)作為測試集.表2～4列出了本文引入的對比算法和本文提出的算法在3個數(shù)據(jù)集和9種訓練集比例下的網絡節(jié)點分類準確率.

Table 2 Accuracy of Vertex Classification on Citeseer表2 Citeseer數(shù)據(jù)集上的節(jié)點分類準確率

Table 3 Accuracy of Vertex Classification on DBLP表3 DBLP數(shù)據(jù)集上的節(jié)點分類準確率

Table 4 Accuracy of Vertex Classification on SDBLP表4 SDBLP數(shù)據(jù)集上的節(jié)點分類準確率

如表2所示，LINE算法的網絡節(jié)點分類性能最差.MFDW為DeepWalk的矩陣分解形式，其在各比例的訓練集條件下獲得的網絡節(jié)點分類性能均優(yōu)于DeepWalk算法.DeepWalk和node2Vec算法的底層均為一個3層的淺層神經網絡算法，不同的是上層的隨機游走序列獲取方式不同.從實驗結果可知，node2Vec算法的網絡節(jié)點分類性能優(yōu)于DeepWalk算法.在Citeseer數(shù)據(jù)集上，網絡節(jié)點的文本特征在節(jié)點分類任務中其性能優(yōu)于DeepWalk算法.因此通過簡單地拼接策略和類似于TADW算法融入文本特征進入網絡表示，其獲得的網絡節(jié)點分類性能均得到了極大地改善.STADW中刪除了對文本特征的優(yōu)化，因此其性能劣于TADW.本文提出的NRNR_N優(yōu)化了隨機游走過程中的1階鄰居節(jié)點，其性能優(yōu)于DeepWalk算法.本文提出的NRNR_R通過節(jié)點三元組的形式將文本特征融入到網絡表示中，其性能優(yōu)于TADW算法.本文提出的NRNR_NR將NRNR_N和NRNR_R的思路融合在一起，即同時將1階鄰居節(jié)點的優(yōu)化和文本特征融入到網絡表示中，其獲得的性能優(yōu)于NRNR_N和NRNR_R，也均優(yōu)于本文中提出的其他對比算法.

如表3所示，在DBLP稠密網絡上，DeepWalk的網絡節(jié)點分類性能略劣于LINE和GraRep.由于稠密網絡中存在大量的連邊，因此，網絡節(jié)點之間的結構關系可得到充分地挖掘，node2Vec，DeepWalk等基于神經網絡的網絡表示學習算法能夠得到充分地訓練.在該數(shù)據(jù)集中，同樣存在基于DeepWalk的矩陣分解MFDW算法其分類性能優(yōu)于DeepWalk的現(xiàn)象.隨著訓練集比例的提高，文本特征TF的網絡節(jié)點分類性能越來越優(yōu)于DeepWalk.但是通將TF的特征向量與DeepWalk的表示向量進行簡單拼接，其獲得的性能卻劣于文本特征的性能.通過矩陣分解思想融入文本特征(TADW)，其網絡表示分類性能遠優(yōu)于DeepWalk，node2Vec，GraRep等網絡表示學習算法.由于是稠密網絡，因此優(yōu)化1階鄰節(jié)點得到的NRNR_N算法其分類性能略優(yōu)于DeepWalk.NRNR_R引入知識表示的思想進入網絡表示，從而將文本特征以三元組約束的形式融入到網絡表示中，其分類性能優(yōu)于TADW.NRNR_NR融合了NRNR_N與NRNR_R的學習過程，因此與本文引入的對比算法相比，NRNR_NR獲得了最好的性能.

如表4所示，在SDBLP數(shù)據(jù)集上，基于矩陣分解的網絡表示取得了很好的節(jié)點分類性能，例如，DeepWalk的矩陣分解算法MFDW，在各訓練集比例下，其性能均優(yōu)于基于神經網絡的DeepWalk算法.基于矩陣分解的高階表示學習GraRep算法同樣也獲得了優(yōu)于DeepWalk的性能.基于本文提出的NRNR_N算法優(yōu)化了DeepWalk算法在隨機游走過程中的1階鄰居節(jié)點，因此，其節(jié)點分類性能優(yōu)于DeepWalk.SDBLP數(shù)據(jù)集上，文本特征的節(jié)點分類性能是最差的，因此，將DeepWalk和文本特征的向量簡單拼接后，其性能的提升是非常有限的.TADW通過誘導矩陣補全融入文本特征到網絡表示，NRNR_R通過神經網絡融入文本特征到網絡表示，STADW刪除了TADW中對文本特征的優(yōu)化.通過實驗發(fā)現(xiàn)，在SDBLP數(shù)據(jù)集上，TADW，STADW，NRNR_N在節(jié)點分類任務上的性能幾乎相同.相較于NRNR_N和NRNR_R，NRNR_NR的性能得到了顯著的提升.

在Citeseer和DBLP數(shù)據(jù)集上，NRNR_N算法的網絡節(jié)點分類性能不如NRNR_R和NRNR_NR算法.在Citeseer數(shù)據(jù)集上，NRNR_N算法的平均分類準確率為0.626 3，DeepWalk算法的平均分類準確率為0.612 2.在DBLP數(shù)據(jù)集上，NRNR_N算法的平均分類準確率為0.669 7，DeepWalk算法的平均分類準確率為0.656 5.因此，在Citeseer和DBLP數(shù)據(jù)集上，DeepWalk和NRNR_N算法之間的平均分類準確率提升為2.32%和2.02%.而NRNR_R和NRNR_NR的提升率遠大于該值.主要原因是雖然NRNR_N在網絡表示學習過程中優(yōu)化了1階鄰居節(jié)點，使得1階鄰居節(jié)點與中心節(jié)點之間的關聯(lián)度大于2階鄰居節(jié)點與中心節(jié)點之間的關聯(lián)度.但是使用Citeseer，DBLP，SDBLP數(shù)據(jù)集和網絡節(jié)點分類準確率衡量算法性能時，NRNR_N和DeepWalk算法均能夠較好地識別不同類別節(jié)點內部節(jié)點的標簽，而NRNR_N算法能夠優(yōu)化不同類別之間的邊界節(jié)點被錯誤分類的過程.例如在邊界節(jié)點中2階鄰居節(jié)點是另外一個類別的節(jié)點時，DeepWalk算法會使得該不同類別的節(jié)點與中心節(jié)點之間具有較近的表示向量空間距離，而NRNR_N算法僅優(yōu)化1階鄰居節(jié)點，因此能夠增進1階鄰居節(jié)點與中心節(jié)點之間的表示向量空間距離，從而疏遠了中心節(jié)點與2階鄰居節(jié)點之間的表示向量空間距離，進而避免將不同類別的節(jié)點分類到同一個類別中.在Citeseer和DBLP數(shù)據(jù)集上，僅使用文本特征進行網絡節(jié)點分類，則文本特征的網絡節(jié)點分類性能優(yōu)于DeepWalk算法，因此，NRNR_R引入了外部文本特征后能夠優(yōu)化網絡節(jié)點分類性能，使得NRNR_R的網絡節(jié)點分類性能優(yōu)于NRNR_N和DeepWalk等算法.

本文主要提出了3種網絡表示學習框架：NRNR_N，NRNR_R，NRNR_NR.NRNR_N是對DeepWalk中隨機游走序列中的1階鄰居節(jié)點進行優(yōu)化，NRNR_R基于DeepWalk模型引入文本特征，NRNR_NR是NRNR_N與NRNR_R的融合，TADW通過矩陣分解思想引入網絡節(jié)點的文本特征.因此，為了直觀地展示本文引入的3種模型是否有效，本文圖示化了NRNR_N，NRNR_R，NRNR_NR，DeepWalk，TADW在Citeseer，DBLP，SDBLP上的網絡節(jié)點分類性能，具體結果如圖2所示.

Fig.2 Performance comparisons of five algorithms on three datasets圖2 3種數(shù)據(jù)集上5種算法性能對比圖

如圖2所示，5種算法在Citeseer和DBLP數(shù)據(jù)集上的網絡節(jié)點分類準確率值跨度大于其在SDBLP數(shù)據(jù)集上的值.在SDBLP數(shù)據(jù)集上，5類對比算法的網絡節(jié)點分類準確率呈現(xiàn)出了顯著的上升趨勢.但在Citeseer和DBLP數(shù)據(jù)集上，準確率曲線表現(xiàn)出了比較緩慢的上升趨勢.另外，在這2類數(shù)據(jù)集上，DeepWalk和NRNR_N的準確率曲線與NRNR_R，NRNR_NR，TADW這3條準確率權限之間有著明顯的大跨度.出現(xiàn)這種現(xiàn)象的主要原因是在稀疏網絡上，不同算法之間的獲取的特征差異性較大，如果某種算法能夠獲取較為充分地反映網絡結構的特征，則其網絡分類性能變得越好.且在這類稀疏網絡上，基于聯(lián)合學習的網絡表示學習算法能夠彌補因為邊稀疏而帶來的訓練不充分問題.而在稠密網絡上，不同算法均能從充分地邊連接中獲得有效的網絡結構特征，因此表現(xiàn)出來的分類性能之間的差異性就越小.

基于表2～4和圖2的結果，本文得到4點結論：

1)在Citeseer稀疏網絡上，基于高階表示的GraRep其網絡節(jié)點分類性能不如DeepWalk優(yōu)異，但是在DBLP和SDBLP等稠密網絡數(shù)據(jù)集上，GraRep的網絡節(jié)點分類性能優(yōu)于DeepWalk.該結果表明，在稀疏網絡上，高階的網絡表示學習算法傾向于獲得較差的分類效果.主要是由于網絡稀疏，通過矩陣多次相乘獲得的高階特征無法準確地反映出網絡結構特征.

2)在DBLP和SDBLP等稠密網絡數(shù)據(jù)集上，基于矩陣分解的網絡表示學習算法比基于淺層神經模型的網絡表示學習算法更有效，前者在網絡節(jié)點分類任務中性能稍優(yōu)于后者.但由于矩陣分解效率和復雜度的限制，基于矩陣分解的網絡表示學習算法在大規(guī)模網絡表示學習任務中不可行.主要的原因是，在稠密網絡中，網絡節(jié)點之間的連邊數(shù)較多，基于純結構的隨機游走算法能夠充分地挖掘出節(jié)點所蘊含的網絡結構，因此不同網絡表示學習算法之間的差異性不明顯.假如引入的外部特征噪音較多，反而會使得網絡表示學習的性能受到影響.

3)網絡節(jié)點的文本特征融入方式較多.本文實驗對比了拼接方法、誘導矩陣補全和類知識表示的節(jié)點三元組約束等方法.其中，簡單的向量拼接方法并不能帶來網絡表示性能大幅度的提升.誘導矩陣補全是一種非常有效的文本特征融入框架，在3類真實數(shù)據(jù)集上均獲得了優(yōu)異的網絡表示性能.本文提出的文本特征融入框架克服了矩陣分解的計算限制，采用節(jié)點三元組對DeepWalk訓練過程進行約束，從而使得到的網絡表示中含有語義信息，也使得網絡表示含有更多的信息.

4)在Citeseer等稀疏網絡上，通過優(yōu)化隨機游走過程中一階鄰居節(jié)點，NRNR_N的分類性能優(yōu)于DeepWalk，但是隨著網絡節(jié)點的平均度的增大，這種差異會變得越來越小.例如在DBLP和SDBLP數(shù)據(jù)集上，NRNR_N和DeepWalk之間的分類性能差異變得很小.通過將2種優(yōu)異的網絡表示學習算法融合學習，得到的算法在網絡節(jié)點分類任務中其性能優(yōu)于其中的一種算法，例如本文使用NRNR_NR融合了NRNR_N和NRNR_R這2種算法的改過程，其性能在3類數(shù)據(jù)集上均獲得了優(yōu)于其中一種算法的效果.

3.5 網絡表示可視化

網絡表示可視化的主要目的是查看訓練得到的表示向量能否出現(xiàn)明顯的聚類現(xiàn)象，如果出現(xiàn)了聚類現(xiàn)象，則在網絡節(jié)點分類和鏈路預測等任務中可發(fā)揮出優(yōu)異的性能.聚類現(xiàn)象可被認為是網絡表示是否學習得到了網絡的社團信息.基于網絡表示得到的社團劃分越準確，則在網絡節(jié)點分類任務中具有更好的可靠性.在此實驗中，本文從Citeseer數(shù)據(jù)集中隨機選取了4類節(jié)點，每個類別隨機選取150個節(jié)點.本文使用 t-SNE算法可視化學習得到的網絡表示.具體結果如圖3所示：

Different shapes and colors represent different types of verticesFig.3 The network visualization results of the partial vertices on the Citeseer dataset圖3 網絡部分節(jié)點表示在Citeseer數(shù)據(jù)集上可視化結果

從圖3可以發(fā)現(xiàn)，本文可視化了DeepWalk，LINE，node2Vec與本文提出的3類模型訓練得到的部分網絡表示向量.從表2～4可知，DeepWalk和LINE的網絡表示分類性能較差，因此，這2種算法學習得到的網絡表示向量在可視化任務中也同樣表現(xiàn)出了較差的結果.node2Vec和NRNR_N可視化結果中，僅有2類節(jié)點表現(xiàn)出凌亂的分布，其余2類顏色的節(jié)點具有明顯的聚類邊界.本文提出的NRNR_R和NRNR_NR的可視化結果中，4類節(jié)點的表示向量均展現(xiàn)出了明顯的聚類現(xiàn)象和聚類邊界.該可視化實驗說明，在網絡表示學習任務中，網絡1階鄰居節(jié)點優(yōu)化、網絡節(jié)點文本優(yōu)化或者2種優(yōu)化聯(lián)合學習的策略均能提高網絡表示學習的性能.

3.6 案例研究

在該案例研究中，首先使用“An Evolutionary Algorithm That Constructs Recurrent Neural Networks”作為目標節(jié)點的文本，然后返回與該目標節(jié)點最相似的3個節(jié)點.本實驗通過余弦相似度計算節(jié)點之間的相似度值.

如表5所示，DeepWalk算法基于網絡的結構特征學習網絡表示，未考慮節(jié)點的文本相似性，因此返回的相似節(jié)點中最相關的節(jié)點文本中不含有目標節(jié)點文本中的詞語.TADW和NRNR_NR均考慮了節(jié)點的文本特征和結構特征，因此，返回的相似節(jié)點中，其節(jié)點文本與目標節(jié)點的文本之間均有相同的詞語共現(xiàn).由于不同的算法挖掘網絡節(jié)點之間的不同結構特征，因此返回的最相似節(jié)點的文本可能并不相同.

Table 5 Case Study on Citeseer表5 Citeseer數(shù)據(jù)集上的案例分析

4 總 結

本文首次引入了鄰節(jié)點優(yōu)化策略提升網絡表示學習性能，在窗口大小為5時，當前節(jié)點的1階鄰節(jié)點被優(yōu)化，自然地與2階鄰節(jié)點產生了不同，進而導致一階鄰節(jié)點和2階鄰節(jié)點對當前中心節(jié)點的影響不同.該1階鄰節(jié)點的優(yōu)化過程被認為是為窗口內的上下文節(jié)點賦予不同的位置信息.本文首次引入了關系模型進入網絡表示學習，該方法是一種新穎的文本嵌入網絡表示的方法.不同與TADW和CENE等單獨訓練文本特征的方式，本文提出的NRNR方法在訓練網絡表示學習模型的同時建模了節(jié)點與文本之間的關聯(lián)關系.為了實現(xiàn)該過程，本文進而引入了節(jié)點關系三元組概念，使得節(jié)點之間含有共同詞語的節(jié)點對在向量表示空間中具有更近的網絡表示.本文提出了3個目標函數(shù)，分別討論了1階鄰節(jié)點、節(jié)點三元組與其2者聯(lián)合學習對網絡表示學習性能的影響.實驗結果表明，添加了1階優(yōu)化的網絡表示學習NRNR_N算法在網絡節(jié)點分類任務中其性能優(yōu)于原始的DeepWalk算法.使用關系模型建模節(jié)點與文本內容的NRNR_R算法在網絡節(jié)點分類任務中其性能優(yōu)于TADW算法.如果將NRNR_N和NRNR_R相結合學習，則得到的NRNR_NR算法在網絡節(jié)點分類任務中其性能均優(yōu)于本文提出的各類對比算法.在網絡可視化測試中，本文提出的NRNR_R和NRNR_NR均展示出了明顯的聚類現(xiàn)象，其聚類邊界明顯.因此，本文所做的實驗地驗證了本文提出的NRNR算法具有可行性.在未來研究中將研究如何增大不同社區(qū)或類別的節(jié)點在向量表示空間中的距離.