由于平臺限制腊敲，公式無法顯示，更好閱讀體驗，請訪問(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é)點到數(shù)百萬和數(shù)十億個節(jié)點不等飞几。大規(guī)模信息網(wǎng)絡(luò)的分析在學(xué)術(shù)界和工業(yè)界引起越來越多的關(guān)注。本文研究的是將信息網(wǎng)絡(luò)嵌入到低維空間的問題独撇，其中每個頂點都表示為一個低維向量屑墨。這種低維嵌入在各種應(yīng)用中非常有用，如可視化纷铣，節(jié)點分類卵史，鏈路預(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é)點的特性往往依賴于其局部和全局的網(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é)點表示。我們受深度學(xué)習(xí)的啟發(fā)阔加，因為其展現(xiàn)出了強大的表示學(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í)過程中戴卜。一階相似度是兩個頂點之間的局部點對的鄰近度，但由于網(wǎng)絡(luò)的稀疏性琢岩，許多真實存在的邊可能缺失投剥，因此，一階相似度不足以表示網(wǎng)絡(luò)結(jié)構(gòu)担孔。因此我們更進(jì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ò)中二階相似度鄰近點對的數(shù)目比一階相似度多很多。由此可以得到徘键，二階相似度的引入能夠在描述網(wǎng)絡(luò)結(jié)構(gòu)方面提供更多的信息练对。因此，我們的方法對稀疏網(wǎng)絡(luò)是魯棒的吹害。
[圖片上傳失敗...(image-a552b0-1510922608055)]
圖1
主要貢獻(xiàn)
- 我們提出了一種深層網(wǎng)絡(luò)結(jié)構(gòu)嵌入的方法螟凭，稱為SDNE。這種方法能夠?qū)⒕W(wǎng)絡(luò)數(shù)據(jù)映射到深層的非線性低維空間它呀，并且具有較好的魯棒性赂摆。同時具我們所知，該方法是第一次將深度學(xué)習(xí)運用于網(wǎng)絡(luò)表示中钟些。
- 我們提出了一個新的半監(jiān)督深層模型烟号，整合了網(wǎng)絡(luò)中的一階和二階相似性。因此政恍，通過該模型得到的低維網(wǎng)絡(luò)表示汪拥，能夠很好的表現(xiàn)網(wǎng)絡(luò)的局部和整體特征。
- 我們提出的算法在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
算法主要步驟：
- 通過k-Nearest neighbor算法得到每個點的一個近鄰邓厕。（參數(shù)k）
- 通過最短路算法構(gòu)造一個N*N的距離矩陣逝嚎。
- 通過Multi-dimensional Scaling算法根據(jù)距離矩陣進(jìn)行非線性降維。（參數(shù)e）
算法結(jié)束以后详恼，我們得到的就是一些e維空間的點补君。
DeepWalk
算法主要步驟：
在圖上隨機游走產(chǎn)生長度為$2w + 1$的路徑，對每個點隨機$\gamma $個隨機游走序列昧互。每一條隨機游走路徑便是相當(dāng)于一個序列（相當(dāng)于一句話）挽铁，這樣序列中的點就有上下文伟桅，定義一個時間窗口$w$，并進(jìn)行馬爾可夫假設(shè)叽掘，最后使用word2vec中的Skip-Gram訓(xùn)練每一個節(jié)點的向量楣铁。
Gram訓(xùn)練每一個節(jié)點的向量。
假設(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 %}是點${v_i}$的向量表征, {% raw %}${c_{{v_i}}}${% endraw %}是點{% raw %}${v_i}${% endraw %}上下文中點${v_j}$的向量表征民褂。
DeepWalk使目標(biāo)$f$最大化茄菊，使用Skip-Gram與Hierarchical Softmax進(jìn)行訓(xù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é)點竖哩，{% 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é)點即可表示為一個低維向量乌企，同時網(wǎng)絡(luò)計算將會變得非常方便虑润。正如我們之前提到的，網(wǎng)絡(luò)的局部結(jié)構(gòu)和全局結(jié)構(gòu)都非常有必要在降維后保存下來加酵，下面將詳細(xì)定義一階相似度和二階相似度拳喻。
定義2（一階相似度）：網(wǎng)絡(luò)中的一階相似度是兩個頂點之間的局部點對的鄰近度。對于由邊（u猪腕，v）鏈接的每對頂點冗澈，該邊的權(quán)重${s_{u,v}}$表示u和v之間的一階相似性，如果在u和v之間沒有邊陋葡，它們的一階相似度為0亚亲。
一階相似度通常意味著現(xiàn)實世界網(wǎng)絡(luò)中兩個節(jié)點的相似性。例如腐缤，在社交網(wǎng)絡(luò)中成為朋友的人往往具有類似的興趣朵栖；在萬維網(wǎng)上互相鏈接的頁面往往談?wù)擃愃频闹黝}。由于一階相似度的重要性柴梆，許多現(xiàn)有的圖嵌入算法陨溅，如IsoMap，LLE绍在，Laplacian Eigenmaps目的都是保持一階相似度门扇。
然而雹有，在現(xiàn)實世界的信息網(wǎng)絡(luò)中，能夠觀察到的鏈接只是小部分臼寄，許多隱藏的其他關(guān)系都沒有被觀察到霸奕。缺失鏈路上的一對節(jié)點，即使它們在本質(zhì)上非常相似吉拳，然而他們的一階相似度為0质帅。 因此，只有一階相似度對維持網(wǎng)絡(luò)結(jié)構(gòu)來說不是很有效留攒。我們自然而然的想到煤惩，具有類似鄰居的頂點往往是相似的。 例如炼邀，在社交網(wǎng)絡(luò)中魄揉，分享相同內(nèi)容的人往往具有相似的興趣，從而成為朋友拭宁，在文本網(wǎng)絡(luò)中洛退，總是與同一組詞匯共同出現(xiàn)的詞往往具有相似的含義。 因此杰标，我們定義二階相似度兵怯，其補充了一階相似性并能夠保留網(wǎng)絡(luò)結(jié)構(gòu)。
定義3（二階相似度）：二階相似度對應(yīng)于網(wǎng)絡(luò)中的點對（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 與所有其他的頂點桶蝎，那么 u 和v之間的二階相似性由{% raw %}${{\rm{\mathcal{N}}}_u}$和${{\rm{\mathcal{N}}}_v}${% endraw %}之間的相似性來決定驻仅。如果沒有一個頂點同時和 u 與 v 鏈接，那么 u 和 v的二階相似性是0登渣。
定義4（網(wǎng)絡(luò)嵌入）：給定網(wǎng)絡(luò){% raw %}$G = \left( {V,E} \right)${% endraw %}噪服，網(wǎng)絡(luò)嵌入的問題是將每個頂點$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 %}中，頂點之間的一階相似度和二階相似度都被保留呻顽。
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)督模型來利用一階和二階相似度绒净。對于每個頂點，我們都可以得到它的鄰域偿衰。因此挂疆，我們設(shè)計了無監(jiān)督的組件來保持二階相似度，并重建每個頂點的鄰域結(jié)構(gòu)下翎。同時缤言，對節(jié)點的一部分，我們可以獲得他們的一階相似度漏设。因此墨闲，我們設(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é)點的鄰居相似，因此模型的二階相似性推励，需要每個節(jié)點鄰居的性質(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é)點${v_i}$的鄰居結(jié)構(gòu)壳贪，$S$提供了每一個節(jié)點的鄰居結(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é)點${v_i}$鄰居節(jié)點的特征馅笙。因此，通過重構(gòu)可以讓具有相似鄰居結(jié)構(gòu)的節(jié)點在隱藏的表示空間也具有相似的表達(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ù)，可以更好的讓具有相似鄰居的點在獲得的表示空間也相似钩蚊。換句話說贡翘，這個非監(jiān)督部分能夠很好的保存網(wǎng)絡(luò)的二階相似度蹈矮。
不僅要維持全局網(wǎng)絡(luò)結(jié)構(gòu)，而且要捕獲局部結(jié)構(gòu)鸣驱。我們使用一階相似度表示網(wǎng)絡(luò)局部結(jié)構(gòu)泛鸟。一階相似度可以作為監(jiā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é)點相距較遠(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ù)集
| 數(shù)據(jù)集 | #(V) | #(E) |
|---|---|---|
| BLOGCATALOG | 10312 | 667966 |
| FLICKR | 80513 | 11799764 |
| YOUTUBE | 1138499 | 5980886 |
| ARXIV GR-QC | 5242 | 28980 |
| 20-NEWSGROUP | 1720 | Full-connected |
為了能夠全面地評價算法得到的低維表示，我們使用了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ù)如下表所示：
| 數(shù)據(jù)集 | #(V) | #(E) |
|---|---|---|
| BLOGCATALOG | 10312 | 667966 |
| FLICKR | 80513 | 11799764 |
| YOUTUBE | 1138499 | 5980886 |
| ARXIV GR-QC | 5242 | 28980 |
| 20-NEWSGROUP | 1720 | Full-connected |
表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è)置
| 數(shù)據(jù)集 | 每一層神經(jīng)元數(shù) |
|---|---|
| BLOGCATALOG | 10300-1000-100 |
| FLICKR | 80513-5000-1000-100 |
| YOUTUBE | 22693-5000-1000-100 |
| ARXIV GR-QC | 5242-500-100 |
| 20-NEWSGROUP | 1720-200-100 |
我們在本文中提出了一種多層的神經(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使用了四層外遇。如果我們使用更深的模型注簿，性能幾乎保持不變，甚至變得更糟跳仿。
| 數(shù)據(jù)集 | 每一層神經(jīng)元數(shù) |
|---|---|
| BLOGCATALOG | 10300-1000-100 |
| FLICKR | 80513-5000-1000-100 |
| YOUTUBE | 22693-5000-1000-100 |
| ARXIV GR-QC | 5242-500-100 |
| 20-NEWSGROUP | 1720-200-100 |
表2. 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)
對于我們的方法诡渴，通過在驗證集上使用網(wǎng)格搜索(grid search)來調(diào)整 ， 和 三個超參數(shù)菲语。對于LINE妄辩，隨機梯度下降的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個頂點妄帘。對于GraRep楞黄，我們將最大轉(zhuǎn)移矩陣步長(maximum matrix transition step)設(shè)置為5。
實驗結(jié)果
多標(biāo)簽分類
我們通過本實驗中的多標(biāo)簽分類任務(wù)來評估不同網(wǎng)絡(luò)表示的有效性抡驼。頂點的表示是從網(wǎng)絡(luò)嵌入方法生成的鬼廓，并被用作將每個頂點分成一組標(biāo)簽的特征。具體來說致盟，我們采用LIBLINEAR軟件包來訓(xùn)練分類器碎税。訓(xùn)練分類器時，我們隨機抽取標(biāo)簽節(jié)點的一部分作為訓(xùn)練數(shù)據(jù)馏锡，其余作為測試雷蹂。對于BLOGCATALOG，我們隨機抽取10％至90％的頂點作為訓(xùn)練樣本眷篇，并使用剩余頂點來測試性能萎河。對于FLICKR和YOUTUBE，我們隨機抽取1％至10％的頂點作為訓(xùn)練樣本，并使用剩余頂點來測試性能虐杯。另外玛歌，我們刪除沒有在YOUTUBE中被任何類別標(biāo)記的頂點。我們重復(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使用隨機游走來獲得頂點的鄰居，由于隨機性而引起了很多噪音臼闻，特別是對于度數(shù)高的頂點鸿吆。
可視化
網(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的輸入。因此蕉毯，每個新聞組文檔被映射為二維向量乓搬。然后我們可以將每個向量可視化為二維空間上的一個點。對于被標(biāo)記為不同類別的文檔代虾，我們在對應(yīng)的點上使用不同的顏色进肯。因此，良好的可視化結(jié)果能讓相同顏色的點彼此靠近棉磨〗冢可視化結(jié)果如圖6所示。
[圖片上傳失敗...(image-b52fc7-1510922608055)]
圖6. 20-NEWSGROUP的可視化
每個點表示一個文檔。點的顏色表示文檔的類別环形。藍(lán)色表示rec.sport.baseball的主題策泣，紅色表示comp.graphics的主題，綠色表示talk.politics.guns的主題抬吟。
從圖7可以看出萨咕，LE和DeepWalk的結(jié)果并不理想，屬于不同類別的點相互混合火本。對于LINE危队，形成不同類別的群集。然而钙畔，在中心部分茫陆，不同類別的文件仍然相互混合。對于GraRep擎析，結(jié)果看起來更好盅弛，因為相同顏色的點分割成分組，但是叔锐，每個群體的邊界不是很清楚挪鹏。顯然，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ì)性的提高。
