本文轉(zhuǎn)載自【Graph Embedding】LINE：算法原理，實(shí)現(xiàn)和應(yīng)用 - 淺夢(mèng)的文章 - 知乎
https://zhuanlan.zhihu.com/p/56478167
之前介紹過(guò)DeepWalk摩骨，DeepWalk使用DFS隨機(jī)游走在圖中進(jìn)行節(jié)點(diǎn)采樣鲫惶，使用word2vec在采樣的序列學(xué)習(xí)圖中節(jié)點(diǎn)的向量表示扣囊。ref: DeepWalk
LINE也是一種基于鄰域相似假設(shè)的方法，只不過(guò)與DeepWalk使用DFS構(gòu)造鄰域不同的是，LINE可以看作是一種使用BFS構(gòu)造鄰域的算法唤殴。此外哺窄，LINE還可以應(yīng)用在帶權(quán)圖中(DeepWalk僅能用于無(wú)權(quán)圖)捐下。
LINE 原文： [1503.03578] LINE: Large-scale Information Network Embedding (arxiv.org)
之前還提到不同的graph embedding方法的一個(gè)主要區(qū)別是對(duì)圖中頂點(diǎn)之間的相似度的定義不同，所以先看一下LINE對(duì)于相似度的定義萌业。
LINE算法原理
一種新的相似度定義
first-order proximity（一階相似度）
1階相似度用于描述圖中成對(duì)頂點(diǎn)之間的局部相似度坷襟，形式化描述為若 ,
之間存在直連邊，則邊權(quán)
即為兩個(gè)頂點(diǎn)的相似度生年，若不存在直連邊婴程，則1階相似度為0。 如上圖抱婉，6和7之間存在直連邊档叔，且邊權(quán)較大桌粉，則認(rèn)為兩者相似且1階相似度較高，而5和6之間不存在直連邊衙四，則兩者間1階相似度為0铃肯。
second-order proximity
僅有1階相似度就夠了嗎？顯然不夠传蹈，如上圖押逼，雖然5和6之間不存在直連邊，但是他們有很多相同的鄰居頂點(diǎn)(1,2,3,4)惦界，這其實(shí)也可以表明5和6是相似的挑格，而2階相似度就是用來(lái)描述這種關(guān)系的。形式化定義為沾歪，令 表示頂點(diǎn)
與所有其他頂點(diǎn)間的1階相似度漂彤，則
與
的2階相似度可以通過(guò)
和
的相似度表示。若
與
之間不存在相同的鄰居頂點(diǎn)瞬逊，則2階相似度為0显歧。
優(yōu)化目標(biāo)
1st-order
對(duì)于每一條無(wú)向邊，定義頂點(diǎn)
和
之間的聯(lián)合概率為：
确镊，
為頂點(diǎn)
的低維向量表示士骤。（可以看作一個(gè)內(nèi)積模型，計(jì)算兩個(gè)item之間的匹配程度）
同時(shí)定義經(jīng)驗(yàn)分布蕾域，拷肌，
優(yōu)化目標(biāo)為最小化:
是兩個(gè)分布的距離，常用的衡量?jī)蓚€(gè)概率分布差異的指標(biāo)為KL散度旨巷，使用KL散度并忽略常數(shù)項(xiàng)后有
1st order 相似度只能用于無(wú)向圖當(dāng)中巨缘。
2nd-order
這里對(duì)于每個(gè)頂點(diǎn)維護(hù)兩個(gè)embedding向量，一個(gè)是該頂點(diǎn)本身的表示向量采呐，一個(gè)是該點(diǎn)作為其他頂點(diǎn)的上下文頂點(diǎn)時(shí)的表示向量珠十。
對(duì)于有向邊张遭，定義給定頂點(diǎn)
條件下访娶，產(chǎn)生上下文(鄰居)頂點(diǎn)
的概率為
其中
優(yōu)化目標(biāo)為：
其中
優(yōu)化技巧
Negative sampling
由于計(jì)算2階相似度時(shí)仰冠，softmax函數(shù)的分母計(jì)算需要遍歷所有頂點(diǎn)，這是非常低效的蝶糯，論文采用了負(fù)采樣優(yōu)化的技巧洋只，目標(biāo)函數(shù)變?yōu)椋?br>
Edge Sampling
注意到我們的目標(biāo)函數(shù)在log之前還有一個(gè)權(quán)重系數(shù)，在使用梯度下降法優(yōu)化參數(shù)時(shí)识虚，
會(huì)直接乘在梯度上肢扯。如果圖中的邊權(quán)方差很大，則很難選擇一個(gè)合適的學(xué)習(xí)率舷礼。若使用較大的學(xué)習(xí)率那么對(duì)于較大的邊權(quán)可能會(huì)引起梯度爆炸鹃彻，較小的學(xué)習(xí)率對(duì)于較小的邊權(quán)則會(huì)導(dǎo)致梯度過(guò)小。
對(duì)于上述問(wèn)題妻献，如果所有邊權(quán)相同，那么選擇一個(gè)合適的學(xué)習(xí)率會(huì)變得容易团赁。這里采用了將帶權(quán)邊拆分為等權(quán)邊的一種方法育拨，假如一個(gè)權(quán)重為的邊，則拆分后分為
個(gè)權(quán)重為1的邊欢摄。這樣可以解決學(xué)習(xí)率選擇的問(wèn)題熬丧，但是由于邊數(shù)的增長(zhǎng)，存儲(chǔ)的需求也會(huì)增加怀挠。
另一種方法則是從原始的帶權(quán)邊中進(jìn)行采樣析蝴，每條邊被采樣的概率正比于原始圖中邊的權(quán)重，這樣既解決了學(xué)習(xí)率的問(wèn)題绿淋，又沒(méi)有帶來(lái)過(guò)多的存儲(chǔ)開(kāi)銷闷畸。
這里的采樣算法使用的是Alias算法，Alias是一種 時(shí)間復(fù)雜度的離散事件抽樣算法吞滞。具體內(nèi)容可以參考 https://zhuanlan.zhihu.com/p/54867139
其他問(wèn)題
低度數(shù)頂點(diǎn)
對(duì)于一些頂點(diǎn)由于其鄰接點(diǎn)非常少會(huì)導(dǎo)致embedding向量的學(xué)習(xí)不充分佑菩，論文提到可以利用鄰居的鄰居構(gòu)造樣本進(jìn)行學(xué)習(xí)，這里也暴露出LINE方法僅考慮一階和二階相似性裁赠，對(duì)高階信息的利用不足殿漠。
新加入頂點(diǎn)
對(duì)于新加入圖的頂點(diǎn) ，若該頂點(diǎn)與圖中頂點(diǎn)存在邊相連佩捞，我們只需要固定模型的其他參數(shù)绞幌，優(yōu)化如下兩個(gè)目標(biāo)之一即可：
若不存在邊相連，則需要利用一些side info一忱，留到后續(xù)工作研究莲蜘。
LINE核心代碼
模型和損失函數(shù)定義
LINE使用梯度下降的方法進(jìn)行優(yōu)化，直接使用tensorflow進(jìn)行實(shí)現(xiàn)掀潮，就可以不用人工寫參數(shù)更新的邏輯了~
這里的 實(shí)現(xiàn)中把1階和2階的方法融合到一起了菇夸，可以通過(guò)超參數(shù)order控制是分開(kāi)優(yōu)化還是聯(lián)合優(yōu)化，論文推薦分開(kāi)優(yōu)化仪吧。
首先輸入就是兩個(gè)頂點(diǎn)的編號(hào)庄新，然后分別拿到各自對(duì)應(yīng)的embedding向量，最后輸出內(nèi)積的結(jié)果。 真實(shí)label定義為1或者-1择诈，通過(guò)模型輸出的內(nèi)積和line_loss就可以優(yōu)化使用了負(fù)采樣技巧的目標(biāo)函數(shù)了~
def line_loss(y_true, y_pred):
return -K.mean(K.log(K.sigmoid(y_true*y_pred)))
def create_model(numNodes, embedding_size, order='second'):
v_i = Input(shape=(1,))
v_j = Input(shape=(1,))
first_emb = Embedding(numNodes, embedding_size, name='first_emb')
second_emb = Embedding(numNodes, embedding_size, name='second_emb')
context_emb = Embedding(numNodes, embedding_size, name='context_emb')
v_i_emb = first_emb(v_i)
v_j_emb = first_emb(v_j)
v_i_emb_second = second_emb(v_i)
v_j_context_emb = context_emb(v_j)
first = Lambda(lambda x: tf.reduce_sum(
x[0]*x[1], axis=-1, keep_dims=False), name='first_order')([v_i_emb, v_j_emb])
second = Lambda(lambda x: tf.reduce_sum(
x[0]*x[1], axis=-1, keep_dims=False), name='second_order')([v_i_emb_second, v_j_context_emb])
if order == 'first':
output_list = [first]
elif order == 'second':
output_list = [second]
else:
output_list = [first, second]
model = Model(inputs=[v_i, v_j], outputs=output_list)
頂點(diǎn)負(fù)采樣和邊采樣
下面的函數(shù)功能是創(chuàng)建頂點(diǎn)負(fù)采樣和邊采樣需要的采樣表械蹋。中規(guī)中矩，主要就是做一些預(yù)處理羞芍，然后創(chuàng)建alias算法需要的兩個(gè)表哗戈。
def _gen_sampling_table(self):
# create sampling table for vertex
power = 0.75
numNodes = self.node_size
node_degree = np.zeros(numNodes) # out degree
node2idx = self.node2idx
for edge in self.graph.edges():
node_degree[node2idx[edge[0]]
] += self.graph[edge[0]][edge[1]].get('weight', 1.0)
total_sum = sum([math.pow(node_degree[i], power)
for i in range(numNodes)])
norm_prob = [float(math.pow(node_degree[j], power)) /
total_sum for j in range(numNodes)]
self.node_accept, self.node_alias = create_alias_table(norm_prob)
# create sampling table for edge
numEdges = self.graph.number_of_edges()
total_sum = sum([self.graph[edge[0]][edge[1]].get('weight', 1.0)
for edge in self.graph.edges()])
norm_prob = [self.graph[edge[0]][edge[1]].get('weight', 1.0) *
numEdges / total_sum for edge in self.graph.edges()]
self.edge_accept, self.edge_alias = create_alias_table(norm_prob)
LINE 應(yīng)用
和之前一樣，還是用LINE在wiki數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類任務(wù)和可視化任務(wù)荷科。 wiki數(shù)據(jù)集包含 2,405 個(gè)網(wǎng)頁(yè)和17,981條網(wǎng)頁(yè)之間的鏈接關(guān)系唯咬，以及每個(gè)網(wǎng)頁(yè)的所屬類別。 由于1階相似度僅能應(yīng)用于無(wú)向圖中畏浆，所以本例中僅使用2階相似度胆胰。
G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])
model = LINE(G,embedding_size=128,order='second')
model.train(batch_size=1024,epochs=50,verbose=2)
embeddings = model.get_embeddings()
evaluate_embeddings(embeddings)
plot_embeddings(embeddings)
分類任務(wù)結(jié)果
micro-F1: 0.615
macro-F1: 0.500
可視化結(jié)果
