Graph Embedding
1.Deepwalk
采用随机游走的方式得到图上结点的序列
2.LINE
一阶：当两个结点边的权重很大时，说明可能是相似的
二阶：如果两个结点的邻居结点相同，说明可能是相似的
DeepWalk在无向图上，LINK在有向图和无向图皆可
一阶相似性
求节点i和节点j的联合概率分布：节点i和节点j的embedding经过一个sigmoid函数得到。
求节点i和节点j的经验概率分布：节点i和节点j相连的边的权重除以所有边的权重的和
然后求两个分布的距离，距离越小说明学出来的embedding效果越好，用KL-divergence来求距离
将得到的距离作为loss函数，训练出最小的距离，得到每个向量的embedding表示
二阶相似性
定义每个节点有两个表示
有向图的经验概率的分母不再是所有边的权重，当求给定顶点vi条件下，产生邻居顶点vj的概率，分母为顶点vi的出边的权重和。
同样，得到两个概率分布，使用KL-divergence求出最小距离，当做loss函数，利用反向传播，得到了每一个节点本身的embedding和该节点作为其他节点邻居时的表示向量的embedding，最后选择顶点本身的embedding作为该节点的二阶相似性
一阶和二阶训练完之后，将两个向量组合成一个embedding，使用拼接的方法
3.Node2vec
同质性表示节点跟周围节点的embedding应该是很相似的，如图中右侧第一个图，每种颜色代表节点的相似性
结构等价性表示节点在图中的位置很相似，如图中右侧第二个图，所有蓝色节点都是连接两个簇的，所以它们的embedding是很相似的
该算法也是采用随机游走的方式，但与DeepWalk不同的是，该游走是一种有策略的游走方式
假设已经从t节点游走到了v节点，可以从v节点游走到x1、x2、x3或者t节点，计算v节点游走到其他节点的概率，表示为πvx，πvx=αpq(t,x)\*wvx，其中wvx表示节点v到节点x的权重，αpq(t,x)的公式如下图所示，其中，dtx=0表示从v节点游走到距离t节点距离为0的节点的概率（也就是从t走到v再走到t的概率），dtx=1表示从v节点游走到距离t节点距离为1的节点的概率。dtx=2表示从v节点游走到距离t节点距离为2的节点的概率
举例：
t->v->z:0因为v到z无边，权值为0
t->v->t:wvt*1/p因为v到t的权值为wvt，又dtx=dtt=0，故αpq=1/p
t->v->x1:wvx1*1因为v到x1的权值为wvx1，有dtx=dtx1=1，故αpq=1
算法如下：
不同的参数值对最后的结果是不同的，当q较小时，1/q较大，说明节点的游走会沿着距离当前节点较远的方向游走。同理相反
4.Struc2vec
node embedding的方式，都基于近邻关系，有些节点没有近邻，但也有相似的结构性
下图定义了距离信息fk(u,v)和它的计算：
如何求g(D1,D2)?
求出来的两个节点的距离就可以表示两个节点在图中的结构相似性，而不考虑他们的邻接点
算法流程：
Struct2vec适用于节点分类中，其结构标识比邻居标识更重要的是，采用Struct2vec效果好。
5.SDNE
之前的DeepWalk，LINK。node2vec，struct2vec都采用了浅层的结构，浅层模型往往不能捕获高度非线性的网络结构。即产生了SDNE方法，使用多个非线性层来捕获node的embedding
引入深度学习方法
使用Encoder-decoder来表示向量，通过输入和输出向量的均方误差计算L2nd，其中引入一个bi，这个bi表示，如果si跟sj是不连接的，bij=1，否则为一个大于1的数，也就是说，如果两个点是连接的，更关注decoder之后能否表现出两个点连接的性质，即考虑点的二阶相似度。
还引入了一阶相似度，一阶相似度考虑的是连接的节点，xi和xj都经过一个Encoder得到一个embedding，计算两个embedding的误差，在误差最小的情况下，就表示两个节点的一阶相似度
最后，将得到的一阶误差，二阶误差和一个正则项加在一起得到了整体误差，通过反向传播，就学习到了模型上的一些参数，然后可以计算出节点的embedding
总结
在日常使用中，要根据图结构和下游任务，深入了解每一种算法的本质去选择对应的算法，这样才能得到更好的效果。