DeepWalk Online Learning of Social Representations

• 概
• 符号说明
• DeepWalk
• 代码

Perozzi B., AI-Rfou R. and Skiena S. DeepWalk: Online learning of social representations. KDD, 2014.

概

经典的 graph embedding 学习方法.

符号说明

• \(V\), node set;
• \(E\), edge set;
• \(G = (V, E)\), 图;

DeepWalk

• DeepWalk 的思想就是把 NLP 中的 skip-gram 搬过来.

• Skip-gram 的任务就是在一串序列

  \[[v_1, v_2, \cdots, v_{i-w}, \cdots, v_{i-1}, v_i, v_{i+1}, \cdots, v_{i+w}, \cdots, v_l] \]

  中, 以某个 \(v_i\) 中心, 窗口大小为 \(w\) 内进行预测:

  \[\min_{\Phi} \quad -\log \mathbb{P}(\{ v_{i-w}, \cdots, v_{i-1}, v_{i+1}, \cdots, v_{i+w} \}| \Phi(v_i)). \]

  其中 \(\Phi(\cdot)\) 将 \(v_i\) 映射为 embedding.

• 在 NLP 中, 序列为 text, 而在图这里, DeepWalk 通过随机游走挑选序列, 其具体流程如下:
  

• 此外, 在概率的计算的时候, 由于图的结点数往往过多, 全量的 softmax 是难以实现的, 故而也采用 Hierarchical Softmax 来近似.

代码

[GraphEmbedding]