論文名稱：node2vec: Scalable Feature Learning for Networks

論文下載：https://arxiv.org/abs/1607.00653#

論文年份：SIGKDD 2016

論文被引：7065（2022/04/26）

數據集+實現：http://snap.stanford.edu/node2vec

論文總結

什么是 node2vec？

node2vec，一種用于網絡中可擴展特征學習的半監督算法框架。其可以用于學習網絡中結點的連續特征表示。其學習結點到特征的低維空間映射，最大限度地保留節點的網絡鄰域的似然。定義了節點的網絡鄰域的概念，并設計了有偏隨機游走用于探索不同的鄰域。

ABSTRACT

網絡中節點和邊緣的預測任務需要在學習算法所使用的工程特征上做出認真的努力。最近在更廣泛的表示學習領域的研究通過學習特征本身在自動預測方面取得了重大進展。然而，目前的特征學習方法的表現力不足以捕捉網絡中觀察到的連接模式的多樣性。

在這里，我們提出了 node2vec，這是一種用于學習網絡中節點的連續特征表示的算法框架。在 node2vec 中，我們學習節點到特征的低維空間的映射，最大限度地保留節點的網絡鄰域的似然。我們定義了一個節點的網絡鄰域的靈活概念，并設計了一個有偏隨機游走程序，它有效地探索了不同的鄰域。我們的算法概括了基于嚴格的網絡鄰域概念的先前工作，我們認為在探索鄰域時增加的靈活性是學習更豐富表示的關鍵。

我們展示了 node2vec 在來自不同領域的幾個真實世界網絡中對多標簽分類和鏈接預測的現有最先進技術的功效。總之，我們的工作代表了一種在復雜網絡中有效學習最先進的任務無關表示的新方法。

1. INTRODUCTION

網絡分析中的許多重要任務都涉及對節點和邊的預測。在典型的節點分類任務中，我們感興趣的是預測網絡中最可能的節點標簽 [33]。例如，在社交網絡中，我們可能對預測用戶的興趣感興趣，或者在蛋白質-蛋白質相互作用網絡中，我們可能對預測蛋白質的功能標簽感興趣 [25, 37]。類似地，在鏈路預測中，我們希望預測網絡中的一對節點是否應該有一條邊連接它們[18]。鏈接預測在各種領域都很有用；例如，在基因組學中，它可以幫助我們發現基因之間的新相互作用，在社交網絡中，它可以識別現實世界的朋友 [2, 34]。

任何有監督的機器學習算法都需要一組信息豐富的、有辨別力的和獨立的特征。在網絡上的預測問題中，這意味著必須為節點和邊構建特征向量表示。一個典型的解決方案是基于專家知識手工設計特定領域的特征。即使人們不考慮特征工程所需的繁瑣工作，這些特征通常也是為特定任務設計的，并且不能泛化到不同的預測任務中。

另一種方法是通過解決優化問題來學習特征表示 [4]。特征學習的挑戰在于定義一個目標函數，這涉及平衡計算效率和預測準確性的權衡。在頻譜的一方面，人們可以直接針對找到優化下游預測任務性能的特征表示。雖然這種有監督的過程具有良好的準確性，但由于需要估計的參數數量激增，它的代價是訓練時間復雜度高。在另一個極端，可以將目標函數定義為獨立于下游預測任務，并且可以以純無監督的方式學習表示。這使得優化在計算上變得高效，并且具有精心設計的目標，它導致與任務無關的特征在預測準確性方面與特定于任務的方法密切匹配 [21, 23]。

然而，當前的技術未能令人滿意地定義和優化網絡中可擴展的無監督特征學習所需的合理目標。基于線性和非線性降維技術的經典方法，如主成分分析、多維縮放及其擴展 [3、27、30、35] 優化目標，該目標轉換網絡的代表性數據矩陣，使其最大化數據表示的方差。因此，這些方法總是涉及適當數據矩陣的特征分解，這對于大型現實世界網絡來說是昂貴的。此外，由此產生的潛在表示在網絡上的各種預測任務上表現不佳。

或者，我們可以設計一個旨在保護節點的局部鄰域的目標。可以使用類似于僅在單個隱藏層前饋神經網絡上的反向傳播的隨機梯度下降 (SGD) 來有效地優化目標。最近在這個方向上的嘗試 [24, 28] 提出了有效的算法，但是依賴于網絡鄰域的嚴格概念，這導致這些方法很大程度上對網絡特有的連接模式不敏感。具體來說，網絡中的節點可以根據它們所屬的社區（即同質性，homophily）進行組織；在其他情況下，組織可以基于網絡中節點的結構角色（即結構等效性，structural equivalence）[7,10,36]。例如，在圖 1 中，我們觀察到節點 u 和 s1 屬于同一個緊密聯系的節點社區，而兩個不同社區中的節點 u 和 s6 共享中心節點的相同結構角色。現實世界的網絡通常表現出這種等價的混合。因此，必須允許一種靈活的算法來學習節點表示，同時遵守以下兩個原則：學習將來自同一網絡社區的節點緊密嵌入在一起的表示的能力，以及學習具有相似角色的節點具有相似嵌入的表示的能力。這將允許特征學習算法在廣泛的領域和預測任務中進行泛化。

