node2vec和deep walk到底在捕捉網路的什麼特性
- 2020 年 12 月 16 日
- AI
上圖為bfs隨機遊走策略產生的embedding結果，下圖為dfs隨機遊走策略產生的embedding結果的可視化，顏色接近的節點代表其embedding的相似性更強，可以看到bfs的搜索策略非常類似於社區發現所得到的社區相似性，即更加接近一種直觀容易解釋的思路，偏向於一階和二階近鄰這類的相似性，也就是距離接近，特別是直接連接的nodes之間的embedding結果接近，也就是「結構性」，可以理解為，BFS的搜索策略能夠捕捉到「近鄰相似性」；
而dfs則看起來比較不那麼直觀了，但是其實從傳統graph的一些評價指標可以進行分析和總結，例如pagerank，pagerank值計算的是節點的流行度，比如說中國的明星和美國的明星，二者的近鄰相似度肯定是非常低的，但是它們都在「演藝圈」這個巨大的graph中扮演著相似的角色，這一點我們可以通過pagerank這類統計方法來得到，成龍和傑森斯坦森之間的pagerank值的差異相對於成龍或傑森斯坦森和其它18線小明星的pagerank值的差異明顯要小得多，而我們的dfs捕捉的相似性指的就是這種相似性，即 節點在更大的範圍內（可能橫跨多個社區而形成的大子圖，具體根據random walk的步數來決定）中扮演的角色（同質性，同樣性質的相似性），例如我們看第二幅圖，連接不同nodes的「樞紐節點」其embedding的相似度往往比較高，從社交網路的角度來說，這些樞紐節點都是「交際花」，雖然她們彼此之間的直接相連的近鄰相似度可能非常低，但是它們「交際」的性質是非常相似的，即在局部的子圖中扮演著相似的角色；
然後是關於deepwalk的問題，首先我們需要知道的是，目前開源的框架里大部分只實現了node2vec，因為我們可以通過將p和q這兩個超參數設定為1，使得node2vec退化為deepwalk來使用，即：
上圖的公式中，p和q均為1的時候，node2vec退化為deepwalk，因此實際上我們可以知道，deepwalk本身並不是基於什麼dfs之類的做遊走的，就是一個純粹的隨機亂走，它即可以捕捉到部分結構性也可以捕捉到部分同質性，具體deepwalk能夠捕捉到什麼樣的性質，就看天意了，所以我們不能說deepwalk就是基於dfs的遊走策略遊走主要捕捉同質性，而應該說deepwalk同時捕捉兩種特性然而兩種特性都捕捉的不是非常到位，而node2vec更像是基於deepwalk上的一個靈活的框架，因為我們可以通過指定超參數來改變我們想要進行embedding的目的，如果我們面臨的實際問題，定義相似性為同質性，這裡舉個例子：
以欺詐問題為例，我們看一下capital one的這篇經典論文里的場景：
將二分圖投影成2個同構圖，然後利用deepwalk各自生成embedding：
用戶-用戶關係圖：兩個用戶在同一個商戶中發生交易，則兩個用戶之間存在一條邊。
商戶-商戶關係圖：同一個用戶與兩個商戶發生交易，則兩個商戶之間有一條邊。
我們假設使用的是 用戶-用戶關係圖，並且認為欺詐分子的欺詐模式是 欺詐用戶集中在兩三家商戶上瘋狂消費刷漏洞騙錢，則在graph中，這些用戶會呈現出比較明顯的社區結構，即他們之間的距離都是非常接近的甚至可能互相直接連接，而不同用戶在不同的局部社區結構中扮演的相同角色的相似性，和欺詐的手段完全沒有關係，那麼這個時候我們可以使用node2vec，令p越小越好，q越大越好從而盡量cover這種近鄰相似性，而反過來，如果欺詐分子的欺詐模式是分散的，例如一個欺詐用戶x1在a、b、c三個商家消費，一個欺詐用戶x2的d、e、f三個商家消費，二者的近鄰相似性較低，但是假設存在這種情況，x1和x2之間雖然存在一定的距離，但是這個距離並不十分遠，這兩個用戶分別處於近鄰的社區結構，並且恰好分別是這兩個社區結構中流行度很高的用戶，則我們可以考慮使用node2vec，令p越大越好，q越小越好從而cover這種「網路角色」相似性，注意，這裡我們強調的是近鄰的社區，因為假設兩個節點之間雖然在各自的局部社區扮演相同或相似的角色，比如流行度都很高，但是這兩個局部社區之間的間隔非常的遙遠，那麼node2vec根本cover不到這種遠距離局部社區相同或相似角色的相似性，因為我們random walk的步數是有限的，比如二者距離了50個hops，而walks的數量只有10步，走到死也沒法恰好在同一個random walk產生的序列里；
因此，只能說deepwalk能夠捕捉節點之間的共現性，這個共現性可能包含了同質性也可能包含了結構性，而node2vec可以讓使用者靈活的定義我們要捕捉更多的結構性還是更多的同質性，置於基於整個graph的同質性，比如上面所說的遠距離局部社區相同或者相似角色的embedding問題，我們就需要考慮使用別的embedding演算法來解決了，比如計算複雜度非常高基本沒法在大規模graph上運行的struc2vec。
