AttrHIN2Vec:一種新型異質信息網絡表示學習模型

文鵬，李青，熊友

（重慶大學計算機學院，重慶 400044）

0 引言

信息網絡，例如社交與通信網絡、論文引用網絡、航線網絡,在現實世界中無處不在[1]。通常，這些信息網絡的規模比較大，給網絡數據分析帶來了巨大的挑戰。一種稱為網絡嵌入（也稱為網絡表示學習）的研究方法在學術界與工業界已經引起了越來越多的關注。網絡嵌入的核心思想是將網絡嵌入到低維空間，并將每個結點表示為低維特征向量。研究表明，網絡嵌入在許多網絡分析任務中表現優異，例如可視化、節點分類、鏈路預測和實體檢索[2-8]。

在過去的幾年中，許多文獻從不同角度對網絡嵌入進行了改進。當前比較流行的方式是將自然語言處理技術應用于網絡嵌入，例如，NLP中著名的Word2Vec 模 型[9,10]。DeepWalk[2]和 Node2Vec[11]模 型 在隨機游走后采用Word2Vec模型（Skip-Gram）。LINE[1]專注于一階相似性和二階相似性來表示網絡。

然而，大多數傳統的網絡嵌入僅僅關注同質網絡[1,11]。同質網絡只能表示單一類型的節點和關系，這意味著它具有天然的局限性。傳統模型在處理不同類型的結點和關系時表現不佳，異質結點的表示難以區分[12]。此外，模型[1,11]沒有考慮節點的屬性信息，這可能會損失一部分有意義的信息。事實上，大量的社交與信息網絡具有結點類型豐富，結點之間的關系存在多樣性的特點[13]，這樣的網絡通常被描述為異質網絡。Dong Y[12]提出了Metapath2Vec和Metapath2Vec++來解決異質網絡表示學習帶來的挑戰，但它忽略了每個結點豐富的屬性信息，并且沒有關注元路徑的權重信息。

在本文中，我們提出了一種名為“AttrHin2Vec”的網絡表示學習模型，旨在獲取異質信息網絡（HIN）的豐富信息。我們首先采用帶權重元路徑的隨機游走來生成結點序列；然后我們提出了一個名為“AttrSkip-Gram”的帶屬性異質Skip-Gram模型來嵌入結點；最后，我們獲得了包括目標結點的結點屬性信息的完整特征向量表示。通過這種方式，我們可以充分發現潛在的結點嵌入信息，進而為網絡分析任務做出貢獻。

總而言之，我們的工作做出了以下貢獻：

●我們提出了一種名為“AttrHIN2Vec”的新型網絡表示學習模型，它保留了異質網絡的結點屬性信息與權重信息。

●我們采用MovieLens-1M數據集進行了多標簽分類實驗。與 DeepWalk/node2vec，LINE，Metapath2Vec等最新網絡表示學習模型相比，我們的模型效果更佳。

1 相關工作

最近，網絡表示學習在學術界和工業界引起了廣泛關注。它起源于應用于網絡分析任務的潛在因子模型[14,15]，例如，用于推薦系統、節點分類的分解模型。隨著深度學習技術的發展，越來越多的基于神經網絡的表述學習模型被提出。一個典型的例子是Word2Vec，它由一個雙層神經網絡組成，旨在學習自然語言處理中單詞的分布式表示[9,10]。基于Word2Vec，Perozzi等提出了DeepWalk[2]。DeepWalk通過在網絡中結點的隨機游走形成一個序列，相當于詞嵌入中文檔的句子，然后將序列作為Skip-Gram模型的輸入，最終得到結點的低維向量表示。此后，為了保留一階和二階相似性，Tang等人[1]提出了名為LINE的大規模信息網路嵌入方法。文獻[11]中提出的Node2Vec模型在鄰近節點的多樣性方面表現良好。Node2Vec模型通過平衡廣度優先采樣與深度優先采樣，生成目標節點序列。然后，通過最大化保留的網絡鄰近節點的相似度得到最終的節點表示。

然而，上述模型都是基于同質網絡。由于異質信息網絡在現實世界中具有更好的描述各種網絡的能力，因此基于異構網絡的網絡嵌入日益引起重視。Yuxiao Dong等[12]研究了異質學習網絡中的表示學習問題，通過改進隨機游走策略和Skip-Gram算法，提出了基于元路徑的隨機游走和異質Skip-Gram算法，建立了Metapath2Vec模型。大量實驗表明，Metapath2Vec在數據挖掘任務上的性能優于當前大多數異質信息網絡表示學習模型。

本文通過設計AttrHIN2Vec模型，通過利用基于元路徑的隨機游走的結點屬性信息和權重信息來捕獲大規模異構網絡中的潛在特征向量，進一步推動了這一方向的研究。

2 問題定義

文獻[13]簡要介紹了異質網絡中的表示學習問題，我們據此提出屬性異質網絡的定義以及學習問題。