現在的工作。我們提出了 node2vec，一種用于網絡中可擴展特征學習的半監督算法。我們使用 SGD 優化了一個定制的基于圖的目標函數，這是由自然語言處理的先前工作所激發的 [21]。直觀地說，我們的方法返回的特征表示可以最大限度地保留 d 維特征空間中節點的網絡鄰域的似然。我們使用二階隨機游走方法為節點生成（樣本）網絡鄰域。

我們的主要貢獻是定義了一個靈活的節點網絡鄰居的概念。通過選擇適當的鄰域概念，node2vec可以學習基于節點的網絡角色和/或它們所屬的社區來組織節點的表示。我們通過開發有偏隨機游（biased random walks）走來實現，這種有偏隨機游走有效地探索給定節點的不同鄰域。與先前工作[24，28]中的嚴格搜索過程相比，所得到的算法是靈活的，通過可調參數給予我們對搜索空間的控制。因此，我們的方法概括了以前的工作，可以模擬網絡中觀察到的等價的全部頻譜。控制搜索策略的參數有一個直觀的解釋，并且偏向于不同的網絡探索策略。這些參數也可以使用一小部分標記數據以半監督的方式直接學習。

我們還展示了如何將單個節點的特征表示擴展到節點對（即邊）。為了生成邊的特征表示，我們使用簡單的二元算子組合各個節點的學習特征表示。這種組合性使 node2vec 可以用于涉及節點和邊的預測任務。

我們的實驗集中在網絡中兩個常見的預測任務：一個多標簽分類任務，其中每個節點都被分配一個或多個類標簽和一個鏈接預測任務，我們在給定一對節點的情況下預測一條邊的存在。我們將 node2vec 的性能與最先進的特征學習算法 [24, 28] 進行對比。我們對來自不同領域的幾個真實世界網絡進行實驗，例如社交網絡、信息網絡以及系統生物學的網絡。實驗表明，node2vec 在多標簽分類方面的性能優于最先進的方法高達 26.7%，在鏈接預測方面的性能高達 12.6%。該算法即使在 10% 的標記數據上也顯示出具有競爭力的性能，并且對噪聲或邊緣缺失形式的擾動也具有魯棒性。在計算上，node2vec 的主要階段可以簡單地并行化，它可以在幾個小時內擴展到具有數百萬個節點的大型網絡。

總的來說，我們的論文做出了以下貢獻：

我們提出了 node2vec，這是一種用于網絡中特征學習的高效可擴展算法，它使用 SGD 有效地優化了一種新穎的網絡感知、鄰域保留目標。

我們展示了 node2vec 如何符合網絡科學中的既定原則，為發現符合不同等價的表示提供了靈活性。

我們擴展了 node2vec 和其他基于鄰域保留目標的特征學習方法，從節點到節點對，用于基于邊緣的預測任務。

我們根據經驗評估 node2vec 在多個真實數據集上的多標簽分類和鏈接預測。

本文的其余部分的結構如下。在第 2 節中，我們簡要調查了網絡特征學習的相關工作。我們在第 3 節中介紹了使用 node2vec 進行特征學習的技術細節。在第 4 節中，我們經驗性地評估 node2vec 在各種現實世界網絡上的節點和邊緣上的預測任務，并評估我們算法的參數敏感性、擾動分析和可擴展性。我們以對 node2vec 框架的討論結束，并在第 5 節中強調未來工作的一些有希望的方向。node2vec 的數據集和參考實現可在項目頁面上找到：http://snap.stanford.edu/node2vec。

2. RELATED WORK

機器學習社區已經在各種標題下對特征工程進行了廣泛的研究。在網絡中，為節點生成特征的傳統范例基于特征提取技術，該技術通常涉及一些基于網絡屬性的種子手工制作特征 [8, 11]。相比之下，我們的目標是通過將特征提取作為表示學習問題來自動化整個過程，在這種情況下，我們不需要任何手工設計的特征。

無監督特征學習方法通常利用圖的各種矩陣表示的譜屬性，尤其是拉普拉斯矩陣和鄰接矩陣。在這種線性代數的觀點下，這些方法可以被視為降維技術。已經提出了幾種線性（例如，PCA）和非線性降維技術（例如，IsoMap）[3,27,30,35]。這些方法存在計算和統計性能缺陷。在計算效率方面，數據矩陣的特征分解是昂貴的，除非解決方案的質量受到近似值的嚴重影響，因此這些方法很難擴展到大型網絡。其次，這些方法對網絡中觀察到的不同模式（例如同質性和結構等價）的目標進行優化時不夠魯棒，并對底層網絡結構和預測任務之間的關系做出假設。例如，譜聚類做出了一個強烈的同質性假設，即圖切分（graph cuts）對分類很有用[29]。這樣的假設在許多情況下是合理的，但在跨不同網絡的有效泛化方面效果不佳。

自然語言處理的表征學習的最新進展為離散對象（例如單詞）的特征學習開辟了新途徑。特別是，Skip-gram 模型 [21] 旨在通過優化鄰域保留似然目標來學習單詞的連續特征表示。該算法如下進行：它掃描文檔的單詞，并針對每個單詞嵌入該單詞，以便單詞的特征可以預測附近的單詞（即，某個上下文窗口內的單詞）。通過使用帶有負采樣的 SGD [22] 優化似然目標來學習單詞特征表示。 Skip-gram 目標基于分布假設，該假設指出相似上下文中的單詞往往具有相似的含義 [9]。也就是說，相似的詞往往會出現在相似的詞鄰域中。

