文鵬，李青，熊友

（重慶大學(xué)計算機學(xué)院，重慶 400044）

0 引言

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

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

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

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

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

●我們提出了一種名為“AttrHIN2Vec”的新型網(wǎng)絡(luò)表示學(xué)習(xí)模型，它保留了異質(zhì)網(wǎng)絡(luò)的結(jié)點屬性信息與權(quán)重信息。

●我們采用MovieLens-1M數(shù)據(jù)集進行了多標(biāo)簽分類實驗。與 DeepWalk/node2vec，LINE，Metapath2Vec等最新網(wǎng)絡(luò)表示學(xué)習(xí)模型相比，我們的模型效果更佳。

1 相關(guān)工作

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

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

本文通過設(shè)計AttrHIN2Vec模型，通過利用基于元路徑的隨機游走的結(jié)點屬性信息和權(quán)重信息來捕獲大規(guī)模異構(gòu)網(wǎng)絡(luò)中的潛在特征向量，進一步推動了這一方向的研究。

2 問題定義

文獻[13]簡要介紹了異質(zhì)網(wǎng)絡(luò)中的表示學(xué)習(xí)問題，我們據(jù)此提出屬性異質(zhì)網(wǎng)絡(luò)的定義以及學(xué)習(xí)問題。

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

屬性異質(zhì)信息網(wǎng)絡(luò)表示學(xué)習(xí)：給定屬性網(wǎng)絡(luò)G，將網(wǎng)絡(luò)中結(jié)點與屬性都轉(zhuǎn)化為向量的表示形式，即學(xué)習(xí)函數(shù)，其中VV是指結(jié)點向量，dV為結(jié)點維數(shù)；而VA則是屬性向量，dA為屬性維數(shù)。和通常的網(wǎng)絡(luò)表示學(xué)習(xí)一樣，在轉(zhuǎn)化后的結(jié)點向量和屬性向量需要滿足：低維連續(xù)、拓?fù)浣Y(jié)構(gòu)完整性和屬性完整性。

3 AttrHin2Vec模型

本文提出的屬性異質(zhì)信息網(wǎng)絡(luò)表示學(xué)習(xí)模型Attr-HIN2vec包括兩個主要模塊，首先是基于帶權(quán)重元路徑的隨機游走，用于生成路徑序列；其次，在異質(zhì)Skip-Gram結(jié)點向量更新的基礎(chǔ)上加入屬性向量的更新，提出屬性異質(zhì)AttrSkip-Gram。

3. 1 帶權(quán)重元路徑隨機游走

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

本文對于異質(zhì)信息網(wǎng)絡(luò)中的每個結(jié)點，依據(jù)定義的元路徑，在權(quán)重概率的指導(dǎo)下都構(gòu)造k條長度為l的路徑序列，然后將這些路徑序列當(dāng)作文檔訓(xùn)練集中的句子，那么結(jié)點的相鄰結(jié)點則可以看作是對應(yīng)的上下文結(jié)點。

3. 2 帶屬性Skip-Gram模型

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

其中,

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

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

將其擴展到整個網(wǎng)絡(luò)圖G，整體的目標(biāo)為最大化函數(shù)：

取對數(shù)后得到公式：

更新公式

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

3. 3 AttrHIN 2Vec算法

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

第13-19行是隨機游走路徑函數(shù)genRandom-Walk，對于一個加權(quán)異質(zhì)信息網(wǎng)絡(luò)G，以及元路徑P，以r為當(dāng)前結(jié)點，生成長度為l的路徑。

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

AttrHIN2Vec算法

Input：

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

Output：

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

4 實驗

本文通過多標(biāo)簽分類的實驗來驗證在Attr-HIN2Vec模型網(wǎng)絡(luò)表示學(xué)習(xí)的效果。在本實驗中，我們使用MovieLens-1M數(shù)據(jù)集[16]。MovieLens-1M數(shù)據(jù)集包含6040個用戶，3883個電影和100209個電影評級，它們由用戶表（users.dat），電影表（movies.dat）和評級表（ratings.dat）組成。

4. 1 實驗設(shè)置

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

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

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

（3）Metapath2Vec[14]：在 Metapath2Vec中，采用元路徑（UMU，用戶-電影-用戶）的隨機游走的異質(zhì)信息網(wǎng)絡(luò)進行網(wǎng)絡(luò)表示學(xué)習(xí)。

（4）AttrHIN2vec：本文提出的在 Metapath2Vec模型的基礎(chǔ)上，通過帶權(quán)重元路徑（UMU，用戶-電影-用戶）隨機游走方法，在異質(zhì)的Skip-Gram模型上增加結(jié)點屬性進行訓(xùn)練。訓(xùn)練結(jié)果的結(jié)點用d維向量表示，前面維的向量是通過結(jié)點在異質(zhì)信息網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)訓(xùn)練得到的，而后面的維向量是將結(jié)點的所有屬性向量取平均值。

本文使用如下相同的參數(shù)進行對比，另外還對本文提出的加權(quán)帶屬性的異質(zhì)信息網(wǎng)絡(luò)中的參數(shù)進行敏感度驗證。

（1）每個結(jié)點為起始結(jié)點的游走次數(shù) w為1000次；

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

（3）訓(xùn)練出來的向量維度d為128；

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

（5）負(fù)采樣的詞的數(shù)量為5。

本文采用準(zhǔn)確率和召回率的調(diào)和平均F值（FMeasure）進行評價。

4. 2 多標(biāo)簽分類實驗

由于電影可能屬于多種類型，因此在本實驗中構(gòu)建異質(zhì)信息網(wǎng)絡(luò)時，我們會隨機選擇一種類型作為結(jié)點的標(biāo)簽。首先，我們使用完整數(shù)據(jù)集進行結(jié)點表示學(xué)習(xí)。然后，將邏輯回歸的訓(xùn)練集從10%到90%進行劃分，將剩余的作為測試集，每個比例的訓(xùn)練集重復(fù)進行10次實驗，取平均的F值進行比較。

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

總之，通過多標(biāo)簽分類實驗，AttrHIN2Vec比目前最先進的方法表現(xiàn)更好。AttrHIN2Vec的優(yōu)勢在于其在進行基于元路徑的隨機游走時，考慮了結(jié)點屬性信息和以及元路徑的權(quán)重信息。

表1 多標(biāo)簽分類結(jié)果

4. 3 參數(shù)敏感度驗證

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

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

5 結(jié)語

本文重點研究異質(zhì)信息網(wǎng)絡(luò)中的表示學(xué)習(xí)?，F(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)工作較少考慮網(wǎng)絡(luò)的屬性信息和權(quán)重信息。為了填補這一空白，我們提出了一種新型的模型：屬性異質(zhì)信息網(wǎng)絡(luò)向量表示模型（AttrHIN2Vec）。它可以用來捕獲網(wǎng)絡(luò)中的潛在特征。實驗表明，AttrHIN2Vec學(xué)到的潛在特征表示可以改善網(wǎng)絡(luò)分析任務(wù)，如多標(biāo)簽分類。

圖1 分類中的參數(shù)敏感度驗證

我們計劃在以下兩個方向繼續(xù)我們的研究。隨著不同類型節(jié)點和關(guān)系的增加，構(gòu)建屬性異質(zhì)信息網(wǎng)絡(luò)的成本將非常高。因此，提高構(gòu)建效率尤為關(guān)鍵。此外，在構(gòu)建網(wǎng)絡(luò)時，屬性的選擇是一個值得研究的問題。