Node2vec簡(jiǎn)述

繼續(xù)萬物皆可embedding之旅，在DeepWalk之后出現(xiàn)了Line和Node2vec兩種改進(jìn)算法，Line的兩階段方式個(gè)人覺得太過丑陋，因此直接跳到Node2vec，其考慮了BFS和DFS兩種搜索策略，能夠更充分的對(duì)圖網(wǎng)絡(luò)進(jìn)行同質(zhì)性和結(jié)構(gòu)相似性的建模，因此也取得了非常好的結(jié)果。

Tips

首先作者闡明了在類似社交網(wǎng)絡(luò)圖結(jié)構(gòu)中，在兩種情況下，node的embedding需要非常的相似，第一是同質(zhì)性，即node處在同一個(gè)社交團(tuán)體中，下圖中的u和s1，s2，s3，s4；第二是結(jié)構(gòu)相似性，即社交群的中心節(jié)點(diǎn)或者是兩個(gè)社交群之間的鏈接節(jié)點(diǎn)，下圖中的u和s6。因此我們的采樣方式需要針對(duì)這些情況作出更合理的采樣，以此使得后續(xù)的skipgram能夠?qū)ν|(zhì)性和結(jié)構(gòu)相似性作出較好的建模。

為什么BFS和DFS的搜索策略能夠反映同質(zhì)性和結(jié)構(gòu)相似性呢。首先需要明確一點(diǎn)，同質(zhì)性更強(qiáng)調(diào)節(jié)點(diǎn)與節(jié)點(diǎn)間的連接關(guān)系，而結(jié)構(gòu)相似性不強(qiáng)調(diào)這一點(diǎn)，即使是非常遠(yuǎn)的節(jié)點(diǎn)，也可能具有非常相似的結(jié)構(gòu)，但是基本不太可能具有同質(zhì)性。BFS，廣度搜索，可以對(duì)結(jié)構(gòu)相似性作出更好的建模，因?yàn)榻Y(jié)構(gòu)相似的節(jié)點(diǎn)比如中心節(jié)點(diǎn)和橋節(jié)點(diǎn)的結(jié)構(gòu)表達(dá)，僅僅需要觀測(cè)其鄰接節(jié)點(diǎn)就能夠有一個(gè)很直觀的刻畫；而對(duì)于DFS，深度搜索，其更能在一個(gè)宏觀的角度反映出一個(gè)節(jié)點(diǎn)與其周圍節(jié)點(diǎn)(不一定是最近鄰節(jié)點(diǎn))的局部關(guān)系，需要多走一點(diǎn)，看多一點(diǎn)，variance高一點(diǎn)，才能了解整個(gè)局部關(guān)系，因此更適合社交群的建模。

通過控制參數(shù)來實(shí)現(xiàn)靈活的調(diào)整BFS和DFS自由度的采樣算法，使得采樣出的序列能夠更好的反應(yīng)同質(zhì)性和結(jié)構(gòu)相似性。

假設(shè)在0時(shí)刻，采樣到的節(jié)點(diǎn)為t，在1時(shí)刻，采樣到的節(jié)點(diǎn)為V，那么在2時(shí)刻，從V轉(zhuǎn)移到節(jié)點(diǎn)x的概率是這樣定義的：

需要注意的是，這里的距離的源節(jié)點(diǎn)是t而不是現(xiàn)在所處的節(jié)點(diǎn)V。參數(shù)p控制返回到源節(jié)點(diǎn)的概率，p值大的話，表示不容易進(jìn)行重復(fù)采樣，使得walk進(jìn)行適度的向外探索，避免重復(fù)冗余。參數(shù)q控制BFS和DFS的程度，具體來說，q大于1，即在t節(jié)點(diǎn)，下一步更容易采樣到距離源節(jié)點(diǎn)一跳的節(jié)點(diǎn)，即周圍節(jié)點(diǎn)，傾向于BFS。而q小于1，下一步更容易采樣到離源節(jié)點(diǎn)2跳的節(jié)點(diǎn)，傾向于DFS。在真正采樣的過程中，這些轉(zhuǎn)移概率是可以事先算好的，所以并不會(huì)影響采樣的效率。確定完采樣策略后，接下來的操作基本和DeepWalk別無二致了。

看一個(gè)toy example。上半圖是p=1，q=0.5的采樣學(xué)到的embedding的可視圖，很明顯是對(duì)同質(zhì)性的刻畫，對(duì)應(yīng)DFS；下半圖是p=1，q=2的可視圖，很明顯是對(duì)中心節(jié)點(diǎn)、橋節(jié)點(diǎn)和邊緣節(jié)點(diǎn)的刻畫，對(duì)應(yīng)BFS。

最后引論文中的一句話作為總結(jié) we observed that BFS can explore only limited neighborhoods. This makes BFS suitable for characterizing structural equivalences in network that rely on the immediate local structure of nodes. On the other hand, DFS can freely explore network neighborhoods which is important in discovering homophilous communities at the cost of high variance.

參考文獻(xiàn)

Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016: 855-864.

總結(jié)

以上是生活随笔為你收集整理的node2vec文献出处_社交网络分析(五)-Node2Vec的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。