metapath2vec: 異質(zhì)圖Graph Embedding

論文：metapath2vec: Scalable Representation Learning for Heterogeneous Networks
作者：Yuxiao Dong Microso Research
論文鏈接：https://www3.nd.edu/~dial/publications/dong2017metapath2vec.pdf
期刊：KDD 2017

今天看的這一篇是Yuxiao Dong發(fā)表在KDD2017的一篇關(guān)于異質(zhì)圖網(wǎng)絡(luò)Graph Embedding。本文提出了基于元路徑的隨機(jī)游走來(lái)指定一個(gè)節(jié)點(diǎn)的鄰居，之后利用異構(gòu)skip-gram模型來(lái)實(shí)現(xiàn)embedding。

1、INTRODUCTION

傳統(tǒng)的網(wǎng)絡(luò)挖掘方法，一般通過(guò)將網(wǎng)絡(luò)轉(zhuǎn)化成鄰接矩陣，在使用機(jī)器學(xué)習(xí)模型挖掘網(wǎng)絡(luò)中的信息。但是，鄰接矩陣通常都很稀疏，且維數(shù)很大。同時(shí)作者提到當(dāng)前的一些基于神經(jīng)網(wǎng)絡(luò)的模型針對(duì)復(fù)雜網(wǎng)絡(luò)的表示學(xué)習(xí)也有非常好的效果。其中包括當(dāng)前已經(jīng)提出的采用了word2vec思想的網(wǎng)絡(luò)表示算法，如Deepwalk，node2vec以及LINE等。但是作者也明確指出了，上述這些算法雖然可以用于網(wǎng)絡(luò)表示學(xué)習(xí)，但僅適合那些只包含一類(lèi)頂點(diǎn)類(lèi)型和邊類(lèi)型的同構(gòu)網(wǎng)絡(luò)（Homogeneous Networks），并不能很好地用于包含多種頂點(diǎn)類(lèi)型和邊類(lèi)型的復(fù)雜關(guān)系網(wǎng)絡(luò)。因此作者提出在基于meta-path的基礎(chǔ)上，提出了在異構(gòu)復(fù)雜關(guān)系網(wǎng)絡(luò)的表示學(xué)習(xí)方法——metapath2vec和metapath2vec++。 metapath2vec的目標(biāo)是最大化保留一個(gè)異構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)和語(yǔ)義信息的似然，首先使用基于meta-path的隨機(jī)游走獲取異構(gòu)網(wǎng)絡(luò)中每種不同類(lèi)型頂點(diǎn)的異構(gòu)領(lǐng)域，然后使用擴(kuò)展的Skip-Gram處理前面獲取的頂點(diǎn)鄰域，最終學(xué)習(xí)每個(gè)不同類(lèi)型頂點(diǎn)的網(wǎng)絡(luò)嵌入表示。

2、 PROBLEM DEFINITION

  • Heterogeneous Network
    異質(zhì)網(wǎng)絡(luò)定義為：G=(V,E,T),其中每個(gè)節(jié)點(diǎn)和邊的映射函數(shù)為：?(v) : V → T_V 和 φ(e) : E → T_E , 其中Tv和TE分別表示定點(diǎn)和邊的類(lèi)型，并且滿(mǎn)足|T_V|+|T_E|>2。

  • Heterogeneous Network Representation Learning
    異構(gòu)網(wǎng)絡(luò)表征學(xué)習(xí)定義為：給定一個(gè)異構(gòu)網(wǎng)絡(luò)G，學(xué)習(xí)一個(gè)d維的潛在表征X \in R^{|V| * d},d<<|V|可以表征網(wǎng)絡(luò)中頂點(diǎn)之間的結(jié)構(gòu)信息和語(yǔ)義場(chǎng)景關(guān)系。模型的輸出是一個(gè)低維的矩陣X，其中的第i行是一個(gè)d維的向量，表示定點(diǎn)i的表示。但是要注意一點(diǎn)，傳統(tǒng)的同質(zhì)圖定點(diǎn)嵌入的表示特征方法很難直接應(yīng)用于異質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)上。

3、 Metapath2vec

