基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法①

倪琦瑄,張 霞,卜 湛

1(南京財經(jīng)大學(xué) 信息工程學(xué)院,南京 210003)

2(南京中醫(yī)藥大學(xué) 人工智能與信息技術(shù)學(xué)院,南京 210023)

3(南京財經(jīng)大學(xué) 江蘇省電子商務(wù)重點實驗室,南京 210003)

1 引言

現(xiàn)實世界中許多的社會,物理和信息系統(tǒng)都是以復(fù)雜網(wǎng)絡(luò)的形式存在的[1].在這些網(wǎng)絡(luò)中,人們通過挖掘網(wǎng)絡(luò)的潛在信息可以解決許多實際的問題,例如鏈路預(yù)測[2],鏈路重構(gòu)[3],節(jié)點分類[4],邊分類等.網(wǎng)絡(luò)表示學(xué)習(xí)將節(jié)點映射到潛在空間[5],并保留了豐富的結(jié)構(gòu)信息,為這些下游數(shù)據(jù)挖掘任務(wù)提供了一種新的解決方法,已在許多論文中被證明能夠非常有效地解決上述任務(wù)[6-13].

近10年里,有很多能夠保持網(wǎng)絡(luò)的結(jié)構(gòu)特性的方法被提出來.然而,以往的研究往往只注重節(jié)點視角下的網(wǎng)絡(luò)拓撲信息,而沒有充分考慮邊視角.現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)算法可以分為兩大類:基于隨機游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法和基于深度學(xué)習(xí)框架的網(wǎng)絡(luò)表示學(xué)習(xí)算法.基于隨機游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法,例如DeepWalk[8]和Node2Vec[9],主要分為隨機游走和Skip-gram[10]算法兩部分,他們通過隨機游走以獲取節(jié)點視角下的網(wǎng)絡(luò)拓撲結(jié)構(gòu),再利用Skipgram 模型對每個節(jié)點進行更新學(xué)習(xí),Node2Vec在DeepWalk的基礎(chǔ)上,加入了帶有偏置的隨機游走,使得其能以不同偏好的游走方式獲取節(jié)點的同質(zhì)性和結(jié)構(gòu)等價性.Line[11]也是一種基于鄰域相似假設(shè)的網(wǎng)絡(luò)表示學(xué)習(xí)算法,通過設(shè)置兩種鄰近性構(gòu)造目標函數(shù)來獲取節(jié)點的局部相似性和鄰居相似性.然而,這些算法往往只關(guān)注了節(jié)點視角下網(wǎng)絡(luò)拓撲信息,而沒有充分考慮邊視角.基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示算法,如SDNE[12],利用半監(jiān)督的自動編碼器模型來學(xué)習(xí)網(wǎng)絡(luò)中每個節(jié)點的表示向量,DNGR[13]則通過Random Surfing 模擬隨機游走過程獲取網(wǎng)絡(luò)拓撲信息,再利用堆疊降噪自編碼器對節(jié)點表示向量進行訓(xùn)練.GAE[14]通過圖卷積作為自編碼器的編碼方式,為每個節(jié)點聚合其鄰居的特征信息,再利用解碼器重構(gòu)網(wǎng)絡(luò)的鄰接信息.這些基于深度學(xué)習(xí)架的網(wǎng)絡(luò)表示學(xué)習(xí)算法往往效果很好,但其涉及到許多復(fù)雜計算,其空間和時間復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的擴大面臨著巨大的挑戰(zhàn),同時,這些算法也只關(guān)注了節(jié)點視角下的節(jié)點之間的連接信息,而沒有考慮過邊視角.而在已有的針對邊的一些研究中,大多考慮的是邊上的屬性或標簽信息[15,16].如NEES[15]通過邊計算節(jié)點之間關(guān)系的相似性,從而設(shè)置帶有偏好的隨機游走,使得節(jié)點的隨機游走的每一步都與上一步有盡可能相似的關(guān)系.ELAINE[16]則通過重構(gòu)每種邊的標簽向量,使得最終學(xué)習(xí)得到的節(jié)點向量能夠同時包含邊的標簽信息和網(wǎng)絡(luò)結(jié)構(gòu)信息.事實上,不同的視角會帶來不同的有效信息,比如不同的社區(qū)劃分.因此,本文將研究重點從節(jié)點轉(zhuǎn)移到邊.利用邊圖(line graph)[17]從邊的角度觀察網(wǎng)絡(luò).在邊圖中,原始網(wǎng)絡(luò)的邊表現(xiàn)為邊圖中的節(jié)點,邊圖中的邊表示原始網(wǎng)絡(luò)中邊之間的連接關(guān)系.Ahn 等人[18]在對重疊社區(qū)發(fā)現(xiàn)問題的研究中就提出了邊社區(qū)的概念,他們通過邊而不是節(jié)點來劃分社區(qū),并指出邊的層次結(jié)構(gòu)與原始網(wǎng)絡(luò)中的節(jié)點層次結(jié)構(gòu)有所不同,從邊的角度觀察目標網(wǎng)絡(luò)可以發(fā)現(xiàn)更多的特征.

