2021網(wǎng)絡學習綜述

網(wǎng)絡表示學習綜述引言網(wǎng)絡數(shù)據(jù)形式可以自然地表達物體和物體間的聯(lián)系,在我們的日常生活與工作中無處不在.舉例來說Facebook和新浪微博等構成了人與人之間的社交網(wǎng)絡互聯(lián)網(wǎng)上成千上萬個頁面構成了網(wǎng)頁鏈接的網(wǎng)絡;國家城市間的運輸交通構成了物流網(wǎng)絡.由此可見,信息網(wǎng)絡是我們生產(chǎn)生活中最為常見的一種信息載體和形式.信息社會中很多網(wǎng)絡節(jié)點擁有豐富的文本等外部信息,形成典型的復雜信息網(wǎng)絡.基于復雜信息網(wǎng)絡的廣泛存在,對這類網(wǎng)絡信息進行研究與分析具有非常高的學術價值和潛在應用價值.對于復雜信息網(wǎng)絡的分析,根據(jù)信息網(wǎng)絡載體的不同,也會具有非常廣的普適性.在學術價值方面,信息網(wǎng)絡是信息的重要表達形式.隨著大數(shù)據(jù)和深度學習技術的突飛猛進,人工智能研究正面臨新一輪的爆發(fā)式發(fā)展,能否對復雜信息網(wǎng)絡做出有效合理的數(shù)據(jù)分析是今后學術研究上的熱門話題.在應用價值方面,信息網(wǎng)絡中擁有著非常廣泛的應用場景,如節(jié)點分類、鏈接預測、|V|×kRepresentationlearning

Features classificationLinkpredictionVertexsimilarity...G=(V,E)

