原文：LINE:Large-scale Information Network Embedding
本文提出一種新的network embedding model：LINE.能夠處理大規(guī)模的各式各樣的網(wǎng)絡窘拯，比如：有向圖闷沥、無向圖邀跃、有權重圖鞍帝、無權重圖.
文中指出對于network embedding問題脆炎，需要保留local structure和global structure，分別對應first-order proximity和second-order proximity.
first-order proximity:兩個節(jié)點之間相連的邊權重越大，這兩個節(jié)點越相似.
second-order proximity:兩個節(jié)點相同的neighbors越多烟央，這兩個節(jié)點越相似.
節(jié)點6和7應該是比較相似的，因為它們有權重較大的邊相連(high first-order proximity).節(jié)點5和6也應該是比較相似的歪脏，因為它們share了很多共同的neighbors(high second-order proximity).
因此希望提出一種方式疑俭，通過考慮second-order proximity來彌補first-order proximity的稀疏，并且更好的保留network的global structure.本文提出了一種objective同時保留了first-order proximity和second-order proximity.
對于objective的優(yōu)化也是困難的婿失，比較常見的方式是通過SGD.然后在很多情況下钞艇，SGD是有問題的，因為帶權圖的權重方差比較大(有的邊權很小豪硅，有的邊權很大哩照，會造成梯度爆炸).本文提出了一種新的邊采樣方法，以正比于邊權的概率進行邊采樣懒浮，之后在模型更新中將邊看做是binary的(0,1)飘弧，這樣邊權就不會影響梯度了.
LINE對有向圖、無向圖砚著、有權重圖次伶、無權重圖都是有效的.
Deepwalk并沒有明確的objective function，直觀上來看它主要考慮second-order proximity.
DeepWalk的策略類似于DFS赖草，而LINE類似于BFS学少，這對于second-order proximity是一種更合理的方式.
DeepWalk只適用于無權重圖，而LINE可以用于有權重圖和無權重圖.
Problem Definition
1)Information Network
G=(V,E) V是節(jié)點集合秧骑，E是邊集合.e∈E是一個有序的節(jié)點對版确，e=(u,v)，并有一個邊權Wuv>0.
如果G是無向圖乎折，那么有(u,v)=(v,u)以及Wuv=Wvu;如果G是有向圖绒疗，那么有(u,v)≠(v,u)以及Wuv≠Wvu.
2)First-order Proximity(local network structure)
對于節(jié)點u,v，如果它們之間有一條邊(u,v)骂澄，那么邊權Wuv表示了u和v之間的first-order proximity.如果它們之間沒有邊吓蘑，那么first-order proximity就為0.
3)Second-order Proximity(global network structure)
定義Pu=(Wu,1，...坟冲，Wu,|V|)表示u對于其他所有節(jié)點的first-order proximity.
u和v之間的second-order proximity由pu和pv之間的相似度來決定.如果沒有節(jié)點同時指向u和v或者同時被u和v所指向磨镶，那么u和v之間的second-order proximity為0.
4)Large-scale Information Network Embedding
Given G=(V,E)
Goal 將所有v∈V在d維空間進行表示.即學習一個函數(shù)
LINE: LARGE-SCALE INFORMATION NETWORK EMBEDDING
一個比較好的embedding model必須有下面這些要求：
?能夠同時保持節(jié)點之間的first-order proximity和second-order proximity.
?能夠在大規(guī)模的network上進行應用.
?能夠在各種類型邊的network上進行應用，包括有向圖健提、無向圖琳猫、有權重圖、無權重圖.
本文提出的LINE模型同時滿足上述三點.
Model Description
先介紹LINE模型分別考慮first-order proximity和second-order proximity私痹，然后通過一種方式將兩者結合起來.
1.LINE with First-order Proximity
這種方法只對無向圖有效脐嫂，無法應用于有向圖.
對first-order proximity建模统刮，對于邊(i,j)，定義節(jié)點vi和vj的聯(lián)合概率分布:
其中
是節(jié)點vi的representation vector.
上述joint distribution是定義在空間V*V上的(輸入是兩個節(jié)點)账千，概率越大表示兩個節(jié)點越相似.
這個分布的經(jīng)驗概率為
也就是i,j之間的邊權/network上所有的邊權之和.
最小化以下目標函數(shù):
其中d(.,.)表示兩個分布的距離(也就是說讓Pmodel逼近Pdata侥蒙，即讓模型分布去逼近經(jīng)驗分布，這和機器學習其他算法的思想是一樣的).
這里需要通過一種方式來衡量兩個概率分布之間的接近程度匀奏，本文選擇KL-divergence.將KL-divergence(這里的KL-divergence用的是經(jīng)驗分布在前鞭衩，模型分布在后，這一點和MLE中是一樣的)帶入(2)式中娃善，有
上述推導的過程中醋旦，需要始終明確一點，最小化目標函數(shù)是通過調整Pmodel中的presentation vector來實現(xiàn)的.最終得到
通過找到最優(yōu)的
(各節(jié)點的presentation vector)來最小化目標函數(shù)(3)会放，即可得到network的embedding(first-order proximity).
2.LINE with Second-order Proximity
second-order proximity對有向圖和無向圖都是可行的.
考慮有向圖(無向圖的邊可以看作兩條方向相反權重相同的有向邊)饲齐，在second-order proximity中，每個節(jié)點有兩個role:
?作為節(jié)點本身
?作為其他節(jié)點的context
通過兩個vector來表示每個節(jié)點的兩個角色咧最，對于節(jié)點vi捂人，ui用于表示作為節(jié)點本身，ui'用于表示節(jié)點作為其他節(jié)點的context.
對于有向邊(i,j)矢沿，定義vj作為context的概率(關于vi).
|V|為節(jié)點總數(shù).其實就是對于vi滥搭，各節(jié)點為其context的概率(分母可以看作是歸一化因子).如果p2(?|v1)和p2(?|v2)的概率分布是相似的(即v1和v2的context相似)，那么這兩個節(jié)點就second-order proximity而言是相似的.
同樣捣鲸，讓Pmodel p2(·|vi)去逼近經(jīng)驗分布p~(·|vi)瑟匆，也就是最小化下面的目標函數(shù):
d(.,.)表示兩個分布間的距離.由于network中各節(jié)點的重要性不同，引入λi來表示各節(jié)點的重要性栽惶，λi可以通過節(jié)點的degree來衡量愁溜，或者通過PageRank等算法來獲得節(jié)點重要性的表示.
經(jīng)驗分布為
其中wij表示邊(i,j)的權重，di是節(jié)點v的出度.
也就是
其中N(i)表示vi的out-neighbors.本文中令λi=di.同樣使用KL-divergence來衡量兩個分布的距離.
上述推導中要明確外厂，調整的是p2中的ui和ui'來使目標函數(shù)最小.
最終有目標函數(shù)
通過learning ui序列和ui'序列來最小化目標函數(shù)冕象，則可以獲得network的embedding(second-order proximity)，也就是 .
3)Combining first-order and second-order proximities
為了使network embedding同時考慮到first-order proximity和second-order proximity汁蝶，先分別train獲得關于first-order proximity的embedding和關于second-order proximity的embedding渐扮，然后將兩者組合在一起(將兩個向量拼接到一起，再做reweight).
Model Optimization
1)negative sampling
對于式(6)掖棉，在計算p2(?|vi)時墓律，式(4)中分母計算量很大，于是通過負采樣的優(yōu)化方法.采樣K條負邊幔亥，learning的時候只更新當前考慮的邊(即(4)中的分子)和K條負邊耻讽，其余的邊不更新，這樣有效提高了計算速度.此時的目標函數(shù)為:
第一項為當前考慮的邊紫谷，第二項考慮采樣到的K條負邊.對于每條負邊齐饮，一個節(jié)點為當前考慮的節(jié)點，另一個節(jié)點由采樣得到笤昨，所以采樣負邊的本質是在采樣節(jié)點(當前考慮的節(jié)點和采樣得到的節(jié)點確定了一條負邊).每個節(jié)點被采樣的概率為Pn(v)祖驱，其中
v為當前考慮的節(jié)點，dv為節(jié)點v的出度(3/4由經(jīng)驗給出).
用異步隨機梯度下降(ASGD)來優(yōu)化式(7)瞒窒，O2對ui求梯度有
可以看到梯度中包含了邊權wij捺僻，當邊權之間有著較高的方差時，比如說有的權重很大崇裁，有的權重很小匕坯，這時候學習率的設置會出現(xiàn)困難.如果根據(jù)小權重的邊選擇大的學習率，那么此時對于大權重的邊會出現(xiàn)梯度爆炸;如果根據(jù)大權重的邊選擇小的學習率拔稳，那么此時對于小權重的邊會出現(xiàn)梯度過小.對于這個問題葛峻，使用邊采樣來解決.
2)Edge Sampling
一種簡單的想法是將權重為w的邊拆成w條binary的邊，但是這樣做對于那些權重較大的邊巴比，很占據(jù)很大的存儲空間.因此考慮一種更加合理的方式术奖，對原來的邊進行采樣，采樣到的邊認為是binary的轻绞，并且每條邊被采樣的概率正比于原來的權重.
接下來說明如何進行采樣采记，W=(w1,w2,...,w|E|)表示所有邊權組成的序列.計算
之后再[0,Wsum]區(qū)間產(chǎn)生隨機數(shù)，隨機數(shù)落在哪條邊權對應的區(qū)間內政勃，就采樣那條邊.這種做法在總邊數(shù)很多的時候唧龄，比較費時，因此考慮一種更優(yōu)的方式.
這里使用alias table method奸远，時間復雜度為O(1).(關于alias table method的資料網(wǎng)上有很多)
LINE model實際應用中可能遇到的問題
1)Low degree vertices
一些節(jié)點的neighbors很少既棺，很難進行精確的presentation.本文對于這些節(jié)點添加second-order neighbors.節(jié)點vi到second-order neighbor j的weight為:
2)New vertices
對于新的節(jié)點如何對它進行presentation.對于一個新節(jié)點i，如果和它連接的已有節(jié)點是已知的懒叛，那么可以知道對于已知節(jié)點的經(jīng)驗分布p1(·,vi)和p2(·|vi).那么最小化目標函數(shù):
優(yōu)化的過程中援制，保持原有已知節(jié)點的embedding不動，更新新節(jié)點的embedding.