在Metapath2vec 中，采用的方式和DeepWalk類(lèi)似的方式，利用skip-gram來(lái)學(xué)習(xí)圖的embedding。1、利用元路徑隨機(jī)游走從圖中獲取序列，2、利用skip-gram來(lái)學(xué)習(xí)節(jié)點(diǎn)的嵌入表示。

對(duì)于基于異構(gòu)網(wǎng)絡(luò)的metapath2vec嵌入算法，包含兩個(gè)部分，分別是元路徑隨機(jī)游走(Meta-Path-Based Random Walks)和Heterogeneous Skip-Gram。

Heterogeneous Skip-Gram
在同構(gòu)網(wǎng)絡(luò)上的基于random walk的graph embedding算法通常對(duì)于一個(gè)同質(zhì)網(wǎng)絡(luò)G=(V,E),目標(biāo)是從每個(gè)頂點(diǎn)的局部鄰域上最大化網(wǎng)絡(luò)的似然：
argmax_\theta \prod_{v \in V} \prod_{c \in N(v)} p(c|v;\theta)
其中N(v)表示定點(diǎn)v的鄰域，也就是其1-hop或2-hop的鄰居節(jié)點(diǎn)。p(c|v;\theta)表示在參數(shù)\theta下，給定節(jié)點(diǎn)v后，節(jié)點(diǎn)C的條件概率。

對(duì)于異質(zhì)圖G=(V,E,T),|T_V|>1,目標(biāo)就是在給定節(jié)點(diǎn)v后，是的其上下文內(nèi)容存在的概率最大化，如下：
argmax_\theta \sum_{v \in V} \sum_{t \in T_V} \sum_{c_t \in N_t(v)} p(c_t|v;\theta)
這里的N_t(v)指的是在節(jié)點(diǎn)v的鄰近節(jié)點(diǎn)中，為第t個(gè)節(jié)點(diǎn)，而概率函數(shù)p(c_t|v;\theta)則為softmax?？杀硎緸椋?img class="math-block" src="https://math.jianshu.com/math?formula=p(c_t%7Cv%3B%5Ctheta)%3D%5Cfrac%7Be%5E%7BX_%7Bct%7D%20.%20X_v%7D%7D%7B%5Csum_%7Bu%20%5Cin%20V%7D%20e%5E%7BX_u.X_v%7D%7D" alt="p(c_t|v;\theta)=\frac{e^{X_{ct} . X_v}}{\sum_{u \in V} e^{X_u.X_v}}" mathimg="1">這里的X_v就是嵌入矩陣中的第v行向量，它表示節(jié)點(diǎn)v的嵌入向量。
metapath2vec中采用Negative Sampling進(jìn)行參數(shù)迭代更新，這時(shí)設(shè)置一個(gè)負(fù)采樣的窗口M，則參數(shù)更新過(guò)程如下：


其中是sigmoid函數(shù)，P(u)是一個(gè)negative node 在M次采用中的預(yù)定義分布。

metapath2vec通過(guò)不考慮頂點(diǎn)的類(lèi)型進(jìn)行節(jié)點(diǎn)抽取來(lái)確定當(dāng)前頂點(diǎn)的頻率。

Meta-Pathe-Based Random Walks
metapath2vec采用的和deepwalk采用的是相同的思路，不過(guò)deepwalk處理的是同質(zhì)圖，但是在異質(zhì)圖中決定下一步隨機(jī)游走的條件概率p(v^{i+1}| v^i)如果只對(duì)節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)做標(biāo)準(zhǔn)化，而不對(duì)節(jié)點(diǎn)類(lèi)型進(jìn)行考慮，在其他論文中證明出：異質(zhì)網(wǎng)絡(luò)上的隨機(jī)游走生成的路徑，偏向（biased）于高度可見(jiàn)的節(jié)點(diǎn)類(lèi)型（具有優(yōu)勢(shì)/主導(dǎo)數(shù)量的路徑的節(jié)點(diǎn)）和 集中(concentrated)的節(jié)點(diǎn)（即：具有指向一小組節(jié)點(diǎn)路徑的 大部分百分比）。
于是本文提出基于元路徑的隨機(jī)游走，獲取不同節(jié)點(diǎn)之間的語(yǔ)義及結(jié)構(gòu)相關(guān)性。
基于元路徑的隨機(jī)游走可以定義成如下形式：


