基于Node2vec的改進(jìn)算法的研究

杜陽(yáng)陽(yáng)，李華康，李 濤

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210046)

0 引 言

信息網(wǎng)絡(luò)在現(xiàn)實(shí)世界中無(wú)處不在，規(guī)模從幾百個(gè)到幾百億個(gè)不等[1]。鄰接矩陣、鄰接表等是常用的數(shù)據(jù)表示方法，但在計(jì)算效率以及數(shù)據(jù)稀疏的問(wèn)題上往往不能達(dá)到很好的效果。隨著深度學(xué)習(xí)的發(fā)展和深入研究，圖數(shù)據(jù)的表示學(xué)習(xí)為圖數(shù)據(jù)的挖掘問(wèn)題提供了新的思路。節(jié)點(diǎn)表示成向量可以應(yīng)用于多個(gè)領(lǐng)域，如可視化[2]、節(jié)點(diǎn)分類[3]、鏈路預(yù)測(cè)[4]以及推薦[5]等。

在圖數(shù)據(jù)挖掘中，評(píng)價(jià)節(jié)點(diǎn)表示算法效果的主要方式是對(duì)節(jié)點(diǎn)進(jìn)行多標(biāo)簽分類[6]。和每個(gè)節(jié)點(diǎn)只有一個(gè)標(biāo)簽的問(wèn)題相比，顯然每個(gè)節(jié)點(diǎn)有多個(gè)標(biāo)簽的問(wèn)題要更為復(fù)雜。目前，基于游走的圖節(jié)點(diǎn)的表示學(xué)習(xí)算法都使用在多標(biāo)簽分類的結(jié)果來(lái)評(píng)價(jià)算法的有效性。

對(duì)于圖節(jié)點(diǎn)的多標(biāo)簽分類問(wèn)題，文中在隨機(jī)游走算法的基礎(chǔ)上考慮了標(biāo)簽信息的指導(dǎo)作用。該算法設(shè)置了一個(gè)游走參數(shù)，使游走時(shí)傾向于走和當(dāng)前節(jié)點(diǎn)有共同標(biāo)簽的鄰居節(jié)點(diǎn)，而不是隨機(jī)游走，并通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 國(guó)內(nèi)外研究現(xiàn)狀

對(duì)數(shù)據(jù)進(jìn)行分析需要將數(shù)據(jù)表示成計(jì)算機(jī)能夠識(shí)別的形式[7]。表示學(xué)習(xí)算法分為監(jiān)督表示學(xué)習(xí)和無(wú)監(jiān)督表示學(xué)習(xí)[8]，其中無(wú)監(jiān)督表示學(xué)習(xí)算法使用無(wú)標(biāo)注的數(shù)據(jù)集，通過(guò)將輸入數(shù)據(jù)變換到不同維度的向量空間來(lái)計(jì)算輸入數(shù)據(jù)的特征表示。常見(jiàn)算法包括局部線性嵌入[9]、獨(dú)立成分分析[10]、無(wú)監(jiān)督字典學(xué)習(xí)[11]以及受限玻爾茲曼機(jī)等。對(duì)于表示學(xué)習(xí)效果的評(píng)價(jià)，除了考察機(jī)器學(xué)習(xí)算法的效果外，Bengio等[12]對(duì)各種表示學(xué)習(xí)算法進(jìn)行了綜述，并討論了表示學(xué)習(xí)的目標(biāo)及評(píng)價(jià)標(biāo)準(zhǔn)。劉知遠(yuǎn)等[13]系統(tǒng)地介紹了知識(shí)表示學(xué)習(xí)的進(jìn)展和主要的表示學(xué)習(xí)算法。

圖數(shù)據(jù)的表示學(xué)習(xí)為使用機(jī)器學(xué)習(xí)算法提供了可能。Chen等[14]提出了一種根據(jù)有向圖的連接結(jié)構(gòu)，將有向圖中的節(jié)點(diǎn)表示為一維向量的方法。目前，圖數(shù)據(jù)表示學(xué)習(xí)算法[15]包括基于譜方法、基于最優(yōu)化、基于概率生成模型以及基于深度學(xué)習(xí)的方法。其中，基于譜方法的圖數(shù)據(jù)表示學(xué)習(xí)算法只考慮了網(wǎng)絡(luò)的結(jié)構(gòu)信息，難以引入網(wǎng)絡(luò)節(jié)點(diǎn)的屬性信息以擴(kuò)展應(yīng)用。基于最優(yōu)化的圖數(shù)據(jù)表示學(xué)習(xí)算法通常與特定的網(wǎng)絡(luò)數(shù)據(jù)處理需求相關(guān)，通用性較差。基于概率生成模型的圖數(shù)據(jù)表示學(xué)習(xí)算法要求網(wǎng)絡(luò)節(jié)點(diǎn)需具有文本屬性，同樣存在通用性差的問(wèn)題。

