一、背景以及目的

最近看到的一些文章會(huì)提到Metapath2vec。于是乎抽了點(diǎn)時(shí)間整理了一下從word2vec方法發(fā)展到metapath2vec的路徑。比較單純的算是知識(shí)總結(jié)。本文盡量闡述思想，不過(guò)度使用公式表達(dá)。

本文中可能會(huì)涉及到的比較重要的知識(shí)，及其出處：

word2vec: Efficient Estimation of Word Representations in Vector Space

論文地址：https://arxiv.org/pdf/1301.3781.pdf

word2vec: word2vec Parameter Learning Explained

論文地址：https://arxiv.org/abs/1411.2738

Random walk：Random Walk: A Modern Introduction

書籍地址：http://www.math.uchicago.edu/~lawler/srwbook.pdf

Deepwalk：DeepWalk: Online Learning of Social Representations

論文地址：https://arxiv.org/pdf/1403.6652.pdf

node2vec：node2vec: Scalable Feature Learning for Networks

論文地址：https://arxiv.org/pdf/1607.00653.pdf

綜述：LEARNING REPRESENTATIONS OF GRAPH DATA: A SURVEY

論文地址：https://arxiv.org/abs/1906.02989v2

二、embedding

在深度學(xué)習(xí)的應(yīng)用過(guò)程中，Embedding 這樣一種將離散變量轉(zhuǎn)變?yōu)檫B續(xù)向量的方式為神經(jīng)網(wǎng)絡(luò)在各方面的應(yīng)用帶來(lái)了極大的擴(kuò)展。該技術(shù)目前主要有兩種應(yīng)用，NLP 中常用的 word embedding 以及用于類別數(shù)據(jù)的 entity embedding。這一章節(jié)中，我們所有的探討都圍繞以下兩個(gè)問(wèn)題：

1. 什么是 neural network embedding？
2. 我們?yōu)槭裁葱枰褂?neural network embedding？

Embedding和One Hot編碼

上面說(shuō)了，Embedding 是一個(gè)將離散變量轉(zhuǎn)為連續(xù)向量表示的一個(gè)方式。在神經(jīng)網(wǎng)絡(luò)中，embedding是非常有用的，因?yàn)樗还饪梢詼p少離散變量的空間維數(shù)，同時(shí)還可以有意義的表示該變量。

我們可以總結(jié)一下，embedding 有以下 3 個(gè)主要目的：

1. 在embedding空間中查找最近鄰，這可以用于推薦
2. 作為監(jiān)督性學(xué)習(xí)任務(wù)的輸入
3. 用于可視化不同離散變量之間的關(guān)系

要了解 embedding 的優(yōu)點(diǎn)，我們可以對(duì)應(yīng) One-hot 編碼來(lái)觀察。One-hot 編碼是一種最普通常見(jiàn)的表示離散數(shù)據(jù)的表示，首先我們計(jì)算出需要表示的離散或類別變量的總個(gè)數(shù) N，然后對(duì)于每個(gè)變量，我們就可以用 N-1 個(gè) 0 和單個(gè) 1 組成的 vector 來(lái)表示每個(gè)類別。這樣做有兩個(gè)很明顯的缺點(diǎn)：

1. 對(duì)于具有非常多類型的類別變量，變換后的向量維數(shù)過(guò)于巨大，且過(guò)于稀疏。
2. 映射之間完全獨(dú)立，并不能表示出不同類別之間的關(guān)系。

因此，考慮到這兩個(gè)問(wèn)題，表示類別變量的理想解決方案則是我們是否可以通過(guò)較少的維度表示出每個(gè)類別，并且還可以一定的表現(xiàn)出不同類別變量之間的關(guān)系，這也就是embedding 出現(xiàn)的目的。而為了更好的表示類別實(shí)體，我們還可以是用一個(gè) embedding neural network 和 supervised 任務(wù)來(lái)進(jìn)行學(xué)習(xí)訓(xùn)練，以找到最適合的表示以及挖掘其內(nèi)在聯(lián)系。

三、word2vec初探

neural network embedding中最早的應(yīng)用之一就是word2vec。

3.1 什么是word2vec

Word2Vec是從大量文本語(yǔ)料中以無(wú)監(jiān)督的方式學(xué)習(xí)語(yǔ)義知識(shí)的一種模型，它被大量地用在自然語(yǔ)言處理（NLP）中。那么它是如何幫助我們做自然語(yǔ)言處理呢？Word2Vec其實(shí)就是通過(guò)學(xué)習(xí)文本來(lái)用詞向量的方式表征詞的語(yǔ)義信息，即通過(guò)一個(gè)嵌入空間使得語(yǔ)義上相似的單詞在該空間內(nèi)距離很近。Embedding其實(shí)就是一個(gè)映射，將單詞從原先所屬的空間映射到新的多維空間中，也就是把原先詞所在空間嵌入到一個(gè)新的空間中去。

