本文轉(zhuǎn)載自【Graph Embedding】LINE：算法原理，實現(xiàn)和應(yīng)用 - 淺夢的文章 - 知乎
https://zhuanlan.zhihu.com/p/56478167

之前介紹過DeepWalk，DeepWalk使用DFS隨機游走在圖中進行節(jié)點采樣，使用word2vec在采樣的序列學(xué)習(xí)圖中節(jié)點的向量表示。ref: DeepWalk

LINE也是一種基于鄰域相似假設(shè)的方法，只不過與DeepWalk使用DFS構(gòu)造鄰域不同的是，LINE可以看作是一種使用BFS構(gòu)造鄰域的算法。此外，LINE還可以應(yīng)用在帶權(quán)圖中(DeepWalk僅能用于無權(quán)圖)。

LINE 原文： [1503.03578] LINE: Large-scale Information Network Embedding (arxiv.org)

之前還提到不同的graph embedding方法的一個主要區(qū)別是對圖中頂點之間的相似度的定義不同，所以先看一下LINE對于相似度的定義。

LINE算法原理

一種新的相似度定義

first-order proximity（一階相似度）

1階相似度用于描述圖中成對頂點之間的局部相似度，形式化描述為若 ,之間存在直連邊，則邊權(quán)即為兩個頂點的相似度，若不存在直連邊，則1階相似度為0。 如上圖，6和7之間存在直連邊，且邊權(quán)較大，則認為兩者相似且1階相似度較高，而5和6之間不存在直連邊，則兩者間1階相似度為0。

second-order proximity

僅有1階相似度就夠了嗎？顯然不夠，如上圖，雖然5和6之間不存在直連邊，但是他們有很多相同的鄰居頂點(1,2,3,4)，這其實也可以表明5和6是相似的，而2階相似度就是用來描述這種關(guān)系的。形式化定義為，令 表示頂點與所有其他頂點間的1階相似度，則與的2階相似度可以通過和的相似度表示。若與之間不存在相同的鄰居頂點，則2階相似度為0。

優(yōu)化目標(biāo)

1st-order

對于每一條無向邊，定義頂點和之間的聯(lián)合概率為：
，為頂點的低維向量表示。（可以看作一個內(nèi)積模型，計算兩個item之間的匹配程度）

同時定義經(jīng)驗分布，，

優(yōu)化目標(biāo)為最小化:

是兩個分布的距離，常用的衡量兩個概率分布差異的指標(biāo)為KL散度，使用KL散度并忽略常數(shù)項后有

1st order 相似度只能用于無向圖當(dāng)中。

2nd-order

這里對于每個頂點維護兩個embedding向量，一個是該頂點本身的表示向量，一個是該點作為其他頂點的上下文頂點時的表示向量。

對于有向邊，定義給定頂點條件下，產(chǎn)生上下文(鄰居)頂點的概率為

優(yōu)化目標(biāo)為：

優(yōu)化技巧

Negative sampling

由于計算2階相似度時，softmax函數(shù)的分母計算需要遍歷所有頂點，這是非常低效的，論文采用了負采樣優(yōu)化的技巧，目標(biāo)函數(shù)變?yōu)椋?br>

Edge Sampling

注意到我們的目標(biāo)函數(shù)在log之前還有一個權(quán)重系數(shù)，在使用梯度下降法優(yōu)化參數(shù)時，會直接乘在梯度上。如果圖中的邊權(quán)方差很大，則很難選擇一個合適的學(xué)習(xí)率。若使用較大的學(xué)習(xí)率那么對于較大的邊權(quán)可能會引起梯度爆炸，較小的學(xué)習(xí)率對于較小的邊權(quán)則會導(dǎo)致梯度過小。

對于上述問題，如果所有邊權(quán)相同，那么選擇一個合適的學(xué)習(xí)率會變得容易。這里采用了將帶權(quán)邊拆分為等權(quán)邊的一種方法，假如一個權(quán)重為的邊，則拆分后分為個權(quán)重為1的邊。這樣可以解決學(xué)習(xí)率選擇的問題，但是由于邊數(shù)的增長，存儲的需求也會增加。

另一種方法則是從原始的帶權(quán)邊中進行采樣，每條邊被采樣的概率正比于原始圖中邊的權(quán)重，這樣既解決了學(xué)習(xí)率的問題，又沒有帶來過多的存儲開銷。

這里的采樣算法使用的是Alias算法，Alias是一種 時間復(fù)雜度的離散事件抽樣算法。具體內(nèi)容可以參考 https://zhuanlan.zhihu.com/p/54867139

其他問題

低度數(shù)頂點

對于一些頂點由于其鄰接點非常少會導(dǎo)致embedding向量的學(xué)習(xí)不充分，論文提到可以利用鄰居的鄰居構(gòu)造樣本進行學(xué)習(xí)，這里也暴露出LINE方法僅考慮一階和二階相似性，對高階信息的利用不足。

新加入頂點

對于新加入圖的頂點 ，若該頂點與圖中頂點存在邊相連，我們只需要固定模型的其他參數(shù)，優(yōu)化如下兩個目標(biāo)之一即可：

若不存在邊相連，則需要利用一些side info，留到后續(xù)工作研究。

LINE核心代碼

模型和損失函數(shù)定義

LINE使用梯度下降的方法進行優(yōu)化，直接使用tensorflow進行實現(xiàn)，就可以不用人工寫參數(shù)更新的邏輯了~

這里的 實現(xiàn)中把1階和2階的方法融合到一起了，可以通過超參數(shù)order控制是分開優(yōu)化還是聯(lián)合優(yōu)化，論文推薦分開優(yōu)化。

首先輸入就是兩個頂點的編號，然后分別拿到各自對應(yīng)的embedding向量，最后輸出內(nèi)積的結(jié)果。 真實label定義為1或者-1，通過模型輸出的內(nèi)積和line_loss就可以優(yōu)化使用了負采樣技巧的目標(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)

頂點負采樣和邊采樣

下面的函數(shù)功能是創(chuàng)建頂點負采樣和邊采樣需要的采樣表。中規(guī)中矩，主要就是做一些預(yù)處理，然后創(chuàng)建alias算法需要的兩個表。

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ù)集上進行節(jié)點分類任務(wù)和可視化任務(wù)。 wiki數(shù)據(jù)集包含 2,405 個網(wǎng)頁和17,981條網(wǎng)頁之間的鏈接關(guān)系，以及每個網(wǎng)頁的所屬類別。 由于1階相似度僅能應(yīng)用于無向圖中，所以本例中僅使用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é)果

參考資料

Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.