受 Skip-gram 模型的啟發，最近的研究通過將網絡表示為“文檔”[24、28]，建立了網絡的類比。就像文檔是有序的單詞序列一樣，可以從底層網絡中采樣節點序列，并將網絡轉換為有序的節點序列。然而，節點有許多可能的采樣策略，導致學習到的特征表示不同。事實上，正如我們將要展示的，沒有明確的抽樣策略適用于所有網絡和所有預測任務。這是先前工作的一個主要缺點，這些工作未能提供從網絡中采樣節點的任何靈活性 [24, 28]。我們的算法 node2vec 通過設計一個靈活的目標來克服這個限制，該目標不依賴于特定的采樣策略，并提供參數來調整探索的搜索空間（參見第 3 節）font>。

最后，對于基于節點和邊緣的預測任務，最近有大量基于現有和新穎的特定于圖的深度網絡架構的監督特征學習工作 [15、16、17、31、39]。這些架構使用幾層非線性變換直接最小化下游預測任務的損失函數，從而實現高精度，但由于高訓練時間要求而以可伸縮性為代價。

3. FEATURE LEARNING FRAMEWORK

我們將網絡中的特征學習表述為最大似然優化問題。讓 $G=(V,E)$ 是一個給定的網絡。我們的分析是通用的，適用于任何 (非) 定向、 (非) 加權網絡。設 $f:V\to {\mathbb{R}}^d$ 是從節點到特征表示的映射函數，旨在學習下游預測任務。這里 $d$ 是一個參數，指定特征表示的維數。等效地，$f$ 是大小為 $|V|\times d$ 的參數矩陣。對于每個源節點 $u\in V$，將 $N_S(u)?V$ 定義為節點 $u$ 通過鄰域采樣策略 $S$ 生成的網絡鄰域。

為了使優化問題易于處理，我們做了兩個標準假設:

• 條件獨立。給定源的特征表示，我們通過假設觀察鄰域節點的可能性獨立于觀察任何其他鄰域節點來分解可能性：
  

• 特征空間的對稱性。源節點和鄰域節點在特征空間中具有相互對稱的影響。因此，我們將每個源-鄰域節點對的條件似然建模為一個 softmax 單元，通過它們的特征的點積參數化：
  

有了上述假設，方程 1 中的目標簡化為：

對于大型網絡來說，每個節點的分區函數 $Z_u={\sum }_{v\in V}exp(f(u)?f(v))$ 計算成本很高，我們使用負采樣 [22] 對其進行近似。我們在定義特征 $f$ 的模型參數上使用隨機梯度上升優化方程 2。

基于Skip-gram架構的特征學習方法最初是在自然語言環境中開發的[21]。給定文本的線性性質，鄰域的概念可以自然地使用連續單詞上的滑動窗口來定義。然而，網絡不是線性的，因此需要更豐富的鄰域概念。為了解決這個問題，我們提出了一個隨機過程，該過程對給定源節點u的許多不同的鄰域進行采樣。鄰域NS(u)不僅限于直接鄰居，而是可以根據采樣策略s具有非常不同的結構

基于 Skip-gram 架構的特征學習方法最初是在自然語言的背景下開發的 [21]。鑒于文本的線性性質，鄰域的概念可以使用連續單詞上的滑動窗口自然地定義。然而，網絡不是線性的，因此需要更豐富的鄰域概念。為了解決這個問題，我們提出了一個隨機過程，它對給定源節點 $u$ 的許多不同鄰域進行采樣。鄰域 $N_S(u)$ 不僅限于直接鄰域，還可以根據采樣策略 $S$ 具有截然不同的結構。

3.1 Classic search strategies

我們將源節點的鄰域采樣問題視為局部搜索的一種形式。如圖 1 所示，其中給定一個源節點 u，我們旨在生成（采樣）其鄰域 $N_S(u)$。重要的是，為了能夠公平地比較不同的采樣策略 $S$，我們將鄰域集 $N_S$ 的大小限制為 $k$ 個節點，然后為單個節點 $u$ 采樣多個集合。通常，有兩種極端的采樣策略來生成 $k$ 個節點的鄰域集 $N_S$：

• 廣度優先采樣 (Breadth-first Sampling，BFS)：鄰域 $N_S$ 僅限于與源直接相鄰的節點。例如，在圖 1 中，對于大小為 k = 3 的鄰域，BFS 對節點 s1、s2、s3 進行采樣。
• 深度優先采樣 (Depth-first Sampling，DFS)：鄰域由在距源節點越來越遠的距離處按順序采樣的節點組成。在圖 1 中，DFS 采樣 s4、s5、s6。

廣度優先和深度優先采樣代表了他們探索的搜索空間的極端場景，從而對學習的表示產生了有趣的影響。

特別是，網絡中節點上的預測任務經常在兩種相似性之間穿梭：同質性和結構等價性[12]。

• 在同質性假設 [7, 36] 下，高度互連且屬于相似網絡簇或社區的節點應該緊密嵌入在一起（例如，圖 1 中的節點 $s_1$ 和 $u$ 屬于同一個網絡社區）。
• 相比之下，根據結構等效假設 [10]，在網絡中具有相似結構的節點應緊密嵌入在一起（例如，圖 1 中的節點 $s_6$ 和 $u$ 充當其相應社區的中心）。重要的是，與同質性不同，結構等價并不強調連通性。節點在網絡中可能相距很遠，但仍具有相同的結構。

