Graph Embedding

Graph Embedding

DeepWalk

Paper : DeepWalk: Online Learning of Social Representations

Paper : Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

DeepWalk = Random Walk + Skip-gram

• DeepWalk在由物品组成的图结构上进行随机游走，产生大量的物品序列，然后将这些物品序列作为训练样本输入Word2Vec进行训练，得到物品Embedding

• 算法流程

  • 构建物品关系图：若某用户先后（紧邻）购买了物品$A$与物品$B$，那么建立有向边$A\to B$。如果后续产生多条相同的有向边，则该有向边的权重被加强

  • 采用DeepWalk产生物品序列：随机选择起始节点，当物品关系图为有向有权图时，DeepWalk的跳转概率为（到达节点$v_i$后，下一步遍历节点$v_j$的概率）

    $$P\left(v_j\mid v_i\right)=\{\begin{array}{ll}\frac{{\mathbf{M}}_{ij}}{{\sum }_{j\in N_{+}\left(v_i\right)}}{\mathbf{M}}_{ij},& v_j\in N_{+}\left(v_i\right),\\ 0,& e_{ij}\notin \mathcal{E},\end{array}$$
    $\mathcal{E}$为边集合，$N_{+}\left(v_i\right)$为节点$v_i$的出边集合，$M_{ij}$为节点$v_i$到节点$v_j$的权重

  • 若物品关系图为无向无权图，将边权当作“1”，出边集合改为边集合，套用上式公式处理即可

  

Node2Vec

Paper : node2vec: Scalable Feature Learning for Networks

Node2Vec

• Node2Vec在DeepWalk的基础上增加了两种Graph Embedding的概念

  • 图的同质性

    Homophily

    • 指距离相近节点的Embedding应尽量相似（节点$u$与其相连的节点$s_1$、$s_2$、$s_3$、$s_4$的Embedding表达应该是接近的）

    • 为了使Graph Embedding的结果能够表达网络的“结构性”，在随机游走的过程中，需要让游走的过程更倾向于BFS，因为BFS会更多地在当前节点的邻域中游走遍历，相当于对当前节点周边的网络结构进行一次“微观扫描”。当前节点是“局部中心点”，还是“边缘节点”，或是“连接性节点”，其生成序列包含的节点数量和顺序必然是不同的，从而让最终的Embedding抓取到更多结构性信息

  • 图的结构性

    Structural Equivalence

    • 指结构上相似的节点的Embedding应尽量相似（节点$u$与$s6$都是各自局部网络的中心节点，结构上相似，其Embedding的表达也应该相似）

    • 为了表达“同质性”，需要让随机游走倾向于DFS，因为DFS更有可能通过多次跳转游走到远方的节点上。DFS的游走更大概率会在一个大的集团内部进行，这就使得一个集团或者社区内部的节点的Embedding更为相似，从而更多地表达网络的“同质性”

  

• 假设Node2Vec从节点$t$跳到节点$v$，再从节点$v$跳转到周围各点

  • 从节点$v$跳转到下一个节点$x$的概率

    $${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$$
    其中$w_{vx}$为边$vx$权重，${\alpha }_{pq}(t,x)$定义如下

    $${\alpha }_{pq}(t,x)=\{\begin{array}{ll}\frac{1}{p}& \text{ if }{d}_{tx}=0\\ 1& \text{ if }{d}_{tx}=1\\ \frac{1}{q}& \text{ if }{d}_{tx}=2\end{array}$$
    其中$d_{tx}$指节点$t$到节点$x$的距离，参数$p$和$q$共同控制着随机游走的倾向性。参数$p$被称为返回参数（Return Parameter），$p$越小，随机游走回节点$t$的可能性越大，Node2Vec就更注重表达网络的结构性；参数$q$为进出参数（In-out Parameter），$q$越小，随机游走到远方节点的可能性越大，Node2Vec就更注重表达网络的同质性

  

• Embedding结果：上图体现同质性，下图体现结构性，颜色越相近的节点Embedding越相近

  

LINE

Paper : LINE: Large-scale Information Network Embedding

LINE

SDNE

Paper : Structural Deep Network Embedding

SDNE

TADW

Paper : Network Representation Learning with Rich Text Information

TADW

EGES

Paper : Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba

Enhanced Graph Embedding with Side Information

• 通过引入额外的补充信息（Side Information）丰富Embedding，从而解决冷启动问题

• 除了通过用户行为序列生成物品关系图之外，还可以利用“相同属性”、“相同类别”等信息建立物品之间的边，生成基于内容的知识图谱。基于知识图谱生成的物品向量可以作为补充信息的Embedding向量

• EGES利用Attention对多个Embedding向量进行融合