舉個(gè)例子：
有四個(gè)詞：man, woman, king, queen.我們通常是希望這四個(gè)詞的embedding結(jié)果有相近的（距離）關(guān)系。man和woman的距離比man和queen的距離小，類似地，man和king的距離與woman和queen的距離相差無(wú)幾，但比man和queen的距離以及woman和king的距離更小。

3.2 skip-gram和CBOW

Word2Vec模型中，主要有Skip-Gram和CBOW兩種模型，從直觀上理解，Skip-Gram是給定input word來(lái)預(yù)測(cè)上下文。而CBOW是給定上下文，來(lái)預(yù)測(cè)input word。如下圖所示。

下圖表達(dá)的是CBOW的網(wǎng)絡(luò)結(jié)構(gòu)，這里是輸入是多個(gè)單詞，一般是求和然后平均再進(jìn)行計(jì)算，最終的損失函數(shù)保持不變。

下圖表示skip-gram的網(wǎng)絡(luò)結(jié)構(gòu)，輸入一個(gè)詞，預(yù)測(cè)周邊的詞。

3.3 負(fù)采樣(negative sampling)

正如我們所看到的，如果想要計(jì)算相關(guān)的模型，對(duì)于我們來(lái)說(shuō)，計(jì)算代價(jià)是很大的。因此有了hierarchical softmax和negative sampling兩個(gè)方法。這里稍微提一下hierarchical softmax這個(gè)方法，其本質(zhì)是將一個(gè)N分類問(wèn)題，通過(guò)建立樹(shù)模型，變成一個(gè)log(N)次二分類問(wèn)題。今天的重點(diǎn)在negative sampling。

負(fù)采樣的思想更簡(jiǎn)單直接：in order to deal with the difficulty of having too many output vectors that need to be updated per iteration, we only update a sample of them.

這就是此思想最核心的部分，它的實(shí)現(xiàn)過(guò)程則是如下面的例子：

當(dāng)訓(xùn)練樣本 ( input word: "fox"，output word: "quick") 來(lái)訓(xùn)練我們的神經(jīng)網(wǎng)絡(luò)時(shí)，“ fox”和“quick”都是經(jīng)過(guò)one-hot編碼的。如果vocabulary大小為10000時(shí)，在輸出層，我們期望對(duì)應(yīng)“quick”單詞的那個(gè)神經(jīng)元結(jié)點(diǎn)輸出1，其余9999個(gè)都應(yīng)該輸出0。這9999個(gè)我們期望輸出為0的神經(jīng)元結(jié)點(diǎn)所對(duì)應(yīng)的單詞我們稱為“negative” word。使用負(fù)采樣時(shí)，我們將隨機(jī)選擇一小部分的negative words（比如選5個(gè)negative words）來(lái)更新對(duì)應(yīng)的權(quán)重。我們也會(huì)對(duì)我們的“positive” word進(jìn)行權(quán)重更新（在我們上面的例子中，這個(gè)單詞指的是”quick“）。

下面請(qǐng)出今天的一號(hào)主角，負(fù)采樣目標(biāo)函數(shù)表達(dá)式：

因此，這個(gè)目標(biāo)函數(shù)可以理解為兩方面的限制：

1. 目標(biāo)詞為1
2. “負(fù)”詞為0，但是負(fù)采樣每次只考慮部分“負(fù)”詞的，而非全量。

四、從word2vec到node2vec

word2vec是將詞變成向量，顧名思義，node2vec其實(shí)就是將復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)變成向量。其核心思想為：生成隨機(jī)游走，對(duì)隨機(jī)游走采樣得到（節(jié)點(diǎn)，上下文）的組合，然后用處理詞向量的方法對(duì)這樣的組合建模得到網(wǎng)絡(luò)節(jié)點(diǎn)的表示。

Deepwalk和node2vec的思想是高度一致的。相比于deepwalk，node2vec在生成隨機(jī)游走過(guò)程中做了一些創(chuàng)新。這里我們不對(duì)兩者進(jìn)行深入比較，但由此提出一個(gè)結(jié)論，也請(qǐng)出今天的二號(hào)主角，這一類編碼方式的核心結(jié)構(gòu)：我個(gè)人把它看做是“上、下”結(jié)構(gòu)

上：想盡一切辦法，在你的網(wǎng)絡(luò)中進(jìn)行游走，并采集成序，具體什么游走策略取決于你想采集到什么信息。

下：將采集好的序當(dāng)作文本，后續(xù)與處理詞向量的方法相似。

