摘要：個假設(shè)領(lǐng)域內(nèi)節(jié)點獨立。參數(shù)的意義分別如下如果，那么采樣會盡量不往回走，對應(yīng)上圖的情況，就是下一個節(jié)點不太可能是上一個訪問的節(jié)點。如果，那么游走會傾向于在起始點周圍的節(jié)點之間跑，可以反映出一個節(jié)點的特性。顯示了當設(shè)置，時的示例。

論文題目：《node2vec Scalable Feature Learning for Network》
發(fā)表時間：  KDD 2016 
論文作者：  Aditya Grover;Aditya Grover; Jure Leskovec
論文地址：  Download
Github：      Go

概述

　　node2vec is an algorithmic framework for representational learning on graphs. Given any graph, it can learn continuous feature representations for the nodes, which can then be used for various downstream machine learning tasks.

• homophily：在同質(zhì)性假設(shè)下，高度連接且屬于相似網(wǎng)絡(luò)集群或社區(qū)的節(jié)點應(yīng)該緊密地嵌入在一起。(例如，圖1中的節(jié)點 $s_1$ 和 $u$ 屬于同一個網(wǎng)絡(luò)社區(qū))
• structural equivalence：在結(jié)構(gòu)等價假設(shè)下，在網(wǎng)絡(luò)中具有相似結(jié)構(gòu)角色的節(jié)點應(yīng)該緊密地嵌入在一起。(例如，圖1中的節(jié)點 $u$ 和 $s_6$ 作為它們相應(yīng)社區(qū)的樞紐)。

　　　　　　　　

　　介紹傳統(tǒng)方法的不足，以及本文采用的自然語言處理方法的介紹。

3. Feature learning framework

　　　　objective function: 

 　　　　　　$/underset{f}{max} /quad  /sum /limits _{u /in V} /log /operatorname{Pr}/left(N_{S}(u) /mid f(u)/right)    /quad  /quad /quad /quad (1)$

　　2個假設(shè)

• • Conditional independence：領(lǐng)域內(nèi)節(jié)點獨立。

• • Symmetry in feature space：點間的影響的一樣的，即：a 對 b 的影響和 b 對 a 的影響一樣。

　　　　　　${/large /operatorname{Pr}/left(n_{i} /mid f(u)/right)=/frac{/exp /left(f/left(n_{i}/right) /cdot f(u)/right)}{/sum_{v /in V} /exp (f(v) /cdot f(u))}} $

　　總結(jié)上述兩個假設(shè)得：

　　　　$/max _{f} /sum /limits_{u /in V}/left[-/log Z_{u}+/sum/limits_{n_{i} /in N_{S}(u)} f/left(n_{i}/right) /cdot f(u)/right]$

　　其中 $Z_{u}=/sum /limits _{v /in V} /exp (f(u) /cdot f(v))$ 。

 　　推導(dǎo)過程：