定義1屬性異質信息網絡表示為G=(V,E,A,T)，其中，V代表網絡中的結點集合，E代表結點相連的邊集合，T為結點類型的集合，并且有|TV|+|TE|＞2。對于任意一個結點v，存在一個映射函數φ(v):V→TV，TV代表結點類型。同樣的，對于任意一條邊e，存在一個映射函數φ(e):E→TE，TE代表邊類型。A為結點屬性集合，即A={a1…,am}。對于任意結點vi∈V，均關聯一個屬性向量[a1(vi)…,am(vi)]，aj(vi)代表結點vi在屬性aj上的取值。

屬性異質信息網絡表示學習：給定屬性網絡G，將網絡中結點與屬性都轉化為向量的表示形式，即學習函數，其中VV是指結點向量，dV為結點維數；而VA則是屬性向量，dA為屬性維數。和通常的網絡表示學習一樣，在轉化后的結點向量和屬性向量需要滿足：低維連續、拓撲結構完整性和屬性完整性。

3 AttrHin2Vec模型

本文提出的屬性異質信息網絡表示學習模型Attr-HIN2vec包括兩個主要模塊，首先是基于帶權重元路徑的隨機游走，用于生成路徑序列；其次，在異質Skip-Gram結點向量更新的基礎上加入屬性向量的更新，提出屬性異質AttrSkip-Gram。

3. 1 帶權重元路徑隨機游走

傳統的元路徑隨機游走算法忽略了元路徑的權重信息，因此，本文采用帶權重的元路徑隨機游走。對于給定的異構網絡G=(V,E,A,T)和元路徑P:，在第i步時的轉移概率如下：

本文對于異質信息網絡中的每個結點，依據定義的元路徑，在權重概率的指導下都構造k條長度為l的路徑序列，然后將這些路徑序列當作文檔訓練集中的句子，那么結點的相鄰結點則可以看作是對應的上下文結點。

3. 2 帶屬性Skip-Gram模型

本文提出帶屬性的Skip-Gram（簡稱AttrSkip-Gram）向量更新模塊分別在metapath2vec的Skip-gram模型的更新模塊基礎上進行改進。利用帶權重元路徑隨機游走策略在屬性異質信息網絡G=(V,E,A,T)中生成多條路徑序列之后，就可以將這些路徑序列當成文本中的句子，選取某條路徑中一個隨機結點v∈V就等同于選取文本中的單詞，然后將v前后大小為τ的窗口定義為結點的上下文Nt(v)，t∈TV，AttrSkip-Gram是根據Nt(v)中各個結點的向量更新中心結點v的向量。基于負采樣的思想，在計算v的向量時，還需要另外進行負采樣，即隨機選取若干v以外的結點，記為NEG(v)。AttrSkip-Gram更新的目標是使得中心結點v的向量近似于其上下文Nt(v)中各結點的向量，并使Nt(v)中各結點的向量遠離負樣本NEG(v)中的結點。由于在異質信息網絡中，還需要考慮結點的類型，所以希望最大化如下目標函數：

其中,

其中，M為結點與屬性之間的映射關系矩陣，Mv表示結點v擁有的屬性集合，為屬性i的輸出層向量表示，為屬性i在投影層的輔助向量。因此，的物理意義為結點v擁有的屬性的輔助向量之和，為結點ct所擁有屬性的輸出層向量之和。

在式（3）中，對于結點 v，正采樣時，ct=u，Lu(ct)=1，公式前半部分有效，最大化 f()v則要求結點ct的屬性向量與中心詞的屬性向量盡可能相似；負采樣時，Lu(ct)=0，公式后半部分有效，則要求與中心詞的屬性向量盡可能不相似。

將其擴展到整個網絡圖G，整體的目標為最大化函數：

取對數后得到公式：

更新公式

同樣的，（12）中對于輔助屬性向量vAi的更新為：

3. 3 AttrHIN 2Vec算法

AttrHIN2vec模型及AttrSkip-Gram更新相關向量的過程如下：首先初始化結點向量XV與屬性向量XA，以及它們在投影層的輔助向量XV'與 XA'（1-2行），對于每個結點，都要生成k條帶權隨機游走路徑（3-5行），其中，第5行為隨機游走路徑生成函數。然后依次根據各條路徑中的節點及其上下文進行向量更新（6-9行），其中，第8行為AttrSkipGram函數。

第13-19行是隨機游走路徑函數genRandom-Walk，對于一個加權異質信息網絡G，以及元路徑P，以r為當前結點，生成長度為l的路徑。

第20-33行是AttrSkipGram函數，用于更新相關向量。第22行中的eV表示上下文結點對于當前計算的中心結點或負采樣結點u的更新量之和，第25行中將eV的值更新到各個上下文結點的輔助向量上；同樣的，為上下文結點所包含的屬性對于結點u的屬性的更新量之和，26-28行中根據eA更新相關的屬性在投影層的輔助向量。

AttrHIN2Vec算法

Input：

屬性異質信息網絡G=(V,E,A,T)；元路徑模式P；每個結點隨機游走路徑數k；隨機游走路徑長度l；結點向量維數dV，屬性向量維數dA，鄰居結點數量τ

Output：

結 點 向 量 矩 陣XV∈R|V|×dV，屬性向量矩陣XA∈R|A|×dA

4 實驗

