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

Structural Deep Network Embedding

論文閱讀Structural Deep Network Embedding
本文的PDF版深層網(wǎng)絡(luò)結(jié)構(gòu)嵌入
這學(xué)期選了非線性電路與系統(tǒng)，最近又在做網(wǎng)絡(luò)表示的相關(guān)研究，特將平時看過比較好的論文寫一寫，和大家分享一下。

簡介

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

網(wǎng)絡(luò)嵌入目前依舊面臨許多挑戰(zhàn)。（1）高維且非線性，深層的網(wǎng)絡(luò)結(jié)構(gòu)特征通常是非線性且高維的。因此，如何去描述學(xué)習(xí)這種高維非線性的特征是非常具有挑戰(zhàn)性的。（2）結(jié)構(gòu)保持，為了能夠?qū)⒔Y(jié)果應(yīng)用到一些具體的網(wǎng)絡(luò)分析任務(wù)中，網(wǎng)絡(luò)嵌入方法需要能夠?qū)⒕W(wǎng)絡(luò)結(jié)構(gòu)較好的保存下來，但是隱藏的網(wǎng)絡(luò)結(jié)構(gòu)是非常復(fù)雜并且難以發(fā)現(xiàn)的。節(jié)點(diǎn)的特性往往依賴于其局部和全局的網(wǎng)絡(luò)結(jié)構(gòu)。（3）稀疏性，真實世界中的大部分網(wǎng)絡(luò)都是稀疏的，只能夠利用極少數(shù)已發(fā)現(xiàn)的關(guān)系連接，因此還遠(yuǎn)遠(yuǎn)不能依此得到滿意的效果。
近些年來，許多網(wǎng)絡(luò)嵌入的方法相繼被提出，它們采用了一些淺顯的模型，比如說：IsoMAP，Laplacian Eigenmap(LE)，Line。由于這些模型的局限性，它們很難獲得網(wǎng)絡(luò)高維的非線性特征。為了解決這個難題，本文提出了深層模型來學(xué)習(xí)網(wǎng)絡(luò)中的節(jié)點(diǎn)表示。我們受深度學(xué)習(xí)的啟發(fā)，因為其展現(xiàn)出了強(qiáng)大的表示學(xué)習(xí)能力，能夠從復(fù)雜的網(wǎng)絡(luò)中學(xué)習(xí)特征。它已經(jīng)在圖像、文本、語音等方面取得了卓越的成績。特別的，我們提出的模型設(shè)計了多層的網(wǎng)絡(luò)結(jié)構(gòu)，這些結(jié)構(gòu)是由許多非線性函數(shù)構(gòu)成，能夠?qū)⒕W(wǎng)絡(luò)數(shù)據(jù)映射到隱藏的非線性空間中，從而挖掘出網(wǎng)絡(luò)的非線性結(jié)構(gòu)。
為了處理網(wǎng)絡(luò)結(jié)構(gòu)保存以及稀疏性問題，我們把一階相似度和二階相似度相結(jié)合，并融于學(xué)習(xí)過程中。一階相似度是兩個頂點(diǎn)之間的局部點(diǎn)對的鄰近度，但由于網(wǎng)絡(luò)的稀疏性，許多真實存在的邊可能缺失，因此，一階相似度不足以表示網(wǎng)絡(luò)結(jié)構(gòu)。因此我們更進(jìn)一步地提出了二階相似度，一對頂點(diǎn)之間的接近程度表示在網(wǎng)絡(luò)中其鄰域網(wǎng)絡(luò)結(jié)構(gòu)之間的相似性。通過一階相似度和二階相似度，我們可以很好的捕獲網(wǎng)絡(luò)的局部特性與全局特性。為了保證網(wǎng)絡(luò)的局部和全局特性在我們的模型中有較好的表示，我們提出了一種半監(jiān)督的結(jié)構(gòu)，其中，無監(jiān)督部分重構(gòu)了二階相似度，以保持全局網(wǎng)絡(luò)結(jié)構(gòu)。而有監(jiān)督的部分利用一階相似度作為監(jiān)督信息來保存網(wǎng)絡(luò)的全局結(jié)構(gòu)。因此，所學(xué)的表示能夠很好的保存網(wǎng)絡(luò)的局部和全局結(jié)構(gòu)。此外，從圖1可以看出，在許多網(wǎng)絡(luò)中二階相似度鄰近點(diǎn)對的數(shù)目比一階相似度多很多。由此可以得到，二階相似度的引入能夠在描述網(wǎng)絡(luò)結(jié)構(gòu)方面提供更多的信息。因此，我們的方法對稀疏網(wǎng)絡(luò)是魯棒的。
[圖片上傳失敗...(image-a552b0-1510922608055)]
圖1

