标签搜索

目 录CONTENT

文章目录

Node Embedding

陈铭
2024-05-26 / 0 评论 / 0 点赞 / 103 阅读 / 724 字 / 正在检测是否收录...

DeepWalk

论文出处:https://arxiv.org/pdf/1403.6652.pdf

算法:
ec6e1c57b2d4003962c214a2825f302c_4cbe65b643364d78b73f35348d5db7be

DeepWalk的思想是:对于图中的每个结点,我们都要以它为起点生成 γ \gammaγ 个具有最大长度的随机游走序列,最终会得到 ∣ V ∣ ⋅ γ |V|\cdot \gamma∣V∣⋅γ 个序列。将每一个序列看成一个句子,将其中的结点看成单词,于是我们可以对这些序列应用 Word2Vec(Skip-Gram + Hierachical Softmax) 得到结点的嵌入表示。

在上图中,w ww 是窗口大小,即在 Skip-Gram 模型中,用中心词预测 2 w 2w2w 个上下文词;d dd 是结点向量的维度;γ \gammaγ 决定了对于图中的每一个结点,我们要以它为起点生成多少个随机游走序列;t tt 是随机游走序列的最大长度。

简单实现

以无向图为例,假设结点都用整型数字标识,相应实现如下

import random
from gensim.models import Word2Vec


def random_walk(graph, root, walk_length):
	# graph为networkx中的无向图类型,root为整型
	# 该函数每次只生成一个随机游走序列
    seq = [root]
    for _ in range(walk_length - 1):
        seq.append(random.choice(list(graph.neighbors(seq[-1]))))
    return seq


def deep_walk(graph, windows_size, embed_size, gamma, walk_length):
    seqs = [random_walk(graph, node, walk_length) for node in graph.nodes for _ in range(gamma)]
    model = Word2Vec(seqs, vector_size=embed_size, window=windows_size, sg=1, hs=1)
    return model.wv

Node2Vec

论文出处:https://arxiv.org/pdf/1607.00653.pdf

DeepWalk 实际上就是把 Word2Vec 用在了图上,Node2Vec 在 DeepWalk 的基础上进行了改进,把完全随机游走(假设一个结点有 N NN 个邻居结点,则下一步到每个邻居结点的概率都为 1 / N 1/N1/N)改成了有偏随机游走(下一步到每个邻居结点的概率不同)。

如下图,Node2Vec 使用的是二阶随机游走,即下一步往哪里走不仅取决于当前结点,还取决于上一结点:
6d5dc556e9666a71d313039ac4622b22_ca058eddd4f348c1807255c9154a0b22

算法:
f10f106e2fa27c0dbae24800be750db6_87062d5968044b79af14b28dda2c90f7

通过伪代码可以看出,该算法与 DeepWalk 的主要区别在于结点的采样策略。因为 DeepWalk 是完全随机游走,所以每次只需要从邻居结点中随机选取一个就OK了,而 Node2Vec 是有偏随机游走,所以需要用到 Alias Sampling 技术,它的时间复杂度是 O ( 1 ) O(1)O(1)(空间换时间)。

有关 Alias Sampling 可参考:https://www.keithschwarz.com/darts-dice-coins/。

简单实现

目前有现成的第三方库(基于NetworkX和Gensim),项目地址:https://github.com/eliorc/node2vec。

from node2vec import Node2Vec

G = nx.les_miserables_graph()
model = Node2Vec(G, dimensions=32, walk_length=3, num_walks=600, p=2, q=0.5, workers=4).fit(window=3,
                                                                                            min_count=1,
                                                                                            batch_words=4)
0

评论区