超碰免费不卡666,良家久久露脸,97欧美国产

??LINE(Larg-scale Information Network Embedding)由Jian Tang等于2015年提出的，該方法提出了一種可以應用在任意邊類型的大型網(wǎng)絡上的節(jié)點嵌入算法，并通過考慮first-order proximity（local structure）和second-order proximity（global structure）實現(xiàn)網(wǎng)絡嵌入。總體來說，相比較之前的Graph/Network Embedding方法，LINE具有如下好處：

適用于任意類型的網(wǎng)絡，這里的任意類型在該文中主要是指邊的權重和方向是任意：有向，無向，有權重，無權重。（LINE并沒有考慮不同節(jié)點類型和邊類型下的異構網(wǎng)絡，有一定的局限性。也就有了后來針對heterogeneous和homogeneous網(wǎng)絡的研究）
LINE提出了一種邊采樣（edge-sampling）算法來提升和優(yōu)化目標函數(shù)，從而克服了傳統(tǒng)的隨機梯度下降（stochastic gradient decent）的局限性。

模型描述（Model Description）

??在具體介紹LINE算法的詳細過程前，還需要了解兩個概念：

First-order Proximity在LINE中用于表征local structure，具體反映在網(wǎng)絡中就是任意兩個頂點之間的距離，即如果兩個頂點在圖中有一條邊，那么這個邊上的權重就是這兩個頂點之間的First-order Proximity，如果是無權重圖，則該First-order Proximity就是1，如果兩個頂點之間沒有邊之間相連，則為0。在現(xiàn)實中的表現(xiàn)就是，如果兩個頂點相鄰，且權重很大，那么這兩個頂點在某種程度上是非常相似的。
Second-order Proximity在LINE中用于表征global structure，其基于一個假設：如果兩個頂點共享大部分鄰居頂點，那么這兩個頂點之間也十分相似。如果兩個頂點之間沒有共享的鄰居頂點，那么這兩個頂點的Second-order Proximity為0。

下圖直觀的展示了First-order Proximity和Second-order Proximity的區(qū)別。

Figure 1: A toy example of information network. Edges can be undirected, directed, and/or weighted. Vertex 6 and 7 should be placed closely in the low-dimensional space as they are connected through a strong tie. Vertex 5 and 6 should also be placed closely as they share similar neighbors.

接下來正式介紹LINE的具體過程：

LINE with First-order Proximity

??為了表征任意兩個頂點之間的First-order Proximity，作者定義了兩個頂點之間的聯(lián)合分布，公式如下：
$\large p_1(v_i,v_j)=\frac{1}{1 + \exp(-\vec{u}_i^T \cdot \vec{u}_j)} \tag{1}$ 其中 $\small \vec{u} \in R^d$ 是頂點 $v_i$ 的低維向量表示，公式（1）定義了一個 $V \times V$ 空間下的概率分布 $\small p(\cdot,\cdot)$ ，它的經(jīng)驗分布可以表示為 $\small \hat{p_1}(i,j)=\frac{w_{ij}}{W}$ ，其中 $\small W=\sum(i,j)\in E^{w_{ij}}$ 。為了保留First-order Proximity，一個最直接的方法就是最小化如下的目標函數(shù)：
$\large O_1=d(\hat{p_1}(\cdot,\cdot),p_1(\cdot,\cdot)) \tag{2}$ 其中 $\small d(\cdot, \cdot)$ 表示兩個分布之間的距離，作者采用KL-divergence來度量，因此公式（2）可以轉化為：
$\large O_1=-\sum_{(i,j)\in E}w_{i,j}\log p_1(v_i,v_j) \tag{3}$ 針對First-order Proximity有一點需要特別注意一下：上述First-order Proximity只適用于不考慮邊方向的網(wǎng)絡或圖，針對有向圖并不適用。通過最小化公式(3)，我們可以找到每個頂點最優(yōu)的 $\small d$ 維向量表示。

LINE with Second-order Proximity