主要貢獻(xiàn)

1. 我們提出了一種深層網(wǎng)絡(luò)結(jié)構(gòu)嵌入的方法，稱為SDNE。這種方法能夠?qū)⒕W(wǎng)絡(luò)數(shù)據(jù)映射到深層的非線性低維空間，并且具有較好的魯棒性。同時具我們所知，該方法是第一次將深度學(xué)習(xí)運(yùn)用于網(wǎng)絡(luò)表示中。
2. 我們提出了一個新的半監(jiān)督深層模型，整合了網(wǎng)絡(luò)中的一階和二階相似性。因此，通過該模型得到的低維網(wǎng)絡(luò)表示，能夠很好的表現(xiàn)網(wǎng)絡(luò)的局部和整體特征。
3. 我們提出的算法在5個真實的數(shù)據(jù)集中，分別對2種應(yīng)用問題（多標(biāo)簽分類、可視化）進(jìn)行了實驗驗證。結(jié)果顯示，對于網(wǎng)絡(luò)標(biāo)簽稀少的數(shù)據(jù)，我們比其它基準(zhǔn)方法提升了至少20%的效果。在某些情況下，我們只需要60%甚至更少的訓(xùn)練數(shù)據(jù)，也能得到很好的成績。

其他相關(guān)工作

IsoMAP

算法主要步驟：

1. 通過k-Nearest neighbor算法得到每個點(diǎn)的一個近鄰。（參數(shù)k）
2. 通過最短路算法構(gòu)造一個N*N的距離矩陣。
3. 通過Multi-dimensional Scaling算法根據(jù)距離矩陣進(jìn)行非線性降維。（參數(shù)e）
   算法結(jié)束以后，我們得到的就是一些e維空間的點(diǎn)。

DeepWalk