在現實世界中，這些等價概念并不是唯一的。網絡通常表現出兩種行為，其中一些節點表現出同質性，而另一些則反映結構等價。

我們觀察到 BFS 和 DFS 策略在生成反映上述任何一個等價的表示方面起著關鍵作用。特別是，BFS 采樣的鄰域導致嵌入與結構等價密切對應。直觀地，我們注意到，為了確定結構等效性，準確地描述局部鄰域通常就足夠了。例如，僅通過觀察每個節點的直接鄰域，就可以推斷出基于網絡角色（如網橋和集線器）的結構等效性。通過將搜索限制在附近的節點，BFS 實現了這種表征并獲得了每個節點附近的微觀視圖。此外，在 BFS 中，采樣鄰域中的節點往往會重復多次。這也很重要，因為它減少了表征 1 跳節點（1-hop nodes）相對于源節點的分布的方差。然而，對于任何給定的 k，BFS 只能探索圖的一小部分。

DFS 則相反，它可以探索網絡的更大部分，因為它可以遠離源節點 $u$（樣本大小 $k$ 是固定的）。在 DFS 中，采樣節點更準確地反映了鄰域的宏觀視圖，這對于基于同質性推斷社區至關重要。然而，DFS 的問題在于，不僅要推斷網絡中存在哪些節點到節點的依賴關系，而且還要描述這些依賴關系的確切性質，這一點很重要。這很難，因為我們對樣本量有限制，而且要探索的鄰域很大，導致方差很大。其次，移動到更大的深度會導致復雜的依賴關系，因為采樣節點可能遠離源并且可能不太具有代表性。

3.2 node2vec

基于上述觀察，我們設計了一種靈活的鄰域采樣策略，使我們能夠在 BFS 和 DFS 之間進行平滑插值。我們通過開發一種靈活的有偏隨機游走程序來實現這一點，該程序可以以 BFS 和 DFS 方式探索鄰域。

3.2.1 Random Walks

形式上，給定一個源節點 u，我們模擬一個固定長度 l 的隨機游走。令 ci 表示遍歷中的第 i 個節點，從 c0 = u 開始。節點 ci 由以下分布生成：

其中 πvx 是節點 v 和 x 之間的非歸一化轉移概率，Z 是歸一化常數。

3.2.2 Search bias α

使我們的隨機游走產生偏差的最簡單方法是根據靜態邊權重 wvx 對下一個節點進行采樣，即 πvx = wvx（在未加權圖 wvx = 1 的情況下）。但是，這不允許考慮網絡結構并指導搜索過程來探索不同類型的網絡鄰域。此外，與分別適用于結構等價和同質性的極端采樣范式 BFS 和 DFS 不同，我們的隨機游走應該適應這樣一個事實，即這些等價概念不是競爭或排他性的，并且現實世界的網絡通常表現出兩者的混合。

我們用兩個參數 p 和 q 來定義一個二階隨機游走來引導游走：考慮一個隨機游走，它剛剛遍歷邊 (t, v)，現在位于節點 v（圖 2）。游走現在需要決定下一步，因此它評估從 v 開始的邊 (v, x) 上的轉移概率 πvx。我們將非歸一化轉移概率設置為 πvx = αpq(t, x) · wvx，其中

dtx 表示節點 t 和 x 之間的最短路徑距離。請注意，dtx 必須是 {0, 1, 2} 之一，因此，這兩個參數對于引導游走是必要且充分的。

直觀地說，參數 p 和 q 控制游走探索和離開起始節點 u 鄰域的速度。特別是，這些參數允許我們的搜索過程（近似）在 BFS 和 DFS 之間進行插值，從而反映對不同節點等價概念的親和力。

返回參數，p。參數 p 控制在行走中立即重新訪問節點的可能性。

• 將 p 設置為較高的值 (> max(q, 1)) 可確保我們在接下來的兩個步驟中不太可能對已經訪問過的節點進行采樣（除非遍歷中的下一個節點沒有其他鄰居）。該策略鼓勵適度探索并避免采樣中的 2 跳冗余。
• 另一方面，如果 p 很低（< min(q, 1)），它將導致游走回溯一步（圖 2），這將使游走“局部”靠近起始節點 u。

進出參數，q。參數 q 允許搜索區分“向內”和“向外”節點。回到圖 2，如果 q > 1，隨機游走偏向靠近節點 t 的節點。這樣的游走獲得了相對于游走中的起始節點獲得底層圖的局部視圖，并在由小區域內的節點組成的樣本方面，近似 BFS 行為。

相反，如果 q < 1，則游走更傾向于訪問距離節點 t 較遠的節點。這種行為反映了鼓勵向外探索的 DFS。然而，這里的一個本質區別是在隨機游走框架內實現了類似 DFS 的探索。因此，采樣節點與給定源節點 u 的距離并沒有嚴格增加，但反過來，受益于易于處理的預處理和隨機游走的卓越采樣效率。請注意，通過將 πv,x 設置為游走 t 中前一個節點的函數，隨機游走是二階馬爾可夫。

隨機游走的好處。與純 BFS/DFS 方法相比，隨機游走有幾個好處。

