AttrHIN2Vec:一種新型異質(zhì)信息網(wǎng)絡(luò)表示學(xué)習(xí)模型

文鵬，李青，熊友

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

0 引言

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

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

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

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

總而言之，我們的工作做出了以下貢獻(xiàn)：

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

●我們采用MovieLens-1M數(shù)據(jù)集進(jìn)行了多標(biāo)簽分類實(shí)驗(yàn)。與 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é)點(diǎn)分類的分解模型。隨著深度學(xué)習(xí)技術(shù)的發(fā)展，越來(lái)越多的基于神經(jīng)網(wǎng)絡(luò)的表述學(xué)習(xí)模型被提出。一個(gè)典型的例子是Word2Vec，它由一個(gè)雙層神經(jīng)網(wǎng)絡(luò)組成，旨在學(xué)習(xí)自然語(yǔ)言處理中單詞的分布式表示[9,10]。基于Word2Vec，Perozzi等提出了DeepWalk[2]。DeepWalk通過在網(wǎng)絡(luò)中結(jié)點(diǎn)的隨機(jī)游走形成一個(gè)序列，相當(dāng)于詞嵌入中文檔的句子，然后將序列作為Skip-Gram模型的輸入，最終得到結(jié)點(diǎn)的低維向量表示。此后，為了保留一階和二階相似性，Tang等人[1]提出了名為L(zhǎng)INE的大規(guī)模信息網(wǎng)路嵌入方法。文獻(xiàn)[11]中提出的Node2Vec模型在鄰近節(jié)點(diǎn)的多樣性方面表現(xiàn)良好。Node2Vec模型通過平衡廣度優(yōu)先采樣與深度優(yōu)先采樣，生成目標(biāo)節(jié)點(diǎn)序列。然后，通過最大化保留的網(wǎng)絡(luò)鄰近節(jié)點(diǎn)的相似度得到最終的節(jié)點(diǎn)表示。

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

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

2 問題定義

文獻(xiàn)[13]簡(jiǎn)要介紹了異質(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é)點(diǎn)集合，E代表結(jié)點(diǎn)相連的邊集合，T為結(jié)點(diǎn)類型的集合，并且有|TV|+|TE|＞2。對(duì)于任意一個(gè)結(jié)點(diǎn)v，存在一個(gè)映射函數(shù)φ(v):V→TV，TV代表結(jié)點(diǎn)類型。同樣的，對(duì)于任意一條邊e，存在一個(gè)映射函數(shù)φ(e):E→TE，TE代表邊類型。A為結(jié)點(diǎn)屬性集合，即A={a1…,am}。對(duì)于任意結(jié)點(diǎn)vi∈V，均關(guān)聯(lián)一個(gè)屬性向量[a1(vi)…,am(vi)]，aj(vi)代表結(jié)點(diǎn)vi在屬性aj上的取值。

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

3 AttrHin2Vec模型

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

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

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

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

3. 2 帶屬性Skip-Gram模型

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

其中,

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

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

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

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

更新公式

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

3. 3 AttrHIN 2Vec算法

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

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

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

AttrHIN2Vec算法

Input：

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

Output：

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

4 實(shí)驗(yàn)

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

4. 1 實(shí)驗(yàn)設(shè)置

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

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

（2）LINE[1]：本文使用考慮一階相似度和二階相似度LINE的改進(jìn)版本進(jìn)行實(shí)驗(yàn)對(duì)比。

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

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

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

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

（2）每次游走的長(zhǎng)度l為100；

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

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

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

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

4. 2 多標(biāo)簽分類實(shí)驗(yàn)

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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