一個好的網(wǎng)絡(luò)表示學(xué)習(xí)算法應(yīng)該能夠有效地保存網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)[9],為了達到這一效果,現(xiàn)有的基于隨機游走的網(wǎng)絡(luò)表示學(xué)習(xí)方法如DeepWalk 主要采用隨機游走獲取網(wǎng)絡(luò)中每個節(jié)點的上下文信息,繼而采用Skip-gram 模型學(xué)習(xí)其低維表示,從而使得具有相似拓撲屬性的節(jié)點具有相似的低維表示.過往的研究表明[19],一個社區(qū)的內(nèi)部連接應(yīng)該多于其外部連接,由于社區(qū)內(nèi)的連接密度應(yīng)該比較高,所以隨機游走時停留在自己社區(qū)內(nèi)節(jié)點上的概率要高于到外部的概率.為了進一步了解邊圖,本文選擇DBLP 數(shù)據(jù)集[20],分別在原始網(wǎng)絡(luò)和對應(yīng)的邊圖上進行隨機游走.在設(shè)置相同的總采樣次數(shù)的情況下,在圖1中畫出了其不同視角下的節(jié)點采樣頻率分布,橫坐標表示原始網(wǎng)絡(luò)中的節(jié)點在不同視角下的采樣過程中的出現(xiàn)次數(shù),縱坐標表示對應(yīng)出現(xiàn)次數(shù)的節(jié)點數(shù)量,可以看到在兩種視角下隨機游走得到的節(jié)點頻率分布是不同的,這是因為邊圖可以為我們提供更多的連接信息,進而可以為我們更好地揭示原始網(wǎng)絡(luò)中的層次結(jié)構(gòu).

圖1 對DBLP 數(shù)據(jù)集進行隨機游走的節(jié)點采樣頻率分布

綜上所述,本文提出了一種融合節(jié)點視角和邊視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法DPBCNE (Dual Perspectives Based Coupled Network Embedding).分別從兩個視角下學(xué)習(xí)網(wǎng)絡(luò)拓撲信息,在這個耦合模型中,可以同時學(xué)習(xí)節(jié)點和邊的低維表示.通過使用節(jié)點-邊的耦合訓(xùn)練機制,可以將節(jié)點和邊映射到相同的低維空間中.與大多數(shù)現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)方法間接獲取邊的表示方法不同,DPBCNE 可以直接學(xué)習(xí)得到節(jié)點和邊的表示,更具有解釋性.本文在4 個真實復(fù)雜網(wǎng)絡(luò)中驗證了DPBCNE的性能,并通過節(jié)點分類,邊分類,鏈路預(yù)測和鏈路重構(gòu)4 個任務(wù)來比較DPBCNE 與當(dāng)下最先進的網(wǎng)絡(luò)表示學(xué)習(xí)方法的效果.在鏈路預(yù)測任務(wù)中,與基準方法相比,DPBCNE 取得了較好的結(jié)果,在合作者網(wǎng)絡(luò)中僅次于CN 算法.而在節(jié)點分類,邊分類和鏈路重構(gòu)任務(wù)中,DPBCNE 均優(yōu)于其他所有網(wǎng)絡(luò)表示學(xué)習(xí)基準方法.