• 隨機游走在空間和時間要求方面都具有計算效率。存儲圖中每個節點的直接鄰居的空間復雜度為 $O(|E|)$。對于二階隨機游走，存儲每個節點的鄰居之間的互連是有幫助的，這會產生 $O(a^2|V|)$ 的空間復雜度，其中 a 是圖的平均度（degree），對于現實世界的網絡通常很小。
• 與經典的基于搜索的采樣策略相比，隨機游走的另一個關鍵優勢是它的時間復雜度。特別是，通過在樣本生成過程中施加圖連通性，隨機游走提供了一種方便的機制，通過跨不同源節點重用樣本來提高有效采樣率。
• 通過模擬長度為 l > k 的隨機游走，由于隨機游走的馬爾可夫性質，我們可以一次為 l - k 個節點生成 k 個樣本。因此，每個樣本的有效復雜度是 $O(\frac{l}{k(l?k)})$ 。例如，在圖 1 中，對長度為 l = 6 的隨機游走 {u, s4, s5, s6, s8, s9} 進行采樣，結果 NS(u) = {s4, s5, s6}，NS(s4) = {s5, s6, s8} 和 NS(s5) = {s6, s8, s9}。請注意，樣本重復使用可能會在整個過程中引入一些偏差。但是，我們觀察到它大大提高了效率。

3.2.3 The node2vec algorithm

node2vec 的偽代碼在算法 1 中給出。在任何隨機游走中，起始節點 u 的選擇存在隱式偏差。由于學習了所有節點的表示，通過模擬從每個節點開始的 r 個固定長度 l 的隨機游走來抵消這種偏差。在游走的每一步，采樣都是基于轉移概率 πvx 進行的。可以預先計算二階馬爾可夫鏈的轉移概率 πvx，因此，使用別名采樣可以在 O(1) 時間內有效地在模擬隨機游走時對節點進行采樣。 node2vec 的三個階段，即計算轉移概率的預處理、隨機游走模擬和使用 SGD 的優化，是按順序執行的。每個階段都是可并行化和異步執行的，有助于 node2vec 的整體可擴展性。

3.3 Learning edge features

node2vec 算法提供了一種半監督方法來學習網絡中節點的豐富特征表示。然而，我們經常對涉及節點對而不是單個節點的預測任務感興趣。例如，在鏈接預測中，我們預測網絡中兩個節點之間是否存在鏈接。由于我們的隨機游走自然基于底層網絡中節點之間的連接結構，因此我們使用自舉方法 (bootstrapping approach) 對單個節點的特征表示將它們擴展到節點對。

給定兩個節點 u 和 v，在相應的特征向量 f(u) 和 f(v) 上定義一個二元算子 ? 以生成表示 g(u, v) 使得 $g:V\times V\to {\mathbb{R}}^{d^{\prime }}$ 其中 d’ 是對 (u, v) 的表示大小。我們希望為任何一對節點定義算子，即使這對節點之間不存在邊，因為這樣做使得表示對于鏈接預測有用，其中測試集包含真邊和假邊（即，不存在）。我們考慮了幾種運算符 ? 的選擇，如表 1 中總結的 d’ = d。

4. EXPERIMENTS

Eq2 中的目標獨立于任何下游任務，并且 node2vec 提供的探索靈活性將學習的特征表示提供給下面討論的各種網絡分析設置。

4.1 Case Study: Les Misérables network

在第 3.1 節中，我們觀察到 BFS 和 DFS 策略代表了基于同質性（即網絡社區）和結構等效性（即節點的結構角色）原則的嵌入節點頻譜的極端。我們現在的目標是通過經驗證明這一事實，并表明 node2vec 實際上可以發現符合這兩個原則的嵌入。

我們使用一個網絡，其中節點對應于小說 Les Misérables [13] 中的角色，邊連接共同出現的角色。該網絡有 77 個節點和 254 條邊。我們設置 d = 16 并運行 node2vec 來學習網絡中每個節點的特征表示。使用 k-means 對特征表示進行聚類。然后，在二維中可視化原始網絡，節點現在根據聚類分配顏色。

圖 3（頂部）顯示了設置 p = 1、q = 0.5 時的示例。注意網絡區域（即網絡社區）是如何使用相同顏色著色的。在此設置中，node2vec 發現了在小說的主要子情節中經常相互交互的角色聚類/社區。由于字符之間的邊緣基于共現，我們可以得出結論，這種表征與同質性密切相關。

為了發現哪些節點具有相同的結構角色，我們使用相同的網絡但設置 p = 1, q = 2，使用 node2vec 獲取節點特征，然后根據獲得的特征對節點進行聚類。這里 node2vec 獲得了節點到聚類的互補分配，使得顏色對應于結構等價，如圖 3（底部）所示。例如，node2vec 將藍色節點嵌入在一起。這些節點代表充當小說不同子情節之間橋梁的角色。類似地，黃色節點主要代表處于外圍且互動有限的角色。可以為這些節點聚類分配替代語義解釋，但關鍵是 node2vec 不依賴于特定的等效概念。正如我們通過實驗所表明的那樣，這些等價概念通常在大多數現實世界的網絡中表現出來，并且對預測任務的學習表示的性能產生重大影響。

4.2 Experimental setup

我們的實驗評估了通過 node2vec 在標準監督學習任務上獲得的特征表示：節點的多標簽分類和邊緣的鏈接預測。對于這兩個任務，我們針對以下特征學習算法評估 node2vec 的性能：

