今天學(xué)的論文是清華大學(xué)崔鵬老師工作《Structural Deep Network Embedding》（后簡(jiǎn)稱 SDNE）杨何，并發(fā)表于 2016 KDD俺亮，目前為止共有 880 多引用，是一個(gè)非常經(jīng)典的將深度學(xué)習(xí)應(yīng)用于 NetWork Embedding 的算法罩润。
SDNE 算法是一個(gè)由多層非線形函數(shù)組成的深度學(xué)習(xí)模型玖翅，其可以捕捉高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)，同時(shí)聯(lián)合優(yōu)化 first-order 和 second-order 學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)割以，前者用作監(jiān)督信息以捕捉網(wǎng)絡(luò)局部結(jié)構(gòu)金度，后者用作非監(jiān)督信息以捕捉網(wǎng)絡(luò)全局結(jié)構(gòu)，所以 SDNE 是一個(gè)半監(jiān)督的深度學(xué)習(xí)模型严沥。
我相信大家看完這段會(huì)有很多疑問(wèn)猜极，至少我看完有以下疑問(wèn)：
多層非線性函數(shù)長(zhǎng)什么樣子？具有非線性激活函數(shù)的多層神經(jīng)網(wǎng)絡(luò)消玄？
如何把 first-order 用作監(jiān)督信息魔吐？
同理，second-order 如何用做非監(jiān)督學(xué)習(xí)莱找？
如何聯(lián)合優(yōu)化酬姆？
深度學(xué)習(xí)模型的 Embedding 怎么得到？還是原來(lái)的那個(gè)輸入矩陣嗎奥溺？
-
引入深度模型是為了擬合高度非線形的網(wǎng)絡(luò)辞色，那速度怎么樣？可以用于大規(guī)模網(wǎng)絡(luò)嗎浮定？
帶著問(wèn)題相满，我們來(lái)一起讀一下論文。
1. Introduction
在真實(shí)網(wǎng)絡(luò)世界中學(xué)習(xí) NetWork Embedding立美，有三大挑戰(zhàn)：
高度非線性：網(wǎng)絡(luò)的底層結(jié)構(gòu)是高度非線性的，使用淺層網(wǎng)絡(luò)無(wú)法捕捉高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)碌更；
結(jié)構(gòu)捕捉：既要捕捉網(wǎng)絡(luò)的局部結(jié)構(gòu)，又要捕捉網(wǎng)絡(luò)的全局結(jié)構(gòu)痛单；
稀疏性：大部分真實(shí)網(wǎng)絡(luò)都是稀疏的劲腿，僅利用節(jié)點(diǎn)的有限連接是不夠的。
為了解決這三大問(wèn)題焦人，作者也提出了三大解決方案：
高度非線性：設(shè)計(jì)了一個(gè)由多層非線性函數(shù)組成的深度網(wǎng)絡(luò)來(lái)學(xué)習(xí) NetWork Embedding，深度網(wǎng)絡(luò)有強(qiáng)大的表示能力來(lái)學(xué)習(xí)網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu)花椭；而多層非線性函數(shù)可以將數(shù)據(jù)映射到一個(gè)高度非線性的潛在空間，可以更好的捕捉到高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)脉幢；
結(jié)構(gòu)捕捉：將 first-order 和 second-order 聯(lián)合應(yīng)用到網(wǎng)絡(luò)的學(xué)習(xí)過(guò)程中歪沃，前者用于捕捉網(wǎng)絡(luò)局部結(jié)構(gòu)，后者用于捕捉網(wǎng)絡(luò)全局結(jié)構(gòu)沪曙；
稀疏性：first-order 是基于節(jié)點(diǎn)間的邊連接奕污，即原始網(wǎng)絡(luò)結(jié)構(gòu)；而 second-order 是基于兩個(gè)節(jié)點(diǎn)共享的鄰域連接來(lái)捕捉節(jié)點(diǎn)的相似性液走，且具有 second-order 相似性的節(jié)點(diǎn)數(shù)量更多碳默，如下圖所示，所以加入 second-order 一定程度上緩解了網(wǎng)絡(luò)稀疏的問(wèn)題缘眶。
fisrt order and second order2. SDNE
我們來(lái)看下 SDNE 具體是怎么實(shí)現(xiàn)的嘱根。
2.1 Autoencoder
在介紹 SDNE 的模型架構(gòu)前，我們先補(bǔ)充學(xué)習(xí)一個(gè)基礎(chǔ)知識(shí)——自編碼器巷懈。
自編碼器（AutoEncoder） 是只有一層隱層節(jié)點(diǎn)该抒，并且輸入和輸出具有相同節(jié)點(diǎn)數(shù)的神經(jīng)網(wǎng)絡(luò)，其目的是求函數(shù)：顶燕。簡(jiǎn)單放一張圖：
AutoEncoder可以看到凑保，不考慮輸入層偏置項(xiàng)的話冈爹，輸入節(jié)點(diǎn)和輸出節(jié)點(diǎn)是一致的喘帚。那么我們?yōu)槭裁匆@么做呢嫉入？
舉一個(gè)例子：我們傳輸大文件時(shí)有兩種方式：直接傳或者是壓縮后再傳敛滋。我們通常會(huì)選擇后者蚁署，因?yàn)閴嚎s后不但文件的體積會(huì)變小隙疚，并且在傳輸完成后還可以通過(guò)解壓還原出原來(lái)的文件绿渣。
而自動(dòng)編碼器也類(lèi)似于這種過(guò)程萌衬，為了盡可能復(fù)現(xiàn)輸入數(shù)據(jù)胰苏，自編碼器必須捕捉輸入數(shù)據(jù)的重要特征癌蓖，從而找到能夠代表原數(shù)據(jù)的主要成分瞬哼，這個(gè)過(guò)程有點(diǎn)類(lèi)似主成分分析（Principal Components Analysis，PCA）租副。
自編碼器沒(méi)有標(biāo)簽數(shù)據(jù)坐慰，所以是一種非監(jiān)督學(xué)習(xí)，前半部分為編碼器用僧，后半部分為解碼器。在實(shí)際應(yīng)用中通常會(huì)使用自編碼器的前半部分糟港。
SDNE 采用的自編碼器比較深秸抚，有多個(gè)隱藏層剥汤，如下圖所示：
deep encoder自編碼器的隱藏層可以表示為：
其中吭敢， 為輸入值鹿驼， 為第 k 層的 i 個(gè)節(jié)點(diǎn)的輸出值畜晰， 為第 k 層的參數(shù)矩陣凄鼻， 為第 k 層的偏置項(xiàng)扫步。
得到 后匈子，我們通過(guò)反轉(zhuǎn)編碼器的計(jì)算過(guò)程得到輸出值 ，自編碼器的目標(biāo)是最小化輸入和輸出的重構(gòu)誤差游岳，所以代價(jià)函數(shù)為：
2.2 FrameWork
然后我們來(lái)看下 SDNE 的整體框架：
Framework of SDNE以左邊的為例：輸入為鄰接矩陣胚迫，輸出為重構(gòu)后的鄰接矩陣访锻，通過(guò)優(yōu)化重構(gòu)誤差來(lái)捕捉全局結(jié)構(gòu)特征期犬；而中間一排龟虎， 就是我們需要的 Embedding 向量鲤妥，模型通過(guò)拉普拉斯特征變換（Laplacian Eigenmaps）優(yōu)化的代價(jià)函數(shù)使得相鄰節(jié)點(diǎn)的 Embedding 向量距離更近拱雏，從而捕捉節(jié)點(diǎn)的局部特征古涧。
PS：個(gè)人猜測(cè)：這里框架圖雖然畫(huà)了兩個(gè)自編碼器羡滑，SDNE 應(yīng)該是只有一個(gè)自編碼器柒昏。如果是兩個(gè)的話职祷，共享參數(shù)這個(gè)操作相對(duì)復(fù)雜有梆，而記錄鄰居節(jié)點(diǎn)的 Embedding 向量就比較容易了。
PS：論文中的圖片畫(huà)錯(cuò)了饺汹，所以我 PS 了一下兜辞。
2.3 Object Functions
再來(lái)看一下半監(jiān)督模型的目標(biāo)函數(shù)逸吵，目標(biāo)函數(shù)由代價(jià)函數(shù)和正則項(xiàng)構(gòu)成扫皱，SDNE 的代價(jià)函數(shù)分為兩塊啸罢，一塊是 first-order 胎食，另一塊是 second-order 衩匣。
我們先來(lái)看一下如何在代價(jià)函數(shù)中加入 second-order 來(lái)捕捉全局網(wǎng)絡(luò)結(jié)構(gòu)琅捏。
second-order 是基于節(jié)點(diǎn)的鄰域建模的递雀，所以我們定義鄰接矩陣：
其中缀程， 為節(jié)點(diǎn) 和節(jié)點(diǎn) 之間的邊滤奈，這里考慮加權(quán)邊撩满； 描述了節(jié)點(diǎn) 的的鄰域結(jié)構(gòu)。
我們將 作為自編碼器的輸入忌锯，即 领炫，由于 反映了節(jié)點(diǎn) 的鄰域結(jié)構(gòu)驹吮，所以通過(guò)自編碼器的重構(gòu)可以使得具有類(lèi)似特征的節(jié)點(diǎn)獲得相似的 Embedding 向量碟狞。
然而，由于網(wǎng)絡(luò)的稀疏性频祝， 將有大量的非零元素常空，所以如果直接使用鄰接矩陣 S 作為自編碼器的輸入則可能會(huì)重構(gòu)出 S 的零元素漓糙。所以為了解決這問(wèn)題昆禽，我們加大了非零元素的懲罰權(quán)重醉鳖，修正后的代價(jià)函數(shù)為：
其中盗棵， 表示哈達(dá)瑪積（Hadamard product）纹因，類(lèi)似于向量的內(nèi)積辐怕； ，當(dāng) 時(shí)僵井，批什，否則 驻债。
Hadamard product：設(shè) 暮的，則
通過(guò)修正后的自編碼器冻辩，以鄰接矩陣 S 為輸入拆祈，以最小化重構(gòu)誤差為約束咙咽，可以將具有相似鄰域結(jié)構(gòu)節(jié)點(diǎn)的 Embedding 向量映射到相鄰位置淤年，即通過(guò) Second-order 捕捉了網(wǎng)絡(luò)的全局結(jié)構(gòu)互亮。
同樣的炊昆，模型既要捕捉網(wǎng)絡(luò)的全局結(jié)構(gòu)凤巨，也要保證網(wǎng)絡(luò)的局部結(jié)構(gòu)敢茁。
我們以 first-order 表示網(wǎng)絡(luò)的局部結(jié)構(gòu)伸刃，使得有連接邊的節(jié)點(diǎn) Embedding 向量相近捧颅，所以代價(jià)函數(shù)為：
為了保證 first-order 和 second-order 相似性碉哑，我們將代價(jià)函數(shù)聯(lián)合起來(lái)扣典，加上正則項(xiàng)后便得到目標(biāo)函數(shù)：
其中激捏， 為超參， 為正則項(xiàng)：
2.4 Optimization
SDNE 使用反向傳播來(lái)更新網(wǎng)絡(luò)參數(shù)图柏，但由于模型高度非線性，參數(shù)空間中可能存在許多局部最優(yōu)任连。因此蚤吹，為了得到全局最優(yōu)，作者使用深度信念網(wǎng)絡(luò)（Deep Belief Network随抠，以下簡(jiǎn)稱 DBN）對(duì)參數(shù)進(jìn)行預(yù)訓(xùn)練裁着。
簡(jiǎn)單介紹一下 DBN，DBN 是由 Hinton 大佬在 2006 年提出的一個(gè)概率生成模型拱她，其由多個(gè)受限玻爾茲曼機(jī)（Restricted Boltzmann Machines二驰，以下簡(jiǎn)稱 RBM）組成。所以在介紹 DBN 之前我們先來(lái)介紹下 RBM秉沼，下圖 RBM 的結(jié)構(gòu)圖：
Restricted Boltzmann Machines其中唬复， 層顯層的狀態(tài)向量， 層為隱藏層的狀態(tài)向量评疗，兩層之間的權(quán)重為 瞧毙，每個(gè)神經(jīng)元都有自己的一個(gè)偏置項(xiàng)有巧，對(duì)隱層而言偏置項(xiàng)為 甜橱，對(duì)顯層而言偏置項(xiàng)為 镊掖。
在 RBM 中归薛，隱層被激活的概率為：
由于是雙向連接崇猫，所以顯層也同樣可以被激活：
以上就是 RBM 的基本構(gòu)造過(guò)程屋厘，并不復(fù)雜溢谤。
我們來(lái)看下工作原理：當(dāng)一條數(shù)據(jù)輸入到顯層時(shí)肝集，RBM 會(huì)根據(jù)公式計(jì)算出每個(gè)隱層被開(kāi)啟的概率浮创，并通過(guò)閾值來(lái)判定是否被激活：
由此便可以得到隱層的每個(gè)神經(jīng)元是否被激活雏掠，給定隱層時(shí)绑青，顯層的計(jì)算方式一致。
了解工作原理后榜配，我們來(lái)看下 RBM 的訓(xùn)練方式：
- 給定的一條數(shù)據(jù)賦值給顯層 ，并計(jì)算出隱層每個(gè)神經(jīng)元被激活的概率 溃论；
- 對(duì)計(jì)算的概率分布進(jìn)行 Gibbs 采樣計(jì)算隱層的輸出值：；
- 利用隱層的狀態(tài)向量重構(gòu)顯層，即通過(guò) 層推導(dǎo)出 巧涧，可以計(jì)算出顯層的每個(gè)神經(jīng)元被激活的概率 缩筛；
- 同樣利用 Gibbs 采樣計(jì)算顯層重構(gòu)值：；
- 重構(gòu)值和原本的輸入值的誤差比較大，所以需要利用反向傳播去更新權(quán)重以縮小誤差识藤；
- 重復(fù)迭代柱彻，直到達(dá)到終止條件惩阶。
DBN 可以視為由多個(gè) RBM 串聯(lián)起來(lái)的結(jié)構(gòu)脐嫂，下圖為最終訓(xùn)練得到的模型：
Structure of DBN在訓(xùn)練時(shí)最下面為第一層結(jié)構(gòu)瑞佩，相鄰兩層構(gòu)成一個(gè) RBM炬丸，必須充分訓(xùn)練 RBM 后才能訓(xùn)練下一個(gè) RBM首启，訓(xùn)練過(guò)程如下圖所示：
train of DBNDBM 是深度學(xué)習(xí)訓(xùn)練中非常有效的參數(shù)初始化方法汁蝶。
我們現(xiàn)在回過(guò)頭來(lái)簡(jiǎn)要的看下 SDNE 的算法：
SDNE Algorithm2.5 Analysis
這一節(jié)主要分析一下新節(jié)點(diǎn)的 Embedding 和訓(xùn)練復(fù)雜度：
- 新節(jié)點(diǎn)：如果新節(jié)點(diǎn) 與現(xiàn)有節(jié)點(diǎn)有連接即纲，那么有連接向量： 具帮，可以利用已有的模型去訓(xùn)練得到新節(jié)點(diǎn)的 Embedding 向量，時(shí)間復(fù)雜度為 ；如果沒(méi)有連接蜂厅，那目前的工作就沒(méi)辦法了～匪凡；
- 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度為 ，其中 n 為節(jié)點(diǎn)數(shù)量掘猿，d 為隱藏層最大維度數(shù)锹雏，c 為網(wǎng)絡(luò)的平均度數(shù)，I 為迭代次數(shù)术奖。
3. Experiments
我們來(lái)看一下 SDNE 在不同數(shù)據(jù)集下礁遵，采用不同評(píng)價(jià)指標(biāo)（MAP、Precision）的性能表現(xiàn)：
imageimageSDNE 在多標(biāo)簽分類(lèi)任務(wù)中的表現(xiàn)：
imageSDNE 在邊預(yù)測(cè)任務(wù)中的表現(xiàn)：
imageSDNE 在不同稀疏程度的數(shù)據(jù)集中的表現(xiàn)：
imageSDNE 的可視化：
imageSDNE 的參數(shù)敏感性：
image4. Conclusion
一句話總結(jié)：SDNE 是一個(gè)具有多層非線性函數(shù)的半監(jiān)督深度學(xué)習(xí)模型采记，其利用 first-order 和 second-order 分別捕捉網(wǎng)絡(luò)的局部結(jié)構(gòu)和全局結(jié)構(gòu)佣耐，使得訓(xùn)練出來(lái)的 Embedding 更具魯棒性，并在多個(gè)真實(shí)數(shù)據(jù)集中獲得良好的表現(xiàn)唧龄。
論文到此就結(jié)束了兼砖，回答一部分看完摘要時(shí)提出的疑問(wèn)：
- 深度模型的 Embedding 還是原來(lái)的那個(gè)輸入矩陣嗎？
先討論這個(gè)問(wèn)題既棺，Embedding 應(yīng)該是 SDNE 中間 層的輸出值讽挟，對(duì)于每一個(gè)節(jié)點(diǎn)其經(jīng)過(guò)多層非線性網(wǎng)絡(luò)后多會(huì)有不同的輸出值。- first-order 如何用作監(jiān)督信息丸冕？second-order 又如何用作非監(jiān)督學(xué)習(xí)耽梅？如何聯(lián)合優(yōu)化？
我是這樣理解的： * second-order 其代價(jià)函數(shù)是輸入的共現(xiàn)矩陣和重構(gòu)的共現(xiàn)矩陣的誤差胖烛，屬于非監(jiān)督學(xué)習(xí)眼姐； * 而 first-order 的代價(jià)函數(shù)是節(jié)點(diǎn)的 Embedding 向量與鄰居節(jié)點(diǎn)的 Embedding 向量的誤差，對(duì)于當(dāng)前節(jié)點(diǎn)而言佩番，其 Label 是鄰居節(jié)點(diǎn)众旗，所以屬于監(jiān)督學(xué)習(xí)； * 聯(lián)合優(yōu)化是指趟畏，把兩個(gè)代價(jià)函數(shù)放在一起計(jì)算總體誤差贡歧，區(qū)別于分開(kāi)訓(xùn)練（還記得哪個(gè)模型是分開(kāi)訓(xùn)練的嗎？）赋秀。- 引入深度模型是為了擬合高度非線形的網(wǎng)絡(luò)利朵，那速度怎么樣？可以用于大規(guī)模網(wǎng)絡(luò)嗎沃琅？
論文沒(méi)寫(xiě)哗咆，大概率速度會(huì)很慢，雖然論文時(shí)間復(fù)雜度為 益眉，每一輪迭代的時(shí)間復(fù)雜度與節(jié)點(diǎn)數(shù)量成線性關(guān)系晌柬，但我覺(jué)得有兩個(gè) Bug： * 論文中指出 d 為隱層最大維度數(shù)（d is the maximum dimension of the hidden layer）姥份，但我覺(jué)得應(yīng)該算成 sum 而不是 max，當(dāng)然也要考慮是否采用 Negative Sampling年碘、Dropout 等優(yōu)化方式澈歉； * SDNE 需要 DBN 進(jìn)行預(yù)訓(xùn)練，這個(gè)時(shí)間也應(yīng)該加上去屿衅，雖然 DBN 的預(yù)訓(xùn)練會(huì)加速 SDNE 的收斂埃难，DBN 本身訓(xùn)練過(guò)程就比較慢； 但 Embedding 通常是離線操作涤久，如果其訓(xùn)練時(shí)間可以接受涡尘，也不一定非要非常快的速度响迂。5. Reference
- 《Structural Deep Network Embedding》
- Upadhyay, Rishabh. (2017). Accent Classification Using Deep Belief Network.
關(guān)注公眾號(hào)跟蹤最新內(nèi)容：**阿澤的學(xué)習(xí)筆記**考抄。 (https://upload-images.jianshu.io/upload_images/21345044-bf1e7097628b4af8.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