下面以node2vec為例，簡(jiǎn)單介紹一下這個(gè)過(guò)程。

4.1 采序

采序的目的很單純：

1. 同一個(gè)社區(qū)內(nèi)的節(jié)點(diǎn)表示相似。
2. 擁有類似結(jié)構(gòu)特征的節(jié)點(diǎn)表示相似。

當(dāng)然，你采序的思想反映了你希望獲取到什么樣的信息。論文原文中提到關(guān)于廣度優(yōu)先或者深度優(yōu)先的采序方式在本質(zhì)上就表達(dá)了對(duì)不同累心信息的重視。BFS傾向于在初始節(jié)點(diǎn)的周圍游走，可以反映出一個(gè)節(jié)點(diǎn)的鄰居的微觀特性；而DFS一般會(huì)跑的離初始節(jié)點(diǎn)越來(lái)越遠(yuǎn)，可以反映出一個(gè)節(jié)點(diǎn)鄰居的宏觀特性。因此！因此！因此！采序策略是直接反應(yīng)操作者對(duì)哪部分信息更加重視?。ǘ?hào)主角再度出現(xiàn)）

node2vec原文中提出的隨機(jī)游走策略，實(shí)際上就是綜合BFS與DFS的策略。下面我們細(xì)細(xì)品一哈。

上圖表示我們剛剛從已經(jīng)采集了t到v，那么下一個(gè)臨幸的對(duì)象應(yīng)該是誰(shuí)？原文作者，給出了以下的轉(zhuǎn)移概率：

釋一下這個(gè)分布：

• 如果t與x相等，那么采樣x的概率為1/p
• 如果t與x相連，那么采樣x的概率為1；
• 如果t與x不相連，那么采樣x的概率為1/q

參數(shù)p、q的意義分別如下：
返回概率p：

• 如果 p>max(q,1)，那么采樣會(huì)盡量不往回走，對(duì)應(yīng)上圖的情況，就是下一個(gè)節(jié)點(diǎn)不太可能是上一個(gè)訪問(wèn)的節(jié)點(diǎn)t。
• 如果p<max(q,1)，那么采樣會(huì)更傾向于返回上一個(gè)節(jié)點(diǎn)，這樣就會(huì)一直在起始點(diǎn)周圍某些節(jié)點(diǎn)來(lái)回轉(zhuǎn)來(lái)轉(zhuǎn)去。

出入?yún)?shù)q：

• 如果q>1，那么游走會(huì)傾向于在起始點(diǎn)周圍的節(jié)點(diǎn)之間跑，可以反映出一個(gè)節(jié)點(diǎn)的BFS特性。
• 如果q<1，那么游走會(huì)傾向于往遠(yuǎn)處跑，反映出DFS特性。

當(dāng)p=1，q=1時(shí)，游走方式就等同于DeepWalk中的隨機(jī)游走。

再一次，采序策略是直接反應(yīng)操作者對(duì)哪部分信息更加重視！（二號(hào)主角再度出現(xiàn)）！

4.2 訓(xùn)練

這部分我們只挑重點(diǎn)的說(shuō)，原文作者通過(guò)擴(kuò)展skipgram，定義了目標(biāo)函數(shù)：

五、metapath2vec來(lái)了

到此，我們已經(jīng)基本了解到了embedding方法中，這一類方法的結(jié)構(gòu)特點(diǎn)（所謂“上、下”）。但是之前接觸的方法均是處理同質(zhì)網(wǎng)絡(luò)的方法，而metapath2vec恰恰是可以處理異質(zhì)網(wǎng)絡(luò)的一個(gè)方法。

Metapath2vec是Yuxiao Dong等于2017年提出的一種用于異構(gòu)信息網(wǎng)絡(luò)（Heterogeneous Information Network, HIN）的頂點(diǎn)嵌入方法。metapath2vec使用基于meta-path的random walks來(lái)構(gòu)建每個(gè)頂點(diǎn)的異構(gòu)鄰域，然后用Skip-Gram模型來(lái)完成頂點(diǎn)的嵌入。在metapath2vec的基礎(chǔ)上，作者還提出了metapath2vec++來(lái)同時(shí)實(shí)現(xiàn)異構(gòu)網(wǎng)絡(luò)中的結(jié)構(gòu)和語(yǔ)義關(guān)聯(lián)的建模。

這里說(shuō)說(shuō)metapath的貢獻(xiàn)：

1. 正式定義了Heterogeneous Network上的表示學(xué)習(xí)過(guò)程，并指明了網(wǎng)絡(luò)異構(gòu)帶來(lái)的特殊挑戰(zhàn)。
2. 提出了有效且高效的能同時(shí)保留結(jié)構(gòu)和語(yǔ)義相互關(guān)系的異構(gòu)網(wǎng)絡(luò)嵌入框架：metapath2vec和metapath2vec++。

