Loading... [DeepWalk: Online Learning of Social Representations](https://arxiv.org/abs/1403.6652) ## 1 算法原理 DeepWalk使用图中节点与节点的共现关系来学习节点的向量表示，其核心算法包含两个步骤，如图1所示： (1)使用随机游走(RandomWalk)的方式在图中进行节点采样获得节点与节点的共现关系； (2)将节点类比成单词，随机游走序列类比成句子，使用SkipGram算法，获得节点的向量表示。  ### 1.1 RandomWalk 随机游走是一种可重复访问节点的深度优先遍历算法。基本思想为：从一个节点出发，随机移动到该节点的一个邻居节点，并将该邻居节点作为新的当前节点，如此循环执行若干步，可得到一串随机游走序列，该随机游走序列可以反映出图的社群结构信息。 DeepWalk使用的是截断式随机游走，即具有最大长度限制的随机游走。截断式随机游走是对图局部信息的一种探索方式，可以同时探索同一个图的不同部分，具有很好的可并行性。同时，截断式随机游具有较好的局部适应性，当图结构发生微小变化时，可以使用新的截断式随机游走来迭代地更新学习模型，而不用重新计算整个图的随机游走。 ### 1.2 SkipGram 短的随机游走序列中节点出现的频率与自然语言中单词出现的频率具有类似的分布(幂律分布)，将图中的节点视为单词，将随机游走序列视为句子，则可类比自然语言的建模方法对网络中的社区结构进行建模。于是根据随机游走中已经过的节点来预测下一个节点的概率可表示为： $$ \Pr(v_i \mid (\Phi(v_1),\Phi(v_2),...\Phi(v_{i-1})) $$ 其中$\Phi(v_i)$将节点$v_i$映射为一个d维向量。但是，这种使用上下文来预测缺失词的方法会随着随机游走序列长度的增加，计算变得十分困难，SkipGram恰好能解决这个问题。 SkipGram是一种自监督语言模型，该模型使用中心词预测上下文，即求$\Phi(v_i)$使得窗口 w 内的单词之间的共现概率$\Pr(\{v_{i-w},...,v_{i+w}\} \setminus v_i \mid \Phi(v_i))$最大。因此其损失函数可定义为： $$ \mathcal L = -\log\Pr(\{v_{i-w},...,v_{i+w}\} \setminus v_i \mid \Phi(v_i)) $$ 该模型假设窗口w内的单词相互独立，于是可用下式进行计算： $$ \Pr(\{v_{i-w},...,v_{i+w}\} \setminus v_i \mid \Phi(v_i)) = \prod_{j=i-w \ j\ne i}^{i+w}\Pr(v_j \mid \Phi(v_i)) $$ SkipGram算法使用梯度下降优化模型，算法具体流程如图2所示。可以使用Softmax回归对第3行的后验分布进行建模，但当节点数量过多时，Softmax回归的归一化项难以计算。DeepWalk使用分层Softmax对其进行优化，将n分类问题转化成 次的二分类问题，从而降低了计算量。  ## 2 代码实现 生成单个随机游走序列：对于给定的起始节点start_node，如果其有邻居节点，则从其邻居节点中随机选择一个作为新的起始节点，并将其添加到随机游走序列walk中，如此循环，直到随机游走序列的长度达到设定的最大长度walk_length。具体代码如下所示： ```Python def random_walk(self, start_node, walk_length): walk = [start_node] while len(walk) < walk_length: nbrs = list(self.G.neighbors(start_node)) # 邻居节点 if len(nbrs) > 0: random_node = random.choice(nbrs) # 随机选择一个节点 walk.append(random_node) start_node = random_node else: break return walk ``` 生成所有节点的随机游走序列：遍历图中的所有节点num_walks次，对每个节点调用random_walk方法生成长度最大为walk_length的随机游走序列，最后将所有的随机游走序列转成字符串类型，以便后续处理。具体代码如下所示： ```Python def simulate_walks(self, num_walks=args.num_walks, walk_length=args.walk_length): walks = [] nodes = list(self.G.nodes()) print("Walking...") for _ in tqdm(range(num_walks)): random.shuffle(nodes) for cur in nodes: walks.append(self.random_walk(cur, walk_length)) # 转成字符串格式 for walk in walks: self.walks_str.append([str(x) for x in walk]) ``` genism库中的Word2Vec实现了SkipGram，可以将单词转换为词向量。其中sentences是供训练的语料，即所有节点的随机游走序列；vector_size是生成的词向量维度；window是窗口大小；min_count=0表示不忽略低频词；sg=1表示使用SkipGram算法；hs=1表示使用分层Softmax优化计算；workers用于指定训练模型时使用的线程数。最后，将得到词向量保存到文件中。具体代码如下所示： ```Python def learn_embeddings(self): print("Learning...") model = Word2Vec(sentences=self.walks_str, vector_size=args.dimensions, window=args.window_size, min_count=0, sg=1, hs=1, workers=args.workers) self.wv = model.wv # 保存 filename, suf = os.path.splitext(self.dataset_name) filename += ".embeddings" path = os.path.join(args.save_dir, filename) model.wv.save_word2vec_format(path) ``` ## 3 实验分析 以下使用DeepWalk算法在Karate Club数据集和BlogCatalog数据集进行了实验，两个数据集分别采用的参数如表所示。 | 参数 | Karate Club | BlogCatalog | 说明 | | ----------- | ----------- | ----------- | ------------------------------------------ | | dimensions | 2 | 128 | 节点嵌入向量维度 | | walk_length | 40 | 80 | 随机游走序列最大长度 | | num_walks | 10 | 10 | 每个节点作为起始节点生成的随机游走序列个数 | | window_size | 10 | 10 | 窗口大小 | | workers | 2 | 10 | 线程数 | ### 3.1 Karate Club数据集测试结果 通过DeepWalk算法将Karate Club数据集中的节点表示为2维向量，然后将节点的向量表示作为K均值聚类算法的输入，分别将图中的节点聚类为4类和2类。 图3是将图中的节点聚类为4类的可视化结果，图4是将图中的节点聚类为2类的可视化结果，图中不同的颜色代表不同的类别。其中图3(a)和图4(a)展示了聚类结果在原图结构中的效果，图3(b)和图4(b)展示了节点嵌入向量在二维空间的分布信息，可以看到在原图中具有相似社群结构的节点，嵌入编码成低维向量后，在低维空间仍然相近，且具有线性可分的决策边界。   ### 3.2 BlogCatalog数据集测试结果 使用DeepWalk对BlogCatalog数据集进行处理，将节点嵌入成128维的向量，然后从标记的节点中随机抽取一部分(TR, 10%~90%)作为训练集，其余部分作为测试集，使用one-vs-rest逻辑回归进行多标签分类，并计算macro-F1和micro-F1分数，实验结果如表2-2所示（使用DeepWalk论文作者提供的测试脚本，未标粗的部分是我的实验结果，标粗部分是作者论文中给出的实验结果） 实验结果显示，在网络的标签较为稀疏的情况下，DeepWalk也能取得不错的性能。  ## 4 总结 本章简述了DeepWalk的算法原理，完成了代码复现，并分别在Karate Club和BlogCatalog数据集上进行了测试，测试结果与预期相符，即DeepWalk能够有效地将网络节点的社群结构信息嵌入到低维的向量空间中。 DeepWalk对语言模型进行了推广，将图与自然语言相联系，把语言模型看作是从不可见的语言图中采样，提供了一种新的研究思路。 DeepWalk的缺点也较为明显，DeepWalk没有关注边权信息，仅通过在图中进行完全随机的游走去获取图中节点的局部特征，因此仅能反映相邻节点的社群相似信息，而无法反映节点的功能角色信息。当两个节点相距较远，但具有相似的功能时，DeepWalk无法捕捉到这种信息。 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