Graph embedding

深碍√TFBOYSˉ_ 2022-09-07 14:55 174阅读 0赞

# 为什么要有Graph embedding #

在图上要表示一个节点，可以使用one-hot来表示，而使用这种方法有两个缺点：

1.  如果节点数量比较多，那么n维的one-hot会非常稀疏；
2.  使用one-hot丢失了节点在图上的连接信息。

# DeepWalk #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]  
为了使用无监督的方式训练每一个节点的embedding，我们会联想到word-embedding的方式，而word-embedding需要语料来训练每一个词的embedding，但是在图上没有一个有序的语料，所以在图上就产生了随机游走的方式来获得序列，利用Word2vec得到每个节点的embedding。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]  
上图中，使用skipGram，在给定 v 4 v\_4 v4的情况下 v 2 , v 3 , v 5 , v 6 v\_2,v\_3,v\_5,v\_6 v2,v3,v5,v6同时出现的概率是多少，window size表示向前或者向后看多少个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 2]  
因为Graph embedding是通过无监督的方式训练的，那么如何评价表示出来的节点的好坏？答案就是需要一个分类器，将学习到的embedding投入分类器中进行分类，判断是否在正确的类别。

使用deep walk进行实战：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 3]

效果还是比较可观的。

# LINE：Lage-scale Information Network Embedding #

如果在大规模的图上做embedding，LINE会达到比较好的效果。

LINE中有两个中心思想：

1.  一阶相似性：局部的结构信息
2.  二阶相似性：节点的邻居。共享邻居的节点可能是相似的。

作者提出LINE如果在节点度比较低的情况下，效果不是很好，因为节点度比较低时，所连接的邻居信息就会比较少，所以二阶相似性不会很好。

同时DeepWalk在无向图上，LINE可以在有向图中使用。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 4]  
上图表示一阶相似性步骤：

1.  随机初始化每一个节点的embedding
2.  利用embedding求出 v i , v j v\_i,v\_j vi,vj的联合概率分布 p 1 ( v i , v j ) = 1 1 + e x p ( − u i T ⋅ u j ) p\_1(v\_i,v\_j)=\\frac\{1\}\{1+exp(-u\_i^T · u\_j)\} p1(vi,vj)=1\+exp(−uiT⋅uj)1
3.  利用权重，求出 v i , v j v\_i,v\_j vi,vj的经验概率分布 p ^ 1 = w i j 其 余 边 的 权 重 \\hat p\_1=\\frac\{w\_\{ij\}\}\{其余边的权重\} p^1=其余边的权重wij
4.  计算联合概率分布和经验概率分布的距离，距离越小说明学习出的embedding越好，使用KL diversion 距离来计算， D K L ( p ∣ ∣ q ) D\_\{KL\}(p||q) DKL(p∣∣q)
5.  经过化简得到损失函数 O 1 = − ∑ ( i , j ) ∈ E W i j log ⁡ p i ( v i , v j ) O\_1=- \\sum\_\{(i,j) \\in E\}W\_\{ij\} \\log p\_i(v\_i,v\_j) O1=−∑(i,j)∈EWijlogpi(vi,vj)

二阶相似性步骤，依然是求出条件概率和经验概率。

得到一阶和二阶的embedding训练完成之后，将他们的embedding直接 contat一个最终的embedding。

# node2vec #

# Struc2vec #

# SDNE #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70]: /images/20220829/32d9170252174cde8dca29fbcb7b6606.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 1]: /images/20220829/007a931d9e1640e183c34d6025d232a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 2]: /images/20220829/052ee8feddbd4573a2190a73ae7a8a50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 3]: /images/20220829/e2d4818f9cfd4ec6840f33698455699b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZpbmNlbnRfZHVhbg_size_16_color_FFFFFF_t_70 4]: /images/20220829/e48a91fac79443c08d0272e96aa80b1c.png