算法论文笔记——GraphEmbedding

GraphEmbedding

本篇笔记简要介绍几种图嵌入算法的原理，不涉及推理和code。想要深入了解的朋友可以点击以下链接。
Git实现 https://github.com/totoroyun/GraphEmbedding.
参考文章 https://zhuanlan.zhihu.com/weichennote.

1.DeepWalk

DeepWalk的思想类似word2vec，使用图中节点与节点的共现关系来学习节点的向量表示，使用随机游走(RandomWalk)的方式在图中进行节点采样构建序列库。
优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大。

2.Line

LINE也是一种基于邻域相似假设的方法，考虑一阶和二阶相似度，1阶相似性认为两个顶点的边权重越大，两个顶点越相似；2阶相似性认为两个顶点的共同邻居越多，两个顶点越相似。
1阶相似度只适用于无向无权图。
2阶相似度可用于有向带权图。
令 p_u 表示顶点 u与所有其他顶点间的1阶相似度，则 p_u 与 p_v 的2阶相似度可以通过p_u 和 p_v 的相似度表示。若p_u 和 p_v 之间不存在相同的邻居顶点，则2阶相似度为0。

优化目标：

我们认为两点越相似嵌入的向量在低纬空间中应该越接近，即P值接近1，经验概率是真实的相似度，目标是希望两者分布近似，即学习向量后计算的概率逼近真实概率，通过最小化目标函数反向传播更新权重。目标函数类似交叉熵。

我们认为给定中心点，该点的邻居点出现的条件概率应该比其他点大，经验概率是网络中真实的条件概率（与权重相关），目标是希望两者分布近似，即学习向量后计算的条件概率逼近真实条件概率，通过最小化目标函数反向传播更新权重。
注：一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的（N2V使用的是相同的向量）；
一阶相似度和二阶相似度是算法的方法参数，使用时需要选择order。

3.Node2Vector

N2V在DeepWalk的基础上加入边权，并控制游走的内外向，综合考虑了DFS邻域和BFS邻域。优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大，这一点与DeepWalk一致，不过N2V的关键在于有偏的采样策略，它使用了更丰富的网络信息，构建的序列库与DeepWalk不同。适用于有向带权网络。
p，q一般采用网格搜索设置。

4.SDNE

5.Struc2Vec