2 基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法

本文提出了一種新的基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法.其主要模型框架如圖2所示,模型可以分為兩個部分:第1 部分,獲取兩種視角下的網(wǎng)絡(luò)結(jié)構(gòu)信息,給定一個原始網(wǎng)絡(luò),首先構(gòu)建邊圖,在原始網(wǎng)絡(luò)和邊圖上分別進行隨機游走,得到不同視角下的節(jié)點采樣序列.第2 部分,耦合更新原始網(wǎng)絡(luò)中的節(jié)點向量和邊向量,根據(jù)節(jié)點和邊之間的對應(yīng)關(guān)系以及不同視角下中心詞節(jié)點和其上下文節(jié)點的關(guān)系,將上述兩個視角結(jié)合起來進行耦合更新,在更新過程中共享節(jié)點和邊的向量表示,最終獲得融合兩種視角下網(wǎng)絡(luò)結(jié)構(gòu)信息的節(jié)點向量和邊向量.

圖2 DPBCNE 模型框架示例

2.1 融合兩種視角的網(wǎng)絡(luò)表示學(xué)習(xí)

對于邊視角,本文首先根據(jù)原始網(wǎng)絡(luò)構(gòu)建邊圖(line graph) 來獲取邊視角下的結(jié)構(gòu)信息.給定的圖G(V,E),其中V表示節(jié)點集合,E表示邊集合.令圖G對應(yīng)的邊圖為Glink.在邊圖Glink中,圖G的邊集合E映射為邊圖的節(jié)點集合Vlink,節(jié)點集合則映射為邊圖的邊集合Elink.通過這種轉(zhuǎn)化構(gòu)建的邊圖記為Glink＜Vlink,Elink＞.

對于兩種視角下信息的獲取,本文采用DeepWalk的方法.通過對不同視角下的節(jié)點進行隨機游走得到語料庫,每一個隨機游走序列都可以看作是自然語言處理中的一個句子,然后用Skip-gram 算法最大化中心詞節(jié)點和其上下文的共現(xiàn)概率,從而得到不同視角下每個節(jié)點的表示向量,使得在同一視角下具有相似結(jié)構(gòu)的節(jié)點具有相似的向量.

因此,雙視角下網(wǎng)絡(luò)結(jié)構(gòu)信息獲取的目標函數(shù)分別為:

其中,N為節(jié)點網(wǎng)絡(luò)中節(jié)點的個數(shù),S為隨機游走得到的節(jié)點序列集合,w表示窗口大小,v表示節(jié)點網(wǎng)絡(luò)中的節(jié)點.Slink為邊圖中隨機游走得到的序列集合,Nlink為邊圖中的節(jié)點個數(shù)即原始網(wǎng)絡(luò)中邊的數(shù)量,vlink表示邊圖中的節(jié)點也即原始網(wǎng)絡(luò)中的邊.

該部分總的目標函數(shù)為:

為了得到有效的網(wǎng)絡(luò)潛在特征,本文同時融合節(jié)點視角和邊視角進行網(wǎng)絡(luò)表示學(xué)習(xí).介于節(jié)點與邊的一對多的關(guān)系,節(jié)點與其對應(yīng)邊的向量應(yīng)當(dāng)更相似,通過不斷耦合更新得到包含兩種視角下網(wǎng)絡(luò)拓撲信息的節(jié)點向量和邊向量,將另一視角的網(wǎng)絡(luò)信息聚合到當(dāng)前視角的節(jié)點向量學(xué)習(xí)上.節(jié)點和邊視角耦合關(guān)聯(lián)模型目標函數(shù)分別如下:

關(guān)聯(lián)部分總的目標函數(shù)為:

其中,Cnode(vi)表示原始網(wǎng)絡(luò)中與節(jié)點vi直接相連的所有邊的集合.表示原始網(wǎng)絡(luò)中與邊直接相連的所有節(jié)點的集合.

根據(jù)上述內(nèi)容,DBPBCNE 算法的總目標函數(shù)如下:

其中,α ∈[0,1]是用來平衡不同視角重要性的一個參數(shù),通過聯(lián)合優(yōu)化使得在節(jié)點學(xué)習(xí)的過程中耦合邊視角下的信息,以得到更有效的節(jié)點表示,同時也能學(xué)習(xí)得到耦合兩個視角下信息的邊向量.

2.2 耦合訓(xùn)練過程

本文使用隨機梯度上升(SGA)來訓(xùn)練模型,通過Softmax 公式來計算上述公式中的概率公式,例如式(1)中使用的P(vi+j|vi),可以通過下列方式來計算:

為降低時間復(fù)雜度,本文采用負采樣的方法對公式(8)進行簡化.除了更新窗口中的已知鄰居節(jié)點外,為給定節(jié)點生成k個負樣本.在計算公式(1)中的梯度時,便不需要在每個梯度步驟中枚舉式(8)中的所有節(jié)點,只需要計算根據(jù)詞分布構(gòu)建的負樣本和已知的正樣本.假設(shè)給定鄰居節(jié)點vi+j的負樣本集合為NEG(vi+j)={v1,v2,···,vk}則:

其中,表示待定參數(shù),為這部分要更新得到的節(jié)點向量,指示函數(shù)對求導(dǎo)可以得出:

從而可以得到原始網(wǎng)絡(luò)中的節(jié)點在節(jié)點視角下通過上下文節(jié)點進行更新的公式如下:

對于節(jié)點-邊耦合關(guān)聯(lián)模型部分,本文通過用原始網(wǎng)絡(luò)中與邊相連的節(jié)點更新邊,用與節(jié)點相連的邊更新節(jié)點,從而使得最終得到的原始網(wǎng)絡(luò)的節(jié)點和邊向量同時學(xué)習(xí)得到兩個視角下的網(wǎng)絡(luò)信息.

對于節(jié)點向量更新部分,給定一個原始網(wǎng)絡(luò)中的節(jié)點vi和對應(yīng)的一個相連邊,其負采樣得到的負樣本集合為同樣,對于邊向量更新部分,給定一個邊圖中的節(jié)點和他對應(yīng)的一個原始網(wǎng)絡(luò)中的節(jié)點vc,其通過負采樣得到的負樣本集合為NEG(vc)={v1,v2,···,vk}

原始網(wǎng)絡(luò)中節(jié)點在關(guān)聯(lián)部分的向量更新公式如下:

原始網(wǎng)絡(luò)中的邊在關(guān)聯(lián)部分的向量更新公式如下:

為了更加詳盡地介紹本文提出的DPBCNE 算法的具體流程,本文給出了算法偽代碼如算法1所示.