• Spectral clustering [29]：這是一種矩陣分解方法，我們將圖 G 的歸一化拉普拉斯矩陣的頂部 d 特征向量作為節點的特征向量表示。
• DeepWalk [24]：這種方法通過模擬均勻隨機游走來學習 d 維特征表示。 DeepWalk 中的采樣策略可以看作是 node2vec 的一個特例，其中 p = 1 和 q = 1。
• LINE [28]：這種方法在兩個獨立的階段學習 d 維特征表示。在第一階段，它通過 BFS 風格的模擬在節點的直接鄰居上學習 d/2 維。在第二階段，它通過在距源節點 2 跳距離處嚴格采樣節點來學習下一個 d/2 維。

我們排除了其他矩陣分解方法，這些方法已經被證明不如DeepWalk [24]。我們還排除了最近的方法，GraRep [6]，該方法將LINE一般化，以合并來自超過 2 跳的網絡鄰域的信息，但是不能有效地擴展到大型網絡。

與先前工作中用于評估基于采樣的特征學習算法的設置相比，我們為每種方法生成相同數量的樣本，然后評估在預測任務中獲得的特征的質量。在這樣做時，我們完全因為實現語言（C/C++/Python）而忽略了觀察到的性能提升，因為它是算法的次要因素。因此，在采樣階段，DeepWalk、LINE 和 node2vec 的參數設置為在運行時生成相同數量的樣本。例如，如果 K 是總體采樣預算，則 node2vec 參數滿足 K = r·l·|V|。在優化階段，所有這些基準測試都使用 SGD 進行優化，我們糾正了兩個關鍵差異。首先，DeepWalk 使用分層采樣來逼近 softmax 概率，其目標類似于 node2vec 使用的目標。然而，與負采樣相比，分層 softmax 效率低下 [22]。因此，在保持其他一切不變的情況下，我們切換到 DeepWalk 中的負采樣，這也是 node2vec 和 LINE 中事實上的近似。

其次，node2vec 和 DeepWalk 都有一個用于優化上下文鄰域節點數量的參數，數量越大，需要的優化輪次就越多。對于 LINE，此參數設置為 unity，但由于 LINE 比其他方法更快地完成單個 epoch，我們讓它運行 k 個 epoch。

用于 node2vec 的參數設置與用于 DeepWalk 和 LINE 的典型值一致。具體來說，我們設置 d = 128, r = 10, l = 80, k = 10，并且針對單個 epoch 運行優化。我們對 10 次隨機種子初始化重復我們的實驗，我們的結果在 p 值小于 0.01 時具有統計學意義。最佳輸入輸出和返回超參數是使用 10% 標記數據的 10 倍交叉驗證來學習的在 p 上進行網格搜索，q ∈ {0.25, 0.50, 1, 2, 4}。

4.3 Multi-label classification

在多標簽分類設置中，每個節點都從有限集 L 中分配一個或多個標簽。在訓練階段，我們觀察一定比例的節點及其所有標簽。任務是預測剩余節點的標簽。這是一項具有挑戰性的任務，尤其是在 L 很大的情況下。我們使用以下數據集：

• BlogCatalog [38]：這是 BlogCatalog 網站上列出的博客作者的社會關系網絡。標簽代表通過博主提供的元數據推斷出的博主興趣。該網絡有 10,312 個節點、333,983 條邊和 39 個不同的標簽。
• Protein-Protein Interactions (PPI) [5]：我們使用智人的 PPI 網絡子圖。子圖對應于由節點誘導的圖，我們可以從標記基因集 [19] 中獲得標簽并表示生物狀態。該網絡有 3,890 個節點、76,584 條邊和 50 個不同的標簽。
• Wikipedia [20]：這是出現在Wikipedia 轉儲的前一百萬字節中的單詞的共現網絡。標簽表示使用斯坦福詞性標注器 [32] 推斷的詞性 (POS) 標簽。該網絡有 4,777 個節點、184,812 條邊和 40 個不同的標簽。

所有這些網絡都表現出同質和結構等價的公平混合。例如，我們期望博主的社交網絡表現出強烈的基于同質性的關系；然而，也可能有一些“熟悉的陌生人”，即不互動但分享興趣的博主，因此在結構上是等效的節點。蛋白質-蛋白質相互作用網絡中蛋白質的生物學狀態也表現出兩種類型的等價性。例如，當蛋白質執行與相鄰蛋白質互補的功能時，它們表現出結構等效性，而在其他時候，它們基于同質性組織以幫助相鄰蛋白質執行相似功能。詞共現網絡相當密集，因為在 Wikipedia 語料庫的 2length 窗口中共現的詞之間存在邊。因此，具有相同 POS 標簽的單詞不難找到，具有高度的同質性。同時，由于句法語法模式，我們期望詞性標記中的一些結構等價，例如名詞后面的限定詞、標點符號后面的名詞等。

實驗結果。節點特征表示被輸入到具有 L2 正則化的 one-vs-rest 邏輯回歸分類器。訓練數據和測試數據平均分成 10 個隨機實例。我們使用 Macro-F1 分數來比較表 2 中的性能，并且相對性能增益超過了最接近的基準。 Micro-F1 和準確性的趨勢相似，未顯示。

