需要論文的朋友可以后臺(tái)私信我獲取

前言

上一篇文章給大家?guī)?lái)了Graph Embedding技術(shù)中的代表算法Deepwalk，今天給大家介紹graph embedding又一代表算法——LINE,LINE(large-scale information Network，大規(guī)模信息網(wǎng)絡(luò))致力于將大型的信息網(wǎng)絡(luò)嵌入到低維的向量空間中，且該模型適用于任何類型(有向、無(wú)向亦或是有權(quán)重)的信息網(wǎng)絡(luò)。并提出了一種解決經(jīng)典隨機(jī)梯度下降限制的邊緣采樣算法，提高了算法的有效性和效率,且在應(yīng)用方面更廣。總結(jié)下來(lái)LINE有以下幾個(gè)特點(diǎn)或者優(yōu)勢(shì)：

(1)適用廣，適合任意類型的網(wǎng)絡(luò)，不論是有向圖還是無(wú)向圖還是帶權(quán)圖。

(2)信息全，目標(biāo)函數(shù)(objective function)同時(shí)考慮了網(wǎng)絡(luò)局部特征和全局特征。

(3)效率高，提出一種邊采樣的算法，可以很好地解決SGD的效率問(wèn)題。

(4)時(shí)間快，提出了十分高效網(wǎng)絡(luò)表示方法，在小時(shí)范圍內(nèi)的單機(jī)節(jié)點(diǎn)上學(xué)習(xí)百萬(wàn)級(jí)頂點(diǎn)網(wǎng)絡(luò)的表示。

下面一下來(lái)看看這篇文章吧。

重要定義

了解LINE算法之前需要了解一下論文里面的幾個(gè)重要概念。

信息網(wǎng)絡(luò)

信息網(wǎng)絡(luò)定義為 G=(V,E)其中V 是頂點(diǎn)集合，頂點(diǎn)表示數(shù)據(jù)對(duì)象， E 是頂點(diǎn)之間的邊緣的集合，每條邊表示兩個(gè)數(shù)據(jù)對(duì)象之間的關(guān)系。每條邊e(E)表示為有序?qū)=(u,v)，并且與權(quán)重Wuv>0相關(guān)聯(lián)，權(quán)重表示關(guān)系的強(qiáng)度。如果G是無(wú)向的，我們有 (u,v) !=(v,u)和Wuv=Wvu ；如果G是有向的，我們有(u,v) !=(v,u) 和Wuv!=Wvu,一般情況下我們認(rèn)為權(quán)重非負(fù)。

一階相似性

網(wǎng)絡(luò)中的一階相似性是兩個(gè)頂點(diǎn)之間的局部點(diǎn)對(duì)的鄰近度。對(duì)于有邊(u,v) 連接的每對(duì)頂點(diǎn)，該邊的權(quán)重Wuv 表示u 和v之間的一階相似性，如果在u 和v之間沒(méi)有觀察到邊，他們的一階相似性為0。

二階相似性

二階相似性指的是一對(duì)頂點(diǎn)之間的接近程度(u,v) 在網(wǎng)絡(luò)中是其鄰域網(wǎng)絡(luò)結(jié)構(gòu)之間的相似性。數(shù)學(xué)上，讓

表示一階附近與所有其他的頂點(diǎn)，那么u和v之間的二階相似性由pu和pv之間的相似性來(lái)決定。如果沒(méi)有一個(gè)頂點(diǎn)同時(shí)和u與v 連接，那么u和v 的二階相似性是0。

大規(guī)模信息網(wǎng)絡(luò)嵌入

給定大網(wǎng)絡(luò) G=(V,E)，大規(guī)模信息網(wǎng)絡(luò)嵌入是將每個(gè)頂點(diǎn)v(V) 表示為低維空間(d)中的向量，學(xué)習(xí)一個(gè)函數(shù):

其中d<<

以上圖為例：一階相似性表示兩個(gè)頂點(diǎn)直接相連，比如6和7兩個(gè)頂點(diǎn)，它們就是相似的；二階相似表示兩個(gè)兩個(gè)頂點(diǎn)有相同的連接頂點(diǎn)，比如5和6雖然不直接連接，但是同時(shí)和1,2,3,4相連，所以5和6是相似的，這和協(xié)同過(guò)濾是不是很像，說(shuō)白了就是根據(jù)圖結(jié)構(gòu)來(lái)表達(dá)頂點(diǎn)間的相似度。