1.1 Deepwalk算法

Deepwalk算法是Bryan Perozzi等[16]提出的將Word2vec的思想用于圖節(jié)點(diǎn)表示學(xué)習(xí)的算法。Yang等證明Deepwalk算法相當(dāng)于將矩陣M分解為兩個(gè)矩陣的乘積，最終得到的節(jié)點(diǎn)特征向量可以由這兩個(gè)矩陣進(jìn)行拼接得到。Yu等[17]使用正則化的低秩矩陣分解來(lái)得到M的分解矩陣。同時(shí)，根據(jù)分解矩陣的原理，Yang等[18]將節(jié)點(diǎn)的屬性信息納入考慮之中，提出改進(jìn)Deepwalk的TADW模型。

Deepwalk算法在游走過(guò)程中，完全隨機(jī)選擇下一步游走的節(jié)點(diǎn)，沒(méi)有一個(gè)明確的目標(biāo)來(lái)指導(dǎo)游走，難以針對(duì)特定的學(xué)習(xí)目標(biāo)來(lái)選擇游走路徑。

1.2 Line算法

Line算法[19]通過(guò)定義兩種節(jié)點(diǎn)之間的相似性，并設(shè)計(jì)相應(yīng)的目標(biāo)函數(shù)，來(lái)優(yōu)化節(jié)點(diǎn)特征的學(xué)習(xí)。該算法的提出者分別使用兩種相似性指標(biāo)下得到的節(jié)點(diǎn)向量表示，以及兩種向量表示的拼接，與Deepwalk得到的節(jié)點(diǎn)向量表示作了對(duì)比實(shí)驗(yàn)，得到了較優(yōu)的節(jié)點(diǎn)標(biāo)簽預(yù)測(cè)結(jié)果。另外，Tang等提出的PTE算法[20]通過(guò)將文檔、詞語(yǔ)、標(biāo)簽組織成一個(gè)異構(gòu)網(wǎng)絡(luò)，以進(jìn)行文檔標(biāo)簽的預(yù)測(cè)任務(wù)，利用了Line算法的思想訓(xùn)練得到各種網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示，提高了預(yù)測(cè)的準(zhǔn)確度。

1.3 Node2vec算法

Node2vec算法[21]是另一種對(duì)Deepwalk算法中的隨機(jī)游走過(guò)程進(jìn)行改進(jìn)的算法，由Aditya等提出。Aditya同樣給出了兩種圖結(jié)構(gòu)中節(jié)點(diǎn)相似度的評(píng)價(jià)標(biāo)準(zhǔn)，分別叫做同質(zhì)性(homophily)[22]和結(jié)構(gòu)對(duì)等性(structural equivalence)[23]。Node2vec算法通過(guò)指定p,q兩個(gè)參數(shù)，給圖中的邊分配權(quán)值，通過(guò)權(quán)值的大小指導(dǎo)游走過(guò)程，實(shí)現(xiàn)了指定游走是更趨向于圖數(shù)據(jù)的深度優(yōu)先遍歷還是更趨向于圖數(shù)據(jù)的廣度優(yōu)先遍歷。通過(guò)多次嘗試，在多標(biāo)簽分類任務(wù)上，Node2vec取得了比Deepwalk和Line算法較好的預(yù)測(cè)效果。

2 基于標(biāo)簽信息的指導(dǎo)游走算法

2.1 算法實(shí)現(xiàn)