算法主要步驟：
在圖上隨機(jī)游走產(chǎn)生長度為$2w + 1$的路徑，對每個點(diǎn)隨機(jī)$\gamma $個隨機(jī)游走序列。每一條隨機(jī)游走路徑便是相當(dāng)于一個序列（相當(dāng)于一句話），這樣序列中的點(diǎn)就有上下文，定義一個時間窗口$w$，并進(jìn)行馬爾可夫假設(shè)，最后使用word2vec中的Skip-Gram訓(xùn)練每一個節(jié)點(diǎn)的向量。
Gram訓(xùn)練每一個節(jié)點(diǎn)的向量。
假設(shè)一個路徑序列為{% 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的優(yōu)化目標(biāo)為:
{% 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 %}是點(diǎn)${v_i}$的向量表征, {% raw %}${c_{{v_i}}}${% endraw %}是點(diǎn){% raw %}${v_i}${% endraw %}上下文中點(diǎn)${v_j}$的向量表征。
DeepWalk使目標(biāo)$f$最大化，使用Skip-Gram與Hierarchical Softmax進(jìn)行訓(xùn)練得到每個點(diǎn)的vector，DeepWalk等價于MF(matrix factorization,矩陣分解)。

深層網(wǎng)絡(luò)結(jié)構(gòu)嵌入

深層網(wǎng)絡(luò)結(jié)構(gòu)嵌入

定義1（網(wǎng)絡(luò)）：給定一個網(wǎng)絡(luò){% raw %}$G = \left( {V,E} \right)${% endraw %}，其中{% raw %}$V = { {v_1}, \cdots ,{v_n}} ${% endraw %}表示為n個節(jié)點(diǎn)，{% raw %}$E = { {e_{i,j}}} {i,j = 1}^n${% endraw %}表示網(wǎng)絡(luò)中所有邊的集合。每一條邊{% raw %}${e{i,j}}${% endraw %}與其網(wǎng)絡(luò)中邊的權(quán)重{% raw %}${s_{i,j}} \ge 0${% endraw %}相關(guān)聯(lián)。如果{% raw %}${v_i}${% endraw %}和{% raw %}${v_j}${% endraw %}之間沒有連接，那么{% raw %}${s_{i,j}} = 0${% endraw %}，否則，對于無權(quán)圖{% raw %}${s_{i,j}} = 1${% endraw %}，有權(quán)圖{% raw %}${s_{i,j}} > 0${% endraw %}
網(wǎng)絡(luò)嵌入的目的是將原始的高維網(wǎng)絡(luò)數(shù)據(jù)映射到低維的表示空間中，網(wǎng)絡(luò)中的每一個節(jié)點(diǎn)即可表示為一個低維向量，同時網(wǎng)絡(luò)計算將會變得非常方便。正如我們之前提到的，網(wǎng)絡(luò)的局部結(jié)構(gòu)和全局結(jié)構(gòu)都非常有必要在降維后保存下來，下面將詳細(xì)定義一階相似度和二階相似度。
定義2（一階相似度）：網(wǎng)絡(luò)中的一階相似度是兩個頂點(diǎn)之間的局部點(diǎn)對的鄰近度。對于由邊（u，v）鏈接的每對頂點(diǎn)，該邊的權(quán)重${s_{u,v}}$表示u和v之間的一階相似性，如果在u和v之間沒有邊，它們的一階相似度為0。
一階相似度通常意味著現(xiàn)實世界網(wǎng)絡(luò)中兩個節(jié)點(diǎn)的相似性。例如，在社交網(wǎng)絡(luò)中成為朋友的人往往具有類似的興趣；在萬維網(wǎng)上互相鏈接的頁面往往談?wù)擃愃频闹黝}。由于一階相似度的重要性，許多現(xiàn)有的圖嵌入算法，如IsoMap，LLE，Laplacian Eigenmaps目的都是保持一階相似度。
然而，在現(xiàn)實世界的信息網(wǎng)絡(luò)中，能夠觀察到的鏈接只是小部分，許多隱藏的其他關(guān)系都沒有被觀察到。缺失鏈路上的一對節(jié)點(diǎn)，即使它們在本質(zhì)上非常相似，然而他們的一階相似度為0。 因此，只有一階相似度對維持網(wǎng)絡(luò)結(jié)構(gòu)來說不是很有效。我們自然而然的想到，具有類似鄰居的頂點(diǎn)往往是相似的。 例如，在社交網(wǎng)絡(luò)中，分享相同內(nèi)容的人往往具有相似的興趣，從而成為朋友，在文本網(wǎng)絡(luò)中，總是與同一組詞匯共同出現(xiàn)的詞往往具有相似的含義。 因此，我們定義二階相似度，其補(bǔ)充了一階相似性并能夠保留網(wǎng)絡(luò)結(jié)構(gòu)。
定義3（二階相似度）：二階相似度對應(yīng)于網(wǎng)絡(luò)中的點(diǎn)對（u，v）是其鄰域網(wǎng)絡(luò)結(jié)構(gòu)之間的相似性。數(shù)學(xué)上，讓{% raw %}${{\rm{\mathcal{N}}}u} = { {s{u,1}}, \cdots ,{s_{u,\left| V \right|}}} ${% endraw %}表示一階附近 u 與所有其他的頂點(diǎn)，那么 u 和v之間的二階相似性由{% raw %}${{\rm{\mathcal{N}}}_u}$和${{\rm{\mathcal{N}}}_v}${% endraw %}之間的相似性來決定。如果沒有一個頂點(diǎn)同時和 u 與 v 鏈接，那么 u 和 v的二階相似性是0。
定義4（網(wǎng)絡(luò)嵌入）：給定網(wǎng)絡(luò){% raw %}$G = \left( {V,E} \right)${% endraw %}，網(wǎng)絡(luò)嵌入的問題是將每個頂點(diǎn)$v \in V$表示為低維空間{% raw %}${\mathbb{R}^d}${% endraw %}中的向量，學(xué)習(xí)函數(shù)$f:\left| V \right| \mapsto {\mathbb{R}^d}$，其中$d \ll \left| V \right|$。在空間{% raw %}${\mathbb{R}^d}${% endraw %}中，頂點(diǎn)之間的一階相似度和二階相似度都被保留。

SNDE模型

算法框架

