GraRep: Learning Graph Representations with Global Structural Information
一種基于全局信息的圖結(jié)點(diǎn)特征向量學(xué)習(xí)算法
1.背景
DW相關(guān)方法追葡，在經(jīng)驗(yàn)上是有效的，但沒有給出損失函數(shù)的具體定義。在本論文中过咬，提出了一個(gè)明確的損失函數(shù)搔耕。
GraRep考慮兩個(gè)信息：
- 兩個(gè)頂點(diǎn)的長(zhǎng)距離關(guān)系治唤，
- 不同的 k-step
2.原理
2.1 Graphs and Their Representations
：一個(gè)信息網(wǎng)絡(luò)被定義為
贿条，其中
是頂點(diǎn)集合处窥，每個(gè)代表一個(gè)數(shù)據(jù)對(duì)象嘱吗，
是頂點(diǎn)之間的邊集，代表兩個(gè)數(shù)據(jù)對(duì)象之間的關(guān)系滔驾。
無(wú)權(quán)重的圖中谒麦，鄰接矩陣中的元素值為0 或者 1 ，0 表示兩個(gè)頂點(diǎn)無(wú)連接哆致、1表示兩個(gè)頂點(diǎn)有鏈接绕德；對(duì)于有權(quán)重的圖，
表示從節(jié)點(diǎn)
到節(jié)點(diǎn)
的權(quán)重摊阀；在本文中只考慮非負(fù)權(quán)重情況耻蛇；
表示節(jié)點(diǎn)
表的個(gè)數(shù)剩瓶，由于使用矩陣表示，可該矩陣是一個(gè)對(duì)角矩陣城丧，可以使用鄰接矩陣
定義
假設(shè)： 節(jié)點(diǎn)
這里給出來定義節(jié)點(diǎn)
GraRep考慮兩個(gè)信息：
- 兩個(gè)頂點(diǎn)的長(zhǎng)距離關(guān)系亡哄，
- 不同的 k-step
k-step 可以獲取圖的全局結(jié)果信息枝缔，舉例：
1-step：兩個(gè)節(jié)點(diǎn)直接相連；
a vs e： a 中兩個(gè)節(jié)點(diǎn)是強(qiáng)鏈接蚊惯， e 中兩個(gè)節(jié)點(diǎn)是弱連接愿卸；
2-step：兩個(gè)節(jié)點(diǎn)通過另外一個(gè)節(jié)點(diǎn)鏈接；
b vs f： b 中 A1與A2 共享了很多鄰居節(jié)點(diǎn)截型，共享鏈接越多趴荸，節(jié)點(diǎn)之間鏈接越強(qiáng)；
3-step：兩個(gè)節(jié)點(diǎn)通過另外兩個(gè)節(jié)點(diǎn)鏈接宦焦；
c vs g
4-step：兩個(gè)節(jié)點(diǎn)通過另外三個(gè)節(jié)點(diǎn)鏈接发钝；
d vs h
上圖a，節(jié)點(diǎn)與
波闹、
的表示可以壓縮成圖b的形式酝豪，由于在計(jì)算中都轉(zhuǎn)化為矩陣了，這種說明感覺是多余的精堕。孵淘。。
2.2 Loss Function On Graph
k -step 轉(zhuǎn)移概率為：
k-step loss function：
求導(dǎo)分解后看出，最后的結(jié)果是兩個(gè)向量的乘機(jī)庄撮，而這兩個(gè)向量對(duì)應(yīng)圖中的兩個(gè)節(jié)點(diǎn)背捌，也就是這個(gè)向量表示的節(jié)點(diǎn)信息。上面就出現(xiàn)了矩陣分解的過程：
2.3 Optimization with Matrix Factorization
可能為0 重窟，這里作非零處理载萌；
下面就是SVD分解的過程惧财，直接截圖了巡扇。
2.4 ALGORITHM
