deepwalk

模型：随机截断游走+skipgram+层级softmax
整个过程：

1. 输入：图的边集和点集
2. 使用随机游走来获得结点序列
3. 使用skip-gram算法来获得结点表示
4. 使用层级softmax来优化目标函数
5. 获得输出：结点的潜在表示
   
   具体算法：
   
   

总结：没有一个专门为网络嵌入设计的目标函数、使用二阶相似性（游走序列）来考虑两个结点的相似性。
疑问：两个结点的相似度是怎么样比较出来的？（文中只提到了根据节点计算上下文序列的概率然后生成向量表示，最后映射到如输出图所示的结果）

node2vec

在deepwalk的基础上改进了采样策略（基于BFS和DFS采样获取结点的邻居序列，而不是通过随机游走来获取的）。文中提到了两种相似性：homophily（同质性）和structual equivalence（结构同等性），如图所示，u与s1是同质性相似，而u与s6则是结构同等性相似。

基于这两种相似性，改进了deepwalk的随机游走算法：



具体算法：

总结：node2vec改进了deepwalk算法，可以实现基于BFS和DFS的游走序列（采样策略不同）。
疑问：是不是没有损失函数？本文中目标函数不是损失函数？结点的相似度又是怎么比较的？一种想法：在游走的时候获得的游走序列（同质性的或者结构同等性的）算的所谓的上下文概率就是两个结点的相似度比较？（而不是类似于欧几里得距离或者cos相似性计算）

struct2vec

node2vec的限制：采样的结点序列会受到游走长度的限制（邻居只能是相连的）或者是滑动窗口的大小的限制。在现实中，往往也有很多结点即使离的很远，甚至不相连，但是是相似的。如图所示：结点u和v虽然不相连，也没有共享邻居但是structural identity相似（结构角色？）根据结点的度来判断这两个结点是否相似（当邻居节点的度也相等时则更加相似）。

具体算法：

1. 分级评估结点相似性
   
   两个度序列的距离计算使用DTM算法来计算。

2. 构建多层图
   
   此时权重有同一层间的权重Ui与Uj，也有不同层间的权重（上层和下层权重不同）。不同层之间的权重是Uik与Uik+1（即：一个结点在当前层与此结点在上层或下层的连接权重，而不是与其他结点的连接权重）
   
   
   
   
   
   
   
   

3. 游走于多层图获得序列（按度从小到大排序）比较两个度序列的距离

4. Skip-gram产生潜在表示（最后的输出是向量，所以相似度是不是可以用欧几里得或者cos来计算？）
   总结：node2vec虽然扩展了“邻居”的定义（更加灵活），但是结构相似的点不共享相同的上下文（游走窗口大小的限制）。deepwalk和node2vec在结构性的分类任务中会失效（只考虑了同质性但是没有考虑结构同等性）
   疑问：当度的大小相同时，两个点按照什么顺序排序？不同层之间的权重可以是不同结点之间的吗，而不仅仅是同个结点的上下层权重？

LINE

LINE（2015年发表，deepwalk是2014年）中提出了对一阶相似性的定义，以及补充了二阶相似性。分开进行最后再组合。
一阶相似性：直接相连的两个结点
二阶相似性：两个结点共享有相同的邻居节点
如图所示：结点6,7是一阶相似，结点5,6是二阶相似。

一阶：



二阶：此时一个结点有两个身份：结点本身和某个结点邻居序列中的一个上下文结点。


lambda取决于结点的出度。
疑问：怎么组合的一阶和二阶？文中说的是未来需要完成的工作。