在本篇文章中，我們提出了一個半監(jiān)督的網(wǎng)絡(luò)嵌入深度框架，整體框架如圖2所示。具體來說，為了捕捉高維非線性的網(wǎng)絡(luò)結(jié)構(gòu)，我們提出了一個深層的體系結(jié)構(gòu)，它由多個非線性映射函數(shù)組成，將輸入數(shù)據(jù)映射到一個高維非線性的隱藏空間，以捕獲網(wǎng)絡(luò)結(jié)構(gòu)。為了解決網(wǎng)絡(luò)結(jié)構(gòu)保持和稀疏性問題，我們提出了一個半監(jiān)督模型來利用一階和二階相似度。對于每個頂點(diǎn)，我們都可以得到它的鄰域。因此，我們設(shè)計了無監(jiān)督的組件來保持二階相似度，并重建每個頂點(diǎn)的鄰域結(jié)構(gòu)。同時，對節(jié)點(diǎn)的一部分，我們可以獲得他們的一階相似度。因此，我們設(shè)計了有監(jiān)督的組件，利用一階相似度作為監(jiān)督信息來改進(jìn)隱藏空間中的表示。通過聯(lián)合優(yōu)化所提出的半監(jiān)督深度模型，SDNE可以保持高維的非線性網(wǎng)絡(luò)結(jié)構(gòu)，保證稀疏網(wǎng)絡(luò)的健壯性。在接下來的部分中，我們將詳細(xì)介紹如何實現(xiàn)半監(jiān)督的深度模型。
[圖片上傳失敗...(image-4ccde2-1510922608055)]
圖2.網(wǎng)絡(luò)整體結(jié)構(gòu)

損失函數(shù)