　　　　${/large /begin{array}{l}/underset{f}{max}  /sum /limits _{u /in V} /log P_{r}/left(N_{s}(u) /mid f(u)/right)///left.=/underset{f}{max}  /sum /limits _{u /in V} /log /prod /limits_{n_{i} /in N_{s}(u)} P_{r}/left(n_{i}/right) f(u)/right)//=/underset{f}{max} /sum /limits_{u /in V} /sum /limits_{n_{i} /in N_{s}(u)} /log /frac{/operatorname{exp}/left(f/left(n_{i}/right) /cdot f(u)/right)}{/sum /limits_{V /in V} /exp (f(v) /cdot f(u))}//=/underset{f}{max} /left[-/sum /limits_{n_{i} /in N_{s}(u)} /log Z_{u}+/sum /limits_{n_{i} /in N_{s}(u)} f/left(n_{i}/right) f(u)/right]//=/underset{f}{max} /left[-/left|N_{s}(u)/right| /log Z_{u}+/sum /limits_{n_{i} /in N_{s}(u)} f/left(n_{i}/right) f(u)/right]/end{array}} $

　　推導(dǎo)過程中常數(shù) $/left|N_{s}(u)/right|$ 忽略掉了，可能是因為這邊采用了負采樣策略，和鄰居節(jié)點沒有關(guān)系。

　　鄰域 $N_{s}(u)$  并不局限于近鄰，但根據(jù)采樣策略S，可以有很大不同的結(jié)構(gòu)。

3.1 Classic search strategies

　　鄰域 $N_{s}(u)$  的大小固定為 $k$ ，使用不同的采樣策略。這里提出兩種采樣策略：BFS and DFS。

　　DFS：鄰域被限制為源的近鄰節(jié)點。

　　　　在 Figure 1 中，假設(shè) $k=3$， 則在 $u$ 的附近采樣 node $s_{1}, s_{2}, s_{3}$。

　　BFS：鄰域由距離源節(jié)點的距離順序采樣的節(jié)點組成。

　　　　在 Figure 1 中，假設(shè) $k=3$， 則在 $u$ 的某路徑上采樣 node $s_{4}, s_{5}, s_{6}$。

3.2 node2vec

　　基于上述觀察結(jié)果，我們設(shè)計了一種靈活的鄰域采樣策略，使我們能夠平滑地在 BFS 和 DFS 之間進行插值。我們通過開發(fā)一種靈活的 biased random walk 來實現(xiàn)這一點，該程序可以以 BFS 和 DFS 的方式探索社區(qū)。

3.2.1 Random Walks

　　形式上，給定一個源節(jié)點  $u$ ，我們模擬一個固定長度為  $l$  的隨機游動。設(shè)  $c_i$  表示行走中的第  $i$  個節(jié)點，以  $c_0=u$  開始。節(jié)點  $c_i$  由以下分布方式生成：

　　　　$P/left(c_{i}=x /mid c_{i-1}=v/right)=/left/{/begin{array}{ll}/frac{/pi_{v x}}{Z} & /text { if }(v, x) /in E //0 & /text { otherwise } /end{array}/right.$

　　其中  $/pi_{v x}$  為節(jié)點  $v$  和節(jié)點  $x$  之間的非歸一化轉(zhuǎn)移概率，$Z$  為歸一化常數(shù)。

3.2.2 Search bias α

　　最簡單的方法：  $/pi_{v x}=w_{v x}$  ，對于無權(quán)圖設(shè)置  $w_{v x} = 1$，對于有權(quán)圖  $/pi_{v x}=w_{v x}$  。

　　我們定義了一個具有兩個參數(shù)  $p$  和  $q$  的二階隨機游走：

　　對于一個隨機游走，如果已經(jīng)采樣了  $(t,v)$  ，即現(xiàn)在停留在節(jié)點  $v$  上，那么下一個要采樣的節(jié)點  $x$  是？作者定義了一個概率分布，也就是一個節(jié)點到它的不同鄰居的轉(zhuǎn)移概率： 

　　　　$/pi_{v x}=/alpha_{p q}(t, x) /cdot w_{v x}$

　　其中：

　　　　$/alpha_{p q}(t, x)=/left/{/begin{array}{ll}/frac{1}{p} & /text { if } d_{t x}=0 //1 & /text { if } d_{t x}=1 ///frac{1}{q} & /text { if } d_{t x}=2/end{array}/right.$

　　這里，$d_{tx}$  表示節(jié)點  $t$  和節(jié)點  $x$  之間的最短路徑距離。

　　$/alpha_{p q}(t, x)$ 解釋如下：

• • 如果  $t$  與  $x$  相等，那么采樣  $x$  的概率為 $/frac{1}{p} $ ；
  • 如果  $  /mathrm{t}$  與  $/mathrm{x}$  相連，那么采樣 $/mathrm{x}$  的概率 $1$ ;
  • 如果  $t$  與  $x$  不相連，那么采樣  $x$  概率為 $/frac{1}{q} $。

　　參數(shù) $p、q $ 的意義分別如下：

　　Return parameter p：

• • 如果 $p>max(q,1)$，那么采樣會盡量不往回走，對應(yīng)上圖的情況，就是下一個節(jié)點不太可能是上一個訪問的節(jié)點  $t$。
  • 如果 $p

　　In-out parameter q：

• • 如果  $q>1$ ，那么游走會傾向于在起始點周圍的節(jié)點之間跑，可以反映出一個節(jié)點的 BFS 特性。
  • 如果  $q<1$ ，那么游走會傾向于往遠處跑，反映出 DFS 特性。

　　當  $p=1，q=1$  時，游走方式就等同于  DeepWalk  中的隨機游走。

• • 存儲圖中每個節(jié)點的近鄰的空間復(fù)雜度為  $O(|E|)$ 。對于二階隨機游走，存儲每個節(jié)點的鄰居之間的互連是有幫助的，導(dǎo)致空間復(fù)雜度為 $O(a^2|V|)$，其中  $a$  是圖的平均度，對于現(xiàn)實世界的網(wǎng)絡(luò)來說通常很小。
  • 與經(jīng)典的基于搜索的采樣策略相比，隨機游走的另一個關(guān)鍵優(yōu)勢是其時間復(fù)雜度。通過在樣本生成過程中施加圖的連通性，跨不同源節(jié)點重用采樣來提高有效采樣率。因此，我們的有效復(fù)雜度是每個樣本的$O/left(/frac{l}{k(l-k)}/right)$。請注意，樣本重用可能會在整個過程中引入一些偏差。然而，我們觀察到，它極大地提高了效率。
    • 舉例：一個長度 $k=6$ 的隨機游走序列 $/left/{u, s_{4}, s_{5}, s_{6}, s_{8}, s_{9}/right/}$ ，為每個節(jié)點生成鄰居信息，$N_{S}(u)=/left/{s_{4}, s_{5}, s_{6}/right/}$  ,   $N_{S}/left(s_{4}/right)=/left/{s_{5}, s_{6}, s_{8}/right/}$ ,   $N_{S}/left(s_{5}/right)=/left/{s_{6}, s_{8}, s_{9}/right/}$

3.2.3 The node2vec algorithm

　　算法參數(shù)：graph  $G$、dimension $d$、Walks per node  $r$，Walk length  $l$，Context size $k$ ，Return  $p$、In-out $q$ 。

1. 1. 根據(jù) $p、q$ 以及權(quán)重參數(shù)計算節(jié)點到它鄰居的轉(zhuǎn)移概率；
   2. 將轉(zhuǎn)移概率加到graph  $G$  中形成  $G$。
   3. $walks$ 用來存儲隨機游走路徑，初始化時為空。
   4. 外循環(huán) $r$  次表示每個節(jié)點作為初始節(jié)點要生成  $r$  個隨機游走。
   5. 然后對圖中每個節(jié)點。
   6. 生成一條隨機游走  $walk$ 。
   7. 將  $walk $  添加到  $walks$  中保存。
   8. 然后用  $SGD$  的方法對  $walks$  進行訓(xùn)練。

　　Step 6 中一條 $walk$ 的生成方式如下：

1. 1. 將初始節(jié)點 $u$ 添加進去。
   2. $walk$ 的長度為 $l$，因此還要再循環(huán)添加 $l-1$個節(jié)點。
   3. 當前節(jié)點設(shè)為 $walk$ 最后添加的節(jié)點。
   4. 找出當前節(jié)點的所有鄰居節(jié)點。
   5. 根據(jù)轉(zhuǎn)移概率采樣選擇某個鄰居 $s$。
   6. 將該鄰居添加到 $walk$ 中。

3.3 Learning edge features

　　我們通常對涉及節(jié)點對而不是單個節(jié)點的預(yù)測任務(wù)感興趣，即  link prediction 。這里定義一個  $g(u,v)$  使用  $f(u)$  和  $f(v)$  來代表邊的特征向量。

4. EXPERIMENTS

4.1 Case Study: Les Misérables network

　　Figure 3（top）顯示了當設(shè)置  $p=1，q=0.5$  時的示例。不同網(wǎng)絡(luò)社區(qū)使用不相同的顏色著色。在這個設(shè)置中，node2vec 發(fā)現(xiàn)了在小說的主要子情節(jié)中經(jīng)常相互作用的角色集群/社區(qū)。由于字符之間的邊緣是基于共現(xiàn)的，我們可以得出這一表征與同質(zhì)性密切相關(guān)的結(jié)論。

　　為發(fā)現(xiàn)哪些節(jié)點具有相同的結(jié)構(gòu)角色，我們使用相同的網(wǎng)絡(luò)，但設(shè)置了 $p=1，q=2$，使用  node2vec 獲得節(jié)點特征，然后根據(jù)所獲得的特征對節(jié)點進行聚類。在這里，  node2vec  獲得了一個節(jié)點對簇的互補分配，這樣顏色就對應(yīng)于結(jié)構(gòu)的等價性，如 Figure 3（bottom）所示。例如， node2vec 將藍色的節(jié)點嵌入在一起。這些節(jié)點代表了小說中不同子情節(jié)之間的橋梁。類似地，黃色節(jié)點主要代表位于外圍且交互作用有限的字符。我們可以為這些節(jié)點集群分配替代的語義解釋，但關(guān)鍵的結(jié)論是，  node2vec  并不與特定的等價概念綁定。正如我們通過實驗所表明的，這些等價的概念通常在大多數(shù)現(xiàn)實世界的網(wǎng)絡(luò)中表現(xiàn)出來，并對預(yù)測任務(wù)的學(xué)習(xí)表示的性能有重大影響。

4.2 Experimental setup

　　我們的實驗評估了通過  node2vec  在標準監(jiān)督學(xué)習(xí)任務(wù)上獲得的特征表示：multilabel classification for nodes and link prediction for edges。對于這兩項任務(wù)，我們根據(jù)以下特征學(xué)習(xí)算法來評估  node2vec  的性能：

　　具體來說，我們設(shè)置了  $d=128 , r=10  ,  l=80  ,  k=10$，并在一個 epoch 中進行優(yōu)化。我們使用 10 個隨機種子初始化重復(fù)實驗。對 10%標記數(shù)據(jù)進行  $ p、q∈{0.25、0.50、1、2、4}$  網(wǎng)格搜索的 10-fold cross-validation ，學(xué)習(xí)最佳  $p$  和  $q$。

　　Node feature representations 被輸入到一個   L2 regularization 的  one-vs-rest logistic regression classifier 上。我們使用 $Macro-F1 scores$ 作為評價標準。

　　對于更多的 fine-grained analysis，我們還比較了性能，同時將 $train-test split$ 從  $10%$  改變到  $90%$  ，學(xué)習(xí)參數(shù)  $p$  和  $q$  在  $10%$  的數(shù)據(jù)進行分析。在 Figure 4 中總結(jié)了  Micro-F1  和  Macro-F1  score  的結(jié)果。

4.4 Parameter sensitivity

　　　　　　　　

4.5 Perturbation Analysis

　　在第一種情況下，我們研究  missing edges  比列對性能的影響（相對于完整的網(wǎng)絡(luò)）。缺失邊是隨機選擇的，受網(wǎng)絡(luò)中連接組件數(shù)量保持固定的約束。如圖我們可以在Figure 5 b（top）中看到，隨著缺邊比列的增加，Macro-F1 分數(shù)大致呈線性下降，斜率較小。在圖隨著時間的推移而演化（例如引文網(wǎng)絡(luò)）或網(wǎng)絡(luò)構(gòu)建昂貴（例如生物網(wǎng)絡(luò)）時，對網(wǎng)絡(luò)中缺失邊緣的魯棒性尤為重要。

　　在第二個擾動設(shè)置中，我們在網(wǎng)絡(luò)中隨機選擇的節(jié)點對之間有噪聲的邊。如 Figure 5 b（bottom）所示，與  missing edges  的設(shè)置相比，node2vec  的性能最初下降的速度略快，但Macro-F1評分的下降速度隨著時間的推移逐漸減慢。同樣，node2vec  對  false edges  的魯棒性在一些情況下是有用的，如傳感器網(wǎng)絡(luò)，用于構(gòu)建網(wǎng)絡(luò)的測量值是有噪聲的。

4.6 Scalability

　　為了測試可伸縮性，我們使用  node2vec  學(xué)習(xí)節(jié)點表示，并使用   Erdo-Renyi Graph 的默認參數(shù)，Node 數(shù)量從 100 個節(jié)點增加到  1000,000  個節(jié)點，平均度設(shè)置為10 不變 。實驗如下：

　　采樣過程包括計算隨機游走的  transition probabilities（可忽略的?。┖湍M隨機游走的預(yù)處理。

4.7 Link prediction

　　在鏈路預(yù)測中，我們給出了一個去掉一定比例邊的網(wǎng)絡(luò)，并且我們想預(yù)測這些缺失的邊。

　　 We generate the labeled dataset of edges as follows: To obtain positive examples, we remove 50% of edges chosen randomly from the network while ensuring that the residual network obtained after the edge removals is connected, and to generate negative examples, we randomly sample an equal number of node pairs from the network which have no edge connecting them.

　　我們所考慮的分數(shù)是根據(jù)構(gòu)成這對節(jié)點的節(jié)點的鄰域集來定義的（Table 3）。

 　　實驗結(jié)果：

5 總結(jié)

『總結(jié)不易，加個關(guān)注唄！』

Datasets

Links to datasets used in the paper:

• BlogCatalog
• Protein-Protein Interaction Source Preprocessed
• Wikipedia Source Preprocessed
• Facebook
• arXiv ASTRO-PH