假設(shè)用G(V,E)表示一個(gè)圖，其中V代表節(jié)點(diǎn)，E代表邊[24]，算法設(shè)置一個(gè)參數(shù)p(0

設(shè)圖G(V,E)中有N個(gè)節(jié)點(diǎn)，當(dāng)前游走的節(jié)點(diǎn)為c，下面需要選擇下一個(gè)c的鄰居節(jié)點(diǎn)作為游走的節(jié)點(diǎn)。假設(shè)c節(jié)點(diǎn)有T個(gè)鄰居節(jié)點(diǎn)，表示為：

neighbors(c)={n1,n2,…,nT},0≤T

(1)

假設(shè)T個(gè)鄰居節(jié)點(diǎn)中有K個(gè)鄰居節(jié)點(diǎn)和c節(jié)點(diǎn)有共同的標(biāo)簽，表示為：

common(c)={m1,m2,…,mk},0≤K≤T

(2)

從上面可以看出，common(c)是neighbors(c)的子集。若c節(jié)點(diǎn)下一個(gè)游走的節(jié)點(diǎn)為d，則顯然d∈neighbors(c)。設(shè)定p參數(shù)，使得p=P(d∈common(c))，表示d屬于common(c)的概率，從而得到一組新的變量f(n)為c的每一個(gè)鄰居節(jié)點(diǎn)分配游走到的概率：

(3)

最后將這組概率值傳遞給Alias Method。

首先加載圖數(shù)據(jù)，記錄每一個(gè)圖節(jié)點(diǎn)對(duì)應(yīng)的鄰居節(jié)點(diǎn)以及每一個(gè)圖節(jié)點(diǎn)對(duì)應(yīng)的標(biāo)簽信息，然后根據(jù)每一個(gè)圖節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的標(biāo)簽信息和事先設(shè)定好的參數(shù)p的值，計(jì)算當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)被游走的概率，然后用Alias Method隨機(jī)選擇鄰居節(jié)點(diǎn)，每個(gè)鄰居節(jié)點(diǎn)被選中的概率等于計(jì)算的被游走的概率值。由概率值和其他設(shè)定好的游走的參數(shù)(如游走的路徑長(zhǎng)度等)開(kāi)始游走，會(huì)得到若干條路徑。之后調(diào)用Word2vec方法對(duì)這若干條游走路徑進(jìn)行訓(xùn)練，將每個(gè)圖節(jié)點(diǎn)表示成向量。最后對(duì)圖節(jié)點(diǎn)進(jìn)行多標(biāo)簽分類，檢驗(yàn)算法的分類效果。分類效果越好，圖節(jié)點(diǎn)向量表示方法的有效性越好。

在第二步中，根據(jù)當(dāng)前節(jié)點(diǎn)和鄰居節(jié)點(diǎn)的標(biāo)簽信息，以及p參數(shù)的值，得到了每個(gè)節(jié)點(diǎn)被游走的概率值。然后將這組概率值用于Alias Method的alias_setup方法，建立alias_nodes變量。alias_nodes變量是一種key-value的數(shù)據(jù)結(jié)構(gòu)，key代表圖中的所有節(jié)點(diǎn)，value與該節(jié)點(diǎn)的鄰居列表等長(zhǎng)，是對(duì)游走概率序列進(jìn)行調(diào)整之后的兩個(gè)概率序列。在Alias Method算法的alias_draw方法中通過(guò)使用隨機(jī)數(shù)與這兩個(gè)概率序列進(jìn)行比較，將返回一個(gè)下標(biāo)索引，然后選取對(duì)應(yīng)該下標(biāo)索引的鄰居節(jié)點(diǎn)作為下一個(gè)游走的節(jié)點(diǎn)。當(dāng)重復(fù)多次地調(diào)用alias_draw方法時(shí)，返回的下標(biāo)索引的概率分布將符合指定的被游走的概率值序列。為每一個(gè)鄰居節(jié)點(diǎn)計(jì)算被游走到的概率的偽代碼如算法2所示。游走部分的偽代碼如算法1所示。

算法1：probability_walk(G，start_node，path_length, alias_nodes)

Input： Graph:G(V,E), the node which path starts from: start_node,

The specified length of path: path_length

The structure of alias method: alias_nodes

Output：path_list

path_list append start_node

current_node=start_node

while the length of path_list < path_length

neighbors_list=G[current_node]

index= alias_draw(alias_nodes[current_node][0], alias_nodes[current_node][1])

next_node=neighbors_list[index]

path_list append next_node

current_node=next_node

算法2：generate_probability(G，T，p)

input： Graph:G(V,E), Tags info:T(V,tag_list), the specified percentage of tags info:p

Output：alias_nodes

for each node inV

neighbors_list=G[node]

Initial probability_list with zeros,its length equals to neighbors_list

for each neighbor in neighbors_list

ifT[node] andT[neighbor] has common element

assign the element in probability_list accordingly to one

count+=1

for each element in probability_list

if element==1

change the element top/count

else

change the element to (1-p)/(length_of_neighbors-count)

alias_nodes[node] = alias_setup(probability_list)

