基于Node2vec的改進算法的研究

杜陽陽，李華康，李 濤

(南京郵電大學 計算機學院，江蘇 南京 210046)

0 引 言

信息網絡在現實世界中無處不在，規模從幾百個到幾百億個不等[1]。鄰接矩陣、鄰接表等是常用的數據表示方法，但在計算效率以及數據稀疏的問題上往往不能達到很好的效果。隨著深度學習的發展和深入研究，圖數據的表示學習為圖數據的挖掘問題提供了新的思路。節點表示成向量可以應用于多個領域，如可視化[2]、節點分類[3]、鏈路預測[4]以及推薦[5]等。

在圖數據挖掘中，評價節點表示算法效果的主要方式是對節點進行多標簽分類[6]。和每個節點只有一個標簽的問題相比，顯然每個節點有多個標簽的問題要更為復雜。目前，基于游走的圖節點的表示學習算法都使用在多標簽分類的結果來評價算法的有效性。

對于圖節點的多標簽分類問題，文中在隨機游走算法的基礎上考慮了標簽信息的指導作用。該算法設置了一個游走參數，使游走時傾向于走和當前節點有共同標簽的鄰居節點，而不是隨機游走，并通過實驗進行驗證。

1 國內外研究現狀

對數據進行分析需要將數據表示成計算機能夠識別的形式[7]。表示學習算法分為監督表示學習和無監督表示學習[8]，其中無監督表示學習算法使用無標注的數據集，通過將輸入數據變換到不同維度的向量空間來計算輸入數據的特征表示。常見算法包括局部線性嵌入[9]、獨立成分分析[10]、無監督字典學習[11]以及受限玻爾茲曼機等。對于表示學習效果的評價，除了考察機器學習算法的效果外，Bengio等[12]對各種表示學習算法進行了綜述，并討論了表示學習的目標及評價標準。劉知遠等[13]系統地介紹了知識表示學習的進展和主要的表示學習算法。

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

1.1 Deepwalk算法

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

Deepwalk算法在游走過程中，完全隨機選擇下一步游走的節點，沒有一個明確的目標來指導游走，難以針對特定的學習目標來選擇游走路徑。

1.2 Line算法

Line算法[19]通過定義兩種節點之間的相似性，并設計相應的目標函數，來優化節點特征的學習。該算法的提出者分別使用兩種相似性指標下得到的節點向量表示，以及兩種向量表示的拼接，與Deepwalk得到的節點向量表示作了對比實驗，得到了較優的節點標簽預測結果。另外，Tang等提出的PTE算法[20]通過將文檔、詞語、標簽組織成一個異構網絡，以進行文檔標簽的預測任務，利用了Line算法的思想訓練得到各種網絡節點的向量表示，提高了預測的準確度。

1.3 Node2vec算法

Node2vec算法[21]是另一種對Deepwalk算法中的隨機游走過程進行改進的算法，由Aditya等提出。Aditya同樣給出了兩種圖結構中節點相似度的評價標準，分別叫做同質性(homophily)[22]和結構對等性(structural equivalence)[23]。Node2vec算法通過指定p,q兩個參數，給圖中的邊分配權值，通過權值的大小指導游走過程，實現了指定游走是更趨向于圖數據的深度優先遍歷還是更趨向于圖數據的廣度優先遍歷。通過多次嘗試，在多標簽分類任務上，Node2vec取得了比Deepwalk和Line算法較好的預測效果。

2 基于標簽信息的指導游走算法

2.1 算法實現

假設用G(V,E)表示一個圖，其中V代表節點，E代表邊[24]，算法設置一個參數p(0

設圖G(V,E)中有N個節點，當前游走的節點為c，下面需要選擇下一個c的鄰居節點作為游走的節點。假設c節點有T個鄰居節點，表示為：

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

(1)

假設T個鄰居節點中有K個鄰居節點和c節點有共同的標簽，表示為：

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

(2)

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

(3)

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

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

在第二步中，根據當前節點和鄰居節點的標簽信息，以及p參數的值，得到了每個節點被游走的概率值。然后將這組概率值用于Alias Method的alias_setup方法，建立alias_nodes變量。alias_nodes變量是一種key-value的數據結構，key代表圖中的所有節點，value與該節點的鄰居列表等長，是對游走概率序列進行調整之后的兩個概率序列。在Alias Method算法的alias_draw方法中通過使用隨機數與這兩個概率序列進行比較，將返回一個下標索引，然后選取對應該下標索引的鄰居節點作為下一個游走的節點。當重復多次地調用alias_draw方法時，返回的下標索引的概率分布將符合指定的被游走的概率值序列。為每一個鄰居節點計算被游走到的概率的偽代碼如算法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 實驗驗證

實驗中使用了blogcatalog數據集，作為在多標簽分類問題上的常用數據集。在blogcatalog數據集中，節點代表博客作者，共包含10 312個節點。圖中的邊代表兩個博客作者的社交關系。圖中節點的標簽是博客作者發表博客的內容類別，平均每一個博客作者包含1.6個標簽。

在標簽分類結果的評價上，使用F1函數進行比較。F1函數是對分類結果的召回率和正確率的加權平均，計算公式表示為：

(4)

而對于多標簽分類問題，考慮到每一個類別標簽在數量上的不平衡性，需要對每一個類別上的F1函數再進行一個加權平均。對F1函數的加權平均方式又可以分為“micro”、“macro”、“samples”和“weighted”四種，分別定義為“米克”、“麥克”、“賽普”以及“威特”。其中，“米克”方式從整體上統計每一個類別正確和錯誤預測的次數；“麥克”方式對每一個類別標簽進行簡單的求平均，沒有考慮標簽數量上的不平衡性；“賽普”和“威特”方式分別從每一次預測的角度和每一個標簽的角度對預測的F1結果進行了加權平均。本次實驗結果的分析將用這四種方式分別進行考量。

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

(a)米克的預測效果

(b)麥克的預測效果

(c)賽普的預測效果

(d)威特的預測效果

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

圖2是游走的參數(包括向量表示的維度、游走的次數)以及訓練數據的比例在使用標簽信息指導游走前后對標簽預測結果影響的對比圖。算法中的標簽指導信息參數p取值0.3，預測結果使用F1評價標準。

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

(a)指導游走前隨維度變化趨勢

(b)指導游走后隨維度變化趨勢

(c)指導游走前隨游走次數變化趨勢

(d)指導游走后隨游走次數變化趨勢

3 結束語

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

在Node2vec的基礎上考慮了標簽信息，但隨著機器學習算法的發展，對表示學習的特征提取有了更高的要求，節點表示的方法有待進一步研究。