我們首先描述無監(jiān)督組件如何利用二階近似保持全局網(wǎng)絡(luò)結(jié)構(gòu)。
二階相似性值指的是節(jié)點(diǎn)的鄰居相似，因此模型的二階相似性，需要每個節(jié)點(diǎn)鄰居的性質(zhì)。給定一個網(wǎng)絡(luò){% 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}$描述了節(jié)點(diǎn)${v_i}$的鄰居結(jié)構(gòu)，$S$提供了每一個節(jié)點(diǎn)的鄰居結(jié)構(gòu)信息。對于$S$來說，我們將傳統(tǒng)的深度自編碼器的進(jìn)行延伸，用來保存網(wǎng)絡(luò)的二階相似性。
下面簡單回顧一下深度自編碼器的主要思想。它屬于一種非監(jiān)督模型，包含編碼器與解碼器。編碼器由許多非線性函數(shù)構(gòu)成，將輸入數(shù)據(jù)映射到表示空間。對應(yīng)的，解碼器也由許多非線性函數(shù)構(gòu)成，它將表示空間映射到輸入數(shù)據(jù)的重構(gòu)空間。給定輸入數(shù)據(jù)${x_i}$，其中對于各個層的隱藏表示如下公式進(jìn)行計算：
{% raw %}$$y_i^{(1)} = \sigma ({W^{(1)}}{x_i} + {b^{(1)}})$${% endraw %}
{% raw %}$$y_i^{(k)} = \sigma ({W^{(k)}}y_i{(k - 1)} + {b^{(k)}}),k = 2, \cdots ,K$${% endraw %}
通過一系列編碼器的計算，我們可以獲得輸出${\hat x_i}$。自動編碼器的目標(biāo)是盡量減少輸入和輸出的重構(gòu)誤差。損失函數(shù)可以表示為：
{% raw %}$${\rm{\mathcal{L}}} = \sum\limits_{i = 1}^n {\left| {{{\hat x}i} - {x_i}} \right|2^2} $${% endraw %}
通過最小化損失函數(shù)能夠較好的還原輸入數(shù)據(jù)的原始表達(dá)，其表示空間能夠提取出原始輸入數(shù)據(jù)的特征?；谏鲜鎏匦?，我們將網(wǎng)絡(luò)的鄰接矩陣S作為自動編碼器的輸入，如： ${x_i} = {s_i}$，那么每一個元素${s_i}$表示節(jié)點(diǎn)${v_i}$鄰居節(jié)點(diǎn)的特征。因此，通過重構(gòu)可以讓具有相似鄰居結(jié)構(gòu)的節(jié)點(diǎn)在隱藏的表示空間也具有相似的表達(dá)。
但是，僅僅通過這種方式還不能直接解決問題。因為在網(wǎng)絡(luò)中，我們可以觀察到一些連接，但是也有一些合法的連接是缺失的。此外，由于網(wǎng)絡(luò)的稀疏性，在鄰接矩陣$S$中，零元素遠(yuǎn)遠(yuǎn)大于非零元素。如果我們直接將S輸入到傳統(tǒng)的自編碼器中，可能會導(dǎo)致大量的零元素出現(xiàn)在重構(gòu)空間，這并不是我們想要的結(jié)果。為了解決這個問題，我們讓其對非零元素的重構(gòu)誤差比零元素的懲罰更大。改進(jìn)的目標(biāo)函數(shù)如下所示：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}}{2nd}} = \sum\limits{i = 1}^n {\left| {({{\hat x}i} - {x_i}) \odot {b_i}} \right|2^2} \{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \left| {(\hat X - X) \odot B} \right|F^2\end{array}$${% endraw %}
其中$ \odot $表示Hadamard積，{% raw %}${b_i} = { {b{i,j}}} {j = 1}^n${% endraw %}，如果{% raw %}${s{i,j}} = 0${% endraw %}，那么{% raw %}${b{i,j}} = 1${% endraw %}，否則${b{i,j}} = \beta > 1$。通過這種改進(jìn)的損失函數(shù)，可以更好的讓具有相似鄰居的點(diǎn)在獲得的表示空間也相似。換句話說，這個非監(jiān)督部分能夠很好的保存網(wǎng)絡(luò)的二階相似度。
不僅要維持全局網(wǎng)絡(luò)結(jié)構(gòu)，而且要捕獲局部結(jié)構(gòu)。我們使用一階相似度表示網(wǎng)絡(luò)局部結(jié)構(gòu)。一階相似度可以作為監(jiān)督信息來約束一對頂點(diǎn)在隱藏表示空間的相似性。因此，我們設(shè)計了監(jiān)督部分來利用一階相似度。損失函數(shù)如下所示：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}}{1nd}} = \sum\limits{i = 1}^n {{s_{i,j}}\left| {y_i^{(K)} - y_j^{(K)}} \right|2^2} \{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \sum\limits{i = 1}^n {{s_{i,j}}\left| {{y_i} - {y_j}} \right|2^2} \end{array}$${% endraw %}
其中{% raw %}${Y^{(k)}} = { y_i^{(k)}} {i = 1}^n${% endraw %}為編碼器獲得的隱藏表示空間。
該公式的靈感來源于拉普拉斯特征映射(Laplacian Eigenmaps)，在表示空間中，如果相似的節(jié)點(diǎn)相距較遠(yuǎn)，那么會受到一個較大的懲罰。通過這一操作，我們的模型能夠很好的保持網(wǎng)絡(luò)的一階相似度。
我們同時考慮網(wǎng)絡(luò)的一階相似度和二階相似度，另外在加上L2正則項，共同構(gòu)成了自動編碼器的損失函數(shù)：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}}{mix}} = {{\rm{\mathcal{L}}}{2nd}} + \alpha {{\rm{\mathcal{L}}}{1nd}} + \upsilon {{\rm{\mathcal{L}}}{reg}}\{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \left| {(\hat X - X) \odot B} \right|F^2 + \alpha \sum\limits{i = 1}^n {{s_{i,j}}\left| {{y_i} - {y_j}} \right|2^2} + \upsilon {{\rm{\mathcal{L}}}{reg}}\end{array}$${% endraw %}
其中：
{% raw %}$$\begin{array}{l}{{\rm{\mathcal{L}}}{mix}} = {{\rm{\mathcal{L}}}{2nd}} + \alpha {{\rm{\mathcal{L}}}{1nd}} + \upsilon {{\rm{\mathcal{L}}}{reg}}\{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} = \left| {(\hat X - X) \odot B} \right|F^2 + \alpha \sum\limits{i = 1}^n {{s_{i,j}}\left| {{y_i} - {y_j}} \right|2^2} + \upsilon {{\rm{\mathcal{L}}}{reg}}\end{array}$${% endraw %}

實驗

數(shù)據(jù)集

為了能夠全面地評價算法得到的低維表示，我們使用了5個真實的網(wǎng)絡(luò)數(shù)據(jù)，包括3個社交網(wǎng)絡(luò)，1個引文網(wǎng)絡(luò)，1個語言網(wǎng)絡(luò)；實驗了2類網(wǎng)絡(luò)應(yīng)用任務(wù)，包括多標(biāo)簽分類和可視化。考慮到各個網(wǎng)絡(luò)數(shù)據(jù)的本身屬性，對于每一類應(yīng)用，我們使用了至少一個數(shù)據(jù)集進(jìn)行試驗。數(shù)據(jù)集的參數(shù)如下表所示：

表1. 網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)