??Second-order Proximity既適用于無向圖，也適用于有向圖。對于一個網(wǎng)絡或圖，不失一般性，我們均假設其為有向圖（無向邊可以理解成兩條方向相反，權重相同的有向邊）。Second-order Proximity假定具有大量相同鄰接頂點的兩個頂點是相似的，在這種情況下，每個可以看作是一個特定的上下文（context），具有相同或相似上下文分布的頂點被認為是相似的。因此，在這種場景下，每個頂點扮演著兩種不同的角色：頂點本身和其他頂點的上下文?；诖?，作者提出了兩種向量表示 $\small \vec{u}_i$ 和 $\small \vec{u}_i^\prime$ ，其中 $\small \vec{u}_i$ 為頂點 $\small v_i$ 作為頂點時的向量表示，而 $\small \vec{u}_i^\prime$ 為頂點 $\small v_i$ 作為context時的向量表示。對于每個有向邊 $\small e_{ij}$ ，作者定義了頂點 $\small v_j$ 作為頂點 $\small v_i$ 的context的條件概率為：
$\large p_2(v_j|v_i)=\frac{\exp(\vec{u}_j^{\prime T} \cdot \vec{u}_i)}{\sum_{k=1}^{|V|} \exp(\vec{u}_k^{\prime T} \cdot \vec{u}_i)} \tag{4}$ 其中 $\small |V|$ 表示頂點 $\small v_i$ 的context的集合大小。公式（4）表示了每個頂點 $\small v_i$ 在其上下文context上的條件概率 $\small p_2(\cdot|v_i)$ ，也就在整個頂點集合上的條件概率，如上所述，如果兩個頂點在其上下文上具有相近的分布，那么認為這兩個頂點在表示上是相似的。為了保留Second-order Proximity，希望每個頂點在其上下文上的條件分布能最大程度的擬合其經(jīng)驗分布，于是作者針對Second-order Proximity提出了新的目標函數(shù)，即最小化下述目標函數(shù)：
$\large O_2=\sum_{i\in V} \lambda_id(\hat{p}_2(\cdot | v_i), p_2(\cdot | v_i)) \tag{5}$ 其中 $\small d(\cdot, \cdot)$ 表示兩個分布之間的距離，作者同樣采用了KL-divergence來度量，另外作者通過引入 $\small \lambda_i$ 來表示不同的頂點在網(wǎng)絡或圖中的重要性，該值可以通過PageRank等考察頂點重要性的方法來獲得。經(jīng)驗分布 $\small \hat{p}_2(\cdot | v_i)$ 可以表示為 $\small \hat{p}_2(v_j | v_i)=\frac{w_{ij}}{d_i}$ ，其中 $\small w_{ij}$ 表示邊 $\small e_{ij}$ 的權重， $\small d_i$ 表示頂點 $\small v_i$ 的出度，假設 $\small \lambda_i = d_i$ ，那么目標函數(shù)（5）可以優(yōu)化如下：
$\large O_2=-\sum_{e_{ij}} \log p_2(v_j | v_i) \tag{6}$ 通過最小化目標函數(shù)學習 $\small \{ \vec{u}_i\}_{i=1..|V|}$ 和 $\small \{ \vec{u}_i^\prime\}_{i=1..|V|}$ ，我們可以得到每個頂點的 $\small d$ 維向量表示 $\small \vec{u}_i^\prime$

Combine First-order Proximity and Second-order Proximity

??為了同事保留頂點的First-order Proximity和Second-order Proximity，作者提出了一種最簡單的也被實驗證明是有效的方法，即對于同一個頂點分別針對兩個目標函數(shù)訓練兩個不同的模型，然后將各自Embedding的結果進行簡單的聯(lián)接（concatenate）即可。當然，作者也提出了在以后的工作中，可以嘗試利用目標函數(shù)（3）和目標函數(shù)（6）進行聯(lián)合訓練以達到embedding的目的。

模型優(yōu)化（Model Optimization）