算法介紹

一階相似性

對(duì)每個(gè)無(wú)向邊(i,j)，定義頂點(diǎn)vi和vj的聯(lián)合概率分布為：

ui(d維)是頂點(diǎn)vi的低維向量表示，為保持其一階相似性，p(,)為空間VxV上的一個(gè)分布：

W為i，j兩點(diǎn)間邊權(quán)重總和。為了求解一階相似，直接方法是最小化以下的目標(biāo)函數(shù)：

d(.,.)為兩種分布之間的距離，我們選擇盡量減少兩個(gè)概率分布的KL 散度。將d(,)替換為 KL 散度并省略一些常數(shù)，我們得到︰

注意一點(diǎn)：一階相似度僅適用于無(wú)向圖,而不適用于有向圖。

二階相似性

二階相似性適用于有向或者無(wú)向圖(比如Deepwalk里面就用到了有向的二階相似性)，二階相似性假定與其他頂點(diǎn)共享鄰居頂點(diǎn)的兩個(gè)點(diǎn)彼此相似(無(wú)向有向均可)，一個(gè)向量u和u'分別表示頂點(diǎn)本身和其他頂點(diǎn)的特定“上下文”，意為二階相似。對(duì)于每個(gè)有向邊(i,j)，我們首先定義由生成“上下文”的概率：

其實(shí)這和word2vec里面的公式是一樣的代表一個(gè)條件分布，我們?nèi)為研究對(duì)象，p(,vi)，降維之后使其接近與經(jīng)驗(yàn)分布p2。因此最小化以下目標(biāo)函數(shù)：

d(,)和一階里面定義一致，表示兩個(gè)分布的距離，λi來(lái)表示網(wǎng)絡(luò)中頂點(diǎn)i的聲望(可以理解為權(quán)重),在本文中即是頂點(diǎn)i的度數(shù)，因此二階相似性的計(jì)算公式為：

最后將得到一階相似向量和二階相似向量直接拼接在一起得到最終的節(jié)點(diǎn)向量。

模型優(yōu)化

由于O2的計(jì)算代價(jià)十分的昂貴，因此目標(biāo)函數(shù)優(yōu)化時(shí)使用了負(fù)采樣方法，為每條邊指定了一個(gè)目標(biāo)函數(shù)：

注：

就是sigmoid函數(shù)，K表示負(fù)采樣邊的個(gè)數(shù)，

其中dv是頂點(diǎn)v的出度(和詞向量里面的幾乎是一樣的)。

上述函數(shù)又可通過(guò)采用異步隨機(jī)梯度下降算法(ASGD)來(lái)優(yōu)化。每一步中，ASGD算法對(duì)小批量邊緣進(jìn)行抽樣，然后更新模型參數(shù)。但是這也帶來(lái)一個(gè)問(wèn)題，如果我們根據(jù)小權(quán)重的邊緣選擇較大的學(xué)習(xí)率，那么大權(quán)重的邊上就會(huì)出現(xiàn)梯度爆炸，如果我們根據(jù)具有較大權(quán)重的邊選擇學(xué)習(xí)小的速率，那么小權(quán)重上的邊就會(huì)出現(xiàn)梯度消失。因此邊緣采樣同樣要優(yōu)化。從起始邊緣采樣并將采樣的邊緣作為二進(jìn)制邊緣，其中采樣概率與原始邊緣的權(quán)重成比例。

實(shí)驗(yàn)分析與展示

與Deepwalk中的實(shí)驗(yàn)類似。

數(shù)據(jù)集

• 語(yǔ)言網(wǎng)絡(luò)：基于英文維基百科頁(yè)面構(gòu)建詞共同網(wǎng)絡(luò)
• 社交網(wǎng)絡(luò)：Flickr、Youtube
• 引用網(wǎng)絡(luò)：作者和論文引文網(wǎng)

算法

• GF
• Deepwalk
• LINE-SGD，
• LINE
• LINE (1st+2nd):

參數(shù)設(shè)置

