转载自【Graph Embedding】DeepWalk：算法原理，实现和应用 - 浅梦的文章 - 知乎
https://zhuanlan.zhihu.com/p/56380812
本文首先从整体介绍一下图表示学习，然后分别从原理，核心代码，应用三个部分介绍DeepWalk。
图表示学习
我们都知道在数据结构中，图是一种基础且常用的结构。现实世界中许多场景可以抽象为一种图结构，如社交网络，交通网络，电商网站中用户与物品的关系等。
目前提到的图算法一般指：
-
经典数据结构与算法层面的：最小生成树(Prim,Kruskal,...)，最短路(Dijkstra,Floyed,...)，拓扑排序，关键路径等
-
概率图模型，涉及图的表示、推断和学习，详细可以参考Koller的书或者公开课
-
图神经网络，主要包括Graph Embedding(基于随机游走)和Graph CNN(基于邻居汇聚)两部分。
这里先看下Graph Embedding的相关内容。
Graph Embedding技术将图中的节点以低维稠密向量的形式进行表达，要求在原始图中相似(不同的方法对相似的定义不同)的节点其在低维表达空间也接近。得到的表达向量可以用来进行下游任务，如节点分类，链接预测，可视化或重构原始图等。
DeepWalk 算法原理
DeepWalk：[1403.6652] DeepWalk: Online Learning of Social Representations (arxiv.org)
虽然DeepWalk是KDD 2014的工作，但却是我们了解Graph Embedding无法绕过的一个方法。
我们都知道在NLP任务中，word2vec是一种常用的word embedding方法，word2vec通过语料库中的句子序列来描述词与词的共现关系，进而学习到词语的向量表示。
DeepWalk的思想类似word2vec，使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系，DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。
RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。给定当前访问起始节点，从其邻居中随机采样节点作为下一个访问节点，重复此过程，直到访问序列长度满足预设条件。
获取足够数量的节点访问序列后，使用skip-gram model进行向量学习。
DeepWalk算法
SkipGram算法
DeepWalk核心代码
DeepWalk算法主要包括两个步骤，第一步为随机游走采样节点序列，第二步为使用skip-gram modelword2vec学习表达向量。
①构建同构网络，从网络中的每个节点开始分别进行Random Walk 采样，得到局部相关联的训练数据；
②对采样数据进行SkipGram训练，将离散的网络节点表示成向量化，最大化节点共现，使用Hierarchical Softmax来做超大规模分类的分类器
Random Walk
我们可以通过并行的方式加速路径采样，在采用多进程进行加速时，相比于开一个进程池让每次外层循环启动一个进程，我们采用固定为每个进程分配指定数量的num_walks的方式，这样可以最大限度减少进程频繁创建与销毁的时间开销。
deepwalk_walk方法对应上一节伪代码中第6行，_simulate_walks对应伪代码中第3行开始的外层循环。最后的Parallel为多进程并行时的任务分配操作。
def deepwalk_walk(self, walk_length, start_node):
walk = [start_node]
while len(walk) < walk_length:
cur = walk[-1]
cur_nbrs = list(self.G.neighbors(cur))
if len(cur_nbrs) > 0:
walk.append(random.choice(cur_nbrs))
else:
break
return walk
def _simulate_walks(self, nodes, num_walks, walk_length,):
walks = []
for _ in range(num_walks):
random.shuffle(nodes)
for v in nodes:
walks.append(self.deepwalk_walk(alk_length=walk_length, start_node=v))
return walks
results = Parallel(n_jobs=workers, verbose=verbose, )(
delayed(self._simulate_walks)(nodes, num, walk_length) for num in
partition_num(num_walks, workers))
walks = list(itertools.chain(*results))
Word2vec
这里就偷个懒直接用gensim里的Word2Vec了。
from gensim.models import Word2Vec
w2v_model = Word2Vec(walks,sg=1,hs=1)
DeepWalk应用
这里简单的用DeepWalk算法在wiki数据集上进行节点分类任务和可视化任务。 wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系，以及每个网页的所属类别。
G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])
model = DeepWalk(G,walk_length=10,num_walks=80,workers=1)
model.train(window_size=5,iter=3)
embeddings = model.get_embeddings()
evaluate_embeddings(embeddings)
plot_embeddings(embeddings)
分类任务结果
'micro-F1': 0.6923076923076923,
'macro-F1': 0.6147590062090043
可视化结果
网友评论