基于矩陣分解的圖算法

基于矩陣分解

快速簡潔呻惕，但屬性信息與結(jié)構(gòu)信息的融合比較困難。

1. Skip-Gram with Negative Sampling (SGNS)

損失函數(shù)

將中心詞 $w$ 與上下文 $c$ 的共現(xiàn)概率用sigmoid表示為
$\delta(\vec{w}^T\vec{c}) = \frac{1}{1+e^{-\vec{w}^T\vec{c}}}$
隨機抽取k個負樣本喻粹，則損失函數(shù)可寫為
$L = -\sum_w \sum_c d(w,c)\left[ \log(\delta(\vec{w}^T\vec{c}))+k\mathbb{E_{c_n \sim P_D}}\log(\delta(-\vec{w}^T\vec{c_n})) \right]$

使用 $d(c)$ 表示語料中包含上下文 $c$ 的組合數(shù)量蟆融， $D$ 表示語料中所有 $(w,c)$ 組合對的集合， $c_n$ 為采樣到的上下文向量守呜，服從分布 $P_D=\frac{d(c)}{|D|}$ 型酥。

負樣本損失表示為 $\delta(-\vec{w}^T\vec{c})$ 有利于后續(xù)推導。

等價于SPMI的分解

對 $L$ 中的 $(w,c)$ 進行合并同類項查乒，得到

$L(w,c) = d(w,c)\log(\delta(\vec{w}^T\vec{c}))+kd(w)\frac{d(c)}{|D|}\log(\delta(-\vec{w}^T\vec{c}))$
對 $x=\vec{w}^T\vec{c}$ 求導等零弥喉，得
$x=\vec{w}^T\vec{c}=\log(\frac{|D|d(w,c)}{d(w)d(c)})-\log(k)$
正好是逐點互信息(Pointwise Mutual Information)矩陣漂移Shifted了 $log(k)$ ，即SPMI玛迄。

PMI中元素為 $PMI(x,y)=\log\frac{P(x,y)}{P(x)P(y)}$ 由境。

PMI矩陣中的無關(guān)向量為 $-\infty$ ，可以規(guī)定只要positive蓖议，得到PPMI逸月，即 $PPMI=max(PMI,0)$ 眼虱。

兩者結(jié)合窍侧，得SPPMI(Shifted Positive PMI)矩陣壤蚜，即 $SPPMI_k(w,c)=max(PMI(w,c)-log(k),0)$ 。

這里證明為了方便修然，只在兩個節(jié)點之間進行了化簡和推導笛钝，其中softmax退化為了sigmiod质况。

同樣可以證明，基于Hierarchical Softmax的Skip-Gram分解的矩陣是
$M_{wc} = \log(\frac{d(w,c)}{d(w)})$

中心詞向量 $\vec{w}$ 矩陣 $W=[\vec{w_1},\vec{w_2}...]$ 玻靡，上下文向量 $\vec{c}$ 矩陣 $C=[\vec{c_1},\vec{c_2}...]$ 结榄，記SPMI為 $A$ ，則分解任務(wù)為
$A_{n \times n} = W_{d \times n}^TC_{d \times n}$
加上正則項后囤捻，優(yōu)化目標為
$L = ||A-W^TC||_F^2 + \frac{1}{2}(||W||_F^2+||C||_F^2)$

2. DeepWalk

DeepWalk

從每個節(jié)點出發(fā)n_walks次臼朗，每次均勻采樣連接節(jié)點，延申長度達walk_length后停止一次游走最蕾，生成一個序列依溯。對采樣的序列，使用word2vec的skip-gram直接訓練瘟则。

Node2Vec

改進游走方式，以便相似節(jié)點和同一社區(qū)節(jié)點更接近枝秤。

廣度優(yōu)先策略醋拧，使同一社區(qū)節(jié)點更接近；
深度優(yōu)先策略淀弹，使不通社區(qū)內(nèi)的相似節(jié)點更接近丹壕。

假設(shè)已由 $t$ 走到 $v$ ，下一個節(jié)點用 $x$ 表示薇溃，則游走方向由下式控制
$a_{pq}(t,x) = \begin{cases} \frac{1}{p} & d_{tx}=0\\ 1 & d_{tx}=1\\ \frac{1}{q} & d_{tx}=2 \end{cases}$
其中 $d_{tx}$ 表示從 $t$ 到 $x$ 的最短路徑長度菌赖。同時可以考慮邊權(quán)重。