??學習目標函數(shù)（6）的過程的計算量是特別大的，因為它需要在整個數(shù)據(jù)集上計算其條件分布，特別是當圖中的頂點和邊的個數(shù)特別巨大的時候。為此作者提出了可以采用T. Mikolov提出的負采樣方法（Negative Sampling），即根據(jù)每條邊 $\small e_{ij}$ 的噪聲分布進行多條負邊采樣，以達到降低計算量的目的。于是針對每條邊，它明確了優(yōu)化以下目標函數(shù)：
$\large \log \sigma(\vec{u}_j^{\prime T} \cdot \vec{u}_i) + \sum_{i=1}^{K}E_{v_n \widetilde{} P_n(v)[\log \sigma(\vec{u}_j^{\prime T} \cdot \vec{u}_i)]} \tag{7}$ 其中
$\sigma (x) = \frac{1}{1+\exp(-x)}$
是一個 $\small sigmoid$ 函數(shù)，公式（7）前半部分用來建模觀察到的所有的邊，而后辦部分用來建模從噪聲分布中負采樣的邊，其中 $\small K$ 表示負采樣的邊的數(shù)目。至于負采樣的具體細節(jié)，具體可以參考Negative Sampling。
??作者通過異步的隨機梯度下降算法ASGD（asynchronous stochastic gradient algorithm）來優(yōu)化公式（7）的學習過程。在每次迭代中，ASGD會隨機選擇一批邊來更新模型的參數(shù)。如果一個邊 $e_{ij}$ 被選中，那么關于頂點 $\small v_i$ 的嵌入向量 $\small \vec{u}_i$ 的梯度可以通過如下公式計算：
$\large \frac{\partial O_2}{\partial \vec{u}_i}=w_{ij} \cdot \frac{\partial \log p_2(v_j | v_i)}{\partial \vec{u}_i} \tag{8}$ 需要注意的是，這里的梯度需要乘以一個邊的權重，如果邊的權重有很大的方差的化就會有問題。例如，在一個單詞網(wǎng)絡中，有些單詞之間共現(xiàn)多次(例如，幾萬次)，而有些單詞之間僅共現(xiàn)幾次。在這種情況下，梯度的比例是發(fā)散的，因此很難去尋找一個合適的學習速度。如果根據(jù)權值較小的邊選擇較大的學習率，則權值較大的邊的梯度會發(fā)生爆炸；而根據(jù)權值較大的邊選擇較小的學習率，會導致梯度過小，長時間難以收斂。

Optimization via Edge Sampling

??解決上述問題最直觀的做法就是，如果所有邊的權重都一樣，那么選擇一個合適的學習速率就沒有任何問題。因此，一個最簡單的處理方法就是將一個加權的邊展開成多個二元邊。即一個權重為 $\small w$ 的邊可以拆分成 $\small w$ 個二元邊。這樣雖然能解決上述問題，但是又產生了一個新的問題，如此拆分會導致邊的規(guī)模在原來基礎上擴大很多倍，直接導致了內存的需求激增。為了解決這個問題，可以對原始邊進行采樣，采樣概率與原始邊的權值成正比，并將采樣后的邊視為二元邊。通過這樣的Edge Sampling采樣處理，使得總體目標函數(shù)保持不變。這樣問題就變成了如何根據(jù)邊的權值對邊進行采樣。這里用 $\small W=(w_1,w_2, \dots, w_{|E|})$ 表示所有的邊的權重序列，首先可以計算所有邊的權重之和 $\small w_{sum}=\sum_{i=1}^{|E|}w_i$ ，然后在區(qū)間 $\small [0, w_{sum}]$ 范圍內隨機選擇一個數(shù)，看這個數(shù)隨機落在哪個區(qū)間 $\small [\sum_{j=0}^{i-1}w_j, \sum_{j=0}^{i}w_j)$ 中。該方法需要 $\small O(|E|)$ 的時間復雜度去抽取一個樣本，當邊的規(guī)模很大時，代價也是很大的。為此，作者使用一種別名表（alias table）的方式根據(jù)權重進行采樣，當重復從相同的離散分布中采樣時，只需要 $\small O(1)$ 的時間。使用別名表進行采樣的時間復雜度是 $\small O(1)$ ，而負采樣的時間復雜度是 $\small O(d(K + 1))$ ，其中K是負采樣的大小。