2.2 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)中使用了blogcatalog數(shù)據(jù)集，作為在多標(biāo)簽分類問(wèn)題上的常用數(shù)據(jù)集。在blogcatalog數(shù)據(jù)集中，節(jié)點(diǎn)代表博客作者，共包含10 312個(gè)節(jié)點(diǎn)。圖中的邊代表兩個(gè)博客作者的社交關(guān)系。圖中節(jié)點(diǎn)的標(biāo)簽是博客作者發(fā)表博客的內(nèi)容類別，平均每一個(gè)博客作者包含1.6個(gè)標(biāo)簽。

在標(biāo)簽分類結(jié)果的評(píng)價(jià)上，使用F1函數(shù)進(jìn)行比較。F1函數(shù)是對(duì)分類結(jié)果的召回率和正確率的加權(quán)平均，計(jì)算公式表示為：

(4)

而對(duì)于多標(biāo)簽分類問(wèn)題，考慮到每一個(gè)類別標(biāo)簽在數(shù)量上的不平衡性，需要對(duì)每一個(gè)類別上的F1函數(shù)再進(jìn)行一個(gè)加權(quán)平均。對(duì)F1函數(shù)的加權(quán)平均方式又可以分為“micro”、“macro”、“samples”和“weighted”四種，分別定義為“米克”、“麥克”、“賽普”以及“威特”。其中，“米克”方式從整體上統(tǒng)計(jì)每一個(gè)類別正確和錯(cuò)誤預(yù)測(cè)的次數(shù)；“麥克”方式對(duì)每一個(gè)類別標(biāo)簽進(jìn)行簡(jiǎn)單的求平均，沒(méi)有考慮標(biāo)簽數(shù)量上的不平衡性；“賽普”和“威特”方式分別從每一次預(yù)測(cè)的角度和每一個(gè)標(biāo)簽的角度對(duì)預(yù)測(cè)的F1結(jié)果進(jìn)行了加權(quán)平均。本次實(shí)驗(yàn)結(jié)果的分析將用這四種方式分別進(jìn)行考量。

在blogcatalog數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖1所示。其中四張圖分別展示了多標(biāo)簽分類結(jié)果使用F1函數(shù)在四種評(píng)價(jià)方法-“米克”、“麥克”、“賽普”和“威特”下的預(yù)測(cè)效果。每一張圖上，橫軸表示在多標(biāo)簽分類時(shí)訓(xùn)練數(shù)據(jù)所占的比例，圖中的五條折線分別顯示了該算法中p參數(shù)取值0，0.2，0.3，0.4以及0.8時(shí)對(duì)應(yīng)的預(yù)測(cè)結(jié)果的提升情況。當(dāng)p取0時(shí)，表示在游走過(guò)程中，基于標(biāo)簽信息的指導(dǎo)作用為零，即完全的隨機(jī)游走。

(a)米克的預(yù)測(cè)效果

(b)麥克的預(yù)測(cè)效果

(c)賽普的預(yù)測(cè)效果

(d)威特的預(yù)測(cè)效果

從圖1可以看到，隨著參數(shù)p的逐漸變大，預(yù)測(cè)效果有了明顯提升。當(dāng)p取值0.2時(shí)，在“麥克”和“賽普”評(píng)價(jià)方式下，其預(yù)測(cè)效果與隨機(jī)游走效果基本相當(dāng)。當(dāng)p=0.2且訓(xùn)練數(shù)據(jù)低于50%時(shí)，在“米克”評(píng)價(jià)方式下，預(yù)測(cè)效果相比于隨機(jī)游走的預(yù)測(cè)效果低了0.01，表明從總體而言，指定參數(shù)p的取值覆蓋到的標(biāo)簽信息的比例低于隨機(jī)游走時(shí)覆蓋到的標(biāo)簽信息的比例。但在“威特”評(píng)價(jià)方式下，預(yù)測(cè)效果相比于隨機(jī)游走的預(yù)測(cè)效果已經(jīng)有了較大的提高，表明從每一個(gè)標(biāo)簽的角度，通過(guò)較少的標(biāo)簽指導(dǎo)信息，游走過(guò)程中在兼顧遍歷整個(gè)圖結(jié)構(gòu)的同時(shí)，算法已經(jīng)開(kāi)始傾向于游走與本次多標(biāo)簽分類任務(wù)關(guān)系更密切，特征更顯著的圖節(jié)點(diǎn)，從而在預(yù)測(cè)結(jié)果上體現(xiàn)出了正確率的提升。

