本文同時(shí)發(fā)布于西土城的搬磚工和簡(jiǎn)書
論文鏈接：Max-Margin DeepWalk: Discriminative Learning of Network Representation
引用格式：
Cunchao Tu, Weicheng Zhang, Zhiyuan Liu, Maosong Sun. Max-Margin DeepWalk: Discriminative Learning of Network Representation. International Joint Conference on Artificial Intelligence (IJCAI 2016).
標(biāo)題：Max-Margin DeepWalk: Discriminative Learning of Network Representation
來(lái)源：IJCAI 2016
問(wèn)題：
作者提出,DeepWalk作為一種典型的學(xué)習(xí)社交網(wǎng)絡(luò)節(jié)點(diǎn)向量表示的方法,在一些任務(wù)上缺乏足夠的區(qū)分能力。故作者在本文提出Max-Margin(最大間隔)DeepWalk方法,在最大間隔分類器的影響下,原先學(xué)習(xí)到的節(jié)點(diǎn)向量的區(qū)分能力有所增強(qiáng)。
背景簡(jiǎn)介：
| 相關(guān)工作 | 解決問(wèn)題 |
|---|---|
| DeepWalk | 基于隨機(jī)游走和Skip-Gram學(xué)習(xí)圖節(jié)點(diǎn)表示 |
| 矩陣分解形式的DeepWalk | 證明DeepWalk等價(jià)于矩陣分解,分解結(jié)果包含內(nèi)容屬性 |
| Max-Margin DeepWalk | 引入SVM分類器增強(qiáng)前述模型習(xí)得向量的區(qū)分能力 |
主要方法：
基于矩陣分解的DeepWalk模型（MFDW）
再提及該方法前需要對(duì)DeepWalk進(jìn)行簡(jiǎn)單的介紹，該方法的具體描述見《DeepWalk: Online Learning of Social Representations》DeepWalk大致過(guò)程如下：隨機(jī)游走遍歷某節(jié)點(diǎn)的鄰節(jié)點(diǎn)，得到一個(gè)節(jié)點(diǎn)序列，再借鑒skip-gram的原理，由單個(gè)節(jié)點(diǎn)預(yù)測(cè)前后序列，學(xué)習(xí)得到該節(jié)點(diǎn)的向量表示。在這其中利用Hierarchical Softmax減小搜索空間。
基于矩陣分解的DeepWalk具體可以參考《Network Representation Learning with Rich Text Information》。簡(jiǎn)單概括的話，作者通過(guò)數(shù)學(xué)推導(dǎo)，證明DeepWalk的學(xué)習(xí)過(guò)程類似傳統(tǒng)主題模型矩陣分解的操作。示意圖如下：
其中M表示圖的鄰接矩陣,W表示節(jié)點(diǎn)的向量表示矩陣,(M∈Rn×k ,n表示節(jié)點(diǎn)個(gè)數(shù),k表示節(jié)點(diǎn)向量維度),T矩陣根據(jù)作者推導(dǎo),類似主題模型矩陣分解的處理思路,作者認(rèn)為該矩陣反應(yīng)了節(jié)點(diǎn)本身的內(nèi)容特征。易知,HT∈Rn×k .最后就可以將之后將W與HT同一行的向量拼接在一起，作為2k維的向量表示節(jié)點(diǎn)屬性。
最大間隔DeepWalk模型（MMDW）
基于最大間隔思想設(shè)計(jì)的分類器中,最為有名的即為SVM分類器,作者使用On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines中提出的多類SVM分類器。該多類分類器的關(guān)鍵在于構(gòu)造W參數(shù)矩陣。(W∈RL×K)的矩陣,L表示label個(gè)數(shù),K表示特征向量維度)在比較時(shí)可以將特征向量x依次與W矩陣每一行參數(shù)點(diǎn)乘,根據(jù)值的大小判斷所屬類別類別。相應(yīng)的優(yōu)化函數(shù)如下：
但是如果只用上述SVM分類器做分類.對(duì)節(jié)點(diǎn)向量本身不產(chǎn)生影響。基于此,作者將前面MFDW的訓(xùn)練過(guò)程與這里SVM分類器的訓(xùn)練過(guò)程,利用節(jié)點(diǎn)向量x作為紐帶結(jié)合起來(lái)，具體方法是利用biased gradient在節(jié)點(diǎn)向量學(xué)習(xí)時(shí),傳遞SVM分類器參數(shù)的變化情況。這樣將節(jié)點(diǎn)在SVM分類器中反應(yīng)的label屬性融合到特征向量中,并且由于SVM分類器本身區(qū)分能力強(qiáng)的特點(diǎn),提高了特征向量的區(qū)分能力。經(jīng)過(guò)上述過(guò)程后,優(yōu)化函數(shù)如下：
相關(guān)工作：
參數(shù)學(xué)習(xí)：
參數(shù)學(xué)習(xí)是模型訓(xùn)練的重要部分。本文由于是SVM分類器與MFDW模型的結(jié)合,模型的迭代更新也自然分為這兩部分。在每一輪次中,針對(duì)某模型的參數(shù)進(jìn)行學(xué)習(xí)更新時(shí),需要保證另一模型的參數(shù)不變。
對(duì)于SVM分類器中的分類器參數(shù)W和松弛變量ζ 而言,學(xué)習(xí)思路參考Crammer&Singer提出的方法,并結(jié)合Keerthi在2008年提出的解決序列對(duì)偶問(wèn)題的方法。
對(duì)于節(jié)點(diǎn)特征向量矩陣X和內(nèi)容矩陣Y的迭代更新,由于節(jié)點(diǎn)向量矩陣X的的節(jié)點(diǎn)特征向量同時(shí)在兩個(gè)模型中出現(xiàn)。那么在優(yōu)化X,Y的時(shí)候,我們考慮加入偏置,使節(jié)點(diǎn)特征向量xi朝著前面最大間隔分類器優(yōu)化的方向迭代更新。即在求取前述LDW關(guān)于xi的偏導(dǎo)時(shí),引入下面的bias因子：
實(shí)驗(yàn)結(jié)果：
由于實(shí)驗(yàn)結(jié)果較多，且部分涉及模型本身性能的分析,這里重點(diǎn)說(shuō)明自己感興趣的部分：
節(jié)點(diǎn)區(qū)分能力圖示：
左圖是傳統(tǒng)DeepWalk的方法,右圖表示本文提出的DeepWalk改進(jìn)模型,從圖中可以看出，由于結(jié)合最大間隔模型，本文模型的區(qū)分能力更強(qiáng)：
模型對(duì)語(yǔ)義信息的把握：
下表反應(yīng)的是原模型與作者改進(jìn)模型在某論文數(shù)據(jù)集上進(jìn)行聚類得到的部分結(jié)果對(duì)比圖。該輪文數(shù)據(jù)集主要包含論文的基本信息及相互引用的情況?？梢钥闯?由于隱含的結(jié)合了label信息在內(nèi),本文所提出的MMDW模型在主題層面對(duì)于數(shù)據(jù)的劃分相比之前的模型，更為準(zhǔn)確。
簡(jiǎn)評(píng)：
選擇這篇論文主要是由于經(jīng)過(guò)一段時(shí)間的調(diào)研,感覺目前學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的embedding表示的方法層出不窮。自己感覺在研究過(guò)程中,如果不能結(jié)合具體問(wèn)題分析具體特征,很難有好的論文創(chuàng)新點(diǎn)。這篇論文就是作為發(fā)表在今年IJCAI上的論文,是一個(gè)將其他節(jié)點(diǎn)屬性信息融合到節(jié)點(diǎn)向量學(xué)習(xí)的很好的例子。具體說(shuō)來(lái),本文為有以下幾點(diǎn)值得學(xué)習(xí)：
創(chuàng)新點(diǎn)突出：
DeepWalk模型是在2014年提出的,在2015年,有人證明DeepWalk可以視作矩陣分解問(wèn)題,并得出分解得到的矩陣包含圖節(jié)點(diǎn)的向量表示和內(nèi)容特征。而最大間隔方法之前在主題模型、分詞等NLP傳統(tǒng)領(lǐng)域使用較多,這里,作者能將該方法遷移用于改善向量區(qū)分能力。這一創(chuàng)新之前無(wú)人涉及，也取得了很好的效果。
選擇選擇得當(dāng)：
本文提出模型中需要用到與節(jié)點(diǎn)內(nèi)容屬性相關(guān)的特征。針對(duì)這一情況,本文在實(shí)驗(yàn)中,使用的主要數(shù)據(jù)包括Cora、Citeseer、Wiki。前兩個(gè)數(shù)據(jù)集包括論文基本信息及其引用情況。Wiki中如果將url視作節(jié)點(diǎn),相互引用的wiki之間視作存在關(guān)系對(duì),我們就可以將其轉(zhuǎn)換為社交關(guān)系網(wǎng)絡(luò)來(lái)處理。這些數(shù)據(jù)的文本部分包含豐富的語(yǔ)義信息,可以有效說(shuō)明論文模型的適用性和優(yōu)勢(shì)。
基礎(chǔ)知識(shí)扎實(shí)：
文中利用文本特征驅(qū)動(dòng)節(jié)點(diǎn)向量訓(xùn)練時(shí)，采用了biased gradient的方法，由于暫時(shí)沒(méi)有查到相關(guān)資料，這里可能這是作者獨(dú)立提出來(lái)的。該方法從算法角度并不復(fù)雜，但卻可以有效的改變訓(xùn)練方向,加入SVM學(xué)習(xí)到的相關(guān)信息,從而“引導(dǎo)”節(jié)點(diǎn)向量的迭代更新。該方法的提出以及文中大量關(guān)于SVM模型的分析推導(dǎo)過(guò)程均顯示出了作者該領(lǐng)域不俗的功力。