對比算法

我們實驗與以下幾個基準(zhǔn)算法進(jìn)行比較：DeepWalk、LINE、GraRep、Laplacian Eigenmaps、Common Neighbor。

評價指標(biāo)

對于多標(biāo)簽分類問題，我們采用micro-F1和macro-F1指標(biāo)進(jìn)行評價。對于標(biāo)簽A，我們將TP（A），F(xiàn)P（A）和FN（A）分別表示為屬于A的樣本被正確分類到A的數(shù)目，不屬于A的樣本被錯誤分類到A的數(shù)目和不屬于A的樣本被正確分類到了類別A的其他類的數(shù)目。假設(shè) 是整個標(biāo)簽集。Micro-F1和Macro-F1定義如下：
Macro-F1是一個每個類的權(quán)重的度量。 定義如下：
{% raw %}$$Macro - F1 = \frac{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {F1(A)} }}{{\left| {\rm{\mathcal{C}}} \right|}}$${% endraw %}
其中F1(A)是標(biāo)簽A的F1度量。
Micro-F1是對每個實例權(quán)重的度量。定義如下：
{% raw %}$$\Pr = \frac{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {TP(A)} }}{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {(TP(A) + FP(A))} }}$${% endraw %}
{% raw %}$$R = \frac{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {TP(A)} }}{{\sum\nolimits_{A \in {\rm{\mathcal{C}}}} {(TP(A) + FN(A))} }}$${% endraw %}
{% raw %}$$Micro - F1 = \frac{{2*\Pr *R}}{{\Pr + R}}$${% endraw %}

參數(shù)設(shè)置

我們在本文中提出了一種多層的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，層數(shù)隨不同的數(shù)據(jù)集而做相應(yīng)調(diào)整。每層的神經(jīng)元數(shù)目如表2所示。其中BLOGCATALOG，ARXIV GR-QC和20-EWSGROUP使用了三層神經(jīng)網(wǎng)絡(luò)，F(xiàn)LICKR和YOUTUBE使用了四層。如果我們使用更深的模型，性能幾乎保持不變，甚至變得更糟。

表2. 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)
對于我們的方法，通過在驗證集上使用網(wǎng)格搜索(grid search)來調(diào)整 ， 和 三個超參數(shù)。對于LINE，隨機(jī)梯度下降的mini-batch大小設(shè)置為1。學(xué)習(xí)速率的初始值為0.025。負(fù)采樣數(shù)(number of negative samples)為5，總采樣數(shù)(the total number of samples)設(shè)為100億。對于DeepWalk，我們將窗口大小設(shè)置為10，步長為40，每次采樣40個頂點(diǎn)。對于GraRep，我們將最大轉(zhuǎn)移矩陣步長(maximum matrix transition step)設(shè)置為5。

實驗結(jié)果

多標(biāo)簽分類