圖2是游走的參數(shù)(包括向量表示的維度、游走的次數(shù))以及訓(xùn)練數(shù)據(jù)的比例在使用標(biāo)簽信息指導(dǎo)游走前后對(duì)標(biāo)簽預(yù)測(cè)結(jié)果影響的對(duì)比圖。算法中的標(biāo)簽指導(dǎo)信息參數(shù)p取值0.3，預(yù)測(cè)結(jié)果使用F1評(píng)價(jià)標(biāo)準(zhǔn)。

其中，圖2(a)、圖2(b)分別顯示了使用指導(dǎo)游走前后隨著向量表示維度(16, 32, 64, 128, 256)的增加，不同訓(xùn)練數(shù)據(jù)占比(0.1, 0.2, 0.5, 0.9)的標(biāo)簽預(yù)測(cè)結(jié)果。圖2(c)、圖2(d)分別顯示了使用指導(dǎo)游走前后隨著游走次數(shù)(1, 3, 10, 30, 50, 90)的增加，不同訓(xùn)練數(shù)據(jù)占比(0.1, 0.2, 0.5, 0.9)的標(biāo)簽預(yù)測(cè)結(jié)果。可以看到，隨著游走次數(shù)從1次增加到10次，預(yù)測(cè)的準(zhǔn)確率迅速提升。在使用標(biāo)簽指導(dǎo)之后，不同的訓(xùn)練數(shù)據(jù)比例下，預(yù)測(cè)效果均超過(guò)隨機(jī)游走的預(yù)測(cè)效果。隨著游走次數(shù)超過(guò)10次，由過(guò)多游走帶來(lái)的噪聲使得預(yù)測(cè)效果有所下降，如圖2(c)中訓(xùn)練比例0.1時(shí)的結(jié)果。但可以看到，當(dāng)訓(xùn)練數(shù)據(jù)的比例增大時(shí)，這種下降得到了補(bǔ)償，如圖2(c)中訓(xùn)練比例大于0.2時(shí)的結(jié)果基本持平或緩慢提升。在使用標(biāo)簽指導(dǎo)后，過(guò)多游走帶來(lái)的噪聲對(duì)標(biāo)簽特征的影響更加嚴(yán)重，可以看到圖2(d)中，訓(xùn)練比例0.2時(shí)預(yù)測(cè)結(jié)果仍然有所下降。因此，合適的游走次數(shù)對(duì)于標(biāo)簽指導(dǎo)游走算法的效果同樣重要。

(a)指導(dǎo)游走前隨維度變化趨勢(shì)

(b)指導(dǎo)游走后隨維度變化趨勢(shì)

(c)指導(dǎo)游走前隨游走次數(shù)變化趨勢(shì)

(d)指導(dǎo)游走后隨游走次數(shù)變化趨勢(shì)

3 結(jié)束語(yǔ)

針對(duì)圖節(jié)點(diǎn)的多標(biāo)簽分類任務(wù)，設(shè)計(jì)了一種基于標(biāo)簽信息指導(dǎo)游走的圖節(jié)點(diǎn)表示學(xué)習(xí)算法。該算法通過(guò)設(shè)置一個(gè)游走參數(shù)p，可以做到在游走過(guò)程中對(duì)有共同標(biāo)簽的鄰居進(jìn)行傾向性可調(diào)的選擇，達(dá)到了在學(xué)習(xí)圖節(jié)點(diǎn)的整個(gè)連接關(guān)系和學(xué)習(xí)節(jié)點(diǎn)之間的標(biāo)簽相似性特征的平衡。最后，實(shí)驗(yàn)對(duì)比了在使用標(biāo)簽指導(dǎo)游走前后以及不同的參數(shù)p和訓(xùn)練數(shù)據(jù)比例下，預(yù)測(cè)效果的變化情況。使用標(biāo)簽指導(dǎo)游走之后，預(yù)測(cè)效果提升較顯著。同時(shí)，實(shí)驗(yàn)也對(duì)比了在使用標(biāo)簽指導(dǎo)游走前后，其他游走參數(shù)(包括游走次數(shù)、節(jié)點(diǎn)向量的維度和訓(xùn)練數(shù)據(jù)占比)對(duì)標(biāo)簽分類的影響情況。

在Node2vec的基礎(chǔ)上考慮了標(biāo)簽信息，但隨著機(jī)器學(xué)習(xí)算法的發(fā)展，對(duì)表示學(xué)習(xí)的特征提取有了更高的要求，節(jié)點(diǎn)表示的方法有待進(jìn)一步研究。