算法1.基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法輸入:圖,窗口大小,向量維度,隨機游走次數(shù),總迭代次數(shù),游走長度,學(xué)習(xí)率,負采樣個數(shù).Xv∈RN×dXvlink∈RNlink×d輸出:節(jié)點表示向量矩陣,邊表示向量矩陣.G(V,E) wd γ ITERl η k X Xlink 1.初始化,G(V,E) Glink＜Vlink,Elink＞2.根據(jù) 構(gòu)建邊圖i=0 γ 3.For to:Ω=shu f fle(V)4.Ωlink=shu f fle(Vlink)5.6.For each do S=RandomWalk(G,vi,l)vi∈Ω 7.8.End for i ∈Ωlink 9.For each do vlink Slink=RandomWalk(Glink,vlink i,l)10.11.End for 12.End for iter=1,2,3,···,ITER 13.For do s∈S 14.For each do Xv X′v 15.根據(jù)式(13)和式(14)更新和Xv X′vlink 16.根據(jù)式(15)和式(16)更新和17.End for slink∈Slink 18.For each do Xvlink X′vlink 19.根據(jù)式(18)和式(17)更新和Xvlink X′v 20.根據(jù)式(19)和式(20)更新和21.End for 22.End for

算法可以分為第一步獲取雙視角下的網(wǎng)絡(luò)結(jié)構(gòu)信息部分和第二步耦合更新部分.第2-10 行分別對節(jié)點視角和邊視角下的網(wǎng)絡(luò)進行隨機游走采樣獲取兩個視角下的網(wǎng)絡(luò)結(jié)構(gòu)信息,第14-22 行表示耦合更新過程,第14-17 行對于第1 步在原始網(wǎng)絡(luò)中采樣得到的所有節(jié)點序列中的每個節(jié)點,分別用其對應(yīng)的上下文節(jié)點和對應(yīng)的邊進行耦合更新,同樣,第18-21 行是對于邊圖中的采樣得到的所有節(jié)點序列中的節(jié)點,也即原始網(wǎng)絡(luò)中的邊,分別用其上下文節(jié)點和對應(yīng)的原始網(wǎng)絡(luò)中的關(guān)聯(lián)節(jié)點進行迭代耦合更新,最終得到融合兩個視角的原始網(wǎng)絡(luò)的節(jié)點向量和邊向量.

對于每一輪的迭代,第一部分的對原始網(wǎng)絡(luò)隨機游走的時間復(fù)雜度為Nrl,對邊圖的隨機游走時間復(fù)雜度為Nlinkrl,第二步耦合更新部分,對于節(jié)點的更新過程時間復(fù)雜度為Ngdk+Ndwrlk,其中g(shù)表示原始網(wǎng)絡(luò)中節(jié)點的平均度,對于邊的更新過程時間復(fù)雜度為2Nlinkdk+Nlinkdwrlk,其中,每個網(wǎng)絡(luò)的平均度通常都有一個最大值,其余的d,w,r,l,k均為可以設(shè)置的常數(shù).

3 實驗分析

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

本文主要針對傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)研究只是通過節(jié)點視角這一單一的視角而沒有考慮邊視角的問題,提出了一種新的基于雙視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí)算法(DPBCNE).本文在4 個真實的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集中分別驗證了該方法的性能,分別為Facebook[21],GRQC[22],HEPTH[22]和DBLP[20]數(shù)據(jù)集.其中Facebook為社交網(wǎng)絡(luò),總共有193 種節(jié)點標簽;GRQC和HEPTH為合作者網(wǎng)絡(luò),數(shù)據(jù)集中沒有標簽信息;DBLP為引文網(wǎng)絡(luò),總共有4 種節(jié)點標簽.

3.2 基準方法

在學(xué)習(xí)到節(jié)點的表示向量后,本文分別在4 個任務(wù)中與當(dāng)下主流的網(wǎng)絡(luò)表示學(xué)習(xí)算法進行比較,其中,(1)-(3)項是基于隨機游走的網(wǎng)絡(luò)表示學(xué)習(xí)算法,(4)-(6)項是基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)算法,此外,針對鏈路預(yù)測和鏈路重構(gòu)任務(wù),本文還選擇了一種效果良好的傳統(tǒng)鏈路預(yù)測方法Common Neighbor[23]作為對比方法,相關(guān)基準算法簡介如下:

