Loading...
墨滴

cpgsmldl

2021/06/05  阅读:56  主题:橙心

DeepWalk算法原理小结

近年来,图神经网络 (GNN) 在各个领域越来越受欢迎,包括社交网络、知识图谱、推荐系统等。

图是由两个部件组成的一种数据结构:顶点(vertices)/节点(nodes)边 (edges)。一个图 G 可以用它包含的顶点 V 和边 E 的集合来描述。

图又分为有向图无向图,这取决于顶点之间是否存在方向依赖关系。

介绍 DeepWalk 之前简单描述一下Graph Embedding 技术,简单点说 Graph Embedding 技术就是得到图中每个节点的向量表示,之后就可以用得到的向量做各种各样的事情。

DeepWalk

DeepWalk 的思想类似 word2vec,使用图中节点与节点的共现关系来学习节点的向量表示。那么关键的问题就是如何来描述节点与节点的共现关系,DeepWalk给出的方法是使用随机游走(RandomWalk)的方式在图中进行节点采样。

算法包括两个步骤:

  • step1: 在图中的节点上执行随机游走生成节点序列
  • step2: 运行skip-gram,根据步骤 1 中生成的节点序列学习每个节点的嵌入

在随机游走过程中,下一个节点是从前一节点的邻居统一采样。然后将每个序列截短为长度为2|w|+1的子序列,其中 w 表示 skip-gram 中的窗口大小。

在论文中,使用分层softmax解决节点数量庞大导致softmax计算成本过高的问题。

伪代码:

DeepWalk 的主要问题是缺乏泛化能力。每当一个新节点出现时,它必须重新训练模型以表示这个节点。因此这种 GNN 不适用于图中节点不断变化的动态图(需要解决 embedding 冷启动问题)。

参考

  1. DeepWalk: Online Learning of Social Representations
  2. 【Graph Embedding】DeepWalk:算法原理,实现和应用
  3. 了解图神经网络GNN和2种高级算法「DeepWalk」+ 「GraphSage」

cpgsmldl

2021/06/05  阅读:56  主题:橙心

作者介绍

cpgsmldl