01 youtube官網 中文新聞數據集分類實驗(深層網絡結構嵌入)

深層網絡結構嵌入

由于平臺限制，公式無法顯示，更好閱讀體驗，請訪問( 買粉絲://tianle.me/2017/06/30/SDNE/ )

論文閱讀 Structural Deep Network Embedding

本文的PDF版 深層網絡結構嵌入

這學期選了非線性電路與系統，最近又在做網絡表示的相關研究，特將平時看過比較好的論文寫一寫，和大家分享一下。

信息網絡在現實世界中普遍存在，例如航空公司網絡，出版物網絡，通信網絡和萬維網。這些信息網絡的規模從幾百個節點到數百萬和數十億個節點不等。大規模信息網絡的分析在學術界和工業界引起越來越多的關注。本文研究的是將信息網絡嵌入到低維空間的問題，其中每個頂點都表示為一個低維向量。這種低維嵌入在各種應用中非常有用，如可視化，節點分類，鏈路預測和選擇推薦。

網絡嵌入目前依舊面臨許多挑戰。（1） 高維且非線性 ，深層的網絡結構特征通常是非線性且高維的。因此，如何去描述學習這種高維非線性的特征是非常具有挑戰性的。（2） 結構保持 ，為了能夠將結果應用到一些具體的網絡分析任務中，網絡嵌入方法需要能夠將網絡結構較好的保存下來，但是隱藏的網絡結構是非常復雜并且難以發現的。節點的特性往往依賴于其局部和全局的網絡結構。（3） 稀疏性 ，真實世界中的大部分網絡都是稀疏的，只能夠利用極少數已發現的關系連接，因此還遠遠不能依此得到滿意的效果。

近些年來，許多網絡嵌入的方法相繼被提出，它們采用了一些淺顯的模型，比如說：IsoMAP，Laplacian Eigenmap(LE)，Line。由于這些模型的局限性，它們很難獲得網絡高維的非線性特征。為了解決這個難題，本文提出了深層模型來學習網絡中的節點表示。我們受深度學習的啟發，因為其展現出了強大的表示學習能力，能夠從復雜的網絡中學習特征。它已經在圖像、文本、語音等方面取得了卓越的成績。特別的，我們提出的模型設計了多層的網絡結構，這些結構是由許多非線性函數構成，能夠將網絡數據映射到隱藏的非線性空間中，從而挖掘出網絡的非線性結構。

[圖片上傳失敗...(image-a552b0-1510922608055)]

圖1

算法主要步驟：

算法主要步驟：

在圖上隨機游走產生長度為$2w + 1$的路徑，對每個點隨機$\gamma $個隨機游走序列。每一條隨機游走路徑便是相當于一個序列（相當于一句話），這樣序列中的點就有上下文，定義一個時間窗口$w$，并進行馬爾可夫假設，最后使用word2vec中的Skip-Gram訓練每一個節點的向量。

Gram訓練每一個節點的向量。

假設一個路徑序列為{ % raw %}$S = \left{ { { v_1},...,{ v_{ |S|}}} \right} ${ % endraw %},對于${ v_i} \in S$，其上下文為{ % raw %}$C = \left{ { { v_{ i - w}},{ v_{ i - w + 1}},...,{ v_{ i + w - 1}},{ v_{ i + w}}} \right}${ % endraw %}, 那么DeepWalk的優化目標為:

{ % raw %}$$f = \frac{ 1}{ { \left| S \right|}}\sum\limits_{ i = 1}^{ \left| S \right|} { \sum\limits_{ - w \le j \le w,j \ne 0} { \log p({ v_{ i + j}}|{ v_i})} } $${ % endraw %}

其中：

{ % raw %}$$p\left( { { v_j}|{ v_i}} \right) = \frac{ { exp\left( { c_{ { v_j}}^T{ r_{ { v_i}}}} \right)}}{ { \sum\nolimits_{ v \in C} { exp\left( { c_{ { v_j}}^T{ r_{ { v_i}}}} \right)} }}$${ % endraw %}

{ % raw %}${ r_{ { v_i}}}${ % endraw %}是點${ v_i}$的向量表征, { % raw %}${ c_{ { v_i}}}${ % endraw %}是點{ % raw %}${ v_i}${ % endraw %}上下文中點${ v_j}$的向量表征。

DeepWalk使目標$f$最大化，使用Skip-Gram與Hierarchical Softmax進行訓練得到每個點的vector，DeepWalk等價于MF(matrix factorization,矩陣分解)。

定義1（網絡） ：給定一個網絡{ % raw %}$G = \left( { V,E} \right)${ % endraw %}，其中{ % raw %}$V = { { v_1}, \cdots ,{ v_n}} ${ % endraw %}表示為n個節點，{ % raw %}$E = { { e_{ i,j}}} { i,j = 1}^n${ % endraw %}表示網絡中所有邊的集合。每一條邊{ % raw %}${ e { i,j}}${ % endraw %}與其網絡中邊的權重{ % raw %}${ s_{ i,j}} \ge 0${ % endraw %}相關聯。如果{ % raw %}${ v_i}${ % endraw %}和{ % raw %}${ v_j}${ % endraw %}之間沒有連接，那么{ % raw %}${ s_{ i,j}} = 0${ % endraw %}，否則，對于無權圖{ % raw %}${ s_{ i,j}} = 1${ % endraw %}，有權圖{ % raw %}${ s_{ i,j}} > 0${ % endraw %}

網絡嵌入的目的是將原始的高維網絡數據映射到低維的表示空間中，網絡中的每一個節點即可表示為一個低維向量，同時網絡計算將會變得非常方便。正如我們之前提到的，網絡的局部結構和全局結構都非常有必要在降維后保存下來，下面將詳細定義一階相似度和二階相似度。

定義2（一階相似度） ：網絡中的一階相似度是兩個頂點之間的局部點對的鄰近度。對于由邊（u，v）鏈接的每對頂點，該邊的權重${ s_{ u,v}}$表示u和v之間的一階相似性，如果在u和v之間沒有邊，它們的一階相似度為0。

一階相似度通常意味著現實世界網絡中兩個節點的相似性。例如，在社交網絡中成為朋友的人往往具有類似的興趣；在萬維網上互相鏈接的頁面往往談論類似的主題。由于一階相似度的重要性，許多現有的圖嵌入算法，如IsoMap，LLE，Laplacian Eigenmaps目的都是保持一階相似度。

然而，在現實世界的信息網絡中，能夠觀察到的鏈接只是小部分，許多隱藏的其他關系都沒有被觀察到。缺失鏈路上的一對節點，即使它們在本質上非常相似，然而他們的一階相似度為0。 因此，只有一階相似度對維持網絡結構來說不是很有效。我們自然而然的想到，具有類似鄰居的頂點往往是相似的。 例如，在社交網絡中，分享相同內容的人往往具有相似的興趣，從而成為朋友，在文本網絡中，總是與同一組詞匯共同出現的詞往往具有相似的含義。 因此，我們定義二階相似度，其補充了一階相似性并能夠保留網絡結構。

定義3（二階相似度） ：二階相似度對應于網絡中的點對（u，v）是其鄰域網絡結構之間的相似性。數學上，讓{ % raw %}${ { \rm{ \mathcal{ N}}} u} = { { s { u,1}}, \cdots ,{ s_{ u,\left| V \right|}}} ${ % endraw %}表示一階附近 u 與所有其他的頂點，那么 u 和v之間的二階相似性由{ % raw %}${ { \rm{ \mathcal{ N}}}_u}$和${ { \rm{ \mathcal{ N}}}_v}${ % endraw %}之間的相似性來決定。如果沒有一個頂點同時和 u 與 v 鏈接，那么 u 和 v的二階相似性是0。

定義4（網絡嵌入） ：給定網絡{ % raw %}$G = \left( { V,E} \right)${ % endraw %}，網絡嵌入的問題是將每個頂點$v \in V$表示為低維空間{ % raw %}${ \mathbb{ R}^d}${ % endraw %}中的向量，學習函數$f:\left| V \right| \mapsto { \mathbb{ R}^d}$，其中$d \ll \left| V \right|$。在空間{ % raw %}${ \mathbb{ R}^d}${ % endraw %}中，頂點之間的一階相似度和二階相似度都被保留。

在本篇文章中，我們提出了一個半監督的網絡嵌入深度框架，整體框架如圖2所示。具體來說，為了捕捉高維非線性的網絡結構，我們提出了一個深層的體系結構，它由多個非線性映射函數組成，將輸入數據映射到一個高維非線性的隱藏空間，以捕獲網絡結構。為了解決網絡結構保持和稀疏性問題，我們提出了一個半監督模型來利用一階和二階相似度。對于每個頂點，我們都可以得到它的鄰域。因此，我們設計了無監督的組件來保持二階相似度，并重建每個頂點的鄰域結構。同時，對節點的一部分，我們可以獲得他們的一階相似度。因此，我們設計了有監督的組件，利用一階相似度作為監督信息來改進隱藏空間中的表示。通過聯合優化所提出的半監督深度模型，SDNE可以保持高維的非線性網絡結構，保證稀疏網絡的健壯性。在接下來的部分中，我們將詳細介紹如何實現半監督的深度模型。

[圖片上傳失敗...(image-4ccde2-1510922608055)]

圖2.網絡整體結構

我們首先描述無監督組件如何利用二階近似保持全局網絡結構。

二階相似性值指的是節點的鄰居相似，因此模型的二階相似性，需要每個節點鄰居的性質。給定一個網絡{ % raw %}$G = \left( { V,E} \right)${ % endraw %}，我們可以獲得到它的鄰接矩陣S，它包含了n個元素${ s_1}, \cdots { s_n}$，對于每一個元素{ % raw %}${ s_i} = { { s_{ i,j}}} { j = 1}^n${ % endraw %}，如果${ v_i}$與${ v_j}$間有相連的邊，那么{ % raw %}${ s { i,j}} > 0${ % endraw %}。因此，${ s_i}$描述了節點${ v_i}$的鄰居結構，$S$提供了每一個節點的鄰居結構信息。對于$S$來說，我們將傳統的深度自編碼器的進行延伸，用來保存網絡的二階相似性。

下面簡單回顧一下深度自編碼器的主要思想。它屬于一種非監督模型，包含編碼器與解碼器。編碼器由許多非線性函數構成，將輸入數據映射到表示空間。對應的，解碼器也由許多非線性函數構成，它將表示空間映射到輸入數據的重構空間。給定輸入數據${ x_i}$，其中對于各個層的隱藏表示如下公式進行計算：

{ % raw %}$$y_i^{ (1)} = \sigma ({ W^{ (1)}}{ x_i} + { b^{ (1)}})$${ % endraw %}

{ % raw %}$$y_i^{ (k)} = \sigma

很赞哦!（793）