(1)DeepWalk[8]:對節(jié)點采用隨機游走和Skip-gram模型以學(xué)習(xí)得到每個節(jié)點的表示向量.

(2)Node2Vec[9]:在DeepWalk的基礎(chǔ)上,引入了帶偏置的隨機游走,以選擇不同的搜索方式采樣節(jié)點.其中,偏置參數(shù)p=0.25,q=0.5.

(3)Line[11]:通過分別定義損失函數(shù)同時保存網(wǎng)絡(luò)中節(jié)點的一階鄰近度和二階鄰近度.

(4)SDNE[12]:使用自動編碼器通過聯(lián)合優(yōu)化目標函數(shù)來保持節(jié)點一階和二階鄰近性.該方法采用高度非線性的函數(shù)對網(wǎng)絡(luò)的鄰接矩陣進行編碼.

(5)DNGR[13]:利用Random Surfing 策略生成概率共現(xiàn)矩陣,再作為疊加去噪自動編碼器的輸入進行節(jié)點表示的學(xué)習(xí).

(6)GAE[14]:使用圖卷積網(wǎng)絡(luò)(GCN)編碼器和內(nèi)積解碼器.該方法利用GCN 學(xué)習(xí)節(jié)點間的高階關(guān)系.

(7)Common Neighbor (CN)[20]:以每個節(jié)點對之間的公共鄰居數(shù)作為節(jié)點之間的相似度評分,以進行鏈路預(yù)測.

在實驗過程中,為保證公平比較,所有實驗的參數(shù)均統(tǒng)一設(shè)置.對于網(wǎng)絡(luò)表示學(xué)習(xí)算法,其維度為128,負采樣樣本數(shù)為5,窗口大小為5,每個節(jié)點的隨機游走次數(shù)為10,步長是40,邊圖的設(shè)置與原始網(wǎng)絡(luò)相同.學(xué)習(xí)率為0.01,最大迭代次數(shù)為200.

3.3 評價指標

為驗證DPBCNE的有效性,本文分別在鏈路預(yù)測,鏈路重構(gòu),節(jié)點分類和邊分類4 個任務(wù)上進行了對比實驗.

對于鏈路預(yù)測和鏈路重構(gòu),采用了AUC(Area Under Curve)和AP(Average Precision) 指標來驗證最終的效果.

AUC表示當(dāng)隨機選擇一個正樣本和一個負樣本時,正樣本分數(shù)高于負樣本的概率.例如,在鏈路預(yù)測任務(wù)中,隨機挑選測試集中的一條邊和一條不存在的邊并進行比較,重復(fù)進行n次,其中有n′次測試集中邊的分數(shù)大于不存在的邊,有n′′次兩者獲得同樣的分數(shù),那么最終得到的AUC計算公式如下:

AP表示平均準確率,其計算公式如下:

其中,Precision表示每個類別的準確率,M表示類別數(shù).

對于節(jié)點分類和邊分類實驗,采用了Micro-F1和Macro-F1 來作為評價指標.定義如下:

其中,F1(A)表示標簽A的F1 得分,C表示所有的標簽集.Pr表示總的準確率,R表示總的召回率.

3.4 節(jié)點分類

節(jié)點分類是網(wǎng)絡(luò)表示學(xué)習(xí)中用以驗證算法有效性的一個重要任務(wù).此任務(wù)在Facebook和DBLP 數(shù)據(jù)集上驗證了DPBCNE 算法,首先移除數(shù)據(jù)集中沒有標簽的節(jié)點,將數(shù)據(jù)集按照30%的比例劃分訓(xùn)練集,剩余的節(jié)點作為測試集,將每個節(jié)點學(xué)習(xí)得到的表示向量作為邏輯回歸分類器的輸入進行訓(xùn)練,通過計算Micro-F1和Macro-F1 來比較不同模型之間的效果,最終結(jié)果如表1所示.

表1 節(jié)點分類實驗結(jié)果