3. Text-Associated DeepWalk (TADW)

DeepWalk的本質(zhì)是在近似重建 $t$ 步共現(xiàn)概率矩陣沐序。結(jié)合Hierarchical Softmax的Skip-Gram分解的矩陣
$M_{wc} = \log(a_{wc}) \\ a_{wc} = \frac{d(w,c)}{d(w) }$
我們只需要找到 $a_{wc}$ 的合理表達琉用，即可直接通過矩陣分解解決問題。

對DeepWalk策幼，假設(shè)只走1步邑时，不妨設(shè)為 $w$ 到 $c$ ，則兩點共現(xiàn)的條件概率應(yīng)為 $a_{wc}=1/d_w$ 特姐， $d_w$ 為節(jié)點 $w$ 的出度晶丘。我們將對應(yīng)的標準化的鄰接矩陣記為 $A$ 。與PageRank所使用的矩陣一致唐含。

于是 $t$ 步共現(xiàn)概率矩陣和要分解的矩陣是
$\hat{A}=(A+A^2+...+A^t)/t \\ M = \log(\hat{A})$
相應(yīng)的損失函數(shù)為
$L = ||M-W^TC||_F^2 + \frac{1}{2}(||W||_F^2+||C||_F^2)$
融合屬性矩陣 $S$ 則為
$L = ||M-W^TCS^T||_F^2 + \frac{1}{2}(||W||_F^2+||C||_F^2)$

4. Accelerated Attributed Network Embedding (AANE)

使用各節(jié)點屬性構(gòu)建余弦相似度矩陣 $S$ 浅浮，分解為 $HH^T$ ，而具有相鄰關(guān)系的節(jié)點對應(yīng)隱變量 $h$ 也應(yīng)該接近

$L = ||S-HH^T||_F^2+\lambda \sum_{(i,j)\in E} w_{ij} ||h_i-h_j||_2$

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

人面猴
序言：七十年代末捷枯，一起剝皮案震驚了整個濱河市滚秩，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌铜靶，老刑警劉巖叔遂，帶你破解...
沈念sama閱讀 218,284評論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件他炊，死亡現(xiàn)場離奇詭異，居然都是意外死亡已艰，警方通過查閱死者的電腦和手機痊末，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,115評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來哩掺，“玉大人凿叠，你說我怎么就攤上這事〗劳蹋” “怎么了盒件？”我有些...
開封第一講書人閱讀 164,614評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長舱禽。經(jīng)常有香客問我炒刁，道長，這世上最難降的妖魔是什么誊稚？我笑而不...
開封第一講書人閱讀 58,671評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任翔始，我火速辦了婚禮，結(jié)果婚禮上里伯，老公的妹妹穿的比我還像新娘城瞎。我一直安慰自己，他們只是感情好疾瓮，可當我...
茶點故事閱讀 67,699評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布脖镀。她就那樣靜靜地躺著，像睡著了一般狼电。火紅的嫁衣襯著肌膚如雪蜒灰。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,562評論 1贊 305
城市分裂傳說
那天漫萄，我揣著相機與錄音卷员，去河邊找鬼。笑死腾务，一個胖子當著我的面吹牛毕骡，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播岩瘦，決...
沈念sama閱讀 40,309評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼未巫，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了启昧？” 一聲冷哼從身側(cè)響起叙凡，我...
開封第一講書人閱讀 39,223評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎密末，沒想到半個月后握爷，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體跛璧，經(jīng)...
沈念sama閱讀 45,668評論 1贊 314
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,859評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年新啼，在試婚紗的時候發(fā)現(xiàn)自己被綠了追城。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 39,981評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡燥撞，死狀恐怖座柱，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情物舒，我是刑警寧澤色洞，帶...
沈念sama閱讀 35,705評論 5贊 347
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站冠胯，受9級特大地震影響火诸，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜荠察，卻給世界環(huán)境...
茶點故事閱讀 41,310評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一惭蹂、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧割粮，春花似錦、人聲如沸媚污。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,904評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽耗美。三九已至京髓，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間商架，已是汗流浹背堰怨。一陣腳步聲響...
開封第一講書人閱讀 33,023評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留蛇摸，地道東北人备图。一個月前我還...
沈念sama閱讀 48,146評論 3贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長得像赶袄，于是被迫代替她去往敵國和親揽涮。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 44,933評論 2贊 355

基于矩陣分解的圖算法