Networkembeddings圖1(網(wǎng)絡版彩圖)網(wǎng)絡表示學習流程圖Figure1(Coloronline)The?owchartofNRL具有實際的應用價值綜上所述針對復雜信息網(wǎng)絡的研究與應用是人工智能學科發(fā)展的學術前沿問題,是智能信息處理和服務發(fā)展的基礎技術保障,針對大規(guī)模復雜信息網(wǎng)絡的學習研究十分必要.在類似Facebook和新浪微博等社交網(wǎng)絡的快速發(fā)展下,很多研究者著力于在網(wǎng)絡數(shù)據(jù)上設計快速有效的算法.在有關網(wǎng)絡的研究中,一個重要的問題就是如何合適的表示網(wǎng)絡信息.傳統(tǒng)的網(wǎng)絡表示一般使用高維的稀疏向量.但是高維稀疏的表示也成為了人們使用統(tǒng)計學習方法時的局限所在,因為高維的向量將會花費更多的運行時間和計算空間.隨著表示學習技術在自然語言處理等領域的發(fā)展和廣泛應用,研究者們轉而探索將網(wǎng)絡中的節(jié)點表示為低維稠密的向量表示的方法.直覺上來看,在網(wǎng)絡中拓撲結構相似的節(jié)點也應該具有相近的向量表示.這里向量表示的相似性一般用向量間的余弦距離或者歐氏距離來表示.之后這些作為節(jié)點表示的向量就可以用作對應節(jié)點的特征并應用到后續(xù)的任務場景中.,尋找解決信息網(wǎng)絡背景下的各種實際問題的普適方法,有效融合網(wǎng)絡結構與節(jié)點外部信息,形成更具區(qū)分性的網(wǎng)絡表示.近年來,網(wǎng)絡表示學習問題吸引了大量的研究者的目光,相關的論文工作也層出不窮,本文將針對近年來的網(wǎng)絡表示學習工作進行系統(tǒng)性的介紹和總結.網(wǎng)絡表示學習的定義本節(jié)將形式化地介紹網(wǎng)絡表示學習的意義.如圖1所示,網(wǎng)絡表示是銜接網(wǎng)絡原始數(shù)據(jù)和網(wǎng)絡應用任務的橋梁.網(wǎng)絡表示學習算法負責從網(wǎng)絡數(shù)據(jù)中學習得到網(wǎng)絡中每個節(jié)點的向量表示,之后這些節(jié)點表示就可以作為節(jié)點的特征應用于后續(xù)的網(wǎng)絡應用任務,如節(jié)點分類、鏈接預測和可視化等.ttVEV是節(jié)點集合E是邊的集合evivjEvi到vj的一條邊.AR|V|×|V|,Aij1(vivjE,Aij0.鄰接矩陣是網(wǎng)絡數(shù)據(jù)的一種簡單直接的表達形式.A的每一行表示了一個節(jié)點和所有其他節(jié)點的鏈接關系,可以看作是對應節(jié)點的一種表示.雖然方便直接,使用鄰接矩陣的網(wǎng)絡表示受到計算效率問題的影響.A|V||V|的存儲空間,|V|增長到百萬級時通常是不可接受的.另一方面,0,數(shù)據(jù)十分稀疏.這種數(shù)據(jù)稀疏性使得快速有效的統(tǒng)計學習方法的應用變得困難[1].因此,研究者們轉而為網(wǎng)絡中的節(jié)點學習低維稠密的向量表示.形式化地,網(wǎng)絡表示學習的目標v∈VRv∈Rk,k|V|..通過優(yōu)化算法自動得到而不需要特征工程的節(jié)點表示可以進一步用于后續(xù)的網(wǎng)絡應用任務,如節(jié)點分類.這些低維的向量表示使得快速高效的算法設計成為可能,而不必再去考慮原本的網(wǎng)絡結構.基于網(wǎng)絡結構的網(wǎng)絡表示學習隨著機器學習技術的發(fā)展,對于網(wǎng)絡中節(jié)點的特征學習已經(jīng)成為了一項非常重要的任務.網(wǎng)絡表示學習算法將網(wǎng)絡信息轉化為低維稠密的實數(shù)向量,并將其用作已有的機器學習算法的輸入.舉例來說,節(jié)點的表示可以作為特征,送到類似支持向量機的分類器中.同時,節(jié)點表示也可以轉化成空間坐標,用于可視化任務[2～5].下面將介紹已有的網(wǎng)絡表示學習算法和相關進展.基于矩陣特征向量計算較早的用于網(wǎng)絡表示學習的算法主要歸于此類.譜聚類算法通過計算關系矩陣的前k個特征向量或奇異向量來得到k維的節(jié)點表示.關系矩陣一般就是網(wǎng)絡的鄰接矩陣或者Laplace矩陣.這類方法強烈的依賴于關系矩陣的構建,不同的關系矩陣的評測結果差異很大.一般來講,基于譜聚類方法的時間復雜度較高,因為特征向量和奇異向量的計算時間是非線性的.另一方面,譜聚類方法需要將關系矩陣整體存于內(nèi)存之中,所以空間復雜度也是不能忽略的.這些局限性阻止了這類算法在大規(guī)模數(shù)據(jù)和在線平臺上的擴展應用.現(xiàn)在將展示幾種譜聚類算法的實例.這些方法的適用性如表1所示.(locallylinearembedding)[6,7]假設節(jié)點的表示是從同一個流形中采樣得到的.局部線性表示假設一個節(jié)點和它鄰居的表示都位于該流形的一個局部線性的區(qū)域.也就是說,一個節(jié)點.局部線性表示使用鄰居節(jié)點表示的加權.最小化損失函數(shù)的優(yōu)化問題最終轉化成某個關系矩陣特征向量計算問題求解.Laplace(Laplaceeigenmap)[8,9]簡單的假設兩個相連的節(jié)點的表示應該相近.特別地,這里表示相近是由向量表示的歐氏距離的平方來定義Laplace矩陣的特征向量計算問題.有向圖表示(directedgraphembedding)[10]進一步擴展了Laplace特征表方法,給不同點的損失函數(shù)以不同的權重.其中點的權重是由基于隨機游走的排序方法來決定,如PageRank.不同于前面的方法,Liu[11](com-munity)的強度,(modularity)引入了損失函數(shù).模塊性是衡量網(wǎng)絡分離程度的指標,高的模塊性值意味著在同一模塊內(nèi)節(jié)點連接緊密,而不同模塊間節(jié)點連接稀疏.最終該優(yōu)化問題轉化為Laplace矩陣的特征向量計算此類方法一般先定義一個關于節(jié)點表示的線性或二次損失函數(shù).然后將最優(yōu)化問題轉化為某個關系矩陣的特征向量計算問題.這一類方法最主要的缺點在于復雜度:大規(guī)模矩陣的特征向量計算是非常消耗計算時間和空間的.表1局部線性表示(LLE)、Laplace特征表(Laplaceeigenmap)、有向圖表示(DGE)的適用性比較Table1ThecomparisonofLLE,Laplaceeigenmap,andDGEGraphtypeModel Undirected DirectedLLE C – –Laplaceeigenmap C C –DGE C C C表2DeepWalk算法和word2vec的類比Table2ThecomparisonbetweenDeepWalkandword2vecModelTargetInputOutputWord2vecWordsSentencesWordembeddingsDeepWalkNodesNodesequencesNodeembeddings基于簡單神經(jīng)網(wǎng)絡的算法3.1小節(jié)介紹的方法中,對最優(yōu)化問題求最優(yōu)解的過程,如特征向量的計算,對于大規(guī)模的網(wǎng)絡數(shù)據(jù)來說是非常耗時的.另一方面,基于神經(jīng)網(wǎng)絡的方法已經(jīng)在自然語言和圖像處理領域上取得了非常突出的成果.雖然梯度下降的參數(shù)更新方法無法保證總是得到最優(yōu)化問題的最優(yōu)解,但是神經(jīng)網(wǎng)絡的方法一般更加快速而且也能得到相當不錯的結果.DeepWalk算法[1]第一次將深度學習中的技術引入到網(wǎng)絡表示學習領域.DeepWalk算法充分利用了網(wǎng)絡結構中的隨機游走序列的信息.使用隨機游走序列而不是鄰接矩陣的優(yōu)勢有兩點:首先,隨機游走序列只依賴于局部信息,所以可以適用于分布式和在線系統(tǒng),而使用鄰接矩陣就必須把所有信息存儲于內(nèi)存中處理,面臨著較高的計算時間和空間消耗.第二,對隨機游走序列進行建?？梢越档徒?-1二值鄰接矩陣的方差和不確定性.無監(jiān)督表示學習方法在自然語言處理領域已經(jīng)得到了廣泛的學習與應用.Perozzi等[1]通過實驗驗證了隨機游走序列中節(jié)點和文檔中的單詞一樣都遵從指數(shù)定律(power-law),從而進一步將著名的詞表示學習算法word2vec[12～14]應用在隨機游走序列上,學習節(jié)點表示.w形式化地,viwvi?wvi?1vi+1vi+w.vi,產(chǎn)生兩側節(jié)點的概率.作為模型簡化,Skip-Gram模型忽略了節(jié)點的順序和距離中心節(jié)點的距離.(1)表示:wminR

kw,k=0

?logPr(vi+k|Ri), (1)其中Pr(vi+k|Ri)由式(2)定義的softmax函數(shù)得到:exp(RiCT)∑||Pr(vj|Ri)= Vk∑||

jkexp(RiCT)k

. (2)2word2vec的類比情況.首先在網(wǎng)絡上采樣生成大量的隨機游走序列,Skip-gramHierarchicalSoftmax模型對隨機游走序列中每個局部窗口內(nèi)的節(jié)點對進行概率建模,最大化隨機游走序列的似然概率,并最終使用隨機梯度下降學習參數(shù).表3不同網(wǎng)絡表示學習方法的比較Table3ThecomparisonofvariousNRLmethodsMethod Matrix Accuracy Speed Spectralclustering L Precise Lowk=1KGraRep Ak,k=1KGraRep Ak,k=1,...,K Precise Slow

Approximate Medium基于簡單神經(jīng)網(wǎng)絡的另一個代表性的網(wǎng)絡表示學習算法就是LINE算法[15].Tang等[15]提出了一種可以適用于大規(guī)模的有向帶權圖的網(wǎng)絡表示學習算法.為了對節(jié)點間的關系進行建模,LINE算法用觀察到的節(jié)點間連接刻畫了第一級相似度關系,用不直接相連的兩個節(jié)點的共同鄰居刻畫了這兩個點之間的第二級相似度關系.直覺上說,對直接相連的兩個節(jié)點間關系的刻畫等價于對原始網(wǎng)絡的鄰接矩陣的建模.但是一個網(wǎng)絡中的邊關系往往是非常稀疏的,所以有必要進一步刻畫第二級相似度關系來考慮雖然并不直接相連,但是共同鄰居較多的節(jié)點對,從而對第一級相似度的信息予以補充.具體來說,LINE算法對所有的第一級相似度和第二級相似度節(jié)點對進行了概率建模,并最小化該概率分布和經(jīng)驗分布之間的KL距離.參數(shù)學習由隨機梯度下降算法決定.基于矩陣分解的方法給定關系矩陣,對關系矩陣進行矩陣分解達到降維的效果,從而得到節(jié)點的網(wǎng)絡表示.Yang等[16]證明了DeepWalk算法實際上等價于某個特定關系矩陣的矩陣分解.由此可見,矩陣分解算法也是學習網(wǎng)絡表示的一種重要手段.GraRep算法[17]考慮了一種特別的關系矩陣.GraRepSVD分解對該關系矩陣進行降維從k步網(wǎng)絡表示.形式化地,A進行行歸一化處理,A中每行的加1.GraRepkAk,k步的隨機游走抵達的概率.更進一步,GraRepk值,k值對k步網(wǎng)絡表示拼接起來,.GraRep的主要缺點在Ak的時候計算效率很低.Yang等[18]在其后續(xù)工作中將基于矩陣分解或者可以轉化為矩陣分解的方法總結成同一個算法框架:第一步構建節(jié)點間的關系矩陣,第二步對該矩陣進行矩陣分解操作得到網(wǎng)絡表示.該工作將譜聚類方法[11],DeepWalk和GraRep方法第一步構建關系矩陣的過程進行了分析對比,并總結在表3中,其中L是Laplace矩陣.通過對表3的觀察,可以得出兩個結論.一是對更高階的關系矩陣Ak的構建可以提升網(wǎng)絡表示的效果,二是精確的計算高階的關系矩陣Ak計算效率很低.這兩個結論促使我們尋找一種可以間接近似高階的關系矩陣且不增加計算復雜度的方法.Yang等[18]提出了一種簡單的網(wǎng)絡表示更新策略NEU,如式(3)所示:Rnew=R+λ1A·R+λ2A·(A·R), (3)其中λ1,λ2是超參數(shù),一般設置為0.5和0.25.該工作證明了式(3)中的策略可以讓更新后的網(wǎng)絡表示近似等價于從更高階的關系矩陣中分解而來,而不增加計算復雜度.實際上,當該算法作用于DeepWalk算法的輸出結果時,只占用DeepWalk算法1%的時間,就可以有非常顯著的提升效果.Unsupervisedcomponent(Localstructurepreservedcost)

Unsupervisedcomponent(Localstructurepreservedcost)SupervisedcomponentSupervisedcomponent(Globalstructurepreservedcost)ParametersharingLaplaceeigenmapsi j圖2(網(wǎng)絡版彩圖)SDNE算法(修改自文獻[19]）Figure2(Coloronline)TheframeworkofSDNE(modi?edfrom[19])基于深層神經(jīng)網(wǎng)絡的方法和之前使用淺層神經(jīng)網(wǎng)絡的方法不同,SDNE[19]使用深層神經(jīng)網(wǎng)絡對節(jié)點表示間的非線性進行建模.整個模型可以被分為兩個部分:一個是由Laplace矩陣監(jiān)督的建模第一級相似度的模塊,另一個是由無監(jiān)督的深層自編碼器對第二級相似度關系進行建模.最終SDNE算法將深層自編碼器的中間層作為節(jié)點的網(wǎng)絡表示,模型如圖2所示.基于社區(qū)發(fā)現(xiàn)的算法如譜聚類算法中展示的,研究者已經(jīng)考慮從社區(qū)發(fā)現(xiàn)角度學習網(wǎng)絡表示.具體來說,就是讓節(jié)點表示的每一維對應該節(jié)點從屬于一個社區(qū)的強度,然后設計最優(yōu)化目標進行求解.這類算法會學習得到上述的社區(qū)強度關系表示,然后轉化為社區(qū)發(fā)現(xiàn)的結果.而學習社區(qū)強度關系表示的過程可以看作是無監(jiān)督的非負節(jié)點表示學習的過程.BIGCLAM[20]作為一個可覆蓋社區(qū)發(fā)現(xiàn)算法,為每個網(wǎng)絡中的節(jié)點學習了一個上述的k維非負向量表示.BIGCLAM算法對網(wǎng)絡中每條邊的生成概率進行建模:兩個點的向量表示內(nèi)積越大,那么這兩個點之間形成邊的概率也就越高.算法的最大化目標是整個網(wǎng)絡結構的最大似然概率.最優(yōu)化求解參數(shù)的過程由隨機梯度下降算法實現(xiàn).保存特殊性質的網(wǎng)絡表示使用向量表示代替原始網(wǎng)絡的策略在帶來便利的同時,也會丟失很多原始網(wǎng)絡中的信息.比如大.但內(nèi)積或者余弦距離都.如社區(qū)(community)等信息,也會在網(wǎng)絡表示學習的過程中丟失.SlidingwindowSlidingwindowVertexembeddingsCommunityembeddingAssignedcommunitiesCommunityembeddingsVertexsequence1234567RandomwalksonanetworkCommunity12Community2Community3713564圖3(網(wǎng)絡版彩圖)CNRL算法(修改自文獻[22])Figure3(Coloronline)TheframeworkofCNRL(modi?edfrom[22])HOPE[21]為每個節(jié)點刻畫了兩種不同的表示,并著眼于保存原始網(wǎng)絡中的非對稱性信息.HOPE構建了不同的非對稱的關系矩陣,JDGSVD算法進行矩陣降維得到節(jié)點的網(wǎng)絡表示.CNRL算法[22]考慮了在節(jié)點表示中嵌入網(wǎng)絡隱藏的社區(qū)信息.如圖3所示,CNRL假設每個節(jié)點屬于多個社區(qū),也就是每個節(jié)點在所有的社區(qū)上有一個概率分布.DeepWalk將隨機游走生成的節(jié)點序列看作句子,將序列中的節(jié)點看作文本中的詞,直接用訓練詞向量的Skip-Gram模型來訓練節(jié)點向量.受這種類比的啟發(fā),CNRL將網(wǎng)絡中的社區(qū)看作文本中的主題,也就是說,網(wǎng)絡中相關的節(jié)點傾向于行程社區(qū),而文本中相關的詞則會構成主題.因此,CNRL算法在生成的隨機游走序列上,將每個節(jié)點序列看成一篇文檔,通過基于Gibbs采樣的LDA[23]來學習每個節(jié)點的社區(qū)分布,并通過隨機采樣的方式,來給序列中的節(jié)點分配其對應的社區(qū)標簽.隨后,在Skip-Gram模型的基礎上,用中心節(jié)點的節(jié)點表示和對應的社區(qū)表示同時去預測隨機游走序列中的鄰近節(jié)點,從而將社區(qū)結構信息保存在節(jié)點表示中.為了對通過主題模型檢測出的社區(qū)有一個直觀的感受,驗證將網(wǎng)絡中的社區(qū)類比為文本中的主題的正確性,CNRL對一個小的Karate網(wǎng)絡進行了社區(qū)發(fā)現(xiàn)結果的可視化,如圖4所示.可以發(fā)現(xiàn),CNRL能夠有效檢測出不同規(guī)模的有重疊的社區(qū),以及有效的識別出社區(qū)邊界. 4(網(wǎng)絡版彩圖)Karate(CNRL-2CNRL-4)([22])Figure4(Coloronline)CommunitydetectionresultsonKarateunfolding,CNRL-2,CNRL-4)(modi?edfrom[22])M|V| kMWTft |V|WTHT|V| HT|V|圖5(網(wǎng)絡版彩圖)TADW算法(修改自文獻[16])Figure5(Coloronline)TheframeworkofTADW(modi?edfrom[16])結合外部信息的網(wǎng)絡表示學習真實世界中的網(wǎng)絡節(jié)點往往會伴隨著豐富的外部信息,.而傳統(tǒng)網(wǎng)絡表示學習主要依賴于網(wǎng)絡拓撲結構信息,而忽略了這些異質的外部信息.因此,如何能夠在網(wǎng)絡表示學習過程中考慮這些外部信息提高網(wǎng)絡表示的質量和增強表示向量在網(wǎng)絡分析任務上的效果,是網(wǎng)絡表示學習領域的重要挑戰(zhàn).結合文本信息的方法在網(wǎng)絡數(shù)據(jù)中,除去節(jié)點間的邊信息以外,也會有很多依存于網(wǎng)絡的文本信息.比如社交網(wǎng)絡中,除去用戶間的好友關系,也會有豐富的用戶狀態(tài)或者博客內(nèi)容等文本信息.我們可以利用這些文本信息作為網(wǎng)絡結構信息的補充,進一步增強網(wǎng)絡節(jié)點表示的強度和效果.[16]在矩陣分解框架下,將節(jié)點的文本特征引入網(wǎng)絡表示學習.5所示,算法算法進一步加強得到:M3個小的矩陣乘積,其T是固定的文本特征向量,另外兩個矩陣是參數(shù)矩陣.算法使用共軛梯度下降法WH矩陣求解參數(shù).真實世界中的網(wǎng)絡節(jié)點在與其他節(jié)點進行交互時,往往會展現(xiàn)出不同方面的特點.例如,一個研究者與不同的研究者發(fā)生合作關系往往因為不同的研究主題;社交媒體中的用戶會因為不同的原因與其他用戶建立聯(lián)系.然而,已有的網(wǎng)絡表示學習方法會給每個網(wǎng)絡節(jié)點學習一個固定的表示向量,不能展現(xiàn)出同一節(jié)點對于不同鄰居節(jié)點角色的變化.此外,這些方法不能對節(jié)點之間的關系進行有效的建模和解釋.因此,CANE[24]利用網(wǎng)絡節(jié)點的文本信息來對節(jié)點之間的關系進行解釋,來為網(wǎng)絡節(jié)點根據(jù)不同的鄰居學習上下文相關的網(wǎng)絡表示. apFaqColumn-pooling+softmaxRow-pooling+apFaqColumn-pooling+softmaxRow-pooling+softmaxPQAuvConvolutionalunit(V)ut=P·apTextembeddingEdgeTextdescriptionTextdescriptionConvolutionalunittanh(PTAQ)(V)ut=Q·aqFigure6TheframeworkofCANE(modi?edfrom[24])CANE假設每個節(jié)點的表示向量由文本表示向量及結構表示向量構成,其中,文本表示向量的生成過程與邊上的鄰居相關,所以生成的節(jié)點表示也是上下文相關的.如圖6所示,CANE利用卷積神經(jīng)網(wǎng)絡對一條邊上兩個節(jié)點的文本信息進行編碼.在文本表示生成的過程中,利用相互注意力機制,選取兩個節(jié)點彼此最相關的卷積結果構成最后的文本表示向量.半監(jiān)督的網(wǎng)絡表示學習無監(jiān)督的網(wǎng)絡表示學習中,其后續(xù)任務很多是以節(jié)點表示作為特征的節(jié)點分類任務.之前的工作主要基于無監(jiān)督的網(wǎng)絡表示學習,在針對節(jié)點分類等機器學習任務時,缺少區(qū)分性.半監(jiān)督的網(wǎng)絡表示學習的想法就是把已經(jīng)標注的節(jié)點的節(jié)點類別或者標簽利用起來,加入到網(wǎng)絡表示學習的過程中,從而針對性的提升節(jié)點網(wǎng)絡表示在后續(xù)分類任務中的效果.為了解決這個問題,Tu等[25]提出了一種半監(jiān)督的網(wǎng)絡表示學習方法MMDW,來學習有區(qū)分性MMXTboundaryMax-marginclassifierClassificationBiasedgradient SupportvectorsYDeepWalkasmatrixfactorization圖7(網(wǎng)絡版彩圖)MMDW算法(修改自文獻[25])Figure7(Coloronline)TheframeworkofMMDW(modi?edfrom[25])的網(wǎng)絡表示.如圖7所示,MMDW同時學習矩陣分解形式的網(wǎng)絡表示模型和最大間隔分類器.為了增大網(wǎng)絡表示的區(qū)分性,MMDW會針對分類邊界上的支持向量計算其偏置向量,使其在學習過程中向正確的類別方向進行偏置,從而增大表示向量的區(qū)分能力..MMDW模型使用半監(jiān)督訓練表示的優(yōu)勢.此外,在網(wǎng)絡表示的可視化中(8),.[26]也采用了類似的方式,模型和最大間隔分類器,來提高網(wǎng)絡節(jié)點分類的效果.Node2vec[27]算法.選取隨機游走序列中下一個節(jié)點的方式是均勻隨機分布的.node2vecpq將寬度.寬度優(yōu)先搜索注重鄰近的節(jié)點并刻畫了相對局部的一種網(wǎng)絡表示,寬度優(yōu)先中的節(jié)點一般會出現(xiàn)很多次,從而降低刻畫中心節(jié)點的鄰居節(jié)點的方差;深度優(yōu)先搜索反應了更高層面上的節(jié)點間的同質性.特別地,node2vecpq控制隨機游走序列的跳轉概率,9所示,假設上一步(t,v),v的不同鄰居,node2vecpq定義了不同的鄰居的跳轉概率,p控制跳向上一個節(jié)點的鄰居的概率q控制跳向上一個節(jié)點的非鄰居的概率具體的未歸一的跳轉概(a)10(a)86Dimension1Dimension14Dimension1Dimension12024681015 10 5 0 5 10 Dimension2

8(b)6(b)420246815 10 5 0 5 10Dimension2圖8(網(wǎng)絡版彩圖)DeepWalk和MMDW可視化結果(修改自文獻[14])Figure8(Coloronline)Thevisualizationresultsof(a)DeepWalkand(b)MMDW(modi?edfrom[14])xx1x2α=1vα=1/qα=1/qα=1/px3t圖9Node2vec算法(修改自文獻[27])Figure9Theframeworkofnode2vec(modi?edfrom[27])率值πvx=αpq(t,x)如下所示:

αpq(t,x)=

1,ifdtx=0,p,ifdtx=p11

(4)q,ifdtx=2.其中,dtx表示節(jié)點t和x之間的最短距離.為了獲得最優(yōu)的超參數(shù)p和q的取值,node2vec通過半監(jiān)督形式,利用網(wǎng)格搜索最合適的參數(shù)學習節(jié)點表示.其他的半監(jiān)督網(wǎng)絡表示學習方法還包括:GCN[28]設計了一種作用于網(wǎng)絡結構上的卷積神經(jīng)網(wǎng)絡,并使用一種基于邊的標簽傳播規(guī)則實現(xiàn)半監(jiān)督的網(wǎng)絡表示學習.Planetoid[29]聯(lián)合地預測一個節(jié)點的鄰居節(jié)點和類別標簽,類別標簽同時取決于節(jié)點表示和已知節(jié)點標簽,從而進行半監(jiān)督表示學習.EdgeautoencoderEdgeautoencoderReconstructededgevectorulv′TranslationmechanismBinaryedgevectorLabel#5Edgewithmulti-labelsLabel#2uv圖10(網(wǎng)絡版彩圖)TransNet算法(修改自文獻[30])Figure10(Coloronline)TheframeworkofTransNet(modi?edfrom[30])結合邊上標簽信息的網(wǎng)絡表示學習節(jié)點與節(jié)點之間也存在著豐富的交互信息例如社交;論文合作網(wǎng)絡中,研究者之間存在合作的論文的具體信息.然而,已有的網(wǎng)絡表示學習模型更側重于節(jié)點本身的信息,0,1值或者連續(xù)的實值而忽略邊上豐富的語義信息同時,而忽略了對節(jié)點之間具體關系的建模和預測能力.為了解決關系的建模和預測問題,等[30]模型,利用平移機制來解決社會關系抽取問題.10所示,假設頭結點表示向量加上關系表示向量等于尾節(jié)點表示向量.其中,,對交互文本抽取出標簽集合來表示關系.隨后,通過深層自動編碼器對標簽集合進行壓縮,來得到關系的表示向量.該模型能夠有效地預測未標注的邊上的標簽集合,在社會關系抽取任務上取得了顯著的提升.評測任務和應用場景節(jié)點分類在進行網(wǎng)絡數(shù)據(jù)的分析時,一個最常見的場景就是對網(wǎng)絡中的節(jié)點進行合理的劃分.舉例來說,在社交網(wǎng)絡上,不同的用戶可以根據(jù)他們的興趣愛好不同分為不同的類別.然而實際數(shù)據(jù)中的類別標注信息是十分稀疏的,所以需要設計算法利用節(jié)點間的連接關系以及少量的已標注分類信息,對大量表4Cora數(shù)據(jù)集上的分類結果Table4Classi?cationresultsonCoraAccuracy(%)

10%a)10%a)50%a)90%a)GF50.8(68.0)61.8(77.0)64.8(77.2)4(+0.1)SC55.9(68.7)70.8(79.2)72.7(80.0)1(+0.1)DeepWalk71.3(76.2)76.9(81.6)78.7(81.9)31(+0.1)LINE1st64.8(70.1)76.1(80.9)78.9(82.2)62(+0.1)LINE2nd63.3(73.3)73.4(80.1)75.6(80.3)67(+0.1)node2vec76.9(77.5)81.0(81.6)81.4(81.9)56(+0.1)TADW78.1(84.4)83.1(86.6)82.4(87.7)2(+0.1)GraRep70.8(76.9)78.9(82.8)81.8(84.0)67(+0.3)Thenumbermeanstrainingratio.表5BlogCatalog數(shù)據(jù)集上的分類結果Table5Classi?cationresultsonBlogCatalogMacro-F1(%) Micro-F1