從表1中可以看到,DPBCNE 模型地結(jié)果在兩個數(shù)據(jù)集上都優(yōu)于其他算法.在Facebook 數(shù)據(jù)集中,DPBCNE的Macro-F1 得分比其他算法中表現(xiàn)最好的DNGR 算法高出了0.99%,Micro-F1 得分則比DNGR算法高出了1.19%.這表明,通過融合兩種視角下的網(wǎng)絡(luò)表示學(xué)習(xí)能夠獲取比在單一視角下更豐富的節(jié)點采樣結(jié)果,也就是更豐富的網(wǎng)絡(luò)結(jié)構(gòu)信息,使得其在節(jié)點的類別劃分上比只關(guān)注單一視角的效果更好.而在DBLP數(shù)據(jù)集中,DPBCNE 算法的Macro-F1和Micro-F1 得分比DNGR 分別高了0.3%和0.55%.DPBCNE 模型在Facebook 數(shù)據(jù)集中的提升效果比在DBLP 數(shù)據(jù)集中更好,這是因為Facebook 數(shù)據(jù)集中每個節(jié)點具有多個標簽,而DBLP 數(shù)據(jù)集的每個節(jié)點有且只有一個標簽,融合了邊視角的耦合網(wǎng)絡(luò)表示學(xué)習(xí),也更能區(qū)分出節(jié)點的重疊社區(qū).

3.5 邊分類

傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)算法通常使用兩個節(jié)點向量簡單相連或相加來作為兩個節(jié)點之間的邊的表示[9].在本任務(wù)中,對于所有的網(wǎng)絡(luò)表示學(xué)習(xí)基準算法,首先學(xué)習(xí)到每個節(jié)點的向量,再用(vi+vj)/2表示節(jié)點vi和節(jié)點vj之間的邊向量.而對于DPBCNE,通過耦合學(xué)習(xí),可以直接得到每條邊的表示,使其更具解釋性.本任務(wù)采用Facebook 數(shù)據(jù)集進行驗證,聚合每對節(jié)點的標簽,作為其對應(yīng)邊的標簽,按照1%～9%的比例對于網(wǎng)絡(luò)中的邊劃分出訓(xùn)練集作為邏輯回歸分類器的輸入.本任務(wù)采用了Micro-F1和Macro-F1 指標來衡量最終的效果,具體結(jié)果如圖3所示.

圖3 邊分類實驗結(jié)果

圖3中,DeepWalk (Link) 方法通過直接對邊圖的節(jié)點進行隨機游走,不進行耦合訓(xùn)練直接得到邊向量.DeepWalk (Link)在邊分類任務(wù)中也取得了比只在節(jié)點上進行DeepWalk 學(xué)習(xí)節(jié)點表示再拼接成邊向量更好的結(jié)果,這說明對于邊向量的計算,在邊圖上直接進行學(xué)習(xí)得到是有效的.同時,DPBCNE 始終高于其他所有方法包括效果良好的DeepWalk (Link),這說明融合兩個視角的耦合訓(xùn)練學(xué)習(xí)得到的邊向量可以更好地保存網(wǎng)絡(luò)中的信息.

3.6 鏈路預(yù)測

在這個任務(wù)中,首先將網(wǎng)絡(luò)中所有的邊劃分為測試集和訓(xùn)練集(比例為3:7),同時保持網(wǎng)絡(luò)的連通性,通過對訓(xùn)練集進行網(wǎng)絡(luò)表示學(xué)習(xí),得到網(wǎng)絡(luò)中每個節(jié)點的表示,再計算|vi-vj|作為vi和vj之間的邊的表示.本文認為兩個節(jié)點之間是否存在邊可以由節(jié)點對應(yīng)向量的絕對差來決定[4].將測試集中的邊看作為正例,對每一個正例等比例地構(gòu)建一條不存在的邊當(dāng)作負例,將其作為邏輯回歸分類器的輸入.本任務(wù)用AUC和AP作為本任務(wù)的評價指標,具體結(jié)果如表2所示.

