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ī)游走來指定一個(gè)節(jié)點(diǎn)的鄰居锰悼，之后利用異構(gòu)skip-gram模型來實(shí)現(xiàn)embedding杀捻。

1疯攒、INTRODUCTION

傳統(tǒng)的網(wǎng)絡(luò)挖掘方法副瀑，一般通過將網(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í)，但僅適合那些只包含一類頂點(diǎn)類型和邊類型的同構(gòu)網(wǎng)絡(luò)（Homogeneous Networks）幕侠，并不能很好地用于包含多種頂點(diǎn)類型和邊類型的復(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)和語義信息的似然梯皿，首先使用基于meta-path的隨機(jī)游走獲取異構(gòu)網(wǎng)絡(luò)中每種不同類型頂點(diǎn)的異構(gòu)領(lǐng)域腮考，然后使用擴(kuò)展的Skip-Gram處理前面獲取的頂點(diǎn)鄰域，最終學(xué)習(xí)每個(gè)不同類型頂點(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)和邊的類型湿蛔，并且滿足 $|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)信息和語義場(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類似的方式，利用skip-gram來學(xué)習(xí)圖的embedding恼布。1螺戳、利用元路徑隨機(jī)游走從圖中獲取序列，2折汞、利用skip-gram來學(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而咆。可表示為： $p(c_t|v;\theta)=\frac{e^{X_{ct} . X_v}}{\sum_{u \in V} e^{X_u.X_v}}$ 這里的 $X_v$ 就是嵌入矩陣中的第v行向量幕袱，它表示節(jié)點(diǎn)v的嵌入向量暴备。
metapath2vec中采用Negative Sampling進(jìn)行參數(shù)迭代更新，這時(shí)設(shè)置一個(gè)負(fù)采樣的窗口M们豌，則參數(shù)更新過程如下：

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

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

Meta-Pathe-Based Random Walks
metapath2vec采用的和deepwalk采用的是相同的思路障癌，不過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)類型進(jìn)行考慮涛浙，在其他論文中證明出：異質(zhì)網(wǎng)絡(luò)上的隨機(jī)游走生成的路徑，偏向（biased）于高度可見的節(jié)點(diǎn)類型（具有優(yōu)勢(shì)/主導(dǎo)數(shù)量的路徑的節(jié)點(diǎn)）和集中(concentrated)的節(jié)點(diǎn)（即：具有指向一小組節(jié)點(diǎn)路徑的大部分百分比）摄欲。
于是本文提出基于元路徑的隨機(jī)游走轿亮，獲取不同節(jié)點(diǎn)之間的語義及結(jié)構(gòu)相關(guān)性。
基于元路徑的隨機(jī)游走可以定義成如下形式：

其中

表示節(jié)點(diǎn)v1和節(jié)點(diǎn)vl之間的路徑組合胸墙。
舉個(gè)例子我注，下圖中“APA”表示一種固定語義的meta-path，“APVPA”表示另外一種固定語義的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)集合吼野。換句話說校哎，游走是在預(yù)先設(shè)定的meta-path $\mathcal{p}$ 的條件上。而且箫锤，meta-path一般都是用在對(duì)稱的路徑上,也就是說在上述路徑組合中贬蛙，頂點(diǎn) $V_t$ 的類型和 $V_l$ 的類型相同雨女。

$\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ī)游走保證不同類型頂點(diǎn)之間的語義關(guān)系之后，可以適當(dāng)?shù)娜谌隨kip-Gram模型中進(jìn)行訓(xùn)練得到節(jié)點(diǎn)的嵌入表示阳准。

4氛堕、 Metapath2vec++

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

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

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

5藕帜、Conclusion

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

參考

1.metapath2vec: Scalable Representation Learning for Heterogeneous Networks

2.Graph Embedding之metapath2vec

最后編輯于：2020.07.19 09:54:19

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末盗誊，一起剝皮案震驚了整個(gè)濱河市时甚，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌哈踱，老刑警劉巖荒适，帶你破解...
沈念sama閱讀 206,126評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異嚣鄙，居然都是意外死亡吻贿，警方通過查閱死者的電腦和手機(jī)串结，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,254評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門哑子，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人肌割，你說我怎么就攤上這事卧蜓。” “怎么了把敞？”我有些...
開封第一講書人閱讀 152,445評(píng)論 0贊 341
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵弥奸，是天一觀的道長。經(jīng)常有香客問我奋早，道長盛霎，這世上最難降的妖魔是什么赠橙？我笑而不...
開封第一講書人閱讀 55,185評(píng)論 1贊 278
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮愤炸，結(jié)果婚禮上期揪，老公的妹妹穿的比我還像新娘。我一直安慰自己规个，他們只是感情好凤薛，可當(dāng)我...
茶點(diǎn)故事閱讀 64,178評(píng)論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著诞仓，像睡著了一般缤苫。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上墅拭，一...
開封第一講書人閱讀 48,970評(píng)論 1贊 284
城市分裂傳說
那天活玲，我揣著相機(jī)與錄音，去河邊找鬼谍婉。笑死翼虫，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的屡萤。我是一名探鬼主播珍剑，決...
沈念sama閱讀 38,276評(píng)論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼死陆！你這毒婦竟也來了招拙？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 36,927評(píng)論 0贊 259
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤措译，失蹤者是張志新（化名）和其女友劉穎别凤，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體领虹，經(jīng)...
沈念sama閱讀 43,400評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡规哪，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,883評(píng)論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了塌衰。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片诉稍。...
茶點(diǎn)故事閱讀 37,997評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖最疆，靈堂內(nèi)的尸體忽然破棺而出杯巨，到底是詐尸還是另有隱情，我是刑警寧澤努酸，帶...
沈念sama閱讀 33,646評(píng)論 4贊 322
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布服爷，位于F島的核電站，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏仍源。R本人自食惡果不足惜心褐，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,213評(píng)論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望笼踩。院中可真熱鬧檬寂，春花似錦、人聲如沸戳表。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,204評(píng)論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽匾旭。三九已至镣屹，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間价涝，已是汗流浹背女蜈。一陣腳步聲響...
開封第一講書人閱讀 31,423評(píng)論 1贊 260
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留色瘩，地道東北人伪窖。一個(gè)月前我還...
沈念sama閱讀 45,423評(píng)論 2贊 352
代替公主和親
正文我出身青樓，卻偏偏與公主長得像居兆，于是被迫代替她去往敵國和親覆山。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,722評(píng)論 2贊 345