1%a)1%a)5%a)9%a)1%a)5%a)9%a)GF6.6(7.9)9.8(11.3)10.3(12.2)17.0(19.6)22.2(25.0)23.7(26.7)19(+1)SC8.4(9.3)13.1(14.8)14.5(17.0)19.4(20.3)26.9(28.1)29.0(31.0)10(+1)DeepWalk12.4(13.6)18.3(20.1)20.4(22.0)24.9(26.4)31.5(33.7)33.7(35.9)935(+1)LINE1st11.1(12.2)16.6(18.3)18.6(20.1)23.1(24.7)29.3(31.6)31.8(33.5)241(+1)LINE2nd10.3(11.2)15.0(16.8)16.5(18.3)21.5(25.0)27.9(31.6)30.0(33.6)244(+1)node2vec12.5(13.0)19.2(19.8)21.9(22.5)25.0(27.0)31.9(34.5)35.1(37.2)454(+1)a)ThesameasinTable4.表6Flickr數(shù)據(jù)集上的分類結果Table6Classi?cationresultsonFlickrMacro-F1(%) Micro-F1

1%a)1%a)5%a)9%a)1%a)5%a)9%a)GF4.3(5.2)4.9(5.4)5.0(5.4)21.1(21.8)22.0(23.1)21.7(23.4)241(+8)SC8.6(10.9)11.6(14.3)12.3(15.0)24.1(29.2)27.5(34.1)28.3(34.7)102(+8)DeepWalk10.5(11.6)17.1(17.8)19.1(19.8)31.8(33.1)36.3(36.7)37.3(37.6)9,292(+8)LINE1st10.3(10.7)16.0(16.6)17.6(18.2)32.0(32.7)35.9(36.4)36.8(37.2)2,664(+8)LINE2nd7.8(8.5)13.1(13.5)14.7(15.2)30.0(31.0)34.2(34.4)35.1(35.2)2,740(+8)a)ThesameasinTable4.的未標注節(jié)點的分類情況進行標注.類似的任務場景還有對互聯(lián)網(wǎng)上的各個網(wǎng)頁進行內(nèi)容上的分類.在節(jié)點分類的應用上,根據(jù)算法預測的未標注節(jié)點的類別可以為節(jié)點的標簽進行推薦,節(jié)約手工標注的人力成本在各類網(wǎng)絡場景都有非常實際的應用.4～6Cora,BlogCatalogFlickr3個公開數(shù)據(jù)集上的節(jié)點分類效果對比.NEU更新后的分類效果.時間一列記錄了各算法的運行時間,NEU更新算法所花費的額外運行CNJaccardSaltonGFGF+NEUSCSC+NEUCNJaccard