我們通過本實驗中的多標(biāo)簽分類任務(wù)來評估不同網(wǎng)絡(luò)表示的有效性。頂點(diǎn)的表示是從網(wǎng)絡(luò)嵌入方法生成的，并被用作將每個頂點(diǎn)分成一組標(biāo)簽的特征。具體來說，我們采用LIBLINEAR軟件包來訓(xùn)練分類器。訓(xùn)練分類器時，我們隨機(jī)抽取標(biāo)簽節(jié)點(diǎn)的一部分作為訓(xùn)練數(shù)據(jù)，其余作為測試。對于BLOGCATALOG，我們隨機(jī)抽取10％至90％的頂點(diǎn)作為訓(xùn)練樣本，并使用剩余頂點(diǎn)來測試性能。對于FLICKR和YOUTUBE，我們隨機(jī)抽取1％至10％的頂點(diǎn)作為訓(xùn)練樣本，并使用剩余頂點(diǎn)來測試性能。另外，我們刪除沒有在YOUTUBE中被任何類別標(biāo)記的頂點(diǎn)。我們重復(fù)進(jìn)行5次實驗，取Micro-F1和Macro-F1指標(biāo)的平均值進(jìn)行度量。結(jié)果分別如圖3到圖5所示。
[圖片上傳失敗...(image-8c4a6-1510922608055)]
圖3 .Micro-F1和Macro-F1在BLOGCATALOG上的表現(xiàn)
[圖片上傳失敗...(image-953fed-1510922608055)]
圖4 .Micro-F1和Macro-F1在FLICKR上的表現(xiàn)
[圖片上傳失敗...(image-bce93a-1510922608055)]
圖5 .Micro-F1和Macro-F1在YOUTUBE上的表現(xiàn)
在圖3到圖5中，我們算法的曲線一直高于其他基準(zhǔn)算法的曲線。它表明，在多標(biāo)簽分類任務(wù)中我們算法學(xué)習(xí)得到的網(wǎng)絡(luò)表示比其他算法得到的效果更好。
在圖3（BLOGCATALOG）中，當(dāng)訓(xùn)練百分比從60％下降到10％時，我們的方法在基準(zhǔn)線上的改善幅度更為明顯。它表明當(dāng)標(biāo)簽數(shù)據(jù)有限時，我們的方法可以比基準(zhǔn)算法有更顯著的改進(jìn)。這樣的優(yōu)勢對于現(xiàn)實世界的應(yīng)用尤其重要，因為標(biāo)記的數(shù)據(jù)通常很少。
在大多數(shù)情況下，DeepWalk的性能是網(wǎng)絡(luò)嵌入方法中最差的。原因有兩個方面。首先，DeepWalk沒有明確的目標(biāo)函數(shù)來捕獲網(wǎng)絡(luò)結(jié)構(gòu)。其次，DeepWalk使用隨機(jī)游走來獲得頂點(diǎn)的鄰居，由于隨機(jī)性而引起了很多噪音，特別是對于度數(shù)高的頂點(diǎn)。

可視化

網(wǎng)絡(luò)嵌入的另一個重要應(yīng)用是在二維空間上生成網(wǎng)絡(luò)的可視化。對此我們在20-NEWSGROUP網(wǎng)絡(luò)進(jìn)行可視化的實驗。我們使用不同網(wǎng)絡(luò)嵌入方法學(xué)習(xí)的低維網(wǎng)絡(luò)表示作為可視化工具t-SNE的輸入。因此，每個新聞組文檔被映射為二維向量。然后我們可以將每個向量可視化為二維空間上的一個點(diǎn)。對于被標(biāo)記為不同類別的文檔，我們在對應(yīng)的點(diǎn)上使用不同的顏色。因此，良好的可視化結(jié)果能讓相同顏色的點(diǎn)彼此靠近?？梢暬Y(jié)果如圖6所示。
[圖片上傳失敗...(image-b52fc7-1510922608055)]
圖6. 20-NEWSGROUP的可視化
每個點(diǎn)表示一個文檔。點(diǎn)的顏色表示文檔的類別。藍(lán)色表示rec.sport.baseball的主題，紅色表示comp.graphics的主題，綠色表示talk.politics.guns的主題。
從圖7可以看出，LE和DeepWalk的結(jié)果并不理想，屬于不同類別的點(diǎn)相互混合。對于LINE，形成不同類別的群集。然而，在中心部分，不同類別的文件仍然相互混合。對于GraRep，結(jié)果看起來更好，因為相同顏色的點(diǎn)分割成分組，但是，每個群體的邊界不是很清楚。顯然，SDNE的可視化效果在群體分離和邊界方面都表現(xiàn)最好。

總結(jié)

在本文中，我們提出了一種深層網(wǎng)絡(luò)結(jié)構(gòu)嵌入，即SDNE來執(zhí)行網(wǎng)絡(luò)嵌入。具體來說，為了捕獲高維非線性的網(wǎng)絡(luò)結(jié)構(gòu)，我們設(shè)計了一個具有多層非線性函數(shù)的半監(jiān)督深度模型。為了進(jìn)一步解決網(wǎng)絡(luò)結(jié)構(gòu)保持和稀疏問題，我們同時使用了一階鄰近度和二階鄰近度來表示網(wǎng)絡(luò)的局部和全局特征。通過在半監(jiān)督的深度模型中優(yōu)化它們，所學(xué)習(xí)的表示能夠體現(xiàn)出網(wǎng)絡(luò)的局部和全局特征，并且對稀疏網(wǎng)絡(luò)是魯棒的。我們在真實的網(wǎng)絡(luò)數(shù)據(jù)集上試驗了多標(biāo)簽分類和可視化任務(wù)。結(jié)果表明，我們的算法與當(dāng)前最好的算法(state-of-the-art)相比有本質(zhì)性的提高。