其中

表示節(jié)點(diǎn)v1和節(jié)點(diǎn)vl之間的路徑組合。
舉個(gè)例子，下圖中“APA”表示一種固定語(yǔ)義的meta-path，“APVPA”表示另外一種固定語(yǔ)義的meta-path。而這樣的meta-path可以幫助挖掘網(wǎng)絡(luò)中更多的信息，因此，在本文中，作者給出了基于meta-path的隨機(jī)游走方式。

給定一個(gè)異質(zhì)網(wǎng)絡(luò)圖G=(V,E,T)和一個(gè)meta-path的模板(scheme) \mathcal{p}，那么在第i步的轉(zhuǎn)移概率定義圖如下：
\begin{equation} p(v^{i+1} | v^i_t;\mathcal{P})= \left \{ \begin{array}{ll} \frac{1}{N_{t+1}(v^i_t)} (v^{i+1},v^i_t) \in E, \phi(v^{i+1})=t+1\\ 0 \quad\quad\quad (v^{i+1},v^i_t) \in E, \phi(v^{i+1}) \neq t+1\\ 0 \quad\quad\quad\quad (v^{i+1},v^i_t) \notin E\\ \end{array}\right. \end{equation}

其中v^i_t∈V_t, 并且N_{t+1}(v^i_t)代表的是節(jié)點(diǎn)v^i_t的鄰居中屬于t+1type的節(jié)點(diǎn)集合。換句話(huà)說(shuō)，游走是在預(yù)先設(shè)定的meta-path \mathcal{p}的條件上。而且，meta-path一般都是用在對(duì)稱(chēng)的路徑上,也就是說(shuō)在上述路徑組合中，頂點(diǎn)V_t的類(lèi)型和V_l的類(lèi)型相同。

\begin{equation} p(v^{i+1}|v_t^i) = p(v^{i+1}|v_l^i),\quad if \quad t=l \end{equation}

基于meta-path的隨機(jī)游走保證不同類(lèi)型頂點(diǎn)之間的語(yǔ)義關(guān)系之后，可以適當(dāng)?shù)娜谌隨kip-Gram模型中進(jìn)行訓(xùn)練得到節(jié)點(diǎn)的嵌入表示。

4、 Metapath2vec++

由于在meta-path中我們是根據(jù)節(jié)點(diǎn)的類(lèi)型進(jìn)行的隨機(jī)游走，但是在在softmax環(huán)節(jié)中，我們是將所有節(jié)點(diǎn)按照同一種類(lèi)型進(jìn)行的負(fù)采樣過(guò)程，并未按照節(jié)點(diǎn)的類(lèi)型進(jìn)行區(qū)分，也就是說(shuō)metapath2vec支持任意類(lèi)型頂點(diǎn)的Negative Sampling。于是就與這一點(diǎn)作者進(jìn)行了改進(jìn)提出了Metapath2vec++。

因而本文提出，異質(zhì)的負(fù)采樣(Heterogeneous negative sampling)。也就是說(shuō)softmax函數(shù)根據(jù)節(jié)點(diǎn)的不同類(lèi)型進(jìn)行歸一化處理，那么p(c_t|v; \theta)是根據(jù)固定類(lèi)型的頂點(diǎn)進(jìn)行調(diào)整。即：


這同時(shí)為了skip-gram最后一層輸出層中的 每個(gè)類(lèi)型都指定了一個(gè)多項(xiàng)分布。負(fù)采樣的目標(biāo)函數(shù)：

5、Conclusion

本篇論文繼續(xù)沿用了同構(gòu)圖上基于隨機(jī)游走的Embedding算法的思想，不過(guò)通過(guò)meta-path來(lái)指導(dǎo)生產(chǎn)隨機(jī)游走的過(guò)程，使得在異質(zhì)圖中的異構(gòu)信息和語(yǔ)義信息保留，同時(shí)借助Skip-Gram模型可以學(xué)習(xí)節(jié)點(diǎn)的表征。

參考

1.metapath2vec: Scalable Representation Learning for Heterogeneous Networks

2.Graph Embedding之metapath2vec

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容