由表2可以看到,DPBCNE的AUC指標都在75%以上,這說明DPBCNE 可以有效地預(yù)測網(wǎng)絡(luò)中的未知邊.在Facebook 數(shù)據(jù)集以及DBLP 數(shù)據(jù)集中,DPBCNE 取得了最好的效果,在GRQC 與HEPTH 數(shù)據(jù)集中DPBCNE的效果僅次于CN 算法,這說明在合作者網(wǎng)絡(luò)中,節(jié)點之間的關(guān)系非常受共同鄰居的影響,復(fù)雜的學(xué)習(xí)反而沒有簡單的指標來得有效,但DPBCNE仍然高于其他所有基于隨機游走和深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí),由于融合了兩種視角,DPBCNE 能夠更好地預(yù)測網(wǎng)絡(luò)中未知的邊.

表2 鏈路預(yù)測實驗結(jié)果

3.7 鏈路重構(gòu)

鏈路重構(gòu)任務(wù)類似于鏈路預(yù)測,不同的是鏈路重構(gòu)所重構(gòu)的是現(xiàn)有的邊,而不是去預(yù)測未知的邊.給定一個網(wǎng)絡(luò),使用不同的鏈路重構(gòu)方法來重構(gòu)原始網(wǎng)絡(luò)的所有邊.在這個任務(wù)中,依舊使用兩個節(jié)點表示向量之間的絕對差作為每條邊的表示.同樣,采用AUC和AP作為評價指標.具體結(jié)果如表3所示.

表3 鏈路重構(gòu)實驗結(jié)果

可以看到,DPBCNE 模型的AUC 結(jié)果都接近于1,這說明該方法能夠很好地保存網(wǎng)絡(luò)的鄰接關(guān)系.在4 個數(shù)據(jù)集中,DPBCNE 始終效果是最好的,相比于傳統(tǒng)的鏈路預(yù)測方法CN,DPBCNE在AUC指標上提升了1.03%～17.59%,在AP指標上提升了0.87%～17.16%,相比于效果最好的基于隨機游走的算法LINE,DPBCNE在AUC指標上提升了0.96%～19.05%,在AP指標上提升了0.69%～24.1%,對比效果最好的基于深度學(xué)習(xí)的算法DNGR,DPBCNE在AUC指標上提升了1.76%～5.3%,在AP指標上提升了1.7%～7.73%.

4 結(jié)論與展望

本文討論了兩種不同視角在社區(qū)結(jié)構(gòu)和隨機游走方面的差異,通過經(jīng)驗分析,本文得出邊視角和節(jié)點視角在隨機游走中出現(xiàn)的節(jié)點分布是不同的,這意味著通過不同的視角,可以獲得更多的網(wǎng)絡(luò)拓撲信息.因此,本文提出了一種新的網(wǎng)絡(luò)表示學(xué)習(xí)算法DPBCNE,可以同時考慮邊視角和節(jié)點視角,并通過耦合學(xué)習(xí),學(xué)習(xí)得到節(jié)點向量和邊向量.本文在節(jié)點分類,邊分類,鏈路預(yù)測和鏈路重構(gòu)4 個任務(wù)上驗證了該方法的效果.DPBCNE在4 個任務(wù)中都展現(xiàn)了其良好的性能.本文只在靜態(tài)網(wǎng)絡(luò)中進行了任務(wù)驗證,而在現(xiàn)實生活中,網(wǎng)絡(luò)是不斷變化的,因此,未來的研究 將該算法考慮擴展到動態(tài)網(wǎng)絡(luò)以及加入深度學(xué)習(xí)框架以獲得更好的效果[24].同時,鑒于DPBCNE 可以直接學(xué)習(xí)得到每條邊的表示,還將考慮將其擴展到知識圖譜的應(yīng)用研究中[25].