本文通過多標簽分類的實驗來驗證在Attr-HIN2Vec模型網絡表示學習的效果。在本實驗中，我們使用MovieLens-1M數據集[16]。MovieLens-1M數據集包含6040個用戶，3883個電影和100209個電影評級，它們由用戶表（users.dat），電影表（movies.dat）和評級表（ratings.dat）組成。

4. 1 實驗設置

本文的分類任務是對電影的類型完成分類，由于在MovieLens-1M的數據集中，同一部電影可能會有好幾種類型，在本實驗中對于多種類型，隨機選擇其中的一個類型來做實驗。我們比較的對象主要是其他網絡表示學習的方法，包括以下幾個：

（1）DeepWalk[2]/node2vec[11]：node2vec通過 p、q兩個參數來控制隨機游走生成的路徑，調整p可以減少來回重復游走的情況，q可以控制隨機游走是以深度優先搜索（q＜1）還是以廣度優先搜索（q＞1）的形式進行隨機游走。當p=1，q=1時，DeepWalk可以視作node2vec的一個特例。本實驗即設置p=1，q=1。

（2）LINE[1]：本文使用考慮一階相似度和二階相似度LINE的改進版本進行實驗對比。

（3）Metapath2Vec[14]：在 Metapath2Vec中，采用元路徑（UMU，用戶-電影-用戶）的隨機游走的異質信息網絡進行網絡表示學習。

（4）AttrHIN2vec：本文提出的在 Metapath2Vec模型的基礎上，通過帶權重元路徑（UMU，用戶-電影-用戶）隨機游走方法，在異質的Skip-Gram模型上增加結點屬性進行訓練。訓練結果的結點用d維向量表示，前面維的向量是通過結點在異質信息網絡中的拓撲結構訓練得到的，而后面的維向量是將結點的所有屬性向量取平均值。

本文使用如下相同的參數進行對比，另外還對本文提出的加權帶屬性的異質信息網絡中的參數進行敏感度驗證。

（1）每個結點為起始結點的游走次數 w為1000次；

（2）每次游走的長度l為100；

（3）訓練出來的向量維度d為128；

（4）上下文窗口大小k為7；

（5）負采樣的詞的數量為5。

本文采用準確率和召回率的調和平均F值（FMeasure）進行評價。

4. 2 多標簽分類實驗

由于電影可能屬于多種類型，因此在本實驗中構建異質信息網絡時，我們會隨機選擇一種類型作為結點的標簽。首先，我們使用完整數據集進行結點表示學習。然后，將邏輯回歸的訓練集從10%到90%進行劃分，將剩余的作為測試集，每個比例的訓練集重復進行10次實驗，取平均的F值進行比較。

表1中列出了多標簽分類結果。簡而言之，提出的AttrHIN2Vec比其他方法表現更好。例如，將10%結點作為訓練數據，AttrHIN2Vec在DeepWalk/node2vec，LINE上的F值實現了0.59-0.71的改進。結果表明，metapath2vec和AttrHIN2Vec比其他模型表現更好，特別是當訓練數據集較小時。

總之，通過多標簽分類實驗，AttrHIN2Vec比目前最先進的方法表現更好。AttrHIN2Vec的優勢在于其在進行基于元路徑的隨機游走時，考慮了結點屬性信息和以及元路徑的權重信息。

表1 多標簽分類結果

4. 3 參數敏感度驗證

在基于Skip-Gram的表示學習中有幾個常見參數（參見章節4.1）。下面將對AttrHIN2Vec模型中的參數進行敏感度分析。圖1顯示了當選擇一個可變參數后，其他參數一定的分類結果的F值。分別進行了三個類別的實驗，即圖中邊帶權重結點無屬性的情況、無權重有屬性及帶權重有屬性。

圖1（a）和圖1（b）中每個根結點游走的次數與游走路徑的長度在三類實驗中，與分類的效果都是成正相關的，分類性能隨著游走次數和路徑長度的增加而收斂，游走次數在1000次之后收斂，而游走路徑長度在100之后收斂，總體來看，帶權重有屬性在同等條件下比其他兩類實驗的效果更好。當w和l較小時，屬性信息起著重要作用。當l達到一定量時，權重信息對分類的貢獻更大。在圖1（c）中，顯示維數d對分類幾乎沒有影響。圖1（d）反映了在上下文窗口數量設定方面，在7之后的效果也越來越差。

5 結語

本文重點研究異質信息網絡中的表示學習。現有的網絡表示學習工作較少考慮網絡的屬性信息和權重信息。為了填補這一空白，我們提出了一種新型的模型：屬性異質信息網絡向量表示模型（AttrHIN2Vec）。它可以用來捕獲網絡中的潛在特征。實驗表明，AttrHIN2Vec學到的潛在特征表示可以改善網絡分析任務，如多標簽分類。

圖1 分類中的參數敏感度驗證

我們計劃在以下兩個方向繼續我們的研究。隨著不同類型節點和關系的增加，構建屬性異質信息網絡的成本將非常高。因此，提高構建效率尤為關鍵。此外，在構建網絡時，屬性的選擇是一個值得研究的問題。