下面我們看看metapath2vec是怎么樣實(shí)現(xiàn)對(duì)異質(zhì)網(wǎng)絡(luò)編碼的。

5.1 定義與問(wèn)題

Heterogeneous Network

對(duì)于一個(gè)異質(zhì)網(wǎng)絡(luò)，目標(biāo)是學(xué)習(xí)到維的表達(dá)式，其中的長(zhǎng)度遠(yuǎn)小于鄰接矩陣邊長(zhǎng)，并且同時(shí)保持圖的結(jié)構(gòu)信息與語(yǔ)義關(guān)系。

這部分劃重點(diǎn)：雖然頂點(diǎn)的類型不同，但是不同類型的頂點(diǎn)的表征向量映射到同一個(gè)維度空間。由于網(wǎng)絡(luò)異構(gòu)性的存在，傳統(tǒng)的基于同構(gòu)網(wǎng)絡(luò)的頂點(diǎn)嵌入表征方法很難有效地直接應(yīng)用在異構(gòu)網(wǎng)絡(luò)上。

5.2 metapath2vec：“上”升級(jí)

metapath2vec方法，著重強(qiáng)調(diào)對(duì)采序過(guò)程的改進(jìn)。其訓(xùn)練過(guò)程方面的改進(jìn)并不明顯。

5.2.1 采序升級(jí)，“上”升級(jí)

meta-path-based random walk

該隨機(jī)游走方式可以同時(shí)捕獲不同類型頂點(diǎn)之間語(yǔ)義關(guān)系和結(jié)構(gòu)關(guān)系，促進(jìn)了異構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)向metapath2vec的Skip-Gram模型的轉(zhuǎn)換。

1. 兩個(gè)點(diǎn)間有邊，且下一個(gè)點(diǎn)屬于我們定義好的metapath上的下一個(gè)類型的節(jié)點(diǎn)。
2. 兩個(gè)點(diǎn)間有邊，但是下一個(gè)點(diǎn)不屬于我們定義好的metapath上的下一個(gè)類型的節(jié)點(diǎn)。
3. 兩個(gè)點(diǎn)間沒(méi)有邊。

此處有個(gè)小技巧。一般來(lái)說(shuō)metapath的定義都是對(duì)稱的，比如：一個(gè)meta-path的scheme可以是"o-a-p-v-p-a-o"。

這個(gè)時(shí)候可以將這一小節(jié)的內(nèi)容對(duì)比上面4.1 采序中的內(nèi)容，可以發(fā)現(xiàn)metapath的第一個(gè)核心貢獻(xiàn)：采序策略。

5.3.1 訓(xùn)練方法

顧名思義，通過(guò)最大化條件概率來(lái)學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)的頂點(diǎn)特征。

這個(gè)時(shí)候再次請(qǐng)出我們的一號(hào)主角，原始skip-gram的負(fù)采樣下的目標(biāo)函數(shù)：

有沒(méi)有發(fā)現(xiàn)區(qū)別。本質(zhì)上的區(qū)別非常細(xì)微。甚至可以說(shuō)沒(méi)有區(qū)別。因此，這部分最主要的貢獻(xiàn)在“采序”升級(jí)。

5.3 metapath2vec++：“下”升級(jí)

上面我看到了metapath2vec對(duì)“上”部分的升級(jí)。下面我們看看metapath2vec++是怎么對(duì)“下”進(jìn)行升級(jí)的。
主要兩點(diǎn)：

• 在負(fù)采樣時(shí)只采樣當(dāng)前類別的節(jié)點(diǎn)
• 輸出維度是當(dāng)前該類型節(jié)點(diǎn)的個(gè)數(shù)

首先，softmax函數(shù)根據(jù)不同類型的頂點(diǎn)的上下文 進(jìn)行歸一化，即是：

這里的目標(biāo)函數(shù)和我們的一號(hào)主角雖然也沒(méi)有本質(zhì)區(qū)別。但是！但是！但是！異質(zhì)網(wǎng)絡(luò)的異質(zhì)信息不僅僅在采序中體現(xiàn)出來(lái)，也在目標(biāo)函數(shù)中被體現(xiàn)出來(lái)。我把metapath2vec的目標(biāo)函數(shù)和metapath2vec++的目標(biāo)函數(shù)放在一起比較看看：

這里也就引出了metapath2vec++在“訓(xùn)練”目標(biāo)上的升級(jí)。

5.4 實(shí)驗(yàn)與說(shuō)明

實(shí)驗(yàn)效果說(shuō)明，下圖是原論文中的截圖。類別聚類準(zhǔn)確率：