對(duì)于所有方法，隨機(jī)梯度下降的小批量大小設(shè)置為1；以起始值p0= 0.025和pt= p0(1-t)設(shè)定學(xué)習(xí)速度， T是小批量或邊緣樣品的總數(shù)；為了公平比較，語(yǔ)言網(wǎng)絡(luò)嵌入的維度被設(shè)置為200；而其他網(wǎng)絡(luò)中，默認(rèn)設(shè)置為128；其他的默認(rèn)參數(shù)設(shè)置包括：LINE的負(fù)采樣k=5，樣本總數(shù)T=100億(LINE),T=200億(GF)，窗口大小win = 10，步行長(zhǎng)度t = 40，對(duì)于Deep Walk，每頂點(diǎn)行走y= 40；所有的嵌入向量最終通過(guò)設(shè)置 ||w||2 = 1進(jìn)行歸一化。

語(yǔ)言網(wǎng)絡(luò)

評(píng)估學(xué)習(xí)嵌入的有效性：詞類比和文檔分類。

詞類比：給定一個(gè)單詞對(duì)(a,b)和一個(gè)單詞c，該任務(wù)旨在找到一個(gè)單詞d，使得c

和d之間的關(guān)系類似于a和b之間的關(guān)系。

由實(shí)驗(yàn)結(jié)果可看出LINE(2nd)優(yōu)于其他模型，相比于其他算法，LINE的二階相似性可以更好的衡量詞在空間中的關(guān)系。這個(gè)算法我沒(méi)有使用過(guò)，對(duì)于這個(gè)實(shí)驗(yàn)結(jié)果我表示懷疑。

由上表可以看出LINE模型在文檔分類上效果強(qiáng)于其他模型。

上表比較一階相似性和二階相似性之間的效果。由表可以看出一階相似體現(xiàn)的是與目標(biāo)詞句法和語(yǔ)義相關(guān)詞的混合。二階相似返回的是目標(biāo)詞對(duì)應(yīng)的所有語(yǔ)義相關(guān)詞。

社交網(wǎng)絡(luò)

與語(yǔ)言網(wǎng)絡(luò)相比，社交網(wǎng)絡(luò)更加稀缺；將每個(gè)節(jié)點(diǎn)分配到一個(gè)或多個(gè)社區(qū)的多標(biāo)簽分類任務(wù)來(lái)評(píng)估頂點(diǎn)嵌入；隨機(jī)抽取不同百分比的頂點(diǎn)進(jìn)行訓(xùn)練，其余用于評(píng)估。結(jié)果在10次不同運(yùn)行中進(jìn)行平均。下面是在Flickr和Youtube數(shù)據(jù)集上的結(jié)果展示。

引用網(wǎng)絡(luò)

通過(guò)GF和LINE兩種方法對(duì)引用網(wǎng)絡(luò)進(jìn)行評(píng)估。還通過(guò)多標(biāo)簽分類任務(wù)評(píng)估頂點(diǎn)嵌入。 我們選擇7個(gè)流行會(huì)議，包括AAAI，CIKM，ICML，KDD，NIPS，SIGIR和WWW作為分類類別。

訓(xùn)練結(jié)果

模型效果 &網(wǎng)絡(luò)稀疏度

參數(shù)分析

從低維向量維度個(gè)訓(xùn)練樣本數(shù)來(lái)展示不同模型效果，總體來(lái)說(shuō)LINE(2nd)好于其他。

穩(wěn)定性

這些圖說(shuō)明了一點(diǎn)，LINE算法很好，很穩(wěn)定，好于Deepwalk等同類型算法。

總結(jié)

看這篇論文給我一種感覺(jué)是有一些很好的地方比如一階、二階相似性等，但是效果不應(yīng)該這么大，可能是有一些工程經(jīng)驗(yàn)文章沒(méi)有說(shuō)或者是我還是體會(huì)到，總結(jié)下來(lái)就是LINE是以圖的結(jié)構(gòu)(邊)來(lái)構(gòu)造樣本，并沒(méi)有Deepwalk里面隨機(jī)游走等方式構(gòu)造序列，這種思想還是有很大的創(chuàng)新性的。

總結(jié)

以上是生活随笔為你收集整理的d3设置line长度_Graph Embedding之LINE算法解读的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。