從結果中，很明顯我們可以看到在探索鄰域中增加的靈活性如何使 node2vec 優于其他基準算法。在 BlogCatalog 中，我們可以通過將參數 p 和 q 設置為較低的值來發現同質性和結構等價的正確組合，在 Macro-F1 分數中比 DeepWalk 提高 22.3%，比 LINE 提高 229.2%。 LINE 的性能比預期的要差，這可以用它無法重復使用樣本來解釋，而使用隨機游走方法可以輕松完成這一壯舉。即使在我們的其他兩個網絡中，存在混合等價的情況，node2vec 的半監督性質也可以幫助我們推斷特征學習所需的適當探索程度。在 PPI 網絡的情況下，最佳探索策略 (p = 4, q = 1) 與 DeepWalk 的統一 (p = 1, q = 1) 探索幾乎無法區分，通過避免冗余，我們僅比 DeepWalk 略有優勢在已經訪問過的節點中通過高 p 值，但在 Macro-F1 分數中比 LINE 有令人信服的 23.8% 增益。然而，一般來說，均勻隨機游走可能比 node2vec 學習的探索策略差得多。正如我們在維基百科詞共現網絡中看到的那樣，統一游走不能引導搜索過程朝向最佳樣本，因此，我們比 DeepWalk 獲得了 21.8% 的增益，比 LINE 獲得了 33.2% 的增益。

對于更細粒度的分析，我們還比較了性能，同時將訓練測試拆分從 10% 更改為 90%，同時像以前一樣在 10% 的數據上學習參數 p 和 q。為簡潔起見，我們在圖 4 中以圖形方式總結了 Micro-F1 和 Macro-F1 分數的結果。在這里我們進行了類似的觀察。所有方法都顯著優于 Spectral 聚類，DeepWalk 優于 LINE，node2vec 始終優于 LINE，并且在跨領域的 DeepWalk 上取得了很大的改進。例如，在 70% 的標記數據下，我們在 BlogCatalog 上實現了比 DeepWalk 26.7% 的最大改進。在最壞的情況下，搜索階段對學習表示幾乎沒有影響，在這種情況下 node2vec 相當于 DeepWalk。同樣，與 LINE 相比，改進更為顯著，除了在 BlogCatalog 上的顯著增益（超過 200%）外，我們觀察到在僅 10% 的標記數據上訓練時，在 PPI 等其他數據集上的大幅改進高達 41.1%。

4.4 Parameter sensitivity

node2vec 算法涉及許多參數，在圖 5a 中，我們使用標記數據和未標記數據之間的 50-50 分割來檢查參數的不同選擇如何影響 Node2vec 在 BlogCatalog 數據集上的性能。除被測參數外，所有其他參數均采用默認值。 p 和 q 的默認值設置為統一。

我們將 Macro-F1 分數測量為參數 p 和 q 的函數。 node2vec 的性能隨著輸入輸出參數 p 和返回參數 q 的減小而提高。這種性能的提高可以基于我們期望在 BlogCatalog 中看到的同質和結構等價。雖然低 q 鼓勵向外探索，但它由低 p 來平衡，確保游走不會離起始節點太遠。

我們還檢查了特征數量 d 和節點的鄰域參數（游走次數 r、游走長度 l 和鄰域大小 k）如何影響性能。我們觀察到，一旦表示的維度達到 100 左右，性能就會趨于飽和。類似地，我們觀察到增加每個源的游走次數和長度可以提高性能，這并不奇怪，因為我們有更大的總體采樣預算 K 來學習表示。這兩個參數對方法的性能都有相對較高的影響。有趣的是，上下文大小 k 也以增加優化時間為代價提高了性能。但是，在這種情況下，性能差異并不大。

4.5 Perturbation Analysis

對于許多現實世界的網絡，我們無法獲得有關網絡結構的準確信息。我們進行了擾動研究，分析了與 BlogCatalog 網絡中的邊緣結構相關的兩個不完美信息場景的 node2vec 的性能。在第一種情況下，我們將性能測量為缺失邊的比例（相對于整個網絡）的函數。缺失的邊是隨機選擇的，受限于網絡中連接組件的數量保持固定的約束。正如我們在圖 5b（頂部）中看到的，隨著缺失邊緣比例的增加，Macro-F1 分數的下降大致呈線性，且斜率很小。在圖隨時間演變的情況（例如，引文網絡）或網絡建設成本高昂（例如，生物網絡）的情況下，網絡中缺失邊的魯棒性尤其重要。

在第二個擾動設置中，我們在網絡中隨機選擇的節點對之間有噪聲邊緣。如圖 5b（底部）所示，與缺失邊的設置相比，node2vec 的性能最初下降的速度稍快，但是隨著時間的推移，Macro-F1 分數的下降速度逐漸放緩。同樣，node2vec 對錯誤邊緣的魯棒性在多種情況下很有用，例如用于構建網絡的測量有噪聲的傳感器網絡。

4.6 Scalability

為了測試可擴展性，我們使用 node2vec 學習節點表示，其中 Erdos-Renyi 圖的默認參數值從 100 增加到 1,000,000 個節點，平均度數為 10。在圖 6 中，我們憑經驗觀察到 node2vec 隨著數量的增加呈線性擴展的節點在不到 4 小時內為 100 萬個節點生成表示。采樣過程包括計算游走（可以忽略不計）的轉移概率的預處理和隨機游走的模擬。優化階段使用負采樣 [22] 和異步 SGD [26] 變得高效。

