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