先前工作中的許多想法可作為使采樣過程在計算上高效的有用指針。我們展示了在 DeepWalk [24] 中也使用的隨機游走如何允許將采樣節點重新用作出現在游走中的不同源節點的鄰域。Alias sampling 允許我們的游走推廣到加權網絡，幾乎沒有預處理[28]。盡管我們可以根據基礎任務和領域自由設置搜索參數，但學習搜索參數的最佳設置會增加開銷。然而，正如我們的實驗所證實的那樣，這種開銷是最小的，因為 node2vec 是半監督的，因此可以用很少的標記數據有效地學習這些參數。

4.7 Link prediction

在鏈接預測中，給定一個網絡，其中刪除了一定比例的邊緣，我們希望預測這些缺失的邊緣。我們生成帶標簽的邊數據集如下：為了獲得正樣本，我們從網絡中隨機抽取 50% 的邊，同時確保邊緣移除后得到的殘差網絡是連通的；為了生成負樣本，我們隨機抽取一個來自網絡的相同數量的節點對，它們沒有連接它們的邊。

由于以前沒有使用任何特征學習算法進行鏈接預測，我們還根據一些流行的啟發式分數評估 node2vec，這些分數在鏈接預測中取得了良好的性能。我們考慮的分數是根據構成該對的節點的鄰域集定義的（參見表 3）。我們在以下數據集上測試基準：

• Facebook [14]：在 Facebook 網絡中，節點代表用戶，邊代表任意兩個用戶之間的友誼關系。該網絡有 4,039 個節點和 88,234 條邊。
• Protein-Protein Interactions (PPI) [5]：在智人的PPI 網絡中，節點代表蛋白質，邊表示一對蛋白質之間的生物相互作用。該網絡有 19,706 個節點和 390,633 條邊。
• arXiv ASTRO-PH [14]：這是一個協作網絡，由提交給電子版 arXiv 的論文生成，其中節點代表科學家，如果兩位科學家在一篇論文中進行了合作，則他們之間存在優勢。該網絡有 18,722 個節點和 198,110 條邊。
  
  實驗結果。我們在表 4 中總結了鏈路預測的結果。為便于演示，省略了每個 node2vec 條目的最佳 p 和 q 參數設置。我們可以從結果中得出的一般觀察結果是，節點對的學習特征表示明顯優于啟發式基準分數，node2vec 在 arXiv 數據集上實現了最佳 AUC 改進，超過了最佳性能基線（Adamic-Adar [1] ）。

在特征學習算法中，node2vec 在所有網絡中的表現都優于 DeepWalk 和 LINE，在 AUC 分數上分別獲得高達 3.8% 和 6.5% 的增益，從而為每種算法提供最佳的二元算子選擇。當我們單獨查看算子時（表 1），node2vec 優于 DeepWalk 和 LINE，除非有一些涉及加權 L1 和加權 L2 算子的情況，其中 LINE 表現更好。總體而言，與 node2vec 一起使用的 Hadamard 算子非常穩定，并且在所有網絡中平均提供了最佳性能。

5. DISCUSSION AND CONCLUSION

本文將網絡中的特征學習作為一個基于搜索的優化問題來研究。這種觀點給了我們多重優勢。它可以解釋基于探索-開發權衡的經典搜索策略。此外，它在應用于預測任務時為學習的表示提供了一定程度的可解釋性。例如，我們觀察到 BFS 只能探索有限的鄰居（neighborhoods）。這使得 BFS 適用于表征網絡中依賴于節點的直接局部結構的等價結構。另一方面，DFS 可以自由探索網絡鄰域，這對于發現同質社區（homophilous communities）很重要，但代價是高方差。

DeepWalk 和 LINE 都可以看作是網絡上的嚴格搜索（rigid search）策略。

• DeepWalk [24] 提出使用均勻隨機游走進行搜索。這種策略的明顯限制是無法控制已探索的鄰居。
• LINE [28] 主要提出了一種廣度優先策略，對節點進行采樣并僅在 1 跳和 2 跳鄰居上獨立優化似然性。這種探索的效果更容易表征，但它具有限制性，并且在探索更深的節點時沒有提供靈活性。

相比之下，node2vec 中的搜索策略既靈活又可控，通過參數 p 和 q 探索網絡鄰域。雖然這些搜索參數具有直觀的解釋，但當我們可以直接從數據中學習它們時，我們會在復雜網絡上獲得最佳結果。從實際的角度來看，node2vec 具有可擴展性并且對擾動具有魯棒性。

我們展示了節點嵌入對鏈接預測的擴展如何勝過專門為此任務設計的流行啟發式得分。我們的方法允許除了表 1 中列出的那些之外的其他二元算子。作為未來的工作，我們想探索 Hadamard 算子比其他算子成功的原因，并根據搜索參數為邊建立可解釋的等價概念。 node2vec 的未來擴展可能涉及具有特殊結構的網絡，例如異構信息網絡、具有顯式域特征的節點和邊緣網絡以及有符號邊緣網絡。連續特征表示是許多深度學習算法的支柱，使用 node2vec 表示作為圖上端到端深度學習的構建塊會很有趣。

總結

以上是生活随笔為你收集整理的【GNN】图嵌入之 node2vec：网络的可扩展特征学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。